On Tue, Apr 01, 2003, Chris Jarshant wrote:

> 
> ----- Original Message -----
> From: "Dr. Stephen Henson" <[EMAIL PROTECTED]>
> To: <[EMAIL PROTECTED]>
> Sent: Monday, March 31, 2003 7:52 PM
> Subject: Re: X509_STORE and X509_verify performance
> 
> 
> > On Mon, Mar 31, 2003, Chris Jarshant wrote:
> >
> > > I generated 1000 test self-signed CA certs, and wrote
> > > a small program to add them all to an X509_STORE in
> > > preparation for verifying a certificate.. But this operation
> > > took a LONG, LONG time.  Even adding 500 certs took
> > > approx. 30 seconds!  It appeared to go real fast for
> > > the first 100 certs, then decelerate, so I suspect some kind
> > > of sorting or linear search algorithm that is slowing
> > > things down.
> > >
> > > Has anyone else experienced this?  I am fearful of what is
> > > going to happen (or not happen) when I try my test
> > > 1000-cert deep chained cert verification.
> > >
> >
> > Well X509_STORE et al is rather broken but it shouldn't be that broken!
> >
> > Do all these certificates have distinct subject names or do they all
> match?
> > The addition algorithm should do an initial binary search for a matching
> > subject name followed by a linear search for an identical certificate.
> >
> 
> Yes they all have distinct subject names of the form "Test CA Certificate X"
> where 0<=X<1000, and all of them have distinct private keys (of bit
> length 384; making 1000 2048-bit keys takes much too much time).
> I can send you the script I used to generate them if ya want, though
> I have a feeling you probably already know how.
> 

Yes I've a fair idea :-)

> > Aw heck I've just had a horrible suspicion about what might be happening.
> I
> > suspect the STACK is having a new certificate appended: this stuffs up the
> > order then the next binary search calls qsort to restore it. This would
> happen
> > when *every* new certificate is added. Erk...
> 
> Yeah, in one of the stack traces I saw under a debugger,
> I saw a qsort in there somewhere.
> 
> Any workarounds you can think of?  Could there be a performance
> feature added that allows you to delay the sorting until you're done,
> or perhaps don't sort it at all until the STORE is used for the first
> time during X509_verify()?  Any way to override qsort with a
> NOP then when adding the last cert, change it back to qsort()?
> 

Well in the short term some kind of evil hack will be needed by an
application. This would involve messing around with the internals of the
X509_STORE and normally you shouldn't go near those. However in this case you
haven't got any choice.

In outline you'd create an X509_OBJECT for each cert and manually sk_push()
each onto the X509_STORE internal STACK. Then they will just be added and no
sorting will take place. The first lookup will sort them anyway.

A better solution medium term would be to fix the X509_STORE_add_cert() so it
doesn't re-sort on each call. It should be possible to add a new stack
function that can efficiently add a new member to an already sorted STACK by
quickly finding where it should go.

Longer term X509_STORE et al wants junking entirely and something nicer put in
its place: its horribly broken.

Steve.
--
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.demon.co.uk/
Email: [EMAIL PROTECTED], PGP key: via homepage.
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [EMAIL PROTECTED]
Automated List Manager                           [EMAIL PROTECTED]

Reply via email to