En av de mest uppmärksammade händelserna på den för ungefär en månad sedan avslutade Crypto-konferensen var en presentation av Adi Shamir om en ny typ av attackmetod mot kryptografiska metoder kallad kubattack.
Adi Shamir
När metoden presenterades fanns inget om den nya metoden publicerat. Detta ledde till en hel del diskussioner och spekulationer på maillistor. Exempelvis diskuterades det mycket om krypton som AES, Twofish är sårbara.
David Wagner skrev ett par längre inlägg på Cryptography-listan (inlägg ett, inlägg två). David skrev bland annat:
Basically the method focuses on terms of the polynomial in which only one secret bit of the key appears, and many of the non-secret bits. Using chosen (or lucky) plaintexts, vary all but one of the non-secret bits, and sum the output bits (mod 2, that is, XOR).
Fix the other non-secret bit to 1. Now all the terms that involve less than the full complement of non-secret bits will appear an even number of times in the sum, and because it is mod 2, they will all cancel out! The only terms that will be left are the ones with one secret bit, and all ones for the non-secret bits… but that is linear in the secret bit! So what you are left with is a simple, linear, polynomial relating unknown (key) bits.
Nu har artikeln Cube Attacks on Tweakable Black Box Polynomials av Itai Dinur and Adi Shamir publicerats på IACR. Författarna skriver i artikelns (långa) sammanfattning:
Almost any cryptographic scheme can be described by tweakable polynomials over GF (2), which contain both secret variables (e.g., key bits) and public variables (e.g., plaintext bits or IV bits). The cryptanalyst is allowed to tweak the polynomials by choosing arbitrary values for the public variables, and his goal is to solve the resultant system of polynomial equations in terms of their common secret variables.
In this paper we develop a new technique (called a cube attack) for solving such tweakable polynomials, which is a major improvement over several previously published attacks of the same type.
For example, on the stream cipher Trivium with a reduced number of initialization rounds, the best previous attack (due to Fischer, Khazaei, and Meier) requires a barely practical complexity of 2**55 to attack 672 initialization rounds, whereas a cube attack can find the complete key of the same variant in 2**19 bit operations (which take less than a second on a single PC). Trivium with 735 initialization rounds (which could not be attacked by any previous technique) can now be broken with 2**30 bit operations, and by extrapolating our experimentally verified complexities for various sizes, we have reasons to believe that cube attacks will remain faster than exhaustive search even for 1024 initialization rounds.
Whereas previous attacks were heuristic, had to be adapted to each cryptosystem, had no general complexity bounds, and were not expected to succeed on random looking polynomials, cube attacks are provably successful when applied to random polynomials of degree d over n secret variables whenever the number m of public variables exceeds d + logd n. Their complexity is 2d−1 n + n2 bit operations,
which is polynomial in n and amazingly low when d is small.
Cube attacks can be applied to any block cipher, stream cipher, or MAC which is provided as a black box (even when nothing is known about its internal structure) as long as at least one output bit can be represented by (an unknown) polynomial of relatively low degree in the secret and public variables. In particular, they can be easily and automatically combined with any type of side channel attack that leaks some partial information about the early stages of the encryption process (which can typically be
represented by a very low degree polynomial), such as the Hamming weight of a byte written into a register.
Publiceringen av artikeln har skapat nya diskussioner, exempelvis på Bruce Schneiers blog.
Min uppfattning om Adi Shamir är att han är en av världens absolut bästa kryptologer, risken att han skulle missat fullständigt och metoden inte alls fungerar tror jag är liten. Men jag kan villigt erkänna att jag kan för lite krypanalys för att göra en vettig bedömning av den nya metoden.
Om det Itai Dinur och Adi Shamir skriver stämmer borde detta vara ett stort steg framåt för kryptanalysen. Och lackmustestet kommer antagligen att vara om det dyker upp en ny våg av attacker mot olika specifika funktioner så fungerar kubattacken.
Att Trivium, en av de nyligen utsedda algoritmerna i eSTREAM-portföljen (och lite av en personlig favorit) skulle få problem så här nära efter avslutningen av eSTREAM visar hur en ny metod plötsligt kan kullkasta flera år av analysarbete.
Vi kommer med stor sannolikhet att få återkomma till den här nya attackmetoden. Inte minst under AHS-tävlingen kommer kubattacken antagligen att uppmärksammas.
