Arytmetyka krzywych NIST w czystym Pascalu dla podpisu PDF

HotPDF wykonuje uzgadnianie kluczy na krzywych eliptycznych i weryfikację podpisów dla PDF w czystym Object Pascalu, bez wiązania z OpenSSL i bez platformowego dostawcy kryptografii w ścieżce. To obejmuje pięć krzywych: P-256, P-384 i P-521 dla rodzin pierwszych NIST, plus X25519 i X448 do uzgadniania kluczy na krzywej Montgomery. Powodem napisania tego kodu, zamiast linkowania, jest wdrożenie, nie czystość. Aplikacja Delphi albo Free Pascal, która dostarcza jeden plik wykonywalny i żadnej kryptograficznej biblioteki DLL, nie ma rozjazdu wersji do zarządzania, dostawcy per platforma do wykrycia ani niczego, co zmienia zachowanie, gdy klient załata swoje biblioteki systemowe

Koszt jest taki, że arytmetyka jest teraz twoja. Modularne mnożenie wielkich liczb całkowitych to kod nieprzebaczający: albo produkuje wyniki identyczne bajtowo względem opublikowanych wektorów testowych, albo produkuje śmieci wyglądające wiarygodnie, a odległość między tymi dwoma stanami może być jednym porównaniem. To jest historia tamtego porównania, bo kształt błędu uogólnia się na każdy pascalski port arytmetyki ciała

Po co w ogóle bibliotece PDF arytmetyka krzywych?

Dwie funkcje to wciągają. Pierwsza to szyfrowanie dokumentów kluczem publicznym: handler listy odbiorców ISO 32000 opakowuje klucz per dokument dla nazwanych certyfikatów, a gdy odbiorca posiada klucz EC, opakowanie idzie przez uzgadnianie kluczy, a nie transport klucza RSA. Bez ECDH nie ma sposobu otwarcia takiego dokumentu. Druga to walidacja podpisów. Weryfikacja podpisu ECDSA nad bajtami /ByteRange potrzebuje mnożenia punktów na krzywej podpisującego, a P-384 jest częsty w profilach rządowych i podpisu kwalifikowanego, gdzie P-256 uchodzi za minimum, a nie cel. HotPDF wystawia wyniki tej pracy przez ścieżkę weryfikacji ECDSA i CMS oraz przez model podłączanych dostawców podpisów

CIOS i jedno odejmowanie na końcu

Mnożenie Montgomery unika dzielenia, pracując w przekształconej domenie, gdzie redukcja to przesunięcie. Wariant używany przez HotPDF to Coarsely Integrated Operand Scanning, który przeplata mnożenie i redukcję limb po limb, więc wartość pośrednia nigdy nie urośnie ponad szerokość modulusu plus jeden limb. Ciało pętli jest proste i łatwe w testowaniu. Ogon już nie: po przeplotach akumulator może być gdziekolwiek w zakresie do dwukrotności modulusu, więc algorytm kończy się warunkowym odejmowaniem, które usuwa jedną kopię liczby pierwszej wtedy i tylko wtedy, gdy akumulator jest od niej większy albo równy

Porównywanie dwóch liczb wielo-limb znaczy przechodzenie od najbardziej znaczącego limba w dół, niosąc pożyczkę. Oczywisty sposób napisania tego to porównanie limba akumulatora z limem modulusu plus przychodząca pożyczka. To wyrażenie jest złe, i to złe w sposób, który większość krzywych ukrywa

// Źle: P[I] + Borrow może się zawinąć, gdy P[I] to $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Poprawnie: porównuj, nigdy nie dodając do limba
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Jak naprawdę wygląda zawinięcie pożyczki?

Wygląda jak krzywa działająca wszędzie poza produkcją. Liczby pierwsze dla P-384 i P-521 zawierają limby złożone z samych jedynek, więc P[I] równa się $FFFFFFFFFFFFFFFF. Dodaj przychodzącą pożyczkę równą jeden i 64-bitowa liczba bez znaku zawija się do zera. Porównanie pyta potem, czy limb akumulatora jest mniejszy od zera, stwierdza, że nie, i wnioskuje, że pożyczka nie jest potrzebna. Jeden limb wyniku jest przekłamany o jeden

P-256 się wymyka, bo żaden z jego limbów nie jest z samych jedynek, więc dodawanie nigdy się nie przepełnia, a błędne wyrażenie akurat zgadza się z poprawnym. To najgorszy możliwy wynik dla zestawu testów: najczęściej testowana krzywa przechodzi, słabiej testowane zawodzą okresowo zależnie od wartości operandów, a awaria wychodzi jako wynik weryfikacji „niepoprawny podpis” na dokumentach, które są całkowicie poprawne. HotPDF nosił jawną bramkę na P-384 dokładnie z tego powodu, zwracając status niedostępności zamiast złej odpowiedzi, dopóki arytmetyka nie została udowodniona względem wektorów referencyjnych

Jak błąd naprawdę zlokalizowano

Nie przez czytanie kodu. Produktywna sekwencja była mechaniczna i nadaje się do ponownego użycia. Po pierwsze, wyeliminuj stałe: każdy limb p, R i R^2 był regenerowany niezależnie i porównywany limb po limb, co eliminuje najczęstsze pojedyncze źródło błędów krzywych. Po drugie, instrumentuj arytmetykę, a nie API: tymczasowa procedura zrzutu drukowała wartości pośrednie mnożenia Montgomery R^2, x^3 i y^2 dla znanego punktu, żeby dało się je sprawdzić względem niezależnie policzonej prawdy

To porównanie wskazało prosto na winowajcę. Łańcuch x był poprawny od końca do końca, podczas gdy y^2 różnił się w dokładnie jednym limb o dokładnie jeden. Różnica jednego limba o jeden to nie błąd mnożenia, błąd propagacji przeniesień ani błąd stałej; to błąd łańcucha pożyczek, a jedyny łańcuch pożyczek w procedurze to końcowe odejmowanie warunkowe. Jeden szczegół niemal to wykoleił: referencyjna stała użyta do zrzutu była sama zapisana w złej kolejności bajtów przy pierwszej próbie, co wyprodukowało niezgodność w wartości y i przez chwilę sugerowało drugi, nieistniejący defekt. Zweryfikuj endianowość swojej prawdy odniesienia, zanim zaufasz jej w oskarżaniu twojego kodu

Sąsiednie pułapki w tej samej procedurze

Trzy kolejne tryby awarii mieszkają w kilku liniach od tamtego porównania, a wszystkie trzy były żywe w pewnym momencie rozwoju

// 1. Akumulator ma jeden limb ponad szerokość modulusu. Porównanie tylko
//    dolnych L limbów gubi przypadek, gdy T równa się dokładnie p plus
//    2^(64*L), co zdarza się dla istotnej części losowych wejść, bo 2p
//    przekracza 2^256 dla P-256 i 2^384 dla P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Generyczne odejmowanie wielo-limb ma to samo zagrożenie zawinięciem:
//    gdy Y[I] to $FFFFFFFFFFFFFFFF, Y[I] + Borrow zawija się do zera, a
//    pożyczka musi przeżyć do następnego limba, zamiast zostać wyzerowana
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Trzeci to nie kod, tylko pochodzenie. Liczba pierwsza dla P-521 była początkowo przepisana ze 130 cyframi szesnastkowymi zamiast 131, jednym F za mało, a stałe Montgomery policzono potem z tej złej liczby pierwszej, więc stałe były samospójne i łącznie złe. Parametry krzywych muszą być wyprowadzane, nigdy wklepywane: policz R jako (1 shl (64 * L)) mod p z liczby pierwszej, której faktycznie używasz, a potem skontroluj krzyżowo R * R mod p względem wartości, na jaką powołuje się twoja stała R^2. Para stałych zgadzających się ze sobą nie dowodzi niczego o żadnej z nich

Strategia weryfikacji, która skaluje się poza jedną krzywą

Techniką, która uczyniła X25519 i X448 opanowywalnymi, było napisanie implementacji lustrzanej w języku o nieograniczonych liczbach całkowitych i przepisanie do niej przepływu sterowania Pascala linia po linii. Gdy lustro daje właściwą odpowiedź, a Pascal nie, defektem jest potknięcie transkrypcji, a zbadanie tej samej wartości pośredniej w obu implementacjach znajduje je w sekundy. Wszystkie trzy klasyczne błędy drabinki RFC 7748 zostały tak złapane: stałoczasowy swap, którego druga linia używała już zamienionej wartości, końcowa inwersja zwracająca z do potęgi minus jeden zamiast przemnożyć ją do X, oraz mnożenie małą stałą składające produkty półsłowne bitowym or i gubiące przeniesienie

Materiał testowy bierz jako bajty, nie jako tekst. Wyodrębnianie klucza prywatnego wzorcem tekstowym to sposób, by poprawna implementacja została oskarżona o błąd o jeden bajt, który mieszka całkowicie w kroku ekstrakcji. Wytnij hex z kodowania DER pod znanymi offsetami i porównuj tablice bajtów

Po poprawieniu łańcucha pożyczek wszystkie pięć krzywych zgadza się bajt w bajt z opublikowanymi wektorami referencyjnymi, a HotPDF już nie bramkuje żadnej z nich. Jeśli integrujesz podpisywanie na certyfikatach albo szyfrowanie listy odbiorców, praktyczny wniosek jest taki, że wybór krzywej jest teraz decyzją polityki, a nie pytaniem o możliwość; profile i pułapki kolejności bajtów po stronie podpisującej są omówione w przewodniku podpisywania PAdES. Szczegóły komponentu i wspierana macierz algorytmów są na stronie produktu HotPDF Delphi PDF component