bcrypt

bcrypt è una funzione di hashing di password progettata da Niels Provos e David Mazières, basata sulla cifratura Blowfish e presentata a USENIX nel 1999. Oltre a incorporare un salt per proteggere la password contro attacchi tabella arcobaleno, bcrypt è una funzione adattiva: col tempo, il conteggio dell'iterazione può essere aumentato per renderla più lenta, in modo da essere resistente ad attacchi di forza bruta anche con capacità computazionale crescente.

La funzione bcrypt è l'algoritmo di hashing di password di default per BSD e altri sistemi, incluse alcune distribuzioni Linux come SUSE Linux. Il prefisso "$2a$" o "$2b$" (o "$2y$") in una stringa di hash in un file shadow password indica che quella stringa hash è un formato modulare di hash bcrypt. Il resto della stringa hash include il parametro costo, un sale 128-bit (codificato base64 con 22 caratteri), e 184 bit del valore hash risultante (codificato base64 con 31 caratteri). Il parametro costo specifica un conteggio iterativo di espansione della chiave in una potenza di due, che è un input dell'algoritmo di cifratura.

Per esempio, il record shadow password $2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy specifica un parametro costo di 10, indicando 2¹⁰ come turni di espansione della chiave. Il sale è N9qo8uLOickgx2ZMRZoMye e l'hash risultante è IjZAgcfl7p92ldGxad68LJZdL17lhWy. Per pratica standard, la password stessa dell'utente non è memorizzata.

Sono presenti implementazioni di bcrypt per C, C#, Java, JavaScript, Perl, PHP, Python, Ruby e altri linguaggi.

Background

Blowfish è importante tra i cifrari a blocchi per la sua dispendiosa fase di setup della chiave. Inizia con sottochiavi in uno stato standard, poi utilizza questo stato per eseguire una cifratura a blocchi usando parte della chiave, e usa il risultato di quella cifratura (che è più precisamente un hashing) per sostituire alcune delle sottochiavi. Successivamente esso utilizza questo stato modificato per criptare altre parti della chiave, e si serve del risultato per sostituire altre sottochiavi. Procede in questo modo, usando uno stato modificato progressivo per eseguire l'hash della chiave e sostituire pezzi dello stato, finché tutte le sottochiavi sono state stabilite.

Provos e Mazières sfruttarono questo, e lo portarono avanti. Essi svilupparono un nuovo algoritmo di setup delle chiavi per Blowfish, nominando la cifratura risultante "Eksblowfish" ("expensive key schedule Blowfish"). Il setup della chiave comincia con una forma modificata dello standard di setup della chiave Blowfish, nel quale sia il sale che la password sono usate come sottochiavi. Sono presenti quindi un numero di turni in cui l'algoritmo Blowfish standard è applicato, usando alternativamente il sale e la password come chiave, in cui ogni turno parte con lo stato sottochiave del turno precedente. In teoria, non esiste nulla di più forte dello standard Blowfish, ma il numero di turni di ricodifica è configurabile; questo processo può quindi essere eseguito arbitrariamente lentamente, contribuendo a dissuadere attacchi di forza bruta sull'hash o sale.

Algoritmo

L'algoritmo bcrypt dipende pesantemente dal suo algoritmo di setup delle chiavi "Eksblowfish", che viene eseguito come di seguito:

EksBlowfishSetup(cost, salt, key)
    state $\gets$ InitState()
    state $\gets$ ExpandKey(state, salt, key)
    repeat (2cost)
        state $\gets$ ExpandKey(state, 0, key)
        state $\gets$ ExpandKey(state, 0, salt)
    return state

InitState funziona come nell'algoritmo Blowfish originale, popolando il P-array e gli ingressi S-box con una parte frazionale di \pi in esadecimale.

La funzione ExpandKey è la seguente:

ExpandKey(state, salt, key)
    for(n = 1..18)
        Pn $\gets$ key[32(n-1)..32n-1] $\oplus$ Pn //treat the key as cyclic
    ctext $\gets$ Encrypt(salt[0..63])
    P1 $\gets$ ctext[0..31]
    P2 $\gets$ ctext[32..63]
    for(n = 2..9)
        ctext $\gets$ Encrypt(ctext $\oplus$ salt[64(n-1)..64n-1]) //encrypt using the current key schedule and treat the salt as cyclic
        P2n-1) $\gets$ ctext[0..31]
        P2n $\gets$ ctext[32..63]
    for(i = 1..4)
        for(n = 0..127)
            ctext $\gets$ Encrypt(ctext $\oplus$ salt[64(n-1)..64n-1]) //as above
            Si[2n] $\gets$ ctext[0..31]
            Si[2n+1] $\gets$ ctext[32..63]
    return state

Di conseguenza, ExpandKey(state, 0, key) è lo stesso del key schedule regolare di Blowfish siccome tutti gli XOR con il valore sale completamente a 0 sono inconcludenti. ExpandKey(state, 0, salt) è simile, ma utilizza il sale come una chiave 128-bit.

L'algoritmo completo bcrypt utilizza queste funzioni per computare un hash da un input dato derivato dalla password, come segue:

bcrypt(cost, salt, input)
    state $\gets$ EksBlowfishSetup(cost, salt, input)
    ctext $\gets$ "OrpheanBeholderScryDoubt" //three 64-bit blocks
    repeat (64)
        ctext $\gets$ EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode
    return Concatenate(cost, salt, ctext)

Input utente

Molte implementazioni di bcrypt troncano la password ai primi 72 byte.

L'algoritmo matematico stesso richiede un'inizializzazione con 18 sottochiavi a 32-bit (equivalenti a 72 ottetti/byte). La specifica originale di bcrypt non impone nessun metodo particolare per mappare password text-based dallo spazio utente in valori numerici per l'algoritmo. Un breve commento nel testo accenna, ma non ordina, la possibilità di usare semplicemente il valore codificato ASCII di una stringa carattere, "Infine, l'argomento chiave è una chiave segreta di cifratura, che può essere una password scelta dall'utente fino a 56 byte (incluso un byte 0 terminante quando la chiave è una stringa ASCII)."

Da notare che la citazione sopra menziona password "fino a 56 byte" anche se l'algoritmo stesso utilizza un valore iniziale di 72 byte. Nonostante Provos e Mazières non dichiarano il motivo della breve restrizione, essi potrebbero essere stati motivati dalla seguente dichiarazione dalla specifica originale di Blowfish di Bruce Schneier, "Il limite di 448 [bit] sulla grandezza della chiave assicura che ogni bit di ogni sottochiave dipende da ogni bit della chiave."

Le implementazioni sono variate nel loro approccio di convertire password in valori numerici iniziali, includendo a volte la riduzione della forza di password contenenti caratteri speciali.

Voci correlate

• Crypt (C)#Blowfish-based scheme crypt - schema di verifica e memorizzazione delle password - Blowfish
• Key stretching
• PBKDF2 (Password-Based Key Derivation Function 2)
• scrypt

Collegamenti esterni

• Bcrypt, su packages.debian.org.