EFTON

Tento článok bol uverejnený na serveri mcu.cz.

SkipJack pre '51 (a AVR)

V tomto článku predstavíme kódovací algoritmus SkipJack, ktorého implementácia predstavuje jednu z najrýchlejších medzi štandardne používanými blokovými šiframi. Rýchle šifry nachádzajú uplatnenie napríklad v čoraz rozšírenejších inteligentných čipových kartách alebo pri kódovaní údajov prenášaných cez verejné médiá ako je napríklad internet.

Šifrovací algoritmus SkipJack vznikol v osemdesiatych rokoch ako štandardný algoritmus pre potreby amerického Úradu pre národnú bezpečnosť NSA [1] a ako taký bol roky utajovaný. Pôvod algoritmu naznačuje uznávaný odborník na otázky šifrovania a bezpečnosti dát Bruce Schneier, keď v jednej poznámke uvádza, že SkipJack je typickou ukážkou armádnej kryptografie [3]. Odtajnenie algoritmu malo tiež kuriózny priebeh. Oficiálnym dôvodom bola snaha vyhovieť požiadavke verejnosti podrobiť algoritmus ako kľúčovú zložku široko nasadzovaného vládneho bezpečnostného systému skrutíniu širšej odbornej verejnosti; avšak Schneier naznačuje, že NSA týmto krokom zakryl organizačný prehmat, keď šifrovací hardware distribuoval vo forme PCMCIA karty, avšak väčšina jej potenciálnych užívateľov nemala k dispozícii príslušný hardware na jej využitie... Každopádne, NSA zverejnila SkipJack v júni 1998, a už na nasledujúci deň vznikla prvá kryptoanalýza naznačujúca potenciálnu slabosť algoritmu [2].

SkipJack šifruje 64-bitový blok dát pomocou 80-bitového kľúča v 32 kolách. Jedná sa o symetrickú šifru, takže existuje aj inverzný algoritmus ktorý dokáže zašifrované dáta za použitia toho istého kľúča odšifrovať. Každé kolo obsahuje rotáciu dát, pričom na časti dát je prevedená zložitejšia operácia zahrňujúca kľúč ako aj nelineárnu operáciu pomocou tabuľky. Kľúč pritom zostáva nezmenený, len sa z neho používa v každom kole iná časť. Zaujímavosťou je, že k dátam je ako dodatočný nelineárny prvok pridávané aj poradové číslo kola.

Podobne ako u TEA aj SkipJacku je vyčítaná jeho jednoduchosť a pomerne krátky 80-bitový kľúč. Na druhej strane napriek pozornosti kryptoanalytikov sa podarilo dosiahnuť len okrajové oslabenie algoritmu. Tak ako u TEA aj tu možno konštatovať že pre väčšinu aplikácií, v ktorých sú 8-bitové mikrokontroléry typicky nasadzované, je bezpečnosť algoritmu SkipJack zrejme dostačujúca.

Algoritmus bol navrhnutý ako veľmi jednoduchý s ohľadom na jeho možnú pomerne jednoduchú implementáciu v hardware. Dokonca aj na 8-bitových procesoroch je možné použiť niektoré optimalizačné kroky - namiesto rotácie o 8 bitov je v každom kole jednoducho premenovaná sada registrov v ktorej sú dáta uložené, jednotlivé kolá je možné namiesto vykonávania v cykloch explicitne rozpísať, čím sa namiesto vypočítavania ukazovateľov na dáta a na kľúč priamo použijú príslušné dáta a časti kľúča. Takto je možné vykonávanie algoritmu výrazne urýchliť na úkor väčšej dĺžky programu.

SkipJack bol implementovaný na jadre '51 v priamej (skipjack.a51) aj urýchlenej (skipfast.a51) podobe, pričom urýchlená verzia bola upravená aj tak, že sú dáta uložené v registroch (skipregs.a51), čo síce vykonávanie algoritmu neurýchli, avšak zmenší nároky na pamäť programu. Ku všetkým trom verziám bol samozrejme spracovaný aj inverzný (dešifrovací) algoritmus (skipj_i.a51, skipf_i.a51, skipr_i.a51). Uvedené príklady obsahujú aj krátky testovací program a štandardnú sadu testovacích vektorov.

V nasledujúcej tabuľke sú zhrnuté vlastnosti všetkých variánt programu. Pre porovnanie je uvedená aj implementácia algoritmu TEA na jadre '51, ako aj implementácie oboch algoritmov v asembleri pre jadro AVR. Pre orientačné porovnanie rýchlosti je ako príklad zvolený systém '51 s 2x urýchleným jadrom (6-clock - skupina RD2) a hodinovým taktom 20MHz (treba si však uvedomiť že špičkoví predstavitelia rodiny '51 disponujú asi 10-násobne vyšším výkonom); pre jadro AVR je uvažovaný hodinový takt 16MHz.

             tea.a51      xtea.a51      skipjack.a51  skipfast.a51   skipregs.a51
size(bytes)  206          218           364           1428           1140
cycles       9350         6952          1682          788            788
kB/sec       2.9          3.8           15.9          33.8           33.8 

             tea.asm(AVR) xtea.asm(AVR)               skipfast.asm(AVR) 
size(bytes)  2*94=188     2*103=206                   2*942=1884         
cycles       6861         6347                        901            
kB/sec       18.7         20.2                        142.1          

             tea_i.a51    xtea_i.a51    skipj_i.a51   skipf_i.a51    skipr_i.a51
size(bytes)  213          224           364           1444           1156
cycles       9436         7051          1683          804            804
kB/sec       2.8          3.8           15.9          33.2           33.2 

Zdrojové súbory sú k dispozícii na stránkach autora.

[1] http://csrc.nist.gov/CryptoToolkit/skipjack/skipjack-kea.htm
[2] http://www.cs.technion.ac.il/~biham/Reports/SkipJack/
[3] http://www.schneier.com/crypto-gram-9807.html#skip