Swinrrr Δημοσ. 16 Οκτωβρίου 2012 Μέλος Δημοσ. 16 Οκτωβρίου 2012 Αντιστροφή του 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 Δημοσ. 16 Οκτωβρίου 2012 Δημοσ. 16 Οκτωβρίου 2012 1) Στον md5 νομίζω υπάρχουν κάποια conflicts (δηλαδή f(x) = f(y)) 2) Το οτι μπορείς να πείς f(x) = a δεν σημαίνει οτι μπορείς να πείς g(a) = x. Ο md5 δεν ειναι αλγόριθμος συμπίεσης, είναι αλγόριθμος κατακερματισμού(hash), δηλαδή στο αποτέλεσμα του δεν εχει αρκετή πληροφορία για να επιστρέψεις στο αρχικό κείμενο. Σκέψου να σπάς βάζα και το md5 του καθε βάζου να ήταν ένα μικρό κομματάκι. Έχοντας μόνο το κομμάτάκι δεν μπορεις να πάρεις πίσω το βάζο, αλλα μπορεις να ξέρεις σε ποιο βάζο ανήκει αν σου δώσουν αντίγραφα των βάζων. 1
Retromaniac Δημοσ. 16 Οκτωβρίου 2012 Δημοσ. 16 Οκτωβρίου 2012 MD5 αποκρυπτογράφηση: http://en.wikipedia.org/wiki/Troll_(Internet)
parsifal Δημοσ. 16 Οκτωβρίου 2012 Δημοσ. 16 Οκτωβρίου 2012 1) Στον md5 νομίζω υπάρχουν κάποια conflicts (δηλαδή f(x) = f(y)) Σωστά νομίζεις. Το σύνολο τιμών της συνάρτησης "MD5" είναι πεπερασμένο: 128-bit μήκος, άρα 2128 διαφορετικές τιμές. Το πεδίο ορισμού της πάλι είναι ένα απειροσύνολο. Θεωρώντας ένα υποσύνολο Α αυτού με πληθικότητα έστω |Α| = 2128 + 1, τότε από την αρχή του περιστερώνα προκύπτει ότι θα υπάρχουν αναγκαστικά τουλάχιστον 2 διαφορετικά x1, x2 ανήκοντα στο Α, με f(x1) = f(x2)...
bnvdarklord Δημοσ. 16 Οκτωβρίου 2012 Δημοσ. 16 Οκτωβρίου 2012 Ναι το σκέφτηκα και γώ αφού πόσταρα το μήνυμα. Αυτό σημαίνει οτι θα έχουμε conflicts πάντα σε κάθε hash αλγόριθμο ομως σωστα; Αρά πάντα θα έχουμε προβλήματα.
computeras13 Δημοσ. 16 Οκτωβρίου 2012 Δημοσ. 16 Οκτωβρίου 2012 Ναι παντα εχεις collisions στους hashing αλγοριθμους. Το perfect hashing υπαρχει μονο σε θεωρητικο επιπεδο. Οσον αφορα την συναρτηση του md5 που μου λετε οτι δεν ειναι σαν την f(x)=5, ναι το ξερω... Αυτο που ηθελα να δειξω ειναι οτι ειναι μονοδρομος αλγοριθμος και τι σημαινει αυτο με ενα απλο παραδειγμα. Sent from my U8800 using Insomnia
Retromaniac Δημοσ. 17 Οκτωβρίου 2012 Δημοσ. 17 Οκτωβρίου 2012 Ναι παντα εχεις collisions στους hashing αλγοριθμους. Το perfect hashing υπαρχει μονο σε θεωρητικο επιπεδο. Οσον αφορα την συναρτηση του md5 που μου λετε οτι δεν ειναι σαν την f(x)=5, ναι το ξερω... Αυτο που ηθελα να δειξω ειναι οτι ειναι μονοδρομος αλγοριθμος και τι σημαινει αυτο με ενα απλο παραδειγμα. Sent from my U8800 using Insomnia Perfect Hashing δεν υπάρχει ούτε σε θεωρητικό.
Super Moderators billdanos Δημοσ. 17 Οκτωβρίου 2012 Super Moderators Δημοσ. 17 Οκτωβρίου 2012 Παω να πάρω ντεπόν (των 1000mg)
defacer Δημοσ. 17 Οκτωβρίου 2012 Δημοσ. 17 Οκτωβρίου 2012 Perfect hashing υπάρχει και έχει μια πολύ συγκεκριμένη έννοια. Δεν έχει καμία σχέση με md5 και άλλα general use hashes γιατί για να μιλάμε για perfect hashing πρέπει το σύνολο των πιθανών εισόδων της hash function να είναι πεπερασμένο και γνωστό εκ των προτέρων -- πράγμα που περιορίζει κατά πολύ τις εφαρμογές στις οποίες μπορούμε να το χρησιμοποιήσουμε, αλλά υπάρχουν.
Retromaniac Δημοσ. 17 Οκτωβρίου 2012 Δημοσ. 17 Οκτωβρίου 2012 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 Δημοσ. 17 Οκτωβρίου 2012 Δημοσ. 17 Οκτωβρίου 2012 (επεξεργασμένο) αυτή η συζήτηση έχει καταπληκτική ροή ... ελπίζω να έχει πιστεί ο 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 Δημοσ. 17 Οκτωβρίου 2012 Δημοσ. 17 Οκτωβρίου 2012 το salt που είχε γράψει ο defacer γιατί πέρασε έτσι? απορώ πάντως που συνεχίζουν να έχουν απαντήσεις τα θέματα του swinrrrrrrrrrrr και πόσο μάλλον σοβαρές
ipduh Δημοσ. 17 Οκτωβρίου 2012 Δημοσ. 17 Οκτωβρίου 2012 το 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 Δημοσ. 17 Οκτωβρίου 2012 Δημοσ. 17 Οκτωβρίου 2012 Perfect hashing υπάρχει και έχει μια πολύ συγκεκριμένη έννοια. Δεν έχει καμία σχέση με md5 και άλλα general use hashes γιατί για να μιλάμε για perfect hashing πρέπει το σύνολο των πιθανών εισόδων της hash function να είναι πεπερασμένο και γνωστό εκ των προτέρων -- πράγμα που περιορίζει κατά πολύ τις εφαρμογές στις οποίες μπορούμε να το χρησιμοποιήσουμε, αλλά υπάρχουν. Άρα πρακτικά, μπορεί εύκολα να δημιουργηθεί collision-free hashing function για εφαρμογές τύπου password hashing (στις οποίες κάκιστα προτιμάται ο MD5, αλλά αυτό είναι άλλο θέμα).
defacer Δημοσ. 17 Οκτωβρίου 2012 Δημοσ. 17 Οκτωβρίου 2012 Άρα πρακτικά, μπορεί εύκολα να δημιουργηθεί collision-free hashing function για εφαρμογές τύπου password hashing (στις οποίες κάκιστα προτιμάται ο MD5, αλλά αυτό είναι άλλο θέμα). Εφόσον όλα τα πιθανά passwords δεν είναι ούτε γνωστά απο πριν ούτε καν πεπερασμένα σε αριθμό, δεν μπορεί να γίνει perfect hashing. Μήπως δεν κατάλαβα καλά τι εννοείς;
Προτεινόμενες αναρτήσεις