Linux, Linus, RDRAND a ignoranti

18.9.2013 01:30 | Přečteno: 3588× |

TL;DR: Jsi ignorant, Linusi, děláš do věcí kterým nerozumíš. Nauč se něco o kryptografii a pak si přečti arch/x86/kernel/cpu/rdrand.c.

Týden nazpět vyšla na Rootu zprávička ohledně petice o vynechání instrukce RDRAND z linuxového generátoru náhodných čísel (to je ta část, která generuje data v /dev/random a /dev/urandom). Zprávička je na http://www.root.cz/zpravicky/linus-o-odstraneni-rdrand-z-jadra-jsi-ignorant-my-vime-co-delame/ a já k ní měl celkem dlouhý komentář. Téma mi ale přišlo zajímavé, a taky mám dojem že by si zasloužilo širší publikum než to, které komentuje zprávičky na rootu, tak jsem se rozhodl založit si blog a trochu to rozvést.

O co jde: Linux Torvalds se dost nelichotivě vyjádřil k návrhu, že by Linuxové jádro nemělo volat instrukci RDRAND. Pro neznalé: tahle instrukce vrátí náhodná data získaná z generátoru implementovaného přímo v hardwaru procesoru. Teoretickou výhodou je kvalita generovaných dat (nejsou deterministická), praktickou výhodou je rychlost. RDRAND v současných procesorech dokáže generovat necelých 800 MB/s.

Ve světle nedávných informací o NSA ale používání RDRAND přestává vypadat jako tak dobrý nápad jako byl na začátku. Hardwarový generátor je totiž pochopitelně closed source, kdo ví, jestli si NSA neprosadila nějaký backdoor. Navíc, v současnosti silně propagované šifry založené na eliptických křivkách (které mimochodem propaguje NIST, ve kterém má NSA velké slovo) naprosto nutně vyžadují kvalitní generátor náhodných čísel. Stačí aby útočník dostal jen pár bitů informace o výsledku RNG a šifra je prolomená. (SONY a PS3 je toho zářným příkladem, i když tam nešlo jen o "pár bitů".)

Linus na obavy reagoval tvrzením, že implementace RDRAND není problém, protože je to jen jeden z mnoha zdrojů entropie, a pool se s ním jen vylepšuje. Pokud by byl výsledek RDRAND špatný, maximálně to k ničemu nebude nebude, ale rozhodně to neuškodí. Vylepšování pak konkrétně obstarává obyčejný XOR, kterým se na konci do posbírané entropie "přimíchá" výsledek RDRAND. Linus zřejmě spoléhá na důkaz nerozluštitelnosti OTP (one-time pad), který v podstatě říká, že ať vezmu cokoli a provedu XOR se skutečně náhodnými daty, výsledek bude zcela nerozeznatelný od náhodných dat. V případě Linuxového jádra je výsledek RDRAND vlastně cleartext, který se zašifruje klíčem - "dobrou" entropií.

Bohužel, tahle úvaha spočívá na jednom zásadním předpokladu - že totiž klíč je naprosto nezávislý na cleartextu. Neboli, že RDRAND generuje čísla jen pomocí onoho hardwarového generátoru, že nepodvádí.

Kdyby například RDRAND vracela vždycky stejné číslo jako druhý operand XORu, výsledek by byl vždycky 0. Ve skutečnosti není problém zařídit, aby výsledek XORu vypadal jakkoli si vymyslíte, stačí si spočítat požadovanou hodnotu a pak udělat XOR s druhým operandem (nasbíranou entropií). Následný XOR ji zase "odmaže". Pokud by /dev/random obsahovalo samé nuly, někdo by si toho velmi rychle všiml. Bohužel, není problém udělat RNG který vrací čísla, která jsou zcela náhodná pro každého kdo nezná klíč. Pro majitele klíče jsou naopak zcela deterministická. Jednoduchý příklad může být např. funkce RNG = SHA1(NSA_KEY || čítač), kde by důkaz že výsledek není náhodný by vyžadoval umět (rychle) najít kolizi v SHA1. To nikdo neumí (doufám). Téhle vlastnosti se krásně říká kleptografie.

Pokud si říkáte: "jak by mohla instrukce vědět co má vrátit," pak jste nedávali pozor. Procesor pochopitelně ví, co je v paměti. Jednotlivé instrukce můžou být dost složité, rozkládat se na desítky operací v mikrokódu, využívat mnohé jednotky procesoru, prostě jedna instrukce může být sama o sobě dost složitý program.

Následující část je naprostá spekulace (oproti té předchozí, která je obyčejná spekulace).

Jen pro zábavu jsem se zamyslel, jak by se nejjednodušeji dal současný RNG v linuxu rozbít, aby si toho nikdo nevšiml. Nápad využívá toho, že RDRAND je definovaný jako inline funkce, a XOR následuje hned potom. Napadlo mě následující: RDRAND při svém vyvolání zkontroluje, jestli je v cache dword 0xCAFEBABE (touhle hodnotou vyplňuje garbage collector v Javě nepoužívanou paměť). Pokud tam není, pak se chová přesně podle dokumentace. Pokud tam je, pak projde pipeline a vymění XOR následující po RDRAND za MOV RAX, <hodnota z kleptogenerátoru>. Pokud v pipeline žádný XOR není, pak se chová podle dokumentace.

Tohle má tu kouzelnou vlastnost, že se slabina projeví jen pokud z /dev/random čte Javovský program, a neprojeví se při testech náhodnosti, protože tam se obvykle nejdřív nasbírají data a pak se na nich dělají výpočty, a navíc se obvykle nepoužívá XOR. Takže chyba nejde debugovat.

Ve skutečnosti dost pochybuju, že by to NSA / Intel udělali zrovna takhle, protože i drobná změna kódu by tenhle backdoor rozbila. Jde spíš o myšlenkový experiment, který měl dokázat, že backdoor nepotřebuje složitý program na to aby fungoval. Navíc by těžko dosáhli těch 800 MB/s, pokud by měli pořád dokola procházet cache.

Nabízí se pochopitelně otázka, proč se obtěžovat s RNG, když se dá udělat zajímavější backdoor někde jinde. Odpověď je bohužel jednoduchá: protože náhodnost nejde rozumně testovat. Jakýkoli backdoor v RNG má velkou šanci, že si ho nikdo nevšimne. Vzpomeňte se na Debian a chybu v OpenSSL. Tam byla entropie generátoru redukována na směšných 16 bitů, a nikdo si toho nevšiml 2 roky. Navíc kdo říká, že backdoorů není víc, že.        

Komentáře

[chrono]

RDRAND sa dá v konfigurácii jadra zakázať.

[Sten]

Linux nedělá XOR, ale používá to jako vstup do něco-jako-hashe, ve kterém se drží entropie. XOR totiž není dostatečně bezpečný i třeba pro statistický útok z user-space.

Pokud jste paranoidní, jde RDRAND snadno vypnout: vmlinuz nordrand

[pc2005]

To vypadá, že okolo verze 3.5/3.6 dostal někdo neodmítnutelnou nabídku .

Nejvtipnější na tom je, že autor toho XORu je právě z intelu . (i když to může být i tím, že RDRAND ekvivalent na moc dalších arch nebude).

[Jendа]

Příloha:

• raw.txt (8454 bytů)

Přečetl jsem si ten pastebin (příloha) a nevím…

Navíc, v současnosti silně propagované šifry založené na eliptických křivkách (které mimochodem propaguje NIST, ve kterém má NSA velké slovo) naprosto nutně vyžadují kvalitní generátor náhodných čísel.

Ne, nevyžadují. Pokud nemáš problém s deterministickou signaturou (RFC 6979), tak nepotřebuješ dokonce vůbec žádnou náhodu. Ve zkratce, ta hodnota, co musí být normálně náhodná, se nastaví na SHA(message || key) (actually, it's HMAC). Pro stejnou zprávu ti to vždycky vyplivne stejný podpis, což ti může vadit nebo se ti naopak může hodit (záleží od aplikace), pro jinou zprávu to vyplivne jinou hodnotu.

Stačí aby útočník dostal jen pár bitů informace o výsledku RNG a šifra je prolomená.

Koukám na to PDF (strana 125) a chtěl bych vidět to odvození pro jiná známá m.

Btw. tohle mě potěšilo:

#define EXTRACT_SIZE 10
if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
  panic("Hardware RNG duplicated output!\n");

mám tedy 2^-80 šanci, že mi to celé crashne? :)

[dumblob]

mám tedy 2^-80 šanci, že mi to celé crashne? :)

Nojo, v pripade povoleneho FIPS 200 (zdravim NIST) je to tak - takze moc bych se nesmal, protoze to je fakt. Ale imho lepsi crash nez dvakrat po sobe stejna hodnota .

[David Watzke]

Ale imho lepsi crash nez dvakrat po sobe stejna hodnota .

Určitě?

[dumblob]

Pozadavkem je, aby se neopakovala 2 po sobe jdouci cisla. Pokud tedy mam na vyber mezi panic() a porusenim pozadavku, tak volim panic() .

[:::]

kde je ten pozadavek?

[dumblob]

Ve FIPS 200

[:::]

to je to 17 strankovy PDF co najde

big brother

, pardon, google, nebo neco jinyho? Protoze tam me fulltext hledani 'repeat' nenaslo akorat 'repeatable'

[dumblob]

Nu, verim tomu, co je napsano ve zdrojacich Linuxu. PDF jsem cele necetl (jedna se o manazerske narizeni), ale je tam nekolik referenci na podminecnou implementaci napr. NIST Special Publication 800-53 (to uz ma 457 stranek a zase kupu referenci).

Takze za sebe rikam, ze jsem presne tento pozadavek nikde nevidel, ale faktem zustava, ze to je v Linuxu implementovane s poznamkou, ze se jedna o zalezitost z FIPS 200.

[:::]

cely me to prijde dost podezrely. Aby to nebyl dalsi backdoor...

Vetsinou se u generatoru napr s blokovou sifrou v counting modu dela casto reseed, prave aby se zajistilo ze se cisla muzou opakovat. Protoze to ze se cisla nikdy neopakuji by umoznilo rozeznat ze se nejedna o true RNG.

Dalsi vec je ta podivne zvolena velikost, kdy testujou ze se neopakuje sequence 10 bytu, ale uz netestujou seq. 5, 9, 11, 20, ... Ze by ten FIPS byl takovej kockopes?

[xkucf03]

Ono ale když se budou pořád dokola opakovat dvě stejná čísla, tak to není o moc lepší…

[dumblob]

Ja to nevymyslel a take se mi to zda jako blbost (tohle si ma aplikace resit sama a nema to byt na jaderne urovni, natoz ve vanilce ).

[pavlix]

Ja to nevymyslel a take se mi to zda jako blbost (tohle si ma aplikace resit sama a nema to byt na jaderne urovni, natoz ve vanilce ).

A čemu to tam vadí, když je to ve výchozí konfiguraci stejně vypnuté?

[dumblob]

Tem, kteri ctou ten kod a mne (jakakoukoliv nadbytecnou zalezitost v jadre povazuji za zverstvo).

[pavlix]

Řekl bych, že zvěrstvem je z tohoto pohledu většina jádra.

[dumblob]

Bohuzel (asi jsme prilisni puriste).

[xkucf03]

Jak už tu někde padlo: náhoda se dost blbě testuje. Záměrně špatný generátor je prakticky neodhalitelný¹ a tohle je asi jen taková ochrana proti případu, že by někdo z blbosti napsal return 1;.

_{[1] dá se otestovat offline, jestli poskytuje dostatečnou entropii, ale za běhu to asi z výkonnostních důvodů nikdo dělat nebude – navíc: u jak velkých kusů by se ta entropie měla měřit?}

[dumblob]

...asi jen taková ochrana proti případu, že by někdo z blbosti napsal return 1;

Nejak mi ta navratova hodnota nedochazi (obrana jadra sama pred sebou na takto trivialni urovni se mi opravdu nezda jako spravne pochopeni). Mas nejaky priklad?

[Jendа]

Mas nejaky priklad?

bit <= '1';

(VHDL, kdyby to někdo nepoznal)

[dumblob]

A uplny kontext by nebyl? I pres trivialni test-bench random generatoru neprojde takovehle uklepnuti se ve VHDL/Verilogu (tim zabranim preklepu HW navrhare).

A ochrana v run-time jadra (tim zabranim pouziti "spatneho" CPU/jadra)? Proc bych to kontroloval jindy nez pri vymene/inicializaci/zmene_mikrokodu kazde casti CPU poskytujici dany random registr? A prosim bez pohadek o semi-intelligent, self-reconfigurable FPGA...

[Jendа]

A uplny kontext by nebyl? I pres trivialni test-bench random generatoru neprojde takovehle uklepnuti se ve VHDL/Verilogu (tim zabranim preklepu HW navrhare).

Nevím, třeba je tam HW bug (vyrostl tam fous křemíku), kdy to uzemní gate jednoho tranzistoru a prostě to občas neupdatne ten registr.

A prosim bez pohadek o semi-intelligent, self-reconfigurable FPGA...

Hej!

[dumblob]

Nevím, třeba je tam HW bug (vyrostl tam fous křemíku), kdy to uzemní gate jednoho tranzistoru a prostě to občas neupdatne ten registr.

Ok, pak bych tyto kontroly musel provadet uplne za kazdou instrukci! A co takhle kontroly toho kontrolniho kodu?! Juj, to je vlastne dalsi kod, ten bych mel pro jistotu take kontrolovat...

Pouceni: Ultra-spolehlive systemy vypadaji jinak a vanilla Linux do teto kategorie nespada.

[Jendа]

Toho, že ti 1+1 vrací 0 si všimneš (crashne ti počítač), toho, že ti HW RNG vrací konstantu si všimneš těžko.

[dumblob]

Nu, tak to by musela byt zatracene velka nahoda, aby fous kremiku vyrostl prave na takovem miste, aby zmenil cely registr (tedy ponechal minulou hodnotu) a ne pouze jeden bitik. Postvat napr. trivialni kontrolu dvou po sobe jdoucich cisel a odvozovat z toho, ze je spatny HW, to bych si netroufnul. PST, ze se fous kremiku projevi v celem obvodu realizujicim RNG (tzn. vycitani hodnot v pameti/cache podle citace; zpracovani; ulozeni do registru; pravidelny update...) prave tak, ze se budou opakovat dve cisla po sobe je imho tak nizka, ze tato kontrola absolutne ztraci smysl).

Z fleku me ani nenapada jina "vykonove/casove" malo narocna metoda softwarove kontroly HW RNG. Imho ani nelze takovou sestrojit, aby byla opravdu pouzitelna (tedy prave napr. pro ten fous kremiku, ktery nekdy vede a jindy nevede proud).

Kdyz to shrnu, tak jakekoliv obdobne trivialni, nezdrzujici kontroly povazuji za nesmysl. Smysl by melo kazdy RNG v kazdem jednotlivem jadru CPU dlouhodobe otestovat jak nekdo navrhoval v teto diskuzi (pak bych vedel co od toho daneho kusu HW mohu ocekavat - zmeny zpusobene starim/zmenou prostredi apod. jsou uz opravdu prilis v kategorii ultra-reliable systemu).

[Jendа]

Nevím, mně přijde bug, že RNG vrací konstantu, docela uvěřitelný… V procesoru asi ne, ale když to bude připojené jako periferie…

[dumblob]

Nevím, mně přijde bug, že RNG vrací konstantu, docela uvěřitelný… V procesoru asi ne, ale když to bude připojené jako periferie…

Mne zase moc ne . Prave proto bych to kontroloval "predem" dlouhodobym testem a ne az pri ostrem nasazeni.

Skoda, ze nemame po ruce nejakou statistiku o HW RNG (napr. tech externich), kolikrat se nejaky HW bug (zasadnim zpusobem ovlivnujici vygenerovana cisla) objevil, abychom tady netipovali jak baby na trhu.

[Jendа]

obrana jadra sama pred sebou na takto trivialni urovni se mi opravdu nezda jako spravne pochopeni

V budoucnu může být HW generátorů více a bude k tomu nějaký driver interface a podle mě se prostě může stát, že to třeba při špatné inicializaci prostě vyčte samé nuly.

[Jendа]

dá se otestovat offline, jestli poskytuje dostatečnou entropii

Fakt? Jak? Poskytuje SHA(_NSAKEY || counter) dostatečnou entropii? Odhalíš to?

[xkucf03]

Záleží, co je counter, odkud kam jeho hodnota roste, zda se někam ukládá, zda se resetuje. Po čase¹ bys měl začít dostávat stejné hodnoty – jinak by to míjelo i záměr útočníka.

_{[1] nebo na různých CPU stejného typu. Případně by to mohli mít vázané na sériové číslo procesoru a museli by evidovat, kdo si jaký koupil – což si zase lidi, kteří dělají něco nebezpečného, dost možná ošetří (např. nekoupí počítač přes Net na svoje jméno) i z jiných důvodů (aby neprosákla jejich identita, kdyby nějaký program někam bonzoval ID procesoru).}

[Jendа]

Záleží, co je counter, odkud kam jeho hodnota roste, zda se někam ukládá, zda se resetuje.

Je 128bitový, takže ho v tomto vesmíru nejspíš nepřetečeš.

nebo na různých CPU stejného typu. Případně by to mohli mít vázané na sériové číslo procesoru a museli by evidovat, kdo si jaký koupil

Teoreticky ti pak stačí bruteforce přes sto milionů prodaných procesorů, což je zvládnutelné.

[Jendа]

tohle si ma aplikace resit sama

Jak to má dělat? Tohle mixuje do poolu, aplikace se k tomu nikdy nedostane.

[dumblob]

Aplikace, ktera ma pozadavek na specialni (pseudo)randomness si ma vytvorit vlastni generator (za vyuziti generickeho, pritomneho v jadre a nebo nejakeho jineho - napr. externiho HW).

[Jendа]

A aplikace, která chce číst vstup z klávesnice, si má vytvořit vlastní driver na USB HID?

Já tohle jako programátor nechci řešit, já chci prostě vytáhnout číslo z /dev/random. Vlastní RNG si psát nebudu, protože bych musel implementovat podporu pro RDRAND, takovou tu věc, co má VIA, externí generátory, šum ze zvukovky, všeho, co si uživatel připojil. A jako uživatel nechci řešit, že teď přidělím svůj externí kvantový generátor náhody :) GnuPG, za chvíli TrueCryptu a teď ty aplikace běží současně a hádají se o to.

[dumblob]

já chci prostě vytáhnout číslo z /dev/random.

Ty si chces vytahnout cislo, ktere je umyslne omezene (tedy napr. podminkou, ze dve po sobe jdouci cisla nejsou stejna)? Nu, nyni se asi kazdy, kdo dela treba simulace apod. obraci v hrobe . Mozna tak pro prehravani hudby ti bude vyhovovat, ze ta nahodnost je takto (to nemusi byt pouze opakovani 2 po sobe jdoucich cisel) silne deterministicky omezena. Ale pro vsechny ostatni aplikace je jakekoliv omezovani jednoznacna nevyhoda.

Btw je uplne bezna praxe si stavet vlastni generatory nahodnych cisel (neni to nic sloziteho, pokud mas na vstupu vysoce nahodny generator s co nejvice rovnomernym rozlozenim pravdepodobnosti - tuto ulohu by imho mel plnit prave /dev/random).

[Jendа]

Ty si chces vytahnout cislo, ktere je umyslne omezene (tedy napr. podminkou, ze dve po sobe jdouci cisla nejsou stejna)?

Výstup /dev/random už takto omezený není, protože je až daleko po mixování! Teď řešíme tahání z HW RNG. Tímto omezením nepatrně snížíš entropii toho, co z něj taháš, takže místo 80 bitů entropie tam přileješ pokaždé 79,9999.

Jediné, co se mi nelíbí, je, že jádro na vadném HW RNG udělá panic(). Podle mě by mělo vyhodit notice nebo warning.

Btw je uplne bezna praxe si stavet vlastni generatory nahodnych cisel (neni to nic sloziteho, pokud mas na vstupu vysoce nahodny generator s co nejvice rovnomernym rozlozenim pravdepodobnosti - tuto ulohu by imho mel plnit prave /dev/random).

Myslíš PRNG nebo co? Protože jinak mě nenapadá, k čemu by mi to bylo…

[dumblob]

Tímto omezením nepatrně snížíš entropii toho, co z něj taháš, takže místo 80 bitů entropie tam přileješ pokaždé 79,9999.

Ano, ale uz tohle mi prijde jako prilis ovlivnujici (proste odriznu nektere potencialni vystupy nasledneho mixovani nebo jim alespon divne zmenim pravdepodobnost vyskytu oproti tomu, jak to HW navrhari zamysleli).

Jediné, co se mi nelíbí, je, že jádro na vadném HW RNG udělá panic(). Podle mě by mělo vyhodit notice nebo warning.

Nu, tady uz "je mi to jedno". Proste padla hodnota nesplnila muj pozadavek a pote me uz nezajima co se bude dit dal (respektive zavisi to na jinych faktorech - vetsinou netechnickych ). Napr. v pripade FIPS 200 bych volil ten panic(), protoze to je poruseni "vyssiho" narizeni naroku na HW.

Myslíš PRNG nebo co? Protože jinak mě nenapadá, k čemu by mi to bylo…

Ano, tady jsem uz mel na mysli PRNG.

[Jendа]

proste odriznu nektere potencialni vystupy nasledneho mixovani nebo jim alespon divne zmenim pravdepodobnost vyskytu oproti tomu, jak to HW navrhari zamysleli

Nutno podotknout, že tohle padne jenom v 2**-80. A výrobci HW RNG neměli zamýšlet, že tam pošlou stejná čísla častěji, protože pak už to jaksi není RNG :).

Nu, tady uz "je mi to jedno". Proste padla hodnota nesplnila muj pozadavek a pote me uz nezajima co se bude dit dal (respektive zavisi to na jinych faktorech - vetsinou netechnickych ). Napr. v pripade FIPS 200 bych volil ten panic(), protoze to je poruseni "vyssiho" narizeni naroku na HW.

Mě by štvalo, že mi někde umře server jenom proto, že chcípnul RNG (což může a nemusí být vážná závada - pokud to třeba není vytížený HTTPS server, tak mě to tak netrápí).

[dumblob]

protože pak už to jaksi není RNG :)

Ale to my prave nevime , takze to bereme jako "hodne nahodne" v porovnani s ostatnimi prostredky bezne dostupnymi jadru. I kdyz by byl ten HW generator "omezeny", porad nevidim sebemensi duvod omezovat jeho vystupy pred vstupem do "mixovani".

Mě by štvalo, že mi někde umře server jenom proto, že chcípnul RNG (což může a nemusí být vážná závada - pokud to třeba není vytížený HTTPS server, tak mě to tak netrápí).

Nesmis mit servery v USA .

[Grunt]

0xCAFEBABE - touhle hodnotou vyplňuje garbage collector v Javě nepoužívanou paměť

Cože?

[Lyco]

Hm, omyl. 0xCAFEBABE je magická hodnota na začátku javovské třídy (souboru .class). Spletl jsem si to s jinými alokátory, které to dělají: Wikipedia

[Grunt]

No spíš mě zaujalo to, že nějaký garbage collector přepisuje uvolňovanou paměť.

[random]

Nic proti, ale tohle už je prostě paranoia. Procesor nemůže vědět, jaký kód zpracovává – vidí sice instrukce, ale nemá a nemůže mít ponětí o „big picture“, o sémantice těch instrukcí. Strojový kód linuxového RNG se každou chvíli mění – kvůli změnám v kódu samotném, kvůli různým .configům i kvůli změnám v kompilátoru – takže se prakticky nedá detekovat. CPU nemůže tušit, ve kterém registru či kde v cache/RAM se nachází vygenerovaná náhodná čísla. A kdyby tohle věděl, vůbec nemusí útočit pomocí ovlivňování RDRAND, ale může ty hodnoty přepsat přímo. Jak to kdo zjistí?

Nevylučuji, že je RDRAND cinklý či prostě jenom nekvalitní, ale ne takhle.

[jkt]

No, predpokladam, ze jste se do vygenerovaneho strojoveho kodu dane funkce nedival. S tou variabilitou to neni zas tak horke -- bude-li tripismenna agentura chtit napadnout velkou cast populace, staci se zamerit na nekolik malo enterprise distribuci.

[random]

Ivy Bridge začalo být vyráběno roku 2011 a to nezahrnuji to, že od zmrazení designu do zahájení produkce taky muselo uběhnout pár měsíců. Do RHEL 6 byla podpora přidána až v půlce roku 2012. Nechcete mi tvrdit, že Intel má křišťálovou kouli a umí detekovat přítomnost kódu, který ještě nebyl napsán?

[:::]

Nechcete mi tvrdit, že Intel má křišťálovou kouli a umí detekovat přítomnost kódu, který ještě nebyl napsán?

1. jak je psany dole, detekovat konkretni kod neni potreba

2. intel nepotrebuje kristalovou kouli, protoze sam dodal ten patch ktery to pouziva...

[alkoholik]

Zapominas na updaty mikrokodu.

[xkucf03]

Proto Linux-Libre nesvobodný microcode neobsahuje.

[pc2005]

Nejsou další revize procesoru nejspíše vypálení aktuálních microcode updatu do interní ROM? To by pak znamenalo kupovat jen první revize :-/.

[Grunt]

Linux-Libre

Teda to je docela drsné i na moje poměry.

[Jendа]

Takže tam nebude ten update. Ale původní (nebo prostě alespoň nějaký) mikrokód tam někde běžet musí.

Btw. ty updaty mikrokódu mě fascinují - hlavně, že se jim tam ještě nic neposralo. Vždyť je to binární patchování za běhu!

[Josef Kufner]

Ono to zas až takový zázrak není. Nasypeš data do kousku paměti a přecvakneš flag, aby to použil místo ROM. Co jsme si programovali instrukce do procesoru ve škole, nic moc složitého to není.

[pc2005]

No asi bych nejdřív vyflushoval pipeline. Zvlášť pokud se vypínají poškozené jednotky třeba (kde můžou být validní data)

[pc2005]

Njn ale pokud by udělal ten backdoor už v 2011 a s XOR patchem čekal, až do 2012, tak ani první revize není důvěryhodná .

[:::]

Jak uz jsem psal jinde, zadny "big picture" na to neni potreba.

[JiK]

nejvic mne zaujal posledni odstavec:

Nabízí se pochopitelně otázka, proč se obtěžovat s RNG, když se dá udělat zajímavější backdoor někde jinde. Odpověď je bohužel jednoduchá: protože náhodnost nejde rozumně testovat. Jakýkoli backdoor v RNG má velkou šanci, že si ho nikdo nevšimne. Vzpomeňte se na Debian a chybu v OpenSSL. Tam byla entropie generátoru redukována na směšných 16 bitů, a nikdo si toho nevšiml 2 roky. Navíc kdo říká, že backdoorů není víc, že.

Ale nemelo by to (mira entropie, tedy skutecna nahodnost generovanych dat) byt zjistitelna treba pomoci komprese? Neni snad pravda, ze skutecne nahodna data jsou nekomprimovatelna?

[:::]

Bohuzel tak jednoduchy to neni. Kompresni algoritmy hledaji jenom zjevny statisticky vlastnosti dat. Kdyz treba vygeneruju pomoci AES v counter modu par GB dat, tak teoreticky by to melo jit zkomprimovat na par byte. Stacilo by uhodnout ze se jedna o AES v counter mode, pomoci brute force najit klic a pocatecni hodnotu counteru a tyhle veci ulozit na vystup. V praxi neco takovyho zkomprimovat nepujde (zadny kompresni algoritmus pravdepodobne nedosahne mensi vyslednou velikost nez ma original).

[pc2005]

Aneb kompresní algoritmy jsou navrženy pouze na specifické formáty dat.

[pavlix]

Tak vzhledem k tomu, že je kompresní algoritmus reversibilní (jinak by neměl smysl), tak asi těžko může obecně zmenšovat objem dat.

[Jendа]

Ano, například nikdo nenavrhl kompresní algoritmus, který provede 2**256 operací (cracknutí AES) a pak to vyoptimalizuje na zašifrované nuly.

[xkucf03]

Takhle offline by to jít testovat mělo¹ – postavit řadu počítačů s různými procesory a různými distribucemi/jádry/knihovnami a generovat gigabajty náhodných dat a zkoumat jejich entropii.

_{[1] dělá to už někdo? bylo by to opravdu vhodné}

[Martin Mareš]

Svatej Tučňáku, to je tedy paranoia. Pokud by hypoteticky Intel chtěl přidávat backdoor do procesoru, má hromadu způsobů, jak to udělat bez nutnosti protlačit patch do jádra. Například není nijak těžké modifikovat instrukce používané na volání syscallů, aby detekovaly otevření /dev/random a čtení z něj. Ale raději bych to neměl říkat moc nahlas, nebo brzy někdo vašeho ražení začne prosazovat, aby se při instalaci Linuxu randomizovala čísla syscallů

Na současném řešení s XORováním mi nepřijde nic zásadně špatně. Osobně bych tedy raději data zamíchal ještě před zahashováním, ale jediný důvod, který k tomu mám, je jakýsi kryptografický konservativismus.

[:::]

Pokud by hypoteticky Intel chtěl přidávat backdoor do procesoru, má hromadu způsobů, jak to udělat bez nutnosti protlačit patch do jádra. Například není nijak těžké modifikovat instrukce používané na volání syscallů, aby detekovaly otevření /dev/random a čtení z něj.

to by se dalo snadno odhalit protoze by ti v systemu neubyvala entropie...

Svatej Tučňáku, to je tedy paranoia.

...

Na současném řešení s XORováním mi nepřijde nic zásadně špatně.

proste jeste nemas ten spravnej security mindset

[Martin Mareš]

to by se dalo snadno odhalit protoze by ti v systemu neubyvala entropie...

Neubývala, protože bych to ošvindloval až při návratu ze syscallu.

proste jeste nemas ten spravnej security mindset

Úhybný manévr, kterým zakrýváte nedostatek (či přesně řečeno absenci) argumentů.

Zkuste být konkrétní a popsat jakýkoliv realistický útok, který by s XORem šel provést a bez něj nikoliv.

[:::]

Neubývala, protože bych to ošvindloval až při návratu ze syscallu.

Jako ze bys prepsal buffer co to vraci? To by se dalo snadno odhalit pridanim jednoho radku do random.c, ktery pred navratem ten buffer vynuluje, pripadne tam nahraje nejakou znamou, nenahodnou hodnotu...

Zkuste být konkrétní a popsat jakýkoliv realistický útok, který by s XORem šel provést a bez něj nikoliv.

Jak uz jsem psal v tom prispevku na ktery jsem odkazoval a ktery se me nechce prekladat do cestiny:

1. reseni s xorem je velice jednoduche. Pravdepodobne mnohem jednoduzsi nez cokoli jinyho co bys dokazal vymyslet

2. narozdil od jinych reseni je to naprosto neodhalitelne...

[Martin Mareš]

Jako ze bys prepsal buffer co to vraci? To by se dalo snadno odhalit pridanim jednoho radku do random.c, ktery pred navratem ten buffer vynuluje, pripadne tam nahraje nejakou znamou, nenahodnou hodnotu...

Ano, dalo by se to odhalit, pokud by ovšem někoho napadlo to odhalovat. Ale to je u řešení s XORem dost podobné: Vaše představa o neodhalitelnosti je naprostá iluze, stačilo by porovnat chování generátoru s jiným ekvivalentním, který používá trochu jinou posloupnost instrukcí.

[Jendа]

Ale to je u řešení s XORem dost podobné: Vaše představa o neodhalitelnosti je naprostá iluze, stačilo by porovnat chování generátoru s jiným ekvivalentním, který používá trochu jinou posloupnost instrukcí.

Opravdu? I když je to implementované tak, aby vylezlo SHA(NSAKEY || counter++ || serial number)?

[pc2005]

SHA(NSAKEY || counter++ || serial number)

Neznamenalo by to, že by RNRAND dávala v této situaci vždy stejnou sekvenci vůči historii volání po powerupu?

P.S. Ale nevím kdy by se měl ten counter inkrementovat.

[Lyco]

Counter by se musel inkrementovat při každém volání RDRAND, jinak by se hodnoty opakovaly.

Pochopitelně by se ten counter musel uložit do nějaké nepřechodné paměti. To se dá zařídit třeba malou EEPROM a kondenzátorem, který při poklesu napětí zařídí napájení pro zápis.

Nebo, teoreticky, by se dala použít paměť která je non-volatile sama od sebe, třeba memristor. (Ne že bych si myslel že je Intel tak pokrokový.)

[pc2005]

Tak to už je spíš sci-fi .

[Lyco]

> Osobně bych tedy raději data zamíchal ještě před zahashováním

Problém není v pořadí, ale v XORu. Kdybych dělal XOR ještě před hashováním, tak dostanu hash hashe, tedy stále zcela předvídatelnou funkci. Správné řešení by bylo např. jednotlivé zdroje spoji jako řetězce a ten pak zahashovat (kryptografickým hashem, pochopitelně). V tomto případě se totiž nemůže stát, že výsledek RDRANDu "zničí" předchozí data.

[Kvakor]

Tak si říkám, kam až by se muselo postoupit, aby bylo jisté, že hardwarový generátor náhodných čísel nemůže být "cinknutý" a vychází mi, že by to muselo být externí zařízení, nejleépe založenmé na kombinaci radioaktivní materiál+Geiger-Müllerův detektor (to celé v tlustostěné olověná nádobě) jako zdroj kvantové náhodnosti a elektronika složená s čistě diskrétních součástek, která by pouze posílala hezky tvarované impulzy na nějaký vstup, kde by vyvolávaly přerušení (např. sérivoý port).

Jenže takto získaná data se stejně musejí stejně zpracovat softwarem a i tak závisí na všem možném od SuperIO chipu na desce přes jádro a jeho zpracování přerušení (nejlepší by bylo co nejvíc realtime) až po samotné zpracování (viz Ramdnomness extractor na Wiklipedii). Mimo toho je objem dat velmi malý (desítky, max. stvoky bitů za sekundu).

PS: Na Fourmilab.ch je takovýto generátor (nazvaný HotBits) poměrně slušně popsaný, včetně softwaru. Tedy až na hardware, na který je použitý hotový detektor, který se u nás asi nesežene, nicméně GM trubice jde sehnat i v ČR (nová stojí okolo dvou-tří tisíc) a zbytek je relativně jednoduchý (viz třeba tady). Jediný problém je sehnat vhodný radioaktivní materiál

[:::]

Pokud mas kvalitni PRNG tak stovky bitu entropie za sekundu by meli stacit.

Kdyby na neco bylo potreba vic tak podle me by bylo nejlepsi pouzit vstup ze zarizeni ktery neni ke generovani nahodnych cisel primo urceny. Tam je mnohem mensi pravdepodobnost ze se tam podari neco schovat. Napriklad hashovat vstup z nejaky zasumneny web kamery...

[Jendа]

Napriklad hashovat vstup z nejaky zasumneny web kamery...

Pozor na integrovaný JPEG kodér, jehož funkcí je naopak šum a entropii odstraňovat ;).

[alkoholik]

Nejsi dost paranoidni. Vzhledem k tomu, ze polocas rozpadu koreluje se vzdalenosti zeme od slunce, prisel bys o par bitu sily podle toho, v ktere fazi roku bys generoval klic..
;)

[pc2005]

WOW to kdyby přišla erupce, tak můžeš ten výsledek zahodit . Prej to ovlivňuje tak den před samotnou erupcí (kolik by stálo NSA dopravit atomovku na slunce? ).

P.S. Docela by mě zajímalo zda v prostředí bez neutrin (asi?) by se některé izotopy staly stabilními.

P.P.S. (OT) Teď funguje ten mechanismus z "1969" dílu stargate (bez mimozemských technologií) .

[Jendа]

P.S. Docela by mě zajímalo zda v prostředí bez neutrin (asi?) by se některé izotopy staly stabilními.

On někdo ukázal, že se izotopy rozpadají (jen) díky neutrinům?

[pc2005]

Ne, ale prý různé izotopy reagují různou rychlostí a Země se okolo Slunce pohybuje extra blízko s malými výkyvy. Nejlepší by bylo, kdyby to měřili třeba na Voyageru 1. Je fakt, že stabilní je moc silné slovo, zvláště když není vyloučeno, že i proton není stabilní. Třeba takovej tantal 180m je protonu prakticky ekvivalentní (zatím nebyl pozorován žádný jeho rozpad).

Jinak vzhledem k rychlosti neutrina ve vesmíru neexistuje místo, kde by nebylo (možná tak černá díra, ale tam se měření dělá špatně, fyzik má práce na roztrhání ).

[Jendа]

Ne, ale prý různé izotopy reagují různou rychlostí a Země se okolo Slunce pohybuje extra blízko s malými výkyvy.

Já zatím viděl jenom jeden nějaký malý experiment, kde tohle pozorovali. Už to někdo ověřil?

[pc2005]

Hmmm máš pravdu, žádný článek, který to potvrzuje na mě nevypadl,resp. čekal bych, že při takovém objevu to bude někdo od 2006 měřit nepřetržitě (cyklus aktivity slunce trvá roky) a průběžně dodávat data. Navíc jsem našel vyvracející článek (že jsi ten článek viděl ještě před prvním postem ). Ale zase tihle naměřili fluktuaci :-/.

BTW Neutrino je schopno reagovat s galliem a přeměnit ho na nestabilní germanium.

[Grunt]

kolik by stálo NSA dopravit atomovku na slunce?

Vzhledem k tomu, že by si musel aktivovat minimálně Naquahdah či Naquadrii a ne blbé Lithium, tak asi hodně.

[jarok]

Nič nové pod Slnkom. Aj také riešenie (rádioaktívny rozpad) už bolo. Kedysi v 50-tych či 60-tych rokoch pre šifrovanie vládnych/vojenských/straníckych liniek medzi Moskvou a Berlínom a/alebo Prahou. Bohužiaľ, zdroj informácie už neviem, ani bližší spôsob fungovania.