MySQL OLD_PASSWORD crittoanalisi?

Non sono a conoscenza di alcuna crittoanalisi pubblicata su MySQL OLD_PASSWORD() , ma è così debole che è una specie di barzelletta. Potrebbe essere dato come esercizio durante un corso di crittografia.

Aggiornamento: una crittoanalisi simile al meet-in-the-middle descritto di seguito è stata pubblicata in F. Muller e T. Peyrin "Crittoanalisi delle funzioni hash basate su funzione T" in International Conference on Information Security and Cryptology - ICISC 2006 nel 2006, con una descrizione più generica e qualche ottimizzazione per trovare password brevi e tenere nella RAM.

Ad esempio, ecco un codice C che "ripristina" lo stato 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;
}

Questa funzione, quando viene fornito lo stato interno dopo i caratteri len password dati nell'array cc[] ( nr e nr2 , due parole a 31 bit e il valore add che è la somma dei caratteri della password), calcola una soluzione valida per nr e nr2 prima l'inserimento dei caratteri della password. Questo è efficiente.

Questo porta ad un facile attacco di tipo "meet-in-the-middle". Considera le sequenze di 14 lettere ASCII minuscole, in modo che ogni lettera sia seguita dal suo complemento (il complemento di 'a' è 'z', il complemento di 'b' è 'y', e così via ...). Ci sono circa 8 miliardi di queste sequenze. Nota che la somma dei caratteri per ognuna di quelle sequenze è sempre il valore fisso 1533. Prendi N di quelle sequenze; per ognuno di essi, calcola l'hash corrispondente con OLD_PASSWORD() e accumula i valori in un file grande: ogni voce contiene la sequenza di caratteri e il corrispondente nr e nr2 . Quindi ordina il file con la coppia dinr 62% nr2 . Questo file è una grande tabella di: "usando questa sequenza, otteniamo dai valori iniziali a che stato interno".

Quindi riprende di nuovo le sequenze N , e questa volta usa oldpw_rev() (come mostrato sopra) per ognuna di esse, usando l'hash effettivo attaccato come punto di partenza per nr e nr2 e 2 * 1533 == 3066 per add . Questo ti darà N altre coppie nr / nr2 , ciascuna con una sequenza corrispondente. Questi valori sono accumulati in un altro file, che si ordina di nuovo in base alla coppia di 62-bit nr / nr2 . Questo secondo file è una grande tabella di: "usando questa sequenza su tale stato interno, otteniamo il valore hash che stiamo attualmente attaccando".

A quel punto devi solo trovare due coppie corrispondenti, cioè lo stesso nr / nr2 nel primo file e nel secondo file. Le sequenze di 14 caratteri corrispondenti sono quindi le due metà di una password di 28 caratteri che corrisponde all'output dell'hash. Questa è probabilmente non la password che è stata utilizzata in primo luogo, ma questa è una password che eseguirà lo hash allo stesso valore e sarà accettata da MySQL. È probabile che tu abbia una coppia corrispondente quando N raggiunge 2 miliardi circa (siamo in uno spazio di dimensioni 2 ⁶² , quindi è sufficiente che N sia nell'ordine di sqrt (2 ⁶² ) ).

Questo attacco ha un fattore di lavoro relativo a 2 ³⁷ (che tiene conto del passo di smistamento), che è molto più piccolo del 2 ⁶² fattore di lavoro che potrebbe teoricamente essere raggiunto con una funzione hash con un'uscita a 62 bit (che è già troppo bassa per una corretta sicurezza). Pertanto, la funzione OLD_PASSWORD() è crittograficamente interrotta.

(Probabilmente ci sono attacchi molto migliori.)

Ho ripulito il mio google-fu ieri e questa volta sono riuscito a trovare un documento del 2006 su questo: F. Muller e T. Peyrin" Crittoanalisi delle funzioni di hash basate su T-Function "nella Conferenza internazionale sulla sicurezza delle informazioni e la crittologia - ICISC 2006 . Ottimo lavoro!

Ma la funzione che descrive è leggermente diversa dall'effettivo OLD_PASSWD di MySQL (alias libmysql / password.c hash_password ()), quindi la loro collisione tra non funziona.

Il foglio dice " se selezioniamo la password" MySQL123 ". L'hash della password è (nk1 & K = 0x1b03947c, nk2 & K = 0x1d6d177b), con K = 0x3fffffff. "e dice che l'hash di RGp0mA23 è lo stesso.

Ma:

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

vs 1b03947a77350d71 per RGp0mA23.

Quindi c'è ancora un po 'di lavoro da fare per affrontare OLD_PASSWORD di MySQL.

Ad ogni modo, si prega di smettere di usare gli hash delle password predefinite MySQL (vecchi o nuovi) e utilizzare una tecnologia almeno avanzata come "crypt " di Unix nel 1978 con sali e conteggio iterativo ....

CVE-2003-1480 è stato rilasciato per l'hash OLD_PASSWORD di MySQL funzione. Dalla consulenza emerge che la preoccupazione principale è che troppo veloce . Dal punto di vista dei team di sviluppo MySQL posso vedere come vogliono ridurre il carico sul database il più possibile. L'uso di un doppio sha1 è uno sforzo di rafforzamento chiave. Per essere onesti, il doppio sha1 è ancora molto veloce e solo eseguirlo due volte è sufficiente per placare il CVE.