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: J.D. on 12 Feb 2010 12:40
Of late I have been attempting to wrap my head around the XL and XSL
algebraic attacks on block ciphers (with only limited success, I might
add), and I have a few questions about how these attacks would apply
to 'hidden' (i.e. unknown to the attacker) data word rotations (such
as those that are used in RC5 and CAST 256). I have looked but I
cannot find any useful papers on this topic (though this may just be a
testament to my deficient Google-fu). Namely:

1) Is there a way to express the function F(x,y) = x <<< y (where 'x'
is a data word, 'y' is either a key or another data word, and '<<<' is
a bitwise circular shift) as a quadratic polynomial equation or set of
such equations over GF(2) or any of its extension fields? In
particular, are there equations that are true with probability 1 (or
nearly 1)?

2) Is there some other way of handling key-dependent and data-
dependent rotations within the XL and XSL attacks other than
describing them with polynomial equations (e.g. linear approximation
or what have you)?
From: Mok-Kong Shen on 12 Feb 2010 15:16
J.D. Wrote:
> Of late I have been attempting to wrap my head around the XL and XSL
> algebraic attacks on block ciphers (with only limited success, I might
> add), and I have a few questions about how these attacks would apply
> to 'hidden' (i.e. unknown to the attacker) data word rotations (such
> as those that are used in RC5 and CAST 256). I have looked but I
> cannot find any useful papers on this topic (though this may just be a
> testament to my deficient Google-fu). Namely:

Being layman, I can't answer your questions. However, I have the
impression that algebraic analysis assumes a "fixed" algorithm with
a constant key. If there is anything of the algorithm that is
changed by the flow of the plaintext during the processing, then
there wouldn't be a fixed set of equations to be solved and hence
the method wouldn't function, I would guess.

But I suppose that even with a fixed algorithm, employing multiple
encryptions -- e.g. first xor the plaintext with output of a PRNG, then
do the block encryption and finally again do an xor with output
of a PRNG or do a pseudo-random permutation of the words of the
output stream from the block algorithm -- would foil the attacks with
algebraic and certain earlier types of analysis in my humble view.
Earlier I suggested to use a master key to generate different keys for
processing different blocks, thus redering such attacks economically
infeasible, even if such analysis researches turn out to be very
succesful. (In algebraic analysis one hopes to be able to crack with
very little plaintext and ciphertext materials, if I don't err.. But,
if each block must be worked on sepeartely, because it has a unique key
different from the keys of other blocks, the computing cost and the
time to decipher the whole message would be too much to be practical.)

M. K. Shen
From: J.D. on 12 Feb 2010 15:46
> Being layman, I can't answer your questions.

OK.


> But I suppose that even with a fixed algorithm, employing multiple
> encryptions -- e.g. first xor the plaintext with output of a PRNG, then
> do the block encryption and finally again do an xor with output
> of a PRNG or do a pseudo-random permutation of the words of the
> output stream from the block algorithm -- would foil the attacks with
> algebraic and certain earlier types of analysis in my humble view.
> Earlier I suggested to use a master key to generate different keys for
> processing different blocks, thus redering such attacks economically
> infeasible, even if such analysis researches turn out to be very
> succesful. (In algebraic analysis one hopes to be able to crack with
> very little plaintext and ciphertext materials, if I don't err.. But,
> if each block must be worked on sepeartely, because it has a unique key
> different from the keys of other blocks, the computing cost and the
> time to decipher the whole message would be too much to be practical.)
>
> M. K. Shen

As far as I understand your comment, I don't think that's right. The
XSL attack (or at least one version of it) only needs a single known
plaintext (and the corresponding ciphertext) in order to recover the
key, and does so by taking into account how the round-keys are derived
from the master user key. If you somehow interweave a PRNG or tweak
or way of varying the subkeys into the cipher, such that the
encryption function is different from block to block, there is nothing
to stop the attacker from analyzing the PRNG, reducing it to a system
of equations, and including it in the overall attack.
From: Mok-Kong Shen on 12 Feb 2010 16:31
J.D. write:
>Mok-Kong.Shen wrote:


>> But I suppose that even with a fixed algorithm, employing multiple
>> encryptions -- e.g. first xor the plaintext with output of a PRNG, then
>> do the block encryption and finally again do an xor with output
>> of a PRNG or do a pseudo-random permutation of the words of the
>> output stream from the block algorithm -- would foil the attacks with
>> algebraic and certain earlier types of analysis in my humble view.
>> Earlier I suggested to use a master key to generate different keys for
>> processing different blocks, thus redering such attacks economically
>> infeasible, even if such analysis researches turn out to be very
>> succesful. (In algebraic analysis one hopes to be able to crack with
>> very little plaintext and ciphertext materials, if I don't err.. But,
>> if each block must be worked on sepeartely, because it has a unique key
>> different from the keys of other blocks, the computing cost and the
>> time to decipher the whole message would be too much to be practical.)

> As far as I understand your comment, I don't think that's right. The
> XSL attack (or at least one version of it) only needs a single known
> plaintext (and the corresponding ciphertext) in order to recover the
> key, and does so by taking into account how the round-keys are derived
> from the master user key. If you somehow interweave a PRNG or tweak
> or way of varying the subkeys into the cipher, such that the
> encryption function is different from block to block, there is nothing
> to stop the attacker from analyzing the PRNG, reducing it to a system
> of equations, and including it in the overall attack.

O.k. In the case of PRNGs I have (unconsiciosly, see below) assumed
that the PRNGs are not so simple to be analysed. If one uses the
congruential PRNGs, there have long been known to be attacks on them
as such. Recently however I suggested that the output words from such
a PRNG be circularly shifted by pseudo-random amounts (e.g. using some
output from the same PRNG), thus rendering the techniques of the genre
of Boyar not workable. In the second case I mentioned (without PRNGs),
I don't change anything of the block algorithm, but only use different
keys for different blocks. Now, assuming that the algebraic analysis
works (BTW, certainly not without considerable computing cost per
block) for the first block and the key of the block is found. This
means that before that the analyst has at hand a pair of correcponding
plaintext and ciphertext of that block. However, that key doesn't help
at all to decrypt the next block, because that has a different key. So
the analyst needs again a pair of plaintext and ciphertext, etc. until
the end of the message. Well then, looking back, one has assumed in the
entire process that all plaintext blocks are known. But then what's the
purpose of doing that "excercise"?

M. K. Shen

From: J.D. on 12 Feb 2010 18:15
On Feb 12, 4:31 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> J.D. write:
>
>
>
> >Mok-Kong.Shen wrote:
> >> But I suppose that even with a fixed algorithm, employing multiple
> >> encryptions -- e.g. first xor the plaintext with output of a PRNG, then
> >> do the block encryption and finally again do an xor with output
> >> of a PRNG or do a pseudo-random permutation of the words of the
> >> output stream from the block algorithm -- would foil the attacks with
> >> algebraic and certain earlier types of analysis in my humble view.
> >> Earlier I suggested to use a master key to generate different keys for
> >> processing different blocks, thus redering such attacks economically
> >> infeasible, even if such analysis researches turn out to be very
> >> succesful. (In algebraic analysis one hopes to be able to crack with
> >> very little plaintext and ciphertext materials, if I don't err.. But,
> >> if each block must be worked on sepeartely, because it has a unique key
> >> different from the keys of other blocks, the computing cost and the
> >> time to decipher the whole message would be too much to be practical.)
> > As far as I understand your comment, I don't think that's right.  The
> > XSL attack (or at least one version of it) only needs a single known
> > plaintext (and the corresponding ciphertext) in order to recover the
> > key, and does so by taking into account how the round-keys are derived
> > from the master user key.  If you somehow interweave a PRNG or tweak
> > or way of varying the subkeys into the cipher, such that the
> > encryption function is different from block to block, there is nothing
> > to stop the attacker from analyzing the PRNG, reducing it to a system
> > of equations, and including it in the overall attack.
>
> O.k. In the case of PRNGs I have (unconsiciosly, see below) assumed
> that the PRNGs are not so simple to be analysed. If one uses the
> congruential PRNGs, there have long been known to be attacks on them
> as such. Recently however I suggested that the output words from such
> a PRNG be circularly shifted by pseudo-random amounts (e.g. using some
> output from the same PRNG), thus rendering the techniques of the genre
> of Boyar not workable. In the second case I mentioned (without PRNGs),
> I don't change anything of the block algorithm, but only use different
> keys for different blocks. Now, assuming that the algebraic analysis
> works (BTW, certainly not without considerable computing cost per
> block) for the first block and the key of the block is found. This
> means that before that the analyst has at hand a pair of correcponding
> plaintext and ciphertext of that block. However, that key doesn't help
> at all to decrypt the next block, because that has a different key. So
> the analyst needs again a pair of plaintext and ciphertext, etc. until
> the end of the message. Well then, looking back, one has assumed in the
> entire process that all plaintext blocks are known. But then what's the
> purpose of doing that "excercise"?
>
> M. K. Shen

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.
 |  Next  |  Last
Pages: 1 2 3 4 5
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?