V tomto Φlßnku vßs seznßmφme s nov²m vyu₧itφm blokovΘ Üifry jak pro generovßnφ nßhodn²ch Φφsel, tak pro Üifrovßnφ. Ukß₧eme vßm, jak lze blokovou Üifru v²hodn∞ p°em∞nit na proudovou pomocφ b∞₧nΘho ΦφtaΦe. Tento nov² operaΦnφ modus byl oficißln∞ navr₧en americk²m standardizaΦnφm ·°adem NIST.
Kvalitnφ pseudonßhodn² generßtor zadarmo
Pokud jste n∞kdy pot°ebovali rychle n∞jak²m zp∙sobem generovat nßhodnß data pro sv∙j program, urΦit∞ jste si byli v∞domi toho, ₧e jakßkoliv nevhodnß odchylka generovan²ch dat m∙₧e cφl tohoto programu zhatit. ╚asto je prost∞ pot°eba mφt jistotu, ₧e data jsou po°ßdn∞ "zamφchanß" a nemajφ ₧ßdnΘ strukturßlnφ vlastnosti (pokud vßm postaΦφ lineßrnφ kongruentnφ generßtory, podφvejte se nap°. na [1]). ╚asto je ale na dosah ruky n∞jakß knihovna s proudov²mi nebo blokov²mi Üiframi a staΦφ ji jen pou₧φt. ZdrojovΘ k≤dy Üifer jsou toti₧ voln∞ dostupnΘ na internetu, nap°φklad na [2], tak₧e zb²vß jen v∞d∞t, jak na to. Ukß₧eme si, ₧e je to vlastn∞ velmi jednoduchΘ.
ProudovΘ Üifry jako generßtory nßhodn²ch znak∙
ProudovΘ Üifry ( jako vÜechny ostatnφ Üifry) pou₧φvajφ n∞jakΘ tajnΘ nastavenφ - Üifrovacφ klφΦ, na n∞m₧ zßvisφ celß jejich v²stupnφ posloupnost. Ta se naz²vß heslo, kterΘ se obvykle xoruje bajt po bajtu na otev°en² text. Pokud by n∞kdo v tomto hesle objevil n∞jakΘ strukturßlnφ zßvislosti vΦetn∞ sebemenÜφch statistick²ch odchylek, narazil by ve skuteΦnosti na slabinu Üifry, co₧ by vedlo k jejφmu odsunu na poh°ebiÜt∞ ne·sp∞Ün²ch, rozbit²ch Üifer. U kvalitnφch Üifer p°edpoklßdßme, ₧e jejich v²stupnφ posloupnost je posloupnostφ nezßvisl²ch nßhodn²ch znak∙. StaΦφ proto zvolit n∞jak² ani ne tajn² klφΦ a z danΘ Üifry tuto posloupnost pou₧φvat v roli generßtoru nßhodn²ch znak∙. Velmi rychlß je nap°φklad Üifra RC4 (viz [3]), jejφ₧ zdrojov² k≤d m∙₧ete vid∞t na obrßzku 1. Z poslednφch pracφ vypl²vß, ₧e jejφch prvnφch 512 (pro puristy 3072) bajt∙ hesla h(i) je vhodnΘ "zahodit" a pou₧φvat a₧ dalÜφ produkci, nebo¥ urΦitΘ statistickΘ nuance zde nalezeny byly. Dßle byly nalezeny urΦitΘ strukturßlnφ zßvislosti i ve velmi dlouhΘm v²stupu, ale jednß se o velmi slo₧itΘ vztahy mezi nejni₧Üφmi bity v²stupnφch bajt∙, p°iΦem₧ desφtky megabajt∙ zde hrajφ roli zßkladnφch m∞rn²ch jednotek pro m∞°itelnΘ odchylky. B∞₧nΘ aplikaci to pochopiteln∞ nevadφ, ale v p°φpad∞, ₧e chceme "jeÜt∞ kvalitn∞jÜφ" v²stup, m∙₧eme pou₧φt n∞kterou kvalitnφ blokovou Üifru.
BlokovΘ Üifry jako generßtory nßhodn²ch znak∙
BlokovΘ Üifry lze ke generovßnφ nßhodn²ch znak∙ pou₧φt podobn²m zp∙sobem jako proudovΘ, jde jen o to, Φφm plnit jejich vstup a jak vyu₧φvat v²stup, Φili o tzv. operaΦnφ modus. Zvolφme si n∞jak² klφΦ pro vybranou Üifru, °ekn∞me AES (viz [4]), a nynφ ji budeme chtφt vyu₧φt tak, aby nßm poskytovala proud znak∙. Mßme na vybranou "star²" modus OFB (p°ehledov∞ o modech viz [7]), nebo "nov²" ΦφtaΦov² modus. Jsou skoro stejn∞ starΘ, ale o ΦφtaΦovΘm modu se dlouho nehovo°ilo, i kdy₧ ho Diffie s Hellmanem publikovali u₧ v roce 1979 (viz [5]). P°ipome≥me si tedy Output Feedback (OFB) neboli modus zp∞tnΘ vazby z v²stupu Üifry. Pokud naÜi Üifru AES se zvolen²m klφΦem K oznaΦφme jako funkci f, jde o to naplnit jejφ vstup na poΦßtku n∞jakou inicializaΦnφ hodnotou (IV, je to 128bitov² °et∞zec) a tuto hodnotu "toΦit p°es Üifru stßle dokola". Formulkou by to bylo takto: x(0) = IV, x(1) = f(x(0)), x(2) = f(x(1)),... , tedy zkrßcen∞ x(i+1) = f(x(i)), p°iΦem₧ hodnoty x(i), i= 1, 2, .... bychom pou₧ili jako nßhodnß Φφsla.
Abychom se nezamotali p°φliÜ brzo
Je z°ejmΘ, ₧e v obdr₧enΘ posloupnosti nem∙₧eme pokraΦovat donekoneΦna, proto₧e mo₧n²ch binßrnφch °et∞zc∙ dΘlky 128 bit∙ je jen 2128. Zßkonit∞ se tedy v generovanΘ posloupnosti x(i) musφme jednou dostat do bodu, kde jsme u₧ jednou byli. Proto₧e funkce f je reverzibilnφ ("zp∞tn² chod" je vlastn∞ deÜifrovßnφ), je z°ejmΘ, ₧e do ka₧dΘho bodu x(i) vede jen jeden p°edch∙dce, neboli vznikß Φist² cyklus bez "p°φvodnφch v∞tvφ", viz obr. 2. Proto₧e f je nßhodnΘ zobrazenφ, celß mno₧ina mo₧n²ch °et∞zc∙ x(i) se rozpadß do °ady takov²ch nßhodn²ch cykl∙. Z teorie pravd∞podobnosti pak vypl²vß, ₧e pr∙m∞rnß dΘlka cyklu je 2127. To je urΦit∞ pro mnoho aplikacφ, kde jsou pot°eba nßhodnß data, dostateΦnΘ. Pro Üifrovßnφ chceme mφt ale jistotu o n∞co v∞tÜφ. Ostatn∞ neÜifrujeme data jen tak pro nic za nic, tak₧e bychom p°ivφtali, kdybychom o dΘlce tohoto cyklu mohli n∞co tvrdit. M∙₧e se toti₧ stßt, ₧e se nßhodn∞ trefφme do cyklu o dΘlce 2 nebo tisφc blok∙, co₧ je velmi mßlo, a doÜlo by k tzv. dvojφmu pou₧itφ hesla, o n∞m₧ budeme hovo°it dßle. Nßsledujφcφ trik ale p°evßdφ vÜechny body z obrßzku 2 do jedinΘho (!) cyklu o dΘlce p°esn∞ 2128.
╚φtaΦ v Üifrovßnφ
B∞₧n² ΦφtaΦ je velmi jednoduchß funkce, kdy se obsah danΘho registru, v naÜem p°φpad∞ 128bitovΘho, zv²Üφ o jedniΦku, p°iΦem₧ ze stavu (hex.) 0xFF...FF se p°echßzφ do nulovΘho stavu. Trivißln∞ vidφme, ₧e tento ΦφtaΦ mß periodu 2128, a¥ zaΦneme z jakΘhokoliv poΦßteΦnφho bodu x(0) = IV. Tak₧e ΦφtaΦ projde vÜechny r∙znΘ 128bitovΘ stavy. To bychom p°esn∞ pot°ebovali od Üifry. Trik je v tom, ₧e jako v²stup nepou₧ijeme p°φmo stavy ΦφtaΦe, ale jejich ÜifrovΘ obrazy. Dostßvßme ale jedin² cyklus? Proto₧e funkce f je reverzibilnφ, nem∙₧e se stßt, ₧e by obrazy dvou r∙zn²ch stav∙ ΦφtaΦe byly stejnΘ, proto₧e pak i jejich vzory, zφskanΘ odÜifrovßnφm, by musely b²t stejnΘ. Maximßlnφ dΘlka posloupnosti tedy z∙stßvß 2128 a navφc posloupnost Üifrov²ch obraz∙ se u kvalitnφ Üifry jevφ jako dostateΦn∞ kvalitnφ zdroj nßhodn²ch znak∙. Je tu urΦitß teoretickß v²jimka, kterß nßm asi v praxi nebude p°φliÜ vadit. NaÜe novß posloupnost je p°ece jen "pravidelnß", a to sice v tom, ₧e prßv∞ nikdy b∞hem generovßnφ 2128 128bitov²ch blok∙ nedojde k tomu, ₧e by byly vygenerovßny dva stejnΘ bloky. U nßhodnΘ posloupnosti to tΘm∞° jist∞ nastane, a to podle tzv. narozeninovΘho paradoxu u₧ s 50% pravd∞podobnostφ n∞kdy v prvnφch 264 blocφch. V jinΘm pohledu vÜak u kvalitnφ Üifry nejsme schopni tuto posloupnost odliÜit od posloupnosti nßhodn²ch znak∙. Kdybychom mezi t∞mito obrazy nalezli jakΘkoliv vyu₧itelnΘ statistickΘ nebo analytickΘ vztahy, danou Üifru bychom tφm vlastn∞ "rozbili" nebo odhalili jejφ slabosti.
Dvojφ pou₧itφ hesla
Za okam₧ik si uvedeme oficißlnφ a formßlnφ definici ΦφtaΦovΘho modu. Nynφ si p°ipomeneme, oΦ vlastn∞ z kryptografickΘho hlediska jde. Pokud pou₧φvßme stejn² klφΦ, vid∞li jsme, ₧e dostßvßme jedinou funkci f, a tφm i jedin² cyklus, v kterΘm se pohybujeme. Hodnoty f(i) pou₧φvßme p°φmo jako heslo, kterΘ xorujeme na otev°en² text. Pokud bychom pou₧ili pro dv∞ zprßvy stejnou inicializaΦnφ hodnotu pro ΦφtaΦ, obdr₧eli bychom i stejn² proud hesla. OznaΦφme-li proud bajt∙ hesla, otev°en²ch a Üifrov²ch text∙ h( j), OT1( j), OT2( j) a èT1( j), èT2( j), pak bychom v tomto p°φpad∞ dostali èT1( j) = OT1( j) [197] h( j) a èT2( j) = OT2( j) [197] h( j). Z toho jednoduchou ·pravou vypl²vß, ₧e èT1( j) [197] èT2( j) = OT1( j) [197] OT2( j). Vidφme, ₧e heslo z tohoto vztahu zcela vypadlo, p°iΦem₧ hodnotu Üifrov²ch text∙ znßme. Znßme proto i hodnotu proudu bajt∙ OT1( j) [197] OT2( j). Nynφ pou₧ijeme nap°φklad metodu p°edpoklßdanΘho slova, znßzorn∞nou na obrßzku 4. Je to ve skuteΦnosti prostΘ vyzkouÜenφ hodnoty OT1( j) nebo OT2( j). Ze znalosti v²razu OT1( j) [197] OT2( j) pak dopoΦφtßme v₧dy druh² otev°en² text. Pokud vyjdou nesmysly, zkouÜφme jinΘ slovo nebo jinou pozici tak dlouho, a₧ nßm vyjde smyslupln² text. ZφskanΘ texty v OT1 i v OT2 pak rozÜi°ujeme na ob∞ strany, a₧ dostaneme oba dva otev°enΘ texty v plnΘ dΘlce. Je tedy z°ejmΘ, ₧e dvojφmu pou₧itφ hesla musφme zabrßnit i v p°φpad∞ ΦφtaΦovΘho modu. Zde vidφme velmi jasn∞, ₧e je pot°eba zajistit, aby hodnoty IV1 a IV2, kterΘ inicializujφ p°φsluÜnΘ ·seky hesla, byly dostateΦn∞ vzdßlenΘ, aby nedoÜlo k p°ekryvu na obrßzku 5.
Co na to norma
Norma velmi p°φsn∞ stanovφ, ₧e pokud se k Üifrovßnφ pou₧φvß tent²₧ klφΦ K s r∙zn²mi inicializaΦnφmi hodnotami pro r∙znΘ zprßvy, nikdy nesmφ dojφt k p°ekryvu hesla za celou dobu platnosti klφΦe K. Norma umo₧≥uje r∙znΘ postupy inkrementace ΦφtaΦe, nap°φklad m∙₧e probφhat jen v dolnφ m-bitovΘ Φßsti b-bitovΘho ΦφtaΦe (tj. mod 2m). Dßle je mo₧nΘ ΦφtaΦ (nebo jeho dolnφch m bit∙) pova₧ovat za lineßrnφ posuvn² registr se zp∞tnou vazbou a jeho stavy obnovovat posunem apod. Dßle je tu zajφmavß mo₧nost nastavit hornφch b-m bit∙ ΦφtaΦe na hodnotu, kterß je n∞jak jednoznaΦn∞ spojena se zprßvou, je₧ se Üifruje (napadß vßs mo₧nß b-m bit∙ haÜe zprßvy), zatφmco zbyl²ch m bit∙ se klasicky inkrementuje. T∞mito vÜemi mo₧n²mi opat°enφmi se docφlφ podmφnky, aby nikdy nebylo pou₧ito totΘ₧ heslo. ┌pln² popis ΦφtaΦovΘho modu naleznete ve specißlnφ publikaci NIST [6], kterß p°ejφmß definice i dalÜφch Φty° klasick²ch mod∙ (ECB, CBC, CFB a OFB) tak, jak byly definovßny v osmdesßt²ch letech v norm∞ FIPS 81.
Jedna v²hoda za vÜechny
Oproti v²Üe jmenovan²m Φty°em klasick²m mod∙m mß ΦφtaΦov² modus jednu neobyΦejnou v²hodu. M∙₧eme pomocφ n∞ho nezßvisle na Φemkoli odÜifrovat nebo zaÜifrovat jak²koliv bajt na jakΘkoliv pozici danΘho souboru nebo proudu dat, a to velmi rychle. PostaΦφ vypoΦφtat odpovφdajφcφ hodnotu ΦφtaΦe a z nφ jednφm volßnφm funkce f obdr₧et p°φsluÜnΘ heslo. U modu OFB bychom museli poΦφtat vÜechny stavy funkce f, abychom ji dostali do odpovφdajφcφ pozice. U modu CBC a CFB bychom zase pot°ebovali znßt okolφ danΘho bajtu ÜifrovΘho textu, abychom mohli sprßvn∞ nastavit zp∞tnou vazbu. To nap°φklad u databßzov²ch aplikacφ nemusφ b²t v₧dy mo₧nΘ, proto₧e nßÜ Üifrovacφ/deÜifrovacφ modul m∙₧e dostat n∞kdy jen Φßst ÜifrovanΘho zßznamu. ╚φtaΦov² modus je v tomto ohledu velmi jednoduch², jeho nev²hodou je nutnost splnit podmφnku r∙zn²ch ΦφtaΦ∙. V praxi je to nejlΘpe mo₧nΘ ud∞lat tak, ₧e inicializaΦnφ hodnotu generujeme nßhodn∞.
Jedna nev²hoda za vÜechny
Vlastnostφ jak blokov²ch, tak proudov²ch Üifer je, ₧e (alespo≥ v zßkladnφm tvaru) nezajiÜ¥ujφ integritu dat. Data sice utajφ, tj. poskytujφ d∙v∞rnost, ale proti jejich modifikaci obecn∞ nic moc nezmohou. Tato vlastnost b²vß tak Φasto opomφjena, ₧e se tΘm∞° v₧ilo, ₧e kdy₧ je n∞co zaÜifrovanΘ, je to bezpeΦnΘ. To je pochopiteln∞ zßsadnφ omyl. Pokud zm∞nφme Üifrov² text u blokovΘ Üifry (krom∞ modu OFB a ΦφtaΦovΘho modu, kterΘ prßv∞ p°etvß°φ blokovou Üifru na proudovou), dojde ke ÜpatnΘmu odÜifrovßnφ ve dvou blocφch otev°enΘho textu. Naproti tomu u Φist∞ proudovΘ Üifry dojde ke ÜpatnΘmu odÜifrovßnφ pouze ve znaku, kter² odpovφdß mφstu zm∞ny v ÜifrovΘm textu. Toho lze pochopiteln∞ zneu₧φvat k r∙zn²m ·tok∙m, pokud ·toΦnφk vφ, jak² druh informace se kde nachßzφ (nap°φklad v souborech bankovnφch transakcφ, databßzφch apod.). Vzhledem k tomu, ₧e zm∞na [197] D na ÜifrovΘm textu vede ke zm∞n∞ [197] D v otev°enΘm textu, ·toΦnφk m∙₧e snadno otev°en² text m∞nit, ani₧ by znal p°φsluÜn² Üifrov² klφΦ.
Shrnutφ
Seznßmili jsme se s nov²m operaΦnφm modem blokov²ch Üifer, ΦφtaΦov²m modem. Jeho v²hodou je snadnost pou₧itφ i jednoduchost v²poΦtu hesla pro danou pozici otev°enΘho/ÜifrovΘho textu. Lze jej vyu₧φt jak k proudovΘmu Üifrovßnφ, tak jako zdroj nßhodn²ch znak∙ pro modelovßnφ r∙zn²ch situacφ, kterΘ Φasto vznikajφ p°i programovßnφ r∙zn²ch aplikacφ.
Vlastimil Klφma, autor@chip.cz
Literatura: [1] Klφma, V.: Generßtory nßhodn²ch Φφsel I a₧ IV, Chip 3 - 6/98 [2] zdrojovΘ k≤dy Üifer: ftp://ftp.funet.fi/pub/crypt/cryptography/symmetric/ [3] Klφma, V.: RC4: èifra, kterß mφchß karty, Chip 9/99, str. 42 - 44 [4] Klφma, V.: AES - Novß Üifra nastupuje, Chip 5/02, str. 142 - 144 [5] Diffie, W., Hellman, M. E.: "Privacy and authentication: An introduction to cryptography", Proceedings of the IEEE, 67 (1979), 397 - 427 [6] Recommendation for Block Cipher Modes of Operation, Methods and Techniques, NIST Special Publication 800-38A, 2001, dostupnΘ na http://csrc.nist.gov/encryption/tkmodes.html [7] Klφma, V.: èifry s mnoha tvß°emi, Chip 7/00, str. 50 - 53 [8] Elektronick² archiv uveden²ch i dalÜφch Φlßnk∙: http://www.decros.cz/bezpecnost/_kryptografie.html
Pßr tip∙ pro programßtory
P°edstavme si, ₧e pro n∞jakou hru (program) pot°ebujeme generovat nßhodnß Φφsla 0 a₧ 9, p°iΦem₧ by bylo vhodnΘ nabφdnout u₧ivateli tutΘ₧ hru (nap°φklad totΘ₧ rozdßnφ karet) si zahrßt jeÜt∞ jednou. Za prvΘ to znamenß um∞t vygenerovat nßhodnß Φφsla, za druhΘ um∞t to p°esn∞ zopakovat. ╪eÜenφ vßs u₧ urΦit∞ napadß - prost∞ Φφslo hry bude rovno inicializaΦnφmu vektoru a klφΦ bude n∞kde v programu nastaven na konstantu, nebo obrßcen∞ - klφΦ bude Φφslo hry a IV bude konstantnφ. Variacφ urΦit∞ naleznete vφce. DalÜφ poznßmka se t²kß ·pravy hesla. Obdr₧enΘ bajty jsou v rozsahu hodnot 0 - 255, ale my pot°ebujeme hodnoty 0 - 9. StaΦilo by t°eba vyu₧φvat Φφslo h(i) mod 10, ale v tom p°φpad∞ bychom nedostali jednotlivΘ Φφslice stejn∞ pravd∞podobnΘ. ╚φslice 0 a₧ 5 by byly oproti ostatnφm "ve v²hod∞", proto₧e na n∞ vedou Φφsla 250 a₧ 255, zatφmco v ostatnφch desφtkßch jsou v²skyty rovnom∞rnΘ. Proto pokud narazφme na bajty v rozsahu 250 - 255, ignorujeme je a ₧ßdnou Φφslici z nich nevytvß°φme. Tφm ve skuteΦnosti upravujeme p∙vodnφ zdroj nßhodn²ch znak∙ z rozsahu 0 - 255 na zdroj nßhodn²ch znak∙ v rozsahu 0 - 245, a tedy po modulovßnφ na 0 - 9. Pokud by se jednalo o karetnφ aplikaci, kde pot°ebujeme Φφsla 0 - 31, staΦφ vyu₧φvat z proudu hesla v₧dy dolnφch p∞t bit∙, nebo Üet°it a proud bajt∙ "sekat" rovnou po p∞ti bitech. UrΦit∞ vßs napadne, ₧e podobn²m zp∙sobem lze z klφΦe ve form∞ textovΘ frßze nebo passwordu (pokud je pou₧ijeme jako klφΦ nebo IV) podobn²m zp∙sobem vygenerovat posloupnost znak∙ v jakΘmkoliv po₧adovanΘm rozsahu, t°eba PIN apod.
K≤d proudovΘ Üifry RC4
P°φprava klφΦovΘ tabulky
èifrovacφ klφΦ (zarovnan² na bajty) cyklicky vepisujeme do pole K(0),K(1), ..., K(255). Zvolφme identickou poΦßteΦnφ permutaci S, tj. S(i) = i, i = 0...255, a promφchßme ji prost°ednictvφm hodnot K(i) podle nßsledujφcφho pseudok≤du takto (+ je sΦφtßnφ v modulu 256):
j = 0
for i = 0 to 255 do
{
j = ( j + S(i) + K(i)) mod 256 v tabulce S vym∞≥ hodnoty S(i) a S( j)
}
Generovßnφ hesla h(i)
x = y = 0
for i = 0 to n do
{
x = x + 1 y = y + S(x) v tabulce S vym∞≥ hodnoty S(x) a S(y) h(i) = S ( S(x) + S(y) )
}
èifrovßnφ
JednotlivΘ bajty hesla h(i) je potΘ xorujφ na otev°en² text (p°i zaÜifrovßnφ) nebo Üifrov² text (p°i deÜifrovßnφ).
