EFTON

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

TEA pre '51 (a AVR)

Nový spôsob napájania mcu - čajom? Ale kdeže. TEA je skratka pre Tiny Encryption Algorithm, čiže drobný kódovací algoritmus, a tento článok popisuje jeho implementáciu na mcu typu '51.

TEA [1] vznikol pri príležitosti prednášky autorov R.Needhama a D.Wheelera z renomovaného pracoviska Univerzity v Cambridge na medzinárodnej konferencii [2]. Cieľom bolo ukázať, že je možné vytvoriť algoritmus typu bloková šifra, optimalizovný na implementáciu na moderných procesoroch a mcu. Konvenčné šifry, sú obvykle tvorené s ohľadom na implementáciu v hardware a častokrát používajú metódy, ktorých implementácia v mcu využíva množstvo zdrojov - programovú a dátovú pamäť, inštrukčné cykly - napr. tabuľkové substitúcie, bitové permutácie. Naproti tomu, TEA využíva len také operácie, ktoré sa implementujú priamočarymi inštrukciami - sčítanie, posuvy, xor. Aj keď je kľúč 128-bitový a veľkosť šifrovaného bloku je 64 bitov, v jednom kroku je spracovaná len polovica bloku dát, čo znamená, že na 32-bitových procesoroch je TEA doslova vecou zopár inštrukcií.

Extrémna jednoduchosť je na druhej strane aj dôvodom k pochybnostiam o bezpečnosti šifry, na čo poukazujú sami autori. Určité oslabenie objavil D. Wagner z Univerzity Berkeley [3], aj keď pre praktické účely sa napr. oslabenie kľúča zo 128 na 126 bitov javí ako bezvýznamné. Autori reagovali vylepšeným algoritmom [4], nazývaným XTEA alebo TEAN, ktorý používa tie isté inštrukcie avšak v inom poradí a tiež kľúč je použitý iným spôsobom. Algoritmu v tejto podobe zatiaľ žiadna výraznejšia slabosť zverejnená nebola. Kryptoanalytici sa zaoberajú zväčša nejako upraveným algoritmom, kde poukazujú na možné chyby; avšak tieto sú mnohokrát práve následkom urobených zmien a nie sú relevantné pre TEA či XTEA. Vznikol však zaujímavý bludný kruh - algoritmu sa vyčíta malé množstvo nezávislých analýz, a preto nebýva implementovaný v dôležitých bezpečnostných balíkoch, čo však má za následok nezáujem zo strany kryptoanalytikov...

Aj keď sa možno nejedná o najprepracovanejšiu šifru, pri implementácii do 8-bitového mcu si však treba predovšetkým uvedomiť, že sila akéhokoľvek zabezpečenia údajov je daná najslabším článkom všetkých zainteresovaných prvkov systému. V súčasnosti sa takýmto slabým článkom javí práve zabezpečenie programovej pamäte mcu, ktorú úspešne spochybňuje množstvo ponúk na "odomknutie" či vyčítanie "zamknutého" mcu na internete.

Predkladaná implementácia TEA a XTEA pre mcu rady '51 si kladie za cieľ vytvoriť kódovaciu rutinu s čo najmenším množstvom použitej programovej pamäte, aj za cenu nie dokonale optimálneho času vykonávania, aby bolo možné rutinu použiť aj v najlacnejších mcu s obmedzeným množstvom programovej pamäte. Ako jazyk je použitý pochopiteľne asembler. Výsledok prekonal moje očakávania, keďže všetky štyri rutiny (priama a inverzná TEA aj XTEA) zaberajú menej ako 256 byte programovej pamäte vrátane 16-byte (128-bitov) kľúča. Pre porovnanie, implementácia klasického algoritmu DES s predpočítaným kľúčom (i keď optimalizovaný na rýchlosť) zaberá asi 700 byte; u AES (Rijndael) je to okolo 1000 byte. Na druhej strane, vykonávanie je (aj vďaka pre maximálnu bezpečnosť odporúčaným 32 cyklom) pomalšie, okolo 9000 inštrukčných cyklov (u DES s predpočítanými subkľúčami je to okolo 6000 cyklov; u AES okolo 3000 cyklov, pričom u AES je dvojnásobná veľkosť spracovaného bloku). U štandardnej 8051 pri hodinovej frekvencii 12MHz to znamená zakódovanie (odkódovanie) asi 900 byte za sekundu.

routine tea.a51 xtea.a51 tea_i.a51 xtea_i.a51
instruction cycles 9350 6952 9436 7051
ROM bytes (excl. key) 190 202 197 208

Uvedené procedúry využívajú kľúč umiestnený v programovej pamäti, avšak je jednoduché ich upraviť tak, aby mohol byť kľúč umiestnený v internej či externej dátovej pamäti. V prípade nedostatku registrového priestoru je tiež možné jednoducho použiť miesto registrov R2 (používa sa ako počítadlo) a R4-R7 (používajú sa ako 32-bitový register) internú dátovú pamäť, čo však má za následok predĺženie procedúry.

Algoritmus je zrejme ľahko implementovateľný aj na iné 8-bitové a vyššie procesory a mcu. Pre mcu rady PIC je publikovaná implementácia TEA pre PIC16 (295 word ROM, 6kbytes/sec@20MHz) a PIC17 (192 word ROM, 12kbytes+/sec@33MHz)[5]. Na stránkach Microchipu je k dispozícii appnote AN953 [6], ktorý obsahuje implementáciu viacerých blokových šifier, okrem iného aj XTEA a jej inverziu, pre radu PIC18, ale neuvádzajú údaje o pamäťových nárokoch a výkone. Pre mcu rady AVR som verejne dostupnú implementáciu TEA či XTEA nenašiel (s výnimkou balíka Sosse, v ktorom sa nachádza takmer nemodifikovaná vzorová verzia v C, vedúca k neefektívnej implementácii - relevantná časť má asi 284 byte a trvá až 12781 cyklov).

Zdrojové súbory (8051): tea.a51, tea_i.a51, xtea.a51 a xtea_i.a51.

Zdrojové súbory (AVR): tea.asm, xtea.asm a xtea_i.asm.


[1] http://www.ftp.cl.cam.ac.uk/ftp/users/djw3/tea.ps; http://www.cix.co.uk/~klockstone/tea.pdf

[2] http://www-users.cs.york.ac.uk/~matthew/TEA/; http://groups-beta.google.com/group/sci.crypt/msg/cd0bd6e564af5836

[3] J. Kelsey, B. Schneier, and D. Wagner, "Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA", ICICS '97 Proceedings, Springer-Verlag, November 1997. (Available from http://www.counterpane.com/related-key_cryptanalysis.html)

[4] http://www.ftp.cl.cam.ac.uk/ftp/users/djw3/xtea.ps; http://www.cix.co.uk/~klockstone/xtea.pdf

[5] http://www.geocities.com/SiliconValley/2499/code.html

[6] http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=1824&appnote=en022056