Fix size_t underflow in binary search in x509cert processing

[jonathanverner]

The original code used size_t for first,last & middle sentinels in a binary search algorithm when looking up OIDs in a table in the OidToNameLookup & OidToKeyUsageValueLookup functions.

If an OID which came before all of the entries in the table was looked up eventually the last sentinel would be decreased to -1 and the search should have ended, as the condition first <= last should have failed. However, since an unsigned type (size_t) was used for the sentinels, decreasing last to -1 underflowed it and the code subsequently crashed.

[noloader]

Thanks @jonathanverner.

I went a different direction with the fix. Instead of using an int, we cut-over to std::binary_search. I would have used your fix if C++ provided a ssize_t on all platforms. I wanted more than an int because of word sizes on 64-bit platforms.

I don't recall why we did not use std::binary_search way back when. In hindsight, we should have used it back then.

Also see Commit d4347966a594.

[jonathanverner]

Using std::binary_search is of course much better :-) Thanks for the quick fix!

[noloader]

Ugh... After cutting over to binary_search, the OID to name lookups are failing:

Dumping identities:
2.5.4.49: 2.5.4.6=US; 2.5.4.8=NY; 2.5.4.7="New York"; 2.5.4.10="Example, LLC"; 2.5.4.3="Example Company"; 1.2.840.113549.1.9.1=support@example.com
2.5.4.3: Example Company
1.2.840.113549.1.9.1: support@example.com
2.5.29.14: 56D9E01807C296FD344E5AFE9F47156BDA12A07D
2.5.29.17: example.com
2.5.29.17: www.example.com
2.5.29.17: mail.example.com
2.5.29.17: ftp.example.com
2.5.29.17: 127.0.0.1
2.5.29.17: 00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:01
2.5.29.17: webmaster@example.com
2.5.29.17: ftpmaster@example.com
2.5.29.17: hostmaster@example.com

That should look like:

Dumping identities:
DN: C=US; ST=NY; L="New York"; O="Example, LLC"; CN="Example Company"; EMAIL=support@example.com
CN: Example Company
EMAIL: support@example.com
SPKI: 56D9E01807C296FD344E5AFE9F47156BDA12A07D
SAN: example.com
SAN: www.example.com
SAN: mail.example.com
SAN: ftp.example.com
SAN: 127.0.0.1
SAN: 00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:01
SAN: webmaster@example.com
SAN: ftpmaster@example.com
SAN: hostmaster@example.co

I'm going to revert to the old code, but guard the oid and make sure it is in the range of the table. Reverted and guarded at Commit dd8ca0d21984.

Sorry it took so long to test the change. OpenSSL 3.0 broke my test scripts. It took me a couple of days to fix all the breaks. OpenSSL is always breaking things. Those devs are like a bull in a fine china shop.

[noloader]

@jonathanverner,

Ok, I finally got this sorted out. I was using std::binary_search incorrectly. We needed to use std::equal_range to get an iterator to the element we were looking for.

The commit of interest is Commit a84e2685789d.

[noloader]

@jonathanverner,

It looks like std::lower_bound is more efficient than std::equal_range. See https://stackoverflow.com/q/18994602.

Cut-over to std::lower_bound happened in Commit 48211562fa2d.