Re: new IKE draft

[Lewis McCarthy <[e-mail]>]

Pau-Chen wrote on 16 Mar 1998:
> Actually, for stronger securuty, I think the input to
> RSA encryption should not be longer than 2/3 of the size of the modulus.

Coppersmith's attack from Eurocrypt `96 imposes this security condition 
when the public exponent is e=3. As his paper notes, there are security 
tradeoffs between the amount (and location) of padding and the size of the
public exponent. For some realistic modulus and public exponent sizes (e.g.
e=3, |N| = 1024 bits), the minimum 64 bits of PKCS #1 padding isn't enough
to prevent an attack when the adversary knows a good chunk of the 
plaintext.

This means trouble for the encryption of long identities in the original PK
Encryption Mode of authentication when the peer's public key has a very
small e, and the adversary has a manageable set of identity guesses to 
check. 

One way to patch this hole would be to increase the minimum padding
length. This would mean IKE would no longer be doing vanilla PKCS #1 
encryption block formatting.

An alternative is to impose a minimum size for the public exponent in RSA 
keys used with the original Encryption mode. The adversary's task is 
easiest when the ID payload is the longest allowed by PKCS #1 (i.e. k-11
octets in length) and the adversary knows all but a single bit of the ID
payload. Thus only 65 bits of the input to encryption are unknown to the
adversary. Conservatively the public exponent e should satisfy 
65 >= n^(1/e), where n is the modulus. (This errs on the side of safety, 
since the padding and payload aren't contiguous in PKCS #1, and the 
padding isn't the most significant block of bits in the plaintext. But I
think this is not too far off the mark.) For example, for n approximately
2^1024, the requirement would be e > 170.

I mildly prefer the latter option. What does the WG think?

I don't believe these attacks pose a threat to the encryption of nonces in 
the original and Revised PK Encryption Modes of authentication. Since the 
nonces are randomly generated, the adversary won't start with any partial
information on the nonces. So there's no realistic foothold for a 
stereotyped message attack. Because the nonces are random and sufficiently
large, the adversary essentially has no hope of finding groups of 
ciphertext susceptible to related message attacks. 
-- 
Lewis    http://www.cs.umass.edu/~lmccarth/