Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Ännu en attack på RC4 » Kryptoblog

Ännu en attack på RC4

January 18th, 2008 by Joachim Strömbergson Leave a reply »

IACR dök det nyligen upp ännu en artikel med en attack på RC4. Jag trodde först att detta var en av artiklarna som kommer att presenteras på FSE 2008, men det är det inte, istället verkar det vara en artikel för EUROCYPT 2008 senare i år.

Artikeln New State Recovering Attack on RC4 av Alexander Maximov and Dmitry Khovratovich beskriver en metod som utifrån en kodsekvens genererad av RC4 kan ta fram det interna tillståndet och därmed nyckeln. Den nya metoden är snabbare än en uttömmande sökning. Författarna skriver:


The stream cipher RC4 was designed by R.~Rivest in 1987, and it has a very simple and elegant structure. It is probably the most deployed cipher on the Earth.

In this paper we analyse the class RC4-$N$ of RC4-like stream ciphers, where $N$ is the modulus of operations, as well as the length of internal arrays.

Our new attack is a state recovering attack which accepts the keystream of a certain length, and recovers the internal state. For the original RC4-256, our attack has the total complexity around $2{241}$ of operations, whereas the best previous attack needs $2{779}$ of time.

Moreover, we show that if the secret key is of length $N$ bits or longer, the new attack works faster than an exhaustive search. The algorithm of the attack was implemented and verified on small cases.

Det börjar bli förvirrande många attacker på RC4. Det skulle vara intressant att se en artikel som på ett bra sätt sammanställer alla olika attacker och visar relationen mellan attackerna samt vad man skulle kunna göra om man kombinerade attackerna.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

2 comments

  1. Simon says:

    Men 2^241 är ju fortfarande en enorm kraftansträngning som inga datorer klarar av, dom verkar dock antyda att denna attack kanske går att förbättra.

    Men RC4 börjar bli gammal och sliten, bättre att köra AES i CTR mode.

  2. Joachim says:

    Aloha!

    Simon: Helt sant. Den här attacken är inte speciellt bra, Klein och FMS är i jämförelse mycket effektivare. Det intressanta är dock att det är ännu ett sätt att attackera RC4.

    Det är därför jag är nyfiken på vad man skulle göra om man kunde kombinera alla attacker: Varje metod ger sitt bidrag (info om interna tillståndet etc) och den kombinerade attacke blir än mer effektiv.

Leave a Reply

You must be logged in to post a comment.