Η (όχι και τόσο τυχαία) ιστορία μιας γεννήτριας τυχαίων αριθμών

Σχεδόν κάθε αλγόριθμος κρυπτογράφησης και σχεδόν κάθε πρωτόκολλο ασφαλείας περιλαμβάνει ένα απλό βήμα "επιλέγουμε έναν τυχαίο αριθμό". Αυτό το βήμα όσο απλό και αν ακούγεται έχει αποτελέσει την Αχίλλειο φτέρνα πολλών συστημάτων και ο λόγος είναι απλός: είναι πολύ δύσκολο να παράγουμε πραγματικά τυχαίους αριθμούς.

Το 2005 ο αμερικάνικος οργανισμός πιστοποίησης NIST  δημοσίευσε μια σειρά από αλγόριθμους δημιουργίας τυχαίων αριθμών. Ένας από αυτούς, ο αλγόριθμος με την ονομασία Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG), προξένησε πολλές εντυπώσεις. Ο αλγόριθμος αυτός βασίζεται στις ελλειπτικές καμπύλες και είχε δημιουργηθεί μερικά χρόνια πριν μετά από συνεργασία του NIST και της εθνικής υπηρεσίας ασφαλείας (NSA). Ο Dual_EC_DRBG είναι ιδιαίτερα αργός, η δημοσίευση του δεν συμπεριλάμβανε κάποια απόδειξη για την ασφάλεια του (δηλ. ότι οι αριθμοί που παράγει είναι πραγματικά τυχαίοι) και για την περιγραφή του είχαν χρησιμοποιηθεί κάποια "περίεργα" μαθηματικά.

To 2006 δυο ξεχωριστές εργασίες, η μία¹ από τον καθηγητή του τμήματος μαθηματικών του Νορβηγικού πανεπιστημίου NTΝU Kristian Gjøsteen και η άλλη² των καθηγητών του τμήματος μαθηματικών του Ολλανδικού TU Eindhoven Berry Schoenmakers και Andrey Sidorenko έδειξαν πως οι αριθμοί που παράγει ο Dual_EC_DRBG δεν είναι απολύτως τυχαίοι, για την ακρίβεια δεδομένου ενός αριθμού, κάποιος μπορεί να προβλέψει τον επόμενο με πιθανότητα 0,1%. Μπορεί η πιθανότητα αυτή να φαίνεται πολύ μικρή, δεν είναι όμως μια αποδεκτή τιμή: ακόμη και μια τόσο μικρή πιθανότητα μπορεί να οδηγήσει στην κατάρρευση ενός συστήματος ασφαλείας. Οι δύο αυτές εργασίες δημιούργησαν τις πρώτες υποψίες ότι κάτι δεν πάει καλά με τον Dual_EC_DRBG.

Το 2007 οι ερευνητές της Microsoft Dan Shumow και Niels Ferguso με μια ανεπίσημη παρουσίαση³ τους στο συνέδριο Crypto 2007 τάραξαν για τα καλά τα νερά. Αυτό που έδειξαν ήταν ότι ο Dual_EC_DRBG είχε πιθανώς μια καλά κρυμμένη πίσω πόρτα. Ο Dual_EC_DRBG βασίζεται σε κάποιες μεταβλητές με προκαθορισμένες τιμές. Οι τιμές που έχουν επιλεχθεί για αυτές τις μεταβλητές δεν έχουν (ακόμη και σήμερα) ποτέ δικαιολογηθεί. Οι 2 ερευνητές έδειξαν λοιπόν πως αυτές οι μεταβλητές μπορούν να συσχετισθούν με ένα μικρό σύνολο από μυστικούς αριθμούς (μυστικοί με την έννοια πως είναι υπολογιστικά ανέφικτο να βρεθούν). Αν κάποιος γνωρίζει αυτό το σύνολο των μυστικών αριθμών μπορεί παρατηρώντας ελάχιστα αποτελέσματα του Dual_EC_DRBG να υπολογίσει εύκολα όλα τα επόμενα αποτελέσματα. Το ερώτημα είναι ποιος θα μπορούσε να ξέρει αυτό το σύνολο των μυστικών αριθμών; Η απάντηση είναι αυτοί που επέλεξαν τις προεπιλεγμένες τιμές για τις μεταβλητές που χρησιμοποιεί ο Dual_EC_DRBG, δηλαδή η NSA!

Παρ' όλες αυτές τις ανακαλύψεις, ο Dual_EC_DRBG περιλαμβάνεται—μυστηριωδώς—στους αλγορίθμους που υποστηρίζει η πιο διαδεδομένη βιβλιοθήκη κρυπτογραφίας: το OpenSSL.

Πριν μερικές μέρες,όλες οι υποψίες επιβεβαιώθηκαν όταν το Reuteurs αποκάλυψε⁴ πως η NSA δωροδόκησε με $10 εκατομμύρια έναν κολοσσό στον χώρο της ασφάλειας, την εταιρεία RSA, για  να χρησιμοποιεί ως προεπιλογή τον αλγόριθμο Dual_EC_DRBG στο δημοφιλές προϊόν της BSAFE. Η αποκάλυψη αυτή έγινε λίγους μήνες πριν από ένα από τα μεγαλύτερα συνέδρια ασφαλείας που διοργανώνεται από την εν λόγω εταιρεία, το RSA Conference, οδηγώντας πολλούς να ακυρώσουν την συμμετοχή τους, ακόμη και τις παρουσιάσεις τους.

Παραπομπές

1. K. Gjøsteen, "Comments on Dual-EC-DRBG/NIST SP 800-90", 2005, [Online], τελευταία πρόσβαση 7 Ιαν. 2014
2. B. Schoenmakers, A. Sidorenko, Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator", 2006, [Online], τελευταία πρόσβαση 7 Ιαν. 2014
3. D. Shumow, Ν. Ferguson, "On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng", Crypto 2007, 2007, [Online], τελευταία πρόσβαση 7 Ιαν. 2014
4. J. Menn, "Exclusive: Secret contract tied NSA and security industry pioneer", Reuteurs, 20 Δεκ. 2013 [Online], τελευταία πρόσβαση 7 Ιαν. 2014