Atacul de forfecare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 6 mai 2018; verificările necesită 9 modificări .

Shift attack ( ing.  slide attack ) - atac criptografic , care este, în cazul general, un atac bazat pe text clar selectat , care permite criptanaliza cifrurilor cu mai multe runde bloc, indiferent de numărul de runde utilizate. Propus de Alex Biryukov și David Wagner în 1999 [1] .

Istoricul creației

Ideea de a crea un atac de forfecare a venit pentru prima dată cu Edna Grossman și Brian Tuckerman în 1977. Raportul corespunzător a fost publicat [2] împreună cu IBM . Grossman și Tuckerman au reușit să arate posibilitatea unui atac asupra unui cifr NDS (New Data Seal) destul de slab . Atacul exploatează faptul că cifrul din fiecare rundă amestecă doar aceeași cheie, folosind aceeași masă în fiecare rundă. Utilizarea textelor clare ocolește acest lucru și ne permite să o considerăm cea mai veche versiune a atacului de schimbare.

În 1990, a fost propusă criptoanaliza diferențială , demonstrând vulnerabilitatea criptosistemelor de tip DES cu mai multe runde [3] . O modalitate de a asigura puterea lor criptografică a fost creșterea numărului de runde utilizate, ceea ce a crescut complexitatea de calcul a atacului proporțional cu numărul lor. Utilizarea acestei îmbunătățiri pentru mulți algoritmi de criptare s-a bazat, în special, pe judecata empirică că orice cifră, chiar și mai degrabă slabă, poate fi făcută criptografic puternic prin repetarea operațiunilor de criptare de mai multe ori:

Cu excepția doar a câtorva cazuri degenerate, algoritmul poate fi securizat în mod arbitrar prin creșterea numărului de runde.

Text original  (engleză)[ arataascunde] Cu excepția câtorva cazuri degenerate, un algoritm poate fi securizat în mod arbitrar prin adăugarea mai multor runde. — B. Preneel, V. Rijmen, A. Bosselears: Principii și performanță a algoritmilor criptografici [4]

De exemplu, unele cifruri propuse ca candidați pentru concursul AES în 1997 au avut un număr destul de mare de runde: RC6(20), MARS(32), SERPENT(32), CAST(48) [1] .

Cu toate acestea, în 1999, a fost publicat un articol al lui Alex Biryukov și David Wagner care descrie un atac de forfecare, care a respins această presupunere. O caracteristică a acestui atac a fost că nu depindea de numărul de runde de cifrare; succesul său a necesitat doar identitatea rundelor și posibilitatea de criptoanaliza a funcției de criptare pe o rundă separată. Articolul descrie, de asemenea, aplicarea acestui atac la cifrul TREYFER și versiunile simplificate ale cifrurilor DES (2K-DES) și BLOWFISH [1] .

În 2000, a fost publicat un al doilea articol, care a demonstrat versiuni îmbunătățite ale atacului de schimbare - „Alunecare cu o răsucire” și „Diapozitiv de completare”, permițând extinderea acestuia la cifrurile ale căror runde au diferențe mici. Deci, cu ajutorul acestor îmbunătățiri, au fost sparte unele modificări ale cifrului DES , precum și o versiune simplificată de 20 de runde a standardului de criptare GOST 28147-89 [5] [6] .

Descriere generală

În cel mai simplu caz [7] , se aplică un atac shift algoritmilor de criptare, care sunt repetări multiple ale unei anumite funcții de criptare , a cărei introducere la fiecare rundă este textul cifrat (rezultatul criptării din runda anterioară) și o cheie rotundă. , care este același pentru toate rundele. Principalele cerințe pentru implementarea cu succes a acestui atac sunt [7] :

  1. Identitatea rundelor (care este garantată prin utilizarea aceleiași funcție și a aceleiași taste în fiecare rundă)
  2. Abilitatea de a găsi cu ușurință cheia , cunoscând textul la intrare și textul la ieșire a unei runde

Algoritmul celui mai simplu atac

Pasul 1. Să luăm ceva text simplu la intrare și textul cifrat corespunzător la ieșirea algoritmului de criptare. Pasul 2. Luați un alt text simplu și textul cifrat corespunzător , astfel încât perechea să fie diferită de perechea deja aleasă . Pasul 3. Să presupunem că este legat de relația = , și este legat de relația , i.e. și sunt rezultatele criptării cu o singură rundă și respectiv. Să numim o astfel de pereche „pereche de alunecare” (pereche de alunecare) [1] . Folosind afirmația că cheia de criptare poate fi calculată cu ușurință, cunoscând textul la intrare și textul la ieșire a unei runde, calculăm cheia la prima rundă de criptare prin relația , iar cheia la ultima rundă de criptare prin relaţia . Pasul 4. Să verificăm egalitatea . pentru că prin condiție, toate cheile rotunde sunt aceleași, atunci această egalitate trebuie satisfăcută, în caz contrar presupunerea făcută la pasul 3 este incorectă și este necesar să revenim la pasul 2, excluzând perechea testată din lista de posibili candidați. Îndeplinirea egalității indică faptul că cheia este potențial cheia rotundă dorită. Pasul 5. Pentru a verifica cheia găsită pentru false pozitive, ar trebui să o înlocuiți în algoritmul de criptare și să verificați funcționarea corectă pe mai multe perechi diferite cunoscute de „text simplu - text cifrat ”. În ciuda faptului că este posibil ca cheia greșită să treacă acest test, în cazul cifrurilor bune, probabilitatea ca aceasta este extrem de mică [7] , ceea ce înseamnă că cheia verificată este cu mare probabilitate cheia rotundă dorită. Astfel, în cazul verificării cu succes, declarăm cheia de căutat, în caz contrar revenim la pasul 2, excluzând perechea verificată și cheia din lista de posibili candidați.

Note despre algoritm

Modificări ale atacului Shift

În cazul cifrurilor bloc moderne, cheile rotunde nu sunt de obicei aceleași. Acest lucru duce la faptul că algoritmul utilizat în construcția celui mai simplu atac este în general inaplicabil pentru astfel de cifruri și necesită unele completări.

Enunțul problemei

Să existe un algoritm de criptare nr. 1, format din blocuri, astfel încât cheia să fie utilizată în runda a treia (vom presupune că numărul total de chei , cheia va fi nevoie mai târziu), și să alegem o pereche de „text simplu – text cifrat” . La ieșirea primei runde, obținem textul , unde este funcția de criptare.

Mai mult, atacul shift implică criptarea textului cu un nou cifr bloc nr. 2, format din blocuri de la la . Să notăm textul cifrat la ieșirea blocului --lea ca . Este ușor de observat că în acest caz, la ieșirea blocului i-lea, vom obține textul deja găsit mai sus , ceea ce înseamnă că textul și textul cifrat sunt legate prin relația .

Astfel, am obținut o pereche care satisface relațiile și , care nu este altceva decât o pereche de deplasare generală. În consecință, în cel mai simplu caz, aceste relații vor lua forma și .

Presupunând că un text are legătură cu raportul , ar trebui să obținem textul cifrat la ieșirea algoritmului de criptare #2 cu textul la intrare, pentru a-l confirma sau infirma prin rapoarte . În cazul unui program de chei banal, algoritmii de criptare nr. 1 și nr. 2 sunt identici, ceea ce înseamnă că poate fi obținut prin criptarea textului cu un cifr bloc deja existent. În caz contrar, algoritmii de criptare nr. 1 și nr. 2 sunt diferiți, iar criptoanalistul nu este capabil să construiască algoritmul nr. 2, ceea ce înseamnă că textul cifrat nu poate fi obținut.

Cazul unei rețele Feistel cu autoasemănări în două runde

Slide de  completare [ 5 ]

După cum se menționează în notele la algoritmul de atac, cazul criptoanalizei cifrurilor cu auto-asemănarea p-round poate fi ușor redus la cel mai simplu caz de atac prin deplasare prin combinarea mai multor runde într-una singură, ceea ce este echivalent cu deplasarea blocurilor de cifr prin runde. În cazul unei rețele Feistel cu taste rotunde alternate alternativ și , adică cu auto-asemănarea în două runde, această abordare poate crește complexitatea criptoanalizei și, prin urmare, poate face ca atacul de schimbare să fie ineficient. În schimb, s-a propus, ca și până acum, să se schimbe doar cu o rundă în loc de două, dar în același timp să se modifice ușor cerințele impuse perechii de schimburi.

În descrierea problemei luate în considerare mai sus, s-a indicat că pentru a căuta o pereche de shift, în cazul general, este necesar să se poată lucra cu două -cifre bloc - cel original, format din blocuri de la până la , iar cel nou, format din blocuri de la la . Slide-ul de completare vă permite să lucrați numai cu cifrul bloc original.

Deși următorul raționament va fi demonstrat folosind un cifr cu 4 runde, acesta poate fi extins la orice număr de runde. Mai întâi, să vedem cum se modifică textul simplu în diferite runde de criptare. Să reprezentăm textul simplu ca , unde și sunt părțile din stânga și respectiv din dreapta ale textului.

Număr rotund Partea stanga Partea dreaptă
unu
2
3
patru

Să notăm textul la ieșirea rundei 1 și textul cifrat . Acum, rețineți că, pentru a găsi textul cifrat la ieșirea unui cifru bloc de 4 runde cu un program cheie , este suficient să adăugați diferența în partea dreaptă a fiecărei runde a cifrului original și apoi să criptați textul cu cifrul rezultat (Fig. 2, diagrama din dreapta). Pentru a face acest lucru, vom furniza textul la intrarea cifrului inițial . Să notăm textul cifrat ca . Să luăm în considerare modul în care textul se modifică în diferite runde de criptare.

Număr rotund Partea stanga Partea dreaptă
unu
2
3

patru

Din aceasta se poate observa că diferența introdusă se păstrează la fiecare rundă, ceea ce înseamnă că textele cifrate și sunt legate prin relațiile: și , iar perechile „text simplu - text cifrat” și prin relațiile și .

Dacă textele sunt legate printr-un raport , ei spun că textele și au o diferență de forfecare (diferența de diapozitive în engleză ) .  

Astfel, se obțin următoarele ecuații pentru perechea de forfecare:


Ca și înainte, în cazul textelor -bit, sunt necesare texte clare pentru a găsi perechea de deplasare . Perechea de forfecare trebuie să satisfacă acum ecuația (vezi Fig. 2). În cazul găsirii unei perechi potențiale de deplasare, a doua ecuație permite găsirea unui candidat , iar dacă funcția este suficient de vulnerabilă la criptoanaliza, atunci aceste ecuații ne permit să găsim cheile potențiale dorite și . După aceea, rămâne doar să verificați dacă există false pozitive.

Alunecare cu o răsucire  [ 5 ]

Cerința specificată în declarația problemei de a putea lucra cu cifrul original #1, constând din blocuri de la la , și noul cifru #2, constând din blocuri de la la la , poate fi ușor transformat folosind așa-numitul shift- abordare și-rotire.

Dacă excludem ultima permutare a părților din stânga și din dreapta ale textului și inversăm ordinea cheilor, atunci decriptarea în rețeaua Feistel va avea loc exact în același mod ca și criptarea [1] . Abordarea shift-and-rotate folosește această proprietate, și anume, propune utilizarea algoritmului de decriptare ca cifru #2 (vezi Fig. 3).

Această abordare nu are diferențe fundamentale față de cel mai simplu algoritm. Ca și în cel mai simplu caz, cerințele pentru perechea de schimbare , unde . Astfel, obținem ecuațiile:


și o condiție care face mai ușor să găsiți perechi de schimburi:

Ca de obicei, în cazul textelor -bit, sunt necesare texte clare pentru a găsi perechea de deplasare . Dacă este găsit, vulnerabilitatea funcției vă permite să găsiți cheia din ecuații .

Numărul de texte necesare la acest pas poate fi redus la . Pentru a face acest lucru, criptăm diverse texte ale formularului și decriptăm diverse texte ale formularului , unde și sunt fixate și îndeplinim condiția . Astfel, din moment ce acum lucrăm, de fapt, cu texte - bit, conform paradoxului zilei de naștere, printre aceste perechi „text simplu-text cifrat”, există o probabilitate mare de apariție a unei perechi de deplasare.

Cheia poate fi găsită prin aplicarea metodei descrise pentru cazul general al cifrurilor bloc cu auto-similaritate p-round, și anume, prin combinarea fiecărei două runde ulterioare într-una singură - astfel reducem problema la cel mai simplu caz. Deși dimensiunea cheii rotunde se va dubla, acest lucru nu va complica criptoanaliza, deoarece cheia , care este jumătate din noua cheie rotundă, este deja cunoscută și trebuie să găsim doar a doua jumătate, egală ca dimensiune cu cea rotundă. cheie în problema inițială.

Alte modificări

O modificare separată poate fi considerată utilizarea simultană a celor două abordări descrise mai sus - Complementation slide și Sliding with a twist, care permite extinderea atacului de schimbare la cifruri cu auto-similaritate în 4 runde [5] .

Problema criptoanalizei cifrurilor cu runde inegale diferă de toate cazurile luate în considerare până acum, în soluția cărora nu se poate folosi niciuna dintre modificările de atac considerate. Pentru cazul unor astfel de cifruri, a fost propus un atac de realiniere cu slide [ 8 ]  , demonstrat pe exemplul de modificări ale cifrului DES , în special, pe exemplul versiunii complete de 16 runde a DES

Sliding-linear attack ( în engleză  slide-linear attack ) [9] este un exemplu de implementare a unui atac shift utilizând principiile criptoanalizei liniare . Lucrarea acestui atac a fost prezentată pe cifrul 4K-DES.

Există, de asemenea, îmbunătățiri pentru a accelera implementarea modificărilor deja existente ale atacului de forfecare. În special, una dintre aceste îmbunătățiri, descrisă în lucrarea lui Eli Biham, Orr Dunkelman, Nathan Keller: Improved Slide Attacks [10] , face posibilă găsirea perechilor de deplasare mult mai rapid folosind o structură de cifră ciclică și permutările cheie corespunzătoare. Funcționarea acestei modificări a fost prezentată pe exemplul diferitelor variante ale cifrului GOST 28147-89 (GOST).

Algoritmi de criptare vulnerabili la atacul prin schimbare și modificările acestuia

Descris în articolele originale: [1] [5]

Descris în alte surse

Atacurile Shift ale clasei de funcții hash [13]

Pe lângă scopul lor inițial - atacarea cifrurilor bloc, principiile atacului shift și-au găsit aplicație și în domeniul criptoanalizei funcției hash. Similar cu cazul cifrurilor bloc, unde a fost folosit un atac shift pentru a găsi programul cheilor, s-a dovedit a fi potențial aplicabil pentru găsirea cheii secrete utilizate pentru a genera și valida hash-ul mesajului transmis. În special, această abordare a fost demonstrată pe exemplul generării inserției simulate (MAC) .

De asemenea, atacul shift s-a dovedit a fi util nu numai în cazul funcțiilor hash criptografice care iau valoarea unei chei secrete ca parametru, ci și în cazul funcțiilor hash care produc un hash doar pe baza unui mesaj. O analiză a unor astfel de funcții bazată pe un atac shift face posibilă identificarea, cu un grad ridicat de probabilitate, a unor proprietăți de shift și, ca urmare, a anumitor modele în funcționarea algoritmilor de hashing.

Funcții hash vulnerabile la atacul shift: [13]

Modalități de creștere a rezistenței criptografice la modificările atacurilor prin shift [7] [16]

Întrucât vulnerabilitățile programului cheie sunt utilizate în timpul atacului de schimb, una dintre măsuri este de a-l complica. În special, este necesar să se evite repetițiile ciclice în programul cheie, dacă este posibil, sau cel puțin să se folosească o perioadă de repetiție suficient de mare. În cazul unui număr mic de taste, în loc de o simplă repetare periodică, ar trebui folosită o ordine aleatorie a secvenței lor.

Pe lângă slăbiciunea programului cheie, atacul shift exploatează și aceleași runde. O modalitate de a evita acest lucru este utilizarea unor constante rotunde diferite ca parametru al funcției de criptare pe runde separate - acest lucru vă permite să faceți diferențe în funcționarea blocurilor de criptare individuale fără a complica în mod semnificativ algoritmul de criptare în ansamblu.

De asemenea, eficacitatea unui atac prin schimbare poate fi redusă semnificativ prin creșterea puterii criptografice a funcției de criptare rotundă. Deci, rezistența sa la atacuri bazate pe texte clare va face mult mai dificilă găsirea cheii rotunde chiar și în prezența unei perechi de shift.

Note

  1. ↑ 1 2 3 4 5 6 7 Alex Biryukov, David Wagner. Slide Attacks  //  Criptare rapidă a software-ului. 6th International Workshop, FSE'99 Roma, Italia, 24–26 martie, 1999 Proceedings. - Springer Berlin Heidelberg, 1999. - P. 245-259 . - ISBN 978-3-540-66226-6 .  (link indisponibil)
  2. ↑ EK Grossman, Thomas J. Watson IBM Research Center Research Division, B. Tuckerman. Analiza unui cifr asemănător Feistel, slăbit de lipsa cheii rotative . - IBM Thomas J. Watson Research Division, 1977. - 33 p.
  3. ↑ Eli Biham, Adi Shamir. Criptanaliză diferențială a criptosistemelor asemănătoare DES  //  Advances in Cryptology-CRYPT0' 90 Proceedings. - Springer Berlin Heidelberg, 1990. - P. 2-21 . — ISBN 978-3-540-54508-8 .  (link indisponibil)
  4. ↑ B. Preneel, V. Rijmen, A. Bosselears. Principiile și performanța algoritmilor criptografici  //  Dr. Jurnalul lui Dobb. - Miller Freeman, 1998. - Vol. 23 , nr. 12 . - P. 126-131 .
  5. ↑ 1 2 3 4 5 6 Alex Biryukov, David Wagner. Advanced Slide Attacks  (engleză)  // Advances in Cryptology - EUROCRYPT 2000. Conferința internațională privind teoria și aplicarea tehnicilor criptografice Bruges, Belgia, 14–18 mai 2000 Proceedings. - Springer Berlin Heidelberg, 2000. - P. 589-606 . — ISBN 978-3-540-67517-4 .  (link indisponibil)
  6. ↑ 1 2 Panasenko S.P. Shift attack // Algoritmi de criptare. Carte de referință specială - Sankt Petersburg. : BHV-SPb , 2009. - S. 40-42. — 576 p. — ISBN 978-5-9775-0319-8
  7. ↑ 1 2 3 4 5 Chalermpong Worawannotai, Isabelle Stanton. Un tutorial despre atacurile slide  . Arhivat din original pe 29 noiembrie 2014.
  8. ↑ Raphael C.-W. Phan. Advanced Slide Attacks Revisited: Realigning Slide on DES  //  Progress in Cryptology – Mycrypt 2005. Prima Conferință Internațională despre Criptologie în Malaezia, Kuala Lumpur, Malaezia, 28-30 septembrie 2005. Proceedings. - Springer Berlin Heidelberg, 2005. - P. 263-276 . — ISBN 978-3-540-28938-8 . Arhivat din original pe 12 iunie 2018.
  9. ↑ 1 2 Soichi Furuya. Slide Attacks with a Known-Plaintext Cryptanalysis  (engleză)  // Information Security and Cryptology - ICISC 2001. A 4-a Conferință Internațională Seul, Coreea, 6-7 decembrie 2001 Proceedings. - Springer Berlin Heidelberg, 2002. - P. 214-225 . - ISBN 978-3-540-43319-4 . Arhivat din original pe 9 iunie 2018.
  10. ↑ Eli Biham, Orr Dunkelman, Nathan Keller. Atacuri de diapozitive îmbunătățite  //  Criptare rapidă a software-ului. 14th International Workshop, FSE 2007, Luxemburg, Luxemburg, 26-28 martie 2007, Revised Selected Papers. - Springer Berlin Heidelberg, 2007. - P. 153-166 . — ISBN 978-3-540-74617-1 .  (link indisponibil)
  11. ↑ Selçuk Kavut, Melek D. Yücel. Slide Attack on Spectr-H64  //  Progress in Cryptology - INDOCRYPT 2002. A treia conferință internațională privind criptologia în India Hyderabad, India, 16-18 decembrie 2002 Proceedings. - Springer Berlin Heidelberg, 2002. - P. 34-47 . - ISBN 978-3-540-00263-5 . Arhivat din original pe 11 iunie 2018.
  12. ↑ Nicolas T. Courtois, Gregory V. Bard, David Wagner. Atacurile algebrice și slide pe KeeLoq  //  Criptare rapidă a software-ului. 15th International Workshop, FSE 2008, Lausanne, Elveția, 10-13 februarie 2008, Revised Selected Papers. - Springer Berlin Heidelberg, 2008. - P. 97-115 . — ISBN 978-3-540-71038-7 . Arhivat din original pe 30 octombrie 2018.
  13. ↑ 1 2 Michael Gorski, Stefan Lucks, Thomas Peyrin. Slide Attacks on a Class of Hash Functions  //  Advances in Cryptology - ASIACRYPT 2008. A 14-a Conferință Internațională privind Teoria și Aplicația Criptologiei și Securitatea Informației, Melbourne, Australia, 7-11 decembrie 2008. Proceedings. - Springer Berlin Heidelberg, 2008. - P. 143-160 . - ISBN 978-3-540-89254-0 .  (link indisponibil)
  14. ↑ Yu Sasaki, Lei Wang, Kazuo Ohta, Noboru Kunihiro. Recuperarea parolei la provocare și răspuns: Atacul diferențial imposibil asupra funcției Hash  //  Progress in Cryptology – AFRICACRYPT 2008. Prima Conferință Internațională de Criptologie în Africa, Casablanca, Maroc, 11-14 iunie 2008. Proceedings. - Springer Berlin Heidelberg, 2008. - P. 290-307 . — ISBN 978-3-540-68159-5 . Arhivat din original pe 6 iunie 2018.
  15. ↑ 1 2 Markku-Juhani O. Saarinen. Criptanaliză a cifrurilor bloc bazate pe SHA-1 și MD5  //  Criptare rapidă a software-ului. 10th International Workshop, FSE 2003, Lund, Suedia, 24-26 februarie 2003. Lucrări revizuite. - Springer Berlin Heidelberg, 2003. - P. 36-44 . - ISBN 978-3-540-20449-7 .  (link indisponibil)
  16. ↑ Francois-Xavier Standaert, Gilles Piret, Jean-Jacques Quisquater. Criptanalysis of Block Ciphers: A Survey  //  Seria de rapoarte tehnice UCL Crypto Group. - 2003. Arhivat la 10 februarie 2014.