Gwarancje twardości dla AES

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?”

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.

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.

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.