Je vhodné používat hasged jako zdroj entropie na virtuálních strojích?

(Upozornění: Rozhodně netvrdím, že HAVEGE dostojí svým tvrzením. Nekontroloval jsem jejich teorii ani implementaci.)

Aby získaly náhodnost, HAVEGE a podobné systémy se živí "fyzickými událostmi", a zejména časováním fyzických událostí. Mezi takové události patří výskyty hardwarových přerušení (které zase shromažďují data o stisknutí kláves, pohybech myši, příchozích ethernetových paketech, době, kdy pevný disk dokončí požadavek na zápis...). HAVEGE také tvrdí, že se živí všemi typy chyb mezipaměti, ke kterým dochází v CPU (mezipaměť L1, mezipaměť L2, TLB, predikce větvení...); chování těchto prvků závisí na tom, co CPU dělal v předchozích několika tisících hodinových cyklů, takže existuje potenciál pro určitou "náhodnost". To závisí na možnosti měřit aktuální čas s velkou přesností (ne nutně přesností), což je místo rdtsc přichází do hry instrukce. Vrací aktuální obsah interního čítače, který se zvyšuje při každém taktu, takže nabízí přesnost pod nanosekundy.

Pro systém virtuálního stroje existují tři možnosti týkající se této instrukce:

1. Nechte instrukce přejít přímo na hardware.
2. Zachyťte instrukci a emulujte ji.
3. Úplně zakažte instrukce.

Pokud správce virtuálního počítače vybere první řešení, pak rdtsc má veškerou potřebnou přesnost a měl by fungovat stejně dobře, jako kdyby byl na fyzickém stroji, pro účely shromažďování entropie z hardwarových událostí. Protože se však jedná o virtuální stroj, jedná se o aplikaci na hostitelském systému; nedostává CPU po celou dobu. Z pohledu hostujícího operačního systému pomocí rdtsc , vypadá to, jako by jeho CPU byl občas "ukraden":dvě po sobě jdoucí rdtsc instrukce, nominálně oddělené jedním hodinovým cyklem, mohou hlásit zvýšení čítače o několik milionů . Stručně řečeno, když rdtsc se jednoduše aplikuje na hardware a hostující OS jej může použít k detekci přítomnosti hypervizoru.

Druhé řešení má za cíl učinit emulaci „dokonalejší“ udržováním virtuálního čítače cyklů pro jednotlivé virtuální počítače, který sleduje cykly skutečně přidělené danému virtuálnímu počítači. Výhodou je, že rdtsc , z pohledu hosta, již nebude vykazovat efekt „ukradených cyklů“. Nevýhodou je, že tato emulace se provádí pomocí spouštění a zachycení výjimky CPU, což zvyšuje náklady na rdtsc operační kód z několika desítek hodinových cyklů (záleží na značce CPU; některé spouštějí rdtsc za méně než 10 cyklů, ostatní používají 60 nebo 70 cyklů) na více než jeden tisíc cyklů. Pokud se host snaží udělat hodně rdtsc (jak k tomu bude mít sklon HAVEGE), pak se zpomalí na plazení. Navíc kód zpracování výjimek naruší opatření; namísto měření časování hardwarové události bude kód měřit dobu provádění obslužné rutiny výjimek, což může pravděpodobně snížit kvalitu extrahované náhodnosti.

Třetí řešení (vypnutí rdtsc ) jednoduše zabrání HAVEGE vrátit dobrou náhodnost. Vzhledem k tomu, že interně používá PRNG, výstup může stále oklamat nástroje statistické analýzy, protože existuje obrovský rozdíl mezi „vypadat náhodně“ a „být nepředvídatelný“ (nástroje pro statistickou analýzu sledují cestu „vypadat náhodně“, ale kryptografické zabezpečení spoléhá na nepředvídatelnost ).

V příručce VirtualBox se uvádí, že VirtualBox se ve výchozím nastavení řídí první metodou (rdtsc je bezpodmínečně povoleno a aplikováno přímo na hardware), ale může být nakonfigurováno pro použití druhého řešení (což v tomto případě nechcete).

Chcete-li otestovat, co váš virtuální počítač dělá, můžete vyzkoušet tento malý program (kompilujte s gcc -W -Wall -O na Linuxu; -O je důležité):

#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;
}

Na nevirtuálním počítači se „skutečným“ rdtsc , bude hlásit hodnotu mezi 10 a 100, v závislosti na značce CPU. Pokud je nahlášená hodnota 0 nebo pokud program spadne, pak rdtsc je zakázáno. Pokud je hodnota v tisících, pak rdtsc je emulován, což znamená, že shromažďování entropie nemusí fungovat tak dobře, jak se očekávalo.

Upozorňujeme, že ani získání hodnoty mezi 10 a 100 nezaručuje, že rdtsc není emulován, protože správce virtuálního počítače při zachování svého virtuálního čítače od něj může odečíst očekávaný čas potřebný pro provedení obsluhy výjimky. Nakonec se opravdu musíte pořádně podívat na manuál a konfiguraci vašeho správce VM.

Celá premisa HAVEGE je samozřejmě sporná. Pro jakékoli praktické zabezpečení potřebujete několik „skutečných náhodných“ bitů, ne více než 200, které použijete jako základ v kryptograficky zabezpečeném PRNG. PRNG bude produkovat gigabajty pseudo-alea nerozeznatelné od skutečné náhodnosti, a to je dost dobré pro všechny praktické účely.

Trvání na návratu k hardwaru pro každý kousek vypadá jako další propuknutí této chybné myšlenky, která považuje entropii za druh benzínu, který spálíte, když se na něj podíváte.

Na upozornění polarssl:Podrobnou technickou odpověď lze nalézt v nejnovějším zdroji debianu:

http://bazaar.launchpad.net/~ubuntu-branches/debian/experimental/haveged/experimental/revision/12?start_revid=12#debian/README.Debian

Shrnutí je:polarssl !=haveged !=HAVEGE

Na experimentech s emulátorem embloms.se:

haveged testovací sada, NIST a ent , ověřte, že sestavení zdroje vytvořilo funkční RNG. Testování za běhu je vyžadováno k ověření funkce chráněné ve virtuálním prostředí. To je poměrně nedávný přírůstek do haveged.

O statistickém testování:

Předpokládejme, že máte hardware RNG , TRNG , jak víš, že to není rozbité? Hardware se rozbije. Německý normalizační orgán má specifikaci, která se zabývá právě tímto problémem, AIS31 . Tento přístup přijal haveged. (Zaujatá) diskuze o standardech pro RNG tak, jak se vztahují na hasged, lze nalézt na:

http://www.issihosts.com/haveged/ais31.html

Nepředvídatelnost HAVEGE je přesně ten samý mechanismus, jaký lze vidět v softwaru pro srovnávání. Není to kvůli posunu časovače, ale agregaci asynchronního chování v moderním procesoru. Opravdu nezáleží na tom, zda změny výkonu pocházejí z nedostatku mezipaměti nebo z časového úseku doručeného jinému procesoru. Na přesnosti časovače také nezáleží, pokud je „adekvátní“. Jak se to určuje? Podle výstupu. Podle návrhu (nebo možná nad návrhem) /dev/random je imunní vůči špatným vstupním datům. Jediný způsob, jak rozvrátit návrh, je lhát o entropii přidané do zásoby entropie. Nejnovější verze hasged provádějí u generovaného výstupu odhad entropie za běhu, aby se zajistilo, že výstup bude v souladu s ideálním TRNG.

Shrnutí:haveged výstup je k nerozeznání od TRNG podle testů používaných německým normalizačním orgánem k certifikaci TRNG . Pokud tomu tak není, haveged se vypne.

(Aktualizováno , s poděkováním gwuertz aktuální autor/správce haveged , přehlédl jsem oddělení mezi HAVEGE a haveged .)

haveged je odlišná implementace metody HAVEGE pro generování náhodných čísel, je aktuální, udržovaná a zdokumentovaná zde:http://www.issihosts.com/haveged/ (a již nepoužívá přímo libhavege).

HAVEGE není příliš aktuální (2006), i když jej někdo nedávno (2009) opravoval kvůli rychlosti a správnosti. Byl bych opatrný, protože nedokumentuje svou metodu, nezmiňuje virtuální stroje a jak bylo uvedeno, spoléhá (silně) na RDTSC (nebo ekvivalent platformy). (Také ze zdrojového kódu se třesu, ale to je dost subjektivní.)

Budu tvrdit, že hostitelský VM by neměl neúmyslně prosakovat žádný stav do hostů, takže by neměl být považován za dobrý zdroj entropie při použití této metody.

Lepším přístupem na Linuxu jsou rng-tools s virtio-rng paravirtualizovaným ovladačem rng (tj. umožnit hostovi přístup k entropii shromážděné hostitelem, což eliminuje mnoho potenciálních problémů s pohledem hostů na „náhodné“ události), nebo můžete najít Entropy Broker užitečnější. Na nejnovějších čipech Intel můžete také odhalit instrukci RDRAND hostům a problém obejít.

Tento článek (z přednášky hpa na LinuxCon Europe 2012 ) je užitečné čtení:http://lwn.net/Articles/525459/ , pojednává také o HAVEGE /haveged (i když ani zde není rozdíl jasný).

Podívejte se na odpovědi na tuto otázku, kde najdete několik myšlenek, jak určit nedostatek náhodnosti:Jaké statistiky lze použít k identifikaci pseudonáhodných dat?