slika 1. generiranje podključeva
| Operacijski Sustavi 2 | OS2-seminar |
| Akelarre, Block Cipher algoritam |
| Autor: | Ivan Sobota | Link za Akelarre source i exe |
| MB: | 0036391822 | "akelarre.rar" |
| e-mail: | ivan.sobota@fer.hr |
Akelarre je simetričan algoritam kriptiranja bloka podataka, vrlo je brz i pogodan za hardversku i softversku implementaciju. Akelarre koristi blokove veličine 128-bita, osmišljen je u Španjolskoj u Madridu, autori su: Gonzalo Álvarez, Dolores de la Guía, Fausto Montoya i Alberto Peinado.
Algoritam je mješavina već postojećih algoritama IDEA i RC5. Iz tih algoritama upotrebljene su dobre stvari i upakirane u novi algoritam nazvan [2] Akelarre. Akelarre koristi podatkovno ovisno rotiranje bitova registra, XOR-anje bitova i zbrajanje u dvojnom komplementu. Iz korištenih operacija vidi se da pripadaju različitim algebarskim grupama, zbog toga je nemoguće pronaći direknu vezu između kriptiranog i jasnog teksta, što je i potrebno kod kriptiranja.
Osnovnu strukturu je nasljedio od IDEA-e, ali umjesto 16-bitnog podbloka koristi 32-bitni. Ne koristi modularno množenje, ali koristi 128-bitno rotiranje ovisno o ključu na početku i u svakoj rundi algoritma. Runda se sastoji još i od podatkovno ovisnog rotiranja nasljeđenog od RC5. Struktura podatkovnog ovisnog rotiranja naziva se i zbrajajuće-rotirajuća struktura (eng. addition-rotation structure).
Akelarre je definiran za varijabilno broj rundi i varijabilni duljinu ključa koja je višekratnik 64-bita. tj. 64,128,192,... Autori preporučuju korištenje Akelarre-a s 4 runde i s 128-bitnom duljinom ključa. U implementaciji i opisu Akelarre algoritma radi se o preporučenoj konfiguraciji autora!
Algoritam se sastoji od 2 osnovna koraka:
2.1 Generianje podključeva
2.2 Kriptiranje
2.3 Dekriptiranje
Generiranje podključeva je prikazano na slici 1. , izvodi se iz n-bitnog glavnog ključa koji je u našem slučaju 128-bita po preporuci autora. Broj podključeva koji je potrebno generirati ovisan je o broju rundi. Tako za r rundi potreban broj podključeva je 13 * r + 9. Za preporuku od 4 runde potreban broj podključeva iznosi 61. Najprije se ključ podijeli u 16-bitne blokove i dobije se m = 8 blokova nazvanih ki za i=1, ... , 8, svaki blok se kvadrira ( 32-bitni broj ) i dodaje mu se konstanta ( A0 ili A1 ) modulo 232.
Ako definiramo ki( 1 ) := ki2 + A0 mod 232 i ki( 1' ) := ki2 + A1 mod 232.
Prvih 8 podključeva se generira sljedećim postupkom:
Krajnjim bajtovima ki( 1 ) formiraju se višeznačajni bajtovi podključa Ki, dok se krajnjim bajtovima k( 1' )( i mod 8 ) +1 formiraju dva manje značajna bajta.
Nakon toga unutarnji bajtovi se kvadriraju i dodaje im se konstanta mod 232 ovisno o podključu kako je prokazano na slici 1.
Sljedečih 8 podključeva Ki za i = 9 do i = 16 slično kao i za prvih osam, samo se za ključ Ki koriste vrijednosi k( 2 )( ( i - 1 ) mod 8 ) + 1 i k( 2' )( i mod 8 ) + 1.
Postupak se nastavlja i za svaku rundu liste podključeva izračunavaju se nove vrijednosti ki( j ) i ki( j' )
sve do 61 podključa. Nakon izračunavanja podključevi se slijedno kopiraj u polje podključeva Zj( i ) koje se koristi u kriptiranju/dekriptiranju.
Kriptiranje se odvija po Akelarre algoritmu prikazanom na slici 2.
Akelarre algoritam kriptiranja sastoji se od ulazne transformacije, v rundi algoritma i izlazne transformacije.
Ulazna transformacija:Ulazna transformacija dijeli ulazni 128-bitni blok podataka na 4 32-bitna podbloka X1, X2, X3, X4. Nakon čega se dobiveni podblokovi kombiniraju s 4 podključa ( svi podključevi su definirani kao Zj( i ), gdje i označava rundu, a j redni broj korištenog podključa u toj rundi ) na sljedeći način:
Ta četiri podbloka dolaze kao ulaz u rundu 1. Svaka runda ( i = 1, ... , v ) sastoji se od sljedećih koraka:
1.) 4 ulazna podbloka R1( i - 1 ), R2( i - 1 ), R3(i - 1 ), R4( i - 1 ) se spajaju u jedan 128-bitni blok.
2.) 128-bitni blok se rotira u lijevo za proizvoljan broj bitova određen s manje značajnih 7 bitova podključa Z1( i ).
3.) tako rotirani 128-bitni blok ponovo se dijeli na 4 32-bitna podbloka S1( i ), S2( i ), S3( i ), S4( i ).
4.) par podblokova se XOR-a te proizvodi ulaz u zbrajajuće-rotirajuću strukturu.
5.) P1( i ) i P2( i ) se kombiniraju s 12 32-bitinih podključeva Z2( i ), Z3( i ), .... , Z13( i ), u Z-R (zbrajajuće-rotirajućoj) strukturi opisanoj kasnije. Izlaz iz te strukture sastoji se od dva 32-bitna podbloka Q1( i ) i Q2( i ).
6.) 4 podbloka iz koraka 3.) se XOR-aju s izlazom Z-R strukture na sljedeći način:
7.) sada i postaje i + 1 i runda se ponavlja s korakom 1.) sve do i = v.
Izlazna transformacija:Nakon zadnje runde slijedi izlazna transformacija definirana na sljedeći način:
1.) izlaz 4 podbloka iz runde v spaja se u jedan 128-bitni blok.
2.) 128-bitni blok se rotira u lijevo za proizvoljan broj bitova određen s manje značajnih 7 bitova podključa Z1( v + 1 ).
3.) tako rotirani 128-bitni blok dijeli se na 4 podbloka S1( v + 1 ), S2( v + 1 ), S3( v + 1 ), S4( v + 1 ).
4.) prethodni podblokovi kombiniraju se s posljednja 4 podključa na sljedeći način:
5.) dobivena 4 podbloka Y1, ... , Y4 spojeni u blok od 128 bitova čine kriptirani blok podataka.
Z-R struktura:
Ostvarivanje Z-R strukture (eng. addition-rotation structure) je ostvareno na sljedeći način:
Struktura je formirana u dvije kolone C1 i C2 kao što je prikazano na slici 3.
Ulazi u strukturu su P1 za prvu kolonu i P2 za drugu, dok su izlazi Q1 za prvu i Q2 za drugu kolonu.
Svaka kolona C1 i C2 radi sljedeće:
1.) viših 31 bitova se rotira u lijevo za određeni broj bitova.
2.) 32-bitnom izlazu prethodnog koraka je dodan podključ.
3.) nižih 31 bitova rezultata zbrajanja se rotira u lijevo za varijabilni broj bitova.
4.) 32-bitnom izlazu rotiranja dodaje se podključ.
5.) viših 31 bitova se ponovo rotira u lijevo za određeni broj bitova.
6.) 32-bitnom rotiranom bloku dodaje se podključ.
7.) ovaj postupak od koraka 3.) do koraka 6.) se ponavlja sve dok se ne izvrši 7 rotacija i 6 zbrajanja s podključevima.
8.) kad završi taj postupak izlaz iz kolone C1 je Q1( i ), a izlaz iz C2 je Q2( i ), gdje i označava broj runde.
Podključevi koji se dodaju u koloni C1 su Z8( i ), ... , Z13( i ), i podključevi za kolonu C2 su Z2( i ), ... , Z7( i ), gdje i također određuje rundu.
Neka s X[ a .. b ] označimo broj koji dobijemo izračunavajnem bitova a do b, gdje b označava najmanje značajan bit 20. Sada možemo odrediti i rotaciju u Z-R strukturi koja za kolonu C2 iznosi: 1. P1( i )[ 4 .. 0 ], 2. P1( i )[ 9 .. 5 ], 3. P1( i )[ 14 .. 10 ], 4. P1( i )[ 19 .. 15 ], 5. P1( i )[ 23 .. 20 ], 6. P1( i )[ 27 .. 24 ] i 7. P1( i )[ 31 .. 28 ]. Za kolonu C1 rotacija se izračunava na isti način samo se koristi blok Q1( i ) umjesto bloka P1( i ).
napomena: implementirani algoritam radi, ali nije provjeren jer ga na internetu nema ili ga nisam uspio pronaći. Primjer rezultata verzije opisane u izvornom dokumentu [2] je različita od rezultata implementacije jer je generiranje ključeva načinjeno s 64-bitnim glavnim ključem. Za sve pogreške pronađene u kodu molim Vas da me obavjestite.
Dekripiranje se odvija po istom algoritmu kao i kriptiranje, s tom razlikom da se podključevi koriste u obrnutnom redosljedu, i neki od njih su inverzni. Korištenje podključeva kod dekriptiranja je prikazano u usporedbi s podključevima kriptiranja u tablici 1.
Izračun inverza ključa nije opisan ni u jednom orginalnom dokumentu [2] [3], ali se jednostavno može zaključiti jer se inverzni ključevi koriste kod rotacije 128-bitnog bloka. Inverz se računa tako da se broj R dobiven iz najnižih 7 bitova korištenih kod rotacije kod kriptiranja zamjeni s ( 128 - R ). To znači da se kod dekriptiranja rotira tako da 128-bitni blok zauzme početno stanje koje je imao prije rotiranja kod kriptiranja.
Akelarre je prilagodljiv simetrični algoritam, ovisno o parametrima koje koristi. Kod algoritma možemo mjenjati broj rundi i duljinu ključa. Ovisno o izabranim parametrima možemo dobiti brži ili sigurniji algoritam. Za većinu slučajeva preporuča se 128-bitni ključ i 4 runde algoritma. Prilikom testiraja algoritma autori su na 130 MHz Intel Pentium-u s Windows 95 operacijskim sustavom i Microsoft Visual C++ 4.0 kompajlerom postigli rezultate od 3,22 Mbita/s. S tim performansama brzina kriptiranja jednaka je brzini kriptiranja IDEA-om s istim brojem rundi, dok RC5 algoritmu s preporučenim parametrima od 8 rundi i 16-bajtnim ključem potrebno je duplo više vremena.
Rezultati testiranja se nalaze i na grafovima gdje je prkazana ovisnost (eng. cross correlation) između jasnog i kriptiranog testa na slici 4. i izvođenja testa na slici 5. Kao poruku koju je algoritam kriptirao je bila 512-bajtna datoteka popunjena nulama i glavni ključ također popunjen nulama.
Zbog jednostavnog svojstva rotiranja i zbrajanja koje je hardverski moguće vrlo jednostavno izvesti pogodan je i za tu vrsu implementacije (eng. on chip). Algoritam je word-oriented pa na računalima skraćuje vrijeme izvođenja, i koristi malo memorije što je još veća pogodnost hardverske implementacije. Pokušaj razbijanja algoritma je uspio jer su nađene slabosti u generiranju podključa i funkciji rundi koja čuva parnost poruke kod rotiranja. Više o kriptoanalizi u dokumentu [3] Cryptanalysis of Akelarre.
[1] Leo Budin: Operacijski sustavi II - skripta, Zagreb, 2004
[2] Akelarre: a new Block Cipher Algorithm - orginalni opis algoritma
[3] Cryptanalysis of Akelarre
[4] Wikipedia - osnovno o Akelarre-u
[5] Stranica autora