Ser capaz de procesar cadenas de longitud arbitraria sin perder información sobre su longitud parece ser muy difícil (es decir, no veo cómo hacerlo) debido a cachés . Una cadena muy larga, por definición, tomará mucho espacio, y así la lectura de la cadena incurrirá en interacción con los cachés. El acceso a la cadena desde la RAM provocará errores de caché y también desalojará otros elementos de datos de las cachés, lo que afectará el comportamiento futuro del código de la aplicación. Una falta de caché cuesta docenas o incluso cientos de ciclos de reloj: es al menos diez veces más visible, desde el exterior, que una predicción errónea de una rama. Si te preocupas por las sucursales, deberías preocuparte mucho más por los cachés.

Sin embargo, podemos hacer trampa con relleno . Supongamos que puede organizar que las dos cadenas que desea comparar se escriban al comienzo de dos búferes grandes de igual tamaño llenos de ceros; también, suponemos que un byte de valor 0 no puede aparecer en una cadena normal (por ejemplo, estas son cadenas C). Entonces todo lo que necesita es hacer una comparación sin fugas de los dos buffers , que tienen la misma longitud. La longitud del búfer se filtrará, pero es un parámetro fijo, constante y conocido públicamente, por lo que no es un problema.

Esto no resuelve el problema; lo mueve Ahora, debe asegurarse de que lo que sea que produzca las cadenas pueda escribirlas en los buffers sin perder información de tamaño. En términos generales, ya no tienes cadenas . Tiene valores binarios de una longitud fija dada que copia con un gran memcpy() ; resulta que estos valores tienen una interpretación de cadena en la que los bytes se consideran caracteres, hasta el primer byte de valor cero.

Desde un punto de vista más alto, tener una "función de comparación segura de cadenas" es como llevar un cubo a bordo del Titanic. Si su código está manejando datos secretos, entonces todo que haga con los datos está potencialmente sujeto a ataques de tiempo. En general, su aplicación puede ser de dos tipos:

• Si la parte secreta only es un único elemento criptográfico y todo lo demás es público, entonces usar algunas primitivas sin fugas tiene sentido y mejorará la seguridad general. Un ejemplo clásico es una Autoridad de certificación , donde la única parte secreta es la clave privada de CA. Mientras el algoritmo de firma no filtre secretos, todo el sistema es robusto contra los ataques de tiempo. De manera similar, un sitio web que realice autenticación basada en contraseña pero que, de lo contrario, contenga solo datos públicos, estará bien.

• Si el secreto se extiende por todo el sistema, como un sitio web que realiza autenticación basada en contraseña para dar acceso a algunos datos confidenciales, entonces concentrarse en la comparación de cadenas no es el adecuado. El código completo del servidor debe estar libre de fugas, y es un esfuerzo considerablemente más difícil (y no sabemos realmente cómo hacerlo).

En cualquier caso, tratar de proteger cualquier parte del código contra ataques de canal lateral se vuelve más difícil cuando el lenguaje es más "de alto nivel". Un lenguaje como PHP, con su gestión de memoria automática (el recolector de basura) y la gestión de cadenas (las cadenas son valores al igual que los enteros) no ayudará en absoluto. Esa es la razón por la que se deben proporcionar primitivas de bajo nivel implementadas en C (como una función de comparación de cadenas sin fugas), pero el problema es mucho más grande y también abarca una gran cantidad de código PHP.

Si asumes un adversario que puede observar los patrones de acceso a la memoria a través de las filtraciones de caché, es una tontería tratar de proteger al adversario que aprende la longitud del secreto. Él siempre lo sabrá. La única forma de protegerse contra esto es garantizar que pueda acceder más allá del final de la cadena sin segfault, lo cual es casi seguro que no puede hacer sin sobrepasar cada cadena en el lenguaje de programación.

¿Ha investigado las necesidades de los programadores de PHP que desean esta función?

En las aplicaciones prácticas que se me ocurren: verificación de contraseñas, tokens de sesión, etc. la cadena conocida sería relativamente pequeña, digamos < 64 bytes; dentro de una línea de caché de Intel. Por lo tanto, su implementación trivial en realidad no causaría diferentes patrones de acceso al caché.

Si realmente necesitas comparar cadenas largas sin pérdida de longitud, debes considerar comparar hashes en su lugar.

Corríjame si me equivoco (en respuesta a Thomas, pero también para responder a la pregunta original en general), pero debería poder esforzarse para lograr verificaciones sin fugas con su código. En este ejemplo, "conocido" es un valor conocido, que se ha incorporado previamente en un búfer, es decir, Si su valor conocido es "qwerty", y permite una longitud máxima de 64, entonces "qwerty" se rellena previamente (se inicializa y almacena una sola vez en el tiempo de carga) en un búfer de 64, lo que garantiza que las cargas de memoria siempre deben ser constantes sin regalar nada). En este caso, solo sabremos si está en caché o no por una falta de caché. Replicando el código en la publicación original.

int check(char *known, size_t known_len, char *unknown, size_t unknown_len, size_t max_len) {

size_t i;
int result = 0;

  // Constant time check, only gives away maximum length.
  if (unknown_len > max_len)
      return 0;

  // Will only give away the length of the attackers string, unless it was already too large (condition above).  Don't bother doing an extra memcpy on your known or the attackers.
  for (i = 0; i < unknown_len; i++) {
      result |= known[i] ^ unknown[i];
  }

  return result == 0 ? 1 : 0;
}

Simplemente ...

... no compare cadenas , compare sus hashes !

Sí, me refiero a esto por seguridad de tiempo (el efecto secundario de la seguridad de contraseña, dejado de lado).

Lo que esto hace

Al comparar hashes, no necesita preocuparse por seguir (lo que podría no ser obvio al principio)

• El proceso de hash toma más tiempo, para cadenas más largas

  ¿Por qué? El hash correcto con el que está comparando la entrada del usuario es (obviamente) de una longitud fija, la única información que puede obtener un usuario es el tiempo que tarda el programa en hacer su entrada (la peor En este caso, esto podría dar algunos consejos sobre el algoritmo de hash subyacente, que no debe confiarse en el secreto de todos modos.

  La única excepción es, si no puede almacenar el hash correcto en algún lugar. Tener que calcularlo primero, también conocido como tratar con la contraseña directamente , trae los mismos problemas de longitud / contraseña exactamente.

• Fallos en la predicción de la sucursal o en el caché

  Obviamente, como se mencionó anteriormente, el hash correcto siempre tiene la misma longitud, sin importar cuánto tiempo tenga la contraseña correcta de cualquier usuario.

En serio, este proceso fácil hace que un problema trivial sea muy difícil.

Acerca de Hash Strength

Si está utilizando un proceso de hash débil (o uno con una entropía ridícula), podría considerar verificar la igualdad de contraseña directa (después de un resultado positivo de comparar hashes), para protegerse contra colisiones.

Sin embargo, esto podría filtrar la información de tiempo / tardar más tiempo, cuando se encuentre con una colisión.

Línea inferior: ¡No uses algoritmos de hash débiles, aplica sal, y deberías estar bien! ;-)