Gwarancje twardości dla AES

14

Wiele kryptosystemów z kluczem publicznym ma pewnego rodzaju sprawdzalne zabezpieczenia. Na przykład kryptosystem Rabin jest tak samo trudny jak faktoring.

Zastanawiam się, czy istnieje taki rodzaj możliwego do udowodnienia bezpieczeństwa dla kryptosystemów tajnych kluczy, takich jak AES. Jeśli nie, jakie są dowody na to, że złamanie takich kryptosystemów jest trudne? (inne niż odporność na ataki prób i błędów)

Uwaga: znam operacje AES (AddRoundKey, SubBytes, ShiftRows i MixColumns). Wydaje się, że twardość AES wynika z operacji MixColumns, która z kolei musi odziedziczyć trudność po pewnym trudnym problemie nad polami Galois (a tym samym algebrą). W rzeczywistości mogę powtórzyć moje pytanie: „Który twardy problem algebraiczny gwarantuje bezpieczeństwo AES?”

MS Dousti
źródło

Odpowiedzi:

8

MIXCOLUMNS zapobiega atakom, które koncentrują się tylko na kilku S-boxach, ponieważ mieszanie kolumn wymaga, aby wszystkie S-boxy uczestniczyły w szyfrowaniu. (Projektanci Rijndael nazwali to „strategią szerokiego szlaku”). Analiza przyczyny S-boxa jest trudna z powodu zastosowania operacji inwersji pola skończonego. Inwersja „wygładza” tabele dystrybucji wpisów S-box, dzięki czemu wpisy wydają się (prawie) jednolite, tj. Nie do odróżnienia od losowej dystrybucji bez klucza. Jest to połączenie dwóch funkcji, które sprawiają, że Rijndael jest pewnie zabezpieczony przed znanymi atakami.

Nawiasem mówiąc, książka The Design of Rijndael jest bardzo dobrą lekturą i omawia teorię i filozofię kryptografii.

Aaron Sterling
źródło
1
Dobre wytłumaczenie. Dzięki. W rzeczywistości miałem dostęp do książki, ale nie wiedziałem, którą część przeczytać (odnośnie mojego pytania). Czy sugerujesz jakiś specjalny rozdział lub sekcję?
MS Dousti,
3
Przeczytałem go ponad dwa lata temu, z biblioteki, więc nie mam przed sobą spisu treści i nie jestem pewien, czy mógłbym udzielić konkretnej odpowiedzi na twoje pytanie, z wyjątkiem tego, że podoba mi się ten sposób zaprojektowali S-boxy tak, aby były łatwe do wdrożenia. Jedną rzecz, którą mogę zasugerować, jest wyjaśnienie przez Stinsona AES i innych sieci substytucyjno-permutacyjnych w kryptografii: teoria i praktyka. To rozdział 3 wydania, który mam, i wygląda na to, że możesz pobrać książkę za darmo pod tym linkiem: ebookee.com/…
Aaron Sterling
1
Dzięki za sugestię książki Stinsona. Czy mógłbyś także przejrzeć Spis treści Projektu Rijndaela i sprawdzić, czy przypomina coś przydatnego?
MS Dousti,
2
Dzięki za link! :-) Tak, zarówno sekcja 3.6, jak i rozdział 5 były dla mnie bardzo interesujące, ponieważ omawiały „dlaczego”, a nie tylko „co”.
Aaron Sterling
10

Jak powiedział David, nie mamy takich obniżek dla AES. Nie oznacza to jednak, że kryptosystem Rabin lub RSA są bezpieczniejsze niż AES. W rzeczywistości, ufam (przynajmniej w jedną stronę, prawdopodobnie również pseudolosową) bezpieczeństwu szyfrów blokowych, takich jak AES / DES itp. (Być może z nieco większą liczbą rund niż standardowo używane), bardziej niż założeniem, że faktoring jest trudne, właśnie dlatego, że nie ma struktury algebraicznej, dlatego trudniej jest wyobrazić sobie jakiś algorytm przełomowy.

Szyfry blokowe można konstruować bezpośrednio z funkcji jednokierunkowych, co jest minimalnym założeniem dla większości crpyotgraphy, ale wynikowa konstrukcja będzie strasznie nieefektywna i dlatego nie będzie używana.

Boaz Barak
źródło
Dzięki Boaz. Myślę, że konstrukt Luby-Rackoffa zapewnia taką rzekomą pseudolosowość opartą na strukturach podobnych do DES, prawda?
MS Dousti,
3
tak. Dokładniej, zaczynasz od funkcji jednokierunkowej, przekształcasz ją w generator pseudolosowy za pomocą Hastada, Impagliazzo, Luby, Levin, a następnie przekształcasz w funkcję pseudolosową za pomocą Goldreicha, Goldwassera, Micali, a następnie faktycznie używasz Luby-Rackoff przekonwertuj go na pseudolosowa permutacja (tj. blok ci pher)
Boaz Barak
6

Ponieważ w ogólny sposób można przekonwertować dowolny schemat szyfrowania klucza publicznego na schemat tajnego klucza, można uzyskać schematy tajnego klucza z podobnymi możliwymi do udowodnienia gwarancjami bezpieczeństwa.

Ale ta odpowiedź jest pedantyczna: dla typowego wdrożonego blockciphera nie mamy możliwej do udowodnienia analizy bezpieczeństwa w sensie redukcji do problemu obliczeniowego. Pojawiły się propozycje blokentów z redukcjami bezpieczeństwa, ale bagaż obliczeniowy potrzebny do ułatwienia redukcji czyni je niekonkurencyjnymi dzięki bardziej wydajnym schematom, takim jak algorytmy AES.

Co ciekawe, społeczność bezpieczeństwa, którą można udowodnić, ogólnie zgodziła się, że zasadne jest przyjęcie bezpieczeństwa blokującego (pseudolosowa permutacja) jako założenia, a następnie zredukowanie go do analizy przy protokołach wyższego poziomu, które wykorzystują blokujący blok jako składnik. Oznacza to, że w przeciwieństwie do niektórych innych wyzwań związanych z bezpiecznym projektowaniem protokołu, wystarczające jest zaufanie do intuicji kryptoanalityków, jeśli chodzi o bezpieczeństwo, jeśli chodzi o blokanty.

David Cash
źródło