eSTREAM-projektet presenterade sin portfölj med strömkrypton i april i år. Portföljen som då presenterades inkluderade fyra krypton i profil ett avsedda i första hand för SW-implementation och fyra krypton i profil två avsedda för inbyggda system och hårdvaruimplementationer. Dessa krypton var:

Profil ett:

• HC-128


• Rabbit


• Salsa 20/12


• Sosemanuk

Profil två:

• F-FCSR-H v2


• Grain v1


• Mickey v2


• Trivium

Sedan april har det hänt en del. Det mest direkta är att eSTREAM-portföljen har uppdaterats med den stora förändringen att F-FCSR-H plockats bort från profil två.

Skälet till detta är att Hell och Johansson skrivit en artikel kallad Breaking the F-FCSR-H stream cipher som tydligen visar en praktiskt genomförbar artikel mot F-FCSR-H. Artikeln skall presenteras på Asiacrypt i december, men tydligen stämmer resultatet då eSTREAM valt att plocka bort F-FCSR-H.

Några andra eSTREAM-krypton som inte ser ut att må speciellt bra är Trivium och Salsa 20, speciellt Trivium ser ut att må dåligt.

I höstas kom Adi Shamirs kubattack som i artikeln innehåller en allvarlig attack mot Trivium. Under hösten har även kommit ett par andra attacker mot Trivium.

I oktober kom artikeln Transforming chosen IV attack into a key differential attack: how to break TRIVIUM and similar designs med en komplexitet på 2**68.

En annan artikel, Slid Pairs in Salsa20 and Trivium, som attackerar både Trivium och Salsa 20 kom i slutet av september. Författarna Deike Priemuth-Schmid och Alex Biryukov skriver:

The stream ciphers Salsa20 and Trivium are two of the finalists of the eSTREAM project which are in the final portfolio of new promising stream ciphers. In this paper we show that initialization and key-stream generation of these ciphers is slidable, i.e. one can find distinct (Key, IV) pairs that produce identical (or closely related) key-streams.

There are 2**256 and more then 2**39 such pairs in Salsa20 and Trivium respectively. We write out and solve the non-linear equations which describe such related (Key, IV) pairs. This allows us to sample the space of such related pairs efficiently as well as detect such pairs in large portions of key-stream very efficiently.

We show that Salsa20 does not have 256-bit security if one considers general birthday and related key distinguishing and key-recovery attacks

Det ser allvarligt ut, men läser man Daniel J Bernsteins svar verkar det inte vara en attack som är bättre än brute force:

These claims are entirely without merit. The “attacks” on Salsa20 are vastly more expensive than the standard brute-force attacks discussed in the original Salsa20 documentation.

Vad gäller Trivium, med tre olika attacker på kort tid, skulle jag inte bli förvånad om den åker ut ur eSTREAM-portföljen och jag skulle vara försiktg att använda den.

Det som gör mig en aning bekymrad är att flera attacker alltså dykt upp strax efter att eSTREAM-projektet avslutats och porföljen presenterats – efter fyra år av utvärderingar.

Om man vore lite konspiratoriskt lagd skulle man kunna få för sig att det är mer prestige och publiceringsvärde i att attackera accepterade och utvalda algoritmer snarare än kandidater. Detta är naturligtvis rent trams, men om det skulle vara så vore det bekymmersamt för forskningen och andra försök att ta fram bra algoritmer – exempelvis för NISTs SHA-3-tävling.

En sista sak om eSTREAM värd att notera är att kryptot Rabbit, enligt en postning av Erik Zenner på eSTREAM-forumet, har fått ändrad licens:

On behalf of Cryptico A/S, the company who designed the Rabbit stream cipher, I’m happy to relay the following:

“Rabbit has been released into the public domain and may be used freely for
any purpose.”

So in retrospect, I think that it was a good decision not to make patent issues a key criterion for the eStream portfolio: The patent status can change, the algorithmic properties can’t.

Tyvärr är inte detta det mest officiella av uttalanden, och dessutom saknar jag information om hur Cryptico avser att agera vad gäller sina patent relaterade till Rabbit. Jag har letat på Cryptico A/S webbplats för att hitta ett mer officiellt uttalande, men där finns inte mycket nyheter.

Jag har kontaktat Erik Zenner för att se om det går att få ett mer officiellt uttalande. Hör jag något publicerar jag det här. eSTREAM-projektets text om licensen för Rabbit har i alla fall inte uppdaterats:

Cryptico A/S currently has patents pending on Rabbit. The algorithm is provided royalty-free for non-commectical use. Licenses for commercial use may be obtained from Cryptico A/S.

Om jag själv skall välja krypton från eSTREAM skulle jag i första hand gå på HC-128 och kanske Salsa 20. I profil två skulle jag välja Grain och Mickey, men då använda versionerna med 128 bit nycklar som inte kostar mer i implementation (bortsett från sex Bytes längre nyckel). Inbyggda system förtjänar lika bra skydd som PC-system.

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.