"Cube" cryptanalysis?

[Greg Rose]

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