How does ConstantTimeByteEq work?

Question

In Go's crytography library, I found this function ConstantTimeByteEq. What does it do, how does it work?

// ConstantTimeByteEq returns 1 if x == y and 0 otherwise.
func ConstantTimeByteEq(x, y uint8) int {
    z := ^(x ^ y)
    z &= z >> 4
    z &= z >> 2
    z &= z >> 1

    return int(z)
}

Answer 1

x ^ y is x XOR y, where the result is 1 when the arguments are different and 0 when the arguments are the same:

x            = 01010011
y            = 00010011
x ^ y        = 01000000

^(x ^ y) negates this, i.e., you get 0 when the arguments are different and 1 otherwise:

^(x ^ y)     = 10111111 => z

Then we start shifting z to the right for masking its bits by itself. A shift pads the left side of the number with zero bits:

z >> 4       = 00001011

With the goal of propagating any zeros in z to the result, start ANDing:

z            = 10111111
z >> 4       = 00001011
z & (z >> 4) = 00001011

also fold the new value to move any zero to the right:

z            = 00001011
z >> 2       = 00000010
z & (z >> 2) = 00000010

further fold to the last bit:

z            = 00000010
z >> 1       = 00000001
z & (z >> 1) = 00000000

On the other hand, if you have x == y initially, it goes like this:

z            = 11111111
z (& z >> 4) = 00001111
z (& z >> 2) = 00000011
z (& z >> 1) = 00000001

So it really returns 1 when x == y, 0 otherwise.

Generally, if both x and y are zero the comparison can take less time than other cases. This function tries to make it so that all calls take the same time regardless of the values of its inputs. This way, an attacker can't use timing based attacks.

Answer 2

It does exactly what the documentation says: It checks if x and y are equal. From a functional point it is just x == y, dead simple.

Doing x == y in this cryptic bit-fiddling-way prevent timing side attacks to algorithms: A x == y may get compiled to code which performs faster if x = y and slower if x != y (or the other way around) due to branch prediction in CPUs. This can be used by an attacker to learn something about the data handled by the cryptographic routines and thus compromise security.