(Avvertimento: Certamente non pretendo che HAVEGE sia all'altezza delle sue affermazioni. Non ho verificato la loro teoria o implementazione.)
Per ottenere la casualità, HAVEGE e sistemi simili si nutrono di "eventi fisici", e in particolare del timing di eventi fisici. Tali eventi includono occorrenze di interruzioni hardware (che, a loro volta, raccolgono dati su battute di tasti, movimenti del mouse, pacchetti Ethernet in arrivo, tempo necessario a un disco rigido per completare una richiesta di scrittura...). HAVEGE afferma inoltre di nutrirsi di tutti i tipi di cache miss che si verificano in una CPU (cache L1, cache L2, TLB, branch forecast...); il comportamento di questi elementi dipende da ciò che la CPU ha fatto nelle precedenti migliaia di cicli di clock, quindi c'è il potenziale per una certa "casualità". Ciò dipende dalla possibilità di misurare l'ora corrente con grande precisione (non necessariamente accuratezza), che è dove rdtsc entra in gioco l'istruzione. Restituisce il contenuto corrente di un contatore interno che viene incrementato a ogni ciclo di clock, quindi offre una precisione inferiore al nanosecondo.
Per un sistema di macchina virtuale, ci sono tre scelte riguardo a questa istruzione:
- Lascia che le istruzioni vadano direttamente all'hardware.
- Trappola l'istruzione ed emulala.
- Disattiva completamente l'istruzione.
Se il gestore della VM sceglie la prima soluzione, allora rdtsc ha tutta la precisione necessaria e dovrebbe funzionare come se fosse su una macchina fisica, allo scopo di raccogliere entropia dagli eventi hardware. Tuttavia, poiché si tratta di una macchina virtuale, è un'applicazione sul sistema host; non riceve sempre la CPU. Dal punto di vista del sistema operativo guest utilizzando rdtsc , sembra che la sua CPU sia stata "rubata" occasionalmente:due rdtsc successivi le istruzioni, nominalmente separate da un singolo ciclo di clock, possono riportare un incremento del contatore di diversi milioni . In poche parole, quando rdtsc viene semplicemente applicato all'hardware, quindi il sistema operativo guest può utilizzarlo per rilevare la presenza di un hypervisor.
La seconda soluzione ha lo scopo di rendere l'emulazione più "perfetta" mantenendo un contatore di cicli virtuale per VM, che tiene traccia dei cicli effettivamente assegnati a quella VM. Il vantaggio è che rdtsc , dal punto di vista dell'ospite, non presenterà più l'effetto "cicli rubati". Lo svantaggio è che questa emulazione viene eseguita attivando e intrappolando un'eccezione della CPU, aumentando il costo del rdtsc opcode da poche decine di cicli di clock (dipende dalla marca della CPU; alcuni eseguono rdtsc in meno di 10 cicli, altri usano 60 o 70 cicli) a più di mille di cicli. Se l'ospite prova a fare un sacco di rdtsc (come sarà incline a fare HAVEGE), quindi rallenterà a passo d'uomo. Inoltre, il codice di gestione delle eccezioni interromperà la misura; invece di misurare la temporizzazione dell'evento hardware, il codice misurerà il tempo di esecuzione del gestore delle eccezioni, il che può plausibilmente abbassare la qualità della casualità estratta.
La terza soluzione (disabilitare rdtsc ) impedirà semplicemente a HAVEGE di restituire una buona casualità. Poiché utilizza internamente un PRNG, l'output può ancora ingannare gli strumenti di analisi statistica, perché c'è un'enorme differenza tra "apparire casuale" ed "essere imprevedibile" (gli strumenti di analisi statistica seguono il percorso "apparire casuale", ma la sicurezza crittografica si basa sull'imprevedibilità ).
Il manuale di VirtualBox afferma che VirtualBox, per impostazione predefinita, segue il primo metodo (rdtsc è incondizionatamente consentito e applicato direttamente sull'hardware), ma può essere configurato per applicare la seconda soluzione (che non vuoi, in questo caso).
Per testare cosa fa la tua VM, puoi provare questo piccolo programma (compila con gcc -W -Wall -O su Linux; il -O è importante):
#include <stdio.h>
#if defined(__i386__)
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ __volatile__ (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
#elif defined(__x86_64__)
static __inline__ unsigned long long rdtsc(void)
{
unsigned hi, lo;
__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}
#endif
int
main(void)
{
long i;
unsigned long long d;
d = 0;
for (i = 0; i < 1000000; i ++) {
unsigned long long b, e;
b = rdtsc();
e = rdtsc();
d += e - b;
}
printf("average : %.3f\n", (double)d / 1000000.0);
return 0;
}
Su una macchina non virtuale, con il "vero" rdtsc , questo riporterà un valore compreso tra 10 e 100, a seconda della marca della CPU. Se il valore riportato è 0, o se il programma va in crash, allora rdtsc è disabilitato. Se il valore è in migliaia, allora rdtsc viene emulato, il che significa che la raccolta di entropia potrebbe non funzionare come previsto.
Nota che anche ottenere un valore compreso tra 10 e 100 non è una garanzia che rdtsc non viene emulato, perché il gestore di VM, pur mantenendo il proprio contatore virtuale, potrebbe sottrargli il tempo previsto necessario per l'esecuzione dell'exception handler. In definitiva, devi davvero dare un'occhiata al manuale e alla configurazione del tuo gestore di macchine virtuali.
Naturalmente, l'intera premessa di HAVEGE è discutibile. Per qualsiasi sicurezza pratica, hai bisogno di pochi bit "casuali reali", non più di 200, che usi come seme in un PRNG crittograficamente sicuro. Il PRNG produrrà gigabyte di pseudo-alea indistinguibili dalla vera casualità, e questo è abbastanza buono per tutti gli scopi pratici.
Insistere per tornare all'hardware per ogni bit sembra l'ennesima esplosione di quell'idea imperfetta che vede l'entropia come una specie di benzina, che bruci quando la guardi.
Sull'avviso polarssl:Una risposta tecnica dettagliata può essere trovata nella fonte debian più recente:
http://bazaar.launchpad.net/~ubuntu-branches/debian/experimental/haveged/experimental/revision/12?start_revid=12#debian/README.Debian
Il sommario esecutivo è:polarssl !=haveged !=HAVEGE
Sugli esperimenti dell'emulatore embloms.se:
Il haveged suite di test, NIST e ent , verificare che una build di origine abbia prodotto un RNG funzionante. Il test in fase di esecuzione è necessario per verificare il funzionamento di haveged in un ambiente virtuale. Questa è un'aggiunta abbastanza recente a haveged.
Sui test statistici:
Supponi di avere un hardware RNG , un TRNG , come fai a sapere che non è rotto? L'hardware si rompe. L'ente standard tedesco ha una specifica che si occupa proprio di questo problema, AIS31 . Questo approccio è adottato da haveged. Una discussione (di parte) sugli standard per RNG così come si applicano a haveged è disponibile all'indirizzo:
http://www.issihosts.com/haveged/ais31.html
La non prevedibilità di HAVEGE è esattamente lo stesso meccanismo visto nel software di benchmarking. Non è dovuto alla deriva del timer, ma all'aggregazione dei comportamenti asincroni in un processore moderno. In realtà non importa se le variazioni delle prestazioni derivano da un fallimento della cache o da un intervallo di tempo consegnato a un altro processore. Anche la precisione del timer non ha importanza fintanto che è "adeguata". Come viene determinato? Dall'uscita. Per progetto (o forse per progetto) /dev/random è immune da dati di input scadenti. L'unico modo per sovvertire il progetto è mentire sull'entropia aggiunta al pool di entropia. Le versioni più recenti di haveged eseguono una stima dell'entropia in fase di esecuzione sull'output generato per assicurare che l'output sia coerente con un TRNG ideale.
Riepilogo esecutivo:haveged l'output è indistinguibile da un TRNG secondo i test utilizzati dall'ente normativo tedesco per certificare TRNG . In caso contrario, haveged si spegnerà.
(Aggiornato , grazie a gwuertz l'attuale autore/manutentore di haveged , ho perso la separazione tra HAVEGE e haveged .)
haveged è un'implementazione distinta del metodo HAVEGE per la generazione di numeri casuali, è aggiornato, mantenuto e documentato qui:http://www.issihosts.com/haveged/ (e non utilizza più libhavege direttamente).
HAVEGE non è molto attuale (2006), sebbene qualcuno l'abbia patchato più recentemente (2009) per velocità e correttezza. Sarei cauto perché non documenta il suo metodo, non menziona le macchine virtuali e, come notato, si basa (pesantemente) su RDTSC (o piattaforma equivalente). (Anche il codice sorgente mi fa rabbrividire, ma è abbastanza soggettivo.)
Sosterrò che la VM host non dovrebbe far trapelare involontariamente alcuno stato nei guest, quindi non dovrebbe essere considerata una buona fonte di entropia quando si utilizza questo metodo.
Un approccio migliore su Linux è rng-tools con il driver rng paravirtualizzato virtio-rng (ovvero consente a un ospite di accedere all'entropia raccolta dall'host, eliminando molti potenziali problemi relativi alla visualizzazione di eventi "casuali" da parte degli ospiti), oppure potresti trovare Entropy Broker più utile. Sui recenti chip Intel puoi anche esporre l'istruzione RDRAND agli ospiti, aggirando il problema.
Questo articolo (dal discorso di hpa al LinuxCon Europe 2012 ) è una lettura utile:http://lwn.net/Articles/525459/ , discute anche HAVEGE /haveged (anche se la distinzione non è chiara neanche qui).
Consulta le risposte a questa domanda per alcune riflessioni su come determinare la mancanza di casualità:quali statistiche possono essere utilizzate per identificare i dati pseudocasuali?