Courtois: nowe ataki na KeeLoq

Nicolas Tadeusz Courtois i Gregory V. Bard opublikowali nowe ataki na algorytm KeeLoq, popularny szyfr wykorzystywany do zdalnego otwierania drzwi i rozbrajania alarmu m.in. w samochodach marki Jaguar.

Algorytm jest szyfrem blokowym z 32-bitowymi blokami i 64-bitowym kluczem, ze względu na małe wymagania pamięciowe stosowanym w radiowych "kluczach" do uruchamiania droższych samochodów (używają go m.in. Chrysler i Jaguar). Badacze wybrali go ponieważ ze względu na prostą konstrukcję i niewielką liczbę rund stanowi dobry obiekt do ćwiczeń nad kryptoanalizą algebraiczną. Opracowany przez Courtois i Barda atak umożliwia odzyskanie pełnego klucza w 2^48 cykli procesora.

Autorzy oceniają atak jako praktyczny. Jest on 2^11 szybszy niż wyczerpujące przeszukiwanie przestrzeni kluczy ("exhaustive search") i wymaga 2^15 par tekstu jawnego i odpowiadających im kryptogramów. Algorytm KeeLoq jest obecnie łamany przez złodziei samochodowych z wykorzystaniem błędów w implementacji algorytmu (prosta inkrementacja IV) lub specjalizowanych, zbudowanych na FPGA procesorów, które są w stanie złamać klucz w ciągu około dwóch tygodni (nowy atak może jeszcze bardziej przyspieszyć ten wynik).

• Nicolas T. Courtois, Gregory V. Bard "Algebraic and Slide Attacks on KeeLoq" (.)