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]
