Případ Lenstra a Heninger
Před několika týdny se objevily práce Lenstra et al. a Heninger et al. popisující velkou množinu RSA klíčů, které lze faktorizovat z důvodu sdílení prvočísel v RSA modulu. Původní Lenstrův článek nezmiňuje, že se jedná výhradně o embedded zařízení, a proto vyvolal „drobnou“ paniku. Z vyjádření Nadii Heninger je patrné, že se jedná o různé „krabičky“ jako embedded routery, firewaly apod.
V Laboratořích CZ.NIC jsme zkoušeli několik modulů faktorizovat. Po chvíli vypadlo prvních cca 80 faktorizovaných modulů, ty jsme pak namapovali zpátky na certifikáty. V EFF SSL Observatory jsme našli 3912 unikátních certifikátů obsahujících tyto moduly a pak ještě několik extra v dalších databázích. Všechny byly self-signed certifikáty embedded zařízení, nejspíš právě ty vygenerované po prvním spuštění. Z toho vyplývá, že nejen první prvočíslo bylo sdílené, ale i to druhé se vygenerovalo často stejně.
Detektivka za hledáním příčiny
Důvod existence těchto slabých RSA klíčů je zřejmě slabá entropie, otázka je, jak se to mohlo stát? Při dlouhých debatách vyplavaly na povrch některé skutečně mizerné implementace RNG. Viděl jsem i implementaci /dev/random, která byla téměř deterministická.
Jednoduše se za seed entropy poolu při inicializaci použilo seconds_since_last_boot z čehož získáme jenom pár bitů entropie. Co se asi tak stane, když bude takové zařízení spuštěno prvně – přesně okamžik kdy se generují ty klíče? Budeme mít, když to hodně přeženu, tak dva bity entropie.
Extrakce myšlenkových postupů HW inženýrů, kooperační paradox a šetření na nesprávném místě
Další část je víceméně překlad hypotetického sledu událostí, který sepsal Marsh Ray (přeloženo se svolením autora; všechny potenciální nepřesnosti jsem nejspíš zanesl překladem). V zásadě se všichni shodli, že tak nějak to se to nejpravděpodobněji událo.
Situuji se do pozice inženýra, který navrhuje logiku a píše low-level firmware pro běžný router/wifi/firewall v ceně kolem 50 dolarů. Následuje „převlnění“ se do filmové snové sekvence…
Jsem HW inženýr s mnoha lety zkušeností, sahajících zpátky téměř až do dob, kdy se navrhovaly plně diskrétní logické obvody. Jsem součástí stávajícího týmu už pět let, mám šedivou bradu, piju čtyři šálky silné kávy denně. Ve volném čase rád čtu science-fiction a ručně vyrábím akustické kytary.
Dosud ve své kariéře jsem nikdy neimplementoval kryptografii, ale ukažte mi specifikaci a umím to navrhnout v programovatelné logice s minimální spotřebou proudu. Nikdo není produktivnější než já, když můžu použít oblíbené nástroje. Nakonec, můj poslední ASIC dizajn prošel validací na první pokus a ušetřil společnosti 100 000 USD.
Šéf týmu (manažer) byl původně taky HW inženýr, ale to bylo dávno před dobou LSI programovatelné logiky. V současnosti jsou jeho nejoblíbenější fráze „Rychleji, levněji, dobíjitelné: vyber dvě“ a „Nemáte z toho dělat Rembrandta“.
Projekt je zatím v prvotní fázi, ještě jsme se nerozhodli pro dodavatele procesoru. Podle odhadu prodejnosti od lidí z marketingu nejspíš skončíme s nějakým SoC s pomocným ASIC-em nebo si obstaráme licenci pro IP core na plnohodnotný ASIC dizajn.
Shodli jsme se na embedded OS, máme dokonce i web server běžící na vývojové desce z posledního projektu. Na něm se postaví uživatelské rozhraní pro správu zařízení.
Fast-forward do pozdější fáze projektu. Uživatelský interface (UI) má už bežící prototyp. Člověk odpovědný za firmware se podílel na vývoji UI a přidal podporu HTTPS použitím knihovny, kterou jsme koupili. Byla vybrána hlavně z důvodu, že podporuje náš embedded OS.
„Softwéráci“ mi říkají, že SSL knihovna stanovuje požadavek na dobrý náhodný generátor a nejlepší by bylo, kdybych ho poskytnul v hardware. Udělali z toho dokonce design requirement, všechno je někdy „poprvé“.
Můj první nápad je použít generátor založen na LSFR, který by se vešel na dostupné místo v ASICu. Tyto jsme použili v některých RF dizajnech a v různých „hračkách“ na implementaci generátorů šumu.
Jenže když se podívám pozorně, požadavky stanovují potřebu kryptograficky silného generátoru, něco víc než obyčejný pseudonáhodný generátor. Musí to generovat „entropii“. To slovo jsem od časů studia na univerzitě dlouho neslyšel. Matně si vzpomínám, že to bylo něco mysteriózního. Ten termín se objevoval jak v pokročilé fyzice, tak v teorii kódů … s úplně odlišnými definicemi!
Googlením se dostanu na článek z wikipedie. Blbé je, že to není příliš užitečné. Nic co by šlo implementovat. Tak hledám „random entropy generator“ a naleznu Turbid: A High-Entropy Randomness Generator.
Článek o Turbid-u je skvělý a celý ho přečtu. Jenže naše „krabička“ nemá ani mikrofon, ani A/D převodník, takže to beru spíš jako kuriozitu. Všimnu si TI CC2530, který používá LSFR a lze ho seedovat z náhodného šumu RF A/D převodníku. Jenže nepoužíváme ani ten čip, ani RF A/D převodník.
Hledám na webu více o zdrojích entropie. Na wiki článku o Hardware random number generator se dozvím o zdroji z radioaktivního rozpadu, detektorech kosmického záření, lavinových diodách, uvádějí se i webkamery, lávové lampy a jiné fascinující/podivné způsoby generování entropie. Ale nic z toho se nevejde do seznamu součástek (bill of materials).
Umím najít pouze jediný zdroj entropie který by šel implementovat v dostupném hardware. Tento je založen na využití volně běžících oscilátorů, které budou pohánět nějaké čítače nebo hodiny a tahat z nich bity do LSFR.
Strávím odpoledne vytvářením experimentální implementace v CADu. Je to zajímavý projekt, ale vyhlídky jsou nevalné. Z několika důvodů to nelze použít:
- Validační nástroj správně označí volně běžící oscilátory za asynchronní logiku a plácne na to obrovské červené varování. Naše směrnice mají taky velké varování proti použití asynchronních dizajnů.
- Ve směrnicích je taky zásada, že kompilátor nesmí generovat varování vůbec. Pravděpodobně bych ostatní dokázal přesvědčit o výjimce, ale v minulosti se nám toto pravidlo osvědčilo.
- Distribuce frekvencí oscilátoru viděna v ostatních částech se nedá předpovědět předem. Určitě se změní když změníme Si procesy nebo několik součástek. Budu muset definovat striktní parametry pro schválení dizajnu, ale nevím, co všechno to ovlivní.
- V důsledku předchozího bodu můj software neumí odhadnout spotřebu obvodu, pokud to nerozdělím na separátní projekt. Řádek v excelu bude mít v příslušné kolonce zapsáno nějaké hausnumero, které jsem vymyslel „stropovou metodou“ (podíval se na strop a napsal, co mě napadlo jako první).
Všechno dosud zmíněné přináší risk a neurčitost. Když to nebude fungovat, bude nutná další revize ASIC, což přidá nějakých 100 000 USD a pár týdnů navíc. Tajně začínám podezřívat advokáty kvantového šumu, že nikdy nenavrhovali obvod pro masovou produkci.
Nevím teď úplně co dělat a tak sdělím, co jsem objevil týmu a produktovému manažerovi na dalším mítingu. Zkouším co nejlépe vysvětlit, co ta „entropie“ je (vynechávám část o lávových lampách).
Někdo z týmu se ohlásí: „Něco jsem četl o oznámení Intelu, že do budoucích čipů budou dávat HW zdroj entropie.“ Produktový manažer se zeptá: „Co dělají jiná zařízení ve stejné cenové relaci?“
Žádný jiný produkt ve stejné cenové hladině neproklamuje hardwarový zdroj entropie. Produkty z vyšší kategorie dokonce požadují stovky dolarů za něj jako volitelnou součást. Náš marketingový tým by rád měl další „fíčuru“, o které by mohl mluvit, ale na druhé straně o tom nikdy neslyšeli, nevědí, jaká je po tom poptávka a možná nechtějí lákat pozornost na fakt, že žádné naše další produkty to stejně nemají.
A tak náš produkt skončí bez hardwarového zdroje entropie.
Naši UI vývojáři by se s tím měli vyrovnat stejně jako s jinými produkty z této kategorie. Uspokojí se s „krmením“ aktuálního času z hodin reálného času, jak je to ukázáno v příkladech od naší crypto knihovny.
Náš QA tým jde ještě dál a otestuje výstupy proti NIST SP 800–22 „A Statistical Test Suite for Random and Pseudorandom Number Generators“. A všechno vypadá fajn.
Defaultně je web UI zapnuto od startu a když chybí certifikát, tak se vygeneruje automaticky. Konec příběhu. Zbytek je historie.
(Konec překladu textu od Marsha Raye.)
Poznámka: TI CC2530 je zajímavá případová studie sama o sobě, trpěl taky slabým RNG. Marsh to komentuje: „Čip s dedikovaným AES koprocesorem a 16-bitovým LSFR RNG. Co špatného by se asi tak mohlo stát?“ Peter Gutmann navrhuje řešení s Zenerovou diodou a Schmittovým klopním obvodem, pak se řeší, zda by to prošlo v čistě digitálním ASIC návrhu.
Poučení z krizového vývoje
Implementace kryptografie je náročná, protože kryptografie obsahuje několik základních principů a pak nespočet speciálních případů, co nedělat; jejich počet snad bude menší než Grahamovo číslo.
Před více než dekádou to jeden kolega trefně okomentoval: „Nechápu, proč se vrtáš v kryptografii. Dáš číslo dovnitř, jiné číslo vypadne ven. Nikdy si nemůžeš být jistý, jestli tam nemáš chybu. Přitom v 3D grafice nebo fyzikálních simulacích vidím bug téměř okamžitě, jako třeba teď, když mým potvorám začaly odlétávat klouby od sebe nekonečnou rychlostí.“
Matthew Green napsal ke generování náhodných čísel pěkný blogpost s názvem „Random number generation: An illustrated primer“.
ČLÁNKY DO MAILU