Ed448 i krzywe Brainpool ECDSA w czystym Pascalu dla PDF

PDFlibPas podpisuje i weryfikuje z użyciem Ed448 oraz trzech krzywych Brainpool ECDSA w czystym Object Pascalu. Żadnej zewnętrznej biblioteki kryptograficznej, żadnego dostawcy platformowego, żadnej biblioteki DLL: PDFlibEd448 implementuje PureEdDSA z RFC 8032 na krzywej edwards448, a PDFlibBrainpool implementuje brainpoolP256r1, brainpoolP384r1 i brainpoolP512r1 z RFC 5639. Oba moduły powstały w ten sam sposób, w oparciu o wektory known-answer wygenerowane niezależnie, zanim napisano choćby jedną linię Pascala, i oba warte są opisania głównie ze względu na błędy

Arytmetyka ciała to niezwyczajnie uczciwy kod. Albo zgadza się bajt w bajt z opublikowanymi wektorami, albo nie, więc nie ma tu miejsca na „prawie działające”. To, co sprawia, że jest trudna, to fakt, że błędna implementacja nadal produkuje podpisy, nadal weryfikuje własne podpisy i nadal wygląda zupełnie wiarygodnie

Dlaczego właśnie te krzywe i dlaczego w Pascalu

Krzywe Brainpool pojawiają się w europejskich profilach podpisu kwalifikowanego, więc biblioteka podpisująca dokumenty na ten rynek nie może traktować ich jako egzotyki. Ed448 znajduje się w zestawie algorytmów, który ISO/TS 32002 wnosi do PDF, a jej wewnętrzną funkcją skrótu jest SHAKE256, a nie SHA-2. Żadna z tych rodzin nie jest dostępna w powszechnie używanych pascalskich bibliotekach kryptograficznych, więc biblioteka PDF, która ich chce, musi je posiadać we własnym kodzie

Argument wdrożeniowy jest ten sam, co w przypadku całej kryptografii tej biblioteki: aplikacja dostarczająca jeden plik binarny bez zależności kryptograficznych nie ma dostawcy do wykrycia, wersji do dopasowania ani zachowania, które zmienia się po załataniu hosta. Podpisywanie to dokładnie ten obszar, w którym ruchoma zależność jest ci najbardziej niepożądana

Stałe pochodzą z tekstu specyfikacji, nigdy z pamięci

Pierwsza próba zapisu punktu bazowego edwards448 powstała z pamięci i okazała się błędna. To nie jest wyjątkowa pomyłka, ale bardzo kosztowna, ponieważ zły punkt bazowy tworzy system spójny wewnętrznie: generowanie kluczy, podpisywanie i weryfikacja zgadzają się wzajemnie ze sobą i rozjeżdżają się z resztą świata

Sprawdzona procedura polega na pobraniu każdego parametru domeny z tekstu specyfikacji, a następnie na weryfikacji krzyżowej. Dla edwards448 oznacza to liczbę pierwszą, stałą krzywej, rząd grupy i obie dziesiętne współrzędne punktu bazowego z RFC 8032, przekonwertowane do wewnętrznej reprezentacji limb, a potem sprawdzone względem opublikowanych wektorów testowych z tego samego dokumentu. Dla krzywych Brainpool oznacza to parametry z RFC 5639, niezależną implementację napisaną w celu generowania wektorów oraz weryfikację krzyżową względem biblioteki systemowej w obu kierunkach, zanim uruchomiono jakiegokolwiek Pascala

Jeden skrót wyprowadzania zasługuje na ostrzeżenie, bo wygląda na uniwersalny, a nim nie jest: odzyskiwanie punktu bazowego ze stałej wartości y działa dla krzywej 25519 i nie działa dla edwards448, gdzie ta wartość nie ma pierwiastka kwadratowego. Skrypt obalił to w kilka sekund, co jest znacznie tańsze niż odkrywanie tego przez debuger

Metoda: implementacja lustrzana na poziomie limb przed jakimkolwiek Paskalem

Techniką, która uczyniła oba moduły opanowywalnymi, jest implementacja lustrzana w języku o nieograniczonych liczbach całkowitych, budowana oddolnie. Najpierw sama warstwa arytmetyczna: mnożenie i odejmowanie w ciele oraz propagacja przeniesień, testowana obciążeniowo względem ich niezmienników algebraicznych na kilkuset losowych przypadkach. Potem pełne generowanie kluczy wewnątrz lustra, bo tam mieszkają błędy semantyczne i tam ich znalezienie jest tanie. Dopiero na końcu transkrypcja na Pascala

Zysk jest diagnostyczny, a nie rozwojowy. Gdy raz wiadomo, że lustro jest poprawne, każda rozbieżność między lustrem a Paskalem to potknięcie transkrypcji, a zbadanie tej samej wartości pośredniej w obu implementacjach od razu ją lokalizuje. To przekształca klasę błędów, które inaczej są niemal niedebugowalne — jeden zły limb głęboko wewnątrz mnożenia skalarnego — w pięciominutowe porównanie

Cztery przyczyny źródłowe w Ed448

Wszystkie cztery znaleziono badając wartości pośrednie, a wszystkie cztery są tego rodzaju usterką, która produkuje wyniki wyglądające na poprawne

Pierwsza to pułapka notacyjna. Większość opublikowanych wzorów na zunifikowane dodawanie Edwardsa zakłada stałą krzywej równą minus jeden, a edwards448 ma plus jeden. Przeniesione bez zmian, licznik współrzędnej y zapisuje się jako sumę tam, gdzie powinna być różnica. Poprawka nie polega na łatanie znaku, lecz na ponownym wyprowadzeniu bezodwrotnościowej postaci iloczynowej z afinicznego prawa dodawania dla właściwej krzywej, co daje cztery wyrażenia współrzędnych i nie zostawia miejsca na odziedziczenie znaku ze złego źródła

Druga dotyczy dekompresji punktów. Odzyskanie afinicznej współrzędnej x ze współrzędnych rzutowych wymaga jednego mnożenia przez odwrotność Z. Mnożenie przez odwrotność podniesioną do kwadratu daje wartość, która wciąż jest poprawną reprezentacją rzutową, a jednocześnie złą współrzędną afiniczną, więc objawem jest poprawne y przy błędnym x. Za każdym razem, gdy jedna współrzędna jest właściwa, a druga nie, błąd leży w normalizacji, a nie w arytmetyce

Trzecia to nawyk przywieziony z krótszej krzywej. Zarówno skalar per podpis, jak i skalar wyzwania muszą być redukowane z pełnego skrótu, który dla Ed448 ma 114 bajtów, a nie z jego pierwszych 57. Krzywa 32-bajtowa również używa pełnego 64-bajtowego skrótu, więc reguła jest spójna; błędne jest tylko założenie, że „połowa skrótu to szerokość skalara”

Czwarta to kolejność. Prefiks separacji domeny przychodzi pierwszy, przed prefiksem kontekstu i wiadomością, co nie jest kolejnością sugerowaną przez intuicyjną lekturę R i A w specyfikacji. Pomyłka tutaj daje podpisy, które weryfikują się względem twojej własnej implementacji i niczego innego, co jest najbardziej mylącą możliwą odmianą awarii

// Projekt przeniesień w ciele: czysta propagacja o semantyce floor,
// dzięki której działają zarówno limby dodatnie, jak i ujemne,
// a odejmowanie nie potrzebuje biasu. Górne przeniesienie zawraca
// przez 2^448 = 2^224 + 1 (mod p), co dotyka limb 0 i limb 8.
// Ograniczone do czterech rund; w praktyce obserwowano dwie
procedure FeCarry(var A: TFe448);
var
  I, Round: Integer;
  Carry: Int64;
begin
  for Round := 1 to 4 do
  begin
    Carry := 0;
    for I := 0 to 15 do
    begin
      A[I] := A[I] + Carry;
      Carry := Floor28(A[I]);          // floor, nie obcinanie
      A[I] := A[I] - (Carry shl 28);
    end;
    if Carry = 0 then
      Break;
    A[0] := A[0] + Carry;              // 2^448 == 1
    A[8] := A[8] + Carry;              // 2^448 == 2^224
  end;
end;

Wcześniejsza wersja tej procedury stosowała bias przed propagacją i przy dużych wejściach wciskała fałszywe przeniesienie złej wielkości do niskich limb. Schematy przeniesień oparte na biasie to uporczywe źródło tej klasy defektów; semantyka floor z ograniczoną pętlą repeat jest łatwiejsza do przemyślenia i mierzalnie wystarczająco szybka

Dwie przyczyny źródłowe w Brainpool

Pierwsza w ogóle nie jest kryptografią. Robocza reprezentacja ma 33 limb, więc iloczyn dwóch wartości potrzebuje 66, a tablicę iloczynu zadeklarowano na 64. Zapis za końcem uszkadzał sąsiednią pamięć, co początkowo objawiało się błędnymi wynikami i dopiero po dodaniu szerszego skanu stało się awarią. Wynikająca z tego reguła warta zastosowania do każdego bufora numerycznego o stałym rozmiarze: wyskaluj go według szerokości iloczynu w najgorszym przypadku, dodaj zapas i nigdy więcej o tym nie myśl. Tablica w kodzie wysyłkowym ma 68 limb

Druga to poplątany kształt potęgowania. Istnieją dwie poprawne postacie square-and-multiply i zużywają one wykładnik w przeciwnych kierunkach: postać od prawej do lewej najpierw mnoży, potem podnosi podstawę do kwadratu i musi czytać bity od najmniej znaczącego końca, natomiast postać od lewej do prawej najpierw podnosi do kwadratu, potem mnoży i czyta od najbardziej znaczącego końca. Pętla inwersji modularnej miała ciało od prawej do lewej z przejściem po bitach od najbardziej znaczących. Obie połówki są podręcznikowe, ich połączenie już nie, a wynikiem jest zła odwrotność, która wciąż wygląda jak wiarygodny element ciała

// Podwajanie i dodawanie punktów w rzucie Jacobiego, gdy rekord
// docelowy może być tą samą zmienną co źródłowy. Kopia całego
// rekordu na wejściu to jedyna niezawodna obrona: zapis limb R
// zanieczyszcza późniejsze odczyty P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // najpierw kopia, potem obliczenia wyłącznie z Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Dwie lekcje procesowe, które kosztowały więcej niż błędy

Przyrostowe hot-fixowanie nie zbiega się do poprawnego modułu kryptograficznego. Jeden ze szkiców łatono wielokrotnie, aż nosił 32 zdublowane procedury i uszkodzoną strukturę, a naprawiło go dopiero przepisanie od nowa. Wzorzec do przyjęcia: albo napisz to raz na podstawie zwalidowanego lustra, albo przepisz od nowa; sekwencja lokalnych poprawek arytmetyki, której jeszcze nie rozumiesz, narasta szybciej, niż ją prostuje

I sprawdź znacznik czasu pliku wykonywalnego, zanim uwierzysz w wynik testu. Kompilacja przyrostowa, która się kompiluje, ale nie konsoliduje ponownie, uruchamia poprzedni plik binarny, co wyprodukowało całą rundę fałszywych tropów o brakujących sondach i zdublowanym wyjściu. Przy debugowaniu kryptografii niewyjaśniony wynik powinien wywołać pytanie „czy to plik binarny, który właśnie zbudowano”, zanim padnie pytanie „czy algorytm jest błędny”

Wydajność, zakres i jak to wywoływać

Redukcja modularna w module Brainpool to bitowo-szeregowe shift-subtract od najwyższego ustawionego bitu iloczynu, więc mnożenie kosztuje z grubsza rząd szerokości bitowej. Weryfikacja P-256 ląduje w niskich setkach milisekund, co dla podpisywania i weryfikacji dokumentów jest bez znaczenia, a dla terminatora TLS byłoby niewystarczające. Redukcja Barretta to oczywisty upgrade i wymaga szerszej wartości roboczej, niż niesie obecna reprezentacja, więc to zmiana na moment, gdy obciążenie jej zażąda, a nie z wyprzedzeniem

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, wewnętrznie SHAKE256, klucze 57-bajtowe
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: wywołujący dostarcza nonce per podpis, więc polityka
  // nonce pozostaje po stronie aplikacji
  Curve := BPLoadCurve(bpP256r1);
  if BPKeyGen(PubX, PubY, PrivateD, Curve) and
     BPSignFixedK(R, S, Hash, PrivateD, Nonce, Curve) then
    Assert(BPVerify(R, S, Hash, PubX, PubY, Curve));
end;

Zwróć uwagę, że punkt wejścia podpisywania Brainpool przyjmuje nonce, zamiast go generować. To celowe: generowanie nonce to najkosztowniejsza w skutkach rzecz, jaką można w ECDSA spartaczyć, bo powtórzona albo przewidywalna wartość ujawnia klucz prywatny, a decyzja o tym, skąd bierze się losowość, należy do aplikacji i jej reżimu zgodności, nie do biblioteki PDF

Te krzywe stoją obok prac postkwantowych opisanych w artykule o FIPS 204 ML-DSA i wpinają się w ten sam potok podpisywania i walidacji, który omawia podpisywanie i walidacja PAdES. Certyfikaty testowe na tych krzywych można wygenerować lokalnie — opisuje to artykuł o certyfikatach samopodpisanych z CryptoAPI. Pełną macierz algorytmów znajdziesz na stronie produktu losLab PDF Developer Library