HotPDF esegue l'accordo di chiavi su curve ellittiche e la verifica delle firme per il PDF in Object Pascal puro, senza binding OpenSSL e senza provider crittografico di piattaforma nel percorso. Ciò copre cinque curve: P-256, P-384 e P-521 per le famiglie di primi NIST, più X25519 e X448 per l'accordo di chiavi su curve di Montgomery. La ragione per scrivere quel codice invece di collegarlo è il deployment, non la purezza. Un'applicazione Delphi o Free Pascal che distribuisce un solo eseguibile e nessuna DLL crittografica non ha disallineamenti di versione da gestire, né provider per piattaforma da rilevare, e nulla che cambi comportamento quando un cliente applica patch alle librerie di sistema
Il costo è che ora l'aritmetica è di Lei. La moltiplicazione modulare su interi grandi è codice che non perdona: o produce risultati identici al byte rispetto ai vettori di test pubblicati o produce spazzatura dall'aspetto plausibile, e la distanza tra quei due stati può essere un singolo confronto. Questa è la storia di quel confronto, perché la forma del bug si generalizza a qualsiasi porting in Pascal dell'aritmetica dei campi
Perché mai una libreria PDF ha bisogno di aritmetica sulle curve?
Due funzioni la richiamano in causa. La prima è la cifratura a chiave pubblica dei documenti: il gestore della recipient list di ISO 32000 incarta una chiave per documento per certificati nominati, e quando un destinatario possiede una chiave EC l'incartamento passa attraverso l'accordo di chiavi anziché il trasporto di chiavi RSA. Senza ECDH non c'è modo di aprire un tale documento. La seconda è la validazione delle firme. Verificare una firma ECDSA sui byte di /ByteRange richiede una moltiplicazione di punti sulla curva del firmatario, e P-384 è comune nei profili governativi e di firma qualificata dove P-256 è considerato il pavimento, non l'obiettivo. HotPDF espone i risultati di quel lavoro attraverso la via di verifica ECDSA e CMS e attraverso il modello di provider di firma collegabile
CIOS, e l'unica sottrazione alla fine
La moltiplicazione di Montgomery evita la divisione lavorando in un dominio trasformato dove la riduzione è uno shift. La variante usata da HotPDF è Coarsely Integrated Operand Scanning, che intreccia la moltiplicazione e la riduzione limb per limb così l'intermedio non cresce mai oltre la larghezza del modulo più un limb. Il corpo del ciclo è semplice e facile da testare. La coda non lo è: dopo le passate intrecciate l'accumulatore può trovarsi in un punto qualsiasi dell'intervallo fino al doppio del modulo, così l'algoritmo finisce con una sottrazione condizionale che rimuove una copia del primo se e solo se l'accumulatore è maggiore o uguale a esso
Confrontare due numeri a più limb significa scendere dal limb più significativo verso il basso mentre si trasporta un borrow. Il modo ovvio di scriverlo è confrontare il limb dell'accumulatore con il limb del modulo più il borrow in arrivo. Quell'espressione è sbagliata, ed è sbagliata in un modo che la maggior parte delle curve nasconde
// Sbagliato: P[I] + Borrow può andare in wrap quando P[I] è $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
Borrow := 1;
Break;
end;
// Corretto: confrontare senza mai aggiungere a un limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
Borrow := 1;
Break;
end;Che aspetto ha davvero un wrap-around del borrow?
Assomiglia a una curva che funziona ovunque tranne che in produzione. I primi per P-384 e P-521 contengono limb interamente di uno, così P[I] è uguale a $FFFFFFFFFFFFFFFF. Sommarci il borrow in arrivo di uno e un unsigned a 64 bit va in wrap a zero. Il confronto quindi chiede se il limb dell'accumulatore sia minore di zero, decide che non lo è, e conclude che non serve alcun borrow. Un limb del risultato è sbagliato di uno
P-256 se la svigna perché nessuno dei suoi limb è tutto di uno, così la somma non va mai in overflow e l'espressione bacata per coincidenza concorda con quella corretta. È il peggior esito possibile per una suite di test: la curva più testata passa, quelle meno testate falliscono in modo intermittente a seconda dei valori degli operandi, e il fallimento affiora come esito di verifica "firma non valida" su documenti perfettamente validi. HotPDF ha mantenuto un gate esplicito su P-384 proprio per questa ragione, restituendo uno stato non disponibile anziché una risposta sbagliata, finché l'aritmetica non è stata provata contro vettori di riferimento
Come è stato davvero localizzato il bug
Non leggendo il codice. La sequenza produttiva era meccanica, ed è riutilizzabile. Prima, eliminare le costanti: ogni limb di p, R e R^2 è stato rigenerato in modo indipendente e confrontato limb per limb, il che esclude la singola fonte più comune di bug sulle curve. Seconda, strumentare l'aritmetica piuttosto che l'API: una procedura di dump temporanea stampava i valori intermedi della moltiplicazione di Montgomery di R^2, di x^3 e di y^2 per un punto noto, così potevano essere confrontati con una verità calcolata indipendentemente
Quel confronto puntava dritto al colpevole. La catena di x era corretta da capo a fondo, mentre y^2 differiva in esattamente un limb di esattamente uno. Una differenza di un limb di uno non è un bug di moltiplicazione, un bug di propagazione del carry o un bug di costante; è un bug di catena di borrow, e l'unica catena di borrow nella routine è la sottrazione condizionale finale. Un dettaglio ha quasi fatto deragliare tutto: la costante di riferimento usata per il dump era essa stessa scritta nell'ordine di byte sbagliato al primo tentativo, il che produceva una mancata corrispondenza nel valore di y e suggeriva brevemente un secondo difetto inesistente. Verificare l'endianness della propria verità di riferimento prima di fidarla per accusare il proprio codice
Le trappole vicine nella stessa routine
Altre tre modalità di guasto vivono a poche righe da quel confronto, e tutte e tre sono state attive a un certo punto durante lo sviluppo
// 1. L'accumulatore ha un limb sopra la larghezza del modulo. Confrontare solo
// i L limb bassi perde il caso in cui T è esattamente p più 2^(64*L),
// che accade per una quota significativa di input casuali perché 2p
// supera 2^256 per P-256 e 2^384 per P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
SubtractModulus(T, P, L);
// 2. Una sottrazione generica a più limb ha lo stesso rischio di wrap: quando
// Y[I] è $FFFFFFFFFFFFFFFF, Y[I] + Borrow va in wrap a zero e il
// borrow deve sopravvivere nel limb successivo invece di essere azzerato
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));La terza non è codice, è provenienza. Il primo per P-521 fu inizialmente trascritto con 130 cifre esadecimali invece di 131, un F in meno, e le costanti di Montgomery furono poi calcolate da quel primo sbagliato, così le costanti erano autoconsistenti e congiuntamente sbagliate. I parametri delle curve devono essere derivati, mai battuti a mano: calcolare R come (1 shl (64 * L)) mod p dal primo che si usa davvero, poi verificare in modo incrociato R * R mod p rispetto al valore che la costante R^2 dichiara. Una coppia di costanti che concordano tra loro non prova nulla su nessuna delle due
Una strategia di verifica che scala oltre una curva
La tecnica che ha reso gestibili X25519 e X448 è stata scrivere un'implementazione mirror in un linguaggio con interi senza limiti e trascriverci il flusso di controllo Pascal riga per riga. Quando il mirror produce la risposta giusta e il Pascal no, il difetto è una svista di trascrizione e esplorare lo stesso valore intermedio in entrambe le implementazioni lo trova in pochi secondi. Tutti e tre i classici errori della ladder RFC 7748 sono stati colti così: uno swap a tempo costante la cui seconda riga riusava il valore già scambiato, un'inversione finale che restituiva z alla potenza meno uno invece di moltiplicarlo dentro X, e una moltiplicazione per piccola costante che assemblava i prodotti di mezza parola con un or bitwise perdendo il carry
Per il materiale di test, prendere i vettori come byte anziché come testo. Estrarre una chiave privata con un pattern testuale è il modo in cui un'implementazione corretta viene accusata di un errore di un byte che vive interamente nel passo di estrazione. Ritagliare l'hex dalla codifica DER a offset noti e confrontare array di byte
Con la catena di borrow corretta, tutte e cinque le curve corrispondono ai vettori di riferimento pubblicati byte per byte, e HotPDF non applica più alcun gate su di esse. Se si sta integrando firma basata su certificati o cifratura con recipient list, la conseguenza pratica è che la scelta della curva ora è una decisione di politica piuttosto che una questione di capacità; i profili e le insidie di ordine dei byte del lato firma sono trattati nel percorso di firma PAdES. I dettagli del componente e la matrice degli algoritmi supportati sono sulla pagina di prodotto di HotPDF Delphi PDF component