Add some utilities for comparing arrays without data-dependent branches

Lets arrays be compared without leaking information about their
contents caused by early exits etc.

2 files changed, 92 insertions, 0 deletions

diff --git a/security-utils/src/main/java/com/yahoo/security/SideChannelSafe.java b/security-utils/src/main/java/com/yahoo/security/SideChannelSafe.java
new file mode 100644
index 00000000000..1f160d94c6a
--- /dev/null
+++ b/security-utils/src/main/java/com/yahoo/security/SideChannelSafe.java
@@ -0,0 +1,54 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.security;
+
+/**
+ * Utility functions for comparing the contents of arrays without leaking information about the
+ * data contained within them via timing side-channels. This is done by avoiding any branches
+ * that depend on the array elements themselves. This inherently means that all operations have
+ * both an upper and a lower bound in processing time that is O(n) for an array of size n, as there
+ * can be no early exits.
+ *
+ * @author vekterli
+ */
+public class SideChannelSafe {
+
+    /**
+     * @return true iff all bytes in the array are zero. An empty array always returns false
+     *         since it technically can't contain any zeros at all.
+     */
+    public static boolean allZeros(byte[] buf) {
+        if (buf.length == 0) {
+            return false;
+        }
+        byte accu = 0;
+        for (byte b : buf) {
+            accu |= b;
+        }
+        return (accu == 0);
+    }
+
+    /**
+     * Compare two byte arrays without the use of data-dependent branching that may leak information
+     * about the contents of either of the arrays.
+     *
+     * <strong>Important:</strong> the <em>length</em> of the arrays is not considered secret, and
+     * will be leaked if arrays of differing sizes are given.
+     *
+     * @param lhs first array of bytes to compare
+     * @param rhs second array of bytes to compare
+     * @return true iff both arrays have the same size and are element-wise identical
+     */
+    public static boolean arraysEqual(byte[] lhs, byte[] rhs) {
+        if (lhs.length != rhs.length) {
+            return false;
+        }
+        // Only use constant time bitwise ops. `accu` will be non-zero if at least one bit
+        // differed in any byte compared between the two arrays.
+        byte accu = 0;
+        for (int i = 0; i < lhs.length; ++i) {
+            accu |= (lhs[i] ^ rhs[i]);
+        }
+        return (accu == 0);
+    }
+
+}
diff --git a/security-utils/src/test/java/com/yahoo/security/SideChannelSafeTest.java b/security-utils/src/test/java/com/yahoo/security/SideChannelSafeTest.java
new file mode 100644
index 00000000000..7a66ed6eb7f
--- /dev/null
+++ b/security-utils/src/test/java/com/yahoo/security/SideChannelSafeTest.java
@@ -0,0 +1,38 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.security;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/**
+ * _Functional_ test of side channel safe utility functions. Testing that they're actually
+ * (probably) side channel safe would be too flaky since it's inherently timing-dependent.
+ */
+public class SideChannelSafeTest {
+
+    @Test
+    void all_zeros_checks_length_and_array_contents() {
+        assertFalse(SideChannelSafe.allZeros(new byte[0]));
+        assertFalse(SideChannelSafe.allZeros(new byte[]{ 1 }));
+        assertTrue(SideChannelSafe.allZeros(new byte[]{ 0 }));
+        assertFalse(SideChannelSafe.allZeros(new byte[]{ 0, 0, 127, 0 }));
+        assertFalse(SideChannelSafe.allZeros(new byte[]{ 0, 0, -1, 0 }));
+        assertTrue(SideChannelSafe.allZeros(new byte[]{ 0, 0, 0 }));
+    }
+
+    @Test
+    void arrays_equal_checks_length_and_array_contents() {
+        assertTrue(SideChannelSafe.arraysEqual(new byte[0], new byte[0]));
+        assertFalse(SideChannelSafe.arraysEqual(new byte[] { 0 }, new byte[0]));
+        assertFalse(SideChannelSafe.arraysEqual(new byte[0], new byte[]{ 0 }));
+        assertTrue(SideChannelSafe.arraysEqual(new byte[] { 0, 0, 0 }, new byte[] { 0, 0, 0 }));
+        assertTrue(SideChannelSafe.arraysEqual(new byte[] { 0x7, 0xe }, new byte[] { 0x7, 0xe }));
+        assertFalse(SideChannelSafe.arraysEqual(new byte[] { 0xe, 0x7 }, new byte[] { 0x7, 0xe }));
+        assertFalse(SideChannelSafe.arraysEqual(new byte[] { -1, 127 }, new byte[] { 127, -1 }));
+        assertFalse(SideChannelSafe.arraysEqual(new byte[] { -1, -1, 1 }, new byte[] { -1, -1, 2 }));
+        assertFalse(SideChannelSafe.arraysEqual(new byte[] { 0, -1, 1 }, new byte[] { 0, -1, 3 }));
+    }
+
+}