Information Security
cryptography programming timing-attack
Updated Sat, 23 Jul 2022 14:22:23 GMT

Simple string comparisons not secure against timing attacks


As I learned in a comment for How to encrypt in PHP, properly?, I was told using a string comparison like the following in PHP is susceptible to timing attacks. So it should not be used to compare two MACs or hashes (also password hashes) for equality.

if ($hash1 === $hash2) {
   //mac verification is OK
   echo "hashs are equal"
} else {
  //something bad happenend
  echo "hashs verification failed!";
}

Can someone please detail me what exactly the problem is, how an attack would look like and possibly provide a secure solution that avoid this particular problem. How should it be done correctly? Is this a particular Problem of PHP or do other languages like e.g. Python, Java, C++, C etc. have the same issues?

Solution

I will add a list with time constant functions for different languages:

PHP:

Discussion: https://wiki.php.net/rfc/timing_attack

bool hash_equals ( string $known_string , string $user_string )

http://php.net/manual/en/function.hash-equals.php

Java Discussion : http://codahale.com/a-lesson-in-timing-attacks/

public static boolean  MessageDigest.isEqual(byte[] digesta, byte[] digestb)

http://docs.oracle.com/javase/7/docs/api/java/security/MessageDigest.html#isEqual(byte[],%20byte[])

C/C++ Discussion: https://cryptocoding.net/index.php/Coding_rules

int util_cmp_const(const void * a, const void *b, const size_t size) 
{
  const unsigned char *_a = (const unsigned char *) a;
  const unsigned char *_b = (const unsigned char *) b;
  unsigned char result = 0;
  size_t i;
  for (i = 0; i < size; i++) {
    result |= _a[i] ^ _b[i];
  }
  return result; /* returns 0 if equal, nonzero otherwise */
}

More I found here: http://www.levigross.com/2014/02/07/constant-time-comparison-functions-in-python-haskell-clojure-java-etc/

Python (2.x):

#Taken from Django Source Code
def constant_time_compare(val1, val2):
    """
    Returns True if the two strings are equal, False otherwise.
    The time taken is independent of the number of characters that match.
    For the sake of simplicity, this function executes in constant time only
    when the two strings have the same length. It short-circuits when they
    have different lengths.
    """
    if len(val1) != len(val2):
        return False
    result = 0
    for x, y in zip(val1, val2):
        result |= ord(x) ^ ord(y)
    return result == 0

Python 3.x

#This is included within the stdlib in Py3k for an C alternative for Python 2.7.x see https://github.com/levigross/constant_time_compare/
from operator import _compare_digest as constant_time_compare
# Or you can use this function taken from Django Source Code
def constant_time_compare(val1, val2):
    """
    Returns True if the two strings are equal, False otherwise.
    The time taken is independent of the number of characters that match.
    For the sake of simplicity, this function executes in constant time only
    when the two strings have the same length. It short-circuits when they
    have different lengths.
    """
    if len(val1) != len(val2):
        return False
    result = 0
    for x, y in zip(val1, val2):
        result |= x ^ y
    return result == 0

Haskell

import Data.Bits
import Data.Char
import Data.List
import Data.Function
-- Thank you Yan for this snippet 
constantTimeCompare a b =
  ((==) `on` length) a b && 0 == (foldl1 (.|.) joined)
  where
    joined = zipWith (xor `on` ord) a b

Ruby

def secure_compare(a, b)
     return false if a.empty? || b.empty? || a.bytesize != b.bytesize
     l = a.unpack "C#{a.bytesize}"
     res = 0
     b.each_byte { |byte| res |= byte ^ l.shift }
     res == 0
   end

Java (general)

// Taken from http://codahale.com/a-lesson-in-timing-attacks/
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;
}




Comments (3)

  • +0 – Thanks for providing these, particularly the C version. This can be adapted to any language, for example if your PHP needs to be compatible with PHP < 5.6 which doesn't have the "hash_equals" function. — Oct 28, 2016 at 04:14  
  • +1 – Don't check length first and then fall out, since that leaks length info. ALWAYS hash each string and then check length of original. — Jan 28, 2017 at 17:48  
  • +0 – Besides the C version, OpenSSL has CRYPTO_memcmp which you could use with implementations in assembly. Note that you must check string size equality or hash strings yourself, since it compares only up to the specified len. — Aug 18, 2019 at 13:54  

External Links

External links referenced by this document:

References