[openssl-dev] [openssl.org #3631] Bug in the binary search in OBJ_bsearch_ex_ in obj_dat.c (1.0.1j)

[Matthias Mucha via RT]

No, i commented out the RSA encrypt routines and several other things 
that i can't/don't use. This resulted in a smaller array to search, 
which led me to this problem.

I know it's no problem if you use OpenSSL the normal way. I don't call 
it from my code. My code only calls methods available in the OpenSSL API.

Am 17.12.2014 14:51, schrieb Richard Levitte via RT:
> Are you using OBJ_bsearch_ex_ directly from your code? It seems to me that you
> have misunderstood how it works. size is the size of one element of your array,
> num is the number of elements. The actual size of the array (in bytes) should
> then be size*num, and you need to make sure that it is.
>
> I would, however, recommend that you don't call this function directly, and
> instead use the macro OBJ_bsearch_ex, which will calculate the element size
> properly for you, given a type that you give it.
>
> On Fri Dec 12 17:52:07 2014, matthias.mucha at jojema.de wrote:
>> Hello,
>>
>> I strapped down OpenSSL 1.0.1j to only the PEM to RSA, BIO and RSA
>> public
>> decrypt functions. So a bug in the binary search in appeared:
>>
>> Current code:
>>
>> const void *OBJ_bsearch_ex_(const void *key, const void *base_, int
>> num,
>> int size,
>> int (*cmp)(const void *, const void *),
>> int flags)
>> {
>> const char *base=base_;
>> int l,h,i=0,c=0;
>> const char *p = NULL;
>>
>> if (num == 0) return(NULL);
>> l=0;
>> h=num;
>> while (l < h)
>> {
>> i=(l+h)/2;
>> p= &(base[i*size]);
>> c=(*cmp)(key,p);
>> if (c < 0)
>> h=i;
>> else if (c > 0)
>> l=i+1;
>> else
>> break;
>> }
>>
>>
>> [...]
>>
>> My case: size = 4
>> num = 4
>>
>> In the first round i evaluates to 2 which can not be divided by size
>> and lets p
>> escape the frame for the pointers, which results in a segfault.
>>
>> General case:
>>
>> This will fail for every case where num < (size * 2)
>>
>>
>> My fix:
>>
>> const void *OBJ_bsearch_ex_(const void *key, const void *base_, int
>> num,
>> int size,
>> int (*cmp)(const void *, const void *),
>> int flags)
>> {
>> const char *base=base_;
>> int l,h,i=0,c=0;
>> const char *p = NULL;
>>
>> if (num == 0) return(NULL);
>> if (num < size*2) {
>> while(i<num)
>> {
>> p=&(base[i*size]);
>> c=(*cmp)(key,p);
>> if (!c) break;
>> else ++i;
>> }
>> }
>> else {
>> l=0;
>> h=num;
>> while (l < h)
>> {
>> i=(l+h)/2;
>> p= &(base[i*size]);
>> c=(*cmp)(key,p);
>> if (c < 0)
>> h=i;
>> else if (c > 0)
>> l=i+1;
>> else
>> break;
>> }
>> }
>>
>> [...]
>>
>> Regards
>>
>> Matthias Mucha
>>
>
> --
> Richard Levitte
> levitte at openssl.org
>