[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]

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