From b272c48f5669da6b01bdf079bc24e9ef30ea09b3 Mon Sep 17 00:00:00 2001 From: Matt Caswell Date: Wed, 18 Oct 2017 14:07:57 +0100 Subject: [PATCH] Don't make any changes to the lhash structure if we are going to fail The lhash expand() function can fail if realloc fails. The previous implementation made changes to the structure and then attempted to do a realloc. If the realloc failed then it attempted to undo the changes it had just made. Unfortunately changes to lh->p were not undone correctly, ultimately causing subsequent expand() calls to increment num_nodes to a value higher than num_alloc_nodes, which can cause out-of-bounds reads/ writes. This is not considered a security issue because an attacker cannot cause realloc to fail. This commit moves the realloc call to near the beginning of the function before any other changes are made to the lhash structure. That way if a failure occurs we can immediately fail without having to undo anything. Thanks to Pavel Kopyl (Samsung) for reporting this issue. Reviewed-by: Bernd Edlinger Reviewed-by: Viktor Dukhovni (Merged from https://github.com/openssl/openssl/pull/4550) (cherry picked from commit 4ce8bebcca90a1f8a3347be29df7a501043d4464) --- crypto/lhash/lhash.c | 62 ++++++++++++++++++++++++++++---------------- 1 file changed, 40 insertions(+), 22 deletions(-) diff --git a/crypto/lhash/lhash.c b/crypto/lhash/lhash.c index f24d0c4c8a..5bb20e1e73 100644 --- a/crypto/lhash/lhash.c +++ b/crypto/lhash/lhash.c @@ -14,6 +14,23 @@ #include #include "lhash_lcl.h" +/* + * A hashing implementation that appears to be based on the linear hashing + * alogrithm: + * https://en.wikipedia.org/wiki/Linear_hashing + * + * Litwin, Witold (1980), "Linear hashing: A new tool for file and table + * addressing", Proc. 6th Conference on Very Large Databases: 212–223 + * http://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf + * + * From the wikipedia article "Linear hashing is used in the BDB Berkeley + * database system, which in turn is used by many software systems such as + * OpenLDAP, using a C implementation derived from the CACM article and first + * published on the Usenet in 1988 by Esmond Pitt." + * + * The CACM paper is available here: + * https://pdfs.semanticscholar.org/ff4d/1c5deca6269cc316bfd952172284dbf610ee.pdf + */ #undef MIN_NODES #define MIN_NODES 16 @@ -191,16 +208,34 @@ void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void static int expand(OPENSSL_LHASH *lh) { OPENSSL_LH_NODE **n, **n1, **n2, *np; - unsigned int p, i, j; - unsigned long hash, nni; + unsigned int p, pmax, nni, j; + unsigned long hash; + + nni = lh->num_alloc_nodes; + p = lh->p; + pmax = lh->pmax; + if (p + 1 >= pmax) { + j = nni * 2; + n = OPENSSL_realloc(lh->b, sizeof(OPENSSL_LH_NODE *) * j); + if (n == NULL) { + lh->error++; + return 0; + } + lh->b = n; + memset(n + nni, 0, sizeof(*n) * (j - nni)); + lh->pmax = nni; + lh->num_alloc_nodes = j; + lh->num_expand_reallocs++; + lh->p = 0; + } else { + lh->p++; + } lh->num_nodes++; lh->num_expands++; - p = (int)lh->p++; n1 = &(lh->b[p]); - n2 = &(lh->b[p + (int)lh->pmax]); + n2 = &(lh->b[p + pmax]); *n2 = NULL; - nni = lh->num_alloc_nodes; for (np = *n1; np != NULL;) { hash = np->hash; @@ -213,23 +248,6 @@ static int expand(OPENSSL_LHASH *lh) np = *n1; } - if ((lh->p) >= lh->pmax) { - j = (int)lh->num_alloc_nodes * 2; - n = OPENSSL_realloc(lh->b, (int)(sizeof(OPENSSL_LH_NODE *) * j)); - if (n == NULL) { - lh->error++; - lh->num_nodes--; - lh->p = 0; - return 0; - } - for (i = (int)lh->num_alloc_nodes; i < j; i++) /* 26/02/92 eay */ - n[i] = NULL; /* 02/03/92 eay */ - lh->pmax = lh->num_alloc_nodes; - lh->num_alloc_nodes = j; - lh->num_expand_reallocs++; - lh->p = 0; - lh->b = n; - } return 1; } -- 2.25.1