[Brick]

Hey liebe Leser,

mich würde interessieren ob eine Hash-Funktion, die einen Hash-Wert aus 128 Bit (Im Nachhinein: die Länge des Hash-Wertes ist 128 Bit) erzeugt, eine Gesamtanzahl von:
340.282.366.920.938.463.463.374.607.431.768.211.456 (entspricht 128 Bit) Hash-Werten erzeugen kann?
Beispiel MD5

Danke im Voraus für die Antworten

Dieser Beitrag wurde von Brick bearbeitet: 06. Juni 2017 - 22:40

[RalphS]

Nein. Das ist unmöglich.

Here's why:

- Eine Hashfunktion ist, wie jede andere Funktion auch, eine Zuordnung von einer Eingabe x zu einem Funktional f(x).

- Eine Hashfunktion hat - im Sprachgebrauch -- weiterhin den Anspruch, unumkehrbar zu sein. Im Klartext: Wenn ich ein Funktional f(x) habe und weiß, daß es mit der Hashfunktion H bestimmt wurde (also H(x)), dann soll ausgeschlossen werden können, aus diesem H(x) wieder x zu ermitteln (cf Inversfunktion).


Was heißt das für uns?

Wenn wir einen Wert X haben, welcher auf einen Wert Y abbildet (unser Hashwert), und wir weiterhin annehmen, daß beide Wertebereiche eingeschränkt sind auf 0..2¹²⁸-1, dann haben wir eine Funktion, die für beliebiges X ein klar definiertes Funktional Y haben *muß*.

Anderenfalls wäre sie nicht eindeutig, da f(x1) identisch zu f(x2); in diesem Fall ist aber der Wertebereich um genau dieses f(x2) verkleinert, weil das ja auf f(x1) abbildet.

Jedem einzelnen X aus dem Wertebereich von X ist also genau ein Y aus dessen Wertebereich zuzuordnen.

Damit haben wir Eineindeutigkeit. Diese ist nach (geläufiger) Hashdefinition nicht zugelassen.


Ergo ist eine unserer Annahmen falsch:
> Entweder lassen wir 1:1 Zuordnungen für Hashfunktionen zu; ODER
> eine Funktion mit identischen Wertebereichen für x und f(x) kann keine Hashfunktion sein.

CAVEAT.

In einem strikt mathematischen Sinne ist eine Hashfunktion ETWAS ANDERES. Hier geht es darum, daß Eingaben in buckets aufgeteilt werden können. Modulo ist nach dieser Definition eine Hashfunktion.

Ergo kann es in einem mathematischen Sinne eine *entartete* Hashfunktion geben, welche eineindeutig zuordnet. Jeder Eingabe X ist damit ein Bucket Y zuzuordnen. Beispiel: Eingabe 0..59, Ausgabe 0..59 (=> Wertebereiche sind identisch) und die Hashfunktion nennt sich schlicht "äquivalent mod 60" (wobei das "äquivalent" hier durch ein Gleichheitszeichen mit drei statt zwei Strichen ausgedrückt wird).

So eine Hashfunktion ist aber für Kryptographiezwecke unbrauchbar.

Dieser Beitrag wurde von RalphS bearbeitet: 06. Juni 2017 - 17:15

[Brick]

Zitat (RalphS: 06. Juni 2017 - 17:11)

Nein. Das ist unmöglich.

Here's why:

- Eine Hashfunktion ist, wie jede andere Funktion auch, eine Zuordnung von einer Eingabe x zu einem Funktional f(x).

- Eine Hashfunktion hat - im Sprachgebrauch -- weiterhin den Anspruch, unumkehrbar zu sein. Im Klartext: Wenn ich ein Funktional f(x) habe und weiß, daß es mit der Hashfunktion H bestimmt wurde (also H(x)), dann soll ausgeschlossen werden können, aus diesem H(x) wieder x zu ermitteln (cf Inversfunktion).


Was heißt das für uns?

Wenn wir einen Wert X haben, welcher auf einen Wert Y abbildet (unser Hashwert), und wir weiterhin annehmen, daß beide Wertebereiche eingeschränkt sind auf 0..2¹²⁸-1, dann haben wir eine Funktion, die für beliebiges X ein klar definiertes Funktional Y haben *muß*.

Anderenfalls wäre sie nicht eindeutig, da f(x1) identisch zu f(x2); in diesem Fall ist aber der Wertebereich um genau dieses f(x2) verkleinert, weil das ja auf f(x1) abbildet.

Jedem einzelnen X aus dem Wertebereich von X ist also genau ein Y aus dessen Wertebereich zuzuordnen.

Damit haben wir Eineindeutigkeit. Diese ist nach (geläufiger) Hashdefinition nicht zugelassen.


Ergo ist eine unserer Annahmen falsch:
> Entweder lassen wir 1:1 Zuordnungen für Hashfunktionen zu; ODER
> eine Funktion mit identischen Wertebereichen für x und f(x) kann keine Hashfunktion sein.

CAVEAT.

In einem strikt mathematischen Sinne ist eine Hashfunktion ETWAS ANDERES. Hier geht es darum, daß Eingaben in buckets aufgeteilt werden können. Modulo ist nach dieser Definition eine Hashfunktion.

Ergo kann es in einem mathematischen Sinne eine *entartete* Hashfunktion geben, welche eineindeutig zuordnet. Jeder Eingabe X ist damit ein Bucket Y zuzuordnen. Beispiel: Eingabe 0..59, Ausgabe 0..59 (=> Wertebereiche sind identisch) und die Hashfunktion nennt sich schlicht "äquivalent mod 60" (wobei das "äquivalent" hier durch ein Gleichheitszeichen mit drei statt zwei Strichen ausgedrückt wird).

So eine Hashfunktion ist aber für Kryptographiezwecke unbrauchbar.

Also ich hatte halt gelesen, dass Hash-Werte von MD5 nicht eindeutig sind.
Und das es mit geringer Wahrscheinlichkeit zwei Dokumente mit dem identischem Hash-Wert geben kann...
Aus der Quelle und aus Wikipedia habe ich mir dann auch die 3,4*10^38 Hash-Werte erschlossen.

https://www.php-einf...es/was-ist-md5/
https://de.wikipedia...est_Algorithm_5
https://de.wikipedia...Cssell%C3%A4nge

Sind diese Quellen also fehlerhaft?

[RalphS]

Dann hab ich Deine Frage mißverstanden.

Eine Hashfunktion klassifiziert. Das ist ihre Aufgabe; dafür ist sie da. Wie erwähnt ist das einfachste Beispiel der Modulo, der zu einer Zahl n den Rest einer ganzzahligen Division liefert. Dabei wird natürlich nicht zu jedem X ein eindeutiges f(x) geliefert, sondern Resteklassen - deswegen spricht man ja auch von Äquivalenz und nicht von Gleichheit. 1 mod 60 ist 1; 61 mod 60 ebenso oder, formal, a*x+b mod x ist äquivalent zu b (das a geht verloren).

Hashfunktionen haben noch eine andere Eigenschaft: Sie bilden Eingaben *beliebiger* Länge auf eine Ausgabe *fixer* Länge ab. Es sollte also auf der Hand liegen, daß irgendwann das Maß voll ist und daß es zwangsläufig Kollisionen geben MUß: Spätestens dann, wenn man 2^Hashlänge+1 verschiedene Eingaben reinfüttert und versucht, diese auf nur 2^Hashlänge abzubilden, ist klar, daß nun zwei unbekannte, aber ermittelbare Eingaben denselben Hashwert haben *müssen*, sodaß für unterschiedliche x1, x2 gilt: f(x1) = f(x2).


Für Kryptographie ist das natürlich nicht gewollt. Kryptographie möchte sich "nur" die unumkehrbare Eigenschaft der Hashfunktionen zunutze machen, während aber Kollisionen (s.o.) vermieden werden.

Das ist mit Hashfunktionen faktisch nicht möglich. Man kann sich annähern, ja, aber Hashfunktionen *können* nicht eindeutig sein. Man kann nur versuchen, den Hash-String so lang zu gestalten, daß für jede Eingabe praktisch nur eine Ausgabe in Frage kommt.


Erschwerend kommt hinzu, daß Hashalgorithmen nicht immer exakt das tun, was sie laut Entwurf tun sollten. Das ist das Problem mit aktuellen Implementierungen wie eben MD5 oder inzwischen auch SHA-1. Es hat sich herausgestellt, daß man zwar DACHTE, daß 1:1 Buckets zugeordnet werden, das aber blöderweise nicht der Fall war.

Schlimmer noch, man mußte feststellen, daß es ein immanentes Problem gibt. 1:1 Abbildung bedeutet Eineindeutigkeit und Eineindeutigkeit bedeutet Umkehrbarkeit, und entsprechend gibt es die berüchtigten Rainbow Tables, letztlich ein Wörterbuch Hash-zu-Klartext. Dagegen hat man dann das Salz "erfunden". Aber auch das hilft nicht gegen Überlauf.

Ein anschauliches Beispiel ist DES (nicht Triple-/3DES, sondern Single-DES). Das ist schön kurz, sodaß man gut nachvollziehen kann, daß "zuviele" Eingaben automatisch für Kollsionen sorgen müssen, unabhängig davon, daß außerdem noch Kollisionen auftreten können, wo man gedacht hatte, daß da keine wären.


Und um Deine Frage zu beantworten unter der Annahme, daß Du nicht die Eingabe, sondern die Ausgabe gemeint hast: JA, es ist Zweck einer kryptographischen Hashfunktion, vollständig abzubilden (alle möglichen Bitmuster sind gültige Ergebnisse der Hashfunktion). NEIN, das wird man praktisch nicht erreichen.

Dieser Beitrag wurde von RalphS bearbeitet: 06. Juni 2017 - 19:53

[der dom]

Die Wahrscheinlichkeit dass 2 Dokumente den selben MD5-Hash haben liegt bei 1:1.5324955408658889e+54.

Ein MD5 Hash kann, wie RalphS das beschrieben hat, unter der Wahrscheinlichkeitsrate wie oben genannt, identisch sein, aber das ist - nun ja, die Wahrscheinlichkeit ist gering - Lottospielen bringt dort mehr :-).

Mich würde gerade viel eher interessieren wofür du das wissen wollen würdest?

Krypto ist nichts womit man sich mal "ebenso" beschäftigt sondern schon, wie meistens, ein tiefgehenderes Thema. Alghotechnisch und so und Background und weiß der Teufel was :-/

[RalphS]

Würd ich so nicht sagen. Das heißt: nicht so ohne Weiteres.

Denn für MD5, welches inzwischen geknackt ist, gibt es Anleitungen im Netz, wie man gezielt Kollisionen herbeiführen kann. Fieser Weise in einer Art, wo die bewußte Information *beliebig* manipuliert werden kann. IIRC mußte man dann nur noch einen spezifischen Block ins Dokument einfügen, welcher dann dafür gesorgt hat, daß das Ergebnis einen vorher festlegbaren MD5-Hash hatte.

Außerdem, und das geht ständig unter: Hashfunktionen arbeiten nicht mit Dokumenten, sondern mit sogenannten Nachrichten. Das ist einfach Text. Kann aber auch "Programmtext" sein (also eine Binärdatei); "Text" dann insoweit, daß das eben alles irgendwie Zeichen sind, wenn auch keinem Zeichensatz entsprechend. Halt simpler Text, der aus Versehen zusätzlich ausführbar ist.

So und nun haben wir also die Möglichkeit, md5 auf sonstwelche Eingaben anzuwenden: Richtigen Text, sagen wir eine SMS. Oder ein Buch, auch richtiger Text, nur viel länger. Bilder. Musik. Videos und sonstwas für Dateitypen, was ja prinzipiell samt und sonders aneinandergereihte Zeichen und damit auch Text ist.

Wenn wir jetzt jeden Erdenbewohner eine A4-Seite schreiben lassen täten, hätten wir sowas ähnliches wie 7'000'000'000 verschiedener Nachrichten.

Lassen wir jeden noch ein Bild malen. Das Doppelte, also ~14mrd.
Ton? Weitere 7mrd.
Irgendwas Bewegtes? Weitere 7mrd.

Und so weiter. Früher oder später haben wir mehr Nachrichten zusammen, als md5 eindeutig abbilden kann.

[Brick]

Vielen Dank für die Antworten

Ich beschäftige mich momentan mit Hash-Funktion, weil ich einen Vortrag über ihre Sicherheit halte und in diesem verwende ich MD5 für ein Beispiel.
Die Anzahl der möglichen Hash-Werte verwende ich um aufzeigen, dass es trotz einer riesigen Anzahl an möglichen "Hashes", realativ einfach ist Kollision zu erzeugen.
Auf Rainbow Tables gehe ich auch ein.

Die Frage habe ich gestellt, weil ich mir nicht sicher war ob bei 128 Bit langen Hash-Werten, tatsächlich die oben angegebe Zahl an Hash-Werten möglich ist.

[RalphS]

Grundsätzlich ja. Sonst wäre es ja albern. Einer der 'simplesten' Angriffe auf Kryptohashfunktionen zielt ja darauf ab, den Wertebereich von H(x) einzuschränken (cf Bitverkürzung). Wenn es also gelingt, ein 1:1 Mapping zu erstellen zwischen der Originalfunktion (mit sagen wir 128bit Länge) und einer anderen mit weniger.

Dann hätte man sozusagen als Nebeneffekt das Ergebnis, daß 2^n-k potentielle Ergebnisse aus der Ergebnismenge nicht zugeordnet werden können (wenn n die Länge der Originalfunktion ist, hier 128, und k die Länge einer zu ermittelnden Analogfunktion).

Oder anders ausgedrückt, wenn es gelingen würde, x^3 mit x^2 darzustellen, dann hätte man sich das x^3 auch sparen können.

Kryptohashes sind ein schwieriges Thema. Ich persönlich würde vom Einsatz abraten (in Abhängigkeit davon, worum es am Ende geht). Man kann auch anders signieren, zB via PGP oder mit X.509.

[My1]

naja aber signaturen mit PGP haben hashwerte und auch in x509 sind hashes sehr bedeutend:

bei PGP zum beispielt geht der block bei ner mail bspw so los:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

und zertifikate in x509 nutzen auch hashes deswegen war es mit SHA1 und den browsern so lustig.

[RalphS]

Ja, die basieren auch darauf, das stimmt. Nicht zuletzt der Fingerprintalgorithmus. Der ist ja schon recht kritisch.

Aber ich bild mir zumindest ein, daß X509 (und PGP) Hashfunktionen zwar verwenden, aber halt darauf "nur" aufsetzen und sich nicht zu 100% drauf verlassen.

Eh. Vermutlich auch nur Wunschdenken.

Wie auch immer, es spricht ja nichts dagegen, das einzusetzen. Man muß sich halt nur im Klaren darüber sein, daß nicht alles Gold ist, was glänzt, und daß Hashfunktionen eben auch Grenzen haben.

Besonders, wenn sie für Dinge verwendet werden, für die sie niemals gedacht waren. Da liegt zumindest für mich auf der Hand, daß es dort irgendwo inhärente Probleme gibt, an die man vielleicht noch gar nicht gedacht hat.

Wenn man einen Laserdrucker hat, kippt man ja auch keine Tinte rein. Und wenn man die trocknet und zu Pulver stapft und DANN da reinkippt, naja dann funktioniert es vielleicht, aber man darf ich dann auch nicht wundern, wenn hinterher der LaserJet kaputt ist.

[My1]

naja die kryptographischen hashs (also nicht so n Kleinkram wie CRC32) sind schon mehr oder weniger dazu gedacht.

Im Prinzip kann man signaturen auch nicht viel anders machen gerade bei großen sachen, da RSA nur begrenzt frisst und dazu saulangsam ist.

Wichtig ist immer dass man a) ne zufällige nonce irgendwo unterbringt, sollte der algo machen (sonst ist was schief, mMn) b) ne aktuelle hashfunktion nutzt und c) auch die Zeit ne bedeutung hat (sodass wenn man nen hash bruteforcen will nochwas zum drauf achten bekommt

eine sache die man aber mMn verbessern könnte ist, da iirc die sig selbst (also das was in RSA selbst landet) meist nur den hash hat (achtung: iirc, is ne weile her dass ich mich damit beschäftigt habe), dass da mehr reinkommt:

ganz nett ist ja dass ne eine RSA nummer etwas mehr passt
in RSA ist bei dem Padding schema OAEP die maximale länge:

(keylength in bytes - 42) Byte

ergo n 2048 bit key kann 214 bytes.

n SHA512 (ich nehm die immer wenns geht da einfach der Raum größer und theoretisch weniger kollisionsgefahr besteht, später dann SHA3-512) das zieht 64 byte. bleiben 150 byte. genug platz um bspw ne 128 byte nonce und die Zeit direkt in die signatur zu packen und wenn diese auch in den Hashvorgang einfließen lassen.

auch würde das unmissverständlich die Zeit Klar machen in der die sig erstellt wurde, ergo man kann nicht bei der nachricht beim fakehashen ne falsche zeit reinstecken, da die in der sig nicht stimmen würde, und die in der Sig bekommen man nur geändert wenn man RSA (oder den algo der zukunft) aufbekommt und dazu kommt, dass man dank der nonce keine vorarbeit leisten kann.

was man auch übles machen könnte wäre, mehrere sichere hashwerte in die sig zu werfen, bspw SHA-512 und SHA3-512 oder so was in der art, da müssten schon beide verfahren ersthafte probleme haben. man muss nur aufpassen, dass man diese werte nebeneinander wirft, und nicht die hashes kaskadiert, denn das wäre übel.

[der dom]

PGP rate ich im Falle von lokal oder intern abgelegten zu verschlüsselnden Daten ab - x.509 da bin ich dabei - aber auch nur in Abhängigkeit von der "Wichtigkeit".

In Programmen nutze ich z.B. in den kleineren Programmteilen AES mit S+P. Bei wichtigen Dingen gehe ich auf x.509 und bei ganz banalen Sachen tatsächlich auf MD5 oder SHA. Das müsste / sollte / kann jeder nach seinem Gusto entscheiden - und das sollte, meines Erachtens nach auf auf die Umgebung abgstimmt werden.

PGP für Mails - klar. Das sollte sein, aber auch da finde ich, kommt es auf die Situation drauf an. Wenn ich z.B. einen simplen Newsletter über [email protected] verschicke, dann brauche ich kein PGP sofern dort keine kritischen Infos drin sind und so ein gedöhns.

Versende ich Mails mit Informationen die keinen was angehen versende oder die mich großflächig (lies: ich -> Firma oder Kunde oder so) angreifbar machen, dann PGP - keine Frage.