"Cube" cryptanalysis?
Greg Rose
ggr at qualcomm.com
Thu Aug 21 14:08:06 EDT 2008
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 <ggr at qualcomm.com
> <mailto:ggr at qualcomm.com>> 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
> majordomo at metzdowd.com <mailto:majordomo at metzdowd.com>
>
>
>
>
> --
> 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 majordomo at metzdowd.com
More information about the cryptography
mailing list