MySQL OLD_PASSWORD cryptanalysis?

21

El hash de contraseña utilizado para las contraseñas de MySQL anteriores a la versión 4.1 (ahora llamado OLD_PASSWORD() ) parece un hash ad-hoc muy simple, sin recuentos de sales o iteraciones. Ver, por ejemplo, una implementación en Python en Fragmentos de Django: antiguo hash de contraseña de MySQL

¿Lo ha cryptanalizado? Roto?

Todo lo que veo en la web son ataques de fuerza bruta. Estos son muy exitosos para contraseñas de longitud corta a media como uno esperaría. Aunque también me pregunto si la fuerza bruta en este algoritmo ad hoc es más lenta que los ataques en la función PASSWORD() más reciente que simplemente usa SHA1 (dos veces), ya que supongo que hay un soporte de aceleración de hardware más amplio para SHA1. Vea más sobre fallas y ataques en las contraseñas de MySQL en En busca de un ejemplo de aplicación conocida que use hashes sin sal

    
pregunta nealmcb 17.04.2011 - 19:36
fuente

3 respuestas

29

No tengo conocimiento de ningún criptoanálisis publicado en MySQL OLD_PASSWORD() , pero es tan débil que es una especie de broma. Podría administrarse como un ejercicio durante un curso de criptografía.

Actualización: se publicó un cryptanalysis similar a la reunión en el medio que se describe a continuación en F. Muller y T. Peyrin "Criptoanálisis de funciones hash basadas en función T" en la Conferencia Internacional sobre Seguridad de la Información y Criptología - ICISC 2006 en 2006, con una descripción más genérica y algunas optimizaciones para encontrar contraseñas cortas y mantenerlas en la RAM.

Por ejemplo, aquí hay un código C que "revierte" el estado interno:

static int
oldpw_rev(uint32_t *pnr, uint32_t *pnr2, uint32_t add,
        unsigned char *cc, unsigned len)
{
        uint32_t nr, nr2;
        uint32_t c, u, e, y;

        if (len == 0) {
                return 0;
        }

        nr = *pnr;
        nr2 = *pnr2;
        c = cc[len - 1];
        add -= c;

        u = nr2 - nr;
        u = nr2 - ((u << 8) ^ nr);
        u = nr2 - ((u << 8) ^ nr);
        nr2 = nr2 - ((u << 8) ^ nr);
        nr2 &= 0x7FFFFFFF;

        y = nr;
        for (e = 0; e < 64; e ++) {
                uint32_t z, g;

                z = (e + add) * c;
                g = (e ^ z) & 0x3F;
                if (g == (y & 0x3F)) {
                        uint32_t x;

                        x = e;
                        x = y ^ (z + (x << 8));

                        x = y ^ (z + (x << 8));
                        x = y ^ (z + (x << 8));
                        nr = y ^ (z + (x << 8));
                        nr &= 0x7FFFFFFF;
                        if (oldpw_rev(&nr, &nr2, add, cc, len - 1) == 0) {
                                *pnr = nr;
                                *pnr2 = nr2;
                                return 0;
                        }
                }
        }

        return -1;
}

Esta función, cuando se le da el estado interno después de los caracteres de contraseña len dados en la matriz cc[] ( nr y nr2 , dos palabras de 31 bits y el valor add que es la suma de los caracteres de la contraseña), calcula una solución válida para nr y nr2 antes de la inserción de los caracteres de la contraseña. Esto es eficiente.

Esto conduce a un ataque fácil de encontrar en el medio. Considere las secuencias de 14 letras ASCII en minúsculas, de manera que cada letra vaya seguida de su complemento (el complemento de 'a' es 'z', el complemento de 'b' es 'y', y así sucesivamente ...). Hay alrededor de 8 billones de tales secuencias. Tenga en cuenta que la suma de los caracteres para cualquiera de esas secuencias es siempre el valor fijo 1533. Tome N de esas secuencias; para cada uno de ellos, calcule el hash correspondiente con OLD_PASSWORD() y acumule los valores en un archivo grande: cada entrada contiene la secuencia de caracteres, y los correspondientes nr y nr2 . Luego ordene el archivo por el par de 62 bits nr / nr2 . Este archivo es una tabla grande de: "utilizando esta secuencia , obtenemos de los valores iniciales a ese estado interno".

Luego toma las secuencias N nuevamente, y esta vez usa oldpw_rev() (como se muestra arriba) para cada una de ellas, usando el hash real atacado como punto de inicio para nr y nr2 y 2 * 1533 == 3066 para add . Esto le dará a usted N otros pares nr / nr2 , cada uno con una secuencia correspondiente. Estos valores se acumulan en otro archivo, que nuevamente se ordena por par de 62 bits nr / nr2 . Este segundo archivo es una tabla grande de: "usando esta secuencia en ese estado interno, obtenemos el valor de hash que estamos atacando actualmente".

En ese punto, solo tiene que encontrar dos pares coincidentes, es decir, el mismo nr / nr2 en el primer archivo y el segundo archivo. Las secuencias de 14 caracteres correspondientes son entonces las dos mitades de una contraseña de 28 caracteres que coincide con la salida de hash. Probablemente sea no la contraseña que se usó en primer lugar, pero esta es una contraseña que tiene el mismo valor y será aceptada por MySQL. Es probable que obtenga un par correspondiente cuando N llegue a 2 billones o menos (estamos en un espacio de tamaño 262 , por lo que basta con que N esté en el orden de sqrt (2 62 ) ).

Este ataque tiene un factor de trabajo sobre 237 (que representa el paso de clasificación), que es mucho más pequeño que el 2 62 factor de trabajo que, en teoría, podría lograrse con una función hash con una salida de 62 bits (que ya es demasiado baja para una seguridad adecuada). Por lo tanto, la función OLD_PASSWORD() está rota criptográficamente.

(Probablemente hay ataques mucho mejores que eso.)

    
respondido por el Thomas Pornin 18.04.2011 - 00:29
fuente
8

Ayer pulí mi google-fu y esta vez logré encontrar un artículo de 2006 sobre esto: F. Muller y T. Peyrin" Cryptanalysis of T-Function Hash Functions "en la Conferencia Internacional sobre Seguridad de la Información y Criptología - ICISC 2006 . ¡Gran trabajo!

Pero la función que describe es muy diferente a la actual OLQL_PASSWD de MySQL (también conocida como libmysql / password.c hash_password ()) por lo que su colisión entre no funciona del todo.

El documento dice " si elegimos la contraseña" MySQL123 ". El hash de la contraseña es (nk1 & K = 0x1b03947c, nk2 & K = 0x1d6d177b), con K = 0x3fffffff. "y dice que el hash de RGp0mA23 es el mismo.

Pero:

mysql> select OLD_PASSWORD('MySQL123');
+--------------------------+
| OLD_PASSWORD('MySQL123') |
+--------------------------+
| 1b03947a6f1ae59b         |
+--------------------------+

vs 1b03947a77350d71 para RGp0mA23.

Por lo tanto, es probable que haya un poco de trabajo por hacer para abordar el OLQL_PASSWORD de MySQL.

De todos modos, deje de usar los hashes de contraseña predeterminados de MySQL (ya sean antiguos o nuevos) y use la tecnología al menos tan avanzada como "crypt " de Unix en 1978 con recuentos de sales e iteración ....

    
respondido por el nealmcb 22.04.2011 - 18:17
fuente
1

CVE-2003-1480 se emitió para el hash OLD_PASSWORD de MySQL función. Aparece en el aviso que la principal preocupación es que es demasiado rápido . Desde la perspectiva de los equipos de desarrollo de MySQL puedo ver cómo quieren reducir la carga en la base de datos tanto como sea posible. El uso de un doble sha1 es un esfuerzo de fortalecimiento clave. Para ser honesto, sha1 aún es muy rápido y solo ejecutarlo dos veces es solo para apaciguar el CVE.

    
respondido por el rook 17.04.2011 - 20:15
fuente

Lea otras preguntas en las etiquetas