Εάν τα σημερινά πρωτόκολλα κρυπτογράφησης αποτύγχανε, θα ήταν αδύνατο να ασφαλιστούν οι διαδικτυακές συνδέσεις — να στείλετε εμπιστευτικά μηνύματα, να πραγματοποιήσετε ασφαλείς οικονομικές συναλλαγές ή να ελέγξετε την ταυτότητα των δεδομένων. Ο καθένας μπορούσε να έχει πρόσβαση σε οτιδήποτε. ο καθένας θα μπορούσε να προσποιηθεί ότι είναι οποιοσδήποτε. Η ψηφιακή οικονομία θα κατέρρεε.
Πότε (ή if) ένας πλήρως λειτουργικός κβαντικός υπολογιστής γίνεται διαθέσιμος, αυτό ακριβώς θα μπορούσε να συμβεί. Ως αποτέλεσμα, το 2017 το Εθνικό Ινστιτούτο Προτύπων και Τεχνολογίας (NIST) της κυβέρνησης των ΗΠΑ ξεκίνησε έναν διεθνή διαγωνισμό για να βρει τους καλύτερους τρόπους για την επίτευξη «μετα-κβαντικής» κρυπτογραφίας.
Τον περασμένο μήνα, ο οργανισμός επέλεξε την πρώτη του ομάδα νικητών: τέσσερα πρωτόκολλα που, με κάποια αναθεώρηση, θα αναπτυχθούν ως κβαντική ασπίδα. Ανακοίνωσε επίσης τέσσερις επιπλέον υποψηφίους που βρίσκονται ακόμη υπό εξέταση.
Στη συνέχεια, στις 30 Ιουλίου, ένα ζευγάρι ερευνητών αποκάλυψε ότι είχαν έσπασε ένας από αυτούς τους υποψηφίους σε μια ώρα σε φορητό υπολογιστή. (Από τότε, άλλοι έκαναν την επίθεση ακόμα πιο γρήγορη, παραβιάζοντας το πρωτόκολλο μέσα σε λίγα λεπτά.) «Μια επίθεση τόσο δραματική και ισχυρή… ήταν πολύ σοκ», είπε Στίβεν Γκάλμπρεϊθ, μαθηματικός και επιστήμονας υπολογιστών στο Πανεπιστήμιο του Όκλαντ στη Νέα Ζηλανδία. Όχι μόνο ήταν εκπληκτικά τα μαθηματικά στα οποία βασίζεται η επίθεση, αλλά μείωσαν την (πολύ απαραίτητη) ποικιλομορφία της μετακβαντικής κρυπτογραφίας - εξαλείφοντας ένα πρωτόκολλο κρυπτογράφησης που λειτουργούσε πολύ διαφορετικά από τη συντριπτική πλειονότητα των σχημάτων στον ανταγωνισμό NIST.
«Είναι λίγο τρομακτικό», είπε Κρίστοφερ Πάικερτ, κρυπτογράφος στο Πανεπιστήμιο του Μίσιγκαν.
Τα αποτελέσματα έχουν αφήσει την κοινότητα της μετα-κβαντικής κρυπτογραφίας συγκλονισμένη και ενθαρρυντική. Ταρακουνήθηκε, γιατί αυτή η επίθεση (και μια άλλη από έναν προηγούμενο γύρο του διαγωνισμού) μετέτρεψε ξαφνικά αυτό που έμοιαζε με ψηφιακή ατσάλινο πόρτα σε υγρή εφημερίδα. «Βγήκε από το μπλε», είπε Ντάστιν Μούντι, ένας από τους μαθηματικούς που ηγούνται της προσπάθειας τυποποίησης NIST. Αλλά αν ένα κρυπτογραφικό σχήμα πρόκειται να χαλάσει, είναι καλύτερο να συμβεί πολύ πριν χρησιμοποιηθεί στη φύση. «Υπάρχουν πολλά συναισθήματα που σε διαπερνούν», είπε Ντέιβιντ Τζάο, μαθηματικός στο Πανεπιστήμιο του Waterloo στον Καναδά που μαζί με τον ερευνητή της IBM Λούκα Ντε Φέο, πρότεινε το πρωτόκολλο το 2011. Σίγουρα η έκπληξη και η απογοήτευση είναι μεταξύ αυτών. «Αλλά επίσης», πρόσθεσε ο Τζάο, «τουλάχιστον χάλασε τώρα».
Μυστικές βόλτες ανάμεσα στις καμπύλες
Ο Jao και ο De Feo είχαν δει μια ευκαιρία για ένα κρυπτογραφικό σύστημα που ήταν και παρόμοιο και κατάλληλα διακριτό από τα γνωστά πρωτόκολλα. Το σχέδιό τους, που ονομάζεται πρωτόκολλο Diffie-Hellman supersingular isogeny (SIDH), ασχολήθηκε με τις ελλειπτικές καμπύλες - τα ίδια μαθηματικά αντικείμενα που χρησιμοποιούνται σε έναν από τους πιο διαδεδομένους τύπους κρυπτογραφίας που αναπτύσσονται σήμερα. Αλλά τα χρησιμοποίησε με εντελώς διαφορετικό τρόπο. Ήταν επίσης το πιο συμπαγές σχέδιο που εξέταζε το NIST (με τον συμβιβασμό ότι ήταν πιο αργός από πολλούς από τους άλλους υποψηφίους).
Και "από μαθηματικά, είναι πραγματικά κομψό", είπε ο Jao. «Εκείνη την εποχή, φαινόταν σαν μια όμορφη ιδέα».
Ας πούμε ότι δύο μέρη, η Αλίκη και ο Μπομπ, θέλουν να ανταλλάξουν ένα μήνυμα κρυφά, ακόμη και κάτω από το άγρυπνο βλέμμα ενός πιθανού επιτιθέμενου. Ξεκινούν με μια συλλογή σημείων που συνδέονται με ακμές που ονομάζεται γράφημα. Κάθε σημείο αντιπροσωπεύει μια διαφορετική ελλειπτική καμπύλη. Εάν μπορείτε να μετατρέψετε μια καμπύλη σε μια άλλη με συγκεκριμένο τρόπο (μέσω ενός χάρτη που ονομάζεται ισογενής), σχεδιάστε μια άκρη μεταξύ του ζεύγους σημείων. Το γράφημα που προκύπτει είναι τεράστιο και εύκολο να χαθεί κανείς μέσα του: Αν κάνετε μια σχετικά σύντομη βόλτα στις άκρες του, θα καταλήξετε κάπου που φαίνεται εντελώς τυχαίο.
Τα γραφήματα της Αλίκης και του Μπομπ έχουν όλα τα ίδια σημεία, αλλά οι ακμές είναι διαφορετικές — ορίζονται από διαφορετικές ισογονίες. Η Αλίκη και ο Μπομπ ξεκινούν από το ίδιο σημείο και ο καθένας πηδάει σε τυχαίες άκρες στο δικό του γράφημα, παρακολουθώντας την πορεία τους από το ένα σημείο στο άλλο. Στη συνέχεια, ο καθένας δημοσιεύει την τοποθεσία τερματισμού του, αλλά κρατά μυστική τη διαδρομή του.
Τώρα ανταλλάσσουν θέσεις: η Αλίκη πηγαίνει στο τελευταίο σημείο του Μπομπ και ο Μπομπ στο της Αλίκης. Ο καθένας επαναλαμβάνει τη μυστική του βόλτα. Αυτό το κάνουν με τέτοιο τρόπο που θα καταλήξουν και οι δύο στο ίδιο σημείο.
Αυτή η τοποθεσία βρέθηκε κρυφά, επομένως η Alice και ο Bob μπορούν να τη χρησιμοποιήσουν ως μυστικό κλειδί - πληροφορίες που τους επιτρέπουν να κρυπτογραφούν και να αποκρυπτογραφούν ο ένας τα μηνύματα του άλλου με ασφάλεια. Ακόμα κι αν ένας επιτιθέμενος δει τα ενδιάμεσα σημεία που στέλνουν ο ένας στον άλλον η Αλίκη και ο Μπομπ, δεν γνωρίζει το μυστικό περίπατο της Αλίκης ή του Μπομπ, επομένως δεν μπορεί να καταλάβει αυτό το τελικό τελικό σημείο.
Αλλά για να λειτουργήσει το SIDH, η Αλίκη και ο Μπομπ πρέπει επίσης να ανταλλάξουν κάποιες πρόσθετες πληροφορίες για τις βόλτες τους. Αυτές οι επιπλέον πληροφορίες είναι που οδήγησαν στην πτώση του SIDH.
Μια νέα ανατροπή στα παλιά μαθηματικά
Τόμας Ντεκρού δεν βάλθηκε να σπάσει το SIDH. Προσπαθούσε να βασιστεί σε αυτό - να γενικεύσει τη μέθοδο για να βελτιώσει έναν άλλο τύπο κρυπτογραφίας. Αυτό δεν λειτούργησε, αλλά πυροδότησε μια ιδέα: η προσέγγισή του μπορεί να είναι χρήσιμη για την επίθεση στο SIDH. Και έτσι πλησίασε Γουάτερ Κάστρικ, ο συνάδελφός του στο Καθολικό Πανεπιστήμιο του Leuven στο Βέλγιο και ένας από τους πρώην διδακτορικούς του συμβούλους, και οι δυο τους βούτηξαν στη σχετική βιβλιογραφία.
Έπεσαν πάνω σε ένα έγγραφο που δημοσίευσε ο μαθηματικός Ερνστ Κάνι το 1997. Σε αυτό υπήρχε ένα θεώρημα που «ήταν σχεδόν αμέσως εφαρμόσιμο στο SIDH», είπε ο Κάστρικ. «Νομίζω ότι μόλις καταλάβαμε ότι… η επίθεση ήρθε πολύ γρήγορα, σε μία ή δύο ημέρες».
Τελικά, για να ανακτήσουν τον μυστικό περίπατο της Αλίκης (και επομένως το κοινό κλειδί), ο Κάστρικ και ο Ντεκρού εξέτασαν το γινόμενο δύο ελλειπτικών καμπυλών - την αρχική καμπύλη της Αλίκης και την καμπύλη που έστειλε δημόσια στον Μπομπ. Αυτός ο συνδυασμός παράγει ένα είδος επιφάνειας που ονομάζεται αβελιανή επιφάνεια. Στη συνέχεια χρησιμοποίησαν αυτές τις αβελιανές επιφάνειες, το θεώρημα του Κάνι (το οποίο συσχετίζει τις αβελιανές επιφάνειες με τις ελλειπτικές καμπύλες) και τις επιπλέον πληροφορίες που έδωσε η Αλίκη στον Μπομπ για να αποκαλύψει κάθε βήμα που έκανε η Αλίκη.
"Είναι σχεδόν σαν ένα σήμα επιστροφής που σας επιτρέπει να κλειδώσετε σε [ορισμένες επιφάνειες αβελίας]", είπε ο Jao. «Και αυτό το σήμα σας λέει ότι αυτός είναι ο τρόπος που πρέπει να ακολουθήσετε για να κάνετε το επόμενο βήμα για να βρείτε τη σωστή [μυστική βόλτα]». Κάτι που τους οδήγησε κατευθείαν στο κοινό κλειδί της Αλίκης και του Μπομπ.
«Είναι μια πολύ απροσδόκητη προσέγγιση, η μετάβαση σε πιο περίπλοκα αντικείμενα για να εξαχθούν αποτελέσματα σχετικά με το απλούστερο αντικείμενο», είπε ο Jao.
«Ήμουν πολύ ενθουσιασμένος που είδα να χρησιμοποιείται αυτή η τεχνική», είπε Κριστίν Λάουτερ, μαθηματικός και κρυπτογράφος στο Meta AI Research που όχι μόνο βοήθησε στην ανάπτυξη κρυπτογραφίας με βάση την ισογονία, αλλά έχει επίσης εργαστεί σε επιφάνειες αβελιανών. «Οπότε ντροπή μου που δεν το σκέφτομαι ως τρόπο να το σπάσω».
Η επίθεση των Castryck και Decru έσπασε την έκδοση χαμηλότερης ασφάλειας του πρωτοκόλλου SIDH σε 62 λεπτά και το υψηλότερο επίπεδο ασφαλείας σε λιγότερο από μία ημέρα. Στη συνέχεια, λίγο αργότερα, ένας άλλος ειδικός τροποποίησε την επίθεση, έτσι ώστε να χρειαστούν μόλις 10 λεπτά για να σπάσει η έκδοση χαμηλής ασφάλειας και μερικές ώρες για να σπάσει την έκδοση υψηλής ασφάλειας. Γενικότερες επιθέσεις δημοσιεύτηκε τις τελευταίες εβδομάδες καθιστούν απίθανο το SIDH να μπορεί να διασωθεί.
«Ήταν ένα ιδιαίτερο συναίσθημα», είπε ο Κάστρικ, αν και γλυκόπικρο. «Σκοτώσαμε ένα από τα αγαπημένα μας συστήματα».
Μια στιγμή της λεκάνης απορροής
Είναι αδύνατο να εγγυηθεί κανείς ότι ένα σύστημα είναι άνευ όρων ασφαλές. Αντίθετα, οι κρυπτογράφοι βασίζονται σε αρκετό χρόνο που περνά και σε αρκετούς ανθρώπους που προσπαθούν να λύσουν το πρόβλημα για να αισθάνονται σίγουροι. "Αυτό δεν σημαίνει ότι δεν θα ξυπνήσετε αύριο και θα διαπιστώσετε ότι κάποιος έχει βρει έναν νέο αλγόριθμο για να το κάνει", είπε. Τζέφρι Χόφσταϊν, μαθηματικός στο Πανεπιστήμιο Μπράουν.
Ως εκ τούτου, διαγωνισμοί όπως του NIST είναι τόσο σημαντικοί. Στον προηγούμενο γύρο του διαγωνισμού NIST, ο Ward Beullens, κρυπτογράφος στην IBM, επινόησε μια επίθεση που έσπασε ένα σχέδιο που ονομάζεται Rainbow σε ένα Σαββατοκύριακο. Όπως ο Castryck και ο Decru, ήταν σε θέση να οργανώσει την επίθεσή του μόνο αφού είδε το υποκείμενο μαθηματικό πρόβλημα από μια διαφορετική οπτική γωνία. Και όπως η επίθεση στο SIDH, έτσι και αυτή έσπασε ένα σύστημα που βασιζόταν σε διαφορετικά μαθηματικά από τα περισσότερα προτεινόμενα μετα-κβαντικά πρωτόκολλα.
«Οι πρόσφατες επιθέσεις ήταν μια στιγμή ορόσημο», είπε Τόμας Περστ, κρυπτογράφος στην startup PQShield. Υπογραμμίζουν πόσο δύσκολη είναι η μετακβαντική κρυπτογραφία και πόση ανάλυση μπορεί να χρειαστεί για τη μελέτη της ασφάλειας διαφόρων συστημάτων. «Ένα μαθηματικό αντικείμενο μπορεί να μην έχει προφανή δομή σε μια προοπτική και να έχει μια εκμεταλλεύσιμη δομή σε μια άλλη», είπε. «Το δύσκολο είναι να προσδιορίσεις τη σωστή νέα προοπτική».
