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

[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