Hinweise und Erlaeuterungen

                            zu Blowfish und CBC






1. Einleitung
~~~~~~~~~~~~~

Die Cryptengine stellt den wichtigsten Teil in einem Verschluesselungsprogramm
dar. Durch sie werden Daten im RAM ver- oder entschluesselt.
Sie wurde komplett in 386-Assembler entwickelt um eine maximale Bearbeitungs-
geschwindigkeit zu erzielen. Durch ein klares Funktionsinterface lassen sich
leicht Schnittstellen zu Hochsprachen festlegen. Mitgeliefert wird bereits
eine komplett einsatzbereite Turbo-Pascal-Unit, eine INCLUDE-Datei fuer
Assemblerprogramme sowie eine Headerdatei fuer C(++) Implementationen.



2. Etwas Theorie...
~~~~~~~~~~~~~~~~~~~

Sinnvolle Datenverschluesslung funktioniert natuerlich nur dann,
wenn der verwendete Algorithmus sicher und schnell genug ist.
Diese beiden Voraussetzungen erfuellt der Blowfish-Algorithmus von Bruce
Schneier. Er wurde von ihm im Fruehjahr 1994 zum ersten Mal in der
Programmiererzeitschrift DDJ vorgestellt, wobei gleichzeitig zu einem
Wettbewerb aufgerufen wurde, diesen neuen Algorithmus auf Schwachstellen
hin zu untersuchen bzw. zu knacken. In der Septemberausgabe 1995 kam man
dann zum Ergebnis, dass Blowfish in seiner jetztigen Form ungebrochen ist
und es voraussichtlich auch bleiben wird.

Was macht Blowfish so attraktiv ?
Neben der Sicherheit, die sowieso jedes Verschluesslungsverfahren
gewaehrleisten muss, ist der grosse Vorteil die hohe Geschwindigkeit.
Dies resultiert aus zwei Gruenden. Zum ersten muss im Algorithmus kein
einziger Sprung durchgefuehrt werden, und zum zweiten arbeitet er intern
mit 32bit-Werten. Beide Faktoren passen genau zu den Leistungsstaerken
moderner Mikroprozessoren, wie z.B. i80486 oder Pentium.
Blowfish ist in seinem Aufbau relativ unkompliziert. Wer die genaue
Wirkungsweise nachvollziehen will lesen bitte die oben genannte Ausgaben
der DDJ, oder das Buch "Applied Cryptogrphy, 2nd Edition" von Bruce Scheier.

Kurz beschrieben funktioniert der Algorithmus folgendermassen :
Blowfish definiert 2 Datenstrukturen, die sogenannten Boxen. Die P-Boxen
sind ein eindimensionales Feld mit 18 32bit-Werten, die S-Boxen ein
zweidimensionales Feld mit 4 x 256 32bit-Werten. In Pascal formuliert
sehen diese etwa so aus :

	pbox : array[1..18] of Longint;
	sbox : array[1..4, 1..256] of Longint;

Ueber deren Inhalte spaeter naeheres.
Verschluesselt mit Blowfish auf folgende Art und Weise : uebergeben
wird ein 64bit-Datenelement (= 8 Bytes). Dieser wird zelegt in zwei Teile,
nennen wir sie einmal DataLeft und DataRight, wobei DataLeft das hoeher-
und DataRight das niederwertige 32bit-Wort des 64bit-Datenelements ist.
Beim Verschluesseln geht mal nun folgendermassen vor :

	1:	for i:= 1 to 16 do begin
	2:	  DataLeft := DataLeft	  XOR pbox[i];
	3:	  DataRight:= F(DataLeft) XOR DataRight;
	4:	  Swap(DataLeft, DataRight);
	5:	end;

In jedem Schleifendurchgang wird zuerst DataLeft mit einem Eintrag aus
den P-Boxen XORrt (2). Danach wird DataRight mit dem Ergebnis der Blowfish-
funktion von DataLeft XORrt (3). Zuletzt vertauscht man die Inhalte von
DataLeft und DataRigtht miteinander (4).
Nach der Schleife sind noch zwei weitere Schritte noetig :

	6:	Swap(DataLeft, DataRight);
	7:	DataRight:= pbox[17] XOR DataRight;
	8:	DataLeft := pbox[18] XOR DataLeft;

Nun koennen DataLeft und DataRight wieder zu einem 64bit-Datenelement zusammen-
gefasst werden. Da die wenigsten Prozessoren aber heute schon 64bit-Integer
verarbeitet koennen uebergibt man der Ver- bzw. Entschluesselungsprozedur
die beiden 32bit-Haelften direkt.
Die Entschluesselungsroutine funktioniert aehnlich, nur werden hier die
P-Boxen von "hinten nach vorn" benutzt :

	1:	for i:= 18 downto 3 do begin
	2:	  DataLeft := DataLeft	  XOR pbox[i];
	3:	  DataRight:= F(DataLeft) XOR DataRight;
	4:	  Swap(DataLeft, DataRight);
	5:	end;
	6:	Swap(DataLeft, DataRight);
	7:	DataRight:= pbox[2] XOR DataRight;
	8:	DataLeft := pbox[1] XOR DataLeft;

Zu erlaeutern bleibt jetzt noch die Blowfish-Funktion F.
Wie man sieht erwartet sie als Parameter einen 32bit-Wert und gibt einen
solchen auch zurueck. Bei ihr kommen nun die S-Boxen ins Spiel. Der
uebergebene 32bit-Wert wird in 4 Bytes aufgespalten, die ihrerseits
nun Indexe auf die die 4 S-Boxen-Felder darstellen. Die jeweiligen S-Boxen
werden dann in einer Funktion zu dem neuen 32bit-Wert zusammengefuegt
Nennen wir die 4 Bytes a, b, c und d, den Eingabewert Input und den
Rueckgabewert einfach F, dann sieht das in Pascal so aus :

	1:	d    := (Input AND $000000ff) + 1;
	2:	Input:= Input SHR 8;
	3:	c    := (Input AND $000000ff) + 1;
	4:	Input:= Input SHR 8;
	5:	b    := (Input AND $000000ff) + 1;
	6:	Input:= Input SHR 8;
	7:	a    := (Input AND $000000ff)+1;
	8:	F    := ((sbox[1,a] + (sbox[2,b] AND $0000001f)) XOR sbox[3,c])
			+ ( sbox[4,d] AND $0000001f);

Man erkennt durch die vielen Binaeroperatoren SHR, AND und XOR, dass Blowfish
gerade dazu praedestiniert ist in Assembler geschrieben zu werden.
Bevor jedoch die Ver- und Entschluesselungsroutinen verwendet werden
koennen muessen die Boxen initialisiert werden.
Zuerst werden die P- und S-Boxen mit Zufallswerten gefuellt. Diese
Zufallswerte werden einmal erzeugt und dann immer wieder benutzt.
Der Autor von Blowfish, Bruce Schneier, verwendet dazu die hexadezimalen
Werte der Kreiszahl PI. Der Vorteil ist, dass bei Verlust der Binaerdatei
mit den Zufallswerten eben jene neu berechnet bzw. erzeugt werden kann.
Es bleibt dem Programmierer ueberlassen, ob er die Zufallsdaten fest
im Code verankert oder sie dynamisch zur Laufzeit nachlaedt.
Blowfish akzeptiert Schluessel bis zu einer Laenge von 56 Bytes. Wie man
den Schluessel erzeugt ist egal. Im allgemeinen wird man dazu das Passwort
des Users direkt uebernehmen, jedoch sind auch andere Varianten, z.B.
Hashing denkbar.
Man hat also ein Feld mit einer bestimmten Anzahl von Bytes, in welchem der
Key bzw. das Passwort gespeichert ist. Nun XORt man jedes Byte der P-Boxen
mit einem Key-Byte. Hat man das Ende des Keys erreicht, so beginnt man wieder
von vorn. In Pseudocode sieht das so aus :

		ByteZeiger = Adresse von P-Box[1]
		Index = 1
		for n=1 to (18*4)
		begin
		  Inhalt von ByteZeiger = Key[Index]
		  ByteZeiger = ByteZeiger + 1
		  Index = Index + 1
		  if Index > (Laenge von Key) then Index = 1
		end

Damit hat das Passwort seine Pflicht getan. Zuguterletzt verschluesselt man
P- und S-Boxen. Dazu definiert man ein 64bit-Datenelement. Praktischerweise
zerlegen wir es gleich in zwei 32bit-Haelften, wir nennen sie InitL und InitR.
Man setzt beide zu Beginn auf 0 und verschluesselt dann alle Boxeneintraege
mit den sich staendig aendernden zwei Haelften.
Wieder in Pascal :

	1:	InitL:=0;
	2:	InitR:=0;
	3:	i:=1;
	4:	while (i<18) do begin
	5:	  Encrypt(InitL, InitR);
	6:	  pbox[i]  :=InitL;
	7:	  pbox[i+1]:=InitR;
	8:	  i:=i+2;
	9:	end;
       10:	for i:=1 to 4 do begin
       11:	  j:=1;
       12:	  while (j<256) do begin
       13:	    Encrypt(InitL, InitR);
       14:	    sbox[i][j]	:=InitL;
       15:	    sbox[i][j+1]:=InitR;
       16:	    j:=j+2;
       17:	  end;
       18:	end;

Nachteilig am Pascal ist, dass man in FOR-Schleifen den Zaehler jeweils
nur um 1 erhoehen kann, deshalb muss hier auf eine WHILE-Schleife ausgewichen
werden.
Nach dieser Verschluesselung der Boxen ist eine Cryptengine nun einsatzbereit.
Bruce Schneier erwaehnte in seinem Artikel, dass man auch die so
verschluesselten Boxen abspeichern und zur spaeteren Verwendung wiederver-
wenden kann (z.B. zur Schluesselweitergabe, leider nicht fuer Kommunikations-
verschluesselung geeignet). Ob der Programmierer dieses Feature dem User
zur Verfuegung stellt bleibt Geschmackssache.

Soviel zur Theorie des Blowfish-Algorithmus.

Das wichtigste nochmals in Kuerze :

a) dass Blowfish Daten in 64bit-Bloecken verarbeitet, d.h. es werden jedesmal
   8 Bytes gleichzeitig ver- oder entschluesselt. Die Verschluesselung eines
   einziges Bytes ist nicht moeglich.

b) dass Blowfish mit einem sogenannten Key initialisiert werden muss. Der Key
   ist nicht anderes als das Passwort, welches der User vor der Ver- oder
   Entschluesslung eingibt. Dieser Key darf maximal eine Laenge von 56 Bytes
   bzw. Zeichen besitzen.

c) dass Zufallswerte benoetigt werden (genauer gesagt die mathematische 
   Konstante PI in hexadezimaler Form) welche zur Initialisierung des
   Algorithmus benoetigt werden. Prinzipiell koennen hier auch Zufallszahlen
   aus "eigener Produktion" verwendet werden. Es hat sich jedoch als bewaehrt
   erwiesen, die vorgegebenen Werte zu nehmen, da eigene Zufallszahlen z.B.
   fehlerhaft sein oder bei Verlust der Quelldatei verloren gehen koennen.

An Speicherplatz ist der Algorithmus aeusserst genuegsam. Der Programmcode
und die benoetigten Daten (im Fachjargon "Boxen" genannt) belegen nicht mehr
als 8 Kb. Dynamische Datenstrukturen werden sowieso nicht verwendet, die
Stackbelastung ist minimal.
Blowfish ist symmetrisch, d.h. es wird genau so schnell ent- wie
verschluesselt. Da beim Blowfish-Verfahren Zufallszahlen im Spiel sind sehen
die verschluesselten Bytes ebenfalls "von aussen" zufaellig aus, d.h. jeder
ASCII-Wert von 0..255 ist in einer bestimmten Datenmenge im Schnitt gleich oft
enthalten, unabhaengig von der Verteilung in der originalen Datenmenge.
Diese Eigenschaft zu kennen ist wichtig, da sich dadurch verschluesselte Daten
nicht mehr komprimieren lassen. Wird trotzdem ein Datenkompression gewuenscht
so ist sie vor der Ver- bzw. nach der Entschluesselung vorzunehmen.




3. Blowfish und noch etwas mehr - die Cryptengine
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ECB-Methode:
Blowfish ist ein Blockverschluesseler, d.h es werden immer 64 Bit unabhaengig
voneinander bearbeitet. Diese Eigenschaft hat den Nachteil, dass man "nur"
2^64 verschiedene 64bit-Paare von unverschluesseltem und die gleiche Menge
an verschluesselten Daten braucht, um dann ein Codebuch zu erstellen, d.h.
jedem verschluesselten Wert eindeutig einen unverschluesselten zuweisen zu
koennen. Dies ist in der Praxis natuerlich ziemlich unsinnig, denn wer hat
schon 2^64*8 Bytes an Daten, in beiderlei Formen ? Doch andere
cryptoanalytische Verfahren koennen darauf aufbauen und diese Schwaeche nutzen.
Da die maximale Key-Lenge von Blowfish 56 Bytes (= 448 Bit) ist muessten
bei einer (vollstaendigen) Brute-Force-Attack (also dem blossen Ausprobieren
aller moeglichen Passwoerter) 2^448 (!) Versuche notwendig sein.

CBC-Methode:
Hier greift man nun zum CBC-Verfahren um diese Sicherheitsluecke zu umgehen.
Wir speichern die 64bit-Datenelemente nicht so wie sie aus der
Verschluesselungsroutine herauskommen, sondern verknuepfen sie untereinander
(CBC = Cipher Block Chaining -> verketten von verschluesselten Bloecken).
Das CBC-Verfahren arbeitet bei Blowfish folgendermassen :
Wir lassen uns zu Beginn ein 64bit-Datenelement von einem Zufallsgenerator
erzeugen. Dieses nennen wir jetzt CBCStr. Wichtig ist, dass dieses Element
gespeichert werden muss, z.B. im Header einer Datei. Es stellt den Beginn
der Kette dar und wird zur Entschluesselung wieder benoetigt.
Nach der Initialisierung des Blowfish-Algorithmus holen wird jetzt das
erste 64bit-Datenelement, das wir verschluesseln wollen. Zuvor XORen wir
es jedoch mit CBCStr! Jetzt erst wird das Datenelement verschluesselt und
kann abgespeichert werden. Und nun der Clou : das verschluesselte Daten-
element ist unser neuer CBCStr! Holen wir also das naechste
64bit-Datenelement, XORen es mit CBCStr, verschluesseln es, speichern es
ab und kopieren seinen Inhalt in CBCStr, ... bis alles verschluesselt ist.
Beim Entschluesseln erfolgt der Vorgang genau umgekehrt. Zuerst entschluesseln
wir das erste verschluesselte 64bit-Datenelement, dann XORen wir es mit dem
"Ur"-CBCStr, denn wir uns gemerkt haben. Jetzt erst koennen wir ueber die
entschuesselten Daten verfuegen. Wir holen nun das zweite verschluesselte
64bit-Datenelement und entschluesseln es. Nun XORen wir es mit dem (!)
verschluesselten ersten Datenelement, weil dieses ja bei der Verschluesselung
der CBCStr fuer das zweite Datenelement war. Wir wiederholen diesen Vorgang
bis alles entschluesselt ist. Dabei haelt man sich immer vor Augen, dass der
verschluesselte Vorgaenger eines Datenelements der zugehoerige CBCStr ist.
Zur Verdeutlichung noch etwas Pseudocode :

    CBC-Verschluesselung:	CBCStr = Random
				Store(CBCStr)
				while (not EndOfData)
				  Read(datenelement)
				  datenelement = datenelement XOR CBCStr
				  Encrypt(datenelement)
				  Save(datenelement)
				  CBCStr = datenelement
				end

    CBC-Entschluesselung:	Restore(CBCStr)
				while (not EndOfData)
				  Read(datenelement)
				  Store(datenelement)
				  Decrypt(datenelement)
				  datenelement = datenelement XOR CBCStr
				  Save(datenelement)
				  Restore(datenelement)
				  CBCStr = datenelement
				end

Da der allererste CBCStr bei der Verschluesselung jedesmal neu mit einem
Zufallsgenerator erzeugt wird bestehen zwischen zwei urspruenglich gleichen
Datenmengen in verschluesseltem Zustand dann keine Gemeinsamkeiten mehr (ein
einfacher Blick in den Hex-Editor genuegt), sodass man keine einzelnen 64bit-
Bloecke isolieren kann.



- Dokumentende -