MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

Βρήκες ή ψάχνεις κάτι ενδιαφέρον για τους τομείς των Μαθηματικών, της Φυσικής ή της Πληροφορικής; Για πέρνα να τα πούμε...

Συντονιστές: kostas213, markelos, Tulis

Απάντηση
Άβαταρ μέλους
sparc
Δημοσιεύσεις: 391
Εγγραφή: Τετ Νοέμ 01, 2006 9:46 am
Real Name: Γιώργος
Gender: Male
Τοποθεσία: Ε204_κ.Φυσικής!!!

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

Δημοσίευση από sparc »

drcypher έγραψε:md5('') == d41d8cd98f00b204e9800998ecf8427e
Η υπογραφή του γιατρού με παραξένεψε και άρχισα να ψάχνω πριν καμιά ώρα τον εν λόγω αλγόριθμο. Ωστόσο αυτό που μου φάνηκε περίεργο δεν είναι το προφανές: τίποτα => 128bit αλλά το γιατί αυτό το γεγονός είναι περίεργο.
Κατέληξα στον τίτλο του εν λόγω post ο οποίος είναι quote από το επίσημο rfc του md5 και (για φαντάσου!) ταυτόσημος της υπογραφής.

Οι hash αλγόριθμοι έχουν έναν και μόνο έναν σκοπό, να καταστήσουν ένα αλφαριθμητικό μη ανακτήσιμο. O αλγόριθμος md5 συγκεκριμένα το επιτυγχάνει αυτό ακολουθώντας κάποιες αυστηρά καθορισμένες αρχές, με βασικότερη όλων το γεγονός ότι στην έξοδο επιστρέφει αλφαριθμητικό σταθερού μήκους 128bit οποιαδήποτε και αν είναι η είσοδος.
Ο αλγόριθμος md5 επιτυγχάνει τα μέγιστα όταν στην είσοδο δώσουμε αλφαριθμητικό μήκους Ν >128bit αφού τότε επιβεβαιώνουμε την πιθανότητα ύπαρξης collision, δλδ την ύπαρξη ενός άλλου αλφαριθμητικού για το οποίο ο αλγόριθμος παράγει την ίδια έξοδο, οπότε και οι πιθανότητες να ανακτηθεί το δικό μας αλφαριθμητικό μικραίνουν.

Υπεραπλουστευμένα, το αλφαριθμητικό εισόδου (A) δεν λειτουργεί ως πηγή αντιθέτως χρησιμοποιείται για να μεταβάλλει την προκαθορισμένη πηγή (S), ένα αρχικό αλφαριθμητικό μήκους 128bit. To S χωρίζεται σε 4 ίσα κομμάτια των 32bit το κάθε ένα από τα οποία μεταβάλλεται (shift) κατά διακριτό αριθμό bits ανάλογα με την τιμή του επόμενου χαρακτήρα του A. Οι μετασχηματισμοί είναι mod 64.

ΥΓ: 32 χαρακτήρες => 128bit ? Να επισημάνω ότι σε κάθε κοινό character set κάθε χαρακτήρας αντιστοιχεί σε 2bit μνήμης, ωστόσο όλοι οι αλγόριθμοι αλφαριθμητικών μετασχηματισμών χρησιμοποιούν το καθολικό Unicode-8 (utf-8 ) στο οποίο κάθε χαρακτήρας αντιστοιχεί σε 4bit.
Τελευταία επεξεργασία από το μέλος sparc την Παρ Μαρ 16, 2007 8:56 pm, έχει επεξεργασθεί 1 φορά συνολικά.
I think therefore I am? Could be! Or is it really someone else who thinks he's me?
Reymond Smullyan - This book needs no title
Στενή είναι η αρετή, δεν μπορώ να αναπνεύσω· μικρός, στενός είναι ο Παράδεισος, δε με χωράει· σαν άνθρωπος μου φαίνεται ο Θεός σας, δεν τον θέλω!
Ν. Καζαντζάκης - Ασκητική
Άβαταρ μέλους
drcypher
Portal Administrator
Portal Administrator
Δημοσιεύσεις: 2299
Εγγραφή: Τετ Νοέμ 01, 2006 7:33 am
Real Name: Κώτσος Φίλ
Gender: Male
Τοποθεσία: Μπροστά στην οθόνη

Δημοσίευση από drcypher »

Πολύ ενδιαφέρουσα παρατήρηση, και ταυτόχρονα σατανική σύμπτωση αν αναλογιστείς πως το έβαλα στην υπογραφή μου για να μην ανοίγω συνέχεια interactive php ώστε να το ξαναϋπολογίζω (χρειάζεται συχνά-πυκνά).

Με μπέρδεψες παρόλα αυτά με τις παρακάτω δυο εκφράσεις:
sparc έγραψε:Ο αλγόριθμος md5 επιτυγχάνει τα μέγιστα όταν στην είσοδο δώσουμε αλφαριθμητικό μήκους Ν >128bit αφού τότε επιβεβαιώνουμε την πιθανότητα ύπαρξης collision
sparc έγραψε:Να επισημάνω ότι σε κάθε κοινό character set κάθε χαρακτήρας αντιστοιχεί σε 2bit μνήμης, ωστόσο όλοι οι αλγόριθμοι αλφαριθμητικών μετασχηματισμών χρησιμοποιούν το καθολικό unicode-8 (utf-8 ) στο οποίο κάθε χαρακτήρας αντιστοιχεί σε 4bit.
Υποθέτω αναφέρεσαι σε "character sets" τα οποία αναπαριστούν δεκαεξαδικά "ψηφία" οπότε για τα σύμβολα 0-9,A-F, αρκούν 4 bits. Παρόλα αυτά ομολογώ με μπέρδεψες με τα δυο bits.

Θα αναπαράγω την κλασική προτροπή του αγαπητού el_greco: "Please, elaborate..."

Επιπλόν, αν βρήκες κάτι σχετικό (γιατί το έψαχνα τις προάλλες) θα ήθελα να μου πεις πόσο πιθανόν είναι δυο strings μικρού μήκους να οδηγούν στο ίδιο md5 output (128 bits). Επειδή δεν γνωρίζω την ορολογία (υποθέτω είναι τα "collisions"), αναφέρομαι σε κάτι αντίστοιχο της πιθανότητας επανάληψης ενός αριθμού π.χ. σε μια γεννήτρια ψευδοτυχαίων αριθμών.

Τέλος, μιας και την ανοίξαμε την κουβέντα, και υπό την προϋπόθεση ότι έχεις υπ' όψιν σου τί παίζει, θα εκτιμούσα μια αναφορά στην "ενίσχυση" του αλγορίθμου όταν πρόκειται για passwords, συμπεριλαμβάνοντας και την τεχνική προσθήκης "salt".
Από τούδε και στο εξής ως στρογγυλοί αριθμοί ορίζονται τα πολλαπλάσια του 5 και οι δυνάμεις του 2.
Άβαταρ μέλους
sparc
Δημοσιεύσεις: 391
Εγγραφή: Τετ Νοέμ 01, 2006 9:46 am
Real Name: Γιώργος
Gender: Male
Τοποθεσία: Ε204_κ.Φυσικής!!!

Δημοσίευση από sparc »

Όσο σκέφτομαι την ιστορία με τα bits μπερδεύομαι. Τεσπα θα με διαψεύσω αφού όσα είπα πριν είναι εσφαλμένα. Στο πρότυπο ASCII κάθε χαρακτήρας αναπαρίσταται από μία ακολουθία 8bit ενώ στο Unicode από 16bit!

'Οπως και να έχει η έξοδος είναι 32 χαρακτήρες. Αν δώσουμε είσοδο 60 χαρακτήρες τότε είναι πολύ πιθανό ένα άλλο αλφαριθμητικό (διαφορετικού μήκους πιθανότατα αλλά πάντα μεγαλύτερου του 32) να δώσει την ίδια έξοδο. Ωστόσο αν η είσοδος είναι μικρότερη του 32 οι πιθανότητες είναι αμελητέες με αποτέλεσμα η αποκρυπτογράφηση να έχει τις περισσότερες φορές μοναδικό αποτέλεσμα.
Αυτός είναι και ο λόγος που δε συνιστάται πλέον η χρήση των MD4-5 ή DES* αλγορίθμων για φύλαξη κωδικών που σπάνια ξεπερνάνε τους 10 χαρακτήρες...

Όσο για το salt, η χρήση του στην φύλαξη κωδικών έχει δύο πλεονεκτήματα (και μόνο αυτά):
 1 Δυσκολεύει τις επιθέσεις λεξικού
 2 Μεγαλώνει το αλφαριθμητικό σε μήκος άνω των 32 χαρακτήρων
I think therefore I am? Could be! Or is it really someone else who thinks he's me?
Reymond Smullyan - This book needs no title
Στενή είναι η αρετή, δεν μπορώ να αναπνεύσω· μικρός, στενός είναι ο Παράδεισος, δε με χωράει· σαν άνθρωπος μου φαίνεται ο Θεός σας, δεν τον θέλω!
Ν. Καζαντζάκης - Ασκητική
Άβαταρ μέλους
drcypher
Portal Administrator
Portal Administrator
Δημοσιεύσεις: 2299
Εγγραφή: Τετ Νοέμ 01, 2006 7:33 am
Real Name: Κώτσος Φίλ
Gender: Male
Τοποθεσία: Μπροστά στην οθόνη

Δημοσίευση από drcypher »

Βασικά το ερώτημα για το salt είναι πάνω-κάτω το εξής: Τι είδους δεδομένα προστίθενται στο αλφαριθμητικό προκειμένου να αυξηθεί το μήκος του σε άνω των 32 χαρακτήρων; Εννοώ, αν μπορείς να αναλύσεις ένα string σε κάτι μικρό (<32 chars) και σε "salt", δεν είναι εξίσου εύκολο να περάσεις στην πρώτη περίπτωση των μικρών αλφαριθμητικών; Προφανώς αγνοώ τον τρόπο με τον οποίο παράγονται τα salts και την σχέση τους με το αρχικό string (input).

Παρόλα αυτά το (1) που αναφέρεις (ότι δυσκολεύει τις επιθέσεις λεξικού) είναι αρκετό ως επιχείρημα, ακόμη κι αν τελικά το salt δεν προσθέτει (θεωρητικά) τίποτα στην "δύναμη" του ίδιου αλγορίθμου. Τουλάχιστον στο βαθμό που αποδυναμώνει τις τεχνικές επίθεσης με λεξικό, υπό την προϋπόθεση, πάντα, πως δεν είναι δυνατόν να γνωρίζεις τι salt θα προσέθετε το md5 στο string του λεξικού που δοκιμάζεις, καθώς σε αντίθετη περίπτωση το "αλάτισμα" θα αποτελούσε σκέτη σπατάλη χρόνου.
Από τούδε και στο εξής ως στρογγυλοί αριθμοί ορίζονται τα πολλαπλάσια του 5 και οι δυνάμεις του 2.
Άβαταρ μέλους
sparc
Δημοσιεύσεις: 391
Εγγραφή: Τετ Νοέμ 01, 2006 9:46 am
Real Name: Γιώργος
Gender: Male
Τοποθεσία: Ε204_κ.Φυσικής!!!

Δημοσίευση από sparc »

Και να προσθέσω ότι δεν υπάρχει καμία γεννήτρια πίσω από αυτούς τους αλγόριθμους... Τα βήματα των μετασχηματισμών καθώς και η αρχική τιμή είναι αυστηρά καθορισμένα. Αυτό συνεπάγεται δύο πράγματα:

- Η αποκρυπτογράφηση δεν είναι κανένα μυστήριο άλλο από την αντίστροφη πορεία, η οποία ωστόσο είναι λιγάκι δύσκολή και χρονοβόρα (ένας συμβατικός υπολογιστής θέλει κάπου 10 χρόνια για να σπάσει ένα hash 15 χαρακτήρων).
- Ωστόσο γίνεται και αν ΔΕΝ υπάρχουν collisions θα οδηγεί στο αρχικό μας αλφαριθμητικό, πάντα.
Σκέψου το σαν το τετράγωνο ενός αριθμού, που είναι απλός υπολογισμός, και την ρίζα, που δυσκολεύει λιγάκι αλλά είναι υπολογίσιμη, με την σύμβαση πως για αριθμούς άνω ενός ορίου δύο διαφορετικοί αριθμοί μπορούν να έχουν το ίδιο τετράγωνο.

Για το salt: Μπορεί να είναι οποιοδήποτε αλφαριθμητικό, θα μπορούσε να είναι το όνομά σου. Ο μόνος κανόνας είναι ότι δεν πρέπει να είναι σε καμία περίπτωση σχετικό με την είσοδό σου. Μην βάλεις δλδ το username ούτε ένα παράγωγο του password. Επίσης το salt μπορεί να (και συνήθως... )είναι μία hardcoded τυχαία τιμή 32 χαρακτήρων που δεν σημαίνει απολύτως τπτ. Όλα αυτά όμως μόνο για το md5.
Μηχανισμοί παραγωγής salt υπάρχουν για άλλους αλγόριθμους που υλοποιούν τεχνικές δημόσιων κλειδιών ώστε να πετύχουν δυνατότητα αποκρυπτογράφησης από τον παραλήπτη. Αλγόριθμοι τέτοιου είδους ουδεμία σχέση έχουν με αλγορίθμους hash γενικότερα.
Θα επαναλάβω ότι η οικογένεια στην οποία ανήκει ο md5 προσπαθεί να κάνει την είσοδο μη ανακτήσιμη με κάθε μέσο από οποιονδήποτε.
I think therefore I am? Could be! Or is it really someone else who thinks he's me?
Reymond Smullyan - This book needs no title
Στενή είναι η αρετή, δεν μπορώ να αναπνεύσω· μικρός, στενός είναι ο Παράδεισος, δε με χωράει· σαν άνθρωπος μου φαίνεται ο Θεός σας, δεν τον θέλω!
Ν. Καζαντζάκης - Ασκητική
Άβαταρ μέλους
Remali tis Fokionos Negri
Δημοσιεύσεις: 321
Εγγραφή: Τετ Νοέμ 01, 2006 11:23 pm
Real Name: KX
Gender: Male
Facebook ID: 0
Τοποθεσία: η εξωτική Κυψέλη
Επικοινωνία:

Δημοσίευση από Remali tis Fokionos Negri »

Get a room...
Εικόνα
"Εάν ταίς γλώσσαις τών ανθρώπων λαλώ καί τών αγγέλων, αγάπη δέ μήν έχω, γέγονα χαλκός ηχών ή κύμβαλον αλαλάζον."
Άβαταρ μέλους
drcypher
Portal Administrator
Portal Administrator
Δημοσιεύσεις: 2299
Εγγραφή: Τετ Νοέμ 01, 2006 7:33 am
Real Name: Κώτσος Φίλ
Gender: Male
Τοποθεσία: Μπροστά στην οθόνη

Δημοσίευση από drcypher »

Η κουβέντα δεν είναι προσωπική μεταξύ εμού και sparc ώστε να αναζητήσουμε "room", άσχετα με το αν μέχρι τώρα έχουμε συμμετάσχει μόνο οι 2 μας. Το "προσωπικό" καθορίζεται από το ενδεχόμενο ακροατήριο και το περιεχόμενο των εκφράσεων, όχι από τον αριθμό των συμμετεχόντων στην (πρώιμη) επεξεργασία του. Ο λόγος που παρατίθεται δημοσίως, λοιπόν, σχετίζεται με το ότι το θέμα είναι ενδιαφέρον από μόνο του, έχει δυνητικό ακροατήριο με πληθάριθμο μεγαλύτερο του 2, ακόμη κι αν κάποιος σκοπεύει να περιοριστεί στην ανάγνωση των δημοσιεύσεων. Ευκτέο είναι, δε, να συμμετάσχει οποιοσδήποτε επιθυμεί. Άλλωστε, οτιδήποτε δεν συνιστά "ενδιαφέρον θέμα" για κάποιον από εμάς, δεν οδηγεί υποχρεωτικά σε "προσωπική συζήτηση" που προορίζεται για chat room :P

Και εγώ που χάρηκα (όταν είδα απάντηση στο topic) ότι κάποιος προσέθεσε στοιχεία...
Από τούδε και στο εξής ως στρογγυλοί αριθμοί ορίζονται τα πολλαπλάσια του 5 και οι δυνάμεις του 2.
Άβαταρ μέλους
darth
Δημοσιεύσεις: 243
Εγγραφή: Σάβ Δεκ 02, 2006 1:35 pm
Real Name: Dimitris

Δημοσίευση από darth »

ρε τι πίνετε?  :P
Απάντηση

Επιστροφή στο “Ζητήματα Μαθηματικών - Φυσικής - Πληροφορικής”