[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: On shared keys

Sami Vaarala <sami.vaarala@netseal.com> writes:

> On 29 Nov 2001, Derek Atkins wrote:
> > Henry Spencer <henry@spsystems.net> writes:
> > > In what way is it worse than old-style shared secrets?  *That* is the
> > > crucial question.
> > 
> > It may be easier to break the RSA key if it's generated with a
> > 'weakly-seeded' PRNG than if the 'weak seed' is used directly.
> 
> I'm not a cryptographist -- can you explain to me why?
> I would expect the RSA keypair to be weaker if the
> pre-shared key had more entropy than the resulting
> RSA key.  But is this the case with the average PSK?

First, the term is "cryptographer"....  Second, please be explicit
when you use the term PSK (Pre-Shared Key), are you talking about a
Pre-Shared Secret Key or a Pre-Shared Public Key?  Please be explicit,
as many of us are arguing that Pre-Shared Public Keys are sufficient.

Third, I can try to explain it.  An average RSA key is 1024-2048 bits
long.  This implies you really need about 1024-2048 bits of entropy
(note that you actually have less that that, because you always know
that the first and last bits are 1, and you know the number has a
particular form, but for brevity of this explanation let's call it the
full length even though it may be a few bits less).

An average shared secret maybe has 50 bits of entropy, if you're
lucky.  The problem is that if you generate an RSA key (requiring
1024-2048 bits of entropy) from a source that only has 50 bits of
entropy, your RSA key effectively has only 50 bits of entropy in it.
This implies that on average only one in every 20-40 bits is truly
random (the others wind up depending on the values of the random
bits).

This implies that there is a lot of redundant, non-random information
in the public key which can make breaking the key much easier.
Considering the key-generation mechanism must be well-known, it means
that you have an easier time determining which bits are the random
ones, which ones are not, and how they relate to each other.

To give a real-world example, a long time ago in a galaxy not
so far away, a Public-Key generator had this code:

	char c = get_random_byte();
	for (i = 0; i < key_length; i++)
		key_buf[i] = c;
	key_pair = generate_key_from_key_buf(key_buf);

What you are suggesting is almost (but not quite) as disastrous as
this completely broken pseudo-code.

I hope this helps explain it.

> -Sami

-derek

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       warlord@MIT.EDU                        PGP key available
Follow-Ups: References: