Έσπασε ο SHA-1!

[cryptogram]

[Από 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 κυκλοφορεί και όποιος ξέρει, βλέπει πως είναι καθαρά μονόδρομος. Για μένα το πόσο μεγάλη είναι η απειλή θα κριθεί από το πόσο γρήγορα και εύκολα βρίσκεται δεύτερη τιμή...

[Omen]

Πραγματικά με εντυπωσίασες με τα "γραπτόμενα" σου! Και είναι και αρκετά ενδιαφέρον αυτό που έγραψες...θα διαβάσω και τα λινκς που έβαλες για να μορφωθώ περισσότερο! Thnx!;)

[cryptogram]

Ευχαριστώ για τα καλά σου λόγια..

 

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

 

:)

[rohamis]

ΑΝ κάποιος θέλει ασφάλεια, ο τελευταίος τόπος που πρέπει να απευθυνθεί είναι το Internet. Το ταχυδρομικό περιστέρι είναι μακράν πιο ασφαλές μέσω για μετάδοση πληροφοριών. Αλήθεια ξέρεις κανένα άλλο open problem για πόσταρε?

[cryptogram]

ΑΝ κάποιος θέλει ασφάλεια, ο τελευταίος τόπος που πρέπει να απευθυνθεί είναι το Internet. Το ταχυδρομικό περιστέρι είναι μακράν πιο ασφαλές μέσω για μετάδοση πληροφοριών. Αλήθεια ξέρεις κανένα άλλο open problem για πόσταρε?

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

[cryptogram]

[Από 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]

[rohamis]

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

Open Problems, ή αλλιώς ανοιχτά προβλήματα είναι κάποια προβλήματα για τα οποία δεν ξέρουμε την λύση και συγκεκριμένα ούτε καν εάν υπάρχει λύση. Το πρόβλημα λύνεται εάν βρεθεί μια γενική λύση (προφανώς) ή εάν αποδειχθεί ότι δεν υπάρχει λύση. Για παράδειγμα το SHA-1 θέσαν ένα πρόβλημα υποστηρίζοντας ότι δεν σπάει διότι δεν υπάρχουν μνμτα με το ίδιο summary κλπ. Αποδείχθηκε ότι υπάρχουν. Ελπίζω να σε βοήθησα.

[cybersledge]

:X οοοοοοοπς! :O

[cryptogram]

Α, ο αθάνατος μαθηματικός!...

 

Στην “επιστήμη των υπολογιστών” δεν είναι ακριβώς έτσι τα πράγματα. Κυρίως στο θέμα της ασφάλειας, σχεδόν τίποτα δεν μπορεί να χαρακτηριστεί ως 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 ν ψηφίων.

[rohamis]

Καλά τα πας με την πολυπλοκότητα αλγορίθμων... BTW τα open problems είναι κατά κύριο λόγω "πληροφορικός" όρος. Όταν ένα πρόβλημα αποδειχθεί ότι έχει λύση ψάχνουμε μετά για το μέγιστο άνω φράγμα στην πολυπλοκότητα διάφορων αλγορίθμων που το επιλύουν. Εννοείται ότι ένα πρόβλημα σπασίματος ενός κωδικού έχει ως το μέγιστο άνω φράγμα την πολυπλοκότητα του brute force (πχ για κωδικό 8 char 2^8=256 διαφορετικοί κωδικοί, άρα και υπολογισμοί). Άλλοι αλγόριθμοι έχουν άλλες υπολογιστικές πολυπλοκότητες.

[cybersledge]

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

 

Εννοείται ότι ένα πρόβλημα σπασίματος ενός κωδικού έχει ως το μέγιστο άνω φράγμα την πολυπλοκότητα του brute force (πχ για κωδικό 8 char 2^8=256 διαφορετικοί κωδικοί, άρα και υπολογισμοί). Άλλοι αλγόριθμοι έχουν άλλες υπολογιστικές πολυπλοκότητες.

Αυτός είναι ο λόγος που έκανα τον διαχωρισμό ανάμεσα σε προβλήματα μαθηματικών και πληροφορικής: ότι στους αλγόριθμους(προβλήματα πληροφορικής) ουσιαστικά τα πάντα έχουν λύση, μιας και τα πάντα γίνονται brute force (δεν νομίζω πως υπάρχει αλγόριθμος για τον οποίο να μην είναι διαθέσιμος ο πηγαίος κώδικας ή τουλάχιστον να μην είναι γνωστή η εσωτερική του λειτουργία ώστε να γραφτεί κώδικας για brute forcing από τους επιτιθέμενους). Οπότε ξεκινάμε όπως λες από πολυπλοκότητα 2^(μήκος bit). Μετά μπαίνει το birthday paradox (παράδοξο των γενεθλίων) και το μειώνει σε 2^((μήκος bit/2)) και μετά.. βλέπουμε. Έναν τέτοιο αλγόριθμο τον θεωρείς ανοικτό πρόβλημα, μιας και μόνο "με τη βία" σπάει. Άμα μειωθεί σε 2^(μήκος bit/2)-1; Είναι αρκετό για να θεωρηθεί λυμένο πρόβλημα; Άμα μειωθεί σε 2^(μήκος bit/2000);

 

Μία μικρή υποσημείωση: πολυπλοκότητα 2^8=256 ισχύει για 8 bit ή για 8 χαρακτήρες επιλεγμένους από αλφάβητο 2 στοιχείων. Για 8 chars έχεις παραπάνω από 8 bit, πιθανότατα 64 bit ή 8 byte (εκτός εάν χαρακτήρες που καταλαμβάνουν πάνω από 1 byte όπως πχ. αλφαβήτου ανατολικής Ασίας), οπότε και υπολογίζουμε 2^64 συνδυασμούς. :geek:

 

edit: Έχω μπλέξει και την πολυπλοκότητα των usernames νομίζω. :X :confused: :O

[rohamis]

Εξ ορισμού τα προβλήματα "σπασίματος" ενός κωδικού είναι (θεωρητικά) λυμένα προβλήματα, μιας και το brute force κάνει πάντα δουλειά (έστω και αν εσύ δεν θα ζεις για να δεις το αποτέλεσμα). Κατά την γνώμη μου ένα πρόβλημα θεωρείται λυμένο όταν φτιαχτεί αλγόριθμος που θα μπορεί να εκτελέσει ο καθένας σε λίγα sec και να πάρει απάντηση. (Τελικά είναι άβυσσος η θεωρία πληροφορικής...)

 

Υποσημείωση : Τελικά έχουμε κωδικό με 8 χαρακτήρες (έστω ASCII που είναι 256) άρα έχουμε 256^8=(2^8)^8=2^64 . Άρα έχουμε και οι δύο δίκιο... ;)

[alfa 156]

θα έχει επιπτώσεις στα p2p?

[cybersledge]

Εάν η ερώτηση είναι το κατά πόσο θα γίνουν λιγότερο ασφαλή τα p2p, η απάντηση είναι μάλλον όχι, μιας και δεν είναι ασφαλή ήδη. :)

 

Εάν η ερώτηση είναι το κατα πόσο θα επιρρεάσει την "καταδίωξη" των p2p από εταιρίες τύπου RIAA, η απάντηση είναι πάλι όχι, δεν μπορώ να βρώ κάποια σύνδεση..

[shodanjr_gr]

Εξ ορισμού τα προβλήματα "σπασίματος" ενός κωδικού είναι (θεωρητικά) λυμένα προβλήματα, μιας και το brute force κάνει πάντα δουλειά (έστω και αν εσύ δεν θα ζεις για να δεις το αποτέλεσμα). Κατά την γνώμη μου ένα πρόβλημα θεωρείται λυμένο όταν φτιαχτεί αλγόριθμος που θα μπορεί να εκτελέσει ο καθένας σε λίγα sec και να πάρει απάντηση. (Τελικά είναι άβυσσος η θεωρία πληροφορικής...)

 

Υποσημείωση : Τελικά έχουμε κωδικό με 8 χαρακτήρες (έστω ASCII που είναι 256) άρα έχουμε 256^8=(2^8)^8=2^64 . Άρα έχουμε και οι δύο δίκιο... ;)

 

 

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

 

Γιατί πχ το brute forcing ενός κωδικού σίγουρα δεν λύνεται σε πολυωνιμικό χρόνο...σκεφτείτε απλά πόσες ώρες θέλει το μέσο σύγχρονο PC για να κάνει brute force ένα κλειδωμένο rar αρχείο...(τα εν λόγω προβλήματα έχουν αν δεν απατόμαι εκθετική πολυπλότητα η οποία είναι από τις ποιο "δυσχερείς").

 

Υπάρχει μεγάλη πιθανότητα να τα λέω στραβά, οπότε διορθώστε με.

[rohamis]

Δυστυχώς ούτε εμείς το είχαμε διαβάσει καλά αυτό το κεφάλαιο.... Παίζει να έχεις δίκιο.