Khufu și Khafre

În criptografie Khufu și Khafre sunt două cifre bloc dezvoltate de Ralph Merkle în 1989 în timp ce lucrau pentru Xerox la Centrul de Cercetare Palo Alto . La fel ca Snefru , o funcție hash , cifrele au fost numite cu numele (în engleză ) a faraonilor egipteni Cheops ( Khufu ), Chefren ( Khafre ) și Snefru .

Înainte de publicare, Xerox a propus voluntar algoritmii Khufu și Khafre pentru examinare de către NSA , care le-a blocat publicarea din motive de securitate națională (a se vedea exportul criptografiei ). Xerox, care avea mai multe contracte guvernamentale, a respectat cererea. Cu toate acestea, documentele au fost copiate de un recenzor, care le-a transmis activistului John Gilmore , care la rândul său le-a distribuit pe grupul de știri sci.crypt [1] ; [2] : toate acestea s-au întâmplat împotriva dorințelor lui Merkle [3] . Schemele au fost făcute publice mai târziu la conferința CRYPTO din 1990 .

Khufu și Khafre sunt brevetate de Xerox (brevet ( EN ) US5003597 , United States Patent and Trademark Office , Statele Unite ale Americii , depus la 26 martie 1991 ).

Khufu

Khufu este un cifru de bloc care funcționează pe blocuri pe 64 de biți cu o cheie neobișnuit de mare : 512 biți (în general, cifrele de blocuri utilizează taste mai mici, care depășesc cu greu 256 de biți). O mare parte din materialul cheie este utilizat pentru a construi casetele S ale cifrului: datorită faptului că timpul necesar acestui proces este destul de ridicat, utilizarea algoritmului nu este recomandată în situațiile în care trebuie tratate multe mesaje. dimensiune mică, dar este mai recomandat pentru criptarea unor cantități mari de date.

Khufu este un cifru Feistel care efectuează în mod normal 16 treceri (deși sunt permise toate valorile între 8 și 64 în trepte de 8), împărțit în blocuri de 8: fiecare grup de 8 pasaje este definit ca un octet , iar pentru fiecare octet un se folosește S-box diferit. Într-un singur pas, cel mai puțin semnificativ octet al jumătății unui bloc este plasat într-o cutie S (de 8x32 biți): ieșirea cutiei S este apoi combinată cu un XOR cu cealaltă jumătate a blocului. Jumătatea stângă este apoi rotită pentru a aduce un nou octet în poziție și în cele din urmă jumătățile sunt inversate. La începutul și la sfârșitul algoritmului, materialul suplimentar al cheii este combinat de XOR cu blocarea ( albirea cheii ). Materialul rămas al cheii este, după cum sa menționat, conținut în casetele S.

Există un atac diferențial în 16 pași al lui Khufu care poate prelua cheia secretă: are nevoie de 2 ⁴³ text clar ales și durează 2 ⁴³ (Gilbert și Chauvaud, 1994). În schimb, 2 ³² text clar și o complexitate de 2 ³² sunt necesare pentru a distinge cifrul de un flux aleatoriu de biți. Un atac de bumerang (Wagner, 1999 ) poate fi folosit într-o situație de atac adaptiv cu text clar / text cifrat ales cu 2 cifre ¹⁸ și complexitate similară. Khufu este, de asemenea, vulnerabil la un atac diferențial imposibil , care poate încălca până la 18 pasaje ale cifrului (Biham și colab. Aa., 1999).

Schneier și Kelsey (1996) au definit cei doi algoritmi ca rețele Feistel incomplete, dezechilibrate, puternic orientate spre eterogenitate .

Khafre

Khafre este similar cu Khufu, dar folosește un set regulat de casete S, care nu calculează din cheie, ci generează din tabelele RAND publicate în 1955 sub titlul A Million Random Digits with 100,000 Normal Deviates , care colectează un milion de cifre aleatorii și o sută de mii de abateri, utilizate pe scară largă în momentul în care puterea de calcul a computerelor nu era cu siguranță cea de astăzi. Având cutii S precomputate permite, în comparație cu Khufu, să cripteze foarte repede cantități mici de date. Pe de altă parte, Khafre necesită un număr mai mare de pași pentru a atinge aceleași niveluri de securitate ca Khufu, ceea ce îl face mai lent în criptarea unor cantități mari de date.

Algoritmul folosește o cheie a cărei dimensiune este un multiplu de 64. Deoarece casetele S nu depind de cheie, Khafre gestionează sub-cheile care sunt modificate prin operații XOR la ​​fiecare 8 pași.

Criptanaliza diferențială este foarte eficientă față de Khafre: 16 pași pot fi încălcați folosind ambele 1500 de texte simple alese, care sunt 2 ^{38 de} texte simple cunoscute. În mod similar, 24 de pasaje pot fi atașate folosind 2 ⁵³ text clar selectat sau 2 ⁵⁹ text clar cunoscut.

Bibliografie

• RC Merkle: Funcții rapide de criptare software - CRYPTO 1990
• Eli Biham , Adi Shamir : Criptanaliza diferențială a lui Snefru, Khafre, REDOC-II, LOKI și Lucifer - CRYPTO 1991
• Henri Gilbert , Pascal Chauvaud: Un atac cu text clar ales al criptosistemului Khufu din 16 runde - CRYPTO 1994
• Bruce Schneier , John Kelsey : Rețelele Feistel dezechilibrate și proiectarea cifrelor de blocuri - Criptare rapidă a software-ului 1996
• Eli Biham, Alex Biryukov , Adi Shamir: Miss in the Middle Attacks on IDEA, Khufu and Khafre - Fast Software Encryption 1999
• David Wagner : The Boomerang Attack - Criptare rapidă a software-ului 1999

Portal de criptografie

Portal de securitate IT