EFTON

Implementácia SEA na x51 a AVR

SEA - Scalable Encryption Standard - je nová bloková šifra od skupiny belgických kryptológov, určený predovšetkým pre mikrokontroléry (mcu).

Šifrovací algoritmus je navrhnutý tak, že využíva len operácie, ktoré sú obvykle základnými inštrukciami mcu - sčítanie, AND, OR, XOR, rotácie a presuny. Vďaka tomuto je implementácia šifry priamočiara a pomerne malá, s pomerne dobrým výsledným výkonom.

Podobne ako prevažná väčšina moderných blokových šifier, aj SEA je Feistelovho typu, avšak s pomerne jednoduchou štruktúrou a neobvykle vysokým počtom kôl. Keďže šifra bola zverejnená len pred niekoľkými mesiacmi, zatiaľ zrejme neexistujú nezávislé kryptoanalýzy, avšak autori pomerne rozsiahlo skúmali jej odolnosť voči niekoľkým možným druhom útoku.

Jednou z neobvyklých vlastnosí šifry je, že berie do úvahy prirodzenú dĺžku dátového slova v mcu, takže sú definované napr. 8-bitová aj 32-bitová verzia šifry. Týmto sa ďalej zjednodušuje jej implementácia. Hoci jednotlivé verzie s rozličnými dĺžkami slova sú navzájom nekompatibilné, nepredstavuje to zásadný nedostatok, keďže obvykle je pri komunikácii protikusom mikrokontroléra výkonný systém (napr. PC), ktorý má dostatok zdrojov a kde nie je optimálna implementácia nevyhnutná.

Ďalšou významnou zvláštnosťou šifry je - ako už jej meno naznačuje - možnosť použiť rôzne dĺžky kódovaných dát a kľúča (scalability - "škálovateľnosť"). Nejedná sa síce o mimoriadnu vlastnosť - mať niekoľko variant šifry s rozličnou dĺžkou dát a kľúča boli napríklad požiadavkou v súťaži o AES - avšak SEA je navrhnutý tak, že umožňuje takmer ľubovoľne veľkú dĺžku dátového bloku a kľúča, jedinou podmienkou je, aby boli rovnaké a aby boli násobkom 6 dátových slov. Samozrejme, v praxi budú použité len niektoré kombinácie dĺžky slova a dĺžky dátového bloku a kľúča, napríklad autori porovnávajú 96-bitovú SEA na 8-bitových mcu a 192-bitovú SEA na 32-bitových mcu. Avšak požiadavky na dĺžku použitého kľúča rastú z roka na rok s nárastom výpočtovej mohutnosti techniky použiteľnej pre útok hrubou silou. Tu SEA ponúka ľahkú a rýchlu možnosť rozšírenia.

Drobnou, avšak užitočnou zvláštnosťou SEA je, že po celom šifrovacom cykle sa kľúč vráti do svojeho pôvodného stavu, takže nie je potrebné použiť zvláštne pamäťové miesto na uchovanie kľúča a na výpočet podkľúčov počas šifrovania.

Počas implementovania šifry na dvoch populárnych 8-bitových platformách - x51 a AVR - sa vyskytlo niekoľko problémov s pochopením silne matematicky orientovaného popisu šifry. Napríklad, pojem "rekurzívny" v popise substitúcie znamená, že v jednotlivých podkrokoch substitúcie sa používa výsledok z predchádzajúceho podkroku. Mätúce je aj označenie zaokrúhlenia "neúplnými" hranatými zátvorkami, čo pri horšie vytlačenom či zobrazenom texte zaniká, pričom zaokrúhlenie vôbec nie je potrebné použiť (počet kôl je vždy nepárne číslo).

Predstavované implementácie sú napísané v asembleri jednotlivých mikrokontrolérov a sú optimalizované na rýchlosť, čo má za následok niekoľkokrát dlhší binárny kód než by bol vznikol pri implementácii sledujúcej presne popis autorov. Dôvodom takéhoto postupu je, že aj takto je dĺžka výsledného kódu značne menšia ako 1 kbyte, pričom v moderných mcu je kódová pamäť (FLASH) veľmi lacná a je k dispozícii obvykle niekoľko kilobyte. Taktiež, referenčná implementácia je len jednosmerná (len kódovanie alebo len dekódovanie), hoci je uvedená aj obojsmerná verzia, ktorá je o niečo dlhšia aj pomalšia.

SEA pre x51

Ako bolo uvedené, táto implementácia sa mierne líši od vzoru autorov. Prvou odlišnosťou je oddelenie nepárnych a párnych kôl, aby sa odstránila zámena ľavej a pravej strany dátového bloku aj kľúča. Táto zámena je nahradená premenovaním ľavej strany za pravú a naopak v párnom kole. Druhá odlišnosť je, že prvá polovica kôl je oddelená od druhej polovice, čím sa odstránilo vetvenie na základe počtu kôl; taktiež bolo nahradená zámena ľavej a pravej straný dát uprostred kôl a na konci premenovaním. Výsledný kód je síce takmer 4-násobne dlhší, avšak vďaka veľkému počtu kôl sa aj pomerne malé skrátenie vykonávania kola prejaví významne na celkovom výkone.

"Škálovateľnosť" tejto implementácie je umožnená dokonalým rozdelením všetkých operácií (čo sa týka dát aj kľúča) na prácu po trojiciach bytov. Predstavená implementácia používa 96-bitový dátový blok aj kľúč, takže sa v každom kole pracuje s dvomi trojicami byteov dát aj kľúča. Pre väčší blok stačí nakopírovať viackrát prácu s trojicami a príslušne premenovať použité premenné (a tiež zmeniť celkový počet kôl, ktorý je zadaný ako polovičná hodnota pre určenie konca cyklu v prvej polovici). Podobne sa dá implementovať aj najmenšia možná verzia SEA (48-bitová). Kľúč aj dáta sú uložené v priamo adresovanej pamäti, takže v praxi toto je limitujúcim faktorom, obmedzujúcim dĺžku dátového bliku a kľúča na asi 288 bitov.

Všetky tri varianty (len kódovanie (Sea), len dekódovanie (iSea) a obojsmerná verzia (EDSea)) sú umiestnené v jednom súbore - sea1.a51 - kde je uvedená aj dĺžka kódu a počet cyklov.

SEA pre AVR

Implementácia pre AVR je "ručným prekladom" x51-tkovej implementácie do assembleru AVR. Sú tu však dva rozdiely. Po prvé, AVR nemajú byteové rotácie (bez carry bitu), takže tieto musia byť simulované štvoricou inštrukcií. Omnoho závažnejší rozdiel však je, že AVR nemajú ekvivalent priamo adresovanej pamäte v x51, takže kľúč aj dáta musia byť umiestnené priamo v sade registrov. Keďže ich čiastočné či úplné umiestnenie v (nepriamo pristupovanej) RAM by znamenalo ich permanentné presúvanie do a z registrov a tým zásadné zníženie výkonu, akékoľvek zväčšenie dĺžky dátového bloku a kľúča je v tejto implementácii vylúčené.

Aj implementácia pre AVR je v troch verziách (len kódovanie (Sea), len dekódovanie (iSea) a obojsmerná verzia (EDSea)) a rovnako sú umiestnené v jednom súbore - sea1.asm spolu s dĺžkou kódu a počtom cyklov. Nachádza sa v ňom aj štvrtá variácia - Sea2 - ktorá pekne demonštruje možnosť skrátiť dĺžku kódu za cenu zníženia rýchlosti.