# Crypto guru thinks outside the box with Cube attack

Senior cryptologist Adi Shamir is developing a new attack for rooting out potential weaknesses in encryption ciphers, dubbed the Cube Attack. Shamir, the S in RSA, explained at a talk at the Crypto2008 conference earlier this month that the attack methodology would succeed against cypher schemes providing that they can be …

#### what are the odds...

that he will be arrested for "revealing flaws in security measures" or under 'terrist' laws? even his name sounds dodgy...

the orange coat with all the pretty arrows, thanks

#### Riiight

So Shamir has a method of breaking low-order polynomial cyphers which "unfortunately this margin is too small to contain"?

Mine's the one with a statement of Fermat's Last Theorem on the back.

#### A5.1 has already been analysed...

There has been published work looking at algebraic attacks against A5.1 (the GSM cipher for most people). Look at: http://www.springerlink.com/content/eu97gk8786h7tj25/ and obtain this paper for full details.

Essentially, A5.1 and other similar ciphers are immune to algebraic attacks because the irregular clocking introduces many non-linear terms, and the order of the terms grows very quickly.

There was work published 2-3 years ago on this also: so this is not really new.

#### Secondary school maths.

Take a polynomial cypher, which for encoding each byte does the following:

f(Xn) = Xn + an^2 + bn + c

where a,b,c make up your key, and Xn is byte n in the source, f(Xn) is the encrypting function.

Now, lets say we know the the source data is likely to contain the string "hello".

So we take every possible sequence of 5 bytes from the encoded data we are trying to brute force and subtract "hello" from them, then we take the difference of the difference between each of the 5 bytes, lets say after subtracting 'hello' we have:

1-2-4-7-11

-1-2-3-4-

--1-1-1--

If the numbers are all the same we have a possible key, and it's trivial to work out a,b,c, decrypt a block of data and see if we got the key right.

In the example: a=1/2, b= 1/2, c=1 if 'h' was the 0th byte (X0).

Basically given you know a likely string of length n, then you can come up with possibly keys for a polynomial in n-1 every 256 bytes, or possible keys for polynomials in n-2 every 65536 bytes.

Note: truncating to between -128 and 127 doesn't make it any harder, the difference of the difference is still going to be correct in 2s complement even if we wrap around multiple times.

Apologies for trying to do mathematics without symbols.

I'd be very very surprised if this is anything new.

#### Let me be the first to say...

"Well, obviously."

Mine's the one with Schaum's outline of high-school algebra printed on the arms.

#### Actual explanation of the attach

If anyone is interested in an actual explanation of the attack, rather than the half-assed speculation that (per usual) we're getting from most of the commentators here, there was a fairly informative thread on sci.crypt not long ago.

See in particular:

http://groups.google.com/group/sci.crypt/msg/9dd2a8224203caeb

(Greg Rose's informal description of the underlying principle)

http://groups.google.com/group/sci.crypt/msg/7065f9a4289581f1

(David Wagner's short explanation of the basics of the attack)

Basically, as I understand it from Wagner's description, the Cube attack uses appropriate plaintext/ciphertext pairs to extract a set of linear functions of the key bits. Once you have enough of them, you can solve for the key bits just as you would with any system of N independent linear equations of N unknowns. (Wagner says that much of the actual Cube attack consists of clever ways of performing these operations.)

Incidentally, as you can see in Wagner's description, for this sort of thing we typically talk about polynomials in GF(2), where there aren't any exponents. A boolean variable times itself equals itself, so (positive integer) exponents are no-ops in GF(2). References here to "higher degree" and "lower degree" refer not to polynomial terms with exponents (as in the little example at the end of the article) but to terms that are products of different variables: x*y*z rather than x**3.

(That doesn't mean the Cube attack only applies to polynomials in GF(2) - just that that's how most of the discussion will probably be framed.)