From 2e94723c1b5d8ab974645e83de90b248265af3cd Mon Sep 17 00:00:00 2001
From: David Woodhouse <David.Woodhouse@intel.com>
Date: Tue, 2 Aug 2016 22:54:46 +0100
Subject: [PATCH] Fix ubsan 'left shift of negative value -1' error in
 satsub64be()

Baroque, almost uncommented code triggers behaviour which is undefined
by the C standard. You might quite reasonably not care that the code was
broken on ones-complement machines, but if we support a ubsan build then
we need to at least pretend to care.

It looks like the special-case code for 64-bit big-endian is going to
behave differently (and wrongly) on wrap-around, because it treats the
values as signed. That seems wrong, and allows replay and other attacks.
Surely you need to renegotiate and start a new epoch rather than
wrapping around to sequence number zero again?

Reviewed-by: Rich Salz <rsalz@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
---
 ssl/record/dtls1_bitmap.c | 61 +++++++++++++++++++++++++++------------
 1 file changed, 42 insertions(+), 19 deletions(-)

diff --git a/ssl/record/dtls1_bitmap.c b/ssl/record/dtls1_bitmap.c
index 9dae9b273e..ecc715d318 100644
--- a/ssl/record/dtls1_bitmap.c
+++ b/ssl/record/dtls1_bitmap.c
@@ -13,7 +13,7 @@
 /* mod 128 saturating subtract of two 64-bit values in big-endian order */
 static int satsub64be(const unsigned char *v1, const unsigned char *v2)
 {
-    int ret, sat, brw, i;
+    int ret, i;
 
     if (sizeof(long) == 8)
         do {
@@ -45,28 +45,51 @@ static int satsub64be(const unsigned char *v1, const unsigned char *v2)
                 return (int)l;
         } while (0);
 
-    ret = (int)v1[7] - (int)v2[7];
-    sat = 0;
-    brw = ret >> 8;             /* brw is either 0 or -1 */
-    if (ret & 0x80) {
-        for (i = 6; i >= 0; i--) {
-            brw += (int)v1[i] - (int)v2[i];
-            sat |= ~brw;
-            brw >>= 8;
-        }
-    } else {
-        for (i = 6; i >= 0; i--) {
-            brw += (int)v1[i] - (int)v2[i];
-            sat |= brw;
-            brw >>= 8;
+    ret = 0;
+    for (i=0; i<7; i++) {
+        if (v1[i] > v2[i]) {
+            /* v1 is larger... but by how much? */
+            if (v1[i] != v2[i] + 1)
+                return 128;
+            while (++i <= 6) {
+                if (v1[i] != 0x00 || v2[i] != 0xff)
+                    return 128; /* too much */
+            }
+            /* We checked all the way to the penultimate byte,
+             * so despite higher bytes changing we actually
+             * know that it only changed from (e.g.)
+             *       ... (xx)  ff ff ff ??
+             * to   ... (xx+1) 00 00 00 ??
+             * so we add a 'bias' of 256 for the carry that
+             * happened, and will eventually return
+             * 256 + v1[7] - v2[7]. */
+            ret = 256;
+            break;
+        } else if (v2[i] > v1[i]) {
+            /* v2 is larger... but by how much? */
+            if (v2[i] != v1[i] + 1)
+                return -128;
+            while (++i <= 6) {
+                if (v2[i] != 0x00 || v1[i] != 0xff)
+                    return -128; /* too much */
+            }
+            /* Similar to the case above, we know it changed
+             * from    ... (xx)  00 00 00 ??
+             * to     ... (xx-1) ff ff ff ??
+             * so we add a 'bias' of -256 for the borrow,
+             * to return -256 + v1[7] - v2[7]. */
+            ret = -256;
         }
     }
-    brw <<= 8;                  /* brw is either 0 or -256 */
 
-    if (sat & 0xff)
-        return brw | 0x80;
+    ret += (int)v1[7] - (int)v2[7];
+
+    if (ret > 128)
+        return 128;
+    else if (ret < -128)
+        return -128;
     else
-        return brw + (ret & 0xFF);
+        return ret;
 }
 
 int dtls1_record_replay_check(SSL *s, DTLS1_BITMAP *bitmap)
-- 
2.25.1