Certificate Paths

[Ian Roberts <iroberts@xxxxxxxxx>]

When attempting to build a certificate path in order to validate a 
certificate I am looking at the following approach

Given two sets, F, U where the initial state is F is the empty set and U 
contains the certificate you wish to validate.

1) While U is not empty;

2) Select a Certificate, C,  from U.  Remove C from U and add to F.

3) Fetch all of the certificates belonging to the issuer (set P)

4) Reduce P by removing all certificates from P that are not valid in 
themselves (date, key usage etc).

5) Reduce P by removing all certificates from P that are already in F.

6) Reduce P to contain only those certificates which contain a public key 
that verifies C.

7) Add P to U.

8) Wend.

If intersection of the set F with the set of explicitly trusted (usually 
root CA) certificates is not empty then we were able to build one or more 
validation path(s).

I believe that this will work with cross certification.

Following the discussion on Key Identifiers I looked at optimising this 
using key identifiers.

The most obvious solution is to include an additional Reduction of P

5b) If C contains a AuthorityKeyIdentifier, Reduce P by removing all 
certificates which contain a KeyIdentifier which does not match.

This however does not address the comment Denis.Pinkas@bull.net made

>As said above, no verification of digital signature should be done
>before getting a full path. This saves signature checks (as requested by
>Paul Koning) without the need to overload the certificate by additional
>mandatory extensions (that take memory place when the certificate is
>stored in a smart card).

since 6 would still require potentially spurious verifies.

All the other solutions I have looked at involve the fetching of 
certificates which are not required by the solution above since deferring 
(6) always has the potential to increase the size of P.  However, 
certificate fetches (e.g. via LDAP, approx 90ms to our local directory 
server) may be more expensive than a verify (appox 20ms in our current 
implementation).

aberger@DARMSTADT.GMD.DE wrote:
> One question: Do we have an algorithm for a complete verification? There
> is one that describes how to verify an existing FC path, but do we have
> an algorithm on how to construct a path?

I agree that we need such an algorithm, however I think that it should be 
expressed as simply as possible and optimizations be left to the implementor 
(they can decide if certificate fetches are more expensive than verifies).

The algorithm above does not build a single path, it collects all 
certificate from the subject up to all self-signed certificates that could 
form valid paths (you can work back down from any trusted root certificate 
in the final intersection  to build a path).


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