Wann gilt sha256 als gescheitert?

Fragen Technik
1

wahrscheinlich in erster linie wenn man von einem hashwert zurück rechnen kann (ohne brutforcen), wie der ursprungswert lautet.
Mit 64 Byte meine ich das der Hashwert 64 Zeichen lang ist (von 0-9 und a - f)
Da ja auch ein 3MB großes MP3-File einen 64Byte großes Hashwert erzeugt, kann ja eigentlich nie von den 64 Byte Hashwert wieder zurück zum 3MB MP3 File zurück gerechnet werden. Also eigentlich unmöglich. Ist das schon mal richtig?

Würde denn Sha256 aber als gescheitert gelten, wenn 2 unterschiedliche Ursprungswerte zum gleichen Hashwert führen würden?
Sooooo viele verschiedene Hashwerte (sha256) gibt es ja nun auch nicht. Maximal 16hoch64 oder? wenn ich also (oder viele computer) brutforcen, und mit 1 anfangen und bis 16hoch64 + 1 alle zahlen dazwischen in einem hash generator eingeben, dann müssen doch 2 verschiedene zahlen aus dem riesigem Nummernkreis zu einem doppelten Hashwert führen.
Ich gehe mal davon aus das das eben noch nie passiert ist, aber bei 16hoch64 +1 versuchen und doppelten hashwert wäre sha256 kaputt?

2

Genau das reicht schon, weil man daraus eventuell Informationen bekommen könnte um weitere Kollisionen zu errrechnen. Eine direkte Gefahr gibt es dann zwar noch nicht direkt, aber es ist definitiv der Anfang um sich einer anderen Hashfunktion zuzuwenden.

Hast du diese Zahl einmal ausgerechnet? Vergleiche diese Zahl mal mit der Anzahl an Atome im sichtbaren Universum.

3 „Gefällt mir“
3

ich wollte mir die zahl mit chat gpt anzeigen lassen.
dafür ist chat gpt einfach zu dämlich.
chat gpt meinte die zahl hätte 78 stellen.
ich dachte sogar das könnte stimmen, da ja 10hoch 64 eine 10 mit 64 stellen dahinter wäre.
somit dachte ich 78 stellen bei 16hoch64 wäre plausibel.
scheint aber nicht so zu sein. Ich und chat gpt sind dafür zu doof.
eine verdoppelung (reis auf jedes schachbrett feld) ist dann schon sehr gewaltig.
ok

4

Ich stecke auch nicht so tief im Thema drin. Aber du kannst mal in den englischen Wikipedia Artikel reinschauen:

→ SHA-2 - Wikipedia

Und zwar in den Abschnitt Cryptanalysis and validation, inkl. der Tabelle.

Dort sieht man wie im Laufe der Jahre immer bessere theoretische Angriffe auf SHA-256/512 gefunden wurden.

SHA-256 verarbeitet und mixt den Input in 64 identischen Runden, um den letztlichen Hash zu erhalten.

Bei gleicher Funktionsweise, aber weniger Runden, sind schon Angriffe bekannt, um entweder Kollisionen zu erreichen, oder auf den ursprünglichen Input zurückzuschließen. Diese Angriffe sind besser als ein Bruteforce-Angriff, haben aber teilweise immer noch sehr hohe Komplexität. D.h. es wäre immer noch ein hoher Rechenaufwand notwendig.

Man könnte also selbst bei Erreichen der 64 Runden nicht von einem Bruch in dem Sinne sprechen, dass man direkt mit einem einfachen Rechner von heute auf morgen alle Hashes zurückrechnen kann.

Trotzdem würde ich SHA-2 als „langsam nicht mehr sicher“ betrachten, wenn der erste Angriff die 64 Runden fast erreicht, also bei voller Rundenzahl signifikant besser als Bruteforce ist. Oder wenn sich eine neue Computer-Technologie rasant dem Punkt nähert, an dem ein Angriff praktisch durchführbar wäre.

Zum Vergleich kann man sich den Vorgänger ansehen:

→ SHA-1 - Wikipedia
→ Secure Hash Algorithm – Wikipedia

Ich fasse zusammen:

Schon Anfang der 2000er Jahre gab es erste Bedenken ggü. praktisch machbaren Angriffen mit sehr hohem Rechenaufwand. 2010 wurde von vielen Seiten der Übergang auf den Nachfolger gefordert. Zwischen 2005 und 2011 wurden immer bessere Kollisions-Angriffe gefunden, die nicht den „normalen“ Aufwand von 2^80, sondern letztlich nur noch 2^60 erfordern. 2017 wurde die erste Kolission veröffentlicht. Seit 2020 kann man unterschiedliche Inputs, z.B. Dokumente, gezielt so verändern bzw. ergänzen, dass man denselben Hashwert erhält. Und trotzdem wird SHA-1 anscheinend immer noch eingesetzt.

„NIST empfiehlt, SHA-1 nicht mehr für digitale Signaturen zu verwenden, lässt die Nutzung für Anwendungszwecke, die keine Kollisionsresistenz benötigen, aber noch bis 2030 zu“.

Der Nachfolger SHA-2 wurde parallel Anfang der 2000er Jahre veröffentlicht und ein Übergang von SHA-1 auf SHA-2 wurde ebenfalls schon vor 2010 empfohlen.

Man sieht also, dass der Übergang fließend ist. Man kann bei Hash-Funktionen m.E. nicht wirklich von einem Bruch sprechen.

Genau so ist es auch. Du hast dir das schon richtig überlegt.

Allerdings benötigt man bei 2^256 möglichen Hashwerten nur einen Aufwand von 2^128 Versuchen, um durch Bruteforce eine beliebige Kollision zu erhalten. Siehe z.B.:

→ Suchergebnisse für „Geburtstagsparadoxon“ - Blocktrainer Forum

Noch viel schlimmer sind aber natürlich Angriffe, bei ein bestimmter Hashwert gezielt erreicht werden kann, oder bei denen zwei Inputs so ergänzt werden können, dass sie denselben Hash liefern.

4 „Gefällt mir“
5

Du hast schon recht, dass beide Zahlen um Größenordnungen abweichen, aber trotzdem sind beide Zahlen gigantisch groß. Es gibt ungefähr 10⁸⁴ Atome und 16⁶⁴ ist „lediglich“ ungefähr 10⁷⁷. Wir vergleichen also eine Zahl mit vielleicht 84 Stellen mit einer Zahl die ungefähr 77 Stellen hat. Wie kann man sich die Zahlen also vorstellen? Roman hatte einmal einen guten Vergleich gebracht.

Gut wir haben jetzt zwar deutlich mehr Atome als die Zahl, die wir vergleichen wollen. Also reduzieren wir die Anzahl einmal ein wenig: Statt alle Atome nehmen wir einmal alle Sterne, die du von der Erde im Idealfall über dir sehen kannst, wenn du 23 Stunden wartest. Damit fallen die Sterne raus, die du in der fehlenden Stunde sehen würdest. Das ist schon eine gute Näherung um die Anzahl der Atome, die du vergleichen willst in die Größenordnung der gesuchten Zahl zu setzen.

Um eine Kollision zu bekommen kannst du dir das jetzt so vorstellen, dass du dir einen dieser betrachteten Sterne aussuchen. Dann kannst du dir von diesem Stern einen beliebigen Himmelskörper aussuchen. Auf diesem Himmelskörper kannst du dir dann einen beliebigen Kontinent, Athmosphärenteil oder Flüssigkeisteil aussuchen. Und von dieser Auswahl suchst du dir ein beliebiges Atom aus.

Die Chance, dass es eine zufällige Kollision im Sha256 gibt ist jetzt also ungefähr so groß als wenn ein anderer Mensch exakt den gleichen Stern ausgesucht hat, exakt den gleichen Planeten, exakt den gleichen Kontinent und dort exakt auf das gleiche Atom gezeigt hat.

Diese Chance ist schon ziemlich gering, die meisten Kollisionen werden schon alleine dadurch verhindert, dass die Menschen auf komplett andere Sterne gezeigt haben. Und selbst wenn es doch einmal der gleiche Stern ist, dann gibt es dort immernoch sehr viel Auswahl an Himmelskörpern, Planeten, Kometen usw. Diese Kette, die von vorne bis hinten komplett gleich sein muss, verdeutlicht vielleicht wie unwahrscheinlich so ein Zufall ist.

Ja es kann vorkommen aber da würde man sofort Systematik unterstellen (also einen Effekt, der es Wahrscheinlicher macht wie z.B. eine Berechnung oder Absprache) anstatt wirklichen Zufall.

1 „Gefällt mir“
6

Noch ein kurzer Nachtrag…

@Fiatnotgood, du fragst ja im Bitcoin Kontext nach einem Bruch von SHA-256.

Dabei ist SHA-256 hier sicherheits-relevant für das Mining, für Transaktionen und beschränkt für deine Wallet. Bei der Wallet besteht der Haupt-Sicherungsmechanismus in Elliptic Curve Cryptography.

Beim Mining ist die Resistenz ggü. Kollisionen aber nun relativ unwichtig. Und solange es langsam immer einfacher wird, gezielt einen Hash zu erreichen, ist das kein Problem.
Nur die Hashrate würde über die Zeit evtl. schneller ansteigen als normal, falls die bekannten Angriffe praktisch für das Mining genutzt werden könnten. Gerade letzteres ist aber ebenfalls unwahrscheinlich.

Bei Wallets und Transaktionen ist die Kollisionswahrscheinlichkeit bedingt relevant. Allerdings hat man auch wesentlich weniger Nutzer von Wallets, als Versuche beim Mining. Andere Angriffe als beliebige Kollisionen wären natürlich wiederum gefährlich.

Hier hatten wir darüber diskutiert:

→ Reichen 12 Wörter?

3 „Gefällt mir“
7

Das ist korrekt.
Da es mehr als 2^256 mögliche Inputs gibt, ist die Konsequenz, dass es mehre (theoretisch sogar unendlich viele) verschiedene Inputs mit gleichem Hash gibt. Das was die Hash Verfahren sicher macht ist, dass es zwar theoretisch möglich aber praktisch quasi unmöglich ist, mit unseren heutigen Resourcen diese Duplikate zu finden.

Im Falle von manchen älteren Hash Varianten wurden solche Hash Kollisionen bereits entdeckt.
Bei SHA256 jedoch „noch“ nicht und das wird wohl noch ne ganze Weile dauern.

1 „Gefällt mir“
8

Ich frage mich, ist es eigentlich mathematisch bewiesen, dass von den theoretischen 2²⁵⁶ Möglichkeiten für ein Hashwert, wirklich alle möglichen Hashwerte durch den Hashing Algorihtmus erreichbar sind? Es könnte ja sein, dass durch den Algorihtmus selbst bestimmte Hashwerte unmöglich zu erreichen sind, ganz egal wie der Input aussieht. Ausprobieren geht ja schlecht. Es muss also mathematisch klar sein dass prinzipiell alle möglichen Hashwerte erreichbar sind. Weil falls nicht, bliebe eigentlich unklar, wie viel mögliche verschiedene Hashwerte wirklich verfügbar sind. Und damit auch die Wahrscheinlichkeit für eine Kollision.

2 „Gefällt mir“
9

Nein, das ist es nicht und damit basiert das alles, wie du sagst, auf Annahmen.

Allerdings nimmt man für die Abschätzung bzgl. Kollisionen an, dass die Outputs im kompletten 256 Bit Wertebereich zufällig verteilt sind. Oder besser gesagt, jedes Hashen entspricht einem Zufallsexperiment.

Man nimmt nicht an, dass jeder 256 Bit Input einen separaten Hashwert ergibt.

Bei Betrachtung relativ „weniger“ Werte, wie in der Realität, sind beide Annahmen praktisch gleichwertig.

Da man Inputs beliebiger Länge hashen kann, gibt es durch die beschränkte Hash-Länge theoretisch natürlich unendlich viele Kollisionen.

5 „Gefällt mir“