Blowfish oder doppelt hält besser

Knacken von Verschlüsselungen bei den Projekten RC5-72, RSAttack und anderen

Blowfish oder doppelt hält besser

Unread postby Bert » 03.09.2007 15:20

Hallo.
Ich verwende in einem Programm eine Implementierung des Blowfish-Algorithmus'. In unserem Fall verschlüsselt er Dateien.
Es gibt meines Wissens noch keine kryptoanalytischen Angriff, so daß die Entschlüsselung nur per brut-force-attack zum Erfolg führen kann.
Doch wie erkennt ein Angreifer, daß er den richtigen Schlüssel gewählt hat?
Er müßte sich die Datei mit einem Hexeditor anschauen um an bestimmten Merkmalen herauszufinden, mit welchem Programm er die vermeintlich entschlüsselte Datei öffnen kann.
So weit so klar, oder?
Wenn ich aber den Algorithmus zweimal anwende, die verschlüsselte Datei noch mal verschlüssele, kann der Angreifer bei keinem aller möglichen Schlüssel ein Treffer finden und ist gescheitert.
Oder sehe ich was falsch?
Wie seht ihr Profis das?

Bert
Bert
Fingerzähler
Fingerzähler
 
Posts: 1
Joined: 03.09.2007 14:57

Unread postby SpeedKing » 03.09.2007 15:57

Ich bin zwar kein Verschlüsselungsprofi, aber rein von der Überlegung her würde ich dir recht geben. Der Angreifer müßte dann für jede mögliche Entschlüsselung nochmals alle möglichen Entschlüsselungen überprüfen, also statt n Möglichkeiten n+n² Möglichkeiten durchrechnen.
User avatar
SpeedKing
TuX-omane
TuX-omane
 
Posts: 2943
Joined: 12.09.2003 17:14

Unread postby arminius » 03.09.2007 16:51

arminius
 

Re: Blowfish oder doppelt hält besser

Unread postby Lasse Kolb » 03.09.2007 17:06

Bin auch kein Experte, aber Lutz Donnerhacke hat - soweit ich mich erinnere - mal gesagt, dass eine Doppel-Verschlüsselung keinen Mehr-Nutzen bringt.

Der Blowfish-Algo an sich ist nach wie vor sehr gut!

Gruß,
Lasse
User avatar
Lasse Kolb
Vereinsvorstand
Vereinsvorstand
 
Posts: 1289
Joined: 03.12.2002 21:06
Location: Braunschweig/Hondelage

Re: Blowfish oder doppelt hält besser

Unread postby SpeedKing » 03.09.2007 17:47

lasse wrote:Bin auch kein Experte, aber Lutz Donnerhacke hat - soweit ich mich erinnere - mal gesagt, dass eine Doppel-Verschlüsselung keinen Mehr-Nutzen bringt.

...wenn man 2x mit dem gleichen Verfahren und den gleichen Schlüsseln verschlüsselt, oder?
User avatar
SpeedKing
TuX-omane
TuX-omane
 
Posts: 2943
Joined: 12.09.2003 17:14

Re: Blowfish oder doppelt hält besser

Unread postby Lasse Kolb » 03.09.2007 17:53

SpeedKing wrote:
lasse wrote:Bin auch kein Experte, aber Lutz Donnerhacke hat - soweit ich mich erinnere - mal gesagt, dass eine Doppel-Verschlüsselung keinen Mehr-Nutzen bringt.

...wenn man 2x mit dem gleichen Verfahren und den gleichen Schlüsseln verschlüsselt, oder?


Vermutlich ...
http://www.softgames.de/forum/frage118721.html
User avatar
Lasse Kolb
Vereinsvorstand
Vereinsvorstand
 
Posts: 1289
Joined: 03.12.2002 21:06
Location: Braunschweig/Hondelage

Unread postby SpeedKing » 03.09.2007 18:22

Eine Zusammenfassung von dem Forum:
Wendet man 2x das gleiche Verfahren an, so ist es besser, stattdessen das Verfahren nur 1x mit einem längeren Schlüssel anzuwenden.
Wendet man zwei verschiedene Verfahren an, so kann das je nach Verfahren wesenlich mehr Sicherheit bringen als 1x mit einem längeren Schlüssel. Man muß aber genau wissen, welche Verfahren man verwendet, sonst kann es sogar einen Verlust an Sicherheit bewirken.
User avatar
SpeedKing
TuX-omane
TuX-omane
 
Posts: 2943
Joined: 12.09.2003 17:14

Re: Blowfish oder doppelt hält besser

Unread postby archre » 03.09.2008 13:51

Das halte ich für ein Gerücht.
Und zwar betrachte man folgenden sogenannten Meet-In-The-Middle Angriff, eine Form eines known-plaintext Angriffs (btw. nicht zu verwechseln mit dem Man-In-The-Middle Angriff):

Sei E(k,x) die Verschlüsselungsfunktion, D(k,x) die Entschlüsselungsfunktion
eines symmetrischen Kryptoverfahrens (wie Blowfish, AES, DES).

Wenn wir zweimal mit einem n-Bit Schlüssel verschlüsseln, berechnen wir also E(k1,E(k2,x)).
Angenommen wir haben ein Klartext/Chiffretext-Paar (m,c) gegeben, dann können wir folgendes machen:

1. Schritt:
D(k2,c) berechnen für alle Schlüssel k2 => Aufwand: O(2^n)
und speichern des Ergebnisses für alle k in einer Hashmap, so dass nach D(k2,c) im Mittel in O(1) zugegriffen werden kann => Speicheraufwand: O(2^n)

2. Schritt:
E(k1,m) berechnen für alle Schlüssel k1 und dabei jedes Mal prüfen, ob das Ergebnis in der Hashmap liegt, ist dies der Fall haben wir unser Schlüsselpaar k1,k2 gefunden
=> Aufwand: O(2^n)

Insgesamt haben wir also einen Zeitkomplexität von O(2^(n+1)) und eine Platzkomplexität von O(2^n).


Nehmen wir jetzt aber einen doppelt so langen Schlüssel und verschlüsseln nur einmal, haben wir im Brute-Force-Verfahren eine Zeitkomplexität von O(2^2n) und somit einen quadratischen Sicherheitszuwachs.

Das ist übrigens der Grund dafür, dass 3DES verwendet wird und nicht 2DES, bei 3DES funktioniert obiger Angriff nicht (zumindest nicht vollständig) und die effektive Schlüssellänge ist doppelt so lang.
Warum dann nicht einfach DES mit doppelt so langem Schlüssel nehmen?
Weil DES in vielen Anwendungen in Hardware realisiert ist und 3DES einfach die alte Implementierung verwenden kann.

Grüße
archre
archre
Idle-Sammler
Idle-Sammler
 
Posts: 4
Joined: 03.09.2008 13:36

Re: Blowfish oder doppelt hält besser

Unread postby SpeedKing » 03.09.2008 14:44

archre wrote:Das halte ich für ein Gerücht.

Verstehe ich nicht...

archre wrote:Insgesamt haben wir also einen Zeitkomplexität von O(2^(n+1)) und eine Platzkomplexität von O(2^n).

Nehmen wir jetzt aber einen doppelt so langen Schlüssel und verschlüsseln nur einmal, haben wir im Brute-Force-Verfahren eine Zeitkomplexität von O(2^2n) und somit einen quadratischen Sicherheitszuwachs.

O(2^(n+1)) ist doch kleiner als O(2^2n), oder?
User avatar
SpeedKing
TuX-omane
TuX-omane
 
Posts: 2943
Joined: 12.09.2003 17:14

Re: Blowfish oder doppelt hält besser

Unread postby archre » 03.09.2008 15:06

exakt und da die Zeitkomplexität quadratisch größer ist, ist das Verfahren sicherer

d.h. ein Angreifer, der bei einem Verfahren mit doppelter Verschlüsselung 10h zum Knacken braucht, bräuchte bei einem Verfahren mit doppelt so langem Schlüssel 100h
archre
Idle-Sammler
Idle-Sammler
 
Posts: 4
Joined: 03.09.2008 13:36

Re: Blowfish oder doppelt hält besser

Unread postby SpeedKing » 03.09.2008 15:28

Und warum ist das dann ein Gerücht?
User avatar
SpeedKing
TuX-omane
TuX-omane
 
Posts: 2943
Joined: 12.09.2003 17:14

Re: Blowfish oder doppelt hält besser

Unread postby archre » 03.09.2008 15:56

SpeedKing wrote:Und warum ist das dann ein Gerücht?


naja das ist doch nur so eine Redensart, "das halte ich für ein Gerücht"
oder anders ausgedrückt "ich habe einen Gegenbeweis"...
archre
Idle-Sammler
Idle-Sammler
 
Posts: 4
Joined: 03.09.2008 13:36

Next

Return to Kryptographie

Who is online

Users browsing this forum: No registered users and 3 guests