[FYI] Bruce Schneier: SHA-1 Broken

Lesenswerte Artikel, Anleitungen und Diskussionen
User avatar
Joe User
Project Manager
Project Manager
Posts: 11578
Joined: 2003-02-27 01:00
Location: Hamburg

[FYI] Bruce Schneier: SHA-1 Broken

Post by Joe User » 2005-02-16 11:27

PayPal.Me/JoeUserFreeBSD Remote Installation
Wings for LifeWings for Life World Run

„If there’s more than one possible outcome of a job or task, and one
of those outcomes will result in disaster or an undesirable consequence,
then somebody will do it that way.“ -- Edward Aloysius Murphy Jr.

captaincrunch
Userprojekt
Userprojekt
Posts: 7225
Joined: 2002-10-09 14:30
Location: Dorsten

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by captaincrunch » 2005-02-16 13:59

Autsch. Das ist übel...

Ganz nebnbei: wieso ging das noch nicht die die Crypto-ML? ;)
DebianHowTo
echo "[q]sa[ln0=aln256%Pln256/snlbx]sb729901041524823122snlbxq"|dc

andreask2
RSAC
Posts: 701
Joined: 2004-01-27 14:16
Location: Aachen

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by andreask2 » 2005-02-16 16:00

Hi!

Was hat dass denn für konkrete Auswirkungen "für Rootserver-Betreiber"?

Abgesehen davon dass meist soweiso noch md5 eingesetzt wird, was wohl noch mehr Schwächen hat: http://www.doxpara.com/md5_someday.pdf , entsprechend noch deutlich schneller "zu entschlüsseln" ist.

Ich verwende md5 hauptsächlich in zwei Bereichen:

1. Gentoo's Portage verwendet md5 um Quelldateien zu verifizieren. Um hier Schaden anzurichten, müsste es ja jemand hinbekommen, schädlichen Quellcode in ein Archiv einzuschleusen, und den Quellcode dann so zu verändern, dass es dieselbe Prüfsumme ergibt. Das ist nach meinem Verständnis allerdings noch deutlich zu aufwändig, oder?

2. Speicherung von Hashwerten von Passwörtern. Wenn es jemand schafft, so einen MD5-Hash zu erspähen, kann er mit Hilfe von John & Co. mit überschaubarem Aufwand das Passwort ermitteln. Wenn man mal von 8 Zeichen ausgeht. Im Moment bin ich mir noch nichtmal so recht bewußt darüber, was der Sinn und Zweck dieses Verfahrens sein soll, im Prinzip geht das ja fast schon on die Richtung "security by obscurity", die Latte wird halt ein wenig höher gelegt als bei Klartext-Passwörtern. Oder übersehe ich hier irgendwas? Was wäre hierbei eine geeignete Alternative, um eben den Aufwand so deutlich zu erhöhen, dass es eben nicht mal eben möglich ist den Ursprungstext zu erraten? (mal abgesehen von ordentlich langen Passwörtern oder public-key verfahren, was bei HTTP-Login aber keine wirkliche Alternative darstellt...)

Soweit ich das verstehe funktionieren die von den Chinesen durchgeführten Angriffe wohl nur so gut, wenn man den ursprünglichen Text kennt, also stellt es besonders eine Gefahr für "1." dar. Bei "2." ist es ja "nur reines brute-force".

Was ist mit dem Public-Key Verfahren, bei SSH? Hat das Auswirkungen hierdrauf?

Grüße
Andreas

User avatar
Joe User
Project Manager
Project Manager
Posts: 11578
Joined: 2003-02-27 01:00
Location: Hamburg

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by Joe User » 2005-02-16 17:35

CaptainCrunch wrote:Autsch. Das ist übel...
Jupp, daher auch als Sticky gesetzt.
CaptainCrunch wrote:Ganz nebnbei: wieso ging das noch nicht die die Crypto-ML? ;)
Ich habe sie nicht abonniert und B.S. hat es erst heute nacht veröffentlicht ;)
PayPal.Me/JoeUserFreeBSD Remote Installation
Wings for LifeWings for Life World Run

„If there’s more than one possible outcome of a job or task, and one
of those outcomes will result in disaster or an undesirable consequence,
then somebody will do it that way.“ -- Edward Aloysius Murphy Jr.

Roger Wilco
Administrator
Administrator
Posts: 6001
Joined: 2004-05-23 12:53

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by Roger Wilco » 2005-02-16 19:13

andreask2 wrote:Wenn es jemand schafft, so einen MD5-Hash zu erspähen, kann er mit Hilfe von John & Co. mit überschaubarem Aufwand das Passwort ermitteln. Wenn man mal von 8 Zeichen ausgeht.
Nein. Du kannst nur eine Zeichenkette ermitteln, die den gleichen MD5-Hash erzeugt. Das ursprüngliche Passwort kann man so nicht wieder herstellen. Um dich dagegen abzusichern, könntest du z. B. 2 Hashes des Passworts, einmal MD5 und einmal SHA-1 (oder andere Verfahren), speichern und vergleichen. Die Wahrscheinlichkeit, dass zwei Hash-Funktionen bei verschiedenen Zeichenketten die gleichen Hash-Werte erzeugen sind sehr gering.

andreask2
RSAC
Posts: 701
Joined: 2004-01-27 14:16
Location: Aachen

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by andreask2 » 2005-02-16 19:48

Naja, ich bin nicht so der große Crypto-Experte ;-)

Aber soweit ich das verstehe gibt es in gibt es bei einem "Zeichensatz" von z.B. [0-1a-zA-Z_-] bei maximal 8 Zeichen 2^48 (64^8) Kombinations-Möglichkeiten.

Bei md5 gibt es dagegen 2^128 Möglichkeiten, also eine ganz andere Größenordung. in anbetracht der Tatsache dass bei solchen Hash-Algorithmen ähnliche Werte möglichst unterschiedliche Ergebnisse liefern sollen, gehe ich davon aus, dass wenn man einen Treffer findet, die Wahrscheinlichkeit dass es sich um das richtige Passwort handelt sehr hoch ist. Und wenn man den gesamten Zeichenraum durchprobiert hast hat man auf jeden Fall das richtige Passwort, wenn man Pech hat auch unrichtige Treffer, was aber wie gsagt in meinen Augen nicht sooo wahrscheinlich ist - und selbst wenn kann man dann immer noch die paar probieren.

captaincrunch
Userprojekt
Userprojekt
Posts: 7225
Joined: 2002-10-09 14:30
Location: Dorsten

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by captaincrunch » 2005-02-16 19:54

andreas: Du sprichst hier aber ausschließlich von Brute Force. Sofern der Algorithmus als solcher Schwachstellen hat, ist das aber meist erst gar nicht mehr nötig, sondern der Rechenweg an sich lässt sich überlisten.
DebianHowTo
echo "[q]sa[ln0=aln256%Pln256/snlbx]sb729901041524823122snlbxq"|dc

dodolin
RSAC
Posts: 4009
Joined: 2003-01-21 01:59
Location: Sinsheim/Karlsruhe

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by dodolin » 2005-02-16 20:10

Was hat dass denn für konkrete Auswirkungen "für Rootserver-Betreiber"?
Nun, zuerst müsste man mal schauen, welche Applikationen man überhaupt einsetzt, die SHA verwenden.

Letztendlich halte ich das ganze (aus praktischer Sicht) aber noch nicht für ganz so kritisch, denn: Es wurde ja lediglich herausgefunden, dass man in 2^69 Operationen eine Kollision bekommt, statt der bisher rechnerisch angenommenen 2^80 Operationen. Das sind zwar schon diverse Größenordnungen weniger, aber vermutlich immer noch recht (zu?) viele. Kommt halt darauf an, wieviel Zeit und Rechenpower der Angreifer hätte und ob er in der konkreten Applikation überhaupt so viele Fehlversuche machen dürfte.

Für die Theoretiker ist das natürlich schon eine schlagende Nachricht. Schließlich ging man bisher davon aus, dass man SHA nicht überlisten kann und weniger als die rechnerischen Operationen benötigt, um eine Kollision hervorzurufen. Und wer weiß, wenn man die Kollisionswahrscheinlichkeit erst mal heruntersetzen konnte (was man bisher ja ausschloss), vielleicht geht es ja noch besser?

User avatar
Joe User
Project Manager
Project Manager
Posts: 11578
Joined: 2003-02-27 01:00
Location: Hamburg

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by Joe User » 2005-02-16 20:33

Na ja, so theoretisch lesen sich weder Golems "Ã?bersezung" http://www.golem.de/0502/36355.html noch Schneiers Blog selbst...
PayPal.Me/JoeUserFreeBSD Remote Installation
Wings for LifeWings for Life World Run

„If there’s more than one possible outcome of a job or task, and one
of those outcomes will result in disaster or an undesirable consequence,
then somebody will do it that way.“ -- Edward Aloysius Murphy Jr.

dodolin
RSAC
Posts: 4009
Joined: 2003-01-21 01:59
Location: Sinsheim/Karlsruhe

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by dodolin » 2005-02-16 23:31

Dann lies vielleicht mal bei Heise:
Dabei sind die Ergebnisse noch relativ weit von gezielten Manipulationen an SHA-1-gesicherten Daten entfernt. Statt der 2^80 Operationen, die das Ausprobieren aller Angriffsmöglichkeiten gegen SHA-1 erfordert, gelingt es den Chinesen bereits mit 2^69 Operationen eine Kollision -- also zwei Datensätze mit gleichem Hash-Wert -- zu finden. So reduziert der Angriff den erforderlichen Aufwand um Größenordnungen. Und auch wenn noch kein praktikables Verfahren für Angriffe bekannt ist, sorgt dies für einige Aufregung in der Krypto-Gemeinde.
http://www.heise.de/newsticker/meldung/56428

andreask2
RSAC
Posts: 701
Joined: 2004-01-27 14:16
Location: Aachen

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by andreask2 » 2005-02-18 14:32

Noch ein paar Hintergründe: http://www.heise.de/security/artikel/56555/

dodolin
RSAC
Posts: 4009
Joined: 2003-01-21 01:59
Location: Sinsheim/Karlsruhe

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by dodolin » 2005-02-18 18:14

Jepp. Wollte den Link zu Heise-Security auch gerade posten, da er meine bisherige Einschätzung ja zu teilen scheint. :)

andreask2
RSAC
Posts: 701
Joined: 2004-01-27 14:16
Location: Aachen

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by andreask2 » 2005-02-19 21:53

dauer also nur gut 2 Tage wenn man das nötige Kleingeld hat: http://it.slashdot.org/article.pl?sid=0 ... 1&from=rss ;-)

User avatar
Joe User
Project Manager
Project Manager
Posts: 11578
Joined: 2003-02-27 01:00
Location: Hamburg

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by Joe User » 2005-02-20 11:53

38.000 US-Dollar ist kein Kleingeld, das ist eine Portokasse...
PayPal.Me/JoeUserFreeBSD Remote Installation
Wings for LifeWings for Life World Run

„If there’s more than one possible outcome of a job or task, and one
of those outcomes will result in disaster or an undesirable consequence,
then somebody will do it that way.“ -- Edward Aloysius Murphy Jr.

Roger Wilco
Administrator
Administrator
Posts: 6001
Joined: 2004-05-23 12:53

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by Roger Wilco » 2005-02-20 12:11

Joe User wrote:38.000 US-Dollar ist kein Kleingeld, das ist eine Portokasse...
$38M sind 38.000.000$ ;)
Immernoch Portokasse? Falls ja, bitte ich um eine kleine Spende. :twisted:

niemand
Posts: 142
Joined: 2003-12-12 18:36

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by niemand » 2005-02-20 19:38

Außerdem stimme ich dem ersten Kommentar zu:
The new SHA-1 break only affects very carefully constructed messages. This means that it is completely useless for an attacker impersonating an existing message, unless that message was purposely constructed to be attackable. The attack is only useful if the attacker creates both messages, and the attacker can choose the exact format of both messages.
Irgendwie ist das Ganze für mich eher "nice to know" als eine konkrete Bedrohung meiner Datensicherheit.

cu

andreask2
RSAC
Posts: 701
Joined: 2004-01-27 14:16
Location: Aachen

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by andreask2 » 2005-02-20 22:06

Sehe ich auch so.

Von der Theorie bis zu einem tatsächlich "sinnvollen" Angriff ist es noch ein großer Schritt - zudem bezieht sich die genannte Methode nur auf eine Kollision, das heißt man kann mit 35 Mio. auf der hohen Kante in 52 Stunden zwei gleiche SHA-1 Hashwerte ohne jegliche Bedeutung erzeugen (aber auch nur wenn man nicht vorher festlegt welcher Hashwert rauskommen soll). Brute-Force/Wörterbuch Attacken gegen gehashte Passwörter sind so oder so erheblich effizienter, und bestimmte Daten mit einer bestimmten Hashsumme mit schädlichen Daten mit derselben Hashsumme zu ersetzen ist wie ich das im Moment verstehe auch nach den neuen Erkenntnissen mit heutigen technischen Mitteln (und auch in den kommenden Jahren) nicht machbar.

[tom]
RSAC
Posts: 671
Joined: 2003-01-08 20:10
Location: Berlin

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by [tom] » 2005-02-21 10:12

andreask2 wrote:Aber soweit ich das verstehe gibt es in gibt es bei einem "Zeichensatz" von z.B. [0-1a-zA-Z_-] bei maximal 8 Zeichen 2^48 (64^8) Kombinations-Möglichkeiten.
Maximal 8 Zeichen heißt "bis zu". Es können aber auch 7, 6 oder 4 sein. Also muss man die Summenformel für endliche geometrische Reihen anwenden.

Um hier keine unnötigen Bildchen mit Formeln zu posten (und zu langweilen :) bedeutet das für diesen "Spezialfall":

Code: Select all

1 - a^(n+1)
------------- - 1
   1 - a
für alle a ungleich 1.

Für Dein Beispiel also (a = 64, n = 8):

Code: Select all

1 - 64^(8+1)
------------- - 1 = 285.942.833.483.840
   1 - 64
Man muss hier nur berücksichtigen, ob ein leeres Passwort erlaubt ist oder nicht - daher "Spezialfall". ;-)

Wenn es genau 8 Stellen wären, dann ist es einfach a^n, also 64^8 aus Deinem Beispiel.

[TOM]

User avatar
Joe User
Project Manager
Project Manager
Posts: 11578
Joined: 2003-02-27 01:00
Location: Hamburg

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by Joe User » 2005-02-21 17:22

PayPal.Me/JoeUserFreeBSD Remote Installation
Wings for LifeWings for Life World Run

„If there’s more than one possible outcome of a job or task, and one
of those outcomes will result in disaster or an undesirable consequence,
then somebody will do it that way.“ -- Edward Aloysius Murphy Jr.

andreask2
RSAC
Posts: 701
Joined: 2004-01-27 14:16
Location: Aachen

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by andreask2 » 2005-03-04 02:09

Nochwas zum Thema: "Forscher erzeugen unterschiedliche X.509-Zertifikate mit gleichem MD5-Hash" -> http://www.heise.de/newsticker/meldung/57038

dodolin
RSAC
Posts: 4009
Joined: 2003-01-21 01:59
Location: Sinsheim/Karlsruhe

Re: [FYI] Bruce Schneier: SHA-1 Broken

Post by dodolin » 2005-03-04 12:06

Der beschriebene Angriff ist derzeit aber nur praktikabel, wenn ein Angreifer in der Lage ist, sowohl Original und Fälschung selbst zu erstellen. Angriffe auf bereits bestehende Zertifikate (Pre-Image Attacks) sind bislang immer noch nicht praktisch durchführbar. Zertifikate, die mit SHA-1 gehashed wurden, sind ebenfalls nicht von diesen Angriffen betroffen.
Also keine Panik. :)