diff --git a/ebtree/ebimtree.h b/ebtree/ebimtree.h
index b40e490..1fe9fa0 100644
--- a/ebtree/ebimtree.h
+++ b/ebtree/ebimtree.h
@@ -198,7 +198,14 @@
 			 * The last two cases can easily be partially merged.
 			 */
 			bit = equal_bits(new->key, old->key, bit, len);
-			diff = cmp_bits(new->key, old->key, bit);
+
+			/* Note: we can compare more bits than the current node's because as
+			 * long as they are identical, we know we descend along the correct
+			 * side. However we don't want to start to compare past the end.
+			 */
+			diff = 0;
+			if (((unsigned)bit >> 3) < len)
+				diff = cmp_bits(new->key, old->key, bit);
 
 			if (diff < 0) {
 				new->node.leaf_p = new_left;
@@ -263,7 +270,14 @@
 
 			new->node.node_p = old->node.node_p;
 
-			diff = cmp_bits(new->key, old->key, bit);
+			/* Note: we can compare more bits than the current node's because as
+			 * long as they are identical, we know we descend along the correct
+			 * side. However we don't want to start to compare past the end.
+			 */
+			diff = 0;
+			if (((unsigned)bit >> 3) < len)
+				diff = cmp_bits(new->key, old->key, bit);
+
 			if (diff < 0) {
 				new->node.leaf_p = new_left;
 				old->node.node_p = new_rght;
diff --git a/ebtree/ebmbtree.h b/ebtree/ebmbtree.h
index 121c59f..fa25ac5 100644
--- a/ebtree/ebmbtree.h
+++ b/ebtree/ebmbtree.h
@@ -306,12 +306,16 @@
 	new_rght = eb_dotag(&new->node.branches, EB_RGHT);
 	new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
 
-	/* Note: we can compare more bits than
-	 * the current node's because as long as they are identical, we
-	 * know we descend along the correct side.
-	 */
 	new->node.bit = bit;
-	diff = cmp_bits(new->key, old->key, bit);
+
+	/* Note: we can compare more bits than the current node's because as
+	 * long as they are identical, we know we descend along the correct
+	 * side. However we don't want to start to compare past the end.
+	 */
+	diff = 0;
+	if (((unsigned)bit >> 3) < len)
+		diff = cmp_bits(new->key, old->key, bit);
+
 	if (diff == 0) {
 		new->node.bit = -1; /* mark as new dup tree, just in case */