Re: Cube cryptanalysis?
Paul Hoffman wrote: At 11:08 AM -0700 8/21/08, Greg Rose wrote: Adi mentioned that the slides and paper will go online around the deadline for Eurocrypt submission; it will all become much clearer than my wounded explanations then. There now: http://eprint.iacr.org/2008/385 Given all the excitement over the Cube attack, readers may be interested to have a closer look at an earlier paper by Vielhaber: Breaking ONE.FIVIUM by AIDA (an Algebraic IV Differential Attack) Michael Vielhaber http://eprint.iacr.org/2007/413 Vielhaber claims that AIDA anticipates the Cube attack; see his post on the iacr eprint forum: http://eprint.iacr.org/forum/read.php?8,59 -James - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Paul Hoffman wrote: At 11:08 AM -0700 8/21/08, Greg Rose wrote: Adi mentioned that the slides and paper will go online around the deadline for Eurocrypt submission; it will all become much clearer than my wounded explanations then. There now: http://eprint.iacr.org/2008/385 Given all the excitement over the Cube attack, readers may be interested to have a closer look at an earlier paper by Vielhaber: Breaking ONE.FIVIUM by AIDA (an Algebraic IV Differential Attack) Michael Vielhaber http://eprint.iacr.org/2007/413 Vielhaber claims that AIDA anticipates the Cube attack; see his post on the iacr eprint forum: http://eprint.iacr.org/forum/read.php?8,59 -James - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Paul Hoffman wrote: At 11:08 AM -0700 8/21/08, Greg Rose wrote: Adi mentioned that the slides and paper will go online around the deadline for Eurocrypt submission; it will all become much clearer than my wounded explanations then. There now: http://eprint.iacr.org/2008/385 I just noticed the following comment from Michael Vielhaber on the iacr eprint discussion forum: http://eprint.iacr.org/forum/read.php?8,59 Vielhaber states that the cube attack is anticipated by his 2007 paper: Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack Michael Vielhaber http://eprint.iacr.org/2007/413 -James - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
At 11:08 AM -0700 8/21/08, Greg Rose wrote: Adi mentioned that the slides and paper will go online around the deadline for Eurocrypt submission; it will all become much clearer than my wounded explanations then. There now: http://eprint.iacr.org/2008/385 --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Steve Bellovin writes: Greg, assorted folks noted, way back when, that Skipjack looked a lot like a stream cipher. Might it be vulnerable? I'm still absorbing Adi's new ideas, and I haven't looked at this in any detail, so anything I say should be taken with an enormous grain of salt. But, off-hand, I'd guess not. I don't see anything that immediately makes me worried about Skipjack, or AES for that matter. In its most basic form, Adi Shamir's cube attack applies when some bit of the output of the stream cipher (or block cipher, etc.) can be written as a polynomial of the key and input such that the degree of the polynomial is not too large. One major innovation is that the attack applies even if the number of terms in the polynomial is enormous -- say, way too many to explicitly write down the polynomial. When the degree is not too large, Adi showed some powerful techniques for recovering the key. Adi pointed out that this might be especially relevant to many LFSR-based stream ciphers. The reason is that many LFSR-based stream cipher use a non-linear filter function of low degree. Often, the key loading process also has relatively low degree. The LFSR itself is linear and hence does not increase the degree. The attack only seems directly relevant to a subset of stream cipher architectures -- for instance, Adi mentioned that he does not know how to apply it to some clock-controlled LFSR-based stream ciphers, such as A5/1 -- but the class of stream ciphers it applies to is an important and common class of stream ciphers. In contrast, I don't expect this to threaten most modern block ciphers. Most block ciphers contain enough rounds, and enough non-algebraic structure in each round, to ensure that the degree of the resulting polynomial will be large, so in those cases the attack does not seem applicable. But of course I could well be missing something, and it's always possible there could be further advances. It's a brilliant piece of research. If you weren't at CRYPTO, you missed an outstanding talk (and this wasn't the only one!). - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
David Wagner wrote: It's a brilliant piece of research. If you weren't at CRYPTO, you missed an outstanding talk (and this wasn't the only one!). Yes, the program chair and committee did a great job. Whatsisname? Oh, yeah, David Wagner. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Yes, of course Adi is correct, but I blame you for reading what I wrote and not what I meant... :-) Adi mentioned that the slides and paper will go online around the deadline for Eurocrypt submission; it will all become much clearer than my wounded explanations then. thanks and regards, Greg. (cc:ed back to the crypto list) Matt Ball wrote: Hi Greg, I don't think we've met, but I'm also at the crypto conference, and happened to be sitting next to Adi and showed him this e-mail thread. He mentioned that the following text was a little misleading: On Wed, Aug 20, 2008 at 2:40 PM, Greg Rose [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: 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. The attack does not vary only one of the non-secret bits, but rather some subset of the non-secret bits. The other non-secret bits need to stay constant. This could happen in counter mode, for example, when the nonce is fixed and only the counter field varies. I'll let Adi double-check this statement for correctness... :) Cheers, -Matt Previous message: James Muir wrote: Greg Rose wrote: Basically, any calculation with inputs and outputs can be represented as an (insanely complicated and probably intractable) set of binary multivariate polynomials. So long as the degree of the polynomials is not too large, the method allows most of the nonlinear terms to be cancelled out, even though the attacker can't possibly handle them. Then you solve a tractable system of linear equations to recover key (or state) bits. I would like to know how Dinur and Shamir's work differs from Courtois' previous work on Algebraic cryptanalysis of block ciphers. It is a refinement of Courtois' technique? Greg, do you, or someone else have some insight on this? I spent about an hour trying to come up with a short but legible explanation of the technique, and failed. Sorry about that. I can visualize it, and could probably reproduce Adi's drawings on a whiteboard, but not with typing. The following is as close as I could come. 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. Gather enough such equations, just a few more than the number of key bits will do, and solve the linear system in trivial time. Note that you had to have 2^(d-2) chosen plaintexts to sum over for each of the equations... that's where the complexity comes from. The attack is called Cube because in the case where d=4, each time you sum over all of the varying known bits, it can be visualized as the face of a cube, the corners of which are the possibilities for the 3 known inputs. Hope that helps. Note that the formula I typed from memory for the complexity was wrong... it's O(n * 2^(d-2)), if the above is correct. For anything more than this, you'll have to wait for the paper. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] -- Thanks! Matt Ball, IEEE P1619.x SISWG Chair M.V. Ball Technical Consulting, Inc. Phone: 303-469-2469, Cell: 303-717-2717 http://www.mvballtech.com http://www.linkedin.com/in/matthewvball - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Steven M. Bellovin wrote: Greg, assorted folks noted, way back when, that Skipjack looked a lot like a stream cipher. Might it be vulnerable? Hmmm, interesting. I'm getting increasingly closer to talking through my hat, but... Skipjack has an 8x8 S-box, so by definition the maximum degree of the polynomials for a trip through the S-box is 8 (but it could be lower... I don't know off the top of my head). There are 32 rounds, but each word gets hit only in every fourth round... that is, each word gets hit 8 times. So the degree from beginning to end should be 64, probably out of range. However Adi mentioned a variant where you sort of meet in the middle, where you have one set of equations to get to some particular bit in the middle from the plaintext, and you get to the same bit backwards from the output bits, and by definition the two polynomials are equal. This should halve the degree, to around 32, if I've understood correctly. With an 80 bit key the attack might be more efficient than brute force. Again from memory the complexity was O(n*2^2d+n^2), (n-bit key, d degree) for skipjack this might be about 2^70. Skipjack's nearly non-existent key schedule really helps. This might be a good project for a grad student. Enough speculation from me... but I'll try to corner Adi later and ask him some of the questions that have been burning in my mind. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
someone wrote: what about RC4, the most important stream cipher in the Internet world? So I cornered Adi for a while. Of course he'd thought of almost everything I wanted to ask. You're not the first to think of RC4 (I confess I wasn't either). No, if you try to express shuffling as a polynomial, its degree is off the planet. As for some of the other things I said: when you compound s-boxes, the degrees multiply. For some reason I can no longer explain, I thought they added. So there's good news and bad news. The good news is that my/our old designs are safe: degrees ~= 64. The bad news (if you think of it that way), Skipjack is also safe, the degree is 4096 (not 32), that is, 8^4 not 8*4. ... and I realised I forgot to mention probably the most interesting thing about the attack! It treats the cipher as a black box. You don't need to know anything about it, except access to an implementation that will accept variable keys for the precomputation phase. If it isn't vulnerable, the precomputation fails. But if it is vulnerable, you'll recover the keys even though you have no idea what the algorithm itself is. Somewhere along there you discover a distinguishing attack. Amazing. Someone else suggested Bluetooth (E0). Probably not vulnerable because the key scheduling is high degree, but neither Adi nor I can remember enough detail to be sure; the keystream generator would be vulnerable if the key-IV scheduling was simple enough. I'm not sure whether Adi's invited talk or Wang's rump session (breaking MD5, SHA-0, HAVAL, ...) is the high point of Crypto for me... I think Cube. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
James Muir wrote: Greg Rose wrote: Basically, any calculation with inputs and outputs can be represented as an (insanely complicated and probably intractable) set of binary multivariate polynomials. So long as the degree of the polynomials is not too large, the method allows most of the nonlinear terms to be cancelled out, even though the attacker can't possibly handle them. Then you solve a tractable system of linear equations to recover key (or state) bits. I would like to know how Dinur and Shamir's work differs from Courtois' previous work on Algebraic cryptanalysis of block ciphers. It is a refinement of Courtois' technique? Greg, do you, or someone else have some insight on this? I spent about an hour trying to come up with a short but legible explanation of the technique, and failed. Sorry about that. I can visualize it, and could probably reproduce Adi's drawings on a whiteboard, but not with typing. The following is as close as I could come. 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. Gather enough such equations, just a few more than the number of key bits will do, and solve the linear system in trivial time. Note that you had to have 2^(d-2) chosen plaintexts to sum over for each of the equations... that's where the complexity comes from. The attack is called Cube because in the case where d=4, each time you sum over all of the varying known bits, it can be visualized as the face of a cube, the corners of which are the possibilities for the 3 known inputs. Hope that helps. Note that the formula I typed from memory for the complexity was wrong... it's O(n * 2^(d-2)), if the above is correct. For anything more than this, you'll have to wait for the paper. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Cube cryptanalysis?
According to Bruce Schneier... http://www.schneier.com/blog/archives/2008/08/adi_shamirs_cub.html ...Adi Shamir described a new generalized cryptanalytic attack at Crypto today. Anyone have details to share? Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Perry E. Metzger wrote: According to Bruce Schneier... http://www.schneier.com/blog/archives/2008/08/adi_shamirs_cub.html ...Adi Shamir described a new generalized cryptanalytic attack at Crypto today. Anyone have details to share? Stunningly smart, and an excellent and understandable presentation. Basically, any calculation with inputs and outputs can be represented as an (insanely complicated and probably intractable) set of binary multivariate polynomials. So long as the degree of the polynomials is not too large, the method allows most of the nonlinear terms to be cancelled out, even though the attacker can't possibly handle them. Then you solve a tractable system of linear equations to recover key (or state) bits. His example was an insanely complicated theoretical LFSR-based stream cipher; recovers keys with 2^28 (from memory, I might be a little out), with 2^40 precomputation, from only about a million output bits. They are working on applying the technique to real ciphers... Trivium, which is a well-respected E*Stream cipher, is in their sights. My team's last LFSR-based cipher, SOBER-128, is I think well respected and fairly conservative. I can say that we are extremely lucky in the way we load the key and IV, that the degree of the polynomials piles up and is quite high; once the cipher is actually running, there are output bits which would have been attackable (degree 16 is certainly tractable), except for lucky use of addition as well as s-boxes... the addition carries represent high degree terms. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Greg Rose [EMAIL PROTECTED] writes: His example was an insanely complicated theoretical LFSR-based stream cipher; recovers keys with 2^28 (from memory, I might be a little out), with 2^40 precomputation, from only about a million output bits. They are working on applying the technique to real ciphers... Trivium, which is a well-respected E*Stream cipher, is in their sights. My team's last LFSR-based cipher, SOBER-128, is I think well respected and fairly conservative. I can say that we are extremely lucky in the way we load the key and IV, that the degree of the polynomials piles up and is quite high; once the cipher is actually running, there are output bits which would have been attackable (degree 16 is certainly tractable), except for lucky use of addition as well as s-boxes... the addition carries represent high degree terms. There are a bunch of deployed mobile phone ciphers that are in the stream cipher class -- any thoughts on whether any of them look vulnerable? Perry -- Perry E. Metzger[EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Perry E. Metzger wrote: Greg Rose [EMAIL PROTECTED] writes: His example was an insanely complicated theoretical LFSR-based stream cipher; recovers keys with 2^28 (from memory, I might be a little out), with 2^40 precomputation, from only about a million output bits. They are working on applying the technique to real ciphers... Trivium, which is a well-respected E*Stream cipher, is in their sights. My team's last LFSR-based cipher, SOBER-128, is I think well respected and fairly conservative. I can say that we are extremely lucky in the way we load the key and IV, that the degree of the polynomials piles up and is quite high; once the cipher is actually running, there are output bits which would have been attackable (degree 16 is certainly tractable), except for lucky use of addition as well as s-boxes... the addition carries represent high degree terms. There are a bunch of deployed mobile phone ciphers that are in the stream cipher class -- any thoughts on whether any of them look vulnerable? With the disclaimer that I think I understand the attack but might nevertheless have misunderstood something: A5/1 is difficult for this attack to apply to because of the clock-controlled shift registers (Adi said this). A5/3 and the current WCDMA f8/f9 is based on Kasumi, and I'd be surprised if the attack applys. Ditto for the AES based CDMA security. The soon-to-be-adopted spare WCDMA algorithm, SNOW-3G, may be vulnerable if used in other ways, but appears to me to be secure in the way it is used in 3G phones. Again, somewhat lucky though, the attack comes very close to working. I believe the appropriate standards committee is going to go off and check this very closely (I spoke to one of the members). Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Greg, assorted folks noted, way back when, that Skipjack looked a lot like a stream cipher. Might it be vulnerable? --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
