Zautomatyzowany model dla różnicowo meet-in-the-middle ataków na szyfry AndRX

Dlaczego to badanie ma znaczenie

Za każdym razem, gdy używamy smartfona, płacimy online lub łączymy się z urządzeniem medycznym, nasze dane chronią małe cyfrowe zamki zwane szyframi blokowymi. Eksperci od bezpieczeństwa nieustannie próbują łamać te zamki, by projektować bezpieczniejsze rozwiązania. Artykuł przedstawia nowy sposób automatyzacji potężnego typu ataku na popularną rodzinę lekkich szyfrów, pomagając badaczom sprawdzić, jak naprawdę silne są te cyfrowe zamki.

Jak działa współczesne łamanie kodów

Współczesne szyfry blokowe mieszają dane w wielu małych krokach, czyli rundach, kontrolowanych przez tajny klucz. Aby ocenić bezpieczeństwo szyfru, kryptanoliza poszukuje wzorców, które nie powinny występować, gdy system zachowywałby się jak czysty przypadkowy proces. Dwa klasyczne narzędzia to kryptanaliza różnicowa, śledząca jak drobne zmiany na wejściu przechodzą na wyjście, oraz ataki meet-in-the-middle, które obliczają od obu końców szyfru i szukają zgodności w środku. Każde z tych podejść ma ograniczenia, ale ich połączenie tworzy dokładniejszą sondę struktury szyfru.

Połączenie dwóch pomysłów atakujących

Badanie koncentruje się na hybrydowej technice zwanej różnicowo meet-in-the-middle. Szyfr dzieli się tutaj na trzy części: sekcję wejściową, środkową i wyjściową. W środkowej części atakujący poszukuje „różnicowego wyróżnika” — wzorca różnic wejścia i wyjścia, który występuje częściej niż przypadek na kilku rundach. Wokół tego rdzenia atakujący częściowo szyfruje od początku i częściowo odszyfrowuje od końca, zgadując tylko wybrane fragmenty klucza. Gdy obie kierunki spotykają się w tym samym stanie wewnętrznym, zgadywane wartości są bardziej prawdopodobne jako prawdziwy klucz, co zawęża przestrzeń przeszukiwań.

Przekształcenie ręcznego rzemiosła w narzędzie automatyczne

Ręczne projektowanie takich połączonych ataków jest niezwykle trudne, zwłaszcza dla szyfrów bitowo zorientowanych, których stan wewnętrzny może mieć 64, 96 lub 128 bitów. Autorzy stworzyli zautomatyzowane ramy wykorzystujące programowanie ograniczeń — metodę opisywania złożonych warunków logicznych tak, aby solver mógł przeszukać wszystkie poprawne możliwości. Najpierw kodują sposób, w jaki różnice przechodzą przez podstawowe cegiełki szyfru oparte na operacjach AND, rotacji i XOR, czyli rodzinę projektów AndRX. Następnie modelują, które bity klucza wpływają na każdy etap i ile tych bitów trzeba faktycznie zgadnąć. Solver przeszukuje wiele sposobów podziału szyfru na sekcje wejściową, środkową i wyjściową, wybierając układ minimalizujący całkowity wysiłek ataku.

Dodatkowe sztuczki by zredukować przestrzeń klucza

Ponad bazowy model ramy dodają dwa triki optymalizacyjne dostosowane do szyfrów stylu Feistela z rodziny AndRX, takich jak SIMON i Simeck. Pierwszy, zwany ideą równoważnych podkluczy, matematycznie przesuwa części kluczy rundowych do przodu lub do tyłu tak, że kilka różnych bitów klucza zachowuje się, jakby były takie same. To zmniejsza liczbę niezależnych bitów, które atakujący musi rozważać. Drugi, selektywne zgadywanie bitów klucza, bada jak nieliniowa operacja AND wykorzystuje swoje wejścia i pokazuje, że w określonych warunkach jeden zgadnięty bit może zastąpić dwa. Autorzy opisują także, choć jeszcze nie w pełni zautomatyzowali, dwa dalsze ulepszenia: partycjonowanie równoległe, które może dodać dodatkową rundę ataku bez zwiększenia czasu, oraz trik redukcji danych, który zmniejsza liczbę potrzebnych wybranych wiadomości.

Co narzędzie ujawnia o rzeczywistych szyfrach

Aby przetestować podejście, badacze zastosowali swój zautomatyzowany model do wszystkich standardowych wariantów lekkich szyfrów SIMON i Simeck, które są kandydatami do stosowania w urządzeniach ograniczonych, takich jak sensory i kontrolery wbudowane. Dla każdej wersji narzędzie znajduje różnicowo meet-in-the-middle atak i szacuje jego koszty dotyczące danych, czasu i pamięci. W wielu przypadkach ataki te obejmują więcej rund niż wcześniejsze meet-in-the-middle lub związane techniki, a często także przewyższają wcześniejsze ataki oparte na niemożliwych różnicach czy zerowej korelacji pod względem liczby objętych rund. Na przykład narzędzie daje ataki obejmujące do 51 rund 128-bitowej wersji SIMON z 256-bitowym kluczem, wydłużając zasięg wcześniejszych metod przy jednoczesnym utrzymaniu pracy poniżej przeszukiwania wyczerpującego wszystkich kluczy.

Szerszy obraz dla przyszłej kryptografii

Dla osób niebędących specjalistami kluczowy przekaz nie jest taki, że SIMON czy Simeck są „złamane” w praktycznych zastosowaniach, lecz że zautomatyzowane narzędzia stają się wystarczająco potężne, by odkrywać subtelne słabości, które trudno byłoby znaleźć ręcznie. Przedstawione ramy są ogólne na poziomie bitowym i w zasadzie można je zaadaptować do innych rodzin szyfrów. Pomagając projektantom szybko sprawdzać, jak nowe algorytmy radzą sobie wobec zaawansowanych ataków łączonych, takie narzędzia wspierają długoterminowy cel budowania szyfrowania, które pozostanie odporne w miarę rozwoju technik analizy.

Cytowanie: Chakraborty, D., Sahoo, S., Nguyen, P.H. et al. An automated model for differential meet in the middle attacks on AndRX ciphers. Sci Rep 16, 14773 (2026). https://doi.org/10.1038/s41598-026-41390-w

Słowa kluczowe: kryptanaliza szyfrów blokowych, różnicowo meet-in-the-middle, szyfr SIMON, szyfr Simeck, programowanie ograniczeń