Kvalitnφ zdroj nßhodn²ch Φφsel je v poΦφtaΦovΘ bezpeΦnosti stejn∞ cenn² jako p°φstupovß hesla, klφΦe nebo ostatnφ bezpeΦnostnφ prvky systΘmu. V lednovΘm Φφsle Chipu jsme vßs seznßmili s nov²m objevem v m∞°enφ entropie zdroje nßhodn²ch Φφsel. Nynφ si ukß₧eme, jak se takovΘ zdroje dajφ najφt v ka₧dΘm poΦφtaΦi a jak je sprßvn∞ vyu₧φt.
Nejprve si uv∞domme, co od kvalitnφho zdroje nßhodn²ch Φφsel (RNG, random number generator) vlastn∞ oΦekßvßme. Mo₧nß si vzpomenete, ₧e jsme v Φφslech 4/98 a₧ 6/98 o nßhodn²ch generßtorech psali. Tehdy vÜak Ülo o tzv. pseudonßhodnΘ generßtory (PRNG, pseudorandom number generators), kterΘ pracovaly zcela deterministick²m matematick²m postupem. Jsou v²bornΘ pro nejr∙zn∞jÜφ ·Φely a simulaΦnφ metody, kde je pot°eba velmi rychle generovat data, kterß majφ û ze statistickΘho hlediska û vÜechny p°φznaky nßhodn²ch dat. V t∞chto p°φpadech nevadφ, ₧e kdyby se na tato data blφ₧e podφvali hacke°i nebo profesionßlnφ luÜtitelΘ, mohli by ze znalosti vzorce pro jejich tvorbu nebo z p°edchozφch dat urΦit i nßsledujφcφ produkci generßtoru.
Od kvalitnφch nßhodn²ch Φφsel ovÜem chceme mnohem vφce, proto₧e mohou mφt bezpeΦnostnφ v²znam. Nßhodnß Φφsla se toti₧ p°φmo pou₧φvajφ jako Üifrovacφ klφΦe prakticky ve vÜech bezpeΦnostnφch protokolech (nap°. SSL) nebo pro tvorbu velmi v²znamn²ch dlouhodob²ch klφΦ∙, klφΦ∙ pro digitßlnφ podpis apod. P°i takovΘmto pou₧itφ je tedy nezbytn∞ nutnΘ kvalitu nßhodnΘho zdroje zaruΦit.
Po₧adavky na RNG
Budeme proto po₧adovat, aby znalost jakΘhokoliv mno₧stvφ p°edchozφch generovan²ch dat nedßvala analytikovi (·toΦnφkovi) ₧ßdnou Üanci pro predikci nßsledujφcφch bit∙. K tomu navφc p°edpoklßdßme, ₧e dotyΦn² ·toΦnφk mß k dispozici:
* pot°ebn² v²poΦetnφ v²kon;
* plnou znalost procesu generovßnφ;
* p°φstup ke stejn²m zdroj∙m, z nich₧ je konstruovßn generßtor (souΦßstky, software);
* mo₧nost testovat a pou₧φvat generßtor.
Pokud i za t∞chto p°edpoklad∙ nßÜ generßtor p°i ·tocφch obstojφ, m∙₧eme ho pova₧ovat za kvalitnφ. P°ipome≥me, ₧e v kontextu pou₧itφ RNG je pot°eba vy°eÜit i obranu proti ·tok∙m systΘmov²m, fyzick²m apod., kter²mi se ovÜem v tomto Φlßnku nebudeme zab²vat. Zde nßm p∙jde jen o "kvalitu nßhodnosti" generovan²ch Φφsel.
True-random generßtory
╚φsla, o nich₧ je °eΦ, se naz²vajφ skuteΦn∞ nßhodnß Φφsla a produkujφ je tzv. true-random generßtory. Nenφ jich mnoho, ani v p°φrod∞, ani v osobnφm poΦφtaΦi. Mezi nejkvalitn∞jÜφ pat°φ generßtory na bßzi radioaktivnφho rozpadu a na bßzi nap∞¥ov∞-proudov²ch zm∞n zp∙soben²ch tepeln²m Üumem a kvantov²mi jevy v polovodiΦov²ch strukturßch. Radioaktivnφ materißl se ke generovßnφ nßhodn²ch bit∙ skuteΦn∞ pou₧φval (i u nßs). Pokud poΦet zachycen²ch Φßstic vznikajφcφch jeho rozpadem za urΦitou Φasovou jednotku byl lich², za°φzenφ vygenerovalo jedniΦku, jinak nulu. Trochu drahΘ û ale jinΘ nezpochybnitelnΘ generovßnφ nßhodn²ch bit∙ p°ed n∞kolika desφtkami let neexistovalo. TakovΘ generßtory proto pou₧φvaly i vÜechny sv∞tovΘ velmoci p°i tvorb∞ jednorßzovΘho hesla (one-time pad) pro Üifrovßnφ diplomatick²ch spoj∙.
Z tohoto p°φkladu je vid∞t, jakΘ asi po₧adavky na true-random generßtor klademe a jak² typ generßtoru by pro nßs byl ideßlnφ. Mßlokdo by nßm toti₧ oponoval, ₧e je schopen rekonstruovat nebo predikovat natolik slo₧it² p°φrodnφ proces, jako je radioaktivnφ rozpad, a to ve form∞, v jakΘ je vyu₧it. Praxe opravdu potvrzuje, ₧e tento generßtor respektuje ka₧d², zatφmco u jakΘhokoliv jinΘho principu se v₧dy najde n∞jak² kritik.
SouΦasn² stav a trendy
Radioaktivnφ materißl pozd∞ji nahradily polovodiΦovΘ prvky, kde se entropie odvozuje od nedeterministick²ch zm∞n v nap∞tφ a proudu na vybran²ch p°echodech. Pochopiteln∞ si to vy₧ßdalo trochu "vφc v∞dy", nebo¥ nßhodnost zm∞n bylo pot°eba prokßzat, zjistit, za jak²ch podmφnek nastßvajφ, a odpovφdajφcφ souΦßstky kalibrovat. NicmΘn∞ se to poda°ilo zvlßdnout a dnes u₧ se jednß o standardizovan² postup. Nßr∙st po₧adavk∙ na p°φtomnost kvalitnφho generßtoru v PC potΘ vedl k pou₧φvßnφ externφch generßtor∙ ve form∞ (pom∞rn∞ drah²ch) p°φdavn²ch desek. V souΦasnΘ dob∞ se zaΦφnajφ RNG realizovat v Φipech, kterΘ se integrujφ p°φmo na zßkladnφ desky u₧ p°i v²rob∞ nov²ch osobnφch poΦφtaΦ∙. V²robce k tomu vedou novΘ bezpeΦnostnφ po₧adavky kryptografie, kterß se pou₧φvß k ochran∞ dat v lokßlnφch sφtφch, na internetu, v elektronickΘmu obchodu, pro Üifrovßnφ a podpis elektronickΘ poÜty v a dalÜφch aplikacφch. Prvnφm p°φkladem tohoto postupu m∙₧e b²t Φip od Intelu (viz infotipy).
Zdroje nßhody v poΦφtaΦi
Pokud nemßme k dispozici specißlnφ Φip, desku nebo externφ generßtor, nezbude nßm ne₧ si pomoci sami. UvedenΘ metody samoz°ejm∞ nejsou ideßlnφ, my se vÜak budeme sna₧it z naÜeho poΦφtaΦe vy₧dφmat maximum. V p°ipojenΘ tabulce uvßdφme p°φklady mo₧n²ch zdroj∙ û jde nßm p°itom o pokud mo₧no fyzikßlnφ zdroje, kde bude nepredikovatelnost chovßnφ velmi dobrß a entropie p°φsluÜnΘho zdroje co nejv∞tÜφ (a pokud mo₧no m∞°itelnß).
Jak konstruovat generßtor
Existuje vφce cest, jak zkonstruovat RNG. Ukß₧eme si zde standardnφ postup, kter² se sklßdß ze Φty° krok∙:
* sb∞r entropie;
* komprese;
* nastavenφ kryptografickΘho generßtoru;
* expanze.
Jak u₧ jist∞ tuÜφte ze t°etφho kroku, podstata spoΦφvß v tom, ₧e vlastnφ generovßnφ nßhodn²ch Φφsel p°esouvßme na kryptografickΘ generßtory. Umφ toti₧ p°esn∞ to, co chceme, tj. generovat nepredikovatelnou posloupnost Φφsel û viz vlastnosti, kterΘ jsme si definovali v odstavci "po₧adavky na RNG".
Kde je ale ta neurΦitost, o kterou se sna₧φme? Neutφkßme od problΘmu, kdy₧ chceme neurΦitost a pou₧φvßme deterministickΘ postupy? Nikoliv û vtip je toti₧ v tom, ₧e v prvnφm kroku zφskanou entropii pou₧ijeme k nastavenφ generßtoru do neurΦitΘho a neznßmΘho poΦßteΦnφho stavu. Kryptografick² generßtor je p°itom konstruovßn tak, ₧e do svΘho v²stupu v ka₧dΘm kroku p°enßÜφ entropii svΘho poΦßteΦnφho stavu. Dφky tomu, ₧e vyu₧φvß jednosm∞rnΘ funkce nebo blokovΘ Üifry, nenφ mo₧nΘ obrßtit jeho chod zp∞t, a staΦφ jej tedy nastavit do neznßmΘho, neurΦitΘho a nedeterministickΘho poΦßteΦnφho stavu.
V²hodnΘ takΘ je, ₧e poΦßteΦnφ nastavenφ vy₧aduje °ßdov∞ pouze desφtky a₧ stovky nßhodn²ch bit∙, zatφmco nßsledujφcφ megabajty nßhodn²ch Φφsel generuje kryptografick² generßtor sßm, a to nesrovnateln∞ rychleji, ne₧ kdybychom zφskßvali entropie z vlastnφho poΦφtaΦe p°φmo. Navφc m∙₧eme generßtor kdykoliv op∞t restartovat (pokud z dostupn²ch zdroj∙ op∞t nasbφrßme dost entropie û po vygenerovßnφ urΦitΘho objemu dat, po stanovenΘ dob∞ apod.). Poj∩me se u₧ ale podφvat na jednotlivΘ kroky podrobn∞ji.
Sb∞r neurΦitosti a jejφ komprese
Cφlem tohoto kroku je zφskat z poΦφtaΦe K bit∙ neurΦitosti. ╪ßdov∞ jde v₧dy o n∞kolik desφtek a₧ stovek bit∙, pro jednoduchost zde uva₧ujme K = 160. P°itom se osv∞dΦuje dbßt n∞kolika standardnφch rad. Za prvΘ je vhodnΘ neurΦitost zφskßvat souΦasn∞ z n∞kolika zdroj∙ (t°eba ze vÜech uveden²ch v tabulce). Za druhΘ, zφskanß data prost∞ jen °adφme za sebou bez ladu a skladu a nemusφme je oΦiÜ¥ovat od "deterministickΘho balastu". Starßme se jen o to, aby v jejich souhrnu bylo obsa₧eno po₧adovanΘ mno₧stvφ entropie (z bezpeΦnostnφch d∙vod∙ sbφrßme dvoj- a₧ trojnßsobek). A za t°etφ, jakmile mßme k dispozici dostateΦnΘ mno₧stvφ dat (zßle₧φ jen na jejich entropii, nikoli na velikosti), aplikujeme na n∞ haÜovacφ funkci. Pro jednoduchost zde budeme uva₧ovat SHA-1, jejφ₧ v²stup je 160 bit∙. V²sledkem haÜovßnφ je °et∞zec 160 nßhodn²ch, nepredikovateln²ch bit∙, kterΘ p°edstavujφ obraz vstupnφch dat obsahujφcφch tuto entropii û tφm je vy°eÜen problΘm "destilace" entropie z nich.
HaÜovacφ funkce zde vlastn∞ vykonßvß dv∞ ·lohy û jednak p°enßÜφ entropii, jednak komprimuje vstupnφ data na v²stup. Mimo jinΘ se zde vyu₧φvß skuteΦnosti, ₧e haÜovacφ funkce p°evßd∞jφ siln∞ korelovanΘ vstupy (liÜφcφ se t°eba o jeden bit nebo p°ehozenφm dvou bit∙) na v²stupy, v nich₧ p°edchozφ algebraickΘ vztahy a zßvislosti jsou zcela pot°eny û nejsou prokazatelnΘ ani v²poΦetn∞ zjistitelnΘ a vypadajφ zcela nßhodn∞ a nezßvisle. HaÜovacφ funkce zajistφ, ₧e v nasbφran²ch datech zßle₧φ jak na po°adφ, tak na hodnot∞ ka₧dΘho bitu zdrojov²ch dat.
HaÜovacφ funkce je ale vzhledem k t∞mto vlastnostem takΘ schopna vn∞jÜkov∞ kamuflovat i Üpatn² zdroj neurΦitosti. Nap°φklad posloupnost SHA-1(systΘmov² Φas), snφmanß jakkoli Φasto, bude pro v∞tÜinu hacker∙ nep°ekroΦiteln²m zdrojem nßhody, pokud nebudou znßt tento p°edpis (touto cestou vÜak jφt nechceme). P°ipome≥me jeÜt∞, ₧e vlastnostmi haÜovacφch funkcφ jsme se blφ₧e zab²vali v Chipu 3/99 a konkrΘtn∞ SHA-1 v Chipu 4/99. Vra¥me se vÜak ke sb∞ru entropie.
M∞°enφ neurΦitosti
Ka₧d² zdroj entropie z poΦφtaΦe, kter² vyu₧ijeme, musφme p°edem dokonale prov∞°it. K m∞°enφ entropie je mo₧nΘ pou₧φt Maurer∙v-Coron∙v test (viz Chip 1/00). Pokud si nevφme rady, existuje takΘ velmi hrub² postup, jak ji odhadnout. Uvßdφme ho zde jen proto, ₧e se jednß o zaveden² ·zus, ale jako globßln∞ bezpeΦn² ho v ₧ßdnΘm p°φpad∞ nedoporuΦujeme. Je velmi jednoduch². Data komprimujeme nejlepÜφm komprimaΦnφm programem, kter² mßme k dispozici, s cφlem dosßhnout co nejv∞tÜφ komprese. PoΦet bit∙ zkomprimovanΘho souboru vyd∞lφme dv∞ma a potΘ jeÜt∞ bezpeΦnostnφ konstantou (2, 10, ..., fantazii se meze nekladou). V²sledkem je p°ibli₧n² poΦet bit∙ entropie.
Tento postup ale nemusφ v₧dy fungovat. Vezm∞me nap°φklad jako zdroj nßhody pohyb myÜi. Vyzveme-li u₧ivatele, aby nßhodn∞ pohyboval myÜφ, a ten bude mφt snahu to skuteΦn∞ ve vlastnφm zßjmu d∞lat, pak m∙₧eme oΦekßvat, ₧e po₧adovan²ch 160 bit∙ entropie dosßhneme b∞hem n∞kolika mßlo sekund. Pokud vÜak toto ·silφ bude u₧ivatel sabotovat, zcela jist∞ nßm tato doba nestaΦφ. Abychom ho p°elstili, museli bychom po₧adovat, aby myÜφ nap°φklad obkresloval zadan² obrazec, a sofistikovan∞ kontrolovat, ₧e to skuteΦn∞ d∞lß, abychom mohli nßhodnΘ odchylky v jeho tazφch vyhodnocovat jako zdroj entropie.
PodobnΘ je to i s Φasto vyu₧φvan²m m∞°enφm Φasu p°i psanφ na klßvesnici. B∞₧n∞ se sleduje doba mezi stisky klßves, trvßnφ jejich stisku a obsah. TakΘ toto se vÜak dß sabotovat û a v∙bec nejlepÜφ je proto lidsk² Φinitel z t∞chto metod vylouΦit. Z bezpeΦnostnφho hlediska bychom rovn∞₧ m∞li zva₧ovat situace, kdy a jak m∙₧e b²t p°φsluÜn² zdroj entropie ovlivn∞n p°φpadn²m ·toΦnφkem. A¥ budeme ale vyu₧φvat cokoli, musφme b²t p°esv∞dΦeni, ₧e po₧adovanΘ mno₧stvφ entropie skuteΦn∞ nasbφrßme.
Standardnφ postupy expanze
P°edpoklßdejme tedy, ₧e jsme n∞jakou vhodnou metodou obdr₧eli 160bitovou hodnotu, kterß je zaruΦen∞ nßhodnß. Budeme ji v dalÜφm vyu₧φvat bu∩ jako klφΦ (KEY) pro blokovΘ Üifry, nebo jako poΦßteΦnφ nastavenφ (SEED) pro haÜovacφ funkce (h). èifrovßnφ dat D klφΦem KEY a vhodnou blokovou Üifrou oznaΦme EKEY(D). Standardnφ postupy expanze nßhodn²ch dat lze jednoduÜe popsat pseudok≤dy podle obrßzku.
Vstupem je hodnota SEED, v²stupem je posloupnost r(1), r(2), ...., r(N). Proto₧e tyto standardnφ postupy v∞tÜinou jsou (nebo alespo≥ mohou b²t) znßmy ·toΦnφkovi, kvalita jejich v²stupu zßvisφ na kvalit∞ prvku, kter² ·toΦnφk neznß, tj. hodnoty SEED. Tuto hodnotu musφme ochrßnit, vÜe ostatnφ za nßs ud∞lß kryptografie.
Varianty tvorby RNG
Uve∩me si zde alespo≥ n∞kterΘ varianty zßkladnφch postup∙, s nimi₧ lze konstruovat r∙znΘ typy RNG:
* po vygenerovßnφ urΦitΘho mno₧stvφ dat se automaticky p°echßzφ na novΘ nastavenφ, tj. na vytvo°enφ novΘ hodnoty SEED;
* b∞hem procesu generovßnφ probφhß kontinußln∞ sb∞r entropie pro novΘ nastavenφ;
* v²stupy z n∞kolika zdroj∙ entropie se mohou vzßjemn∞ dopl≥ovat, kombinovat a obnovovat v r∙zn²ch Φasov²ch intervalech;
* p°i vytvß°enφ novΘ hodnoty SEED z r∙zn²ch zdroj∙ entropie je mo₧nΘ k nim p°idat i starou hodnotu SEED;
* p°i realizaci p°edchozφho kroku se nepou₧ije starß hodnota SEED p°φmo, ale prost°ednictvφm h(SEED), z bezpeΦnostnφch d∙vod∙ se toti₧ SEED v poΦφtaΦi neuchovßvß p°φmo;
* v kroku expanze je mo₧nΘ pou₧φt spoleΦn∞ s °et∞zcem KEY i urΦitou tajnou hodnotu SECRET, jejφ₧ ochran∞ je v danΘm systΘmu v∞novßna zv²Üenß pozornost.
Zßv∞r
Generßtory nßhodn²ch Φφsel se Φasto pou₧φvajφ pro senzitivnφ bezpeΦnostnφ ·Φely. Proto je nezbytnΘ v∞novat jejich tvorb∞ stejnou pozornost jako jin²m bezpeΦnostnφm prvk∙m. Zde jsme uvedli standardnφ postupy tvorby takov²ch generßtor∙, kterΘ vyu₧φvajφ kryptografickΘ postupy k tomu, aby zajistily nepredikovatelnost sv²ch v²stup∙ a souΦasn∞ obsahovaly entropii originßlnφho zdroje.
