Re: Encryption Key Lengths

[Greg Rose <ggr@qualcomm.com>]

At 13:10 5/01/2000 -0800, Brian Mann wrote:
>I'm installing a VPN on my network for the first time, and need to make
>decisions regarding key lengths. The available range for public key
>length was 256 to 1024 bits. Being very paranoid, I selected 1024 bits.
>Now I'm being asked for a private key length, with an available range
>from 64 to 512 bits. The install program is prompting me with:

[deletia]

There are three different effective key lengths you've mentioned.
1. The modulus size (1024)
2. The exponent size (what we're trying to determine)
3. The symmetric cipher key (3DES, 168 bits)

Lenstra has recently published a very detailed paper about this stuff. But 
basically, the idea is to balance the strengths so that there is no obvious 
"weakest point". The trouble is that these three things are different 
fruits, so no truly direct comparison is possible.

Attacks against the modulus go according to a complicated formula 
("super-poly-logarithmic-sub-exponentional-function, even though the 
thought of it has something of rambunction..." :-); 1024 bits is about 
equivalent to a 90 bit symmetric key. Compute time for D-H goes up roughly 
according to the cube of the length of the modulus.

Attacks against the exponent go according to the square root of the length 
of the exponent, so to match the modulus you need at least about 180 bits. 
Computation for D-H is directly proportional to the length of the 
exponent... so 256 bits is about 25% more expensive than 180 bits, and is a 
nice conservative choice, and a better match for the strength of 3DES.

3DES (even the two key version) is not the weak point.

The Diffie-Hellman stuff happens (hopefully) so rarely that it won't affect 
your overall load.

hope that helps,
Greg.


Greg Rose                                     INTERNET: ggr@Qualcomm.com
Qualcomm Australia        VOICE:  +61-2-9181-4851   FAX: +61-2-9181-5470
Suite 410, Birkenhead Point,             http://people.qualcomm.com/ggr/
Drummoyne NSW 2047    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C