Αριθμητική καμπυλών NIST σε καθαρό Pascal για υπογραφή PDF

Το HotPDF εκτελεί συμφωνία κλειδιών ελλειπτικών καμπυλών και επαλήθευση υπογραφών για PDF σε καθαρό Object Pascal, χωρίς σύνδεση OpenSSL και χωρίς πάροχο κρυπτογραφίας πλατφόρμας στη διαδρομή. Καλύπτει πέντε καμπύλες: P-256, P-384 και P-521 για τις prime οικογένειες NIST, συν X25519 και X448 για συμφωνία κλειδιών σε καμπύλες Montgomery. Ο λόγος να γραφτεί αυτός ο κώδικας αντί να συνδεθεί είναι η ανάπτυξη, όχι η καθαρότητα. Μια εφαρμογή Delphi ή Free Pascal που διανέμει ένα εκτελέσιμο χωρίς κρυπτογραφικό DLL δεν έχει ασυμφωνία εκδόσεων προς διαχείριση, δεν έχει πάροχο ανά πλατφόρμα προς ανίχνευση, και δεν έχει τίποτα που αλλάζει συμπεριφορά όταν ένας πελάτης ενημερώνει τις βιβλιοθήκες συστήματός του

Το κόστος είναι ότι πλέον η αριθμητική είναι δική σας ευθύνη. Ο modular πολλαπλασιασμός μεγάλων ακεραίων είναι ανελέητος κώδικας: είτε παράγει αποτελέσματα ταυτοίχια σε bytes έναντι δημοσιευμένων δοκιμαστικών διανυσμάτων είτε παράγει πειστικά φαινόμενο σκουπίδια, και η απόσταση ανάμεσα σε αυτές τις δύο καταστάσεις μπορεί να είναι μία σύγκριση. Αυτή είναι η ιστορία εκείνης της σύγκρισης, γιατί το σχήμα του σφάλματος γενικεύεται σε κάθε μεταφορά αριθμητικής σώματος σε Pascal

Γιατί χρειάζεται καθόλου αριθμητική καμπυλών μια βιβλιοθήκη PDF;

Δύο λειτουργίες το τραβάνε μέσα. Η πρώτη είναι η κρυπτογράφηση εγγράφων με δημόσιο κλειδί: ο χειριστής λίστας παραληπτών του ISO 32000 τυλίγει κλειδί ανά έγγραφο για ονομαστικά πιστοποιητικά, και όταν ένας παραλήπτης κατέχει κλειδί EC το τύλιγμα περνά από συμφωνία κλειδιών και όχι από μεταφορά κλειδιών RSA. Χωρίς ECDH δεν υπάρχει τρόπος να ανοίξει τέτοιο έγγραφο. Η δεύτερη είναι η επικύρωση υπογραφών. Η επαλήθευση υπογραφής ECDSA πάνω στα bytes του /ByteRange χρειάζεται πολλαπλασιασμό σημείου στην καμπύλη του υπογράφοντος, και το P-384 είναι συνηθισμένο σε κυβερνητικά προφίλ και προφίλ πιστοποιημένης υπογραφής όπου το P-256 θεωρείται το δάπεδο και όχι ο στόχος. Το HotPDF εκθέτει τα αποτελέσματα αυτής της εργασίας μέσω της διαδρομής επαλήθευσης ECDSA και CMS και μέσω του προσάρμοστου μοντέλου παρόχων υπογραφής

CIOS, και η μία αφαίρεση στο τέλος

Ο πολλαπλασιασμός Montgomery αποφεύγει τη διαίρεση δουλεύοντας σε μετασχηματισμένο πεδίο όπου η αναγωγή είναι ολίσθηση. Η παραλλαγή που χρησιμοποιεί το HotPDF είναι η Coarsely Integrated Operand Scanning, που πλέκει τον πολλαπλασιασμό και την αναγωγή limb προς limb ώστε το ενδιάμεσο να μη μεγαλώνει ποτέ πέρα από το πλάτος του module συν ένα limb. Το σώμα του βρόχου είναι απλό και εύκολο να ελεγχθεί. Η ουρά δεν είναι: μετά από τα πλεκτά περάσματα ο αθροιστής μπορεί να βρίσκεται οπουδήποτε στο εύρος έως δύο φορές το module, οπότε ο αλγόριθμος τελειώνει με μια υπό συνθήκη αφαίρεση που αφαιρεί ένα αντίγραφο του πρώτου αν και μόνο αν ο αθροιστής είναι μεγαλύτερος ή ίσος με αυτόν

Η σύγκριση δύο αριθμών πολλαπλών limbs σημαίνει πορεία από το πιο σημαντικό limb προς τα κάτω κουβαλώντας borrow. Ο προφανής τρόπος να γραφτεί είναι να συγκριθεί το limb του αθροιστή με το limb του module συν το εισερχόμενο borrow. Εκείνη η έκφραση είναι λάθος, και είναι λάθος με τρόπο που οι περισσότερες καμπύλες κρύβουν

// Λάθος: το P[I] + Borrow μπορεί να τυλίξει όταν το P[I] είναι
// $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Σωστό: σύγκριση χωρίς ποτέ πρόσθεση σε limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Πώς μοιάζει στην πραγματικότητα ένα wrap-around borrow;

Μοιάζει με μια καμπύλη που δουλεύει παντού εκτός στην παραγωγή. Οι πρώτοι αριθμοί για P-384 και P-521 περιέχουν limbs που είναι ολόκληρα άσοι, οπότε το P[I] ισούται με $FFFFFFFFFFFFFFFF. Προσθέστε το εισερχόμενο borrow του ενός σε αυτό και ένας unsigned 64-bit τυλίγει στο μηδέν. Η σύγκριση ρωτά μετά αν το limb του αθροιστή είναι μικρότερο του μηδενός, αποφασίζει ότι δεν είναι, και συμπεραίνει ότι δεν χρειάζεται borrow. Ένα limb του αποτελέσματος είναι κατά ένα εκτός

Το P-256 γλιτώνει επειδή κανένα από τα limbs του δεν είναι ολόκληρο άσοι, οπότε η πρόσθεση δεν ξεχειλίζει ποτέ και η ελαττωματική έκφραση τυχαίνει να συμφωνεί με τη σωστή. Αυτό είναι το χειρότερο δυνατό αποτέλεσμα για μια σουίτα test: η πιο τεσταγμένη καμπύλη περνά, οι λιγότερο τεσταγμένες αποτυγχάνουν διαλείπουσα ανάλογα με τις τιμές τελεστών, και η αστοχία αναδύεται ως αποτέλεσμα επαλήθευσης «άκυρη υπογραφή» σε έγγραφα απόλυτα έγκυρα. Το HotPDF κουβαλούσε ρητή πύλη στο P-384 ακριβώς γι' αυτόν τον λόγο, επιστρέφοντας κατάσταση μη διαθέσιμου αντί για λάθος απάντηση, μέχρι η αριθμητική να αποδειχθεί έναντι reference διανυσμάτων

Πώς εντοπίστηκε στην πραγματικότητα το σφάλμα

Όχι διαβάζοντας τον κώδικα. Η παραγωγική σειρά ήταν μηχανική, και είναι επαναχρησιμοποιήσιμη. Πρώτα, εξαλείψτε τις σταθερές: κάθε limb των p, R και R^2 αναπαράχθηκε ανεξάρτητα και συγκρίθηκε limb προς limb, που αποκλείει τη μοναδική πιο συνηθισμένη πηγή σφαλμάτων καμπυλών. Μετά, οπλιστείτε την αριθμητική και όχι το API: μια προσωρινή διαδικασία dump εκτύπωσε τις ενδιάμεσες τιμές του πολλαπλασιασμού Montgomery του R^2, του x^3 και του y^2 για ένα γνωστό σημείο, ώστε να μπορέσουν να ελεγχθούν έναντι αληθείας υπολογισμένης ανεξάρτητα

Εκείνη η σύγκριση έδειξε ευθεία τον ένοχο. Η αλυσίδα x ήταν σωστή από άκρη σε άκρη, ενώ το y^2 διέφερε σε ακριβώς ένα limb κατά ακριβώς ένα. Διαφορά ενός limb κατά ένα δεν είναι σφάλμα πολλαπλασιασμού, σφάλμα διάδοσης κρατούμενου ή σφάλμα σταθεράς· είναι σφάλμα αλυσίδας borrow, και η μόνη αλυσίδα borrow στη ρουτίνα είναι η τελική υπό συνθήκη αφαίρεση. Μια λεπτομέρεια παραλίγο να το εκτροχιάσει: η reference σταθερά που χρησιμοποιήθηκε για το dump είχε γραφτεί η ίδια σε λάθος σειρά bytes στην πρώτη απόπειρα, που παρήγαγε ασυμφωνία στην τιμή y και υπέδειξε σύντομα ένα δεύτερο, ανύπαρκτο ελάττωμα. Επαληθεύστε την endianness της αλήθειας-αναφοράς σας πριν την εμπιστευτείτε για να κατηγορήσει τον κώδικά σας

Οι γειτονικές παγίδες στην ίδια ρουτίνα

Τρεις ακόμα λειτουργίες αστοχίας ζουν λίγες γραμμές μακριά από εκείνη τη σύγκριση, και και οι τρεις ήταν ζωντανές σε κάποιο σημείο κατά την ανάπτυξη

// 1. Ο αθροιστής έχει ένα limb πάνω από το πλάτος του module. Η σύγκριση
//    μόνο των χαμηλών L limbs χάνει την περίπτωση όπου το T ισούται
//    ακριβώς με p συν 2^(64*L), που συμβαίνει για σημαντικό μερίδιο
//    τυχαίων εισόδων επειδή το 2p ξεπερνά το 2^256 για P-256 και το
//    2^384 για P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Μια γενική αφαίρεση πολλαπλών limbs έχει τον ίδιο κίνδυνο τυλίγματος:
//    όταν το Y[I] είναι $FFFFFFFFFFFFFFFF, το Y[I] + Borrow τυλίγει στο
//    μηδέν και το borrow πρέπει να επιβιώσει στο επόμενο limb αντί
//    να μηδενιστεί
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Η τρίτη δεν είναι κώδικας, είναι προέλευση. Ο πρώτος αριθμός για P-521 μεταγράφηκε αρχικά με 130 δεκαεξαδικά ψηφία αντί για 131, ένα F λιγότερο, και οι σταθερές Montgomery υπολογίστηκαν κατόπιν από εκείνον τον λάθος πρώτο, οπότε οι σταθερές ήταν αυτοσυνεπείς και από κοινού λάθος. Οι παράμετροι καμπυλών πρέπει να εξάγονται, ποτέ να πληκτρολογούνται: υπολογίστε το R ως (1 shl (64 * L)) mod p από τον πρώτο που πραγματικά χρησιμοποιείτε, και μετά διασταυρώστε το R * R mod p με την τιμή που ισχυρίζεται η σταθερά R^2 σας. Ένα ζευγάρι σταθερών που συμφωνούν μεταξύ τους δεν αποδεικνύει τίποτα για καμία

Στρατηγική επαλήθευσης που κλιμακώνεται πέρα από μία καμπύλη

Η τεχνική που έκανε το X25519 και το X448 διαχειρίσιμα ήταν η γραφή υλοποίησης-κατοπτρισμού σε γλώσσα με απεριόριστους ακεραίους και η μεταγραφή της ροής ελέγχου της Pascal σε αυτήν γραμμή προς γραμμή. Όταν ο κατοπτρισμός παράγει τη σωστή απάντηση και η Pascal όχι, το ελάττωμα είναι ολίσθηση μεταγραφής και η εξέταση της ίδιας ενδιάμεσης τιμής και στις δύο υλοποιήσεις τη βρίσκει σε δευτερόλεπτα. Και τα τρία κλασικά λάθη της σκάλας RFC 7748 πιάθηκαν έτσι: ένα swap σταθερού χρόνου του οποίου η δεύτερη γραμμή επαναχρησιμοποιούσε την ήδη αντιμετατεθέμενη τιμή, μια τελική αντιστροφή που επέστρεφε το z στη δύναμη μείον ένα αντί να τον πολλαπλασιάσει μέσα στο X, και ένας πολλαπλασιασμός μικρής σταθεράς που συναρμολογούσε γινόμενα ημι-λέξεων με bitwise or και έχανε το κρατούμενο

Για δοκιμαστικό υλικό, πάρετε διανύσματα ως bytes και όχι ως κείμενο. Η εξαγωγή ιδιωτικού κλειδιού με text pattern είναι ο τρόπος που μια σωστή υλοποίηση κατηγορείται για σφάλμα κατά ένα byte που ζει εξ ολοκλήρου στο βήμα εξαγωγής. Κόψτε το hex από την κωδικοποίηση DER σε γνωστά offsets και συγκρίνετε πίνακες bytes

Με τη διόρθωση της αλυσίδας borrow, και οι πέντε καμπύλες ταιριάζουν με δημοσιευμένα reference διανύσματα byte προς byte, και το HotPDF δεν φράσσει πλέον καμία. Αν ενσωματώνετε υπογραφή βάσει πιστοποιητικών ή κρυπτογράφηση λίστας παραληπτών, το πρακτικό συμπέρασμα είναι ότι η επιλογή καμπύλης είναι πλέον απόφαση πολιτικής και όχι ερώτημα δυνατότητας· τα προφίλ και οι παγίδες σειράς bytes της πλευράς υπογραφής καλύπτονται στον οδηγό υπογραφής PAdES. Οι λεπτομέρειες του στοιχείου και ο υποστηριζόμενος αλγοριθμικός πίνακας βρίσκονται στη σελίδα προϊόντος HotPDF Delphi PDF component