8
\$\begingroup\$

I am writing a function that does a constant time compare of two byte arrays. I want it to be constant time to insure there is no side channel attacks possible.

  1. Does the code protect against timing attacks or other side channel attacks (of which I could fix)
  2. Any other suggestions for improvements

Note: This code is called infrequently so performance is not a big deal

/// <summary>
/// Performs a comparison of two identical sized byte arrays. 
/// Performs in constant time to prevent timing/side channel attacks
/// </summary>
public int CompareConstantTime(byte[] bytesA, byte[] bytesB)
{
    if (bytesA == null)
        throw new ArgumentNullException(nameof(bytesA));
    if (bytesB == null)
        throw new ArgumentNullException(nameof(bytesB));
    if (bytesA.Length != bytesB.Length)
        throw new ArgumentOutOfRangeException("byte length must be equal");

    //only the lest significant bit is used
    int aIsLarger = 0;
    int bIsLarger = 0;

    unchecked
    {
        for (int i = 0; i < bytesA.Length; i++)
        {
            int byteA = bytesA[i];
            int byteB = bytesB[i];

            int byteAIsLarger = ((byteB - byteA) >> 8) & 1;
            int byteBIsLarger = ((byteA - byteB) >> 8) & 1;

            aIsLarger = aIsLarger | (byteAIsLarger & ~bIsLarger);
            bIsLarger = bIsLarger | (byteBIsLarger & ~aIsLarger);
        }

        //fixes to standard compaire results (0 if A = B, 1 if A > B, -1: B > A)
        int result = aIsLarger - bIsLarger;
        return result;
    }
}
\$\endgroup\$
8
  • \$\begingroup\$ @Vogel612, oh, I am pretty sure OP is not talking about time complexity, code in question is clearly O(N). He is talking about algorithm called constant time string/array comparison. See: security.stackexchange.com/questions/77428/… or crypto.stackexchange.com/questions/30958/… \$\endgroup\$
    – Nikita B
    Mar 6 '17 at 14:27
  • \$\begingroup\$ I feel like there isn't much to review code-style wise. And your questions about security will probably find a much better answer, if you ask them on the sites linked above. \$\endgroup\$
    – Nikita B
    Mar 6 '17 at 14:35
  • \$\begingroup\$ @NikitaB along with any security considerations I would also be grateful for any code-style type advice as well. Also you are correct in I am interested in constant time comparison. \$\endgroup\$
    – webwake
    Mar 6 '17 at 21:31
  • \$\begingroup\$ I'm not sure that sign extension doesn't leak information. This could both influence the conversion from byte to int as well as the subtraction right after that. I would at least perform int byteA = bytes[i] & 0xFF to get rid of the first sign extension. The deliberate underflow to negative values in the integer based calculation is probably all right, as internally they will just be registers - although setting the carry bit might still leak the tiniest bit of info. \$\endgroup\$ May 24 '17 at 13:28
  • \$\begingroup\$ If you would OR 100h to the integer values before subtraction you may be able to get rid of that as well (just thinking out loud here). \$\endgroup\$ May 24 '17 at 13:34
2
\$\begingroup\$

Some nitpicking:

/// <summary>
/// Performs a comparison of two identical sized byte arrays. 
/// Performs in constant time to prevent timing/side channel attacks
/// </summary>

This does not answer arguably the main question one would have: what does it mean for one array to be "larger" than another, when both have equal size? Do you compare sums of the elements? Do you compare first non-equal pair of elements (looks like this one is correct)? Do you use some other even less obvious criteria? You should explain this in above documentation, so it is not necessary to read through obscure boolean logic in order to get the answer.


public int CompareConstantTime(byte[] bytesA, byte[] bytesB)

This method should probably be refactored into static extension method, so it is easier to re-use if needed.

public static int ConstantTimeCompareTo(this byte[] bytes, byte[] otherBytes)

throw new ArgumentOutOfRangeException("byte length must be equal");

There is no range per se at this point. I think base ArgumentException is a better fit.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.