MD5 αποκρυπτογράφηση

[Swinrrr]

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

 

Να στο δώσω με ένα απλό παράδειγμα. Έστω οτι έχουμε την συνάρτηση f(x)=5, η οποία όπως καταλαβαίνεις ανεξάρτητα από την είσοδο x που δίνουμε μας επιστρέφει πάντα 5. Αν εγώ τώρα σου δώσω αυτό το 5 εσύ μπορείς να πεις τι αριθμό έδωσα εγώ σαν είσοδο; Σαφώς και δεν μπορείς.

 

Κάπως έτσι δουλεύει και ο MD5, με σαφώς καλύτερη συνάρτηση για να μπορεί να πληρή κάποιες άλλες κρυπτογραφικές ιδιότητες που απαιτούνται γενικότερα στην κρυπτογραφία (τις οποίες δεν θα αναλύσω). Τώρα για τον ακριβή τρόπο με τον οποίο λειτουργεί ο MD5 κοίτα εδώ (γιατί δεν μπορώ αυτή την στιγμή να κάτσω να τα γράψω).

 

Για να κλείσω τελείως το θέμα, δεν γίνεται να βρεις το αρχικό μήνυμα σε hashing αλγορίθμους με κάποια συνάρτηση αναστροφής γιατί απλά δεν υπάρχει κάτι τέτοιο από μαθηματικής απόψεως. Trust me, το μεταπτυχιακό μου είναι στην ασφάλεια υπολογιστών και ασχολήθηκα και διάβασα πολλά papers για τον MD5.

 

 

ΔΕΝ είναι έτσι MD5 είναι f(x)=a. {x1->a1,x2->a2....} όπου για κάθε χ παράγεται μοναδικό α -μεταβλητή και α εξαρτάτε από διαδικασία . Ουσιαστικά χ1->σταθερα1 , ....

 

Εγώ έχω φτιάξει ένα md5 mp3 player, Δουλεύει με πολύ απλό τρόπο και σε ένα cd χωράνε 1.000.000.000 τραγούδια.

Κάνω κρυπτογράφηση mp3 σε md5 και πιάνει μόνο 16 bytes. Μετά ο player το αντιστρέφει και το παίζει. Καμιά φορά αν θέλω να χωρέσω πολλά τραγούδια κάνω με md5 όλο το φάκελο κατευθείαν. Το μόνο μειονέκτημα της 2ης μεθόδου είναι ότι δεν μπορώ να ακούσω όποιο θέλω αλλά πρέπει να τα ακούσω όλα με την σειρά.

 

Να και ο ένας στο πλανήτη που το κατάφερε , ας και δεν πρόκειται να το πει πως έκανε ... . !-)

 

//------------------------------------------------------------------

Βρε παίδες , έχει πoλλες εφαρμογές MD5 ! Ίσως θα χρειαστώ να ανοίξω ολόκληρο ξεχωριστό blog για το θέμα αυτό που ο καθένας θα εισάγει τις προτάσεις του για την αντιστροφή . Και βέβαιος εγώ Θα κάνω τα πρώτα βήματα στη σύνθεση της DEMD5() και ο κώδικας θα είναι open sourse .

Όλα θα γίνει αν θα έχω χρόνο βεβαια , και δεν θα βαρεθω , αλλά εξαρτάται και από τις προτάσεις σας.

[bnvdarklord]

1) Στον md5 νομίζω υπάρχουν κάποια conflicts (δηλαδή f(x) = f(y))

2) Το οτι μπορείς να πείς f(x) = a δεν σημαίνει οτι μπορείς να πείς g(a) = x.

 

Ο md5 δεν ειναι αλγόριθμος συμπίεσης, είναι αλγόριθμος κατακερματισμού(hash), δηλαδή στο αποτέλεσμα του δεν εχει αρκετή πληροφορία για να επιστρέψεις στο αρχικό κείμενο.

 

Σκέψου να σπάς βάζα και το md5 του καθε βάζου να ήταν ένα μικρό κομματάκι. Έχοντας μόνο το κομμάτάκι δεν μπορεις να πάρεις πίσω το βάζο, αλλα μπορεις να ξέρεις σε ποιο βάζο ανήκει αν σου δώσουν αντίγραφα των βάζων.

[Retromaniac]

MD5 αποκρυπτογράφηση:

http://en.wikipedia.org/wiki/Troll_(Internet)

[parsifal]

1) Στον md5 νομίζω υπάρχουν κάποια conflicts (δηλαδή f(x) = f(y))

 

Σωστά νομίζεις. Το σύνολο τιμών της συνάρτησης "MD5" είναι πεπερασμένο: 128-bit μήκος, άρα 2¹²⁸ διαφορετικές τιμές. Το πεδίο ορισμού της πάλι είναι ένα απειροσύνολο. Θεωρώντας ένα υποσύνολο Α αυτού με πληθικότητα έστω |Α| = 2¹²⁸ + 1, τότε από την αρχή του περιστερώνα προκύπτει ότι θα υπάρχουν αναγκαστικά τουλάχιστον 2 διαφορετικά x₁, x₂ ανήκοντα στο Α, με f(x₁) = f(x₂)...

[bnvdarklord]

Ναι το σκέφτηκα και γώ αφού πόσταρα το μήνυμα. Αυτό σημαίνει οτι θα έχουμε conflicts πάντα σε κάθε hash αλγόριθμο ομως σωστα; Αρά πάντα θα έχουμε προβλήματα.

[computeras13]

Ναι παντα εχεις collisions στους hashing αλγοριθμους. Το perfect hashing υπαρχει μονο σε θεωρητικο επιπεδο.

 

Οσον αφορα την συναρτηση του md5 που μου λετε οτι δεν ειναι σαν την f(x)=5, ναι το ξερω... Αυτο που ηθελα να δειξω ειναι οτι ειναι μονοδρομος αλγοριθμος και τι σημαινει αυτο με ενα απλο παραδειγμα.

 

Sent from my U8800 using Insomnia

[Retromaniac]

Ναι παντα εχεις collisions στους hashing αλγοριθμους. Το perfect hashing υπαρχει μονο σε θεωρητικο επιπεδο.

 

Οσον αφορα την συναρτηση του md5 που μου λετε οτι δεν ειναι σαν την f(x)=5, ναι το ξερω... Αυτο που ηθελα να δειξω ειναι οτι ειναι μονοδρομος αλγοριθμος και τι σημαινει αυτο με ενα απλο παραδειγμα.

 

Sent from my U8800 using Insomnia

Perfect Hashing δεν υπάρχει ούτε σε θεωρητικό.

[billdanos]

Παω να πάρω ντεπόν (των 1000mg)

 

[defacer]

Perfect hashing υπάρχει και έχει μια πολύ συγκεκριμένη έννοια. Δεν έχει καμία σχέση με md5 και άλλα general use hashes γιατί για να μιλάμε για perfect hashing πρέπει το σύνολο των πιθανών εισόδων της hash function να είναι πεπερασμένο και γνωστό εκ των προτέρων -- πράγμα που περιορίζει κατά πολύ τις εφαρμογές στις οποίες μπορούμε να το χρησιμοποιήσουμε, αλλά υπάρχουν.

[Retromaniac]

Defacer εννοούσα για οποιοδήποτε πλήθος data, σίγουρα κάνεις perfect hashing όταν έχεις ένα data set που καλύπτεται από το μέγεθος του hash key

"It has been proved that a general purpose minimal perfect hash scheme requires at least 1.44 bits/key"

[ipduh]

αυτή η συζήτηση έχει καταπληκτική ροή ...

 

ελπίζω να έχει πιστεί ο Swimrr ότι δεν αντιστρέφεται μαθηματικα. Εάν όχι, καρφί δεν μου καίγεται, και συνεχίζω

 

λοιπον γίνεται με brute force για μικρά strings ...

 

... πρεπει να υπολογίσουμε το πλήθος των MD5 ...

για να υπολογίσουμε big O, omegas , mem reqs , κτλ

 

αν υποθέσουμε οτι οι χαρακτήρες είναι το λατινικο αλφάβητο + Αριθμοι ~ 36 χαρακτήρες

για κάθε χαρακτήρα ν που προσθετουμε στο string το πλήθος μεγαλωνει 36 φορες

 

πχ για strings με 10 χαρακτήρες ,πχ κωδικοί, θα χρειαστει να υπολογισουμε και να ψάξουμε σε 36^10 hashes

 

το πρόβλημα είναι ότι οι χαρακτηρες μπορουν να είναι και μικροι ... οπότε μιλάμε μάλλον για 62^10

 

αν υποθέσουμε ότι οι κωδικοί μπορούν να περιέχουν και !@#$%^&*()_+ μιλάμε για 74^10

 

για να προλάβω τον Swimrr ...

 

όχι δεν τα βάζουμε όλα αυτα σε μια MySQL db ... μα πως ...

 

rainbow tables ... ...

 

νταμπ .. νταμπ .. χμ ..αχ ...

 

http://ophcrack.sourceforge.net/

Επεξ/σία 17 Οκτωβρίου 2012 από ipduh

[warlock9_0]

το salt που είχε γράψει ο defacer γιατί πέρασε έτσι?

απορώ πάντως που συνεχίζουν να έχουν απαντήσεις τα θέματα του swinrrrrrrrrrrr και πόσο μάλλον σοβαρές

[ipduh]

το salt που είχε γράψει ο defacer γιατί πέρασε έτσι?

απορώ πάντως που συνεχίζουν να έχουν απαντήσεις τα θέματα του swinrrrrrrrrrrr και πόσο μάλλον σοβαρές

 

βασικά νομίζω ότι έχουμε hijack το θέμα εδώ και καιρό, αλλά αν ο swinnnrrrr το διαβάζει θα μάθει πολλά,

αλλά και εμείς μαθαίνουμε έτσι,

 

καλή η αναφόρα στο salt --

 

εάν κάποιος αποκτήσει την βάση κάποιου με παράνομο τρόπο τότε ίσως μπορεί να βρει και το salt του νομιμου κατοχου

στον κώδικα του νόμιμου κατοχου ... ίσως και όχι ... αλλά υπάρχει και άλλος τρόπος,

 

ομως σε αλλα πραγματικά σενάρια το πλήθος των δοκιμών για ένα string 10 χαρακτήρων θα ήταν

74 ^10 * ( πληθος salt ) ~~~

αντε γεια αν θες να δοκιμάσεις όλα τα salt για 32 χαρακτήρες ~~~

θα ήταν κάτι σαν 74 ^10 * 62^32

 

καλά νέα Swimrrrrrrrrrrr , έαν έχεις στα χέρια σου μια μέγαλη σύλλογη απο hashes --κωδικούς -- με το ίδιο salt

τότε μάλλον μπορείς να βρείς το salt γιατι όλο και κάποιος `ανίκητος` απο τους χρήστες θα έχει κωδικό 0123456789 ή κάτι ανάλογο

οπότε μπορείς να κάνεις μια πιο έξυπνη και λιγότερο brute force επίθεση

[Haldol]

Perfect hashing υπάρχει και έχει μια πολύ συγκεκριμένη έννοια. Δεν έχει καμία σχέση με md5 και άλλα general use hashes γιατί για να μιλάμε για perfect hashing πρέπει το σύνολο των πιθανών εισόδων της hash function να είναι πεπερασμένο και γνωστό εκ των προτέρων -- πράγμα που περιορίζει κατά πολύ τις εφαρμογές στις οποίες μπορούμε να το χρησιμοποιήσουμε, αλλά υπάρχουν.

 

Άρα πρακτικά, μπορεί εύκολα να δημιουργηθεί collision-free hashing function για εφαρμογές τύπου password hashing (στις οποίες κάκιστα προτιμάται ο MD5, αλλά αυτό είναι άλλο θέμα).

[defacer]

Άρα πρακτικά, μπορεί εύκολα να δημιουργηθεί collision-free hashing function για εφαρμογές τύπου password hashing (στις οποίες κάκιστα προτιμάται ο MD5, αλλά αυτό είναι άλλο θέμα).

 

Εφόσον όλα τα πιθανά passwords δεν είναι ούτε γνωστά απο πριν ούτε καν πεπερασμένα σε αριθμό, δεν μπορεί να γίνει perfect hashing. Μήπως δεν κατάλαβα καλά τι εννοείς;