cryptogram Δημοσ. 16 Φεβρουαρίου 2005 Δημοσ. 16 Φεβρουαρίου 2005 Από 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 κυκλοφορεί και όποιος ξέρει, βλέπει πως είναι καθαρά μονόδρομος. Για μένα το πόσο μεγάλη είναι η απειλή θα κριθεί από το πόσο γρήγορα και εύκολα βρίσκεται δεύτερη τιμή...
cryptogram Δημοσ. 16 Φεβρουαρίου 2005 Μέλος Δημοσ. 16 Φεβρουαρίου 2005 [Από 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": hex = [0123456789ABCDEF]
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.