nicht angemeldet
Gibt es einen Hash-Algo, der einen 13 Stelligen Code erzeugt?
suitHi,
Gibt es einen Hash-Algo, der einen 13 stelligen Code erzeugt bestehend aus den Buchstaben abcdef und den Zahlen 0123456789 ?
lg
mike
-
Hi,
Gibt es einen Hash-Algo, der einen 13 stelligen Code erzeugt bestehend aus den Buchstaben abcdef und den Zahlen 0123456789 ?
lg
mikeKlaro:
substr( md5( $variable ) ,0 ,13);Das wäre jetzt PHP Syntax. Muss die Programmiersprache leider raten.
Gruß
ratender
T-Rex-
Danke für die schnelle Hilfe.
lg
mike -
substr( md5( $variable ) ,0 ,13);
Äh nein - das ist kein Hash mit 13 Stellen sondern ein vrstümmelter Hash der eine Signifikant höhere Kollisionswahrscheinlichkeit hat als ein (theoretisch) baugleicher Hashalgorithmus, der tatsächlich 13 Stellen liefert.
vgl. "Geburtstagsproblem."
Bei einem echten (perfekten) Hash-Algorithmus mit 13 Stellen und 16 Zeichen Vorrat würde eine Kollision nach spätestens ~4.5*10^15 Klartexten auftreten - wenn du aber die Entropie eines Streuwerts verringest, indem du einfach vom Fetigen Hash ein paar Stellen abschneidest, tritt so eine Kollision potentiell früher auf.
-
Das war die wissenschaftlich korrekte Erklärung!!
Und doch taugt ihm angeblich meine Lösung.Bin aber sehr gespannt auf deinen Lösungsvorschlag.
Gruß
gespannter
T-Rex-
Und doch taugt ihm angeblich meine Lösung.
Kommt drauf an, was er damit macht - spätestens, wenn in 3 Monaten irgendwas nicht richtig funktioniert, wird er dich verfluchen :p
Bin aber sehr gespannt auf deinen Lösungsvorschlag.
Ich bin sehr gespannt auf den Sinn hinter der Frage des OP - wozu ist der "13-stellige Code" da?
Ich hätte ja bei 13 Stellen auf uniqid() mit default-Werten getippt :p
-
Kommt drauf an, was er damit macht - spätestens, wenn in 3 Monaten irgendwas nicht richtig funktioniert, wird er dich verfluchen :p
Da hab ich mich längst in ein anderes Land abgesetzt. Generell hast du recht, ich kontere jedoch in dem ich sage, dann muss er sein Problem näher beschreiben.
Ich hätte ja bei 13 Stellen auf uniqid() mit default-Werten getippt :p
uniqid ... und schon wieder was gelernt. Gut das ich nachgefragt hab. Danke!
Gruß
Unique
T-Rex-
Kommt drauf an, was er damit macht - spätestens, wenn in 3 Monaten irgendwas nicht richtig funktioniert, wird er dich verfluchen :p
Da hab ich mich längst in ein anderes Land abgesetzt. Generell hast du recht, ich kontere jedoch in dem ich sage, dann muss er sein Problem näher beschreiben.
Ich hätte ja bei 13 Stellen auf uniqid() mit default-Werten getippt :p
uniqid ... und schon wieder was gelernt. Gut das ich nachgefragt hab.
Und nein, das ist kein Hash oder sonstwas sondern einfach nur eine Hexadezimale Darstellung der aktuellen Serverzeit in Microsekunden. Und nein, sie ist nicht eindeutig.
-
-
-
-
Moin!
substr( md5( $variable ) ,0 ,13);
Äh nein - das ist kein Hash mit 13 Stellen sondern ein vrstümmelter Hash der eine Signifikant höhere Kollisionswahrscheinlichkeit hat als ein (theoretisch) baugleicher Hashalgorithmus, der tatsächlich 13 Stellen liefert.
Das kannst du doch sicher mathematisch beweisen, oder?
vgl. "Geburtstagsproblem."
Ich glaube nicht, dass das Geburtstagsproblem hier maßgeblich ist.
Bei einem echten (perfekten) Hash-Algorithmus mit 13 Stellen und 16 Zeichen Vorrat würde eine Kollision nach spätestens ~4.5*10^15 Klartexten auftreten - wenn du aber die Entropie eines Streuwerts verringest, indem du einfach vom Fetigen Hash ein paar Stellen abschneidest, tritt so eine Kollision potentiell früher auf.
Das heißt, du hast Erkenntnisse über die Streuung von MD5-Ergebnissen?
- Sven Rautenberg
-
Moin!
Das kannst du doch sicher mathematisch beweisen, oder?
Das kann man sogar in einer Art begreifen, die für Kinder eingängig ist:
Mit einer nicht negativen zweistelligen Zahl des Dezimalsystems lassen sich kollisionsfrei (also eineindeutig) 100 verschiedene Items durchnummerieren. Mit einer 3-stelligen Zahl 1000, mit einer vierstelligen sogar 10.000. Also steigt die Zahl der kollisionsfreien Zuordnungen im Verhältnis zur Stellenzahl exponentiell an.
Hat man jetzt kein Dezimalsystem, sondern ein System mit einem größeren Ziffenvorrat, also 0 bis 1 und a-z (was md5 macht), dann ist das so, dass man mit einer einstelligen Zahl dieses Systems 36, mit einer zweistelligen 36 * 36 = 1.296, mit einer dreistelligen 36^3=46.656 mit einer dreizehnstelligen 170.581.728.179.578.208.256 mit einer 32-stelligen sogar 63.340.286.662.973.277.706.162.286.946.811.886.609.896.461.828.096 Items eineindeutig zuordnen.
Da ein Hashverfahren nichts anderes ist, als eine Zahl zu berechnen, welche den übergebenen Text repräsentiert und da es unendlich viele Texte gibt, kommt man also zu dem Schluss, dass wenn man mit einem 32-stelligen Hash spätestens(!) dem 63.340.286.662.973.277.706.162.286.946.811.886.609.896.461.828.097en Text eine bereits vergebene Nummer geben muss.
Bei 13 Stellen aber spätestens(!) schon dem 170.581.728.179.578.208.257en Text.
Die Wahrscheinlichkeit einer Kollision, also dass zwei unterschiedliche Texte der selben Zahl zugeordnet werden, wenn man nur 13 statt 32 Stellen nutzt ist demnach 36^32/36^13 = 8.983.937.243.574.936.144.818.585.412.584.022 mal höher.
Diese Zahl sieht ziemlich groß aus. Also ist es, verwendet man für den Hash nur 13 Stellen statt 32 "signifikant" wahrscheinlicher, dass zwei Texte den gleiche Hash bekommen.
Für die Zahlen danke ich den Programmierern des freien Linux-Programmes "bc".
fastix
-
Hi,
Das kannst du doch sicher mathematisch beweisen, oder?
Das kann man sogar in einer Art begreifen, die für Kinder eingängig ist:
Ich denke mal, dass dies Sven klar ist. Es geht um folgende Frage:
gibt es eine bestimmte Verteilung auf den ersten bzw. den letzten Ziffern?Wenn suit sagt, dass durch reines Kürzen des Hashes die Kollisionswahrscheinlichkeit "signifikant ansteigt" (was ich interpretiere als "über die von dir berechnete Wahrscheinlichkeit hinaus), dann müsste er wissen, dass z.B. die letzten Ziffern anders gebildet werden als die erste.
Anders ausgedrückt:
ist die Verteilung der Ziffern gleichverteilt, steigt durch reines Kürzen die Kollisionswahrscheinlichkeit etwa so an, wie du es beschrieben hast.
Sind z.B. die späteren Ziffern anders verteilt als jene zu Beginn, dann würde das Kürzen des String die Kollisionswahrscheinlichkeit deutlich anders verändern.Bis die Tage,
Matti-
Wenn suit sagt, dass durch reines Kürzen des Hashes die Kollisionswahrscheinlichkeit "signifikant ansteigt" (was ich interpretiere als "über die von dir berechnete Wahrscheinlichkeit hinaus), dann müsste er wissen, dass z.B. die letzten Ziffern anders gebildet werden als die erste.
Das war unglücklich ausgedrückt, das eine bezog sich auf das Geburtstagsproblem, das andere auf den Rest :) - in meinem Abschlusssatz steht daher auch "tritt so eine Kollision potentiell früher auf".
Sicher ist das natürlich nicht und ohne Kenntnis über die genannten Faktoren nicht möglich - aber für etwas, das man einfach nicht wissen kann, ist das zu gefährlich.
ist die Verteilung der Ziffern gleichverteilt, steigt durch reines Kürzen die Kollisionswahrscheinlichkeit etwa so an, wie du es beschrieben hast.
Nicht etwa, sondern exakt - und die verhält sich nicht linear. "50 % vom String abschneiden" heisst nicht "50 % kleinerer Wertbereich"
Sind z.B. die späteren Ziffern anders verteilt als jene zu Beginn, dann würde das Kürzen des String die Kollisionswahrscheinlichkeit deutlich anders verändern.
Aber nachdem du das bei einem so komplexen Verfahren nicht wissen kannst, hast du ziemlich gute Chancen, dass es so ist - oder auch nicht - und aus kryptographischer Sicht ist das einfach nicht Schlau, weil man sich bei solchen Sachen böse verschätzen kann.
-
Moin!
Wenn suit sagt, dass durch reines Kürzen des Hashes die Kollisionswahrscheinlichkeit "signifikant ansteigt" (was ich interpretiere als "über die von dir berechnete Wahrscheinlichkeit hinaus), dann müsste er wissen, dass z.B. die letzten Ziffern anders gebildet werden als die erste.
Dann könnte man die ersten Ziffern weglassen und die Kollisionswahrscheinlichkeit würde nicht signifikant ansteigen? Man kann dicke Bücher über Hashalgorithmen lesen aber ich glaube im Verhältnis zu dem signifikanten Unterschied zwischen der originalem MD5-Hash und dessen Verkürzung auf 13 Stellen ist der Unterschied, ob man die ersten oder die letzten 19 Stellen streicht oder eine jede anderen Kürzungsvorschrift anwendet kaum noch bemerkbar. Fakt ist, dass selbst kleinste Veränderungen am Text zu einer Änderung quer durch den gesamten Hash führen, was darauf schließen lässt, dann jeder Algorithmus der _blosen_ Kürzung auf die gleiche Stellenzahl zu einer annähernd gleich erhöhten Kollisionswahrscheinlichkeit führt.
Nun, statt rein zu kürzen könnte ja auch die Bildungsvorschift verändert werden. md5 kennt Ziffern und kleine Buchstaben. Erhöht man auf Ziffern, Kleine Buchstaben und große Buchstaben hat man nicht 36 sondern 62 "Ziffern".
36^32 = 63340286662973277706162286946811886609896461828096
36^13 = 170581728179578208256
62^13 = 200028539268669788905472Das kann man weiter treiben und 8 Bit (ein Byte) voll ausnutzen:
256^13= 20.282.409.603.651.670.423.947.251.286.016Nutzt man die Busbreite eines 64-Bit-Prozessors aus, dann kommt man auf:
18446744073709551616^13 =
28638903918474961204418783933674838490721739172170652529441449702311\ 06400535290415934528426582462837542935950921899972007439686075707337\ 67004450260415645796205128743079792121022668012614789787762450400082\ 31745247475930553606737583615358787106474295296Texte bis zur ersten Kollison. Trotz der Kürzung auf 13 Stellen wäre eine Kollision sehr viel unwahrscheinlicher. Eine Schwierigkeit sehe ich dann aber in dem der Menschheit verfügbaren und für Menschen merkbaren Zeichenvorrat. Immerhin soll man das Ergebnis eines Hashes auch ausdrucken können um es auf einem gänzlich anderen Kanal (z.B. per Bote) transportieren zu können, damit festgestellt werden kann, ob ein über den ersten Kanal übermittelter "Text" unverändert ist.
Merke: Man kann einen Hash mit 13 Stellen so sicher machen wie einen mit 32 Stellen, wenn man den Algorithmus so verändert, dass er einen größeren Zeichenvorrat nutzt.
Die Fehler, die md5 unzweifelhaft hat, treten übrigens hinter den gezeigten Zahlen zurück. Das Hauptproblem von md5 ist die Vorhersagbarkeit: Es ist unter bestimmten Voraussetzungen möglich zwei Texte mit gleichem Hash (das ist die erwähnte Kollision) zu _generieren_.
MFFG (Mit freundlich- friedfertigem Grinsen)
fastix
-
Hi,
Wenn suit sagt, dass durch reines Kürzen des Hashes die Kollisionswahrscheinlichkeit "signifikant ansteigt" (was ich interpretiere als "über die von dir berechnete Wahrscheinlichkeit hinaus), dann müsste er wissen, dass z.B. die letzten Ziffern anders gebildet werden als die erste.
Dann könnte man die ersten Ziffern weglassen und die Kollisionswahrscheinlichkeit würde nicht signifikant ansteigen?
Nein, das habe ich nicht gesagt.
16^32 ist deutlich größer als 16^13.Aber wenn (und nun lies dir suits Posting durch, er erklärt das genauer) die Wahrscheinlichkeitsverteilung auf einzelnen Stellen nicht gleich ist, dann ist die Wahrscheinlichkeit, zu einem 13-stelligen String einen String mit passendem verstümmelten MD5-Hash zu finden, eben nicht die erwarteten 16^13 sondern anders, je nach Verteilung.
Das meine ich mit "über die von dir berechnete Wahrscheinlichkeit hinaus". Für genauere Aussagen muss man genauer wissen, wie MD5 verteilt. Und genau dieses Wissen hat Sven infrage gestellt.
Bis die Tage,
Matti-
Das meine ich mit "über die von dir berechnete Wahrscheinlichkeit hinaus". Für genauere Aussagen muss man genauer wissen, wie MD5 verteilt. Und genau dieses Wissen hat Sven infrage gestellt.
Und dieses Wissen hat vermutlich auch keiner - es ist aber bekannt, dass die Hashes nicht gleichverteilt und nicht surjektiv sind. Und allein diese Tatsache ist der Grund dafür, warum das kürzen sich nicht direktproportional zur Rechnung verhält.
Das Ausmaß selbst ist natürlich nicht bekannt.
-
-
Merke: Man kann einen Hash mit 13 Stellen so sicher machen wie einen mit 32 Stellen, wenn man den Algorithmus so verändert, dass er einen größeren Zeichenvorrat nutzt.
Du vergisst dabei, dass MD5 eine 128-Bit-Ganzzahl ist - die nur als 32-stellige Hexadezimalzahl, als 39-stellige Dezimalzahl oder sonstwie dargestellt wird.
Wenn man viele Hashes in einer Datenbank speichert, ist man selbst Schuld, wenn man diese als Text speichert - es bleiben 128 Bit. Warum sollte man für 128 Bit Informationsgehalt 32 Byte Speicherplatz verschenken?
Die Fehler, die md5 unzweifelhaft hat, treten übrigens hinter den gezeigten Zahlen zurück. Das Hauptproblem von md5 ist die Vorhersagbarkeit: Es ist unter bestimmten Voraussetzungen möglich zwei Texte mit gleichem Hash (das ist die erwähnte Kollision) zu _generieren_.
Und nachdem das bereits bei einem vollständigen, ungekürzten Hash machbar ist, ist es ungleich einfacher, wenn man nur noch rund 1/3 der Stellen hat.
-
Hi!
md5 kennt Ziffern und kleine Buchstaben.
MD5 kennt nur 128 Bit. Diese werden normalerweise als 32-stellige Hexadezimalzahl notiert. Also 0..9 und a..f und keineswegs g..z. Ob die Buchstaben groß oder klein geschriebnen werden ist dabei unerheblich.
Lo!
-
MD5 kennt nur 128 Bit. Diese werden normalerweise als 32-stellige Hexadezimalzahl notiert. Also 0..9 und a..f und keineswegs g..z. Ob die Buchstaben groß oder klein geschriebnen werden ist dabei unerheblich.
Er meint: wenn man die Zahl als Text darstellt, kann man die Zahlenbasis ändern um so eine kürzere Zeichenkette zu erhalten - aber warum sollte man das machen?
-
Moin!
Er meint: wenn man die Zahl als Text darstellt, kann man die Zahlenbasis ändern um so eine kürzere Zeichenkette zu erhalten - aber warum sollte man das machen?
Weil dies nach Übertragung des Hashes in Papierform (=2. unabhängiger Kanal) ermöglicht, weniger Stellen einzutippen?
MFFG (Mit freundlich- friedfertigem Grinsen)
fastix
-
Er meint: wenn man die Zahl als Text darstellt, kann man die Zahlenbasis ändern um so eine kürzere Zeichenkette zu erhalten - aber warum sollte man das machen?
Weil dies nach Übertragung des Hashes in Papierform (=2. unabhängiger Kanal) ermöglicht, weniger Stellen einzutippen?
Und dabei suchst du Zeichen auf der Tastatur deren Existenz du bisher nichtmal kanntest, wenn du die Zahlbasis auf hochdrehst :p
-
Moin!
Und dabei suchst du Zeichen auf der Tastatur deren Existenz du bisher nichtmal kanntest, wenn du die Zahlbasis auf hochdrehst :p
Jepp. Da war doch was mit dem Typ, der in einer schönen bunten Windows-Oberfläche per Fernverwaltung ein ganz neues und ganz sicheres True-Crypt-Password eingab und ganz vergaß, dass er alle die schönen Sonderzeichen dann beim Booten des Servers (der in einem Rechenzentrum steht) über eine merkwürdige Konsole (in Java implementiert) eingeben muss - die auf Steuerzeichen ziemlich merkwürdig reagiert.
MFFG (Mit freundlich- friedfertigem Grinsen)
fastix
-
Tach,
Jepp. Da war doch was mit dem Typ, der in einer schönen bunten Windows-Oberfläche per Fernverwaltung ein ganz neues und ganz sicheres True-Crypt-Password eingab und ganz vergaß, dass er alle die schönen Sonderzeichen dann beim Booten des Servers (der in einem Rechenzentrum steht) über eine merkwürdige Konsole (in Java implementiert) eingeben muss - die auf Steuerzeichen ziemlich merkwürdig reagiert.
gut dass TrueCrypt deswegen immer einen Testlauf inklusive Booten startet und das Paßwort nur nach erfolgreichem Versuch setzt.
mfg
Woodfighter-
Jepp. Da war doch was mit dem Typ, der in einer schönen bunten Windows-Oberfläche per Fernverwaltung ein ganz neues und ganz sicheres True-Crypt-Password eingab und ganz vergaß, dass er alle die schönen Sonderzeichen dann beim Booten des Servers (der in einem Rechenzentrum steht) über eine merkwürdige Konsole (in Java implementiert) eingeben muss - die auf Steuerzeichen ziemlich merkwürdig reagiert.
gut dass TrueCrypt deswegen immer einen Testlauf inklusive Booten startet und das Paßwort nur nach erfolgreichem Versuch setzt.
Vielleicht hat der Typ das genau aus dem Grund so implementiert :)
-
-
-
-
-
-
-
-
-
-
Äh nein - das ist kein Hash mit 13 Stellen sondern ein vrstümmelter Hash der eine Signifikant höhere Kollisionswahrscheinlichkeit hat als ein (theoretisch) baugleicher Hashalgorithmus, der tatsächlich 13 Stellen liefert.
Das kannst du doch sicher mathematisch beweisen, oder?
Nein (sort of) - aber siehe unten, durch ein paar bekannte "Probleme" im MD5 liegt der Schluss nachvollziehbar.
vgl. "Geburtstagsproblem."
Ich glaube nicht, dass das Geburtstagsproblem hier maßgeblich ist.
Für den von dir herraus gegriffenen Teil nicht - der ist dafür relevant, dass dieses vorgehen bei einer perfekt gleichverteilten Hashfunktion zu einer höheren Kollisionswahrscheinlichkeit führt, wenn man einfach ein oder mehrere Stellen abschneidet. Das würde sich direkt proportional verhalten.
Bei einem echten (perfekten) Hash-Algorithmus mit 13 Stellen und 16 Zeichen Vorrat würde eine Kollision nach spätestens ~4.5*10^15 Klartexten auftreten - wenn du aber die Entropie eines Streuwerts verringest, indem du einfach vom Fetigen Hash ein paar Stellen abschneidest, tritt so eine Kollision potentiell früher auf.
Das heißt, du hast Erkenntnisse über die Streuung von MD5-Ergebnissen?
Es sollte doch mittlerweile allgemein bekannt sein, dass MD5 nicht surjektiv ist und keine "gleichverteilten" Ergebnisse liefert
Ein ganz einfaches Beispiel - du hast einen Hash-Algorithmus der nicht surjektiv und nicht gleichverteilt ist.
Der Streuwert besteht aus 2 Dezimalziffern - der Wertbereich dieser Zeichenkette liegt bei 00 bis 99 (also 100 Möglichkeiten) - tatsächlich ist es aber so, dass in 33% der Fälle der Hash 10 daherkommt und in 66% der Fälle 01. Es gibt also im Grunde nur 2 Möglichkeiten, die nicht gleichverteilt sind
Jetzt nimmst du aus Platzgründen deinen Hash und halbierst ihn, die erste Stelle muss reichen - du hast also aufgrund der Gleichverteilung nur noch eine 0 oder 1 zu erwarten - aufgrund der ungleichmßigen Verteilung und dass der Wertbereich nicht völl ausgeschöpft wird, hast du aber mit der halben Anzahl an Stellen nicht einfach eine halbierte Wertbereich sondern eine um den Faktor 10 geringeren zusätzlich durch die fehlerhalfte Gleichverteilung hat dieser keinen Linar geringeren Informationsgehalt sondern im schlimmsten Fall nur noch 66 %.
Nachdem du aber nicht wissen kannst, wie die Werte verteilt sind und wie die fehlende Surjektivität zum Tragen kommt, hast du also ziemlich gute Chancen, dass du schlechter dastehst als vorher.
-
-
-
-
Gibt es einen Hash-Algo, der einen 13 stelligen Code erzeugt bestehend aus den Buchstaben abcdef und den Zahlen 0123456789 ?
Wozu willst du das wissen?
-
Hallo Mike,
Gibt es einen Hash-Algo, der einen 13 stelligen Code erzeugt bestehend aus den Buchstaben abcdef und den Zahlen 0123456789 ?
Vielleicht kannst du im folgenden Archivthread eine Lösung finden: http://forum.de.selfhtml.org/archiv/2009/8/t190177/#m1267232
DOrt hatte ich nach einem ähnlichen Problem gefragt (6-stelliger Hashwert). Die Lösungsvorschläge haben mir sehr geholfen und du hast ja sogar 13 Stellen zur Verfügung.
ciao
romy--
Piraten ahoi