Μετακβαντική κρυπτογραφία – νέος αλγόριθμος «έφυγε σε 60 λεπτά»

Έχουμε γράψει για το PQC, συντομογραφία μετα-κβαντική κρυπτογραφία, αρκετές φορές πριν.

Σε περίπτωση που έχετε χάσει όλο τον ενθουσιασμό των μέσων ενημέρωσης των τελευταίων ετών σχετικά με τον λεγόμενο κβαντικό υπολογισμό…

…είναι (αν συγχωρείτε αυτό που ορισμένοι ειδικοί θα θεωρήσουν πιθανώς μια απερίσκεπτη υπεραπλούστευση) ένας τρόπος κατασκευής υπολογιστικών συσκευών που μπορούν να παρακολουθούν πολλαπλά πιθανά αποτελέσματα ενός υπολογισμού ταυτόχρονα.

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

Δύο ενδιαφέρουσες κρυπταναλυτικές επιταχύνσεις είναι δυνατές χρησιμοποιώντας μια συσκευή κβαντικού υπολογισμού, με την προϋπόθεση ότι μπορεί να κατασκευαστεί μια κατάλληλα ισχυρή και αξιόπιστη συσκευή:

• Ο κβαντικός αλγόριθμος αναζήτησης του Grover. Συνήθως, αν θέλετε να αναζητήσετε ένα τυχαία σειρά απαντήσεων για να δείτε αν η δική σας είναι στη λίστα, θα περιμένατε να ξεπεράσετε ολόκληρη τη λίστα, στη χειρότερη περίπτωση, προτού λάβετε μια οριστική απάντηση. Για παράδειγμα, εάν θέλετε να βρείτε το κλειδί αποκρυπτογράφησης AES 128-bit για την αποκωδικοποίηση ενός εγγράφου, θα πρέπει να αναζητήσετε τη λίστα με όλα τα πιθανά κλειδιά, ξεκινώντας από το 000..001, ..2, ..3, και ούτω καθεξής, μέχρι το τέλος FFF..FFF (αξία 16 byte FF), για να είστε σίγουροι για την ολοκλήρωση του προβλήματος. Με άλλα λόγια, πρέπει να έχετε προϋπολογισμό για να δοκιμάσετε και τα 2¹²⁸ πιθανά κλειδιά είτε πριν βρείτε το σωστό κλειδί είτε προσδιορίσετε ότι δεν υπήρχε. Ο αλγόριθμος του Grover, ωστόσο, δεδομένου ενός μεγάλου και αρκετά ισχυρού κβαντικού υπολογιστή, ισχυρίζεται ότι μπορεί να ολοκληρώσει το ίδιο κατόρθωμα με το τετραγωνική ρίζα της συνηθισμένης προσπάθειας, σπάζοντας έτσι τον κώδικα, θεωρητικά, σε μόλις 2⁶⁴ προσπαθεί αντί.
• Κβαντικός αλγόριθμος παραγοντοποίησης Shor. Αρκετοί σύγχρονοι αλγόριθμοι κρυπτογράφησης βασίζονται στο γεγονός ότι ο πολλαπλασιασμός δύο μεγάλων πρώτων αριθμών μαζί μπορεί να γίνει γρήγορα, ενώ η διαίρεση του προϊόντος τους ξανά στους δύο αριθμούς με τους οποίους ξεκινήσατε είναι τόσο καλή όσο και αδύνατη. Για να πάρετε μια αίσθηση για αυτό, δοκιμάστε να πολλαπλασιάσετε 59×87 χρησιμοποιώντας στυλό και χαρτί. Μπορεί να χρειαστεί περίπου ένα λεπτό για να το βγάλετε (5133 είναι η απάντηση), αλλά δεν είναι τόσο δύσκολο. Τώρα δοκιμάστε τον άλλο τρόπο. Διαχωρίστε, ας πούμε, το 4171 στους δύο συντελεστές του. Πολύ πιο δύσκολο! (Είναι 43×97.) Τώρα φανταστείτε να το κάνετε αυτό με έναν αριθμό 600 ψηφίων. Χαλαρά μιλώντας, έχετε κολλήσει στην προσπάθεια να διαιρέσετε τον 600ψήφιο αριθμό με κάθε πιθανό 300ψήφιο πρώτο αριθμό μέχρι να πετύχετε το τζάκποτ ή να διαπιστώσετε ότι δεν υπάρχει απάντηση. Ο αλγόριθμος του Shor, ωστόσο, υπόσχεται να λύσει αυτό το πρόβλημα με το λογάριθμος της συνήθους προσπάθειας. Επομένως, η παραγοντοποίηση ενός αριθμού 2048 δυαδικών ψηφίων θα πρέπει να διαρκεί μόλις δύο φορές περισσότερο από την παραγοντοποίηση ενός αριθμού 1024 bit, όχι δύο φορές περισσότερο από την παραγοντοποίηση ενός αριθμού 2047 bit, που αντιπροσωπεύει μια τεράστια επιτάχυνση.

Αντιμετώπιση της απειλής

Η απειλή από τον αλγόριθμο του Grover μπορεί να αντιμετωπιστεί απλώς ενισχύοντας το μέγεθος των αριθμών που χρησιμοποιείτε τετραγωνίζοντάς τους, πράγμα που σημαίνει διπλασιασμό του αριθμού των bit στον κρυπτογραφικό κατακερματισμό ή στο συμμετρικό κλειδί κρυπτογράφησης. (Με άλλα λόγια, εάν πιστεύετε ότι το SHA-256 είναι εντάξει αυτή τη στιγμή, η χρήση του SHA-512 θα παρείχε μια εναλλακτική λύση ανθεκτική στο PQC.)

Αλλά ο αλγόριθμος του Shor δεν μπορεί να αντιμετωπιστεί τόσο εύκολα.

Ένα δημόσιο κλειδί 2048 bit θα χρειαζόταν το μέγεθός του να αυξηθεί εκθετικά, όχι απλά με τετραγωνισμό, έτσι ώστε αντί για ένα κλειδί 2×2048=4096 bit, είτε θα χρειαστείτε ένα νέο κλειδί με το αδύνατο μέγεθος των 2²⁰⁴⁸ κομμάτια…

…ή θα έπρεπε να υιοθετήσετε ένα εντελώς νέο είδος μετα-κβαντικού συστήματος κρυπτογράφησης στο οποίο δεν εφαρμόστηκε ο αλγόριθμος του Shor.

Λοιπόν, ο οργανισμός προτύπων των Η.Π.Α., το NIST εκτελούσε ένα PQC "ανταγωνισμός" από τα τέλη του 2017.

Η διαδικασία ήταν ανοιχτή σε όλους, με όλους τους συμμετέχοντες ευπρόσδεκτους, όλους τους αλγόριθμους ανοιχτά δημοσιευμένους και τον δημόσιο έλεγχο όχι απλώς δυνατό, αλλά ενθαρρύνεται ενεργά:

Κλήση για προτάσεις. [Κλειστό 2017-11-30]. […] Προβλέπεται ότι τα νέα πρότυπα κρυπτογραφίας δημόσιου κλειδιού θα καθορίσουν μία ή περισσότερες μη ταξινομημένες, δημοσίως αποκαλυπτόμενες ψηφιακές υπογραφές, κρυπτογράφηση δημόσιου κλειδιού και αλγόριθμους δημιουργίας κλειδιών που είναι διαθέσιμοι παγκοσμίως και είναι ικανοί να προστατεύουν ευαίσθητες κρατικές πληροφορίες στο άμεσο μέλλον, ακόμη και μετά την εμφάνιση των κβαντικών υπολογιστών.

Μετά από τρεις γύρους υποβολών και συζητήσεων, ανακοίνωσε το NIST, στις 2022-07-05, ότι είχε επιλέξει τέσσερις αλγόριθμους που θεώρησε «πρότυπα» με άμεση ισχύ, όλοι με απολαυστικά ονόματα: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, να SPHINCS+.

Η πρώτη (CRYSTALS-KYBER) χρησιμοποιείται ως αυτό που ονομάζεται α Μηχανισμός Βασικής Συμφωνίας (KEM), όπου δύο άκρα ενός δημόσιου καναλιού επικοινωνίας επινοούν με ασφάλεια ένα εφάπαξ ιδιωτικό κλειδί κρυπτογράφησης για την εμπιστευτική ανταλλαγή δεδομένων αξίας μιας περιόδου σύνδεσης. (Με απλά λόγια: οι snooper απλά παίρνουν λάχανο σε ψιλοκομμένο, ώστε να μην μπορούν να κρυφακούσουν τη συζήτηση.)

Οι άλλοι τρεις αλγόριθμοι χρησιμοποιούνται για Ψηφιακές υπογραφές, με το οποίο μπορείτε να διασφαλίσετε ότι τα δεδομένα που λάβατε στο τέλος ταιριάζουν ακριβώς με αυτά που έβαλε ο αποστολέας στον άλλο, αποτρέποντας έτσι την παραβίαση και διασφαλίζοντας την ακεραιότητα. (Με απλά λόγια: αν κάποιος προσπαθήσει να διαφθείρει ή να μπλέξει με τα δεδομένα, θα το μάθετε.)

Απαιτούνται περισσότεροι αλγόριθμοι

Ταυτόχρονα με την ανακοίνωση των νέων προτύπων, η NIST ανακοίνωσε επίσης α τέταρτος γύρος του ανταγωνισμού της, προωθώντας άλλους τέσσερις αλγόριθμους ως πιθανά εναλλακτικά KEM. (Θυμηθείτε ότι, τη στιγμή που γράφονται αυτές οι γραμμές, έχουμε ήδη τρεις εγκεκριμένους αλγόριθμους ψηφιακής υπογραφής για να διαλέξετε, αλλά μόνο ένα επίσημο KEM.)

Αυτοί ήταν: BIKE, Classic McEliece, HQC και SIKE.

Περιέργως, το Αλγόριθμος McEliece εφευρέθηκε πολύ πίσω στη δεκαετία του 1970 από τον Αμερικανό κρυπτογράφο Robert Mc Eliece, ο οποίος πέθανε το 2019, πολύ μετά την έναρξη του διαγωνισμού του NIST.

Δεν έπιασε ποτέ, ωστόσο, γιατί απαιτούσε τεράστιες ποσότητες βασικού υλικού σε σύγκριση με τη δημοφιλή εναλλακτική της εποχής, τον αλγόριθμο Diffie-Hellman-Merkle (DHM, ή μερικές φορές απλώς DH).

Δυστυχώς, ένας από τους τρεις αλγόριθμους του Γύρου Τέσσερα, δηλαδή SIKE, φαίνεται να έχει σπάσει.

Σε ένα εγκεφαλικό χαρτί με τίτλο ΜΙΑ ΑΠΟΤΕΛΕΣΜΑΤΙΚΗ ΕΠΙΘΕΣΗ ΑΝΑΚΤΗΣΗΣ ΚΛΕΙΔΙΟΥ ΣΤΟ SIDH (ΠΡΟΚΑΤΑΡΚΤΙΚΗ ΕΚΔΟΣΗ), οι Βέλγοι κρυπτογράφοι Wouter Castryk και Thomas Decru φαίνεται να έχουν καταφέρει κάτι σαν θανάσιμο πλήγμα στον αλγόριθμο SIKE

Σε περίπτωση που αναρωτιέστε, το SIKE είναι σύντομο Υπερsingular Isogeny Key Encapsulation, και το SIDH σημαίνει Υπερsingular Isogeny Diffie-Hellman, μια συγκεκριμένη χρήση του Αλγόριθμος SIKE όπου δύο άκρα ενός καναλιού επικοινωνίας εκτελούν μια «κρυπτογράφηση» παρόμοια με το DHM για την ανταλλαγή μιας δέσμης δημόσιων δεδομένων που επιτρέπει σε κάθε άκρο να εξάγει μια ιδιωτική τιμή προς χρήση ως μυστικό κλειδί κρυπτογράφησης μιας χρήσης.

Δεν θα προσπαθήσουμε να εξηγήσουμε την επίθεση εδώ. Απλώς θα επαναλάβουμε αυτό που ισχυρίζεται η εφημερίδα, δηλαδή ότι:

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

Αλλά η έξοδος που εξάγεται (οι πληροφορίες αναφέρονται ως η ισογενής φ παραπάνω) υποτίθεται ότι είναι το μέρος της διαδικασίας που δεν αποκαλύφθηκε ποτέ – το λεγόμενο ιδιωτικό κλειδί.

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

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

Προφανώς, ο αλγόριθμος σπασίματος κλειδιού χρειάζεται περίπου μία ώρα για να κάνει τη δουλειά του, χρησιμοποιώντας μόνο έναν πυρήνα CPU με το είδος της επεξεργαστικής ισχύος που θα βρείτε σε έναν καθημερινό φορητό υπολογιστή.

Αυτό έρχεται σε αντίθεση με τον αλγόριθμο SIKE όταν έχει ρυθμιστεί ώστε να πληροί το Επίπεδο 1, τον βασικό βαθμό ασφάλειας κρυπτογράφησης του NIST.

Τι να κάνω;

Τίποτα!

(Αυτά είναι τα καλά νέα.)

Όπως προτείνουν οι συντάκτες της εργασίας, αφού σημείωσαν ότι το αποτέλεσμά τους είναι ακόμα προκαταρκτικό, «Με την τρέχουσα κατάσταση πραγμάτων, το SIDH φαίνεται να έχει σπάσει πλήρως για οποιαδήποτε δημόσια καμπύλη βάσης».

(Αυτά είναι τα άσχημα νέα.)

Ωστόσο, δεδομένου ότι ο αλγόριθμος SIKE δεν έχει εγκριθεί ακόμη επίσημα, μπορεί τώρα είτε να προσαρμοστεί για να αποτρέψει τη συγκεκριμένη επίθεση (κάτι που οι συγγραφείς παραδέχονται ότι είναι πιθανό), είτε απλώς να απορριφθεί εντελώς.

Ό,τι κι αν συμβεί τελικά στο SIKE, αυτό είναι μια εξαιρετική υπενθύμιση του γιατί η προσπάθεια να εφεύρετε τους δικούς σας αλγόριθμους κρυπτογράφησης είναι γεμάτη κινδύνους.

Είναι επίσης ένα χαρακτηριστικό παράδειγμα του γιατί τα ιδιόκτητα συστήματα κρυπτογράφησης που βασίζονται στη μυστικότητα του ίδιου του αλγορίθμου να διατηρήσουν την ασφάλειά τους είναι απλώς απαράδεκτα το 2022.

Εάν ένας αλγόριθμος PQC, όπως ο SIKE, επέζησε από εμπειρογνώμονες από όλο τον κόσμο για περισσότερα από πέντε χρόνια, παρά το γεγονός ότι είχε αποκαλυφθεί ειδικά ώστε να μπορεί να υποβληθεί σε δημόσιο έλεγχο…

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

---