Add timingsafe_memcmp().

ok deraadt, jmc, tedu

6 files changed, 154 insertions, 34 deletions

diff --git a/include/string.h b/include/string.h
index b0b851edafb..ffb034acdd0 100644
--- a/include/string.h
+++ b/include/string.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: string.h,v 1.27 2014/01/22 21:06:45 tedu Exp $	*/
+/*	$OpenBSD: string.h,v 1.28 2014/06/13 02:12:17 matthew Exp $	*/
 /*	$NetBSD: string.h,v 1.6 1994/10/26 00:56:30 cgd Exp $	*/
 
 /*-
@@ -138,6 +138,7 @@ size_t	 strlcpy(char *, const char *, size_t)
 void	 strmode(int, char *);
 char	*strsep(char **, const char *);
 int	 timingsafe_bcmp(const void *, const void *, size_t);
+int	 timingsafe_memcmp(const void *, const void *, size_t);
 #endif 
 __END_DECLS
 
diff --git a/lib/libc/string/Makefile.inc b/lib/libc/string/Makefile.inc
index 1f6d756182b..a293219058a 100644
--- a/lib/libc/string/Makefile.inc
+++ b/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/lib/libc/string/bcmp.3 b/lib/libc/string/bcmp.3
index 52584b4b838..720a8bf3040 100644
--- a/lib/libc/string/bcmp.3
+++ b/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/lib/libc/string/memcmp.3 b/lib/libc/string/memcmp.3
index ebd838825ad..25d308e6171 100644
--- a/lib/libc/string/memcmp.3
+++ b/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/lib/libc/string/timingsafe_bcmp.3 b/lib/libc/string/timingsafe_bcmp.3
new file mode 100644
index 00000000000..0886731ce7b
--- /dev/null
+++ b/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/lib/libc/string/timingsafe_memcmp.c b/lib/libc/string/timingsafe_memcmp.c
new file mode 100644
index 00000000000..04e2ac5e206
--- /dev/null
+++ b/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);
+}