înregistrare Logare
Puncte:1
Ahmed avatar Crypto

De ce nu este posibil să atacăm un AES prin crearea unei funcții pentru a modela substituția care are loc într-o cutie s?

drapel ru
Ahmed

Îmi dau seama că casetele s sunt capabile să facă transformările făcute în AES neliniare. Cu toate acestea, nu sunt sigur cum acest lucru face AES sigur. De exemplu, dacă nu avem caseta s, atunci este posibil să calculăm cheia dintr-un set de ecuații liniare:

$C^1=Ax+k$

$C^2=AC^1+k$

...

$y=AC^n+k$

Unde A este transformarea liniară, k este cheia, C ca texte cifrate intermediare, n ca număr de runde de criptare, x ca intrare și y ca rezultat final.Totuși, dacă adăugăm o casetă S, atunci nu ar fi posibil să reprezentăm substituția pe care o efectuează în funcție de x, f(x), astfel încât acum avem:

$C^1=Af(x)+k$

$C^2=Af(C^1)+k$

...

$y=Af(C^n)+k$

Care pentru mine pare să cadă, de asemenea, pradă eliminării gaussiene (prin înlocuirea fiecărei ecuații în funcția următoarei), deși o astfel de funcție pentru substituția care apare în casetele s poate fi extrem de complicat de derivat. Dacă ni se oferă câteva valori x care sunt supuse criptării utilizând aceeași cheie și că casetele s sunt cunoscute public, ar trebui să putem calcula cheia. Îmi dau seama că, în realitate, acest lucru nu se poate întâmpla, altfel AES nu ar fi folosit deloc, așa că aș fi foarte recunoscător pentru orice ajutor în identificarea unde am greșit/cum ar interveni casetele S pentru a preveni apariția unei astfel de metode :)

112
1 + 4
aes
kelalaka avatar
drapel in
kelalaka
Trebuie să te confrunți cu monomii de gradul 128 (în medie 127) și cu un număr mare de monomii. Courtois a pretins că a spart AES (însemnând că complexitatea este mai mică de căutare pe 128 de biți), dar asta a fost foarte speculativ. Aceasta are deja numele de rezolvare SAT. Consultați [Cartea lui Bard pentru mostre](https://www.amazon.com/Algebraic-Cryptanalysis-Gregory-Bard-ebook/dp/B00FB36BZO/).
2
Răspunde
Fractalice avatar
drapel in
Fractalice
Rezolvarea @kelalaka SAT este doar o metodă de a rezolva astfel de sisteme. Ceea ce sugerează Ahmed este pur și simplu liniarizarea (care este o componentă de bază a metodelor mai avansate bazate pe baza Gröbner, liniarizarea eXtended, ElimLin etc.).
1
Răspunde
kelalaka avatar
drapel in
kelalaka
@Fractalice Am folosit SAT ca termen mare (văd acum că folosirea rezolvării SAT provoacă o direcție greșită). GB, XL, XLS, RL, EL sunt toate mijloacele de a rezolva problema noastră SAT, în special în Criptografie. Bard le acoperă deja pe majoritatea în cartea lor. Răspunsul la acest Q este doar câteva lucrări
0
Răspunde
kelalaka avatar
drapel in
kelalaka
În 2003, Murphy și Robshaw au descoperit o descriere alternativă a AES, înglobând-o într-un cifr mai mare numit „BES”, folosind operații foarte simple pe un singur câmp, GF(28). Un atac XSL produce un set mai simplu de ecuații care ar rupe AES cu ~2^100 comp., dacă Courtois et. toata analiza este corecta. În 2005 Cid. et al au dat dovadă că, în forma sa propusă, algoritmul XSL nu oferă o metodă eficientă de rezolvare a sistemului de ecuații AES; cu toate acestea, Courtois a contestat concluziile lor. La FSE 2007, Chu-Wee Lim și Khoongming Khoo au arătat că nu poate funcționa așa cum a fost prezentat
3
Răspunde
Puncte:2
Fractalice avatar Crypto
drapel in
Fractalice

Daca am inteles bine, sugerezi sa tratezi valorile intermediare $C^i$ ca variabile.

Problema este că $f(C^i)$ este neliniar și conține mai multe monomii decât cele 128 de variabile (deoarece neliniaritatea provine din caseta S, numărul de monomii este de cel mult 256$\time16$). Prin urmare, nu este posibil să-l eliminați folosind ecuația $C^i = ...$, și $C^i$ nu este folosit nicăieri altundeva. Rețineți că, dacă adăugați mai multe valori de text simplu/ciphertext, variabilele $C^i$ nu sunt la fel, așa că nu puteți folosi o altă pereche pentru a elimina acele monomii suplimentare. În schimb, se adaugă mai multe variabile.

Rețineți că S-box-ul are o slăbiciune prin faptul că există pătratică ecuații (peste $GF(2)$) conectându-și intrarea și ieșirea (în loc de ecuațiile directe de gradul 7 ale cutiei S), ceea ce simplifică foarte mult sistemul. Cu toate acestea, totuși, nimeni nu a reușit să arate o modalitate de a rezolva un astfel de sistem sau un sistem similar mai rapid decât cheia bruteforce AES.

Pentru înregistrare, sursa ecuațiilor pătratice este că caseta S este echivalentă afin cu $GF(256)$ funcție inversă $y=x^{254}$. Avem $yx^2=x^{256}=x$ Așadar $yx^2-x=0$, care este pătratică peste $GF(2)$ (se împarte în 8 ecuații).

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.