Discussion:
DESX Extended Modes Question
Richard Outerbridge
2005-01-11 12:15:10 UTC
As originally proposed DESX uses two different values for its Pre-
and Post- whitening XORs. It was shown that (at least for ECB mode)
it made no difference if they were the same. Ahh, but what about
extended modes? For CBC, OFB and CFB if the Pre- and Post- whitening
values are the same don't they cancel each other out on the input?

I realize that DESX has never been formally defined for extended modes,
but naively I'm considering taps before the first Pre-whitening XOR and
after the last Post-whitening XOR.

So: How secure is DESX in naive extended modes if the Pre- and Post-
whitenings are the same?

outer
Vincent Rijmen
2005-02-12 12:35:40 UTC
I think there is no problem.
For instance, look at CBC.
With ordinary DES, plaintext blocks and ciphertext blocks are related as
follows:
C_i = DES(P_i + C_{i-1})
With the tap scheme you describe for DESX, this becomes:
C_i = K + DES(K + P_i + C_{i-1})

The `cancellation effect' implies that K + C_{i-1} equals the output of
the (i-1)th DES operation, but I don't think that this matters because
you never see that output value.

A funny effect seems to be that taps after the Pre-whitening XOR and
before the Post-whitening XOR give exactly the same map from plaintexts
to ciphertexts.

Vincent
Post by Richard Outerbridge
As originally proposed DESX uses two different values for its Pre-
and Post- whitening XORs. It was shown that (at least for ECB mode)
it made no difference if they were the same. Ahh, but what about
extended modes? For CBC, OFB and CFB if the Pre- and Post- whitening
values are the same don't they cancel each other out on the input?
I realize that DESX has never been formally defined for extended modes,
but naively I'm considering taps before the first Pre-whitening XOR and
after the last Post-whitening XOR.
So: How secure is DESX in naive extended modes if the Pre- and Post-
whitenings are the same?
outer
Foo Bar
2005-03-01 18:51:34 UTC
[Edited to fix top-posting]
Post by Vincent Rijmen
Post by Richard Outerbridge
As originally proposed DESX uses two different values for its Pre-
and Post- whitening XORs. It was shown that (at least for ECB mode)
it made no difference if they were the same. Ahh, but what about
extended modes? For CBC, OFB and CFB if the Pre- and Post- whitening
values are the same don't they cancel each other out on the input?
I realize that DESX has never been formally defined for extended modes,
but naively I'm considering taps before the first Pre-whitening XOR and
after the last Post-whitening XOR.
That is the correct way. Let's call taps before the pre-whitening XOR
and after the post-whitening XOR "outer" mode and taps after the
pre-whitening XOR and before the post-whitening XOR "inner" mode.
(Obviously, if you XOR the feedback value in CBC mode before or after
the pre-whitening doesn't really matter as XOR is commutative.)

As always, don't trust inner modes! Outer mode uses DESX as one
undivided unit and since an adversary can simulate whatever outer mode
he wants if he has access to ECB DESX, the proof of security applies.

Inner mode is different. Here, the mode does something the adversary
in the DESX proof cannot do - it uses an internal value for the
feedback and thus the proof no longer applies.

And in fact, inner-OFB DESX with equal pre- and post-keys is not
stronger than simple DES under known plaintext (what value is output
in a step and what enters the DES function in the next step?).
Inner-CBC DESX (independent keys or equal keys) is equally weak under
known plaintext/adaptively chosen ciphertext (KP/ACC) with a few
blocks of text.

Note that "How to protect DES against exhaustive key search" by Kilian
and Rogaway (http://wwwcsif.cs.ucdavis.edu/~rogaway/papers/desx.ps)
states that: "... Existing DES CBC hardware can be gainfully employed
the ciphertext." which I think is incorrect since it describes DESX
inner-CBC, which is no stronger than DES against KP/ACC. Yes, KP/ACC
is easy to protect against, but there could be other attacks.

Question: Are there any attacks against inner-CBC DESX (with equal or
independent whitening keys) that only require known plaintext? What
I'm interested in attacks on DESX in inner modes that are better than
the attacks that apply to outer modes.)
Post by Vincent Rijmen
Post by Richard Outerbridge
So: How secure is DESX in naive extended modes if the Pre- and Post-
whitenings are the same?
Extended outer modes do not reduce the security of DESX.
Post by Vincent Rijmen
I think there is no problem.
For instance, look at CBC.
With ordinary DES, plaintext blocks and ciphertext blocks are related as
C_i = DES(P_i + C_{i-1})
C_i = K + DES(K + P_i + C_{i-1})
The `cancellation effect' implies that K + C_{i-1} equals the output of
the (i-1)th DES operation, but I don't think that this matters because
you never see that output value.
I agree. The main point of the pre- and post-keys is to hide the input
and output of the DES computation.
Post by Vincent Rijmen
A funny effect seems to be that taps after the Pre-whitening XOR and
before the Post-whitening XOR give exactly the same map from plaintexts
to ciphertexts.
I'm not sure what you mean. Could you explain?

/FB