[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: draft-ietf-ipsec-ciph-cbc-02.txt
Some comments on the weak keys of IDEA.
Also note that the following paper will be presented at Eurocrypt'98
(Helsinki, June 1-4).
Philip Hawkes, Differential-linear weak key classes of IDEA
Vincent Rijmen
Bart Preneel
-------------------------------------------------------------------------------
Katholieke Universiteit Leuven tel. +32 16 32 11 48
Dept. Electrical Engineering-ESAT / COSIC fax. +32 16 32 19 86
K. Mercierlaan 94, B-3001 Heverlee, BELGIUM
bart.preneel@esat.kuleuven.ac.be
http://www.esat.kuleuven.ac.be/~preneel
-------------------------------------------------------------------------------
The draft says:
>
> 2.3 Weak Keys
>
> Weak key checks SHOULD be performed. If such a key is found, the
> key SHOULD be rejected and a new SA requested. Some cipher
> algorithms have weak keys or keys that MUST not be used due to
> their weak nature.
>
[...]
> IDEA:
>
> IDEA has weak keys of the following form [Crypto93]:
>
> 0000,0000,0x00,0000,0000,000x,xxxx,x000
>
> where "x" can be any hexadecimal number.
>
> Keys of this form guarantee the value of bit-wise XOR of resultant
> ciphertext pairs from the bit-wise XOR of certain plaintext pairs.
>
[...]
> [Crypto93] J. Daeman, R. Govaerts, J. Vandewalle, "Weak Keys for
> IDEA", Advances in Cryptology, CRYPTO 93 Proceedings,
> Springer-Verlag, pp. 224-230.
>
This statement is incorrect, and it is certainly not in accordance with
the [Crypto93] reference. Also note that the name of the first author
is Daemen rather than Daeman.
In [Crypto93], three classes of weak keys have been identified:
1) keys that result in a linear factor:
0000 00ab 0000 0000 00c0 0000 000d xyzt
where
a = 0,1,2,3
b = 0,8
c = 0,2,4,6,8,10,12,14
d = 0,1
x,y,z,t = any value (2^23 keys)
A linear factor is a linear relation between certain bits of the input and certain
bits of the output, that holds with probability one.
2) keys for which a certain difference in the plaintext input leads to
a predictable difference in the output (with probability one)
0000 00ax yzb0 0000 00tc 0000 000u vwd0
where
a = 0,1,2,3
b = 0,8
c = 0,8
d = 0,2,4,6,8,10,12,14
x,y,z,t,u,v,w = any value (2^35 keys)
This is the class of keys that has the weakness that is explained in the draft.
Note that the weak key values given in the standard do not agree.
3) other weak keys
0000 00ax yzb0 0000 00tu v000 cwsq prd0
a = 0,1,2,3
b = 0,8
c = 0,1
d = 0,2,4,6,8,10,12,14
x,y,z,t,u,v,w,s,q,p,r = any value (2^51 keys)
This is a class of keys that can be easily recovered if the attacker knows the
ciphertexts corresponding to 16 plaintexts with a certain structure.
(more exactly, the differences between the 16 plaintexts need to have
a certain value). Class 2 is a subclass of class 3. Note that according
to [Crypto93], class 1 is not a subclass of class 3.
If this is considered to be "too complex," one can define
the following class, that contains all weak keys and is easy to write down:
0000 00xx xxx0 0000 00xx x000 xxxx xxxx
Of course this is a serious overkill (2^64 keys).
-------------------------------------------------------------------------------
On Tue, 10 Mar 1998, Roy Pereira wrote:
>
> Internet Engineering Task Force R. Pereira
> IP Security Working Group TimeStep Corporation
> Internet Draft R. Adams
> Expires in six months Cisco Systems Inc.
> March 10, 1998
>
>
>
> The ESP CBC-Mode Cipher Algorithms
> <draft-ietf-ipsec-ciph-cbc-02.txt>
>
Follow-Ups:
References: