Re: [IETF-PKIX] Key Identifiers

[Moshe Litvin <moshe@xxxxxxxxxxxxxx>]

Robert,

A little math: Assume that we are talking about 512 bits RSA keys, the
number of prime number < n is about n/ln n. So the number of prime
number of 256 bits is about 2^256/ln 256 > 2^248. Even if we take only
the primes that are exactly 256 bits it is  > 2^246, which means that
the number of RSA keys of 512 bits is > 2^492. 

Now what are the chances of key collision?

Moshe

Ian Roberts wrote:
> 
> >From: pkoning@xedia.com
> >To: Ian Roberts
> >Subject: Re: [IETF-PKIX] Key Identifiers
> >Date: 20 April 1998 15:01
> >
> >>>>>> "Ian" == Ian Roberts <iroberts@ZERGO.COM> writes:
> >
> > Ian> The discussion on Key Identifiers lead me down the following
> > Ian> chain of thought;
> >
> > Ian> If the Key Identifier is useful for building a path, then it
> > Ian> would be useful to be able to query a directory server for
> > Ian> certificates containing keys with a given key identifier.
> >
> > Ian> If directory servers become sufficiently large (for example, the
> > Ian> size of the Altavista search engine) then a lookup of a large
> > Ian> number of certificates by Key Identifier should be possible
> > Ian> within a couple of seconds (with many occurring concurrently).
> >
> > Ian> If the directory server contained 200 million certificates, then
> > Ian> a possible attack would be to generate key sets and then query
> > Ian> the directory server for matches.  This would give someone with
> > Ian> a fairly low-spec machine the ability to search several hundred
> > Ian> million keys per second.
> >
> >Ian,
> >
> >It sounds like you're thinking about some sort of attack on
> >something.  But I can't figure out what you're attacking and how.
> >
> >    paul
> >
> >
> 
> Sorry, from where I was standing it looked clear, but then these odd
> thoughts always do :-)
> 
> Conventional key search attacks focus a lot of CPU power toward cracking a
> single key set.  It is the cost of this CPU time that is the deterrent and
> hopefully stops low-budget individuals from using this method.
> 
> However, where someone has access to a large directory server, where
> certificate retrievals can be done by Key Identifier (where the key
> identifier is the SHA-1 hash of the public key), then a low power CPU can be
> use to generate key sets (slowly) and the key identifier, and then use the
> directory server to see if any certificates exist with the same Key
> Identifier - any which are found can then be compared for public key
> equality.  For any match you have then discovered the private key for that
> certificate.
> 
> This technique would not aid anyone in cracking a particular key, but could
> be used in an attempt to crack any key held in a directory.
> 
> For example
> 
> With a single budget PC you could generate a key set, say every 5 seconds,
> they can then use the directory server to see if that key set matches any of
> the (say) 200 million certificates on the server (on a server the size of
> Altavista, in a couple of seconds), thus they can in effect try 40 million
> keys per second, using someone else's CPU power.  The key identifier is not
> unique, but a check for quality of public would soon show if you have
> discovered someone's key set.
> 
> Hope this is clearer,
> 
> Ian Roberts
> 
> --
> Zergo Limited, The Square, Basing View, Basingstoke, Hants. RG21 4EG, UK
> Tel: + 44 (0) 1442 342 600    Fax: +44 (0) 1256 812 901
> Website:  http://www.zergo.com