Subject: Restricting key sizes to mult of 64 bits

From: [email-masked]
Date: Wed, 14 Apr 1999 11:03:30 -0700

The DSS spec requires that DSS keys be a multiple of 64 bits in size.
PGP has not enforced this limitation in the past, but we are adding that
now.

At the same time, we are considering requiring that newly generated keys
of the other types, ElGamal and RSA, also be multiple of 64 bits (note
that this is only enforced on keygen).  The rationale is that keys of
"oddball" sizes may not be properly supported by all implementations.
We want users' keys to be able to be used in a wide range of present and
future implementations, possibly including non-PGP environments like
smartcard systems and X.509 or SPKI.  By making the key sizes a nice,
round number, we improve the chances of them functioning properly in
these other environments.

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.

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.

However, there is some concern that the user and developer community
may be opposed to losing this flexibility in their key size choices.
I was hoping to get some feedback here about whether this change seems
reasonable.  OpenPGP participants have provided valuable feedback in the
past regarding design decisions made by NAI, often after the fact.  This
time it would be helpful to find out beforehand if there will be opposition
to restricting newly generated keys in this way.

Thanks for your comments,

Hal Finney
NAI, Inc.

---

From: Werner Koch <[email-masked]>
Date: Wed, 14 Apr 1999 22:09:47 +0200

> of the other types, ElGamal and RSA, also be multiple of 64 bits (note

I can agree on a multiple of 8 bits but I don't the an advantage to 
use any other value.

> weren't able to use their keys with the CAPI version.

Working around bugs in one companies new product is a Bad Thing to do.
There are many other issues we could fix for them by changing the
standards ;-).  Adding workarounds for some products which are around
for a long time is a different thing.

Just my 0.02 Euros

-- 
Werner Koch at guug.de           www.gnupg.org           keyid 621CC013

---

From: Michael Marking <[email-masked]>
Date: Fri, 16 Apr 1999 07:10:30 -0700

At 10:09 PM 99/04/14 +0200, you wrote:
>[email-masked] writes:
>
>> At the same time, we are considering requiring that 
>> newly generated keys of the other types, ElGamal 
>> and RSA, also be multiple of 64 bits (note
>
>I can agree on a multiple of 8 bits but I don't the 
>an advantage to use any other value.

Why?

For a given maximum key size, this restriction cuts
the available key space in half, approximately. What
effect does it have on the difficulty of an attack?

>> 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.
>

Discovered errors are an indicator that additional, 
latent errors are likely to exist. The fringe cases 
are often the ones which encounter the errors. If we 
do not permit "odd" key sizes, or other inconvenient 
usage, then we may allow sloppy practices which 
ultimately might jeopardize the security of the user.

>There are many other issues we could fix for them by 
>changing the standards ;-). 

>Adding workarounds for some products which are around 

Yes. A warning to the user, or a documented
configuration option, is a much better solution.

---

From: Werner Koch <[email-masked]>
Date: Fri, 16 Apr 1999 18:24:29 +0200

> >an advantage to use any other value.

Because it is the natural unit of measure on most computers.

> effect does it have on the difficulty of an attack?

I didn't mean that we need a restriction at all.

---

From: Jon Callas <[email-masked]>
Date: Wed, 21 Apr 1999 15:21:58 -0700

As has been noted, DSS requires that the keys be a multiple of 64.
According to M,Vo,&V (section 11.58, p453), DSA requires this too. It says,
"...the size of p can be any multiple of 64 bits between 512 and 1024 bits
inclusive." They are apparently quoting FIPS 186 on this. I know that
Schneier also says something similar.

I think it's tacit that DSA keys need to be multiples of 64 bits. I'm
willing to explicitly say this in the next revision. It is, of course,
polite for an implementation to permit odd-size keys, but an implementation
is permitted to reject this.

I don't see any reason to restrict the key sizes on Elgamal or RSA keys.
And as the owner of a 1723 bit RSA key, I'm against it.

	Jon