Las comparaciones de cadenas simples no son seguras contra los ataques de tiempo [duplicado]

14

Como aprendí en un comentario para ¿Cómo cifrar en PHP, correctamente? , me dijeron que usar una comparación de cadenas como la siguiente en PHP es susceptible de ataques de tiempo. Por lo tanto, no debe utilizarse para comparar dos MAC o hashes (también hashes de contraseña) para la igualdad.

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

¿Puede alguien, por favor, detallarme cuál es exactamente el problema, cómo sería un ataque y posiblemente proporcionar una solución segura que evite este problema en particular? ¿Cómo debe hacerse correctamente? ¿Es este un problema particular de PHP o lo hacen otros lenguajes como, por ejemplo, Python, Java, C ++, C, etc. tienen los mismos problemas?

    
pregunta evildead 12.03.2015 - 20:27
fuente

3 respuestas

15

El problema aquí es que las funciones de comparación de cadenas genéricas regresan tan pronto como encuentran una diferencia entre las cadenas. Si el primer byte es diferente, regresan después de solo mirar un byte de las dos cadenas. Si la única diferencia está en el último byte, procesan ambas cadenas completas antes de regresar. Esto acelera las cosas en general, lo que normalmente es bueno. Pero también significa que alguien que puede decir cuánto tiempo se tarda en comparar las cadenas puede hacer una buena suposición de cuál es la primera diferencia.

En un escenario de ataque, un atacante tiene el control total de $mac1 (se toma del mensaje creado por el atacante), mientras que $mac2 es el MAC real válido para el mensaje del atacante. $mac2 debe permanecer en secreto del atacante, o puede pegarlo en su mensaje y así forjar un mensaje válido. El atacante, al analizar el tiempo que lleva obtener una respuesta, probablemente puede averiguar dónde está la primera diferencia entre su MAC y la real. Puede probar todas las posibilidades para ese byte, encontrar el correcto y luego trabajar en el siguiente byte seguro sabiendo que los primeros k bytes son correctos. Al final, probó solo 256 * len MAC (si len es la longitud del MAC) en lugar de 256 len, debería haberlo intentado.

    
respondido por el cpast 12.03.2015 - 21:50
fuente
16

Agregaré una lista con funciones de constante de tiempo para diferentes idiomas:

PHP :

Discusión: enlace

bool hash_equals ( string $known_string , string $user_string )

enlace

Java Discusión: enlace

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

enlace

C / C ++ Discusión: enlace

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 */
}

Más encontré aquí: enlace

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;
}
    
respondido por el evildead 12.03.2015 - 23:49
fuente
2

Los ataques de temporización contra comparaciones de cadenas no son específicos de PHP. Funcionan en cualquier contexto en el que una cadena provista por el usuario se verifique con una cadena secreta utilizando el algoritmo de comparación estándar de "cortocircuito" (la verificación se detiene en el primer byte no coincidente). Esto se aplica a PHP, Python, C e incluso a sistemas de bases de datos como MySQL.

El enfoque estándar para este problema es iterar siempre en todos los bytes de la cadena, independientemente del contenido. Como pseudo código:

function safe_string_comp(str_1, str_2):
    if byte_length(str_1) =/= byte_length(str_2):
        return FALSE
    else:
        comparison_bit := 0  // 0 if the strings match, 1 otherwise
        for i := 0, i < byte_length(str_1), i := i + 1:
           comparison_bit := comparison_bit | (str_1[i] ^ str_2[i])

        return comparison_bit == 0

El símbolo | denota el operador de bit cowise OR , y ^ es el bit de sabios XOR .

Las versiones recientes de PHP (> = 5.6.0) ya tienen una función incorporada llamada hash_equals . Si no está disponible, se debe implementar el algoritmo anterior. Por lo tanto, una función de comparación de cadenas segura en el tiempo puede tener este aspecto:

<?php

/**
 * Count the number of bytes in a string.
 *
 * Note that the strlen() function is ambiguous, because it will either return the number of *bytes* or the
 * number of *characters* with regard to mb_internal_encoding(), depending on whether the Mbstring extension
 * has overloaded the string functions:
 * http://php.net/manual/en/mbstring.overload.php
 *
 * For example, the non-overloaded strlen() function returns 2 for the string "\xC3\x84". However, if the
 * function is overloaded and the internal encoding set to UTF-8, the same string is interpreted as a single
 * character, namely the "Ä" umlaut. So the function returns 1 in this case.
 */
function byte_length($binary_string)
{
    if (extension_loaded('mbstring'))
        return mb_strlen($binary_string, '8bit');
    else
        return strlen($binary_string);
}



/**
 * Timing-safe string comparison.
 *
 * The standard string comparison algorithm stops as soon as it finds a non-matching byte. This leaks information
 * about the string contents through time differences, because the longer the common prefix, the longer the
 * comparison takes (e. g. checking "aaax" against "aaaa" theoretically requires slightly more time than checking
 * "xaaa" against "aaaa").

 * To avoid this problem in security contexts like MAC verification, iterate over *all* bytes of the strings
 * regardless of the content.
 */
function secure_string_equals($string_1, $string_2)
{
    // Use built-in hash_equals() function if available (PHP >= 5.6.0)
    if (function_exists('hash_equals'))
    {
        return hash_equals($string_1, $string_2);
    }
    else
    {
        $equals = false;

        if (!is_string($string_1) || !is_string($string_2))
        {
            trigger_error('One of the arguments is not a string.', E_USER_ERROR);
        }

        if (byte_length($string_1) == byte_length($string_2))
        {
            // 0 if the strings are equal, 1 otherwise
            $comparison_bit = 0;
            for ($byte_index = 0; $byte_index < byte_length($string_1); $byte_index++)
            {
                $comparison_bit |= ord($string_1[$byte_index]) ^ ord($string_2[$byte_index]);
            }

            $equals = ($comparison_bit == 0);
        }

        return $equals;
    }
}
    
respondido por el Fleche 13.03.2015 - 00:30
fuente

Lea otras preguntas en las etiquetas