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]
