%% LyX 1.6.0 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[ngerman]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8x]{inputenc}
\usepackage{babel}

\usepackage{url}
\usepackage[unicode=true, pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=false]
 {hyperref}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newenvironment{lyxlist}[1]
{\begin{list}{}
{\settowidth{\labelwidth}{#1}
 \setlength{\leftmargin}{\labelwidth}
 \addtolength{\leftmargin}{\labelsep}
 \renewcommand{\makelabel}[1]{##1\hfil}}}
{\end{list}}
\newenvironment{lyxcode}
{\par\begin{list}{}{
\setlength{\rightmargin}{\leftmargin}
\setlength{\listparindent}{0pt}% needed for AMS classes
\raggedright
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\normalfont\ttfamily}%
 \item[]}
{\end{list}}

\begin{document}

\title{Wurstkessel — Kryptographie in Forth}
\ifx\shorttitle\undefined\else
\shorttitle{Wurstkessel — Forth--Kryptographie}
\fi


\author{Bernd Paysan}
\maketitle
\begin{abstract}
Dieser Artikel behandelt das Thema ,,symmetrische Verschlüsselung{}``
anhand eines Beispiels. Zur symmetrischen Verschlüsselung gehört auch
ein kryptographisch starker Hash und ein ebensolcher Zufallsgenerator.
Und da man Programme, die man schreibt, auch testen muss, können Überlegungen
zum Knacken der Verschlüsselung auch nicht fehlen.
\end{abstract}
\begin{multicols}{2}


\section*{Motivation}

Auf die Idee, einen eigenen Algorithmus zur symmetrischen Verschlüsselung
zu entwickeln, kam ich, als ich die Implementierung des ,,Whirlpool{}``-Algorithmus
\cite{whirlpool} angesehen habe. Whirlpool ist kein Haushaltsgerät,
sondern ein relativ neuer Hash--Algorithmus. MD5 ist ja geknackt,
und damit wertlos. Auch SHA--1 hat bekannte Schwächen, und wenn einmal
eine Schwäche bekannt ist, dann taucht bald die nächste auf \cite{sha-1}.
Und SHA--2 basiert auf demselben Algorithmus, ist also wohl auch nicht
besser. Also müssen zumindest neue Hash--Algorithmen her.

Als Ziel habe ich mir dann gesetzt, dass der Algorithmus einfach implementiert
werden kann, sowohl in Hardware als auch in Software --- und da auch
auf sehr einfach gestrickten CPUs --- und dass er ein inhärent hohes
Maß an Parallelität hat, und damit zumindest theoretisch auch ein
hoher Durchsatz möglich ist. Und natürlich sollte der Algorithmus
auch skalieren, d.h. es soll möglich sein, die Schlüssel- bzw. Hashlänge
je nach Bedarf zu variieren.

Die aktuelle Runde der NIST, einen Kandidaten für SHA--3 zu finden,
habe ich zwar verpasst. Das ist aber nicht wirklich schlimm, denn
Kryptographie gedeiht nicht mit Schnellschüssen.


\section{Kryptologische Grundlagen}

In der VD 1/2005 habe ich ja schon mal über Verschlüsselung geschrieben,
damals über den RSA--Algorithmus, der zum Austausch von Schlüsseln
und zur digitalen Signatur verwendet wird. Damals ging es um asymmetrische
Verschlüsselung, deren Hauptzweck der Austausch von Schlüsseln (Public--Key--Verfahren)
und digitale Signaturen sind. Das damals war nur eine schematische
Modellimplementierung, der zur Anwendung noch einige Details fehlten,
neben der Bignum--Bibliothek insbesondere
\begin{itemize}
\item ein guter Pseudo--Zufall
\item ein symmetrisches Verschlüsselungsverfahren
\item und ein kryptographischer Hash
\end{itemize}
Wir werden sehen, dass die drei Verfahren auf derselben Basis aufbauen
können. Gerade der Zufall ist ein wichtiges Element, denn wenn man
eine wirklich gute Zufallsfolge hat, kann man mit ihr auch perfekt
verschlüsseln. Der sogenannte ,,One--Time--Pad{}`` ist die einzige
kryptographische Methode, die wirklich nicht brechbar ist --- wenn
man sie bestimmungsgemäß anwendet, d.h. den zu verschlüsselnden Text
mit einer Folge von Zufallszahlen verknüpft, die mindestens so lang
wie der Text ist, und genau einmal gebraucht wird. In der Praxis ist
diese Methode nur in Spezialfällen brauchbar, da der Aufwand zum sicheren
Austausch des Schlüssels genauso hoch ist wie der Aufwand zum geheimen
Austausch einer unverschlüsselten Nachricht --- und ein vorab ausgetauschter
Schlüssel dann auch noch entsprechend sicher verwahrt werden muss.

Trotzdem gibt uns diese Methode ein Ziel vor: Unsere Verschlüsselung
soll sich ohne Kenntnis des Schlüssels nicht von Zufall unterscheiden,
und der Schlüssel selbst darf nur durch Ausprobieren gefunden werden.
Etwas Vergleichbares gilt auch für einen Hash: Der Hash--Wert einer
Nachricht ist zwar deterministisch durch die Nachricht bestimmt, soll
aber ebenfalls wie ein völlig zufälliger Wert aussehen, der sich zwar
mit jeder Änderung der Nachricht ändert, aber in einer unvorhersehbaren
Weise --- ändert man ein Bit in der Nachricht, so sollten sich ca.
die Hälfte aller Bits des Hashes andern (und natürlich nicht vorhersehbar
sein, welche Hälfte der Bits sich ändert). Aus dem Hash--Wert soll
nicht auf die Nachricht zurückgeschlossen werden können; genauso wenig
soll es möglich sein, durch gezielte Modifikation der Nachricht einen
bestimmten Hashwert zu erzeugen.

Whirlpool verwendet zwar einen anderen theoretischen Ansatz, die Implementierung
für 64--Bit--Prozessoren ist aber tabellengetrieben. Aus genau diesem
tabellengetriebenen Ansatz habe ich dann meinen Algorithmus hergeleitet.
Basis ist eine Funktion, die zwei 512 Bit lange Zahlen so durch den
Fleischwolf dreht, dass nur noch Wurst herauskommen kann:

\[
\phi(a,s,e)\to a',s'\]


wobei
\begin{lyxlist}{00.00.0000}
\item [{$a$}] ein Akkumulator ist,

\begin{itemize}
\item der am Ende der Transformation als Hashwert ausgegeben wird,
\item bei der symmetrischen Verschlüsselung mit dem Text verknüpft wird,
\item oder als Zufallszahl dient,
\end{itemize}
\item [{$s$}] ein interner Zustand, der nicht preisgegeben werden soll,
und
\item [{$e$}] eine Entropiequelle, also bei Hash und Verschlüsselung die
Botschaft selbst, beim Generieren von Zufallszahlen externe, echt
zufällige Ereignisse, die mit dem Pseudozufallsgenerator gemischt
werden können.
\end{lyxlist}
Die Anforderung an $\phi$ ist schlicht: Sie soll sich leicht und
schnell berechnen lassen, aber die Umkehrung $\phi^{-1}$ soll praktisch
unmöglich berechenbar sein.


\section{Algorithmus}

Ich will also aus Eingangsvektoren möglichst schnell möglichst ,,zufällige{}``
Zahlen bekommen. Was liegt näher, als die Eingangsvektoren über eine
Tabelle einfach auf wirklich zufällige Werte abzubilden? Ich habe
mir auf \url{www.random.org} also 256 wirklich zufällige 64--Bit--Werte
besorgt. Die Indices in diese Tabelle sind also Bytes aus meinem Akkumulator
und dem internen Zustand. Diese 64--Bit--Werte verknüpfe ich mit einem
XOR--Operator; damit Vertauschungen auch unterschiedliche Werte geben,
rotiere ich den Wert vor der nächsten XOR--Verknüpfung um eins nach
links.

Die Idee dabei ist: Indizierung von 256 zufälligen 64--Bit--Werten
ergibt eben diese 256 möglichen zufälligen Werte. Verknüpfe ich zwei
davon, einer um ein Bit rotiert, bekomme ich $256^{2}=64$k Werte,
zwischen denen kein erkennbarer Zusammenhang besteht. Acht Werte derart
verknüpft, ergibt ca. $256^{8}=2^{64}$ verschiedene Werte, zwischen
denen ebenfalls kein erkennbarer Zusammenhang besteht. Wenn die Theorie
stimmt, dann sollten dabei $2^{32}$ Kollisionen entstanden sein,
d.h., bestimmte Ausgangswerte liefern das gleiche Ergebnis. Das ist
so gewünscht, das würde nämlich auch passieren, wenn man statt der
Abbildung einfach $2^{64}$ echte Zufallszahlen ziehen würde.

Damit das Ganze noch weniger deterministisch wird, starte ich diese
Verknüpfung mit einem 64--Bit--Wert aus dem Status; dabei permutiere
ich die Status--Wörter in einem möglichst langen Zyklus.

Den Index in die Tabelle bekomme ich, indem ich je ein Byte aus dem
Status mit einem Byte aus dem Message--Akkumulator verXODERe. Dabei
transponiere ich den Status, d.h., ich schreibe die Wörter byteweise
in Zeilen und laufe dann spaltenweise durch. Den Message--Akkumulator
durchlaufe ich mit Primzahlschritten, jede Runde eine andere Schrittweite.
Am Ende einer Runde wird der alte Status mit dem Message--Akkumulator
ver-XODERt. Damit stelle ich sicher, dass selbst für den Fall einer
Kollision entweder der Message--Akkumulator oder der Status einen
anderen Wert enthält, also bei der nächsten Runde wieder ein anderes
Ergebnis gefunden wird.

Oder in mathematische Formelsprache gekleidet:
\begin{description}
\item [{$rng_{x}$}] 256 64--bittige Zufallszahlen von \url{www.random.org}
in einer Tabelle
\item [{$rol(rng_{x},1)\oplus rng_{y}$}] gibt 64k zufällig aussehende
Zahlen
\item [{$r^{j}=\bigoplus_{i=0}^{7}rol(rng_{x_{i}^{j}},i)$}] gibt ca. $2^{64}-2^{32}$
zufällig aussehende Zahlen
\item [{$x_{i}^{j}=a_{p(8j+i)}\oplus s_{j}^{i}$}] Index in die Tabelle:
Bytes aus dem Akkumulator (in verschiedenen Schrittweiten durchlaufen)
mit einem Byte des transponierten Status verknüpfen
\item [{$s^{j}=s^{p(j)}\oplus r^{j}$}] Die 64--Bit--Worte des Status werden
permutiert und mit den generierten Zahlen verXODERt.
\item [{$e'=a\oplus e,a'=s\oplus e'$}] Akkumulator, Message (,,Entropie{}``)
und Status miteinander verXODERn.
\end{description}
Die ,,naive{}`` Implementierung in Forth sieht dann so aus (nur
die wesentlichen Teile):
\begin{lyxcode}
8table~round\#~\\
~~~13~,~29~,~19~,~23~,~31~,~47~,~17~,~37~,~\\
8table~permut\#~\\
~~~2~,~6~,~1~,~4~,~7~,~0~,~5~,~3~,~\\
~~~\textbackslash{}~permut~length~15~\\
:~mix2bytes

~~(~index~n~k~-{}-~b1~..~b8~index'~n~)~\\
~~wurst-state~+~8~0~DO~\\
~~~~>r~over~wurst-source~+~c@~\\
~~~~r@~c@~xor~-rot~dup~>r~+~\$3F~and~\\
~~~~r>~r>~8~+~LOOP~\\
~~drop~;~\\
:~bytes2sum~(~ud~b1~..~b8~-{}-~ud'~)~\\
~~~~~>r~>r~>r~>r~~>r~>r~>r~>r~\\
~~~~~r>~rngs~wurst~~r>~rngs~wurst~\\
~~~~~r>~rngs~wurst~~r>~rngs~wurst~\\
~~~~~r>~rngs~wurst~~r>~rngs~wurst~\\
~~~~~r>~rngs~wurst~~r>~rngs~wurst~;~~\\
:~round~(~n~-{}-~)~dup~1-~swap~~8~0~DO~\\
~	wurst-state~I~permut\#~\\
~~~~~64s~+~64@~-64swap~\\
~	I~mix2bytes~2>r~bytes2sum~2r>~\\
~~~~~64swap~nextstate~I~64s~+~64!~\\
~~~~~LOOP~2drop~update-state~;~~\\
:~rounds~(~n~-{}-~)~~message~swap~\\
~~~~dup~\$F~and~8~umin~0~?DO~\\
	I~rounds\#~round~\\
	dup~'round-flags~Ith~and~IF~\\
	~~~~swap~+entropy~swap~\\
	THEN~\\
~~~~LOOP~2drop~;~
\end{lyxcode}

\subsection{Performance}

Die naive Implementierung war zunächst sehr langsam (bigForth: ca.
1MB/s auf einem 2,5GHz Phenom). Wahrscheinlich war ein Code--Daten--Konflikt
das Problem --- nach Beseitigung dessen ging die Performance auf 23MB/s
hoch (Gforth: 20MB/s, dank 64 Bit nur unwesentlich langsamer). Um
die Performance zu verbessern, habe ich die Schleife aufgerollt, was
die Performance auf 46MB/s verdoppelte (bigForth).

Das war immer noch nicht sehr befriedigend, also habe ich das libcc--basierte
C--Interface in Gforth genutzt, um den aufgerollten Schleifen--Code
mit dem GCC zu compilieren. Mit knapp über 500MB/s kam dabei dann
ein Ergebnis heraus, das auch den Erwartungen entspricht. Als Benchmark
nutze ich das Wort \texttt{time-rng}, als Berechnungsgrundlage dient
eine Runde pro 512 Bits. Der Zufallsgenerator, der hier getimed wird,
macht zwei Runden pro 512 Bits, liefert also ca. 250MB/s Zufallszahlen.


\section{Analyse}

Um festzustellen, wie sicher der Algorithmus ist, muss man natürlich
versuchen, ihn zu brechen. Die Funktion $\phi$ soll ja unumkehrbar
sein, d.h., wir sollten uns ansehen, wie sich z.B. das Ändern eines
einzelnen Bits auswirkt. Nach einer Runde unterscheidet sich ein 64--Bit--Wort,
und dieses 64--Bit--Wort hat auch nur genau einen unserer 256 Zufallswerte
getauscht. Das heißt, wir müssen uns ,,nur{}`` die 64k möglichen
Kombinationen zwischen zwei Zufallswerten und 8 mögliche Rotationen
ansehen, um auf die Änderung dieses einzelnen Bits zurückschließen
zu können.

Bei der nächsten Runde breitet sich die Änderung des Status entsprehend
aus. Alle 8 Status--Worte sind nun anders und haben mindestens eine
Zufallszahl getauscht; da wir in den meisten Fällen auch Auswirkungen
auf die Änderung des Message--Akkumulators haben, im Durchschnitt
sogar zwei Zufallszwahlen. Dazu müssten wir nun $2^{32}$ mögliche
Kombinationen durchsuchen, und zwar pro Wort. Eine weitere Runde sind
dann alle Zufallszahlen im Status ausgetauscht, ein Zurückschließen
ist weitgehend unmöglich. Der Message--Akkumulator hinkt prinzipbedingt
immer eine Runde hinterher, weil hier nur der alte Status ver-XODERt
wird. Wir hängen also noch eine vierte Runde an, um sicher zu gehen,
dass sowohl Status als auch Message--Akkumulator ausreichend durcheinandergewürfelt
sind.

Wie viele Runden müssen wir zwischen dem Hinzufügen von
Information beim Hashen ausführen? Vermutlich nur eine. Wir müssen
aber am Ende der Hash--Berechnung mindestens 4 Leerrunden durchführen,
damit kein Rückschluss auf die Message möglich ist.

Wieviele müssen wir beim Verschlüsseln ausführen? Mindestens 2. Um
das zu beweisen, reicht eine einfache Klartextattacke: Angenommen,
wir kennen die ersten 128 \mbox{Bytes} einer Message (inklusive Länge). Wir
können dann aus den ersten beiden Blöcken des verschlüsselten Texts
sowohl den Akkumulator als auch den Status berechnen --- einfach,
indem wir die beiden aufeinanderfolgenden Blöcke ver-XODERn, und die
darin enthaltenen Message--Blöcke herausrechnen. Mit diesem vollständig
rekonstruierten internen Status können wir den Rest des Texts entschlüsseln.

Das klappt nicht, wenn wir eine zweite Runde hinzufügen --- denn dann
befindet sich in jedem Block der verschlüsselten Message die XODER--Verknüpfung
von zwei internen Zuständen. Daraus einen einzelnen herauszurechnen
ist schwer möglich.


\section{Anweisungen zum sicheren Gebrauch}

Kryptographie ist nur sicher, wenn sie sorgfältig betrieben wird.
Die folgenden Anweisungen beschreiben, wie man bekannte Probleme umgeht.
\begin{description}
\item [{Signatur}] Signiert wird der Hash--Wert der Datei, indem er mit
dem privaten Schlüssel verschüsselt wird. Es wird empfohlen, einen
zufälligen Startwert im Akkumulator zu verwenden. Dieser zufällige
Startwert stellt sicher, dass ein Angreifer nicht vorab eine Kollision
berechnen kann, und damit später ein anderes Dokument unterschieben
kann. Nachträglich kann ein Angreifer immer noch eine Kollision finden,
aber das ist erheblich schwerer (verdoppelt die Anzahl Bits in der
Stärke des Hashs). Bruce Schneier empfiehlt, als Startwert den öffentlichen
Schlüssel zu verwenden --- das ist aber wenig sinnvoll, da der dem
Angreifer ja bekannt ist.
\item [{Verschlüsselung}] Verschlüsselt man mit einem Schlüssel mehrere
Nachrichtenteile (z.B. Anhänge in einer E--Mail), so ist es ratsam,
den Akkumulator für jeden Teil mit einem anderen Zufallswert vorzubelegen.
Will man eine Replay--Attacke verhindern, kann man auch einen Timestamp
in die Vorbelegung einbeziehen.\end{description}
\begin{thebibliography}{3}
\bibitem[1]{whirlpool}Vincent Rijmen und Paulo S. L. M. Barreto \emph{Whirlpool}
\emph{Page }\texttt{\href{http://www.larc.usp.br/~pbarreto/WhirlpoolPage.html}{http://www.larc.usp.br/$\sim$pbarreto/Whirlpool Page.html}}

\bibitem[2]{sha-1}Meldung auf Heise Security vom 11.6.2009 \emph{\href{http://www.heise.de/security/news/meldung/140259}{Attacke auf SHA-1 weiter vereinfacht}}

\bibitem[3]{source} Der komplette Quellcode, der zu lang zum Abdrucken
ist, ist Teil des bigForth--Repositorys \texttt{\href{http://www.forth-ev.de/repos/bigforth/wurstkessel.fs}{http://www.forth-ev.de/repos/bigforth/wurst kessel.fs}}

\end{thebibliography}
\end{multicols}
\end{document}