Re: [IETF-PKIX] Key Identifiers

[Ian Roberts <iroberts@xxxxxxxxx>]

>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