imported>SchlurcherBot: Bot: http → https

2025-08-04T17:42:18Z

Bot: http → https

Neue Seite

{{Infobox Blockchiffre
| name = Blowfish
| bild = Blowfish structure.svg|lang=de
| bildname = Feistelnetzwerk von Blowfish
| entwickler = [[Bruce Schneier]]
| datum = 1993
| schlüssellänge = 32–448 Bit (Standard 128 Bit)
| blockgröße = 64 Bit
| struktur = [[Feistelchiffre]]
| runden = 16
| kryptoanalyse = <div style="text-align:left">
* vier Runden von Blowfish sind anfällig für eine [[Differentielle Kryptoanalyse]]
* 14 Runden sind, für eine Klasse von schwachen Schlüsseln, anfällig für eine [[Zufällige Permutation|Pseudozufalls-Permutation]]</div>
}}
'''Blowfish''' ({{deS|[[Kugelfisch]]}}) ist ein symmetrischer [[Blockverschlüsselung]]salgorithmus, der 1993 von [[Bruce Schneier]] entworfen und erstmals im April 1994 in ''[[Dr. Dobb’s Journal]]'' publiziert wurde. Er wurde [[Gemeinfreiheit|gemeinfrei]] veröffentlicht und nicht patentiert.<ref>{{Internetquelle |url=https://www.schneier.com/academic/blowfish/ |titel=Schneier on Security: The Blowfish Encryption Algorithm |zugriff=2018-02-23}}</ref>

Blowfish hat eine feste Blocklänge von 64 [[Bit]], basiert auf einem [[Feistelnetzwerk]] und besitzt schlüsselabhängige [[S-Box]]en. Die [[Schlüssellänge]] kann 32 Bit bis 448 Bit betragen. Aus diesen Schlüsselbits werden vor Beginn der Ver- oder Entschlüsselung die so genannten Rundenschlüssel P1 bis P18 und die Einträge in den S-Boxen erzeugt, insgesamt 4168 Byte.

== Funktionsweise ==

Die Abbildung zeigt den internen Aufbau von Blowfish. Der 64 Bit breite Klartextblock wird in zwei Hälften <math>L_1</math> und <math>R_1</math> geteilt. In jeder sogenannten Runde, von denen insgesamt 16 durchlaufen werden, wird die linke Hälfte des Datenblocks mit einem vorab berechneten 32 Bit breiten Rundenschlüssel P1 bis P16 [[XOR-Verknüpfung|XOR]]-verknüpft, dann das Ergebnis in die Rundenfunktion ''F'' eingegeben und deren Ausgabe mit der rechten Hälfte XOR-verknüpft und die Hälften anschließend vertauscht. Am Ende werden noch die beiden Hälften mit den Rundenschlüsseln P17 und P18 XOR-verknüpft:

:<math> R_{i+1} = L_i \oplus P_i,</math>
:<math> L_{i+1} = R_i \oplus F(R_{i+1}) \quad (i \; \text{von} \; 1 \; \text{bis} \; 16)</math>
:<math> R_{18} = L_{17} \oplus P_{17}, \; L_{18} = R_{17} \oplus P_{18}</math>

<math>L_{18}</math> und <math>R_{18}</math> bilden dann den Schlüsseltextblock. Die Entschlüsselung läuft exakt gleich ab, nur werden dabei alle Rundenschlüssel P1 bis P18 in umgekehrter Reihenfolge verwendet. Das beruht auf der Vertauschbarkeit der XOR-Verknüpfungen. XOR ist sowohl [[Kommutativgesetz|kommutativ]] als auch [[Assoziativgesetz|assoziativ]]. Es ist gleich, ob man eine Hälfte des Datenblocks erst mit einem Rundenschlüssel und dann mit der Ausgabe der Funktion ''F'' verknüpft oder umgekehrt.

In der Funktion ''F'' kommen die schlüsselabhängigen S-Boxen zum Einsatz. Der Eingabewert wird in vier Byte geteilt, mit denen jeweils ein Wert aus einer von vier 8 × 32 Bit S-Boxen ausgelesen wird. Diese Werte werden mittels XOR und Addition modulo <math>2^{32}</math> verknüpft:


:<math> F(x) = \lbrace \lbrack \, S_1(x_{24..31}) \; + \; S_2(x_{16..23}) \, \rbrack \; \oplus \; S_3(x_{8..15}) \, \rbrace \; + \; S_4(x_{0..7})</math>.

Dabei steht <math>x_{a..b}\!\,</math> für die Bits an den Positionen ''a'' bis ''b'' aus der Binärdarstellung des Wertes ''x''.

=== Schlüsseleinteilung ===
Blowfish verwendet 18 Rundenschlüssel <math>P_1</math> bis <math>P_{18}</math> mit je 32 Bit und vier S-Boxen mit je 256 = 28 Einträgen von je 32 Bit. Die Initialisierung der <math>P_i</math> und der S-Boxen erfolgt mit einer fixen Zahlenfolge, die aus der Binärdarstellung der [[Kreiszahl|Kreiszahl π]] abgeleitet wird, um die Anforderungen an eine [[unverdächtige Konstante]] zu erfüllen. Die Nachkommastellen von π sind [[Pseudozufall|pseudozufällig]] und unabhängig vom restlichen Blowfish-Algorithmus.<ref>{{Literatur|Autor=Bruce Schneier| Titel=Description of a new variable-length key, 64-bit block cipher (Blowfish)| Sammelwerk=FSE 1993| Reihe=Lecture Notes in Computer Science| Band=809| Verlag=Springer| Jahr=1994| Seiten=201| Online=[https://www.schneier.com/paper-blowfish-fse.html schneier.com]}} {{Zitat|Sprache=en|I chose the digits of pi as the initial subkey table for two reasons: because it is a random sequence not related to the algorithm, and because it could either be stored as part of the algorithm or derived when needed. |Übersetzung= Ich habe die Ziffern von Pi als Initialisierung der Unterschlüssel aus zwei Gründen gewählt: weil es eine zufällige Folge ohne Bezug zum Algorithmus ist, und weil sie entweder als Teil des Algorithmus gespeichert, oder bei Bedarf berechnet werden kann. }}</ref> Davon ausgehend werden sowohl die Rundenschlüssel als auch die S-Boxen S1 bis S4 schlüsselabhängig verändert.

Dazu wird zuerst der Schlüssel in 32-Bit-Blöcke aufgeteilt. Danach wird jeder Rundenschlüssel mit den 32-Bit-Blöcken des Schlüssels XOR-verknüpft. Dabei wechseln sich die Blöcke des Schlüssels nacheinander ab. Danach wird ein Block mit 64 Nullbits verschlüsselt, unter Verwendung der aktuellen Rundenschlüssel und der wie oben initialisierten S-Boxen. Die linke und rechte Hälfte des entstandenen Schlüsseltextes ersetzen dann den ersten und zweiten Rundenschlüssel. Dann wird der obige Schlüsseltext mit den geänderten Rundenschlüsseln nochmals verschlüsselt, und der dritte und vierte Rundenschlüssel wird ersetzt usw. Nachdem auf diese Weise alle Rundenschlüssel ersetzt wurden, kommen die Einträge der S-Boxen an die Reihe, wobei auch wieder die jeweils nächste Verschlüsselung mit dem aktuellen Stand der S-Boxen gemacht wird. Es werden also insgesamt 521 Verschlüsselungen durchgeführt, bis die 18 Rundenschlüssel und die 1024 S-Box-Einträge ersetzt sind.

Danach bleiben die Rundenschlüssel und die Werte in den S-Boxen so lange konstant, bis ein neuer Schlüssel gewählt wird.

Als [[C++]]-Code:
<syntaxhighlight lang="cpp">
uint32_t P[18]; // Rundenschlüssel
uint32_t S[4][0x100]; // S-Boxen

uint32_t f (uint32_t x) {
uint32_t h = S[0][x >> 24] + S[1][x >> 16 & 0xff];
return ( h ^ S[2][x >> 8 & 0xff] ) + S[3][x & 0xff];
}

void encrypt (uint32_t & L, uint32_t & R) {
for (int i=0 ; i<16 ; i += 2) {
L ^= P[i];
R ^= f(L);
R ^= P[i+1];
L ^= f(R);
}
L ^= P[16];
R ^= P[17];
swap (L, R);
}

void decrypt (uint32_t & L, uint32_t & R) {
for (int i=16 ; i > 0 ; i −= 2) {
L ^= P[i+1];
R ^= f(L);
R ^= P[i];
L ^= f(R);
}
L ^= P[1];
R ^= P[0];
swap (L, R);
}

void key_schedule (uint8_t key[], int keylen) {
// ...
// Initialisiere P[] und S[][] mittels der Kreiszahl Pi; hier ausgelassen
// Es ist zu beachten, dass Pi in big-endian Reihenfolge eingelesen wird
// ...
int i;
int j=0;
int k;
for (i=0 ; i<18 ; ++i)
{
/* Der Schlüssel wird byteweise gelesen, und */
/* in big-endian Reihenfolge mit P[] verrechnet */
uint32_t tmp = 0;
for (k=0 ; k<4 ; k++)
{
tmp = tmp << 8 | key[j];
if(++j >= keylen) j=0;
}
P[i] ^= tmp;
}
uint32_t L = 0, R = 0;
for (i=0 ; i<18 ; i+=2) {
encrypt (L, R);
P[i] = L; P[i+1] = R;
}
for (i=0 ; i<4 ; ++i)
for (j=0 ; j<0x100 ; j+=2) {
encrypt (L, R);
S[i][j] = L; S[i][j+1] = R;
}
}
</syntaxhighlight>

== Kryptoanalyse und Sicherheit ==
Es ist kein effizienter Angriff auf die Blowfish-Verschlüsselung mit voller Rundenzahl bekannt. Ein so genannter Sign-Extension-Bug wurde in einer Veröffentlichung des C-Codes gefunden.<ref>Mike Morgan: [https://www.schneier.com/blowfish-bug.txt ''Blowfish can be cracked! (Fix included…)''.] Newsgroup sci.crypt</ref>

Serge Vaudenay fand 1996 einen [[Kryptoanalyse#Angriffsszenarien|Known-Plaintext-Angriff]], der zum Brechen der Verschlüsselung 28''r'' + 1 bekannte Paare von Klartext und Schlüsseltext benötigt. Der Parameter ''r'' bezeichnet die Anzahl der Runden. Zudem entdeckte er eine Klasse von schwachen Schlüsseln, die erkannt und mit nur 24''r'' + 1 Klartext-Paaren gebrochen werden können. Dieser Angriff kann jedoch nicht gegen regulären Blowfish eingesetzt werden, da er die Kenntnis der schlüsselabhängigen S-Boxen voraussetzt.

[[Vincent Rijmen]] stellt in seiner Doktorarbeit einen differenziellen Angriff zweiter Ordnung vor, der Blowfish mit höchstens 4 Runden brechen kann. Außer der [[Brute-Force-Methode]] ist kein Weg bekannt, den Algorithmus mit 16 Runden zu brechen.<ref name="vaudenay-weak-keys">{{cite web
|url= http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Vau96a
|title= On the Weak Keys of Blowfish
|accessdate= 2007-12-31
|last= Vaudenay
|first= Serge
|date= 2006-08-23
|work=
|pages=
|doi=
|quote=
|format= [[PostScript]]
|language= en
|archiveurl= https://web.archive.org/web/20071104154101/http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Vau96a
|archivedate= 2007-11-04
|offline= yes
}}</ref>

[[Bruce Schneier]] merkt an, dass er den neueren [[Twofish]]-Algorithmus empfiehlt, obwohl Blowfish noch in breiter Verwendung ist.<ref name="schneier-interview-dec-2007">{{cite web
|url = http://www.computerworld.com.au/index.php/id;1891124482;pp;1;fp;4194304;fpid;1
|title = Bruce Almighty: Schneier preaches security to Linux faithful
|accessdate = 2007-12-31
|language = en
|last = McConnachie
|first = Dahna
|date = 2007-12-27
|work = Computerworld
|pages = 3
|doi =
|quote = At this point, though, I’m amazed it’s still being used. If people ask, I recommend Twofish instead.
|offline = yes
|archiveurl = https://web.archive.org/web/20081005014100/http://www.computerworld.com.au/index.php/id;1891124482;pp;1;fp;4194304;fpid;1
|archivedate = 2008-10-05
}}</ref>

Da Blowfish eine Blockgröße von 64 Bit verwendet (AES verwendet 128 Bit Blöcke), ist ein [[Geburtstagsangriff]] – vor allem im [[HTTPS]]- oder [[OpenVPN]]-Kontext – möglich. Im Jahr 2016 zeigte der SWEET32-Angriff, wie ein Geburtstagsangriff genutzt werden kann, um den Klartext wiederherzustellen. Der SWEET32-Angriff funktioniert bei Verschlüsselungsverfahren wie Blowfish, die mit einer Blockgröße von 64 Bit arbeiten.<ref>{{cite web
| url=https://sweet32.info/
| title=On the Practical (In-)Security of 64-bit Block Ciphers – Collision Attacks on HTTP over TLS and OpenVPN
| author=Karthikeyan Bhargavan, Gaëtan Leurent
| date=2016-08
| language=en
| publisher=ACM CCS 2016}}</ref>

== Beispiele ==

Im [[GNU Privacy Guard]] sind Blowfish und [[Twofish]] implementiert und können auf Wunsch aktiviert werden. Das [[Cryptographic File System]] (CFS) ist ein auf [[Network File System|NFS]] aufsetzendes verschlüsseltes [[Dateisystem]] für [[Unix|UNIX]] und unterstützt ebenfalls Blowfish. Ein quelloffenes Windows-Programm zum Verschlüsseln von Dateien mittels Blowfish, Twofish und weiteren Algorithmen wie z. B. AES ist Blowfish Advanced CS. Auch im [[OpenDocument]]-Datenformat ist Blowfish als Verschlüsselungsmethode aufgeführt. Ab [[PHP]] 5.3 ist Blowfish Bestandteil der crypt-Funktion. Blowfish ist ebenfalls in der freien Krypto-Bibliothek [[OpenSSL]] implementiert.<ref>Offizielle OpenSSL-Dokumentation: {{Webarchiv|text=Blowfish |url=https://www.openssl.org/docs/crypto/blowfish.html |wayback=20140214081002 }}</ref> Die [[Virtual Private Network|VPN]]-Software [[OpenVPN]] nutzt als symmetrische Komponente standardmäßig ebenfalls Blowfish.<ref>{{Webarchiv|url=http://www.imped.net/oss/misc/openvpn-2.0-howto-edit.html#security |wayback=20150209011916 |text=Offizielle OpenVPN-Dokumentation }}</ref>

OpenSSH hat in dem Ende 2016 veröffentlichten Release 7.4 die Blowfish-Unterstützung, wie auch viele andere schwache Chiffren, entfernt.<ref>[https://www.openssh.com/txt/release-7.4 OpenSSH 7.4 Release Notes]</ref>

== Siehe auch ==
* [[Twofish]], Nachfolger von Blowfish
* [[Puffy (Maskottchen)|Puffy, the blowfish]], Maskottchen der [[OpenSSH]]

== Literatur ==
* Vincent Rijmen: ''Cryptanalysis and design of iterated block ciphers''. doctoral dissertation, Oktober 1997.
* Bruce Schneier: ''Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish)''. Fast Software Encryption 1993, S. 191–204, [https://www.schneier.com/paper-blowfish-fse.html schneier.com].
* Bruce Schneier: ''The Blowfish Encryption Algorithm – One Year Later''. In: ''[[Dr. Dobb’s Journal]]'', 20(9), S. 137, September 1995, [https://www.schneier.com/paper-blowfish-oneyear.html schneier.com].
* Serge Vaudenay: ''On the weak keys of Blowfish''. In: D. Gollmann (Ed.): ''Fast Software Encryption (FSE’96)'', LNCS 1039. Springer-Verlag, 1996, S. 27–32.

== Weblinks ==
* [https://www.schneier.com/blowfish.html Bruce Schneiers Beschreibung des Algorithmus] [https://www.schneier.com/blowfish-download.html incl etlicher Sourcecodes]
* [https://www.schneier.com/code/constants.txt S-Box und P-Box]
* [https://www.php-einfach.de/sonstiges_generator_blowfish.php Online Blowfish-Verschlüsselung (PHP oder JavaScript)]
* [http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#Blowfish Standard Cryptographic Algorithm Naming zu Blowfish]
* {{Webarchiv | url=http://www.lassekolb.info/bfacs.htm | wayback=20130219032000 | text=Blowfish Advanced CS}}

== Einzelnachweise ==
<references />

[[Kategorie:Blockverschlüsselung]]

Blowfish - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https