Board index   FAQ   Search  
Register  Login
Board index Επιστήμη & Τεχνολογία Ζητήματα Μαθηματικών - Φυσικής - Πληροφορικής

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

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

Moderators: kostas213, markelos

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

Postby sparc » Fri Mar 16, 2007 9:34 pm

drcypher wrote: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.
Last edited by sparc on Fri Mar 16, 2007 9:56 pm, edited 1 time in total.
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
Στενή είναι η αρετή, δεν μπορώ να αναπνεύσω· μικρός, στενός είναι ο Παράδεισος, δε με χωράει· σαν άνθρωπος μου φαίνεται ο Θεός σας, δεν τον θέλω!
Ν. Καζαντζάκης - Ασκητική
User avatar
sparc
 
Posts: 391
Joined: Wed Nov 01, 2006 10:46 am
Location: Ε204_κ.Φυσικής!!!
Real Name: Γιώργος
Gender: Male

Postby drcypher » Fri Mar 16, 2007 9:55 pm

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

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


sparc wrote:Να επισημάνω ότι σε κάθε κοινό 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.

-Από τη σκληρόδετη έκδοση του "Γιατί μπορώ" (Διαδόσεις "Φίλιος", 2009)
User avatar
drcypher
Portal Administrator
Portal Administrator
 
Posts: 2293
Joined: Wed Nov 01, 2006 8:33 am
Location: Μπροστά στην οθόνη
Real Name: Κωνσταντίνος Φίλιος
Gender: Male
Facebook ID: 1359164311

Postby sparc » Fri Mar 16, 2007 10:06 pm

Όσο σκέφτομαι την ιστορία με τα 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
Στενή είναι η αρετή, δεν μπορώ να αναπνεύσω· μικρός, στενός είναι ο Παράδεισος, δε με χωράει· σαν άνθρωπος μου φαίνεται ο Θεός σας, δεν τον θέλω!
Ν. Καζαντζάκης - Ασκητική
User avatar
sparc
 
Posts: 391
Joined: Wed Nov 01, 2006 10:46 am
Location: Ε204_κ.Φυσικής!!!
Real Name: Γιώργος
Gender: Male

Postby drcypher » Fri Mar 16, 2007 10:20 pm

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

Παρόλα αυτά το (1) που αναφέρεις (ότι δυσκολεύει τις επιθέσεις λεξικού) είναι αρκετό ως επιχείρημα, ακόμη κι αν τελικά το salt δεν προσθέτει (θεωρητικά) τίποτα στην "δύναμη" του ίδιου αλγορίθμου. Τουλάχιστον στο βαθμό που αποδυναμώνει τις τεχνικές επίθεσης με λεξικό, υπό την προϋπόθεση, πάντα, πως δεν είναι δυνατόν να γνωρίζεις τι salt θα προσέθετε το md5 στο string του λεξικού που δοκιμάζεις, καθώς σε αντίθετη περίπτωση το "αλάτισμα" θα αποτελούσε σκέτη σπατάλη χρόνου.
Από τούδε και στο εξής ως στρογγυλοί αριθμοί ορίζονται τα πολλαπλάσια του 5 και οι δυνάμεις του 2.

-Από τη σκληρόδετη έκδοση του "Γιατί μπορώ" (Διαδόσεις "Φίλιος", 2009)
User avatar
drcypher
Portal Administrator
Portal Administrator
 
Posts: 2293
Joined: Wed Nov 01, 2006 8:33 am
Location: Μπροστά στην οθόνη
Real Name: Κωνσταντίνος Φίλιος
Gender: Male
Facebook ID: 1359164311

Postby sparc » Fri Mar 16, 2007 10:21 pm

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

- Η αποκρυπτογράφηση δεν είναι κανένα μυστήριο άλλο από την αντίστροφη πορεία, η οποία ωστόσο είναι λιγάκι δύσκολή και χρονοβόρα (ένας συμβατικός υπολογιστής θέλει κάπου 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
Στενή είναι η αρετή, δεν μπορώ να αναπνεύσω· μικρός, στενός είναι ο Παράδεισος, δε με χωράει· σαν άνθρωπος μου φαίνεται ο Θεός σας, δεν τον θέλω!
Ν. Καζαντζάκης - Ασκητική
User avatar
sparc
 
Posts: 391
Joined: Wed Nov 01, 2006 10:46 am
Location: Ε204_κ.Φυσικής!!!
Real Name: Γιώργος
Gender: Male

Postby Remali tis Fokionos Negri » Sat Mar 17, 2007 10:11 am

Get a room...
Image
"Εάν ταίς γλώσσαις τών ανθρώπων λαλώ καί τών αγγέλων, αγάπη δέ μήν έχω, γέγονα χαλκός ηχών ή κύμβαλον αλαλάζον."
User avatar
Remali tis Fokionos Negri
 
Posts: 321
Joined: Thu Nov 02, 2006 12:23 am
Location: η εξωτική Κυψέλη
Real Name: KX
Gender: Male

Postby drcypher » Sat Mar 17, 2007 7:40 pm

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

Και εγώ που χάρηκα (όταν είδα απάντηση στο topic) ότι κάποιος προσέθεσε στοιχεία...
Από τούδε και στο εξής ως στρογγυλοί αριθμοί ορίζονται τα πολλαπλάσια του 5 και οι δυνάμεις του 2.

-Από τη σκληρόδετη έκδοση του "Γιατί μπορώ" (Διαδόσεις "Φίλιος", 2009)
User avatar
drcypher
Portal Administrator
Portal Administrator
 
Posts: 2293
Joined: Wed Nov 01, 2006 8:33 am
Location: Μπροστά στην οθόνη
Real Name: Κωνσταντίνος Φίλιος
Gender: Male
Facebook ID: 1359164311

Postby darth » Tue Mar 20, 2007 9:44 pm

ρε τι πίνετε?  :P
User avatar
darth
 
Posts: 243
Joined: Sat Dec 02, 2006 2:35 pm
Real Name: Dimitris


Return to Ζητήματα Μαθηματικών - Φυσικής - Πληροφορικής

Who is online

Users browsing this forum: No registered users and 1 guest