Jaderné noviny – 13. 3. 2014: Hardwarové generátory náhodných čísel a bezpečnost

1. 4. 2014 | Luboš Doležel | Jaderné noviny | 4881×

Aktuální verze jádra: 3.14-rc6. Statistiky cyklu 3.14. Ředění náhodnosti: Přidání RDSEED; Míchání a ředění.

Obsah

• Aktuální verze jádra: 3.14-rc6
• Statistiky cyklu 3.14
• Ředění náhodnosti
  • Přidání RDSEED
  • Míchání a ředění

Aktuální verze jádra: 3.14-rc6

Aktuální vývojová verze jádra je 3.14-rc6 vydaná 9. března. Linus k ní řekl: Neobjevily se žádné velké problémy, ale vynořilo se vcelku dost malých zádrhelů, které by tam v této fázi cyklu být neměly. Navíc je rc6 znatelně větší než rc5. Proto opravdu doufám, že příští týden bude klidnější, jinak budu uvažovat o rc8 nebo dokonce rc9.

Stabilní aktualizace: verze 3.13.6 a 3.10.33 byly vydány 6. března; verze 3.4.83 následovala 11. března.

Statistiky cyklu 3.14

Obvykle je v době vydání -rc6 konečná verze na dohled. Tentokrát ale Linus vyhrožuje nutností -rc8 nebo dokonce -rc9 kvůli množství zbývajících problémů. I kdyby bylo vydání konečné verze ještě daleko, situace kolem 3.14 by už měla být dostatečně stabilní na to, aby dávalo smysl se podívat na to, odkud přišly změny do tohoto vydání. Ve zkratce to lze popsat jako „nic nezvyklého“ spolu s pokračováním stávajících trendů.

V době psaní tohoto textu se vývojový cyklus dočkal něco přes 12 000 neslučovacích sad změn od přesně 1400 vývojářů. Tyto změny přidaly 591 000 řádek kódu a odstranily 250 000 řádek kódu, což dává čistý přírůstek 341 000 řádek kódu. Nejaktivnějšími vývojáři tentokrát byli:

Nejaktivnější vývojáři verze 3.14

Podle počtu změn H Hartley Sweeten 278 2,3 % Laurent Pinchart 232 1,9 % Jingoo Han 174 1,4 % Rashika Kheria 162 1,3 % Geert Uytterhoeven 138 1,1 % Tejun Heo 123 1,0 % Sachin Kamat 122 1,0 % Kuninori Morimoto 110 0,9 % Sujith Manoharan 97 0,8 % Linus Walleij 89 0,7 % Wei Yongjun 86 0,7 % Alex Deucher 82 0,7 % Stephen Warren 81 0,7 % Lars-Peter Clausen 79 0,7 % Ville Syrjälä 78 0,6 % Namhyung Kim 76 0,6 % Thierry Reding 74 0,6 % Johannes Berg 73 0,6 % Christoph Hellwig 73 0,6 % Ding Tianhong 71 0,6 %

Podle změněných řádek Greg Kroah-Hartman 73035 10,5 % Micky Ching 23657 3,4 % Stephen Boyd 17511 2,5 % Paul Gortmaker 17511 2,5 % Greg Rose 16428 2,4 % Tero Kristo 14509 2,1 % Ben Skeggs 13320 1,9 % Sergio Aguirre 8388 1,2 % Ben Hutchings 8002 1,2 % Tejun Heo 7975 1,2 % Laurent Pinchart 7799 1,1 % Frank Haverkamp 7424 1,1 % Takashi Iwai 6247 0,9 % Thomas Hellstrom 6148 0,9 % Tom Lendacky 6103 0,9 % Upinder Malhi 6012 0,9 % Sujith Manoharan 5837 0,8 % Peter De Schrijver 5680 0,8 % H Hartley Sweeten 5586 0,8 % Rob Clark 5345 0,8 %

Po krátké odmlce se H. Hartley Sweeten vrátil do žebříčku podle počtu změn díky další práci na opravách ovladačů Comedi ve stromu staging. Laurent Pinchart odvedl mnoho práce na Video4Linux a stromu architektury ARM, zatímco Jingoo Han pokračuje v pročišťování stromu ovladačů. Rashika Kheria přispěla řadou patchů pročišťujících ovladače a Geert Uytterhoeven odvedl mnoho práce na architektuře m68k a subsystémech embedded ovladačů.

Greg Kroah-Hartman se často objevuje vysoko v žebříčku podle počtu změněných řádek; tentokrát je to díky přidání ovladače Realtek 8821 PCI WiFi a nadstandardního počtu revertovaných patchů. Micky Ching přidal do stromu staging ovladače rts5208 a rts5288, Stephen Boyd přispěl podporou pro různý hardware od Qualcommu, Paul Gortmaker (mimo jiné) pročistil řadu hlavičkových souborů a Greg Rose přispěl síťovým ovladačem i40evf.

Vývoj jádra 3.14 podpořilo alespoň 210 zaměstnavatelů. Nejaktivnějšími byli:

Nejaktivnější zaměstnavatelé ve verzi 3.14

Podle počtu změn Intel 1233 10,2 % (None) 1075 8,9 % Red Hat 877 7,3 % (Unknown) 701 5,8 % Linaro 528 4,4 % Samsung 523 4,3 % SUSE 396 3,3 % IBM 351 2,9 % Renesas Electronics 339 2,8 % Google 324 2,7 % Texas Instruments 288 2,4 % Vision Engraving Systems 278 2,3 % (Consultant) 268 2,2 % NVIDIA 248 2,1 % FOSS Outreach Program for Women 237 2,0 % Huawei Technologies 211 1,8 % Freescale 210 1,7 % Qualcomm 157 1,3 % Oracle 152 1,3 % Broadcom 144 1,2 %

Podle počtu řádek Linux Foundation 78675 11,4 % Intel 69526 10,0 % (None) 47083 6,8 % Red Hat 46371 6,7 % Texas Instruments 28274 4,1 % (Unknown) 25716 3,7 % IBM 25427 3,7 % Realsil Microelectronics 23676 3,4 % SUSE 22686 3,3 % NVIDIA 20720 3,0 % Samsung 19988 2,9 % Wind River 19946 2,9 % Code Aurora Forum 17878 2,6 % Google 13452 1,9 % Linaro 12945 1,9 % Cisco 12747 1,8 % (Consultant) 12301 1,8 % Qualcomm 10806 1,6 % Renesas Electronics 9655 1,4 % Freescale 9533 1,4 %

Je tu jen málo překvapení; místo toho vidíme pokračování trendů, které pozorujeme už delší dobu. Po krátkém skoku ve verzi 3.13 množství příspěvků od dobrovolníků pokračuje v klesání. Vypadá to, že se Intel natrvalo usadil na vrcholu žebříčku podle počtu změn, kterými přispěl. Nadále roste objem příspěvků od výrobců z oblasti mobilních a embedded zařízení. Bylo by lákavé zvolat, že verze 3.14 bude obsahovat opravu v ovladači nouveau, která přišla přímo z NVIDIA, ale pravdou je, že to je už podruhé; první oprava byla potichu začleněna už do verze 3.9 počátkem roku 2013.

Trochu odlišné výsledky se objeví, když se podíváme na „signoffy“ od jiných lidí než autorů. Tyto tagy jsou přidány správci subsystémů při přijetí patche; tato statistika tedy může prozradit, přes koho jdou patche do jádra. Po přiřazení signoffů k zaměstnavatelům získáme tyto výsledky:

Nejvíce signoffů ve verzi 3.14

Podle vývojáře Greg Kroah-Hartman 1516 13,1 % David S. Miller 1128 9,7 % Mark Brown 502 4,3 % Andrew Morton 465 4,0 % Mauro Carvalho Chehab 370 3,2 % John W. Linville 352 3,0 % Simon Horman 256 2,2 % Arnaldo Carvalho de Melo 237 2,0 % Daniel Vetter 225 1,9 % Rafael J. Wysocki 173 1,5 % Jeff Kirsher 166 1,4 % Chris Mason 160 1,4 % Linus Walleij 148 1,3 % Ingo Molnar 146 1,3 % Brian Norris 140 1,2 % John Crispin 129 1,1 % Jesse Brandeburg 127 1,1 % Josef Bacik 126 1,1 % Johannes Berg 125 1,1 % Benjamin Herrenschmidt 121 1,0 %

Podle zaměstnavatele Red Hat 2336 20,2 % Linux Foundation 1548 13,4 % Intel 1367 11,8 % Linaro 1093 9,4 % Google 649 5,6 % Samsung 647 5,6 % (None) 417 3,6 % Facebook 283 2,4 % SUSE 270 2,3 % Renesas Electronics 265 2,3 % IBM 262 2,3 % Texas Instruments 200 1,7 % Broadcom 183 1,6 % (Unknown) 159 1,4 % Fon 129 1,1 % NVIDIA 97 0,8 % Cisco 91 0,8 % Pure Storage 91 0,8 % (Consultant) 82 0,7 % University of Cambridge 77 0,7 %

Koncentrace do několika málo firem už není taková, jak tomu bývalo, ale i tak více než polovina patchů začleněných do 3.14 prošla přes zaměstnance pouhých čtyř organizací. Linaro a Facebook se v tomto seznamu posunuli výše; v obou případech je to díky tomu, že přijali vývojáře, kteří už roli správců subsystému měli. I zde postupem času podíl připadající na vývojáře dobrovolníky pomalu klesá.

Suma sumárum, mašinérie vývoje jádra se zdá být v celkem ustáleném stavu, vše běží hladce a změny probíhají velmi pozvolna. Proto je otázkou, zda ještě dává smysl se statistikami zabývat po každém vydání, nebo zda by bylo lepší hodnotit až celý rok.

Ředění náhodnosti

Jedním z užitečnějších důsledků Snowdenových odhalení může být přísnější kontrola zabezpečení našich systémů. I když nikdo nemůže tvrdit, že všechny problémy byly nalezeny a opraveny, v řadě oblastí došlo za poslední rok ke zlepšení. Jednou z oblastí, která se v poslední době dočkala pozornosti, je generování náhodných čísel v jádře. Dva nedávné patche v tomto trendu pokračují, i když je těžké určit, zda jde o přímý dopad odhalení špehování NSA (a dalších rozvědek).

Oba patche mění stav „zdroje náhodnosti“ [entropy pool], který slouží ke generování náhodných čísel v /dev/random i /dev/urandom. Na tento zdroj se váže (konzervativní) odhad obsaženého množství entropie (neboli stavu, který nemůže útočník zjistit). Vše, u čeho se má za to, že opravdu přidává entropii, je v tomto odhadu zohledněno, zatímco jiné, dost možná útočníkem řízené vstupy jsou zkrátka přimíchány, aniž by došlo k úpravě odhadu. Odhad entropie se používá k blokování těch, kteří čtou /dev/random, pokud je požadovaný objem dat větší než množství entropie ve zdroji.

Přidání RDSEED

První patch je od H. Petera Anvina a přidává podporu instrukce RDSEED do jádra. RDSEED je instrukce přidaná do procesorů Intel, která vrací plně připravenou entropii vhodnou pro použití jako seed pro PRNG. Patche přimíchávají čtyři bajty z výstupu RDSEED do zdroje při bootu (bez započtení zvýšení entropie). Navíc jsou čtyři bajty generovány pomocí této instrukce jednou za sekundu a následně přimíchány do zdroje. Také se používá pro „nouzové naplnění“: 64 bajtů z RDSEED je vzato, pokud právě bude /dev/random blokovat kvůli nedostatku množství entropie. V obou posledních případech se jsou za každý bajt výstupu RDSEED připočteny čtyři bity do odhadu množství entropie.

Někteří jsou toho názoru, že by se za výstup black-boxu generujícího náhodná čísla v hloubi čipu od Intelu neměl odhad vůbec zvyšovat. Jde o těžkou otázku, jelikož tomu, aby instrukce vracela sekvence známé NSA, nestojí v cestě žádné technické překážky a nikdo (přinejměnším mimo Intel) si nemůže být jist tím, že tomu tak není. I když se to může zdát paranoidní, řada dříve paranoidních představ se během minulého roku přesunula do kategorie uvěřitelných. Tyto obavy ale nebyly vzneseny kvůli patchům RDSEED.

Míchání a ředění

Druhý zmiňovaný patch, tentokrát od Keesa Cooka, přidává výstup nově vytvořené instance hardwarového RNG do zdroje entropie. Při registraci RNG (přes hwrng_register()) je do výstupu přimícháno šestnáct bajtů jeho výstupu, ale bez navýšení údaje o množství entropie. Jason Cooper měl obavy, že i pouhé přimíchání těchto bajtů do zdroje by mohlo vést k problémům: Zařazením tohoto patche, i bez zvyšování množství entropie, získává zlotřilé hwrng mnohem větší vliv na počáteční stav zdrojů entropie.

Cookovi to ale nepřišlo odlišné od míchání jiných náhodných nebo na systému závislých údajů při bootu:

Určitě nechci být tím, kdo by oslaboval zdroj entropie. Ale myslím si, že se tento patch nijak neliší od jiných, které přidávájí do zdroje MAC adresu síťové karty – jde o to vzít něco z mého systému, co je jedinečné nebo náhodné, a podpořit tak seed entropie. Přišlo by mi hloupé, kdybych načetl modul hwrng-tpm a nemělo to vliv na můj systémový zdroj entropie.

Navíc se ozval Matt Mackall, bývalý správce subsystému pro generování náhodných čísel, s připomenutím důležité vlastnosti míchající funkce. Jelikož je tato funkce vratná, přimíchání dat řízených útočníkem do zdroje nikdy nevede k odstranění náhodnosti, která tam předtím byla:

Míchací funkce ve zdroje je úmyslně _vratná_. Jde o zásadní vlastnost pro bezpečnost.

To znamená, že pokud máme počáteční tajný stav zdroje X a útočníkem podstrčená data Y, pak můžeme udělat:

X' = mix(X, Y)

a

X = unmix(X', Y)

Z tohoto je vidět, že kombinace (X' a Y) stále obsahuje informaci, která byla původně v X. Jelikož určitě není v Y, pak musí celá zůstávat v X'.

To Coopera moc neuklidnilo, stále měl obavy z přimíchání výstupu hardwarových RNG zkraje bootu systému. Měl strach, že by tyto bajty otrávily zdroj, ale Mackall zopakoval svůj argument jinými slovy:

Pokud je zdroj v útočníkovi známém stavu zkraje bootu, přidání útočníkem řízených dat tento stav nezhoršuje. Pravdou je, že pokud nemá útočník dokonalou kontrolu nad vstupy, pak přimíchání dalších věcí udělá útok exponenciálně složitějším.

Jinými slovy: přimíchání nemůže nikdy odstranit neznámost obsahu zdroje, může ji jedině přidat. Proto je jediným důvodem, proč něco do zdroje nepřimíchat, výkon.

Ačkoliv měl Mackall o vratnosti (a jejích dopadech) míchací funkce jasno už při návrhu, vypadá to, že ostatní vývojáři o této vlastnosti nevěděli. Je to zajímavá vlasnost, která dává smysl, pokud o ní víte, ale jinak je to poněkud neintuitivní. V každém případě Cooper své námitky stáhl a správce hardwarových RNG Herbert Xu patch zařadil do fronty. Měli bychom jej spatřit ve verzi 3.15.

       

Komentáře

[ndd]

pokud máme počáteční tajný stav zdroje X a útočníkem podstrčená data Y

přimíchání nemůže nikdy odstranit neznámost obsahu zdroje, může ji jedině přidat.

Ibaze ten zdroj je pre procesor znamy. A ked bude Intel velmi zakerny, tak moze kludne RDSEED implementovat tak, ze bude vracat presne rovnake cisla ako iny zdroj entropie (napr. bude pocitat s nejakym vzorom pristupu do pamate). Pri XORe nam taky nahodny generator bude vracat napr. same nuly alebo co chceme.

V zaujme bezpecnosti to mozeme obmedzit tak, ze bude nejaky seed MAC adresa sietovky (napriklad) - ta sa da vzdialene zistit a hned mozeme generovat rovnake nahodne cisla ako ten pocitac.

Naproti tomu ma nenapada rozumny sposob, ako by procesor mohol ovplyvnit nahodnost jemu znamych pseudonahodnych cisel bez svojej instrukcie - mohol by sice nieco "zle spocitat", ale to je velmi napadne.

[chrono]

Ak by také niečo dokázal pri inštrukcii RDSEED, tak by si s tým určite poradil aj bez nej.

[ndd]

Ako bez zvysenia narocnosti?

[chrono]

Ak by pri tej inštrukcii dokázal zistiť, kde má OS uložené údaje, ktoré potom bude chcieť zmanipulovať, tak to určite dokáže aj bez tej inštrukcie.

[ndd]

Lenze priama manipulacia "vypoctovych vysledkov" je velmi nachylna na nahodne objavenie, na rozdiel od manipulacie vysledku nejakej instrukcie, ktora ma aj tak vracat nahodne data. Alebo to chces robit inak?

[Zopper]

Jedna věc je provést útok stylem "vygeneruju predikovatelnou hodnotu", druhá věc je znát kompletní stav systému. Pokud by ten CPU mohl zjistit, co je aktuálně v poolu (a tedy dokázal interpretovat linuxové jádro, kde je který paměťový prostor...), tak nepotřebuješ takhle oslabovat generátor, stačí natvrdo přepsat pool nulama (či náhodně vypadající hodnotou) a zvýšit hodnotu entropie.

A nebo udělat jakýkoliv jiný útok, protože pokud ví co a jak, tak v tuhle chvíli má to CPU větší možnosti, než root. Jinak, tohle je právě to, proč vznikla petice [1] za odstranění RdRand z jádra, kterou Linus odmítl.

[1] http://www.change.org/en-GB/petitions/linus-torvalds-remove-rdrand-from-dev-random-4

[ndd]

Nemusi vediet plne interpretovat Linuxove jadro. Staci, ked sa nauci (vymyslim si), ze pristup postupne na adresy x az x+19 a na kazdej nejaky shift, bitovy OR a XOR ma pouzit k vygenerovaniu "svojej" hodnoty. Zhodou okolnosti nemusi ist o generator nahodnych cisel - prepisanie "nenahodnych" hodnot nulami by bolo asi programatormi rychlo odhalene. Ked sa na zaklade hodnot vrati iny vysledok "nahodneho cisla", tak to nie je az take napadne.

[Jirka W.]

Pověsit škodlivý kód na instrukci, kterou uživatel vůbec nemusí použít, by moc rozumné nebylo. To je, jako by se počítačový vir přidal do seznamu nainstalovaných programů s možností odinstalace. Kdyby chtěl Intel ovlivňovat výsledky generátoru náhodných čísel, udělá to tak, aby tomu nemohl uživatel zabránit.

[ndd]

Ibaze robit nieco v PC tak, aby tomu uzivatel nemohol zabranit, to dost dobre nejde. Ked to teda ma zaroven fungovat. Kludne navrhnite riesenie - to moje predchadzajuce je trivialne a myslim, ze by to Intel zvladol kludne implementovat.

[chrono]

Lenže to by procesor musel vedieť, aké sú tie údaje veľké, kde sa nachádzajú, čo sa s nimi bude robiť (aby to vygenerovanie hodnoty malo želaný účinok)... Ak by také niečo dokázali, tak by určite mohli urobiť čokoľvek (napr. odlíšiť tú časť, ktorá kontroluje, či generované náhodné údaje nie sú nejako upravované).

[Jendа]

Pokud tam je tohle

if (!arch_get_random_long(&v))
  break;
hash.l[i] ^= v;

(což se nejspíš přeloží jako RDRAND a pak hned XOR s něčím), tak není potřeba přílišná invence, aby procesor zjistil, co se asi stane…

(napr. odlíšiť tú časť, ktorá kontroluje, či generované náhodné údaje nie sú nejako upravované)

To mi přijde jako mnohem složitější (udělat to tak, aby na to brzo někdo nepřišel).

[chrono]

Predpokladám, že to, že kód využívajúci tú funkciu musí vyzerať práve takto a nikdy inak, je popísané v nejakej dokumentácii, aby to jednotlivé OS mohli správne implementovať. :)

[Jendа]

V případě potřeby se detekce opraví updatem mikrokódu.

[ndd]

+1; uz som sa bal, ze to napadlo len mna.

[chrono]

Takže vlastne stačí upraviť ten kód a zakázať aktualizáciu mikrokódu procesoru a problém je vyriešený. :)

[Jendа]

Pověsit škodlivý kód na instrukci, kterou uživatel vůbec nemusí použít, by moc rozumné nebylo.

Zajímavé. Přitom se šíří spousta škodlivého software přes e-maily, které uživatel vůbec nemusí otevřít, webové stránky, které uživatel vůbec nemusí navštívit…