Το SLH-DSA εξηγημένο μαθηματικά

1. Περί τίνος πρόκειται

Στο McGesund, οι πελάτες των πακέτων Αξιολογήσεις Premium και Σήματα Premium μπορούν να επιλέξουν το επίπεδο υπογραφής PQ-Dual-Diversified. Τότε κάθε κωδικός QR φέρει, εκτός από την κλασική υπογραφή Ed25519, δύο κβαντικά ανθεκτικές υπογραφές: ML-DSA-87 και SLH-DSA-SHA2-256f.

Αυτό το άρθρο εξηγεί τη δεύτερη. Είναι κατασκευασμένη διαφορετικά από οτιδήποτε άλλο χρησιμοποιούμε.

Το SLH-DSA δεν είναι κρυπτογράφηση. Το περιεχόμενο παραμένει δημόσια αναγνώσιμο. Το SLH-DSA αποδεικνύει προέλευση και ακεραιότητα — όπως κάθε ψηφιακή υπογραφή.

Το SLH-DSA σημαίνει ολογράφως Stateless Hash-Based Digital Signature Algorithm. Αναπτύχθηκε από το SPHINCS+ και τυποποιήθηκε το 2024 ως FIPS 205. Το όνομα προδίδει ήδη την ιδιαιτερότητά του: η μέθοδος χρησιμοποιεί μόνο συναρτήσεις κατακερματισμού. Ούτε πλέγματα, ούτε ελλειπτικές καμπύλες, ούτε μεγάλους πρώτους αριθμούς.

---

2. Τι ακριβώς υπογράφεται;

Στο McGesund, το SLH-DSA υπογράφει την ίδια εγγραφή δεδομένων που καλύπτει και η υπογραφή Ed25519 στον κωδικό QR: το payload του κωδικού QR. Περιέχει μεταξύ άλλων σε ποια επιχείρηση ανήκει ο κωδικός (fid), τι είδους είναι (typ), πότε εκδόθηκε (iat) και μέχρι πότε ισχύει (exp) — ως μια συμπαγώς κωδικοποιημένη ακολουθία byte (CBOR).

Αυτή η ακολουθία byte είναι το μήνυμά μας $M$. Αν κάποιος αλλάξει εκ των υστέρων έστω και ένα bit, καμία από τις υπογραφές δεν ταιριάζει πλέον.

Η υπογραφή SLH-DSA δεν βρίσκεται μέσα στον ίδιο τον κωδικό QR. Με περίπου 49 KB είναι πολύ μεγάλη γι' αυτό. Αποθηκεύεται ως ξεχωριστή «σφραγίδα» στην εγγραφή QR στο backend του McGesund και φορτώνεται στο πρόγραμμα περιήγησης όταν κάνετε κλικ στο «Έλεγχος αυθεντικότητας».

---

3. Γιατί μια μέθοδος μόνο από συναρτήσεις κατακερματισμού;

Κάθε μέθοδος υπογραφής στηρίζεται σε ένα πρόβλημα που χωρίς το μυστικό κλειδί είναι πρακτικά άλυτο:

Το Ed25519 θα το έσπαγε ένας μεγάλος κβαντικός υπολογιστής. Τα FALCON και ML-DSA θεωρούνται κβαντικά ανθεκτικά — όμως και τα δύο στηρίζονται σε προβλήματα πλεγμάτων. Αν κάποια μέρα βρεθεί μια θεμελιώδης επίθεση κατά των πλεγμάτων, θα επηρεαστούν και τα δύο ταυτόχρονα.

Το SLH-DSA, αντίθετα, χρειάζεται μόνο η συνάρτηση κατακερματισμού να κάνει αυτό για το οποίο κατασκευάστηκε:

Αυτή είναι η επί μακρότερον και διεξοδικότερα μελετημένη υπόθεση όλης της κρυπτογραφίας. Ακόμη και ένας κβαντικός υπολογιστής βοηθά εδώ μόνο περιορισμένα: ο αλγόριθμος του Grover υποδιπλασιάζει τα bit ασφάλειας. Γι' αυτό η παραλλαγή 256 χρησιμοποιεί τιμές κατακερματισμού $n = 32$ byte $= 256$ bit — μετά τον Grover απομένουν ακόμη 128 bit.

Ακριβώς γι' αυτό το επίπεδο λέγεται Diversified: Το ML-DSA (πλέγματα) και το SLH-DSA (κατακερματισμός) προέρχονται από διαφορετικές μαθηματικές οικογένειες. Αν πέσει η μία, η άλλη εξακολουθεί να ισχύει.

---

4. Δομικό στοιχείο 1: υπογραφή με αλυσίδες κατακερματισμού (WOTS+)

Η βασική ιδέα είναι εκπληκτικά απλή. Ξεκινάμε με ένα μόνο ψηφίο.

Πάρτε μια μυστική τυχαία τιμή $s$ και κατακερματίστε την ξανά και ξανά:

Το τέλος της αλυσίδας, $p$, δημοσιεύεται. Αυτό είναι το δημόσιο κλειδί για αυτό το ένα ψηφίο.

Για να υπογραφεί ένα ψηφίο $d$ μεταξύ 0 και 15, αποκαλύπτεται η τιμή της αλυσίδας στη θέση $d$:

Όποιος θέλει να ελέγξει, κατακερματίζει το $\sigma$ άλλες $15 - d$ φορές. Αν προκύψει ακριβώς το $p$, η υπογραφή είναι γνήσια:

Ένα μικρό παράδειγμα

Υπογράφουμε το ψηφίο $d = 6$:

• Ο υπογράφων δημοσιεύει $\sigma = H^6(s)$.
• Ο ελεγκτής υπολογίζει $H^{9}(\sigma) = H^{15}(s)$ και συγκρίνει με το $p$. Ταιριάζει.

Ένας πλαστογράφος που έχει δει το $\sigma$ μπορεί χωρίς κόπο να υπολογίσει από αυτό τα $H^7(s)$, $H^8(s)$ κ.ο.κ. — δηλαδή να υπογράψει μεγαλύτερα ψηφία. Μικρότερα δεν μπορεί, γιατί για αυτό θα έπρεπε να κατακερματίσει προς τα πίσω.

Το άθροισμα ελέγχου κατά του «μετρήματος προς τα πάνω»

Για να μην μπορεί κανείς απλώς να αυξάνει ψηφία, υπογράφεται επιπλέον ένα άθροισμα ελέγχου:

Αν ένας πλαστογράφος αυξήσει ένα ψηφίο του μηνύματος, το $C$ γίνεται μικρότερο — και για αυτό θα έπρεπε να υπολογίσει προς τα πίσω στην αλυσίδα του αθροίσματος ελέγχου. Έτσι αποκλείονται και οι δύο κατευθύνσεις.

Σε κλίμακα μιας τιμής κατακερματισμού

Μια τιμή κατακερματισμού 32 byte έχει 64 ψηφία στη βάση 16. Σε αυτά προστίθενται 3 ψηφία αθροίσματος ελέγχου:

Μια τέτοια υπογραφή ονομάζεται WOTS+ (Winternitz One-Time Signature). Το μεγάλο της μειονέκτημα κρύβεται στο όνομα: One-Time, μίας χρήσης. Όποιος υπογράψει δύο διαφορετικά μηνύματα με το ίδιο κλειδί, αποκαλύπτει τόσες τιμές αλυσίδων ώστε οι πλαστογραφίες γίνονται δυνατές.

---

5. Δομικό στοιχείο 2: πολλά κλειδιά μίας χρήσης κάτω από μία στέγη (δέντρο Merkle)

Αν κάθε κλειδί επιτρέπεται να χρησιμοποιηθεί μόνο μία φορά, χρειάζονται πάρα πολλά — αλλά θέλουμε να δημοσιεύσουμε μόνο ένα δημόσιο κλειδί.

Η λύση είναι ένα δέντρο Merkle: τα δημόσια κλειδιά $2^{h'}$ ζευγών WOTS+ σχηματίζουν τα φύλλα. Κάθε δύο γειτονικά κατακερματίζονται μαζί, τα αποτελέσματα ξανά ανά ζεύγη, μέχρι να μείνει στην κορυφή μία μόνο ρίζα.

Στο SLH-DSA-SHA2-256f κάθε δέντρο έχει ύψος $h' = 4$, δηλαδή $2^4 = 16$ φύλλα.

Για να αποδειχθεί ότι ένα συγκεκριμένο φύλλο ανήκει στο δέντρο, παρέχεται η διαδρομή αυθεντικοποίησης: οι 4 αδελφοί κόμβοι στον δρόμο προς τα πάνω. Με αυτούς ο ελεγκτής κατακερματίζει από το φύλλο μέχρι τη ρίζα. Αν προκύψει η γνωστή ρίζα, το φύλλο ανήκει στο δέντρο.

---

6. Δομικό στοιχείο 3: δέντρα πάνω σε δέντρα (υπερδέντρο)

16 κλειδιά μίας χρήσης φυσικά δεν αρκούν. Γι' αυτό το SLH-DSA στοιβάζει δέντρα το ένα πάνω στο άλλο: η ρίζα ενός δέντρου υπογράφεται με ένα κλειδί WOTS+ του δέντρου από πάνω. Αυτός ο πύργος ονομάζεται υπερδέντρο.

Στο SLH-DSA-SHA2-256f υπάρχουν $d = 17$ στρώσεις, καθεμία με ύψος 4:

Στο κατώτατο επίπεδο είναι έτσι διαθέσιμα

φύλλα. Η ρίζα του ανώτατου δέντρου ονομάζεται $\text{PK.root}$ — αυτή είναι το πραγματικό δημόσιο κλειδί.

Σημαντικό: κανείς δεν υπολογίζει αυτά τα δέντρα εκ των προτέρων. Όλες οι μυστικές τιμές παράγονται όποτε χρειάζονται από μια μυστική αρχική τιμή $\text{SK.seed}$. Αποθηκεύονται μόνο τέσσερις τιμές των 32 byte η καθεμία:

Το ιδιωτικό κλειδί αποτελείται και από τις τέσσερις (128 byte), το δημόσιο μόνο από τα PK.seed και PK.root (64 byte).

---

7. Δομικό στοιχείο 4: ένα δάσος κατά των τυχαίων συμπτώσεων (FORS)

Τώρα το πραγματικό πρόβλημα: πώς ξέρει ο υπογράφων ποιο από τα $2^{68}$ φύλλα είναι ακόμη αχρησιμοποίητο;

Παλαιότερες μέθοδοι βασισμένες στον κατακερματισμό (XMSS, LMS) τηρούν για τον σκοπό αυτό έναν μετρητή. Αυτός δεν πρέπει ποτέ να επαναφερθεί — ούτε από ένα αντίγραφο ασφαλείας, ούτε από έναν δεύτερο διακομιστή. Αν συμβεί παρ' όλα αυτά, ένα κλειδί μίας χρήσης χρησιμοποιείται δύο φορές και η μέθοδος έχει σπάσει. Τέτοιες μέθοδοι ονομάζονται με κατάσταση.

Το SLH-DSA είναι χωρίς κατάσταση: το φύλλο επιλέγεται ψευδοτυχαία από το ίδιο το μήνυμα. Τότε μπορεί να συμβεί δύο μηνύματα να πέσουν στο ίδιο φύλλο. Γι' αυτό στο κατώτατο επίπεδο δεν κρέμεται μια υπογραφή μίας χρήσης, αλλά μια υπογραφή λίγων χρήσεων: το FORS (Forest of Random Subsets).

Το FORS αποτελείται από $k = 35$ μικρά δέντρα Merkle με $2^a = 2^9 = 512$ φύλλα το καθένα. Τα φύλλα είναι μυστικές τυχαίες τιμές.

Για την υπογραφή, ο κατακερματισμός του μηνύματος διασπάται σε 35 αριθμούς των 9 bit ο καθένας. Κάθε αριθμός επιλέγει στο «δικό του» δέντρο ακριβώς ένα φύλλο. Η υπογραφή περιέχει για κάθε δέντρο:

• τη μυστική τιμή αυτού του φύλλου
• τη διαδρομή αυθεντικοποίησής του (9 κόμβοι)

Ένας πλαστογράφος θα έπρεπε, για ένα άλλο μήνυμα, να πετύχει σε και τα 35 δέντρα φύλλα των οποίων τα μυστικά έχουν ήδη αποκαλυφθεί. Ακόμη κι αν η ίδια παρουσία FORS έχει χρησιμοποιηθεί μερικές φορές, αυτό είναι μάταιο.

---

8. Ολόκληρη η διαδικασία της υπογραφής

1. Τυχαία συνιστώσα. Από το $\text{SK.prf}$, έναν νέο τυχαίο αριθμό και το μήνυμα προκύπτει μια τιμή $R$ 32 byte.
2. Κατακερματισμός του μηνύματος.
   $$\text{digest} = H_{\text{msg}}(R,\ \text{PK.seed},\ \text{PK.root},\ M)$$
   Τα 49 byte της σύνοψης μοιράζονται: 40 byte επιλέγουν τα 35 φύλλα FORS, το υπόλοιπο καθορίζει ποιο δέντρο (idx_tree) και ποιο φύλλο (idx_leaf) στο κατώτατο επίπεδο του υπερδέντρου χρησιμοποιείται.
3. Υπογραφή FORS επί του μηνύματος. Από αυτήν προκύπτει ένα δημόσιο κλειδί FORS.
4. Υπογραφή υπερδέντρου επί αυτού του κλειδιού FORS: 17 υπογραφές WOTS+, καθεμία με μια διαδρομή αυθεντικοποίησης, στρώση προς στρώση μέχρι το $\text{PK.root}$.

Η τελική υπογραφή είναι απλώς η συνένωση:

---

9. Γιατί η υπογραφή έχει μέγεθος 49.856 byte

Με τις παραμέτρους του SLH-DSA-SHA2-256f, το μέγεθος μπορεί να υπολογιστεί ακριβώς ($n = 32$ byte ανά τιμή κατακερματισμού):

Για σύγκριση: μια υπογραφή Ed25519 έχει 64 byte, το ML-DSA-87 έχει 4.627 byte. Το μέγεθος είναι το τίμημα για το ότι το SLH-DSA αρκείται σε τίποτα άλλο πέρα από συναρτήσεις κατακερματισμού.

---

10. Πώς ελέγχει το πρόγραμμα περιήγησης

Στο SLH-DSA, έλεγχος σημαίνει: εκ νέου κατακερματισμός.

1. Υπολογίζεται ξανά η σύνοψη από το $R$, το δημόσιο κλειδί και το μήνυμα.
2. Από τα 35 αποκαλυφθέντα φύλλα FORS και τις διαδρομές τους υπολογίζονται οι 35 ρίζες των δέντρων και από αυτές το δημόσιο κλειδί FORS.
3. Με καθεμία από τις 17 υπογραφές WOTS+ οι αλυσίδες κατακερματίζονται μέχρι το τέλος, σχηματίζεται το δημόσιο κλειδί WOTS+ και μέσω της διαδρομής κατακερματίζεται προς τα πάνω μέχρι τη ρίζα του δέντρου.
4. Στο τέλος πρέπει να προκύψει ακριβώς το $\text{PK.root}$.

Πρόκειται για μερικές χιλιάδες κλήσεις της συνάρτησης κατακερματισμού — παιχνιδάκι για έναν υπολογιστή. Στο πρόγραμμα περιήγησης ο έλεγχος διαρκεί σε εμάς περίπου 6 έως 12 χιλιοστά του δευτερολέπτου.

---

11. Τι συμβαίνει αν κάποιος αλλάξει την εγγραφή δεδομένων;

Αν αλλάξει έστω και ένα bit του μηνύματος $M$, η σύνοψη αλλάζει εντελώς. Έτσι οι 35 αριθμοί δείχνουν σε άλλα φύλλα FORS και η μέθοδος σε άλλη θέση στο υπερδέντρο.

Τα αποκαλυφθέντα μυστικά δεν ταιριάζουν πλέον: οι ρίζες που υπολογίζονται ξανά αποκλίνουν και στο τέλος δεν προκύπτει το $\text{PK.root}$. Ο έλεγχος αποτυγχάνει.

Για να κατασκευάσει παρ' όλα αυτά μια έγκυρη υπογραφή, ένας επιτιθέμενος θα έπρεπε να γνωρίζει μυστικά που δεν δημοσιεύθηκαν ποτέ — δηλαδή να υπολογίσει μια συνάρτηση κατακερματισμού προς τα πίσω.

---

12. Γιατί ακριβώς 256f;

Το FIPS 205 ορίζει δώδεκα σύνολα παραμέτρων: δύο οικογένειες κατακερματισμού (SHA-2 και SHAKE), τρία επίπεδα ασφάλειας (128, 192, 256) και για το καθένα μία γρήγορη («f») και μία μικρή («s») παραλλαγή.

Το 256 σημαίνει κατηγορία ασφάλειας 5 του NIST — το ίδιο επίπεδο με τα FALCON-1024 και ML-DSA-87.

Επιλέξαμε το «f» επειδή οι επιχειρήσεις μπορούν να εκδώσουν έως 500 κωδικούς QR με μία κίνηση. Με το «s» η υπογραφή θα διαρκούσε πάνω από 20 λεπτά, με το «f» κάτω από ένα λεπτό. Σε αντάλλαγμα η υπογραφή είναι μεγαλύτερη — αφού δεν βρίσκεται μέσα στον κωδικό QR, αυτό είναι ανεκτό.

SHA-2 αντί για SHAKE, επειδή τα SHA-256 και SHA-512 διαθέτουν επιτάχυνση υλικού σε πρακτικά κάθε συσκευή.

---

13. Τυχαιότητα κατά την υπογραφή

Το FIPS 205 επιτρέπει δύο τρόπους παραγωγής του $R$:

• ντετερμινιστικά: ίδιο μήνυμα, ίδια υπογραφή
• τυχαιοποιημένα («hedged»): συμμετέχει και ένας νέος τυχαίος αριθμός

Χρησιμοποιούμε την τυχαιοποιημένη παραλλαγή. Δύο υπογραφές επί του ίδιου μηνύματος φαίνονται επομένως διαφορετικές — και οι δύο είναι έγκυρες. Αυτό δυσχεραίνει επιθέσεις που συνδυάζουν μετρήσεις στη συσκευή (κατανάλωση ρεύματος, χρόνος) με επαναλαμβανόμενες υπογραφές.

---

14. Τι κάνει συγκεκριμένα το McGesund με αυτό

Το επίπεδο. Το PQ-Dual-Diversified διατίθεται στα Αξιολογήσεις Premium και Σήματα Premium. Ένας κωδικός QR φέρει τότε τρεις υπογραφές:

Η διαδικασία υπογραφής. Μια υπογραφή SLH-DSA κοστίζει περίπου ένα τέταρτο του δευτερολέπτου υπολογιστικού χρόνου. Για να παραμένει ο διακομιστής στο μεταξύ διαθέσιμος για όλους τους άλλους, τους υπολογισμούς εκτελούν ξεχωριστά νήματα παρασκηνίου.

Ο έλεγχος. Το πρόγραμμα περιήγησης του αναγνώστη φορτώνει και τις δύο σφραγίδες και τις ελέγχει με το ίδιο άρθρωμα WASM όπως όλες τις άλλες υπογραφές PQ. Εμείς παρέχουμε τα δεδομένα· ο υπολογισμός γίνεται στη συσκευή του επισκέπτη.

Η αντιπαραβολή με το NIST. Το άρθρωμά μας περνά τα επίσημα διανύσματα δοκιμής του NIST για το SLH-DSA-SHA2-256f: από τις αρχικές τιμές του NIST προκύπτουν byte προς byte τα ίδια κλειδιά, και όλες οι σκόπιμα αλλοιωμένες υπογραφές απορρίπτονται. Μπορείτε να το ελέγξετε μόνοι σας στο πρόγραμμα περιήγησης στη σελίδα δοκιμών NIST.

Το χρονικό αγκύρωμα. Όπως για όλα τα κλειδιά, το αποτύπωμα του κλειδιού SLH-DSA αγκυρώνεται μέσω OpenTimestamps σε ένα μπλοκ του Bitcoin.

---

15. SLH-DSA, ML-DSA και FALCON δίπλα δίπλα

Με λίγα λόγια: το SLH-DSA είναι η πιο αργή και η μεγαλύτερη από τις τρεις μεθόδους — και η πιο συντηρητική. Δεν βασίζεται σε τίποτα που δεν προϋποθέτει ήδη ούτως ή άλλως κάθε άλλη υπογραφή: μια ασφαλή συνάρτηση κατακερματισμού.

---

16. Μια πρόταση για να κρατήσετε

Όποιος κατέχει τη μυστική αρχική τιμή, υπογράφει σε ένα τέταρτο του δευτερολέπτου. Όποιος δεν την κατέχει, θα έπρεπε να υπολογίσει το SHA-256 ή το SHA-512 προς τα πίσω — ακόμη και με κβαντικό υπολογιστή.

Για τον αναγνώστη μιας αξιολόγησης αυτό σημαίνει: ακόμη κι αν κάποια μέρα πέσουν όλες οι μέθοδοι πλεγμάτων, αυτή η υπογραφή παραμένει επαληθεύσιμη. Δεν χρειάζεται να μας πιστέψει. Μπορεί να το επαληθεύσει.