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 …
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.
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.
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.)
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
