Algebraic attacks and data word rotations
in [Cryptography]
|
Prev: Protecting 3x16 bits with 16 bits ? (Which error correcting code for mode 3?)
Next: why doesn't the decryption primitive in PKCS#1 employ RSA blinding?
From: Mok-Kong Shen on 13 Feb 2010 07:25 J.D. wrote: > This only would work if the PRNG is secure against algebraic attack > (and secure generally). If it is not secure then it should be > possible to extract the master key that you used to prime the PRNG. > On the other hand, if it is secure then presumably whatever mechanism > that makes the PRNG secure against algebraic attack could be built > into the block cipher right from the start, and you wouldn't need the > complex scheme you outline. I am not yet aware of a technique to analyse the congruential PRNG with the modification I indicated, namely the bits of the output words are circularly shifted by pseudo-random amounts. I surmise that's rather difficult to be formulated in algebraic terms. Of course, my conjecture could be false. That's why I posted my idea previously in the group, in the hope that some experts would be interested to investigate the issue. But up till now there is yet no feedback to my posting. As to the method of employing a different key to encrypt different blocks in order to "fundamentally" foil the algebraic and certain earlier well-researched analysis techniques of breaking block ciphers (which, BTW, in contrast to the algebraic analysis, generally need "enormous" materials processed with one and the same key), do you (or some other experts of the group) have "concrete" comments? I should be very very grateful to know them, if any. Thanks, M. K. Shen
From: Greg Rose on 13 Feb 2010 12:59 In article <c5811827-c986-4c25-99f7-bd75b1354122(a)y33g2000yqb.googlegroups.com>, J.D. <degolyer181(a)yahoo.com> wrote: >Of course, if we are talking about a 32-bit data word rotation then >without reduction to a system of quadratic polynomials this would give >us a system of polynomials of degree 6, no? Can XL or XSL even work >on systems of polynomials of such high degree? The various papers by >Courtois et al only mention quadratic systems, as far as I recall... The problem is that, generally speaking, the number of monomials goes up exponentially in the degree of the polynomial, and therefore the number of new variables does too. Algebraic attacks on stream ciphers have been feasible up to about degree 5, IIRC. But when you point at block ciphers, each round adds either more variables or increases the degree, until it becomes infeasible again. Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
From: J.D. on 13 Feb 2010 13:28 On Feb 13, 12:59 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: > In article <c5811827-c986-4c25-99f7-bd75b1354...(a)y33g2000yqb.googlegroups..com>, > > J.D. <degolyer...(a)yahoo.com> wrote: > >Of course, if we are talking about a 32-bit data word rotation then > >without reduction to a system of quadratic polynomials this would give > >us a system of polynomials of degree 6, no? Can XL or XSL even work > >on systems of polynomials of such high degree? The various papers by > >Courtois et al only mention quadratic systems, as far as I recall... > > The problem is that, generally speaking, the > number of monomials goes up exponentially in the > degree of the polynomial, and therefore the number > of new variables does too. Algebraic attacks on > stream ciphers have been feasible up to about > degree 5, IIRC. But when you point at block > ciphers, each round adds either more variables or > increases the degree, until it becomes infeasible > again. > > Greg. > > -- > Greg Rose > 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C I see. Thanks.
From: J.D. on 13 Feb 2010 13:46 On Feb 13, 12:59 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: > In article <c5811827-c986-4c25-99f7-bd75b1354...(a)y33g2000yqb.googlegroups..com>, > > J.D. <degolyer...(a)yahoo.com> wrote: > >Of course, if we are talking about a 32-bit data word rotation then > >without reduction to a system of quadratic polynomials this would give > >us a system of polynomials of degree 6, no? Can XL or XSL even work > >on systems of polynomials of such high degree? The various papers by > >Courtois et al only mention quadratic systems, as far as I recall... > > The problem is that, generally speaking, the > number of monomials goes up exponentially in the > degree of the polynomial, and therefore the number > of new variables does too. Algebraic attacks on > stream ciphers have been feasible up to about > degree 5, IIRC. But when you point at block > ciphers, each round adds either more variables or > increases the degree, until it becomes infeasible > again. > > Greg. > > -- > Greg Rose > 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C So, would it be accurate to say that a block cipher like RC5, where w (the word size parameter) is 32 or 64, should be highly resistant to algebraic attack after a few rounds, due primarily to the high degree of the data-dependent rotations? In fact, even if we used xor to merge the round keys with the state rather than using addition modulo 2^w, it should still be highly resistant (though substantially less resistant to other sorts of attack), yes?
From: Greg Rose on 13 Feb 2010 16:41
In article <488c0226-2f3f-4f25-a77d-92cd1ea47c1b(a)z39g2000vbb.googlegroups.com>, J.D. <degolyer181(a)yahoo.com> wrote: >On Feb 13, 12:59�pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: >> In article ><c5811827-c986-4c25-99f7-bd75b1354...(a)y33g2000yqb.googlegroups.com>, >> >> J.D. <degolyer...(a)yahoo.com> wrote: >> >Of course, if we are talking about a 32-bit data word rotation then >> >without reduction to a system of quadratic polynomials this would give >> >us a system of polynomials of degree 6, no? �Can XL or XSL even work >> >on systems of polynomials of such high degree? �The various papers by >> >Courtois et al only mention quadratic systems, as far as I recall... >> >> The problem is that, generally speaking, the >> number of monomials goes up exponentially in the >> degree of the polynomial, and therefore the number >> of new variables does too. Algebraic attacks on >> stream ciphers have been feasible up to about >> degree 5, IIRC. But when you point at block >> ciphers, each round adds either more variables or >> increases the degree, until it becomes infeasible >> again. >> >> Greg. >> >> -- >> Greg Rose >> 232B EC8F 44C6 C853 D68F �E107 E6BF CD2F 1081 A37C > >So, would it be accurate to say that a block cipher like RC5, where w >(the word size parameter) is 32 or 64, should be highly resistant to >algebraic attack after a few rounds, due primarily to the high degree >of the data-dependent rotations? In fact, even if we used xor to >merge the round keys with the state rather than using addition modulo >2^w, it should still be highly resistant (though substantially less >resistant to other sorts of attack), yes? That agrees with my understanding, yes. Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C |