Add timingsafe_memcmp().

ok deraadt, jmc, tedu

6 files changed, 153 insertions, 38 deletions

diff --git a/src/lib/libc/string/Makefile.inc b/src/lib/libc/string/Makefile.inc
index 1f6d756182..a293219058 100644
--- a/src/lib/libc/string/Makefile.inc
+++ b/src/lib/libc/string/Makefile.inc
@@ -1,4 +1,4 @@
-#       $OpenBSD: Makefile.inc,v 1.34 2014/03/23 23:16:48 tedu Exp $
+#       $OpenBSD: Makefile.inc,v 1.35 2014/06/13 02:12:17 matthew Exp $
 
 # string sources
 .PATH: ${LIBCSRCDIR}/arch/${MACHINE_CPU}/string ${LIBCSRCDIR}/string
@@ -7,11 +7,11 @@ SRCS+=	explicit_bzero.c memccpy.c memmem.c memrchr.c stpcpy.c stpncpy.c \
         strcasecmp.c strcasestr.c strcoll.c strdup.c \
         strerror.c strerror_r.c strlcat.c strmode.c strndup.c strnlen.c \
         strsignal.c strtok.c strxfrm.c \
+        timingsafe_bcmp.c timingsafe_memcmp.c \
         wcscat.c wcschr.c wcscmp.c wcscpy.c wcscspn.c wcslcat.c wcslcpy.c \
         wcslen.c wcsncat.c wcsncmp.c wcsncpy.c wcspbrk.c wcsrchr.c wcsspn.c \
         wcsstr.c wcstok.c wcswcs.c wcswidth.c wmemchr.c wmemcmp.c wmemcpy.c \
-        wmemmove.c wmemset.c wcsdup.c \
-        timingsafe_bcmp.c wcscasecmp.c
+        wmemmove.c wmemset.c wcsdup.c wcscasecmp.c
 
 # machine-dependent net sources
 # m-d Makefile.inc must include sources for:
@@ -149,7 +149,8 @@ MAN+=	bcmp.3 bcopy.3 bstring.3 bzero.3 ffs.3 memccpy.3 memchr.3 \
         strcat.3 strchr.3 strcmp.3 strcoll.3 strcpy.3 strcspn.3 strdup.3 \
         strerror.3 string.3 strlen.3 strmode.3 strncat.3 strncpy.3 strpbrk.3 \
         strrchr.3 strsep.3 strsignal.3 strspn.3 strstr.3 strtok.3 strxfrm.3 \
-        swab.3 strlcpy.3 wcscasecmp.3 wcscat.3 wcschr.3 wcscmp.3 wcscpy.3 \
+        swab.3 strlcpy.3 timingsafe_bcmp.3 \
+        wcscasecmp.3 wcscat.3 wcschr.3 wcscmp.3 wcscpy.3 \
         wcscspn.3 wcsdup.3 wcslcpy.3 wcslen.3 wcspbrk.3 wcsrchr.3 wcsspn.3 \
         wcsstr.3 wcstok.3 wcswidth.3 wmemchr.3 wmemcmp.3 wmemcpy.3 wmemmove.3 \
         wmemset.3
@@ -167,9 +168,9 @@ MLINKS+=strlen.3 strnlen.3
 MLINKS+=strstr.3 strcasestr.3
 MLINKS+=strtok.3 strtok_r.3
 MLINKS+=strerror.3 strerror_r.3
+MLINKS+=timingsafe_bcmp.3 timingsafe_memcmp.3
 MLINKS+=wcscasecmp.3 wcsncasecmp.3
 MLINKS+=wcscat.3 wcsncat.3
 MLINKS+=wcscmp.3 wcsncmp.3
 MLINKS+=wcscpy.3 wcsncpy.3
 MLINKS+=wcslcpy.3 wcslcat.3
-MLINKS+=bcmp.3 timingsafe_bcmp.3
diff --git a/src/lib/libc/string/bcmp.3 b/src/lib/libc/string/bcmp.3
index 52584b4b83..720a8bf304 100644
--- a/src/lib/libc/string/bcmp.3
+++ b/src/lib/libc/string/bcmp.3
@@ -27,21 +27,18 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.\"     $OpenBSD: bcmp.3,v 1.10 2013/06/05 03:39:23 tedu Exp $
+.\"     $OpenBSD: bcmp.3,v 1.11 2014/06/13 02:12:17 matthew Exp $
 .\"
-.Dd $Mdocdate: June 5 2013 $
+.Dd $Mdocdate: June 13 2014 $
 .Dt BCMP 3
 .Os
 .Sh NAME
-.Nm bcmp ,
-.Nm timingsafe_bcmp
+.Nm bcmp
 .Nd compare byte string
 .Sh SYNOPSIS
 .In string.h
 .Ft int
 .Fn bcmp "const void *b1" "const void *b2" "size_t len"
-.Ft int
-.Fn timingsafe_bcmp "const void *b1" "const void *b2" "size_t len"
 .Sh DESCRIPTION
 The
 .Fn bcmp
@@ -56,33 +53,15 @@ bytes long.
 Zero-length strings are always identical.
 .Pp
 The strings may overlap.
-.Pp
-The
-.Fn timingsafe_bcmp
-function has the same semantics as
-.Fn bcmp ,
-but its running time is independent of the contents of
-.Fa b1
-and
-.Fa b2 ,
-making it safe to use for comparing secret values such as cryptographic MACs.
-In contrast,
-.Fn bcmp
-returns after finding the first differing byte,
-making it vulnerable to timing attacks.
 .Sh SEE ALSO
 .Xr memcmp 3 ,
 .Xr strcasecmp 3 ,
 .Xr strcmp 3 ,
 .Xr strcoll 3 ,
-.Xr strxfrm 3
+.Xr strxfrm 3 ,
+.Xr timingsafe_bcmp 3
 .Sh HISTORY
 The
 .Fn bcmp
 function first appeared in
 .Bx 4.2 .
-.Pp
-The
-.Fn timingsafe_bcmp
-function first appeared in
-.Ox 4.9 .
diff --git a/src/lib/libc/string/memcmp.3 b/src/lib/libc/string/memcmp.3
index ebd838825a..25d308e617 100644
--- a/src/lib/libc/string/memcmp.3
+++ b/src/lib/libc/string/memcmp.3
@@ -1,4 +1,4 @@
-.\"     $OpenBSD: memcmp.3,v 1.8 2013/06/05 03:39:23 tedu Exp $
+.\"     $OpenBSD: memcmp.3,v 1.9 2014/06/13 02:12:17 matthew Exp $
 .\"
 .\" Copyright (c) 1990, 1991 The Regents of the University of California.
 .\" All rights reserved.
@@ -31,7 +31,7 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: June 5 2013 $
+.Dd $Mdocdate: June 13 2014 $
 .Dt MEMCMP 3
 .Os
 .Sh NAME
@@ -70,6 +70,7 @@ Zero-length strings are always identical.
 .Xr strcmp 3 ,
 .Xr strcoll 3 ,
 .Xr strxfrm 3 ,
+.Xr timingsafe_memcmp 3 ,
 .Xr wmemcmp 3
 .Sh STANDARDS
 The
diff --git a/src/lib/libc/string/timingsafe_bcmp.3 b/src/lib/libc/string/timingsafe_bcmp.3
new file mode 100644
index 0000000000..0886731ce7
--- /dev/null
+++ b/src/lib/libc/string/timingsafe_bcmp.3
@@ -0,0 +1,92 @@
+.\"     $OpenBSD: timingsafe_bcmp.3,v 1.1 2014/06/13 02:12:17 matthew Exp $
+.\"
+.\" Copyright (c) 2014 Google Inc.
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.Dd $Mdocdate: June 13 2014 $
+.Dt TIMINGSAFE_BCMP 3
+.Os
+.Sh NAME
+.Nm timingsafe_bcmp ,
+.Nm timingsafe_memcmp
+.Nd timing-safe byte sequence comparisons
+.Sh SYNOPSIS
+.In string.h
+.Ft int
+.Fn timingsafe_bcmp "const void *b1" "const void *b2" "size_t len"
+.Ft int
+.Fn timingsafe_memcmp "const void *b1" "const void *b2" "size_t len"
+.Sh DESCRIPTION
+The
+.Fn timingsafe_bcmp
+and
+.Fn timingsafe_memcmp
+functions lexicographically compare the first
+.Fa len
+bytes (each interpreted as an
+.Vt unsigned char )
+pointed to by
+.Fa b1
+and
+.Fa b2 .
+.Pp
+Additionally, their running times are independent of the byte sequences compared,
+making them safe to use for comparing secret values such as cryptographic MACs.
+In contrast,
+.Xr bcmp 3
+and
+.Xr memcmp 3
+may short-circuit after finding the first differing byte.
+.Sh RETURN VALUES
+The
+.Fn timingsafe_bcmp
+function returns 0 or 1 if the byte sequence pointed to by
+.Fa b1
+compares equal to or not equal to (respectively)
+the byte sequence pointed to by
+.Fa b2 .
+.Pp
+The
+.Fn timingsafe_memcmp
+function returns \-1, 0, or 1 if the byte sequence pointed to by
+.Fa b1
+compares less than, equal to, or greater than (respectively)
+the byte sequence pointed to by
+.Fa b2 .
+.Pp
+Note that these return values are compatible with, but stricter than,
+the ones specified for
+.Xr bcmp 3
+and
+.Xr memcmp 3 .
+.Sh SEE ALSO
+.Xr bcmp 3 ,
+.Xr memcmp 3
+.Sh STANDARDS
+The
+.Fn timingsafe_bcmp
+and
+.Fn timingsafe_memcmp
+functions are
+.Ox
+extensions.
+.Sh HISTORY
+The
+.Fn timingsafe_bcmp
+function first appeared in
+.Ox 4.9 .
+.Pp
+The
+.Fn timingsafe_memcmp
+function first appeared in
+.Ox 5.6 .
diff --git a/src/lib/libc/string/timingsafe_memcmp.c b/src/lib/libc/string/timingsafe_memcmp.c
new file mode 100644
index 0000000000..04e2ac5e20
--- /dev/null
+++ b/src/lib/libc/string/timingsafe_memcmp.c
@@ -0,0 +1,46 @@
+/*      $OpenBSD: timingsafe_memcmp.c,v 1.1 2014/06/13 02:12:17 matthew Exp $   */
+/*
+ * Copyright (c) 2014 Google Inc.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <limits.h>
+#include <string.h>
+
+int
+timingsafe_memcmp(const void *b1, const void *b2, size_t len)
+{
+        const unsigned char *p1 = b1, *p2 = b2;
+        size_t i;
+        int res = 0, done = 0;
+
+        for (i = 0; i < len; i++) {
+                /* lt is -1 if p1[i] < p2[i]; else 0. */
+                int lt = (p1[i] - p2[i]) >> CHAR_BIT;
+
+                /* gt is -1 if p1[i] > p2[i]; else 0. */
+                int gt = (p2[i] - p1[i]) >> CHAR_BIT;
+
+                /* cmp is 1 if p1[i] > p2[i]; -1 if p1[i] < p2[i]; else 0. */
+                int cmp = lt - gt;
+
+                /* set res = cmp if !done. */
+                res |= cmp & ~done;
+
+                /* set done if p1[i] != p2[i]. */
+                done |= lt | gt;
+        }
+
+        return (res);
+}
diff --git a/src/regress/lib/libc/timingsafe/timingsafe.c b/src/regress/lib/libc/timingsafe/timingsafe.c
index 9ecac93c09..e7807db258 100644
--- a/src/regress/lib/libc/timingsafe/timingsafe.c
+++ b/src/regress/lib/libc/timingsafe/timingsafe.c
@@ -1,4 +1,4 @@
-/*      $OpenBSD: timingsafe.c,v 1.1 2014/06/13 01:55:02 matthew Exp $  */
+/*      $OpenBSD: timingsafe.c,v 1.2 2014/06/13 02:12:17 matthew Exp $  */
 /*
  * Copyright (c) 2014 Google Inc.
  *
@@ -42,21 +42,17 @@ check()
         /* Check for reflexivity. */
         ASSERT_EQ(0, timingsafe_bcmp(bufone, bufone, N));
         ASSERT_EQ(0, timingsafe_bcmp(buftwo, buftwo, N));
-#if notyet
         ASSERT_EQ(0, timingsafe_memcmp(bufone, bufone, N));
         ASSERT_EQ(0, timingsafe_memcmp(buftwo, buftwo, N));
-#endif
 
         /* Check that timingsafe_bcmp returns 0 iff memcmp returns 0. */
         ASSERT_EQ(cmp == 0, timingsafe_bcmp(bufone, buftwo, N) == 0);
 
-#if notyet
         /* Check that timingsafe_memcmp returns cmp... */
         ASSERT_EQ(cmp, timingsafe_memcmp(bufone, buftwo, N));
 
         /* ... or -cmp if the argument order is swapped. */
         ASSERT_EQ(-cmp, timingsafe_memcmp(buftwo, bufone, N));
-#endif
 }
 
 int