cryptogram

Κρυπτόγραμμα: Μάιος 2005 Σε αυτό το τεύχος: -REAL ID: Η Πραγματική Ταυτότητα -Θα έπρεπε να αναφέρεται η τρομοκρατία στις Ειδήσεις; -Οι νέοι κίνδυνοι των αυτόματων ‘ταχυτητο-παγίδων’ -Ανατυπώσεις του Κρυπτογράμματος -Ανίχνευση πυρηνικού υλικού στις μεταφορές -Η προοπτική ενός σκουληκιού SSH -Νέα -Βιομετρικά διαβατήρια στο Ηνωμένο Βασίλειο -Απαγορεύονται οι αναπτήρες σε αεροπλάνα -Ναρκοπέδια ασύρματου δικτύου -Η Έκθεση PITAC για την κυβερνο-ασφάλεια -Κλοπή ταυτότητας επιδοτούμενη από το κράτος -Καταπολέμηση της ενοχλητικής αλληλογραφίας ©Copyright Cryptogram.gr 2004-2005 ΥΓ: Για λόγους φιλευσπλαχνίας, αυτή τη φορά δεν επισυνάπτουμε τις 26 σελίδες του τεύχους...

Α, ο αθάνατος μαθηματικός!... Στην “επιστήμη των υπολογιστών” δεν είναι ακριβώς έτσι τα πράγματα. Κυρίως στο θέμα της ασφάλειας, σχεδόν τίποτα δεν μπορεί να χαρακτηριστεί ως open problem ή solved problem γιατί πάντα υπάρχουν και άλλες παράμετροι μέσα. Για παράδειγμα τώρα που ‘έσπασε’ ο SHA-1, δεν σημαίνει ότι το πρωτόκολλο αυτό ακυρώνεται τελείως, απλά ότι υπάρχουν κάποιες αδυναμίες. Η παράμετρος που κάνει τη διαφορά εδώ είναι πόσο γρήγορα και εύκολα γίνεται η εκμετάλλευση αυτών των αδυναμιών, που καθορίζει το πόσο έχει αποτύχει ο αλγόριθμος ως μέσο ασφαλείας. Η ολική σύγκρουση στον SHA-1 γίνεται στους 2^69 υπολογισμούς. Αυτό είναι περίπου 590 πεντάκις-εκατομμύρια υπολογισμοί, ή 590,295,810,358,705,651,712 για να είμαστε ακριβείς. Έτσι το SHA-1 μπορούμε να πούμε ότι έσπασε με 2 τρόπους: Ο πρώτος είναι ο μαθηματικός, ο οποίος διαβεβαιώνει πως λόγω μίας αδυναμίας του SHA-1, μπορεί να βρεθεί σύγκρουση σε 2^69 συνδυασμούς, πολύ λιγότερο από το θεωρητικό 2^80**. Ο δεύτερος είναι ο πρακτικός, ο οποίος είναι ότι 2^69 συνδυασμοί είναι οριακά εφικτοί σε αυτή την εποχή. Στην ασφάλεια τα πάντα είναι συγκριτικά. Τα συγκρίσιμα μεγέθη είναι το μήκος του κλειδιού και τα υπολογιστικά συστήματα που υπάρχουν την παρούσα στιγμή στον κόσμο. Για τα σημερινά δεδομένα, ένα κλειδί PGP 4096 χαρακτήρων είναι πρακτικά άσπαστο. Σε δέκα χρόνια θα χρειαζόμαστε τουλάχιστον 16384 για να νιώθουμε ασφαλείς. Δεν θα σημαίνει ότι έχει γίνει πιο αδύναμο το PGP ως αλγόριθμος. Απλά θα είναι πιο πιθανή η εύρεση του κλειδιού ψάχνοντας τα κλειδιά ένα-ένα (brute forcing). Στον SHA-1. όπως και στους περισσότερους αλγόριθμους, μπορεί να εφαρμοστεί η τεχνική «second preimage*», η οποία μειώνει τους υπολογισμούς αρκετά, αλλά όχι αρκετά για να είναι εφικτό το σπάσιμό τους με τα σημερινά τεχνολογικά δεδομένα. (2^106 αντί για 2^160)** Σε αυτή την περίπτωση, θεωρείται σπασμένο ή όχι; Μαθηματικά ίσως, από άποψη ασφαλείας σίγουρα όχι. Κάτι που μπορεί να θεωρηθεί σπασμένο με τη μαθηματική έννοια και την πρακτική έννοια είναι το RC4 όπως χρησιμοποιήθηκε από την Microsoft στην κρυπτογράφηση των αρχείων Word και Excel όπως περιγράφεται το Κρυπτόγραμμα Φεβρουαρίου. Οι επιπτώσεις είναι καταστροφικές για την ασφάλεια αυτών των αρχείων καθώς δεν γίνεται μειωμένο brute-forcing αλλά αναστροφή του κρυπτογραφήματος. Οπότε για να απαντήσω στην ερώτησή σου, ‘ανοιχτό’ πρόβλημα υποθέτω πως είναι το PGP. Προσωπικά θεωρώ πως το pgp είναι ένα πρόγραμμα για παρανοϊκούς (ένας από αυτούς και εγώ πάντα) το οποίο υπερνικά τις πιθανότητες σπασίματος με ένα σχετικά καλό κώδικα που στηρίζεται από ένα τεράστιο κλειδί (από 1024 μέχρι 4096 bit). Το μειονέκτημα αυτής της παράνοιας είναι φυσικά ο χρόνος που χρειάζεται για να κρυπτογραφηθεί ένα μήνυμα με ένα κλειδί μήκους 4096 χαρακτήρων. Και ίσως για ένα μήνυμα μερικών γραμμών να μην τίθεται θέμα ταχύτητας αλλά για την κρυπτογράφηση μεγάλων αρχείων γίνεται αρκετά σημαντική. Βέβαια υπάρχουν και άλλα ανοιχτά προβλήματα που απλά δεν ασχολήθηκε κανείς να τα σπάσει:) ________________________ *Αρνούμαι να το μεταφράσω «δεύτερη προεικόνα» ή να εξηγήσω τι είναι σε αυτή την φάση… Θα μας πάρει λίγη ώρα. Ίσως κάποια άλλη φορά. **Αυτά τα παραδείγματα είναι αναλλοίωτες παραθέσεις από άρθρα. Η διαφορά είναι ότι στην πρώτη περίπτωση λαμβάνουμε υπόψη το ‘παράδοξο των γενεθλίων’(birthday paradox) ενώ στην δεύτερη όχι. Το παράδοξο των γενεθλίων λέει πολύ χοντρικά πως μπορούμε να κάνουμε 2^(ν/2) υπολογισμούς για να βρούμε το αντίστροφο ενός hash ν ψηφίων.

[Από Cryptogram.gr forums] Στα σχόλια που ακολουθούν την εγγραφή στο blog του Bruce Schneier, αναφέρθηκαν τα rainbow hash tables. Αυτό είναι απλά γελοίο και θα εξηγήσω γιατί.. Τα rainbow tables είναι ουσιαστικά ένα λεξικό τιμών-hash των τιμών. πχ: cryptogram : 11A6A7A89E1B1E6C220BDAA925ECC277BF6B6886 Crypto-Gram : 378FF32D2F3C6E38D55C538960E3AFABEED543D7 Cryptogram.gr : 86465AF2CD7E22780153A6195E1E1F8E45C37F99 Κρυπτόγραμμα : BEC5A23B30BEBB6D5476ED887485C586EF28FBFD τα οποία είναι ταξινομημένα κατα αύξουσα τιμή hash. Τώρα όποιος έχει το hash "86465AF2CD7E22780153A6195E1E1F8E45C37F99" και θέλει να βρεί τι είναι, ανατρέχει σε αυτούς τους πίνακες και βρίσκει την αρχική τιμή. Ο υπολογισμός rainbow tables δεν έχει να κάνει με το σπάσιμο του αλγόριθμου. Απλά δίνεις στο πρόγραμμα το αλφάβητο που θα χρησιμοποιήσει, το ελάχιστο μήκος τιμής, το μέγιστο μήκος τιμής(και άλλα αλλά δεν μας ενδιαφέρουν σε αυτή την φάση) και το πρόγραμμα υπολογίζει το hash όλων των τιμών που του δίνεις μία-μία. Πχ για νούμερα-μόνο, από μήκος 1 έως 5, θα υπόγιζε τα hashes των τιμών 1 μέχρι 99999. ___________________ Να χρησιμοποιηθούν rainbow tables για τον SHA-1 είναι ιδιαίτερα ηλίθιο και αναποτελεσματικό: Δοκιμάστε κάποιο πρόγραμμα παραγωγής rainbow tables το οποίο να δείχνει πόση μνήμη θα καταλαμβάνουν οι πίνακες. Δοκιμάστε αυτά τα στοιχεία: -------- Hash: SHA-1 Ελάχιστο μήκος - Min Length: 1 Μέγιστο μήκος - Max Length: 263 (ο μέγιστος αριθμός bit στην τιμή του SHA-1, σωστά;) Αλφάβητο(charset): ALL. Αριθμός 'αλυσίδας' (chain count): 50000000 (καθορίζει το μήκος του κάθε αρχείου) Αριθμός πινάκων (no of tables) : 9999999999 (καθορίζει τον αριθμό των αρχείων) --------Για να δείτε αυτό το αποτέλεσμα: Εύρος κλειδιών (Key Space): 1.#INF Απαιτούμενη μνήμη (Disk Space): 3.155.613.300.05 GB Πιθανότητα επιτυχίας: Success probability: -1.#IND-- (-1.#J%) Κοινώς, το πρόγραμμα δεν μπορεί να κάνει αρκετά μεγάλους υπολογισμούς για να βρεί το μέγεθος των πινάκων. Οπότε το ξεχνάμε να βρούμε όλο το φάσμα των εισαγώμενων τιμών (domain). Ας δούμε τι γίνεται με τις τιμές hash που μπορούν να βγούν από αυτόν τον αλγόριθμο: Δοκιμάστε αυτά τα στοιχεία: -------- Hash: SHA-1 Ελάχιστο μήκος (Min Length): 160 Μέγιστο μήκος (Max Length): 160 Αλφάβητο(charset): Δεκαεξαδικό(HEX). * Αριθμός 'αλυσίδας' (chain count): 50000000 (καθορίζει το μήκος του κάθε αρχείου) Αριθμός πινάκων (no of tables) : 9999999999 (καθορίζει τον αριθμό των αρχείων) --------Για να δείτε αυτό το αποτέλεσμα: Εύρος κλειδιών: 4.562*10^192 Απαιτούμενη μνήμη: 3.155.613.300.05 GB Πιθανότητα επιτυχίας: -1.#IND-- (-1.#J%) Η 'χρήση μνήμης' φαίνεται να κολλάει στα 3.155.... GB για υπερβολικά μεγάλες τιμές το οποίο υποδεικνύει ότι δεν είναι πραγματική (ναι, η πραγματική είναι περισσότερη) αλλά αυτό που είναι σημαντικό εδώ είναι το εύρος κλειδιού. Υπάρχουν 4.562*10^192 πιθανές τιμές. Ο αριθμός είναι ασύλλυπτος. Ενδεικτικά, ένα petabyte είναι 10^15 byte. Δείτε τι χωράει ένα petabyte.. _________________ *Δεν υπάρχει από προεπιλογή. Πρέπει να προσθέσετε αυτή την γραμμή στο "charset.txt":

open problem? δεν σε ακολουθώ..

Ευχαριστώ για τα καλά σου λόγια.. Πολύ σύντομα θα προσφέρουμε πολύ τέτοιο υλικό (ασφάλεια ηλεκτρονικών και μη μέσων) στον ιστοχώρο μας... :)

[Από cryptogram.gr forums] ________________________ Από το blog του Bruce Schneier, νέα εγγραφή πριν από 3 ώρες: ______ Ο SHA-1 έσπασε. Όχι κάποια μειωμένη ή απλοποιημένη έκδοση, ο πλήρης SHA-1. Η ομάδα των Xiaoyun Wang, Yiqun Lisa Yin και Hongbo Yu (κυρίως από το Πανεπιστήμιο Shandong της Κίνας) κυκλοφόρησαν σε περιορισμένο κύκλο μια εισήγηση ανακοινώνοντας τα ακόλουθα αποτελέσματα: -ολικές συγκρούσεις(collisions) στον πλήρη SHA-1 στους 2^69 υπολογισμούς (operations), πολύ λιγότερο από τους 2^80 υπολογισμούς που χρειάζονται για επίθεση brute-force σύμφωνα με το μήκος του κλειδιού (160 bit). -ολικές συγκρούσεις στον πλήρη SHA-0 στους 2^39 υπολογισμούς. -ολικές συγκρούσεις στον μειωμένο** SHA-1 58-επαναλήψεων (58-round) στους 2^33 υπολογισμούς. Η επίθεση ενισχύεται από προηγούμενες επιθέσεις στους SHA-0 και SHA-1 και είναι πολύ μεγάλο κρυπταναλυτικό αποτέλεσμα. Λίγο-πολύ θάβει τον SHA-1 ως αλγόριθμο hash για ψηφιακές υπογραφές, αν και δεν επιρρεάζει εφαρμογές όπως το HMAC όπου οι συγκρούσεις δεν είναι σημαντικές. Η εισήγηση δεν έχει κυκλοφορήσει επίσημα ακόμα. Σε αυτό το σημείο δεν μπορώ ακόμη να πω αν η επίθεση είναι αυθεντική, αλλά δείχνει καλή και η ομάδα έρευνας είναι αξιόπιστη*. Περισσότερες πληροφορίες όταν αποκτήσω κάτι νεότερο. ______ Θα προσπαθήσω να αναλύσω τι σημαίνει αυτό. Το πρότυπο του SHA-1 (Secure Hash Standard) παρουσιάστηκε το 1995 και βρίσκεται εδώ(στα αγγλικά). Δεύτερον, οι προηγούμενες επιθέσεις που αναφέρονται είναι αυτές και αυτές, οι οποίες όμως αφορούν τον αλγόριθμο SHA-0, τον οποίο η NIST απέσυρε όταν παρουσίασε τον SHA-1. Οι αδυναμίες αφορούν κάποιες μερικές και κάποιες ολικές συγκρούσεις. Συγκεκριμμένα, βρέθηκαν διαφορετικές τιμές για τις οποίες οι SHA-0 υπογραφές τους ήταν ίδιες σε 142 από τα 160 bit(μερική σύγκρουση). Αυτές αφορούσαν τον πλήρη αλγόριθμο SHA-0. Επίσης ανακοινώ8ηκαν πολλές ολικές συγκρούσεις (πανομοιότυπες υπογραφές) στον μειωμένο** SHA-0 65 επαναλήψεων(65 round). Η σημερινή ανακοίνωση περιλαμβάνει ολικές συγκρούσεις στον πλήρη SHA-1, στον μειωμένο SHA-1 58 επαναλήψεων και στον πλήρη SHA-0. Προσωπικά μου προκαλεί εντύπωση το μέγεθος της μικρότερης ολικής σύγκρουσης SHA-0 (2^39 ή 78 bit) σε σύγκριση με τα 160 bit του κλειδιού. Ελεύθερη μετάφραση από την παρουσίαση του SHA-1: ______ Ο SHA-1 χρησιμεύει στον υπολογισμό μιας αναπαράστασης ενός μηνύματος ή αρχείου. Όταν ένα μήνυμα μικρότερο των 264 bis δίνεται στον αλγόριθμο, ο SHA-1 παράγει μια ακολουθία χαρακτήρων μήκους 160 bit που ονομάζεται σύνοψη του μηνύματος (message digest). Αυτή η ακολουθία μπορεί να χρησιμοποιηθεί από τον Αλγόριθμο Ψηφιακής Υπογραφή (Digital Signature Algorith-DSA), ο οποίος παράγει ή επαληθεύει την υπογραφή του μηνύματος. [...] Ο SHA-1 αποκαλείται ασφαλής επειδή είναι υπολογιστικά αδύνατο να βρεθεί μήνυμα που να αντιστοιχεί σε δεδομένη σύνοψη (digest), ή να βρεθούν δύο διαφορετικά μηνύματα που να έχουν την ίδια σύνοψη. Με πολύ μεγάλη βεβαιότητα, κάθε αλλαγή στο μήνυμα θα αποτελέσει σε παραγωγή διαφορετικής σύνοψης, οπότε η υπογραφή δεν θα επιβεβαιωθεί.[...] Εφαρμογές: Αυτό το πρότυπο μπορεί να χρησιμοποιηθεί με Αλγόριθμο Ψηφιακής Υπογραφής(ΑΨΥ) σε ηλεκτρονική αλληλογραφία, ηλεκτρονική μεταφορά κεφαλαίων, διανομή λογισμικού, αποθήκευση δεδομένων και άλλες εφαρμογές όπου χρειάζεται βεβαιότητα για την εγκυρότητα των δεδομένων και πιστοποίηση την προέλευση του μηνύματος.[...] ______ Τι άλλαξε; Η προαναφερθείσα ομάδα βρήκε συγκρούσεις στον παραπάνω αλγόριθμο για κλειδιά μήκους 138 χαρακτήρων ή μικρότερα (εφ'όσον είναι 2^69 υπολογισμοί). Μια ολική σύγκρουση σε μια συνάρτηση hash είναι δύο διαφορετικές τιμές που αντιστοιχούν στην ίδια τιμή hash. Στην περίπτωση του SHA, αυτό μεταφράζεται σε δύο μηνύματα που έχουν την ίδια σύνοψη, άρα και υπογραφή. Ελπίζω να βλέπετε το πρόβλημα. Στην παρουσίαση του προτύπου του SHA-1 παρουσιάζεται ρητά πως αυτό είναι υπολογιστικά αδύνατο. Η ομάδα βρήκε ολικές συγκρούσεις στο SHΑ-1, πράγμα που υποδεικνύει ότι ο αλγόριθμος έχει αδυναμίες. Να υπογραμμιστεί πως η αδυναμία έχει να κάνει με διαφορετικές τιμές που έχουν την ίδια σύνοψη, όχι αντιστροφής του αλγορίθμου. Κάτι τέτοιο θα ήταν πολλαπλάσιας επικινδυνότητας, μιας και θα καθιστούσε τον αλγόριθμο άχρηστο ως συνάρτηση hash, μιας και το κύριο χαρακτηριστικό αυτών είναι το ότι είναι μονόδρομες. Κάτι τέτοιο θα είχε τρομακτικές επιπτώσεις σε κάθε είδους πληροφορίας που προστατεύενται από SHA-1. Οι περισσότεροι που θα διαβάσουν αυτές τις τελευταίες γραμμές θα πουν πως αναστροφή του SHA δεν γίνεται***. Μπορεί να έχουν δίκιο, αλλά χτες θα έλεγαν ότι δεν γίνεται να βρεθούν δύο τιμές που να έχουν το ίδιο SHA digest/σύνοψη. _______ Και γιατί μας αφορά; Στην Ελλάδα, ο SHA χρησιμοποιείται ως ότι καλύτερο στην ψηφιακή υπογραφή δεδομένων. Σε (δια-)τραπεζικά συστήματα, επικοινωνίες, υπουργεία, και πολλές άλλες κρίσιμες εφαρμογές. Μια από τις χρήσης του SHA-1 είναι ως "ασφαλής αλγόριθμος" ψηφιακής υπογραφής για την πιστοποίηση της αυθεντικότητας των φορολογικών στοιχείων(αποδείξεων,τιμολογίων,...) στις μηχανές ΕΑΦΔΣΣ ("Ειδικών Ασφαλών Φορολογικών Διατάξεων Σήμανσης Στοιχείων") του Υπουργείου Οικονομίας και Οικονομικών (δείτε εδώ τα σημεία 2.3.1-2.3.3,2.5.1,2.7.1,4.5.3,4.7.1,5.3,6.1.1 κ.α.). Καιρός για SHA-2; ©Copyright Cryptogram.gr 2005 ________ Στο παραπάνω άρθρο, ο συμβολισμός 2^Χ σημαίνει 2 υψωμένο στην δύναμη Χ. *Είναι η ίδια ομάδα που ανακάλυψε τις ολικές συγκρούσεις στην MD5.. ** Οι μειωμένοι αλγόριθμοι χρησιμοποιούνται κυρίως όταν οι πλήρεις είναι πολύ χρονοβόροι. ***Για να είμαι ρεαλιστής, ούτε εγώ πιστεύω πως τίθεται θέμα αντιστροφής του SHA. Ο πηγαίος κώδικας του SHA κυκλοφορεί και όποιος ξέρει, βλέπει πως είναι καθαρά μονόδρομος. Για μένα το πόσο μεγάλη είναι η απειλή θα κριθεί από το πόσο γρήγορα και εύκολα βρίσκεται δεύτερη τιμή...