Akelarre

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. března 2021; kontroly vyžadují 64 úprav .

Akelarre
Tvůrce	Kolektiv autorů G. Álvarez Marañón, A. Fúster Sabater, D. Guía Martínez, F. Montoya Vitini, A. Peinado Domínguez
zveřejněno	1996 _
Velikost klíče	Více 64 bitů (doporučeno - 128 bitů)
Velikost bloku	128 bit
Počet kol	Jakékoli (doporučeno - 4)
Typ	Síť SP

Akelarre  je bloková šifra vyvinutá týmem španělských autorů a představená na SAC v roce 1996; kombinuje základní vývoj IDEA s koncepty z RC5 . Název akelarre se také používá v baskičtině pro označení shromáždění čarodějnic [1] .

Popis

Akelarre je 128bitová bloková šifra. V tomto případě je délka klíče proměnná a musí být násobkem 64 bitů; počet průchodů šifrováním je také proměnným parametrem. Optimální hodnoty navržené autory jsou 128bitový klíč a 4 kola [2] . Funkce šifrování v Akelarre je strukturálně podobná té, kterou poskytuje IDEA. Mezi těmito šiframi je ale obecně celá řada podstatných rozdílů: IDEA například používá 16bitovou velikost slova, nikoli 32bitovou, odlišná je i množina používaných primitivních operací. Akelarre platí [3] :

• modulo sčítání ;
• bitový exkluzivní OR ( XOR );
• operace kruhového posunu doleva o proměnný počet bitů ( ).

Právě použití cyklického posunu o proměnný počet bitů určuje podobnost tohoto algoritmu s RC5 [4] . Všechny uvedené operace patří do různých algebraických grup a jsou nekompatibilní v tom smyslu, že asociativní a distributivní zákony neplatí pro žádnou z nich. To vám umožní skrýt všechny existující vztahy mezi holým textem a šifrovým textem a klíčem, což ztěžuje kryptoanalýzu [5] .

Operační algoritmus

Strukturálně lze algoritmus rozdělit na dvě podčásti:

1. Šifrovací/dešifrovací algoritmus.
2. Algoritmus pro rozšíření klíče zadaného uživatelem.

Šifrování

Nejprve je otevřený text X rozdělen do 128bitových bloků, z nichž každý je dále rozdělen do 4 dílčích bloků X1 ... X4 , na které je již aplikována primární transformace. Celá procedura šifrování probíhá ve třech fázích.

• Vstupní transformace spočívá v modulovém přidání rozšířených klíčových fragmentů Ki1 , Ki4 s podbloky X1 , X4 a aplikování bitového exkluzivního OR ( XOR ) na rozšířené klíčové fragmenty Ki2 , Ki3 a podbloky X2 , X3 respektive. Tyto transformace jsou nutné k zamezení následků možného vstupu do vstupu sekvence všech nul nebo samých jedniček a také ke ztížení napadení šifry pomocí diferenciální kryptoanalýzy (viz slabý klíč ).
• Šifrovací kola:

1. Na začátku každého kola se otočí 128bitový blok, který je výsledkem spojení dílčích bloků vytvořených v důsledku vstupní transformace nebo předchozího kola; ve třetím kole ( ) je proměnný počet bitů specifikujících posun určen nejméně významnými bity fragmentu klíče Km1 vytvořeného jako výsledek procedury rozšíření klíče.
2. V další fázi je 128bitový blok opět rozdělen do 4 dílčích bloků po 32 bitech a bitové OR jsou vypočteny pro pár prvních dvou a poté pro pár posledních dvou bloků. Další transformace výsledných bloků C1 , C2 jsou určeny činností AR - modulu ( addičně -rotační struktura). Struktura modulu se skládá ze dvou sloupců: C 1 se přivádí na vstup prvního, C 2  - druhého. Pro C1 : _
   • Prvních 31 bitů C1 je otočeno doleva (velikost posunu je určena nejméně významnými 5 bity C2 ) .
   • K výsledku získanému v předchozím kroku se přičte modulo číslo s jedním z fragmentů rozšířeného klíče Km8 .
   • Posledních 31 bitů výstupního bloku předchozího kroku se otočí doleva jako v kroku 1.
   • 32bitový blok získaný v předchozím kroku je přidán modulo k číslu s podklíčem Km9 podobně jako v kroku 2 .
   • Vysokých 31 bitů výstupního bloku z předchozího kroku se otočí doleva jako v kroku 1.
   • 32bitový blok získaný v předchozím kroku je přidán modulo k číslu s podklíčem Km10 jako v kroku 2.
   • Kroky 3 až 6 se opakují, dokud nebude provedeno celkem 7 posunů a 6 přidání podklíče.

C 02 se zpracovává obdobně pouze pomocí kláves K m2 ... K m7 . Z bloků D 1 , D 2 získaných v důsledku provozu modulu se přidáním bloků vytvořených rozdělením 128bitového bloku na začátku kola vytvoří 4 výstupní hodnoty kola ( každý z X1 , X3 se přidá k D1 a každý z X2 , X4-  s D2 ) . Aplikace bitového posunu ne na celý blok, ale pouze na 31 bitů se provádí, aby se předešlo možné identitě výstupních a vstupních výsledků, kterou lze pozorovat při použití složených čísel [6] .

• Při finální transformaci se podblok 128bitového bloku vytvořený zřetězením 128bitového bloku získaného po posledním kole cyklicky posouvá doleva o počet bitů určený posledními 7 bity podklíče K f1 , po který je výsledný blok rozdělen na 32bitové podbloky, na které jsou aplikovány operace podobné těm ze vstupního bloku transformace, ale s klíči K f2 …K f5 [7] .

Dešifrování

Algoritmus dešifrování je v podstatě organizován stejným způsobem jako algoritmus používaný pro šifrování, pouze podklíče jsou již generovány na základě šifrovacích klíčů. Shoda mezi klíči pro šifrování a pro dešifrování je následující (zde se počáteční transformací rozumí nulté kolo a konečnou transformací je (r + 1) kolo) [8] :

Kolo	Klíče používané při šifrování	Klíče používané při dešifrování
Prvotní transformace
1. kolo
2. kolo
m-té kolo
r-té kolo
Finální transformace

Rozšíření klíče

Aby algoritmus fungoval, je vyžadován klíč skládající se z alespoň 22 dílčích bloků po 32 bitech (704 bitů) [9] . Následující popis odpovídá použití algoritmu na 128bitový klíč:

1. Uživatelský klíč je rozdělen na 8 částí po 16 bitech k 1 ... k 8 .
2. Každý jednotlivý fragment je umocněn na druhou, aby se získala 32bitová hodnota, a modulo sčítání počtu výsledných hodnot se provádí samostatně s každou z konstant a 1 , a 2 ; v důsledku toho se na základě každého z počátečních klíčů ki1 vytvoří dvě dočasné hodnoty Kti a K'ti . Konstanty by měly být zvoleny tak, aby se zabránilo možnému vytvoření klíče sestávajícího pouze z nul. Autoři navrhli 1 =A49ED284H a 2 = 73503DEH [ 10] .
3. Z dočasných hodnot získaných v předchozím kroku se vytvoří fragmenty předběžného rozšířeného klíče Ke1 ... Ke8 . Každý z těchto fragmentů je výsledkem zřetězení 8 nízkých a 8 vysokých bitů K'ti , stejně jako 8 nízkých a 8 vysokých bitů Kti ; 16 bitů umístěných uprostřed každé z dočasných hodnot je zpracováno podobným způsobem jako zpracování k 1 ... k 8 pro získání nových hodnot rozšířených klíčových fragmentů [11] .
4. Klíče použité v počáteční transformaci ( K i1 … K i4 ), provozu AR-modulu ( K m1 … K m13 pro každé z m kol) a konečné transformaci ( K f1 … K f5 ) jsou postupně vyplněny hodnoty K e1 vzniklé během činnosti algoritmu …K e8 [12] .

Udržitelnost

Již rok poté, co byla šifra představena, provedla práce Nielse Fergusona a Bruce Schneiera útok, který umožňuje prolomení na základě vzorku ne více než 100 otevřených textů. Útok probíhá ve 4 fázích: v prvních dvou se obnoví počáteční a konečná konverze bitů podklíče a další dvě využívají zranitelnosti schématu rozšíření klíče a se zvýšením počtu kol v algoritmu, také prudce narůstá množství informací, které lze získat o fungování systému. Složitost organizace AR-modulu díky jeho vlastnostem (paritní vlastnosti) vůbec nekomplikuje hackování [13] . Ve stejné práci je uveden další útok, ve kterém navíc použití diferenciální charakteristiky algoritmu umožňuje snížit počet nutných operací nakonec na .

Další prací, ve které byla úspěšně provedena kryptoanalýza Akelarre, je Lars Knudsen a Vincent Ridgman. Popisují dva možné útoky: jeden je založen na použití otevřeného textu , druhý umožňuje odhalit klíč pouze pomocí šifrovaného textu a některých informací o otevřeném textu - zejména stačí vědět, že se jedná o anglický text ASCII . Stejně jako útoky navržené v práci Fergusona a Schneiera, útoky navrhované v této práci nezávisí na počtu kol algoritmu nebo velikosti klíče a útok založený pouze na šifrovaném textu patří mezi prakticky použitelné, protože již jeden poslech postačuje kanál pro jeho realizaci [14] .

Význam

Akelarre, koncipovaný jako algoritmus, který úspěšně kombinuje prvky dvou spolehlivých a dobře známých algoritmů IDEA a RC5 a má složitou architekturu, neprokázal vysokou kryptografickou sílu, což jasně ukázalo, že kombinace komponent dvou dobře chráněných algoritmů nemusí vždy vést. ve spolehlivém novém [15] . Jak je uvedeno v názvu jednoho z článků, které zkoumaly algoritmus [16] :

Dvě plusy někdy dávají mínus.

Původní text  (anglicky)[ zobrazitskrýt] Dvě práva někdy dělají chybu.

Úpravy

Po úspěšné kryptoanalýze Akelarre představili jeho návrháři aktualizovanou variantu nazvanou Ake98 . Tato šifra se liší od původního Akelarreova nového AR-boxu (Addition-Rotation box) permutací slov prováděnou na konci šifrovacího průchodu, stejně jako přidáním podklíčů na začátku každého šifrovacího průchodu. Parametry jako velikost klíče a velikost bloku přitom zůstaly jako dříve nastavitelné, jejich minimální velikost však tvůrci nedefinovali [17] . Modul AR funguje v nové verzi jako generátor pseudonáhodných čísel .

V roce 2004 našli Jorge Nakaara Jr. a Daniel Santana de Freita velké třídy slabých klíčů pro Ake98. Tyto slabé klíče umožňují analýzu rychleji než hrubou silou a používají pouze 71 známých kusů textu pro 11,5 šifrovacích průchodů v Ake98. Kromě toho bylo ve stejné práci provedeno hodnocení výkonu algoritmu, které ukázalo, že ačkoli pro počet kol 25,5 nebo více nemá algoritmus slabé klíče, ukazuje se, že je 4krát pomalejší. než IDEA , 8krát pomalejší než AES a 14krát - RC6 [18] .

Poznámky

1. ↑ Stamp M. et al, 2007 , str. 160.
2. ↑ Panasenko S., 2009 , s. 101.
3. ↑ Álvarez MG et al, 1996 , str. 2-3.
4. ↑ Panasenko S., 2009 , s. 99.
5. ↑ Álvarez MG et al, 1996 , str. 2.
6. ↑ Álvarez MG et al, 1996 , str. 5-6.
7. ↑ Panasenko S., 2009 , s. 98-100.
8. ↑ Álvarez MG et al, 1996 , str. 6.
9. ↑ Álvarez MG et al, 1996 , str. 7.
10. ↑ Álvarez MG et al, 1996 , str. 7-8.
11. ↑ Panasenko S., 2009 , s. 101-102.
12. ↑ Ferguson N. a kol., 1997 , str. 207-208.
13. ↑ Ferguson N. a kol., 1997 , str. 210-211.
14. ↑ Panasenko S., 2009 , s. 102-103.
15. ↑ Knudsen L. a kol., 1997 , str. 223.
16. ↑ Panasenko S., 2009 , s. 103.
17. ↑ Júnior J. et al, 2005 , str. 208.
18. ↑ Júnior J. et al, 2005 , str. 213-214.

Literatura

• Álvarez MG, Fúster SA, Guía MD, Montoya VF, Peinado DA Akelarre: Nový algoritmus blokové šifry // SAC'96, Třetí výroční seminář o vybraných oblastech kryptografie - Queen's University, Kingston, Ontario, 1996, Proceedings. - 1996. - S. 1-14 .
• Panasenko S.P. Kapitola 3 // Šifrovací algoritmy. Speciální referenční kniha - Petrohrad. : BHV-SPb , 2009. - S. 97-103. — 576 s. — ISBN 978-5-9775-0319-8
• Ferguson N., Schneier B. Cryptanalysis of Akelarre // SAC'97: Fourth Annual Workshop on Selected Areas in Cryptography, Carleton University, Ottawa, 1997, Proceedings. - 1997. - S. 201-212 .
• Knudsen LR, Rijmen V. Dvě práva někdy dělají chybu // SAC'97: Fourth Annual Workshop on Selected Areas in Cryptography, Carleton University, Ottawa, 1997, Proceedings. - 1997. - S. 213-223 .
• Júnior J. N. , Freitas D. S. Cryptanalysis of Ake98  (anglicky) // Progress in Cryptology - INDOCRYPT 2004 : 5th International Conference on Cryptology in India, Chennai, India, December 20-22, 2004. Proceedings , K. Cantewanthan Berlin , Heidelberg , New York, NY , Londýn [atd.] : Springer Berlin Heidelberg , 2005. - S. 206-217. — 431 s. - ( Lecture Notes in Computer Science ; Vol. 3348) - ISBN 978-3-540-24130-0 - ISSN 0302-9743 ; 1611-3349 – doi:10.1007/978-3-540-30556-9_17
• Stamp M., Low MR Aplikovaná kryptoanalýza: prolamování šifer v reálném světě. - John Wiley & Sons, Inc., Hoboken, New Jersey, 2007. - S. 160. - ISBN 978-0-470-11486-5 .

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) nafukovací ryba Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher