2's compliment September 14, 2008 8:23 PM

chirp chirp chirp chirp — (sound of crickets chirping)

Thanks for the link, from the 3 of us with the mathematical maturity to get through the paper.

Your readers need a Doghouse to flame or a security theater to lambast — not a research paper that will encourage their own independent thinking.

Wow, that comment was kind of mean. I have to admit that I don’t understand the math well enough to get through the paper but….damn. That’s a mighty high opinion you’ve got of yourself. I guess I should just go back to smoking my weed and stop reading big boy blogs.

(High five for Kevin)

Carlo Graziani September 14, 2008 9:32 PM

“Almost any cryptographic scheme can be described by tweakable polynomials…”

I don’t doubt that this is true. But could someone educate me as to why this is true? That is, why are cryptograpic schemes based on non-polynomial functions uncommon?

Thanks for the paper. I was almost stopped at “Since x_i^2 = x_i modulo 2, the terms t_I in the polynomial can be indexed by the subset I = {1 … n } of the variables which are multiplied together, and polynomials can be represented by sums of t_I’s for all the subsets I in some collection C.”, but thankfully it became clearer with the examples in the next section.

David Wagner’s summary (that you linked to earlier) would probably have sufficed for my limited maths, of course 🙂

@Carlo

These “polynomials in GF(2)” are really just bits in binary logic: x * y = x AND y; x + y = x XOR y; x + 1 = NOT x.

So anything you can do with a collection of logic gates can be represented as a polynomial function in GF(2). (Possibly a very, very large one, but anyway…)

(polite and discreet cough) mmm, don’t you mean “2’s complement” ? (and even the apostrophe is an indulgence).

Have they published a version that includes more of the proofs?

“”Almost any cryptographic scheme can be described by tweakable polynomials…”

I don’t doubt that this is true. But could someone educate me as to why this is true? That is, why are cryptograpic schemes based on non-polynomial functions uncommon?”

I may be barking up the wrong tree but here is a possible explanation.

Remember that any encryption scheme is just a way to pair a finite number of inputs with the same number of outputs. In this light, the statement is just saying that in most encryption schemes we can fit a polynomial of order = (#inputs-1) so that it passes through all (input, output) pairs.

Eg, say our encryption scheme is 0 –> 1, 1 –> 0. There are two pairings so we want a polynomial of degree one:

f(x) = ax + b

We plug in our desired pairings f(input) = output and solve for the coefficients a and b.

f(0) = 1 and f(1) = 0, so

a0 + b = 1 ==> b = 1
a
1 + b = 0 –> a + 1 = 0 ==> a = -1

So the polynomial:
f(input) = 1-1*input

completely matches the given encryption scheme as every input is mapped to the desired output.

To see there’s a way to do this for any pairing provided each input has a single output:
http://en.wikipedia.org/wiki/Lagrange_polynomial

~~~~~~~~~~~~~~~~~~~~~~~

Some complications:
1) Our encryption scheme doesn’t only depend on the input message, it also depends on the key. ie, we want an f(input,key) not just f(input). In practice I guess this might mean that the coefficients for the polynomial depend on the key.

For our simple example above we could have:
f(key, input) = ( (-1) ^ key ) * input + key

where key, input, and output are in {0,1}

2) The polynomial may not be over the real numbers. To do the Lagrange polynomial thing it seems you need multiplicative inverses. Hence, I would guess you can use polynomials to model any function from a field into itself. http://en.wikipedia.org/wiki/Field_(mathematics) You may not need that much or you may need more conditions – I’d have to think about it.

john doe September 15, 2008 6:29 AM

@ 2’s compliment [sic]

see sciolism/sciolist/sciolistic

first get the two’s complement right then mount that high horse of yours

Nice black box approach for those cheap rfid cards eh.

Fred the pedant September 15, 2008 10:30 AM

@ John Doe,

“2’s compliment [sic]”

It might have been an attempt at a joke…

The ‘person’ (an assumption on my part) did say,

“from the 3 of us with the mathematical maturity”

So they might have assumed Bruce was No 1, they as No 2 were “paying a complement” 😉 and the final third party well who knows…

But then again I think you have it, they are sat upon a nags back talking through the unfortunate beasts orafice (which one I will leave to the reader…)

Alex: No, the polynomials in question is not over the real numbers, but over the field of integers modulo 2. Each bit of the output is some function of the input and key bits. We know this function is a polynomial because ALL bit-valued functions of sets of bits is a polynomial over integers modulo 2. It is a multi-variable polynomial with each input bit and each key bit corresponding to a variable.

Because x*x=x in the chosen field, in general the degree of these polynomials is at most the total number of variables, i.e. (number of input bits)+(number of key bits). The attack applies if, by some weakness in the cryptographic structure, the degree for of the polynomial corresponding to one of the output bits just happens to be appreciably lower than (number of key bits).

Fred P September 15, 2008 1:53 PM

Very neat attack.

While reading it, I was wondering if it would be possible to extend this attack via recursion into smaller cubes. I don’t think that this is a useful extension, though, as my brief examination suggests that it seems that you need more information than you are guaranteed to have to do this effectively.

Some Kinda Nazi September 15, 2008 5:36 PM

@2’s compliment

“Posted by: 2’s complement at September 14, 2008 8:23 PM”

There, fixed that for you, Mr. Mathematical Background. Jerk.

Ishmael September 16, 2008 8:23 AM

Chuckle, when I see one of these papers come across, I am reminded of Bruce’s comment that he was one of the three or five people worldwide competent to evaluate a new crypto algorithm.

So I will print the paper and, with it in hand, make some hapless mathematician’s life a burden to him/her by demanding a translation of the “good parts” at every opportunity.

This practice has some unanticipated side benefits — sometimes I will go for weeks without even the sight of a mathematician and can clear the crowd from in front of the coffeemaker by waving any sheaf of paper with an excited “Hey, I’ve been looking for you …” 🙂

— Ishmael

Maybe it was spelled correctly in the first place. As in, “Hey, 2, lookin’ good today! Been workin’ out?” 😉

Carlo Graziani September 16, 2008 10:09 AM

Thanks, I think I understand the situation now. In summary:

(1) Digital cryptosystems are bit-vector-valued functions of an m-bit message M and a k-bit key K;

(2) All such functions are representable by sets of m+k-order polynomial functions of M and K, one polynomial for each ciphertext bit, in consequence of the x*x=x property;

(3) A necessary condition for practical security is that k be “large”, ensuring that the order of the polynomials is high, making the system of equations difficult to invert;

(4) “Large” k is not a sufficient condition for security, because a poorly designed cryptosystem may be subjected to chosen-plaintext attacks that permit the attacker to carry out algebraic operations that reduce the order of some of the polynomials. Potentially drastic reductions are possible;

(5) This sort of attack had been known for some special cryptosystems, but Dinur and Shamir have now developed a general methodology that can apply this order-reduction attack to any cryptosystem.

(6) This methodology can be applied to validate cryptosystems, by verifying that all the ciphertext bits correspond to irreducibly high-order polynomials.

Carlo: almost right. (2) m+k is an upper bound on the degrees of the polynomials. A vulnerable cryptosystem has polynomials with lower degrees, in the simple sense that all higher-degree coefficients happen to be 0.

(3) Yes, k needs to be large – but that is not in itself news; too small k just make brute-force key guessing possible. However a large k does not ensure that the polynomial degree will be high. (Consider treehouse cryptography: a 128-bit key is xored into each 128-bit plaintext bit for bit. Here n+k is 256, but all polynomials have degree 1!) The key to resilience against this attack is to get the actual degree of the polynomial closer to the n+k maximum.

(4) I don’t think it is a good description of the attack to say that algebraic manipulations reduce the degree of the original polynomials. The degrees need to be low to begin with, and in the black-box mode the original polynomials are never known exactly at all.

Clive Robinson September 16, 2008 1:48 PM

Hmm,

Still thinking on this one part’s of me say “bl***y obvious” which begs the question “why has it not been thought of before”. Which my gut tells me is a sure indicator that it’s a little fissure that is going to get a very sharp wedge driven into it and therefore turn into a very big crack quite unexpectadly.

My other thought is it explains why GCHQ amongst others has been looking for maths bods with theoretical FWT type skills.

Michael Vielhaber September 18, 2008 5:01 AM

The so-called “Cube attack” is (in my personal, thus heavily partial, opinion) precisely the AIDA attack presented by myself in 2007 at

http://eprint.iacr.org/2007/413

( in Dinur/Shamir)

Maybe, this paper is a bit of help to understand the AIDA/Cube attack. Please note that (shame on me 😉 I was not aware of the ANF concept in 2007, hence the ENF I “introduced” there is thus the ANF.

What remains unsolved, and also by Dinur/Shamir, is how to find some linear (in the key vars) parts of the full ANF (algebraic normal form) in some poly-bounded time.
This is what I call Phase A, and which takes “several weeks” also with D/S, (Sect. 7.3, l. 3).

Lexicon:

AIDA == Cube
t: on p.2, l.2 == C_I, with I={i_1,..,i_n}
Prop. 3 == Thm. 1
Prop. 3 == Thm. 2 (equivalent to Thm 1 with C_I replaced by C_I union {x_j})
Table p.5 (for t >= 625), last l. of Sect 7. (for t=640) == Tables 1,2 (for t >= 672, 770, resp.)

Personally, I prefer to be proud and happy to have anticipated Adi Shamir by almost a year, instead of mumbling about plagiarism. Anyway, now OUR attack receives the deserved public attention.

Michael Vielhaber September 18, 2008 5:25 AM

Again part of the lexicon, which was partially eaten by the webpage:

Lexicon:

AIDA == Cube
t: [i_1,..i_n] on p.2, l.2 == C_I, with I={i_1,..,i_n}

Instead of [ ] read “less” and “more”, which do not make it into the preview.

This is a reinvention of an old method, hopefully this will not become yet another series of papers investigating some theory under a new name – which was the case with XL.

Please stop the hype and move away from discipling things you don’t understand. 🙂

I wonder if you can lend me your whole program of CUBE ATTACK in application to the Trivium Cipher. Due to my limited knowledge, I sincerely hope that you can offer me timely help. Words cannot express my gratitude.

Sidebar photo of Bruce Schneier by Joe MacInnis.