Subject: Re: Restricting key sizes to mult of 64 bits

From: [email-masked] (Peter Gutmann)
Date: Tue, 27 Apr 1999 01:29:48 (NZST)

>Some users have already encountered a problem with oddly sized keys. We
>shipped software which used Microsoft's built-in Crypto API (CAPI) to do the
>RSA calculations.  As it turned out, CAPI had a bug which prevented it from
>working properly with unusual key sizes.  Those users weren't able to use
>their keys with the CAPI version.

This has been a known problem (well, known to everyone but Microsoft) since the
very first CryptoAPI shipped about three years ago.  For people who haven't
seen this, MS assume that an RSA key has certain fixed properties (eg that p, q
= n/2 bits exactly, that e < 32 bits, and various other bletcherousness - noone
will ever need more than 640K, and noone will ever type a URL larger than 1024
characters).  I don't think PGP should have to include workarounds for bugs in
their code.

>We would like to reduce the chance of running into similar problems in the
>future, and keeping keys to round sizes should help.  The choice of 64 bits as
>the multiple is based on trading off the desire for plenty of key sizes versus
>minimizing the chance of an unsupported key size.  The fact that DSS uses 64
>bit multiples suggests that this is a reasonable value.

I'm not sure of the rationale for this in DSS (possibly some hardware
limitation, perhaps in the Capstone chips?) but requiring it isn't a good idea.
DSS assumes that you'll be using Kravitz' kosherizer to generate keys, however
there are other, better (in some circumstances) algorithms which can't easily
generate keys of a certain size.  For example the Lim-Lee algorithm, which
generates keys with certain very nice properties for DLP-based PKC's, doesn't
easily generate keys of a certain size (this is a problem with the X9.42
standard for DH, which mandates the use of the kosherizer for generating DH
keys (!!!) and then has to add all sorts of horrible kludges to get around
things like small subgroup attacks.  If they used Lim-Lee this wouldn't be a
problem, and generation would be much more efficient than with the kosherizer).

The point of this ramble is that requiring certain more or less arbitrary
properties (eg X9.42's requirement to use the kosherizer) greatly limits the
flexibility available during key generation while providing no clear advantage.

Peter.