PROBUDIT
WAKE ( anglicky Word A uto Key Encryption , šifrování slov na automatickém klíči ) je proudový šifrovací algoritmus na automatickém klíči vyvinutý Davidem Wheelerem v roce 1993. Původně byl navržen jako středně rychlý šifrovací systém (rychlost proudových šifer se měří v cyklech na bajt šifrovaného prostého textu ) bloky (minimální množství informací, které může algoritmus zpracovat; v tomto případě je blok 32 bitů ), s vysokou bezpečností. Podle autora jde o jednoduchý rychlý šifrovací algoritmus vhodný pro zpracování velkého množství dat, ale i krátkých zpráv, kde se mění pouze tajný klíč . Vhodné pro použití hashů na tajných klíčích používaných při ověřování . Příkladem možného praktického využití tohoto algoritmu je šifrování textového datového toku v SMS . Vzhledem k velké velikosti bloku jej nelze použít v komunikaci v reálném čase [1] [2] [3] [4] [5] .
Vlastnosti
Algoritmus pracuje v režimu CFB - předchozí slovo zašifrované sekvence slouží jako základ pro generování dalšího. Existují však úpravy algoritmu související se změnou procesu generování klíčů a umožňujícími pracovat v režimech OFB a ROFB (Reverse OFB) [6] . Šifra gama používá 32bitová slova a délka startovacího klíče je 128 bitů [1] . Algoritmus také používá náhradní S-box , který se skládá z 256 32bitových slov. V práci jsou použity čtyři proměnné , pro lepší výkon by měly být použity registry jako takové . Práce se opírá o opětovné použití tabulek v mezipaměti a přítomnost velkého stavového prostoru . To znamená, že datová mezipaměť by se měla bez problémů vejít do tabulky 256 slov [2] .
Algoritmus je dostatečně rychlý – na 32bitových procesorech architektury VLIW je odhadovaný výkon 6,38 cyklů na bajt, což převyšuje výkon algoritmu SEAL , ale je horší než RC4 (3,5 a 10,6 cyklů na bajt) [3 ] .
Šifra se hodí ke kryptoanalýze, konkrétně k útokům na vybraný otevřený text a vybraný šifrový text [7] .
Struktura algoritmu
Algoritmus je založen na kaskádovém použití směšovací funkce ( je bitové znaménko konjunkce , [7])logickýje, bitový posunXORoperacebitováto je Navíc slova v -bloku jsou složena tak, že množina vysokých bajtů těchto slov je permutací od 0 do 255 (první bajty každého slova jsou jedinečné), zatímco zbývající 3 bajty jsou vyplněny náhodně [ 8] . Směšovací funkce je reverzibilní z takových úvah, že znalost jednoho ze slov na vstupu a slova na výstupu bude stačit k obnovení druhé neznámé na vstupu [9] .
WAKE se skládá ze čtyř stupňů funkce se zpětnou vazbou pro každý a ještě jeden pro celou skupinu stupňů. Toto množství je zvoleno jako minimální možné pro úplnou difúzi .dat ve slově (to znamená, že když se změní alespoň jeden bit klíče, výsledek šifrovacího algoritmu se změní úplně), protože -blok provádí nelineární transformaci , a použití bitové "AND" a výhradní "OR" také zavádí mírnou nelinearitu [2] .
Popis algoritmu
Proces šifrování probíhá ve třech fázích [1] :
- proces generování S-boxu;
- Proces generování autoklíčů;
- Přímé šifrování a dešifrování.
Proces generování S-boxu
Nejprve jsou první hodnoty -bloku (náhradní tabulka) inicializovány tajným klíčem. Příklad algoritmu pro vyplnění této tabulky je uveden [1] :
- Inicializujte pomocnou tabulku skládající se z 8 slov s permutací prvních tří bitů:
- Zkopírujte klíč v prvních 4 slovech tak, aby: , kde je výsledek rozdělení klíče na čtyři stejné části.
- Vytvořte zbývající slova v cyklu :
- Proveďte shrnutí: . Takže i prvních pár slov bude záviset na všech bitech .
- Definujte pomocné proměnné:
- Proveďte permutaci v prvním bajtu slov v tabulce:
- Inicializujte následující proměnné:
- Zamíchejte slova v :
![{\displaystyle s[0]:726a8f3b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f427acd66f84f609984917ca4c2472b581ad767)
![{\displaystyle s[1]:e69a3b5c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f17ae1cebd1f17d7289d9554169c769ecb5c104)
![{\displaystyle s[2]:d3c71fe5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f50a424fce4b229755f0f202e396ec36373eac89)
![{\displaystyle s[3]:ab3c73d2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efbeaab3071f2eff1ea0afc278a983431c00f038)
![{\displaystyle s[4]:4d3a8eb3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ccf537b24fadcf890a00e6d2625ad664ebd4408e)
![{\displaystyle s[5]:0396d6e8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cefe28390cfce30b1794e18dbc4c0555eb9671ac)
![{\displaystyle s[6]:3d4c2f7a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08f6305dfe7fe6668cafd9806ec0bd6608062aa4)
![{\displaystyle s[7]:9ee27cf3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/244574dce33fc7576ac5446e81ec75744c573f2f)
![{\displaystyle S[0]...S[3]:}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7deac674d7b3f5866a52615c1a14e6c413812b84)
![{\displaystyle S[0]=K[0];\ S[1]=K[1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21dd61f2bbd228b13ad7baef06785388a73dbc2d)
![{\displaystyle S[2]=K[2];\ S[3]=K[3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11a163ee24127a2cc7130b4dcf96972619bd87bc)
![{\displaystyle K[0],\ K[1],\ K[2],\ K[3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be980c89fc45fbb2afc842de5899264568377fb0)
![{\displaystyle x=S[n-1]+S[n-4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7532a9062b26f69395a9c7a12dc867368e814edf)
![{\displaystyle S[n]=x>>3\oplus s[x\wedge 7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a32fded15ebdf67f98d64ecc2273ec01900969aa)
![{\displaystyle S[n]\ +\!=S[n+89]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40fb002b874a6a4e3e677462193dbdfce17a1883)
![{\displaystyle X=S[33]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/505b29ff8b6add09608b368b3d8e8d1f08e0fdab)
![{\displaystyle Z=S[59]\lor 0{\text{x}}01000001}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02ccedc07c58bea0dab56596c40dd4cdf6b744fa)
![{\displaystyle S[n]=S[n]\land 0{\text{x}}00FFFFFF\oplus X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19f8d9aa93846f5796ddf4cb3050aa6000f3916e)
![{\displaystyle S[256]=S[0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d88d26153316f59310f0f2e4f06cabc9002b17a4)
![{\displaystyle Temp=(S[n\oplus X]\oplus X)\land 255}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d0f6752c83a867631e4ee83f8d6bcff2983b89e)
![{\displaystyle S[n]=S[Temp]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/911b3b4b4f63a284bcf4180c74d23a0a67c52c7f)
![{\displaystyle S[X]=S[n+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93b3f4a8e36aa9e4c4fff8eaf7f3e6731d32b7ba)
Konstrukční metodu lze snadno upravit a výše uvedený algoritmus je pouze příkladem. Hlavní věc je, že výsledek algoritmu má všechny vlastnosti prezentované z důvodů kryptografické síly -bloku . Můžete tedy například vyplnit tabulku slov náhodnými čísly , ale v tomto případě uniknou informace o opakovaných a nulových položkách tabulky , které nepřesahují 1,5 bitu pro každou položku. Tvůrce algoritmu však tvrdí, že proces permutace na vysokých bajtech slov výrazně pomáhá snížit únik. A permutace na všech čtyřech bytech dále snižuje pravděpodobnost čtení tabulky. Výše uvedený vyplňovací algoritmus je tedy kompromisem mezi bezpečností a rychlostí, protože jsou v něm permutovány vysoké bajty blokových slov [10] .
Proces generování autoklíče
Generování se provádí podle blokového schématu algoritmu [7] :
- Nejprve musíte inicializovat hodnoty registru pomocí klíče (případně jiného): jsou zodpovědní za stejné rozdělení klíče na stejné části.
- Slova v posloupnosti kláves se počítají takto:
- Další slovo sekvence kláves je určeno hodnotou extrémního případu:
![{\displaystyle R3[0]=K[0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84f375f5f38ea20ab7543d3a71444588fd4cbd9e)
![{\displaystyle R4[0]=K[1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/039bfd70edffc8af3b8d523ad636f403dc0a754d)
![{\displaystyle R5[0]=K[2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8b6c15f10ff242fcbcf159fbba39145d14f12ad)
![{\displaystyle R6[0]=K[3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1fd47a7ec040ea789ad22b65bec35e320dc378a)
![{\displaystyle R3[i+1]=M(R3_{i},R6_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55297277753a5abd131735b178532c9a497d4135)
![{\displaystyle R4[i+1]=M(R4_{i},R3_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef54376f281a83a35ae2722e978ca9e91a2d8165)
![{\displaystyle R5[i+1]=M(R5_{i},R4_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c20b7f5c4adfbd7e05124ceb385ba4ab363a527)
![{\displaystyle R6[i+1]=M(R6_{i},R5_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57f3cdd541e464b76bcace50cbbc83bba9ad2df7)
![{\displaystyle K_{i+1}=R6[i+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05025d976af123c4c0d0a4159857fc2058585920)
Klíč by měl být změněn v případě velkého prostého textu (doba změny klíče je přibližně 10 000 slov – v tomto případě se algoritmus zpomalí asi o 2–3 %) [11] .
Šifrování a dešifrování
Obě metody jsou gamifikací otevřeného textu (nebo šifrovaného textu) pomocí klíčové sekvence. Šifrování a dešifrování se provádí podle vzorce [12] :
, kde je slovo v otevřeném nebo šifrovaném textu v závislosti na tom, zda se provádí šifrování nebo dešifrování.
Použití
Existuje poměrně mnoho způsobů, jak tuto šifru použít, ale autor formuluje pouze tři hlavní metody [13] :
- Doplnění zašifrovaných dat dvěma slovy na obou koncích a následné vyplnění všech bitů těchto slov stejnými náhodnými hodnotami. Dekodér tak bude schopen rozpoznat, kdy je pro úspěšné dešifrování zprávy nutné použít další klíč v pořadí klíčů;
- Změna startovacího klíče pro každý nový datový blok;
- Šifrování posledních čtyř slov otevřeného textu, další gamifikace se startovacím klíčem celé sekvence a provedení stejného v opačném pořadí s dalším startovacím klíčem. Tato metoda může také zahrnovat použití některé standardní hashovací funkce soukromého klíče , která má stejný startovací klíč a tabulku náhrad, aby se vygenerovala hash 128 bitů. Tento hash je smíchán s prvními čtyřmi slovy otevřeného textu, ve skutečnosti k dalšímu šifrování dochází stejným způsobem jako dříve. Každá nová zpráva tedy tvoří nový výsledek na výstupu algoritmu. Také v případě použití hashovací funkce se rychlost provádění zvýší asi 5krát ve srovnání s konvenční metodou. Metoda je dobrá, protože se dobře hodí pro krátké zprávy, kde opakovaný výpočet náhradní tabulky výrazně snižuje efektivitu aplikace. Použití stejné náhradní tabulky je tedy rozumným krokem.
Příklad práce
Příklad fungování tohoto šifrovacího algoritmu je uveden následovně [1] :
- Spustit inicializaci klíče : "legitosinarhusni". V šestnáctkové soustavě to bude vypadat takto:
- Je nutné rozdělit klíč na čtyři stejné části a inicializovat počáteční hodnoty registrů:
- Výpočet dalšího slova sekvence kláves ( -blok již byl vygenerován na základě dostupného startovacího klíče): - nový klíč.
- Dále nechť je „ROBBI RAHIM“ brán jako prostý text. V HEX reprezentaci by to bylo . Tuto číselnou sekvenci je nutné gamifikovat pomocí klíče:
![{\displaystyle R3[0]=6C656769}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89697f4737990490540d1d7a3700ed45db08585c)
![{\displaystyle R4[0]=746F7369}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb7b55f4bf0f0efadbd6266262afe23e802a61ea)
![{\displaystyle R5[0]=6E617268}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1296b1a7f93b89b3bc96c73902c70facb26cc3e)
![{\displaystyle R6[0]=75736E69}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58f91913589833ce1b5aa57ed2066dfa5a8c0e07)
![{\displaystyle M(R3[0],R6[0])=M(6C656769,75736E69)=(6C656769+75736E69)>>8\oplus S_{(6C656769+75736E69)\land 255_E{0>))8D5D >8\oplus S_{210}=00E1D8D5\oplus 1C5A4A56=1CBB9283}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8057630680b54dae7d7768dacecae7a73a415a94)
![{\displaystyle R3[1]=1CBB9283}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2487d32e5368c6eef579c43ad501d0d179aa2e46)
![{\displaystyle M(R4[0],R3[1])=M(746F7369,1CBB9283)=(746F7369+1CBB9283)>>8\oplus S_{(746F7369+1CBB9283)\land 255_{1205)= >8\oplus S_{236}=00912B05\oplus 26853B5R4=2614105E}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edbc5e823e26191ace431e0fd97101c1e1f17342)
![{\displaystyle R4[1]=2614105E}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b544f55803d0dfe781eec34bea66fb6e2d4be8b)
![{\displaystyle M(R5[0],R4[1])=M(6E617268,2614105E)=(6E617268+2614105E)>>8\oplus S_{(6E617268+2614105E)\land 255_{06)457={16 >8\oplus S_{198}=00947582\oplus 244C066R5=24D873EE}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fde3806a733304c795add0714ff2c6b3fc847944)
![{\displaystyle R5[1]=24D873EE}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebd11acb5613a6567e4cd0cc09d0843411b6372c)
![{\displaystyle M(R6[0],R5[1])=M(75736E69,24D873EE)=(75736E69+24D873EE)>>8\oplus S_{(75736E69+24D873EE)\land 255_97BE25)= >8\oplus S_{87}=009A4BE2\oplus C2C748D2=C25D0330}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27b775a968a296b1464b896d8cb1d4c16cf09d0d)
![{\displaystyle R6[1]=C25D0330}](https://wikimedia.org/api/rest_v1/media/math/render/svg/538a224e3687f756412edb0da53d4390745305e8)
| Ne. | Znak prostého textu | ASCII kód | Gamma proces | Výsledek ASCII | Výstupní symbol |
|---|---|---|---|---|---|
| jeden | R | 52 | 52 XOR C2 | 90 | • |
| 2 | O | 4F | 4F XOR 5D | 12 | _( např. symbol ) |
| 3 | B | 42 | 42 XOR 03 | 41 | A |
| čtyři | B | 42 | 42 XOR 30 | 72 | r |
| 5 | I | 49 | 49 XOR C2 | 8B | ‹ |
| 6 | SPACE | dvacet | 20 XOR 5D | 7D | } |
| 7 | R | 52 | 52 XOR 03 | 51 | Q |
| osm | A | 41 | 41 XOR 30 | 71 | q |
| 9 | H | 48 | 48 XOR C2 | 8A | Š |
| deset | I | 49 | 49 XOR 5D | čtrnáct | _(např. postava) |
| jedenáct | M | 4D | 4D XOR 03 | 4E | N |
Zašifrovaná sekvence slov je tedy „•_Ar‹}QqŠ_N“.
Kryptoanalýza
Algoritmus šifrování proudu je přístupný k dešifrování prostřednictvím útoků na vybraný prostý text a vybraný šifrovaný text [7] . V případě první varianty útoku je učiněn pokus o obnovení náhradní tabulky protříděním možností otevřeného textu na vstupu, druhou je výběr šifrového textu pro přesné určení stejných neznámých hodnot - blok. Je známo, že výpočetní náročnost útoku matched-plaintext je přibližně nebo závislá na zvolené modifikaci útoku (v prvním případě se používá více variant otevřeného textu). Výpočetní složitost útoku hrubou silou je přibližně , to znamená, že relativní efektivita útoku s hozeným textem je zřejmá [14] . Další výhodou útoku navrženého v tomto článku [15] je, že nezávisí na překlíčování [16] . Algoritmy, kterými se provádí kryptoanalýza , se však stanou neproveditelnými, pokud se zvětší délka slova ( bity, kde ). Lze je tedy v budoucnu výrazně zlepšit [17] [15] .
Také nepřetržitá změna dat na kterémkoli místě šifrovacího algoritmu během provozu může ohrozit náhradní tabulku. V případě, že je -blok již znám, je k přesnému určení hodnot registru potřeba pouze 5 párů slov s nešifrovaným textem [11] .
Poznámky
- ↑ 1 2 3 4 5 Legito, Robbi Rahim .
- ↑ 1 2 3 Wheeler, 1993-12-09 , s. 127.
- ↑ 1 2 Craig, 1997-01-20 , str. 276.
- ↑ Wheeler, 1993-12-09 , s. 132.
- ↑ Hui-Mei Chao , str. 2.
- ↑ Craig, 1997-01-20 , str. 279.
- ↑ 1 2 3 4 Schneier, 1996 , str. 336.
- ↑ Shamkin, 2006 , str. 64.
- ↑ Craig, 1997-01-20 , str. 278.
- ↑ Wheeler, 1993-12-09 , s. 129.
- ↑ 12 Wheeler, 1993-12-09 , s. 130.
- ↑ Pudovkina, 2001-01-01 , str. 2.
- ↑ Wheeler, 1993-12-09 , s. 131.
- ↑ Pudovkina, 2001-01-01 , str. 7.
- ↑ 1 2 Pudovkina, 2001-01-01 .
- ↑ Pudovkina, 2001-01-01 , str. 2.7.
- ↑ Pudovkina, 2001-01-01 , str. 1.7.
Literatura
Knihy
- Schneier, B. Applied Cryptography: Protocols, Algorthms, and Source Code in C. - 2nd edition. - John Wiley & Sons, Inc., 1996. - 784 s. — ISBN 0471128457 .
- A.V. Jakovlev, A.A. Bezbogov, V.V. Rodin, V.N. Shamkin. Kryptografická ochrana informací: výukový program. - Tambov: Nakladatelství Tambov. Stát tech. un-ta, 2006. - 140 s. — ISBN 5-8265-0503-6 .
Články
- Wheeler, D. Algoritmus hromadného šifrování dat // Rychlé softwarové šifrování. — Springer, Berlín, Heidelberg, 12. 1993. - str. 127-134 . — ISBN 3540581081 . - doi : 10.1007/3-540-58108-1_16 .
- Craig SK Clapp. Optimalizace rychlé proudové šifry pro VLIW, SIMD a superskalární procesory // Rychlé softwarové šifrování. — Springer, Berlín, Heidelberg, 1997-01-20. - str. 273-287 . - doi : 10.1007/bfb0052353 .
- Legito, Robbie Rahim . Šifrování SMS pomocí automatického šifrování klíče Word | IJRTER (anglicky) . www.ijrter.com (2017). Staženo: 8. února 2017.
- Marina Pudovkina. Analýza vybraných útoků v otevřeném textu na WAKE Stream Cipher . - 2001-01-01. — č. 065 .
- Efektivní toková šifra využívající různé velikosti toku klíčů . výzkumná brána. Datum přístupu: 18. února 2017.