[HaBo]

rhopimy

Anzeige

servus!

hab mal ne frage...
kann man einen des-schlüssel herausfinden wenn man den plain- und ciphertext hat?
zb.:
cipher: AB 31 41 DA 90 38 0E EA
plain: 00 00 00 00 00 00 00 00

danke schon mal...

rhopimy :)

menace

ja, mit vollständiger Schlüsselsuche, optimiert durch Statistik.
An der Ruhr-Uni Bochum gibt es ein Gerät, dass einen DES Schlüssel für sowas in 8 Tagen knackt.

rhopimy

servus!

also kann man das nur durch probieren rausfinden?
mal ne frage zu des:
kann es sein, dass wenn man z.b. 00 00 00 00 00 00 00 00 mit zwei verschieden schlüsseln codiet der gleiche ciphertext rauskommt??
wenn nicht, dann gibt es ja für jeden schlüssel einen individuellen ciphertext(z.b. von 00 00 00 00 00 00 00 00). also muesste es doch irgendwie möglich sein jeden ciphertext(z.b von 00 00 00 00 00 00 00 00) den dazugehörigen schlüssel zuzuordnen.
oder???


mfg rhopimy

Elderan

Hallo,
Wieso sollte das nicht möglich sein?


Sofern man von einem festen Klartext ausgeht, z.B. lauter Nullen, dann ist das durchaus möglich.

Allerdings bei 2^56 Schlüssel mit je 64 Bit (Block) macht das 5 × 10^17 Byte, oder 536 870 912 Gigabyte.
Viel Spaß beim abspeichern.

Und dies nur für 1 möglichen Klartext, also für lauter Nullen.
Wenn der abgefangene Text den Block nicht enthält, kommt man auch wieder nicht an den Key.

rhopimy

also geht das problem definitiv nicht über die mathematik zu lösen??

menace

Weil dann die Bijektivität der Chiffre nicht gegeben ist bei DES.. Ich bin erstaunt, Elderan, von dir so eine Frage zu hören.


Theoretisch ja. nennt sich key-related-attacks...
praktisch stösst auch die mathematik irgendwann an eine komplexitätsgrenze

Elderan

Hallo,
menace, du musst genau darauf achten, was rhopimy wissen wollte.
Die bijektivität ist natürlich gewährleistet (1 Klartextblock gehört zu 1 Geheimtextblock bei festem Key), aber das wollte rhopimy gar nicht wissen.

Hier fragt er, ob folgender Fall möglich ist (wo ist die Latex extension im Board?)
Ek(x) = Ek'(x)
Mit k != k'

(Ek(x) heißt Verschlüsselung von x mit dem Schlüssel k)

Bei DES ist es etwas komisch mit Blocklänge zu Schlüssellänge, bei AES-256 (oder Twofish-256) wird es aber klar.
Es gibt 2^128 mögliche Eingaben und 2^128 mögliche Ausgaben.
Allerdings gibt es 2^256 mögliche Schlüssel!

D.h., wenn ich die Eingabe 00 00 00... mit jedem jedem existierenden Key (2^256) verschlüssel, mit der Vorgabe, dass kein Ciphertext doppelt vorkommen darf, dann müsste ich 2^256 verschiedene Ausgaben/Ciphertexte erhalten.
Da aber ein Block die Länge 128 Bit hat (haben kann), und ich 2^256 Kombinationen nicht durch 128 Bit darstellen kann, heißt dies logischer weise, dass die Eingabe (der Block) 00 00 00... mit zwei verschiedenen Schlüsseln den gleichen Ciphertext haben muss.

Bei der Kombinationen von 128 Bit Schlüssellänge und 256 Bit Keylänge heißt dies sogar, dass der Block 00 00 00... mit ca. 2^128 verschiedenen Schlüsseln die gleiche Ausgabe hat.


Bei DES ist zwar die Schlüssellänge kürzer als die Blocklänge, dennoch ist es sehr sehr wahrscheinlich, dass der Block 00 00 00 mit zwei Unterschiedlichen Keys den gleichen Geheimtext ergeben.

PS: Ich denke du hast einfach die Frage nicht genau gelesen.


PPS: Symmetrische Algorithmen haben nur bedingt etwas mit Mathematik zu tun. Es werden eher chaotische Strukturen verwendet um das Knacken zu erschweren.
AES wird z.B. Kritisiert, weil es mathematisch zu "schön" ist.

Datenschleuder

menace

Ok, generell hast du recht, da stimme ich dir zu. asche auf mein haupt.
aber gerade bei DES ist der eine (imo für mich glückliche ausnahmefall, wo das nicht so ist.
Ich hab ja in diesem Fall (eigentlich nicht mal) 64 Bit Schlüssellänge und 64 Bit Blocklänge. Womit wir 2^64 Symbole haben für Chiffre/Klartext/Schlüsselraum, und damit genau die Festlegung auf einen Schlüssel, wenn Klar- und ChiffreSymbol gegeben sind, genau wie beim OTP..

Auch symmetrische Algorithmen haben etwas mit Mathematik zu tun. Auch wenn AES als zu "schön" kritisiert wird, er ist erfolgreich und gut begriffen. Auch fasst die Zahlentheorie immer mehr Fuss in der Kryptographie. Von Statistik gar nicht zu reden

Elderan

Hallo,
Wie gesagt, DES stellt da eine Ausnahme dar.
Allerdings ist selbst dort es äußerst Wahrscheinlich, dass 00 00.. mit zwei verschiedenen Keys den gleichen Ciphertext ergeben.

DES wurde ja nicht so entwickelt, dass alle Cipher-Combinationen entstehen, wenn man 00... mit allen Keys durchprobiert, sondern moderne Algorithmen verhalten sich eher wie (Pseudo)-Zufallsgeneratoren.

D.h. hier kommt das Geburtstags-Paradoxen wieder zum tragen.
Man kann den DES Algorithmus auch relativ leicht als Hash-Funktion verwenden, wird z.B. unter Unix/Linux auch in abgewandelter Form für die Passwörter verwenden.

Also:
H(X) = Ex(00...) := Hashwert von X (Verschlüsselung von 00 mit X als Key)

Die Ausgabe der Hash-Funktion beträgt ja 64 Bit, um eine beliebige Kollision der Hashfunktion zu finden muss ich im Schnitt etwas mehr als die Quadratwurzel an zufälligen Eingaben testen.
D.h., ich muss etwas mehr als 2^32 Eingaben testen um im Schnitt eine Kollision zu erhalten.
Da der Key aber 2^56 Werte haben kann (16 Mio. mehr als durchschnittlich nötig), erhalten ich mit einer Wahrscheinlichkeit von 99,99...% eine Kollision, sprich 2 unterschiedliche Keys ergeben den gleichen Geheimtext.
Geburtstagsparadoxon
Geburtstagsangriff

PS: Versuch nachher mal ne Kollision zu finden, wenn ich am meinem PC sitze und etwas Zeit habe.
2^32 Werte durchprobieren ist nicht viel

menace

Und wie sieht's aus? ich bin nämlich mittlerweile zur überzeugung gelangt, dass es bei DES nicht der fall ist

Elderan

Hallo,
also das Programm ist soweit fertig, mir mangelds aber gerade etwas an Arbeitsspeicher ^^ (der neue Rechner hat irgendwelche Hardwaremacken und stürtzt dauernd ab und die alten Rechner haben viel zu wenig Ram).

Man muss ja 96 Bit pro Verschlüsselung abspeichern, macht bei 2^32 Verschlüsselung 48 GB.
Ist zwar nicht allzuviel, aber doch schon einiges an Daten.


(Ich könnte den Server in der Uni missbrauchen, der hat 32 GB RAM, aber ich glaub dann haut mich unser Admin ^^)

Naja, muss schauen ob der neue PC nächste Woche vernünftig läuft.

Allerdings, wie schon gesagt, schau dir das Geburtstagsparadoxon an, und dann kann jeder selber nachrechnen, wie wahrscheinlich eine Kollision ist (99,....%)