Comparing Byte Arrays

Comparing two-byte arrays for equality is not only one of the most primitive reusable operations, but it is also one of the most commonly used in cryptography. The fundamental requirement for a byte array comparison (BAC) is to return true if two-byte arrays are equal, and false otherwise. Two-byte arrays are equal when their lengths are equal and all byte pairs in corresponding array positions are also equal.

BAC gets an important additional security requirement when used in security constructs: BAC implementation should not leak any information about the data within the two arrays being compared for equality.

Direct comparison (insecure)

Code Listing 6

Direct comparison implements the fundamental BAC requirement, but it also makes a variable number of comparisons based on the position of the first unequal byte pair, which leaks timing information that can help mount effective guessing attacks to uncover the data. These types of attacks are known as side-channel attacks (the side channel in this case is timing). You should never use direct comparison with sensitive or secret data.

AND comparison

Code Listing 7

The AND comparison is similar to a direct comparison that keeps comparing byte pairs even after the result is determined to be false. It performs a fixed amount of work in every comparison, which protects against timing attacks. AND comparison is the BAC approach used by Microsoft within their internal CryptoUtil classes (System.Web.Security.Cryptography namespace—System.Web assembly and System.Web.Helpers namespace—System.Web.WebPages assembly).

XOR comparison

Code Listing 8

XOR comparison exploits the fact that equal byte pairs XOR to zero and OR-ing all XOR-ed results together would only produce zero if all byte pairs are equal. The XOR approach might have a slight advantage over the AND approach because the XOR-OR combination is pure bit shifting, and is typically compiled into direct assembly equivalents, while Boolean AND combination can be compiled into conditional branching instructions, which might have different timings.

Double-HMAC comparison

The AND and XOR approaches force you to make certain assumptions about potential timing variabilities in the implementation of basic operations on a particular platform. Microsoft’s implementation of .NET runs on Windows, where Microsoft has a good understanding and control of how compilation happens. Other .NET implementations, such as Mono, might also target specific platforms and have a good handle on what assembly-level code is produced.

There might be scenarios, however, where you are not comfortable making specific assumptions about the implementation of low-level primitives such as Boolean logic or bit-shifting operations. In these scenarios, you can do a random-key HMAC of both arrays first, and then do BAC on the HMAC results rather than on the original arrays. Once you replace the original arrays with their HMAC equivalents, the choice of BAC is no longer important: you can use either one.

Code Listing 9

Note that when Xor(aHMAC, bHMAC) returns true, we actually return the result of an additional Xor(a, b). The reason is that fixed-length digests such as hash functions and HMAC are guaranteed to have domain collisions. There must exist two arbitrary-length unequal arrays a and b, which produce the same fixed-length hash/HMAC value. You cannot come up with such a and b, but they do exist. We perform an additional BAC on (a, b) directly in order to ensure that such collisions, when they happen, do not lead to a false positive result.

The double-HMAC approach is obviously slower and more complex than all other approaches discussed so far. We prefer the XOR approach for all Microsoft .NET-to-MSIL languages (C#, VB.NET, F#), and the double-HMAC approach for languages that ship source code to be compiled with an undetermined compiler (JavaScript).