¿Se compara el tiempo constante cuando los tamaños de matriz no son iguales?

1

¿Cuál es la forma preferida o recomendada para buscar comparaciones con el tiempo de los concursantes cuando las longitudes de la matriz no son iguales?

¿Deberíamos salir lo antes posible? Algo como:

if (array1.size() != array2.size()) {
    return NOT_EQUAL;
}

int accum = 0;
for(int i = 0; i < array1.size(); i++) {
    accum |= array1[i] ^ array2[i];
}

return (accum == 0) ? EQUAL : NOT_EQUAL;

¿O deberíamos evitar la salida temprana y comparar tanto como sea posible con la esperanza de enmascarar tanto como sea posible? Algo como:

int size = min(array1.size(), array2.size());
int accum = (array1.size() ^ array2.size());

for(int i = 0; i < size; i++) {
    accum |= array1[i] ^ array2[i];
}

return (accum == 0) ? EQUAL : NOT_EQUAL;

¿O algo más?

¿O es esta pregunta más apropiada para la gente en Crypto.SE debido a su minuciosidad teórica?

EDIT : esto parece estar relacionado con Ataques de tiempo en los hashes de contraseñas . Pero la pregunta citada es un ejemplo particular del problema generalizado (y estoy interesado en la pregunta generalizada).

No estoy seguro de estar de acuerdo con la respuesta o afirmación de la pregunta citada de que "El uso de los ataques de tiempo en este caso no le dirá a un atacante más de lo que sabría si tuviera el hash y la sal almacenados. ... " porque el atacante podría estar intentando recuperar la contraseña de hash a través de ataques de tiempo. Dada una contraseña con hash, en algunos casos solo es un salto a la contraseña.

    
pregunta jww 05.01.2015 - 01:15
fuente

3 respuestas

1

Abortar temprano está bien, ya que no revela la sincronización de nada secreto (a menos que consideres que la longitud sea un secreto, lo que no parece plausible).

En cuanto a su edición, también está bien comparar hashes de contraseña en tiempo no constante. El atacante no tiene un mecanismo eficiente para "elegir" salidas de hash de contraseñas, de modo que pueda recorrer todas las posibilidades de un byte en una posición mientras mantiene constantes los bytes anteriores. Por lo tanto, nuevamente no hay un ataque de tiempo, ni siquiera para revelar la contraseña con hash.

    
respondido por el Stephen Touset 05.01.2015 - 02:00
fuente
1

Problema: desea comparar dos secuencias, una secuencia proporcionada por el usuario U[] y una secuencia secreta S[] cuya longitud desea mantener en secreto. No desea revelar, a través del tiempo transcurrido de comparación, si S es más corto que U o la longitud del prefijo común de U y S .

No puedes abortar la comparación después de alcanzar el final de S porque eso revelará la longitud de S . Tampoco puede abortar después de la primera falta de coincidencia porque eso revelará la longitud del prefijo común. Lo que puede hacer es repetir el último elemento en S hasta que llegue al final de U . Por ejemplo, si U es "goodbye" y S es "hello" , desea comparar como si fuera "hellooo" .

El siguiente código (no probado) en Python debería ilustrar el concepto:

def slow_seq_eq(userseq, secretseq):
    """Compare sequences without disclosing secretseq's length."""
    Silast = len(secretseq) - 1
    is_equal = True
    for Uidx in range(len(userseq)):
        Sidx = min(Uidx, Silast)  # Repeat the last element of S to len(U)
        if secretseq[Sidx] != userseq[Uidx]:
            is_equal = False
    if len(U) != len(S):
        is_equal = False
    return is_equal

Esto, por supuesto, supone que el operador de comparación != toma tiempo constante, al igual que el operador de indexación. La organización de S para ubicarse en una cierta alineación en relación con las líneas de caché o las páginas de memoria virtual podría, en teoría, mantener vivo el ataque de sincronización.

    
respondido por el Damian Yerrick 06.01.2015 - 02:08
fuente
1

Si los datos con los que está comparando no son secretos, entonces realmente no importa lo que haga. Los ataques de tiempo se utilizan para obtener información a la que aún no tiene acceso. Si ya tiene acceso, el ataque no es necesario.

Si está protegiendo un secreto, entonces no importa si es una contraseña o no. Debes manejarlo de la misma manera, con las mismas precauciones. Con el fin de evitar la sincronización de los canales laterales, se asegura de que la longitud de entrada sea la misma que la del valor almacenado, haciendo un hash entre ambos y haciendo una comparación de tiempo constante. Por supuesto, debe almacenar el valor de hash del valor almacenado en la base de datos, de modo que no lo vuelva a calcular cada vez. Vea el pseudocódigo a continuación.

Pseudocódigo para comparaciones constantes de tiempo:

bool compareToSecret(input/* input from user*/)
  dbHash = getSecretFromDb()

  inHash = hash(input); // sha256, bcrypt or whatever. Attacker 
                        // knows how long this takes, but it 
                        // doesn't get her anything

  // at this point, both inhash and dbhash are the same length.

  // the following loop is constant order time. Hashes are always the
  // same length, and all values of the hashes are always compared
  bool result = true
  int len = strlen(inHash)
  for( int i=0; i<len; i++ )
     result &= (inHash[i] == dbHash[i])

  return result

abortar temprano durante la comparación

Abortar temprano durante la comparación es problemático, ya que filtra información sobre la comparación y se puede usar para aprender la contraseña directamente.

  1. El atacante intenta secretos de longitud 1. Uno de estos secretos tardará unos milisegundos más en regresar que los otros, ya que hay un secreto de 1 longitud cuyo primer carácter coincide con el secreto almacenado. El atacante aprende el primer personaje del secreto.
  2. El atacante intenta 2 todos los secretos de carácter con la primera letra que comienza con un valor correcto conocido. Uno de estos secretos será unos milisegundos más rápido, ya que el segundo personaje se compara correctamente.
  3. El atacante se repite, atacando por separado a cada personaje del secreto. Finalmente, el atacante aprende el secreto almacenado.

Esto es más rápido que un ataque de fuerza bruta, porque el atacante puede atacar a cada personaje por separado en lugar de todo el secreto a la vez.

abortando temprano: antes de comparar

Abortar temprano, como lo menciona Steven Tousset, filtra la longitud del secreto. Esto no parece mucho al principio, pero le permite al atacante acelerar su ataque en órdenes de magnitud. Digamos que el sistema acepta secretos de longitud 1-5. Manteniéndolo muy simple, el secreto está compuesto solo de dígitos. Por lo tanto, hay 10 + 100 + 1,000 + 10,000 + 100,000 = 111,110 valores posibles. Un ataque de fuerza bruta necesita hacer aproximadamente 100,000 pruebas para probar todos los valores posibles.

Si el sistema le permite al atacante saber la longitud del secreto, un atacante puede reducir dramáticamente la cantidad de valores que necesita probar probando primero 5 valores: '1', '12', '123', '1234', y '12345'. Ahora el atacante sabe cuanto tiempo es el secreto. Si es 1 personaje, ahora solo tiene que hacer 10 pruebas en lugar de cien mil. Si tiene 2 caracteres, solo necesita hacer 100 pruebas. Sin este dato clave, el atacante necesita realizar muchas más pruebas antes de que encuentren el secreto.

otro problema: almacenamiento recuperable

También hay otro problema. Si el secreto conocido puede compararse con el valor de entrada, entonces tiene que almacenar el secreto en forma recuperable. Busque en este sitio los detalles relacionados con las contraseñas, pero esto a menudo se considera una mala práctica con el almacenamiento de contraseñas y debe evitarse. En general, con cualquier tipo de secreto, si no es absolutamente necesario tener el valor en bruto, no debe almacenarse en forma recuperable. El almacenamiento irrecuperable evita varios ataques, ya que su secreto depende de cómo lo use.

una cosa más: optimización del compilador

El código, a continuación, es un pseudo código. Si tuviera que pasar su equvalente a través de un compilador o un tiempo de ejecución que realiza la optimización, entonces debe tener mucho cuidado para asegurarse de que el código no se optimice. Hay varios trucos en diferentes idiomas, que están fuera del alcance de este comentario. Gracias a @Polynomial para recordarlo

    
respondido por el atk 05.01.2015 - 03:37
fuente

Lea otras preguntas en las etiquetas