NIST-Kurvenarithmetik in Pure Pascal für PDF-Signaturen

HotPDF führt elliptische Kurven-Schlüsselvereinbarung und Signaturverifikation für PDF in reinem Object Pascal aus, ohne OpenSSL-Bindung und ohne Plattform-Kryptoprovider im Pfad. Das umfasst fünf Kurven: P-256, P-384 und P-521 für die NIST-Primfamilien, dazu X25519 und X448 für Schlüsselvereinbarung auf Montgomery-Kurven. Der Grund, diesen Code zu schreiben statt zu linken, ist Deployment, nicht Reinheit. Eine Delphi- oder Free-Pascal-Anwendung, die eine einzige ausführbare Datei und keine kryptografische DLL ausliefert, hat keinen Versionsdrift zu verwalten, keinen plattformspezifischen Provider zu erkennen und nichts, das das Verhalten ändert, wenn ein Kunde seine Systembibliotheken patcht

Der Preis ist, dass die Arithmetik nun Ihnen gehört. Big-Integer-Modularmultiplikation ist unerbittlicher Code: Sie erzeugt entweder byteidentische Ergebnisse gegen veröffentlichte Testvektoren oder plausibel aussehenden Müll, und der Abstand zwischen diesen beiden Zuständen kann ein einziger Vergleich sein. Das ist die Geschichte dieses Vergleichs, denn die Gestalt des Bugs verallgemeinert sich auf jeden Pascal-Port von Körperarithmetik

Warum braucht eine PDF-Bibliothek überhaupt Kurvenarithmetik?

Zwei Features ziehen sie herein. Das erste ist Public-Key-Verschlüsselung von Dokumenten: Der ISO-32000-Recipient-List-Handler wickelt einen Dokumentschlüssel für benannte Zertifikate ein, und wenn ein Empfänger einen EC-Schlüssel hält, läuft das Einwickeln über Schlüsselvereinbarung statt über RSA-Schlüsseltransport. Ohne ECDH gibt es keinen Weg, ein solches Dokument zu öffnen. Das zweite ist die Signaturvalidierung. Eine ECDSA-Signatur über die /ByteRange-Bytes zu verifizieren braucht eine Punktmultiplikation auf der Unterzeichnerkurve, und P-384 ist in Behörden- und Qualified-Signature-Profilen üblich, wo P-256 als Untergrenze gilt statt als Ziel. HotPDF stellt die Ergebnisse dieser Arbeit bereit über den ECDSA- und CMS-Verifikationspfad und über das pluggable Signature-Provider-Modell

CIOS und die eine Subtraktion am Ende

Montgomery-Multiplikation vermeidet Division, indem sie in einem transformierten Bereich arbeitet, in dem Reduktion eine Verschiebung ist. Die Variante, die HotPDF verwendet, ist Coarsely Integrated Operand Scanning, die Multiplikation und Reduktion Limb für Limb verschachtelt, sodass das Zwischenergebnis nie über die Modulusbreite plus einen Limb hinauswächst. Der Schleifenrumpf ist geradlinig und leicht zu testen. Der Schwanz ist es nicht: Nach den verschachtelten Durchgängen kann der Akkumulator irgendwo im Bereich bis zum Doppelten des Modulus liegen, also endet der Algorithmus mit einer bedingten Subtraktion, die eine Kopie der Primzahl entfernt, wenn und nur wenn der Akkumulator größer oder gleich ihr ist

Zwei Multi-Limb-Zahlen zu vergleichen bedeutet, vom höchstwertigen Limb abwärts zu laufen, während man einen Borrow mitführt. Die naheliegende Art, das zu schreiben, ist, den Akkumulator-Limb gegen den Modulus-Limb plus den eingehenden Borrow zu vergleichen. Dieser Ausdruck ist falsch, und er ist so falsch, dass die meisten Kurven es verbergen

// Falsch: P[I] + Borrow kann überlaufen, wenn P[I] $FFFFFFFFFFFFFFFF ist
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Richtig: vergleichen, ohne jemals zu einem Limb zu addieren
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Wie sieht ein Borrow-Überlauf tatsächlich aus?

Es sieht aus wie eine Kurve, die überall funktioniert außer in der Produktion. Die Primzahlen für P-384 und P-521 enthalten Limbs, die durchweg Einsen sind, also ist P[I] gleich $FFFFFFFFFFFFFFFF. Addiert man den eingehenden Borrow von eins dazu, läuft ein 64-Bit-Unsigned auf null über. Der Vergleich fragt dann, ob der Akkumulator-Limb kleiner als null ist, entscheidet nein und schließt, dass kein Borrow nötig ist. Ein Limb des Ergebnisses geht um eins daneben

P-256 entkommt, weil keiner seiner Limbs durchweg Einsen ist, also läuft die Addition nie über, und der fehlerhafte Ausdruck stimmt zufällig mit dem korrekten überein. Das ist der schlimmstmögliche Ausgang für eine Test-Suite: Die meistgetestete Kurve besteht, die weniger getesteten scheitern intermittierend je nach Operandenwerten, und der Fehler zeigt sich als Verifikationsergebnis „ungültige Signatur“ bei Dokumenten, die völlig gültig sind. HotPDF führte aus genau diesem Grund eine explizite Sperre für P-384 mit und gab einen Nicht-verfügbar-Status statt einer falschen Antwort zurück, bis die Arithmetik gegen Referenzvektoren bewiesen war

Wie der Bug tatsächlich lokalisiert wurde

Nicht durch Lesen des Codes. Die produktive Sequenz war mechanisch, und sie ist wiederverwendbar. Erstens die Konstanten eliminieren: Jeder Limb von p, R und R^2 wurde unabhängig regeneriert und Limb für Limb verglichen, was die mit Abstand häufigste Quelle von Kurven-Bugs ausschließt. Zweitens die Arithmetik instrumentieren statt die API: Eine temporäre Dump-Prozedur druckte die Zwischenwerte der Montgomery-Multiplikation von R^2, von x^3 und von y^2 für einen bekannten Punkt, damit sie gegen unabhängig berechnete Wahrheit geprüft werden konnten

Dieser Vergleich zeigte direkt auf den Täter. Die x-Kette war von Ende zu Ende korrekt, während y^2 in genau einem Limb um genau eins abwich. Eine Ein-Limb-Differenz von eins ist kein Multiplikations-Bug, kein Carry-Fortpflanzungs-Bug und kein Konstanten-Bug; sie ist ein Borrow-Ketten-Bug, und die einzige Borrow-Kette in der Routine ist die abschließende bedingte Subtraktion. Ein Detail entgleiste das Beinahe: Die für den Dump verwendete Referenzkonstante war selbst beim ersten Versuch in der falschen Byte-Reihenfolge notiert, was eine Abweichung im y-Wert erzeugte und kurz einen zweiten, nicht existierenden Defekt nahelegte. Prüfen Sie die Endianness Ihrer Ground Truth, bevor Sie sie Ihren Code anklagen lassen

Die Nachbarfallen in derselben Routine

Drei weitere Fehlermodi wohnen wenige Zeilen von diesem Vergleich entfernt, und alle drei waren irgendwann während der Entwicklung aktiv

// 1. Der Akkumulator hat einen Limb über der Modulusbreite. Nur die
//    unteren L Limbs zu vergleichen verpasst den Fall, in dem T exakt
//    p plus 2^(64*L) entspricht, was für einen erheblichen Anteil
//    zufälliger Eingaben vorkommt, weil 2p 2^256 bei P-256 und
//    2^384 bei P-384 übersteigt
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Eine generische Multi-Limb-Subtraktion hat dieselbe Überlaufgefahr:
//    Ist Y[I] $FFFFFFFFFFFFFFFF, läuft Y[I] + Borrow auf null über, und
//    der Borrow muss in den nächsten Limb überleben, statt gelöscht zu werden
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Der dritte ist kein Code, sondern Provenienz. Die Primzahl für P-521 wurde zunächst mit 130 Hexadezimalziffern statt 131 transkribiert, ein F zu kurz, und die Montgomery-Konstanten wurden dann aus dieser falschen Primzahl berechnet, also waren die Konstanten selbstkonsistent und gemeinsam falsch. Kurvenparameter müssen hergeleitet werden, niemals eingetippt: Berechnen Sie R als (1 shl (64 * L)) mod p aus der Primzahl, die Sie tatsächlich verwenden, und prüfen Sie dann R * R mod p gegen den Wert, den Ihre R^2-Konstante behauptet. Ein Paar Konstanten, das miteinander übereinstimmt, beweist nichts über irgendeine von ihnen

Eine Verifikationsstrategie, die über eine Kurve hinaus trägt

Die Technik, die X25519 und X448 beherrschbar machte, war eine Spiegelimplementierung in einer Sprache mit unbeschränkten Integern und die Transkription des Pascal-Kontrollflusses hinein, Zeile für Zeile. Wenn der Spiegel die richtige Antwort liefert und das Pascal nicht, ist der Defekt ein Transkriptions-Ausrutscher, und das Abtasten desselben Zwischenwerts in beiden Implementierungen findet ihn in Sekunden. Alle drei klassischen RFC-7748-Leiter-Fehler wurden so gefangen: ein Constant-Time-Swap, dessen zweite Zeile den bereits getauschten Wert wiederverwendete, eine abschließende Inversion, die z in die Potenz minus eins hob, statt ihn in X hineinzumultiplizieren, und eine Kleinkonstanten-Multiplikation, die Halbwort-Produkte mit einem bitweisen or zusammensetzte und den Carry verlor

Für Testmaterial nehmen Sie Vektoren als Bytes statt als Text. Einen privaten Schlüssel mit einem Textmuster zu extrahieren ist der Weg, auf dem einer korrekten Implementierung ein Off-by-ein-Byte-Fehler angehängt wird, der vollständig im Extraktionsschritt lebt. Schneiden Sie das Hex aus der DER-Kodierung an bekannten Offsets heraus und vergleichen Sie Byte-Arrays

Mit korrigierter Borrow-Kette entsprechen alle fünf Kurven den veröffentlichten Referenzvektoren byte für Byte, und HotPDF sperrt keine von ihnen mehr. Wer zertifikatsbasiertes Signieren oder Recipient-List-Verschlüsselung integriert, nimmt als praktische Erkenntnis mit, dass die Kurvenwahl nun eine Richtlinienentscheidung ist statt eine Fähigkeitenfrage; die Profile und Byte-Order-Fallen der Signaturseite behandelt der PAdES-Signaturdurchgang. Komponentendetails und die unterstützte Algorithmusmatrix stehen auf der Produktseite der HotPDF Delphi PDF-Komponente