Debian-Installer: SHA1 Problem

Alles rund um sicherheitsrelevante Fragen und Probleme.
breakthewall
Beiträge: 507
Registriert: 30.12.2016 23:48:51

Debian-Installer: SHA1 Problem

Beitrag von breakthewall » 23.02.2017 18:34:35

Hallo

Mir viel heute zufällig ein Problem auf hinsichtlich des LUKS-Header-Hashes, der vom Debian-Installer gesetzt wurde. Nämlich SHA1, was seit heute offiziell als gebrochen gilt. Und das ist darum dubios, weil die Voreinstellung des cryptsetup, schon seit vielen Monaten SHA-256 ist. Wieso werden Standard-Vorgaben nicht übernommen und selbst gesetzt, zumal das im Debian-Installer nicht konfigurierbar ist? Das dürfte nicht sein. Auch wenn die Art der Nutzung unter LUKS/dm-crypt keine Sicherheitslücke bedeutet. Wäre wohl jemand so freundlich diese Sache im Bugtracker zu melden? Habe bislang keine Erfahrungen damit.

tobo
Beiträge: 1964
Registriert: 10.12.2008 10:51:41

Re: Debian-Installer: SHA1 Problem

Beitrag von tobo » 23.02.2017 18:44:52

Der gilt schon seit gut 10 Jahren "offiziell" als gebrochen. Heute wurde eine erste Kollision veröffentlicht.

uname
Beiträge: 12046
Registriert: 03.06.2008 09:33:02

Re: Debian-Installer: SHA1 Problem

Beitrag von uname » 23.02.2017 19:58:36

Meinst du deine Daten sind 6500 CPU-Jahre und nochmal 100 GPU-Jahre wert?

DeletedUserReAsG

Re: Debian-Installer: SHA1 Problem

Beitrag von DeletedUserReAsG » 23.02.2017 20:49:02

Da wurde doch „nur“ eine Kollision erzeugt? Das wäre im LUKS-Szenario wertlos. Dennoch ist die ursprüngliche Frage nicht von der Hand zu weisen, wenn‘s stimmt: dass der eigentliche Default mittlerweile einen anderen Algo vorgibt, und der Installer aus Gründen oder auch nicht auf SHA1 umstellt.

uname
Beiträge: 12046
Registriert: 03.06.2008 09:33:02

Re: Debian-Installer: SHA1 Problem

Beitrag von uname » 24.02.2017 08:53:50

Vielleicht einen Bug-Report schreiben.

Benutzeravatar
MSfree
Beiträge: 10686
Registriert: 25.09.2007 19:59:30

Re: Debian-Installer: SHA1 Problem

Beitrag von MSfree » 24.02.2017 09:20:16

tobo hat geschrieben:Der gilt schon seit gut 10 Jahren "offiziell" als gebrochen. Heute wurde eine erste Kollision veröffentlicht.
Naja, es liegt in der Natur der Dinge, daß ein Hashwert nicht eindeutig sein kann. Bei einem (fiktiven) 32Bit-Hash gäbe es halt nur rund 4 Milliarden unterschiedliche Hashes, so daß die Chance einer Kollision eins zu 4 milliarden ist.

Bie SHA-1 sollte die Wahrscheinlichkeit einer Kollision 1 zu 2^80 sein, es wurde aber gezeigt, daß es auf 1 zu 2^69 reduziert werden kann. Aber selbst 2^69 ist immer noch eine gigantische Zahl, die eben 6500 CPU-Jahre plus 100-GPU-Jahre zum Berechnen einer Kollision benötigt, was mit 57 Millionen CPU-Kernen plus 880000 Graphikkarte rund 1 Stunde dauern würde, sofern das linear skalierbar wäre. (kann man bei AWS so viel CPUs/GPUs mieten?)

Wollte man z.B. gezielt Schadsoftware bei Debian einschleusen, müßte man ein populäres Softwarepaket wie SSH nehmen, dort Schadsoftware einbringen. Die Schadsoftware müßte aber so beschaffen sein, daß sie die Größe des DEB-Paketes nicht ändert und so, daß sich der gleiche Hashwert ergibt, den das originale SSH-Paket hatte.

Im Grunde kann man das auch mit SHA-256 oder SHA-512 erreichen, es dauert halt nur länger, wird also teurer für den Angreifer. Solange es genug andere Schwachstellen im Betriebssystem gibt, die viel leichter auszunutzen sind wie eine SHA-1 Kollision zu erzeugen, wird man eher die nutzen.

Für den Zweck der Paketsignierung ist SHA-1 im Moment bestimmt noch nicht so unsicher geworden, daß man in Panik verfallen müßte und den ganzen Hash-Mechanismus austauschen müßte.

uname
Beiträge: 12046
Registriert: 03.06.2008 09:33:02

Re: Debian-Installer: SHA1 Problem

Beitrag von uname » 24.02.2017 11:06:49

Interessant in dem Zusammenhang ist vielleicht noch das Geburtstagsparadoxon [1]. Es ist "dabei viel einfacher, zwei zufällige Texte zu finden, die denselben Prüfwert haben, als zu einem vorgegebenen Text einen weiteren zu finden, der denselben Prüfwert aufweist".

Aber ich denke das war bei der Wahrscheinlichkeit schon eingerechnet. Umgekehrt wäre es viel einfacher beliebige Dateien zu finden, die dieselbe Prüfsumme haben.

[1] https://de.wikipedia.org/wiki/Geburtstagsparadoxon

dufty2
Beiträge: 1709
Registriert: 22.12.2013 16:41:16

Re: Debian-Installer: SHA1 Problem

Beitrag von dufty2 » 24.02.2017 18:58:57

Sorry, aber da bin ich ganz anderer Meinung.
Wenn man sich das mal wirklich anschaut, da kommt einem das kalte (Security-)Grausen:

Code: Alles auswählen

$ wget https://shattered.it/static/shattered-{1,2}.pdf
$ ls -l
422435 Feb 22 23:42 shattered-1.pdf
422435 Feb 22 23:42 shattered-2.pdf
$ sha1sum shattered-{1,2}.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf
Und was sie geändert haben, ist quasi nur die Hintergrundfarbe (zumindest auf den ersten Blick).
Es handelt sich also NICHT um zwei Dateien mit gleicher Blocksize und gleichem Hash, aber völlig unterschiedlichen Inhalt. Das ist eben NICHT der Fall (zumindest optisch).

DeletedUserReAsG

Re: Debian-Installer: SHA1 Problem

Beitrag von DeletedUserReAsG » 24.02.2017 19:10:01

Es handelt sich also NICHT um zwei Dateien mit gleicher Blocksize und gleichem Hash, aber völlig unterschiedlichen Inhalt. Das ist eben NICHT der Fall (zumindest optisch).
Die Nutzdaten dieses PDFs mögen bei 40kB (grob geschätzt) liegen. Bleiben 90% Daten, die man so aufeinander abstimmen kann, dass es kollidiert. Ich behaupte: mit einer vorgegebenen Datei ohne Datenmüll, nur mit den Nutzdaten, hätten sie’s nicht geschafft, eine zweite Datei mit gleichem Hash zu erstellen, die sich überhaupt im PDF-Viewer öffnen lässt. Und für das hier betrachtete Szenario mit den Headern ist’s eh nicht relevant. Was nicht heißen soll, dass man es gutfinden müsse – nur eben, dass man nicht gleich in Panik ausbrechen sollte.

dufty2
Beiträge: 1709
Registriert: 22.12.2013 16:41:16

Re: Debian-Installer: SHA1 Problem

Beitrag von dufty2 » 24.02.2017 19:15:31

Grad' erst entdeckt, ein Easteregg ;)

Code: Alles auswählen

$ strings shattered-1.pdf | head -5 | tail -1
$SHA-1 is dead!!!!!
Schon ziemlich beeindruckend:

Code: Alles auswählen

$ strings shattered-1.pdf > s1
$ strings shattered-2.pdf > s2
$ wc -l s{1,2}
 4422 s1
 4422 s2
$ diff s{1,2}
7c7
< x,v!V`
---
> x0Z!Vda0
$

tobo
Beiträge: 1964
Registriert: 10.12.2008 10:51:41

Re: Debian-Installer: SHA1 Problem

Beitrag von tobo » 24.02.2017 19:53:02

MSfree hat geschrieben:Für den Zweck der Paketsignierung ist SHA-1 im Moment bestimmt noch nicht so unsicher geworden, daß man in Panik verfallen müßte und den ganzen Hash-Mechanismus austauschen müßte.
Im Grunde genommen hast du natürlich recht - kein Mensch muss deswegen "jetzt" in Panik verfallen. Grundsätzlich wird man das aber trotzdem umstellen - wieso auch nicht. Man sitzt da auf 2 Implementierungen rum, eine ist sicher und eine ist unsicher. Also verwende ich die sichere. Für die Entscheidung zur Umstellung spielt es überhaupt keine Rolle, wieviele CPU- und GPU-Jahre der Angriff kostet.
https://wiki.debian.org/SHA-1

DeletedUserReAsG

Re: Debian-Installer: SHA1 Problem

Beitrag von DeletedUserReAsG » 24.02.2017 20:11:43

Schon ziemlich beeindruckend:
Naja, eigentlich:

Code: Alles auswählen

$ xxd shattered-1.pdf > s1.hex
$ xxd shattered-2.pdf > s2.hex

$ diff s{1,2}.hex
13,20c13,20
< 000000c0: 7346 dc91 66b6 7e11 8f02 9ab6 21b2 560f  sF..f.~.....!.V.
< 000000d0: f9ca 67cc a8c7 f85b a84c 7903 0c2b 3de2  ..g....[.Ly..+=.
< 000000e0: 18f8 6db3 a909 01d5 df45 c14f 26fe dfb3  ..m......E.O&...
< 000000f0: dc38 e96a c22f e7bd 728f 0e45 bce0 46d2  .8.j./..r..E..F.
< 00000100: 3c57 0feb 1413 98bb 552e f5a0 a82b e331  <W......U....+.1
< 00000110: fea4 8037 b8b5 d71f 0e33 2edf 93ac 3500  ...7.....3....5.
< 00000120: eb4d dc0d ecc1 a864 790c 782c 7621 5660  .M.....dy.x,v!V`
< 00000130: dd30 9791 d06b d0af 3f98 cda4 bc46 29b1  .0...k..?....F).
---
> 000000c0: 7f46 dc93 a6b6 7e01 3b02 9aaa 1db2 560b  .F....~.;.....V.
> 000000d0: 45ca 67d6 88c7 f84b 8c4c 791f e02b 3df6  E.g....K.Ly..+=.
> 000000e0: 14f8 6db1 6909 01c5 6b45 c153 0afe dfb7  ..m.i...kE.S....
> 000000f0: 6038 e972 722f e7ad 728f 0e49 04e0 46c2  `8.rr/..r..I..F.
> 00000100: 3057 0fe9 d413 98ab e12e f5bc 942b e335  0W...........+.5
> 00000110: 42a4 802d 98b5 d70f 2a33 2ec3 7fac 3514  B..-....*3....5.
> 00000120: e74d dc0f 2cc1 a874 cd0c 7830 5a21 5664  .M..,..t..x0Z!Vd
> 00000130: 6130 9789 606b d0bf 3f98 cda8 0446 29a1  a0..`k..?....F).
Ist trotzdem erheblich weniger, als ich angenommen hatte. Die Frage ist, wieviel von den 413kB denn nun Fülldaten sind, um die Kollision zu ermöglichen. Und ob‘s bei einer gegebenen Datei ebenso möglich wäre.

dufty2
Beiträge: 1709
Registriert: 22.12.2013 16:41:16

Re: Debian-Installer: SHA1 Problem

Beitrag von dufty2 » 24.02.2017 20:42:59

"Fülldaten" braucht es wohl nicht so viel:

Code: Alles auswählen

$ wget arw.me/f/{1,2}.html
$ sha1sum {1,2}.html
ba97502d759d58f91ed212d7c981e0cfdfb70eef  1.html
ba97502d759d58f91ed212d7c981e0cfdfb70eef  2.html
$ file *.html
1.html: PDF document, version 1.3
2.html: PDF document, version 1.3
$ ls -l *.html
752 Feb 23 22:48 1.html
752 Feb 23 22:48 2.html
Aber diese "PDF"-Dateien lassen sich nicht mehr öffnen.

wanne
Moderator
Beiträge: 7448
Registriert: 24.05.2010 12:39:42

Re: Debian-Installer: SHA1 Problem

Beitrag von wanne » 27.02.2017 13:27:16

Also bitte hier nichts durcheinander werfen!
SHA-1 ist immer noch aller erste Wahl als Paswort-Hash und überall sonst, wo Kollisionen keine Rolle spielen.
Er hat da noch immer die volle stärke von 160Bit, und ist nicht im geringsten angreifbar noch gibt es irgend welche Ansätze, wie man ihn angreifen könnte.

Für Hashes gibt es prinzipiell ein paar verschiedene Anforderungen. (Von einfach zu erfüllen nach schwerer.)
  • Zufällig ergeben sich selten 2 Kollisionen. (Gleichverteilung auch bei nicht gleichverteilten inputs.) (Das gilt für praktisch alle Hashes z.B. auf für CRC. Der wird bis heute massiv zur Fehlerkorrektur bei Übertragungen eingesetzt. In MACs oder passwort-hashes hat der aber nichts zu suchen. (Hauptschwäche von WEP) )
  • Es ist schwer möglich einen Klartext zu einem bekannten Hash zu finden. (preimage) Das ist wichtig für Passwörter. aber md5 und sha-1 sind hier noch problemlos verwendbar. Aber eben nicht CRC.
  • Es lassen schwer möglich zu einem bekannten Klartext einen zweiten mit gleichem Hash zu finden. (Second Preimage) Das ist wichtig für MACs und Signatueren. Auch das ist für SHA-1 noch niemandem gelungen. MD5 sind aber wohl zumindest theoretisch Angriffe bekannt. Ausreichend ist das nicht, sobald man Daten anderer Signiert. (Wie das z.B. bei Ausweisen oder x509 der Fall ist, wo die CA jemand anderen bestätigt.) Mail-Signaturen mit SHA-1 sind prinzipiell noch sicher. – Bis man auf die Idee kommt harmlos klingende Mails weiterzuleiten. (Und zu signieren.)
  • Kollisionsangriffe: Wie oben allerdings ist der Klartext nicht bekannt sondern frei wählbar.
    Das klingt nicht sonderlich sonderlich unterschiedlich ist es am ende aber doch. Es ist meist um Zig Größenordnungen einfacher einfacher einen ein harmloses und ein "böses" Zertifikat mit dem gleichen Hash zu erstellen als zu einem fest vorgegebenen harmlosen ein "böses". (Und das geht bei SHA oder MD5 sogar noch weit über das Geburtstagsparadoxon hinaus.) Deswegen erkannte der Firefox SHA-1 Zertifikate, die aus der Zeit vor dem bekannt werden der Angriffe stammten noch an, neuere nicht mehr.
Der Angriff bezieht sich im Moment ausschließlich auf Kollisionen. Also den letzten Punkt. Es ist auch absolut unwahrscheinlich, dass er je die oberen beiden Punkte beeinflussen wird.
Wer also nur einen der oberen Punkte braucht ist mir anderen Hashes noch immer gut beraten die alten besser erprobten zu nutzen. LDAP spezifiziert deswegen z.B. bis heute ausschließlich SHA-1.

Signaturen sind dagegen etwas völlig anderes. Da der Sourcecode von andern Leuten stammt, müssen sie Punkt 4 Widerstehen. Und entsprechen nutzt man für sowas keinen SHA-1. Auch vor 10 Jahren nicht. Auch wenn der Angriff im Moment noch vergleichsweise lange dauert.

Habe aber gerade mal geguckt. Bei mir sind die Paketsignaturen alle mit SHA-256:
pgpdump debian.tu-bs.de_debian_dists_jessie_Release.gpg

Code: Alles auswählen

Old: Signature Packet(tag 2)(540 bytes)
        Ver 4 - new
        Sig type - Signature of a binary document(0x00).
        Pub alg - RSA Encrypt or Sign(pub 1)
        Hash alg - SHA256(hash 8)
        Hashed Sub: signature creation time(sub 2)(4 bytes)
                Time - Sat Jan 14 12:04:51 CET 2017
        Sub: issuer key ID(sub 16)(8 bytes)
                Key ID - 0x8B48AD6246925553
        Hash left 2 bytes - 3a 3b 
        RSA m^d mod n(4092 bits) - ...
                -> PKCS-1
rot: Moderator wanne spricht, default: User wanne spricht.

Benutzeravatar
schorsch_76
Beiträge: 2535
Registriert: 06.11.2007 16:00:42
Lizenz eigener Beiträge: MIT Lizenz

Re: Debian-Installer: SHA1 Problem

Beitrag von schorsch_76 » 27.02.2017 14:16:24

wanne hat geschrieben:Also bitte hier nichts durcheinander werfen!
SHA-1 ist immer noch aller erste Wahl als Paswort-Hash und überall sonst, wo Kollisionen keine Rolle spielen.
Du hast verstanden was du da sagst???? 8O

wanne
Moderator
Beiträge: 7448
Registriert: 24.05.2010 12:39:42

Re: Debian-Installer: SHA1 Problem

Beitrag von wanne » 27.02.2017 14:44:09

schorsch_76 hat geschrieben:Du hast verstanden was du da sagst????
Ja. Genau Es ist für passwort Hashes vollig irrelevant ob man Kollisionen erzeugen kann oder nicht.
Ein Hash kann kollissionresisten sein, und trotzdem kein guter Passwort-Hash und umgekehrt.

Hier ein Beispiel in jede Richtung:
  • Code: Alles auswählen

    echo $1
    Die Identität: Die Funktion gibt einfach das Passwort zurück: – Absolut kollisonsresistent. Zwei unterschiedliche Passwörter bleiben unterschiedlich, wenn man sie nicht verändert. Aber ein scheiß für Passworter. Man kann sie einfach ablesen. (Gleiches gilt für AES und jedes andere symmetrische Verschlüsselungsverfahren.)
  • Code: Alles auswählen

    printf %32s $1 | sha1sum
    Auffüllen des Passworts mit Leerzeichen auf eine gewisse Länge und dann ein gutes Hash-Verfahren. Früher absolut üblich, wenn z.B. Verfahren nur mit festen vielfachen von 8 Zeichen umgehen konnten. Kollisionen sind jetzt total einfach zu erzeugen: "Auto" und " Auto" geben den gleichen Hash. Trotzdem ist es ein sicheres Hashverfahren.
    Beispiel:

    Code: Alles auswählen

    printf %32s "Auto" | sha1sum            
    fc692abaaa6520c6f2d313183abb2b608e634edc
    printf %32s "        Auto" | sha1sum                                            
    fc692abaaa6520c6f2d313183abb2b608e634edc
    
rot: Moderator wanne spricht, default: User wanne spricht.

Benutzeravatar
MSfree
Beiträge: 10686
Registriert: 25.09.2007 19:59:30

Re: Debian-Installer: SHA1 Problem

Beitrag von MSfree » 27.02.2017 14:55:47

wanne hat geschrieben:Es ist für passwort Hashes vollig irrelevant ob man Kollisionen erzeugen kann oder nicht.
Ich hoffe, du weißt, was du da gerade für einen unüberlegten Satz von dir gegeben hast 8O

Wenn mein Pasßwort SuperGeheim wäre und ich ein Paßwort erstellen kann, daß den gleichen Hash wie SuperGeheim hat und z.B. EasyAccess lautet, kann ich mich mit Benutzername und EasyAccess statt SuperGeheim einloggen.

Es spielt eine geradezu essentielle Rolle, ob man Hash-Collisions leicht herstellen kann. Daß es für alle anderen Hash-Verfahren auch zwagsläufig Kollisionen geben muß, ist auch klar, das erzeugen einer Kollision muß aber möglichst genauso aufwändig sein wie das Ermitteln eines Paßwortes per brute Force.

wanne
Moderator
Beiträge: 7448
Registriert: 24.05.2010 12:39:42

Re: Debian-Installer: SHA1 Problem

Beitrag von wanne » 27.02.2017 15:18:58

@all bitte meinen Post durchlesen und verstehen bevor ihr antwortet.
MSfree hat geschrieben:Wenn mein Pasßwort SuperGeheim wäre und ich ein Paßwort erstellen kann, daß den gleichen Hash wie SuperGeheim hat und z.B. EasyAccess lautet, kann ich mich mit Benutzername und EasyAccess statt SuperGeheim einloggen.
Das wäre ein Second Preimage-Angriff. Um den auszuführen musst du vorher wissen, dass das Passwort superGeheim war.
Jetzt gibt es zwei Möglichkeiten:
  1. Du weißt schon dass das Passwort superGeheim war: Es ist völlig egal ob du dich auch noch mit einem anderen Passwort mit dem gleichen Hash erzeugen kannst. Du kannst dich ja auch mit dem echten Passwort anmelden.
  2. Du weißt noch nicht, dass das Passwort superGeheim war, sondern kennst lediglich den Hash. Dann kannst du auch EasyAccess nicht finden, weil du ja das Passwort wissen müsstest um auf EasyAccess zu kommen.

Einfach mal am Beispiel von Oben:

Code: Alles auswählen

printf %32s $1 | sha1sum
Ich habe dir oben gezeigt, dass es ohne weiteres möglich ist, zwei passwörter zu generieren, die den geilchen Hash (fc692abaaa6520c6f2d313183abb2b608e634edc) ergeben.
Es ist also einfach Kollisionen zu erzeugen.

Jetzt deine Aufgabe:
Ich habe ein Passwort, (beziehungsweise einige Passwörter) dass den Hash ergibt:

Code: Alles auswählen

c1970ddd8ea392778daa5556613d88914a9a9752
Versuche jetzt mal das passende Passwort dazu zu finden. 500€ wenn du's schaffst, bevor ich's veröffentliche.

Einfach mal ernsthaft ausprobieren und du wirst den Unterschied zwischen einem Preimage-Angriff und einem Second-Preimage Angriff ganz schnell merken.

Und ich bitte jeden anderen der hier recht schnell und unüberlegt antwortet das ebenfalls zu versuchen.
rot: Moderator wanne spricht, default: User wanne spricht.

Benutzeravatar
MSfree
Beiträge: 10686
Registriert: 25.09.2007 19:59:30

Re: Debian-Installer: SHA1 Problem

Beitrag von MSfree » 27.02.2017 15:39:26

wanne hat geschrieben:@all bitte meinen Post durchlesen und verstehen bevor ihr antwortet.
Unterstell mir hier nichts!

Ich denke, die Unwissenheit liegt auf deiner Seite. :wink:
[*]Du weißt noch nicht, dass das Passwort superGeheim war, sondern kennst lediglich den Hash. Dann kannst du auch EasyAccess nicht finden, weil du ja das Passwort wissen müsstest um auf EasyAccess zu kommen.[/list]
Der Witz ist, daß ich das nicht wissen muß. Per brute Force kann ich solange Zeichenkombinationen durchprobieren, bis ich entweder SuperGeheim oder EasyAccess finde, was dann schon nur noch der halbe Suchaufwand wäre. Und, je mehr Kollisionen sich erzeugen ließen, desto mehr gültige Paßwörter für den selben Hash könnte man generieren, was Brute Force Attacken dann immer einfacher werden läßt.

Und jetzt denk nochmal darüber nach, ob es wirklich so völlig egal ist, ob man für Hashes Paßwortpseudonyme generieren kann.
Und ich bitte jeden anderen der hier recht schnell und unüberlegt antwortet das ebenfalls zu versuchen
Und ich halte es für ganz schlechten Stil, erst Recht von einem Moderator, anderen zu versuchen, das Maul zu verbieten.

wanne
Moderator
Beiträge: 7448
Registriert: 24.05.2010 12:39:42

Re: Debian-Installer: SHA1 Problem

Beitrag von wanne » 27.02.2017 16:02:48

MSfree hat geschrieben:Und, je mehr Kollisionen sich erzeugen ließen, desto mehr gültige Paßwörter für den selben Hash könnte man generieren, was Brute Force Attacken dann immer einfacher werden läßt.
Um das mal einzuordnen:
Wenn Google den vollen Angriff der 2⁶⁹ versuche braucht in einer Millisekunde (Das ist deutlich schneller als ein dein 200Hz Bildchirm die Bilder bewegt) durchführen könnte.
Bräuchten Google aufgrund der von dir genannten Eigenschaft für SHA-1 4159074 mal so lange, wie das Universum bis jetzt existiert.
Noch Fragen ob das irgend wie den Praktischen Einsatz von SHA-1 beeinträchtigt?
Und vor allem sind deine Passwörter wirklich entsprechend stark, als dass sie dem mit einem anderen Hashverfahren standhalten würden?

Oder allgemeiner:
Für alle Hashes gilt: Sie haben konstante Länge. => Es gibt immer unendlich viele Kollisionen.
Die frage ist wie schnell man die Findet. I Optimalfall ist das für einen 160Bit langen Hash halt im Schnitt nach 2¹⁵⁹ versuchen der Fall. (besser geht nicht, weil einem ja irgend wann die unterschiedlichen hashes ausgehen.)
Da sieht es ist im Moment nicht schlechter aus für SHA-1.
rot: Moderator wanne spricht, default: User wanne spricht.

dufty2
Beiträge: 1709
Registriert: 22.12.2013 16:41:16

Re: Debian-Installer: SHA1 Problem

Beitrag von dufty2 » 27.02.2017 17:04:52

wanne hat geschrieben:Kollisionen sind jetzt total einfach zu erzeugen: "Auto" und " Auto" geben den gleichen Hash.
Das ist natürlich Quark. 'printf %32s "Auto"' und 'printf %32s " Auto"' erzeugen den ein- und denselben String und somit trivialerweise den gleichen Hash. Da aber der Input (für die Hashfunktion) jedesmal der gleiche ist, kann man auch nicht von einer Kollision sprechen.
wanne hat geschrieben: Die frage ist wie schnell man die Findet. I Optimalfall ist das für einen 160Bit langen Hash halt im Schnitt nach 2¹⁵⁹ versuchen der Fall. (besser geht nicht, weil einem ja irgend wann die unterschiedlichen hashes ausgehen.)
Aufgrund des Geburtstagsparadoxon findet man Hashkollisionen nicht mit 1/2, sondern mit der Wurzel.
Es sind jetzt nicht 19 sondern 23 Tage für SQRT(365 Tage), weils noch irgendeinen konstanten Faktor (den ich vergessen habe ;) ) gibt.
Somit benötigt man (circa) 2**80 bei 160 Bit. SHA-1 ist aber schlechter: 2**61 (oder so in der Gegend).

Benutzeravatar
schorsch_76
Beiträge: 2535
Registriert: 06.11.2007 16:00:42
Lizenz eigener Beiträge: MIT Lizenz

Re: Debian-Installer: SHA1 Problem

Beitrag von schorsch_76 » 27.02.2017 18:48:31

wanne hat geschrieben: Und ich bitte jeden anderen der hier recht schnell und unüberlegt antwortet das ebenfalls zu versuchen.
Na dann zitieren wir jemanden der sich damit auskennt:

https://www.schneier.com/blog/archives/ ... start.html
Bruce Schneier hat geschrieben: Especially note this bit: "Freestart collisions, like the one presented here, do not directly imply a collision for SHA-1. However, this work is an important milestone towards an actual SHA-1 collision and it further shows how graphics cards can be used very efficiently for these kind of attacks." In other words: don't panic, but prepare for a future panic.

This is not that unexpected. We've long known that SHA-1 is broken, at least theoretically. All the major browsers are planning to stop accepting SHA-1 signatures by 2017. Microsoft is retiring it on that same schedule. What's news is that our previous estimates may be too conservative.
Man beachte, das war 10/2015. Jetzt hat google die sha1 Kollision geliefert.
Bruce Schneier hat geschrieben: SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.
https://www.schneier.com/blog/archives/ ... roken.html

wanne
Moderator
Beiträge: 7448
Registriert: 24.05.2010 12:39:42

Re: Debian-Installer: SHA1 Problem

Beitrag von wanne » 27.02.2017 19:27:45

Der wichtige Teil steckt da:
All the major browsers are planning to stop accepting SHA-1 signatures by 2017.
Es geht um Signaturen. Zu diesem Zeitpunkt war SHA-1 sogar der einzige Hash, den der FF als MAC unterstützte. Und der FF will den da auch nicht rauswerfen. (Obwohl ich das auch da durchaus sinnvoll fände.) Auch da wird wenn man es gut anstellt lediglich ein Kollisionsangriff benötigt. (Nur da halt in Echtzeit.)
Für das Masterpasswort nutzt Firefox noch immer einen einfachen SHA-1.
Also 3DES(SHA-1(salt,masterpw),sql-light-value); Keine PBKDF2!
3DES hat btw. ein stärke von 2⁸⁰.
Also eher weg von dem Ding.
dufty2 hat geschrieben:Das ist natürlich Quark. 'printf %32s "Auto"' und 'printf %32s " Auto"' erzeugen den ein- und denselben String
Nein. Genau das ist ein typischer Ansatz um Kollisionen zu erzeugen: Man sorgt dafür, dass irgend ein zwischenzustand gleich ist. Es war ja auch Absicht, dass es offensichtlich ist, wie ich das gebaut habe.
Für das Widerlegen ist es völlig egal wie Primitiv das Beispiel ist. Ich habe ein Beispiel gebraucht für das das gilt. PUNKT.
Ich kann dir auch gerne irgend einen hash basteln, bei dem das nicht mehr gar so offensichtlich ist. Nur traue ich mir halt nicht zu einen Preimagefreien zu bauen. Da haben sich halt schon größere dran vertan. Deswegen habe ich halt den SHA-1 von dem das bekannt ist, dahinter gehängt.
rot: Moderator wanne spricht, default: User wanne spricht.

Benutzeravatar
schorsch_76
Beiträge: 2535
Registriert: 06.11.2007 16:00:42
Lizenz eigener Beiträge: MIT Lizenz

Re: Debian-Installer: SHA1 Problem

Beitrag von schorsch_76 » 27.02.2017 19:39:53

Es ist nicht die Implementierung gebrochen. Es ist der Algorithmus gebrochen und damit alles was davon abstammt.

Nur weil im FF SHA1 damals das einzige war, bedeutet das nicht, das es gut war. Jetzt ist es vorbei mit SHA1.
Bruce Schneier hat geschrieben: SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.
https://www.schneier.com/blog/archives/ ... roken.html

Spätestens jetzt muss man davon Abschied nehmen. Siehe damals MD5. Man kann jetzt nicht mehr sagen, das SHA1 sicher ist für Passwörter. Das was damals mit MD5 passiert ist, wird auch mit SHA1 passieren.
Wikipedia über MD5 hat geschrieben: Inzwischen sind die Kollisionsangriffe so weit fortgeschritten, dass eine weitere Nutzung von MD5, insbesondere in solchen Szenarien, in denen der Nutzer nicht die zu signierenden Dateien komplett kontrolliert, abzulehnen ist. Ein 2009 durchgeführter Test des Computermagazins c’t unter Verwendung von GPGPU ermöglicht es einem etwa ein Jahr alten Highend-Spiele-PC mit zwei Nvidia GeForce 9800 GX2 (insgesamt vier Grafikprozessoren), in knapp 35 Minuten eine Kollision zu finden.[8]
https://de.wikipedia.org/wiki/Message-D ... lgorithm_5

dufty2
Beiträge: 1709
Registriert: 22.12.2013 16:41:16

Re: Debian-Installer: SHA1 Problem

Beitrag von dufty2 » 27.02.2017 19:55:19

wanne hat geschrieben:
dufty2 hat geschrieben:Das ist natürlich Quark. 'printf %32s "Auto"' und 'printf %32s " Auto"' erzeugen den ein- und denselben String
Nein. Genau das ist ein typischer Ansatz um Kollisionen zu erzeugen: Man sorgt dafür, dass irgend ein zwischenzustand gleich ist. Es war ja auch Absicht, dass es offensichtlich ist, wie ich das gebaut habe.
Für das Widerlegen ist es völlig egal wie Primitiv das Beispiel ist. Ich habe ein Beispiel gebraucht für das das gilt. PUNKT.
Sorry, das ist Quark:
In der Kryptographie spricht man _dann_ von einer Kollision, wenn zwei _verschiedene_ Inputs den gleichen Output sprich Hash liefern.
PUNKT.

Für die Interessierten ist hier das paper zum Nachlesen:
https://shattered.it/static/shattered.pdf

Antworten