[Cryptography] Implementing constant-time string comparison

[ianG]

On 17/06/2014 20:36 pm, sycamoreone wrote:

> Why are other libraries not doing this? That is, is this paranoid,
> or merely taking constant-time serious? Or does the 'unusual' return
> statement serve another purpose?

> http://codahale.com/a-lesson-in-timing-attacks/  suggested this
> Java implementation for Keyzar:
> 
> public static boolean isEqual(byte[] a, byte[] b) {
>     if (a.length != b.length) {
>         return false;
>     }
> 
>     int result = 0;
>     for (int i = 0; i < a.length; i++) {
>       result |= a[i] ^ b[i]
>     }
>     return result == 0;
> }


That's what I do.  My code below, fwiw.



    /**
     * Constant Time Equality of two byte arrays.
     *
     * Constant time is only reliable to the extent that the arrays
     * are of the same length.
     * (It could be organised to be CT if one of them is null, but that
     * seems like broken code to rely on such a thing, and any trickery
     * might not survive the JIT.)
     *
     * @param one is a byte array of any length, else null
     * @param two ditto
     * @return true if the arrays are byte/bit-wise equal,
     *         true if both null, false if one only null,
     *         false if different lengths
     * @see webfunds.util.Equals which is more comprehensive and
     *       adds noisy()
     */
    public static final boolean ctEquals(final byte[] one, final byte[] two)
    {
        if (one == null && two == null)                  return true;
        if (one == null || two == null)                  return false;
        if (one.length != two.length)                    return false;

        int xorDiffs = 0;

        /*
         * Run through the entire array(s), and XOR them to highlight
         * any differing bits.  This is the contant time bit.
         */
        for (int i = 0; i < one.length; i++) {
            xorDiffs |= ((int)(one[i] ^ two[i])) & 0xff;
        }

        /*
         *
         * Original NaCl C code turns any zero into -1, any bits into
         * zero flipped those back to zero or -1 respectively,
         * so a definition of 0==equals, -1==differs was returned.
         *      return (1 & (((int)diffBits - 1) >>> 8)) - 1;
         * The problem with this is that we have to turn it into
         * a boolean here, so the CT maths don't gain us anything,
         * and even in C, the caller is likely to do the same thing...
         */
        return 0 == xorDiffs ;
    }