%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% (c) Andreas Hofmeier
%	http://abmh.de/
%       http://an-h.de/
%       http://an-h.de.vu/
%       http://www.lgut.uni-bremen.de/an-h/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%    This document is free software; you can redistribute it and/or
%    modify it under the terms of the GNU General Public License as
%    published by the Free Software Foundation; either version 2 of
%    the License, or (at your option) any later version.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article}

%PDF \usepackage[final]{ps4pdf}

%%%%%%%%% GERMAN
\usepackage{a4,german}
%\usepackage{a4}

\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}

%%%%%%%%% GERMAN
\usepackage{ngerman}

%%%%%%%%% PDF-Latex:
%PDF \ifpdf
%PDF   \usepackage[pdftex]{graphics}
%PDF   \usepackage{ae}
%PDF   \usepackage{graphicx}
%PDF   \usepackage[
%PDF      pdftex,
%PDF      a4paper,
%PDF      bookmarks,
%PDF      bookmarksopen=true,
%PDF      bookmarksnumbered=true,
%PDF      pdfauthor={Andreas Hofmeier  --  abmh.de},
%PDF      pdftitle={AES -- Eine Einführung in Kryptographie},
%PDF %     colorlinks=true,
%PDF %     linkcolor=black,
%PDF %     filecolor=black,
%PDF %     urlcolor=black
%PDF   ]{hyperref}
%PDF \else
%PDF   \usepackage[dvips]{graphics}
%PDF \fi

%NOTPDF
  \usepackage[dvips]{graphics}
%PDF

%\usepackage[dvips]{graphics}
\usepackage{latexsym}
\usepackage{exscale}
\usepackage{amssymb,amsmath}
%\documentclass[11pt]{report}
%\usepackage{isolatin1}
%\usepackage{german}
\usepackage{epsf}
\usepackage[dvips]{rotating}

\usepackage{longtable}
\usepackage{dcolumn}

\usepackage{listings}

%\usepackage{eurosym}
%\EUR{300}

\usepackage{multicol}
%\usepackage[dvips]{rotating}

%ENDHEAD

%\parindent=0pt
%\parskip=\baselineskip

%\setcounter{tocdepth}{4}
%\setcounter{secnumdepth}{4}

\pagestyle{empty}
%\pagestyle{myheadings}
%\markright{\mbox{\bf A. Hofmeier, ...}}

\begin{titlepage}
\title{
%  \centerline{
%    \epsffile{../LSBULogo.eps}
%  }
AES -- Eine Einführung in Kryptographie}
\author{Andreas Hofmeier}
%\date{12. Mai 2003}
\date{}

\end{titlepage}


\begin{document}
\maketitle
\begin{center}
\begin{tabular}{rl}


Betreuer: &Prof. Dr. Thomas Risse\\
%%%%%%%%%%%%%%%%%%%%%%%%%%Deadline: & 13.05.2005\\
%Hand-In: & 03.04.2004\\
%\\
%Student: & Andreas Hofmeier\\
%Student ID: & 2406108\\
%Address: & Dante Road Student Residence\\
% & Room 2G3\\
% & 2 Dante Place\\
% & London SE11 4RX \\
%Tele Number: & 0870 036 5618 \\
%%eMail: & an-h@an-h.de
%\\
Studiengang: & ESTI, 7. Semester \\
Martrikelnummer: & 94453 \\
\\
\end{tabular}

\end{center}

\vspace{3cm}

\begin{abstract}
\noindent
Im ersten und zweiten Abschnitt dieses Dokumentes wird eine Übersicht über
die Grundlagen der Kryptographie gegeben. Es werden Summen-,
Permutations- und Substitutionsverfahren erklärt.
\\\\
Dieses Wissen wird im dritten Abschnitt angewendet, um AES, den neuen
Verschlüsselungsstandard, zu untersuchen.
\\\\
Der vierte Abschnitt gibt einen Überblick über grundlegende Methoden,
AES anzuwenden. Dies wird im fünften Abschnitt konkretisiert, indem
die Erstellung eines verschlüsselten Containers (Dateisystem) unter
GNU Linux beschrieben wird.
\\\\
\end{abstract}
\newpage


\tableofcontents
\setlength{\parindent}{0pt}
\setlength{\parskip}{\baselineskip}
\newpage
\setcounter{page}{1}

\pagestyle{myheadings}
% Engineering Informations Management: Standards and Specificaions: Assignment: Principle of Controlled Documentation
\markright{\mbox{\bf A. Hofmeier, AES -- Eine Einführung in Kryptographie}}

\section{Was ist Kryptographie?}

Kryptographie\footnote{Verschlüsselung, Geheimcode} bezeichnet
Verfahren, welche entwickelt wurden, um Informationen vor unbefugtem
Zugriff zu schützen. Dies ist notwendig, da es in der digitalen Welt
möglich ist, Daten ohne nennenswerten Aufwand zu vervielfältigen. Dies
hinterlässt im Allgemeinen keine Spuren an den Daten. Soll ein
öffentliches Netzwerkes zur Datenübertragung genutzt werden, ist der
Einsatz von Kryptographie anzuraten, da es nicht möglich ist, seine
Nachricht in einen Briefumschlag zu stecken.  Heutige Datennetzwerke
sind eher mit dem Versand von Postkarten zu vergleichen: Jeder, der
sich in den Weg der Postkarte (oder der Datenübertragung) einklinken
kann, ist in der Lage mitzulesen. Wie bereits erwähnt, entstehen dabei
keine Spuren an den übermittelten Daten.

Um eine Nachricht vor den Augen Neugieriger zu schützen, wandelt
Kryptographie die Nachricht mit Hilfe eines mathematischen Verfahrens
in die Chiffre\footnote{oder Geheimschrift} um. Wer die Nachricht
lesen will, muss über ein Verfahren verfügen, welches diese Umwandlung
rückgängig macht.

Soll sichergestellt werden, dass nur ein einziger Empfänger die
Nachricht lesen kann, müssen sich Sender und Empfänger ein
einzigartiges mathematisches Verfahren teilen. Es wäre sehr aufwendig,
so viele mathematische Verfahren zu entwickeln und auf Sicherheit hin
zu überprüfen. Aus diesem Grund wird das mathematische Verfahren so
gestaltet, dass es von einem weiteren Parameter abhängig ist: dem
Schlüssel. Die gleiche Nachricht, mit dem selben Verfahren aber mit
unterschiedlichen Schlüsseln verschlüsselt, führt zu verschiedenen
Chiffren. Um die Nachricht lesen zu können, muss auf der
Empfängerseinte nicht nur das Verfahren, sondern auch der Schlüssel
bekannt sein.

Diese Klasse von Verfahren wird als symmetrische Verschlüsselung
bezeichnet, da zum Ver- und Entschlüsseln derselbe Schlüssel
verwendet wird.

Von der symmetrischen Verschlüsselung wird die unsymmetrische
Verschlüsselung unterschieden. Eine weiterführende Einführung in die
Grundprinzipien der Kryptographie (symmetrische und unsymmetrische
Verschlüsselung) wird unter {\tt
http://www.abmh.de/fhs/crypt/DerTunnel/DerTunnel.PDF.pdf} gegeben.

Diese Dokument beschäftigt sich dagegen mit AES, dem Advanced
Encryption Standard, einem Standardverfahren zur symmetrischen
Verschlüsselung.




\section{Grundlegende Verfahren der Verschlüsselung}

\subsection{Summenverfahren}
\label{Summenverfahren}

Bei dem Summenverfahren werden der Klartext und der Schlüssel
aufsummiert um die Chiffre zu erhalten. Die Chiffre wird wieder lesbar
gemacht, indem der Schlüssel von der Chiffre abgezogen wird.

Beispiel:

\begin{itemize}
\item Verschlüsselung\\
Klartext ({\tt 6124627}) + Schlüssel ({\tt 4531773})

\begin{center}
\begin{tabular}{r}
$6124627$ \\
$+4531773$ \\
\hline
$10656400$ \\
\end{tabular}
\end{center}

Ergebnis: Chiffre ({\tt 10656400})

\item Entschlüsselung\\Chiffre ({\tt 10656400}) minus Schlüssel ({\tt
4531773})

\begin{center}
\begin{tabular}{r}
$10656400$ \\
$-4531773$ \\
\hline
$6124627$ \\
\end{tabular}
\end{center}

Ergebnis: Klartext ({\tt 6124627})

\end{itemize}

Das Aufsummieren von Nachrichten gestaltet sich im allgemeinem
schwieriger. Der Grund dafür ist, dass Nachrichten bzw. Daten
normalerweise nicht als ``eine Zahl'' vorliegen, sondern wesentlich
komplexere Strukturen aufweisen. So werden Nachrichten meist in
Sprache formuliert. Diese Sprache besteht aus Sätzen, welche wiederum
aus Wörtern bestehen.  Wörter ihrerseits bestehen aus Buchstaben. In
Computern werden Daten (also auch Nachrichten) auf unterster Ebene als
Byte Strings (Aneinanderreihungen von Zeichen) behandelt. Solch ein
Byte String kann mathematisch als Zahl aufgefasst werden. Praktisch
übersteigt die größer dieser Zahl schnell alle technisch handhabbaren
Dimensionen. Daher wird bei der Verschlüsselung nicht der gesamte
Byte String als Zahl betrachtet, sondern jedes Byte für sich alleine.

\newpage
Beispiel:

\begin{itemize}
\item Verschlüsselung\\
Klartext (``{\tt TREFFEN UM SIEBEN}'') + Schlüssel (``{\tt ZEBRA}'')

\end{itemize}

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_0Sum0.eps}
%\caption{}
\end{figure}


Die folgenden Annahmen werden getroffen, um die Nachricht
verschlüsseln zu können:

\begin{enumerate}

\item Jeder Buchstabe der Nachricht wird einzeln verschlüsselt.
\item Jedem Buchstabe wird aufgrund seine Position im Alphabet eine
Zahl zugeordnet: {\tt A = 0, B = 1, ... Z = 25, Freiraum = 26}.
\item Ist die Nachricht länger als der Schlüssel, wird dieser
wiederholt angewendet.

\end{enumerate}

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_0Sum1.eps}
%\caption{}
\end{figure}

Wie im Beispiel zu erkennen ist, ergeben sich bei einigen Additionen
Werte über 26. Diese können scheinbar keinem Buchstaben zugeordnet
werden. Diesem Problem wird mit Hilfe der modulo27-Operarion
abgeholfen.

%Diese Problem tritt auf, da die Menge an Buchstaben, denen Zahlen
%zugeordnet werden können, beschränkt ist. Dagegen ist die Menge der
%ganzen Zahlen nicht begrenzt.
%
%Diese Problem kann umgangen werden, indem der Zahlenraum nicht als
%unendlicher Zahlen-Strahl, sondern als begrenzter Zahlen-Kreis
%aufgefasst wird. Dieser Kreis verbindet das künstliche Ende des
%Zahlenstrahls (26) mit seinem Anfang (0).
%
%\begin{figure}[h]
%\includegraphics[width=14.52cm]{RST_AES_1Zahlen.eps}
%%\caption{}
%\end{figure}
%
%Eine Addition von 27 führt im Zahlenkreis wieder auf den
%Ausgangswert. Auf das Beispiel bezogen Heißt das, dass ab 26 mit 0
%hätte weitergezählt werden müssen. Der Schritt (1) im Beispiel
%realisiert dies mit Hilfe der modulo27-Operation. modulo27 gibt den
%(ganzzahligen) Divisionsrest der Division einer ganzer Zahlen durch
%27 zurück. Diese Operation kann nachgebebildet werden, indem sooft 27
%abgezogen wird, bis das Ergebnis kleiner als 27 ist. Nach der
%Operation (1) können alle Zahlen wieder Buchstaben zugeordnet werden.

Soll die Chiffre entschlüsselt werden, müssen die entgegengesetzten
Rechenoperationen durchgeführt werden. Im Beispiel heißt dies, den
Schlüssel von der Chiffre abzuziehen. Dazu werden den Buchstaben
erneut Zahlen zugewiesen, welche dann voneinander subtrahiert werden
können. Auch bei dieser Operation entsteht das Problem des begrenzten
Zeichenvorrats, dem wieder durch modulo27 abgeholfen wird.

%Diese
%Operation (2) kann nachgebildet werden, indem solange 27 zu dem
%Ergebnis hinzuaddiert wird, bis dieses größer als 0 ist.

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_0Sum2.eps}
%\caption{}
\end{figure}

%Der begrenzte Zahlenraum ist nicht nur eine Annahme in diesem
%abstrakten Beispiel, sondern eine zentralen Einschränkung jeder
%Rechenmaschine. So basieren alle heutigen Computer auf Bits, welche
%als Zahlenraum von 0 und 1 aufgefasst werden können.
%
%Diese Bits können zusammengefasst werden, um größere Zahlenräume
%(komplexere Sachverhalte) darzustellen. Werden acht Bit zu einem Byte
%zusammengefasst, sind $2^8 = 256$ verschiedene Zahlen
%darstellbar. Diese werden im so genannten ASCII-Zeichensatz
%verschiedenen Zeichen (Buchstaben, Zahlen und Sonderzeichen)
%zugeordnet. Aus diesen Zeichen können nun wieder Texte (Nachrichten)
%komponiert werden.
%
%Computer arbeiten von Haus aus mit diesen beschränkten
%Zahlenräumen. Wird auf einem 8-Bit-Rechner die Zahl 254 mit der Zahl 4
%addiert, so ist das Ergebnis 2 und nicht wie erwartet 258. Der Grund
%dafür ist, dass jedes Rechenwerk mit einem begrenztem Zahlenraum
%arbeitet. Dieser kann als Zahlenkreis aufgefasst werden. Um
%mitzuteilen, dass der Zahlenraum überschritten wurde, setzt das
%Rechenwerk im allgemeinem ein Überlauf-Bit. Diese Rechenwerke haben
%die Eigenschaft, dass Berechnungen auch dann zum Richtigen Ergebnis
%führen, wenn Zwischenergebnisse den Begrenzte Zahlenraum
%verlassen. Das Ergebnis muss sich allerdings wieder im Zahlenraum
%darstellen lassen.

\newpage
Das folgende Beispiel zeigt, wie jedes Bit eines Bytes einzeln addiert
wird. Es wird also nicht die gesamte Zahl, bestehend aus acht Bit,
addiert, sondern die Bits unabhängig voneinander:

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_2XOR.eps}
%\caption{}
\end{figure}

Auf Grund der Symmetrie ist die Rechenoperation (1) und (2) in diesem
Beispiel identisch. Die Addition zweier Bits mit anschließender
Operation (1) ist eine weitläufig bekannte Rechenoperation in
Computern: Die XOR oder Exklusiv-Oder-Operation. XOR kommt auch
heutzutage bei Verschlüsselung sehr häufig zum Einsatz.


\newpage
\subsection{Permutationsverfahren}
\label{Permutationsverfahren}

Das Permutationsverfahren stellt eine weitere Möglichkeit dar,
Nachrichten zu verschlüsseln. Bei diesem Verfahren werden die
Positionen der Zeichen verändert, nicht aber die Zeichen selber. Dies
kann beispielsweise erreicht werden, indem die Nachricht von rechts
nach links und von oben nach unten in eine Matrix geschrieben wird und
danach von oben nach unten und von rechts nach links wieder
herausgelesen wird.

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_3Matrix.eps}
%\caption{}
\end{figure}

Natürlich sind alle möglichen Formen von ``Matrizen'' und Aus-
bzw. Einlesemustern vorstellbar. Deters (2002) beschreibt zum Beispiel
eine historische Anwendung dieses Verfahrens: Die Regierung von Sparta
zur hat bereits 500 v. Chr. mit Hilfe eines Holzstabes (Skytale)
verschlüsselt. Die Nachricht wurde vom Sender der Länge nach auf einen
mit einem Pergamentsteifen umwickelten Holzstab geschrieben. Danach
wurde das Pergament abgewickelt, nochmals abgeschrieben und
versandt. Der Empfänger musste nun die empfangene Nachricht auf einen
Pergamentstreifen schreiben und diesen um einen Holzstab mit dem
richtigen Durchmesser wickeln, um die Nachricht zu entschlüsseln.

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_3Skytale.eps}
%\caption{}
\end{figure}

Beispiel einer historischen Verschlüsselung. Übernommen von Deters
(2002).


\subsection{Substitutionsverfahren}
\label{Substitutionsverfahren}

Das Substitutionsverfahren ersetzt Elemente der Nachricht nach
bestimmten Regeln gegen andere Elemente. Deters (2002) führt hier das
älteste bekannte Beispiel einer Verschlüsselung auf: die
Cäsar-Chiffre. Diese Methode ist nach Cäsar benannt. Er schrieb das
Alphabet zweimal untereinander, wobei er es beim zweiten Mal um drei
Buchstaben nach rechts einrückte. (Das Lateinischen Alphabet verfügt
nicht über die Buchstaben J, K, W, Y und Z.):

{\tt A B C D E F G H I L M N O P Q R S T U V X}\\
{\tt U V X A B C D E F G H I L M N O P Q R S T}
\begin{flushright}
Übernommen von Deters (2002).
\end{flushright}

Um eine Nachricht zu verschlüsseln, werden alle Zeichen der
Nachricht durch das korrespondierende Zeichen ersetzt:

{\tt TREFFEN UM SIEBEN} $\leftarrow$ Klartext\\
{\tt QOBCCBI RH PFBVBI} $\leftarrow$ Chiffre\\










\section{Advanced Encryption Standard (AES)}

\subsection{Geschichte und Anforderungen an AES}

AES ist der in einem öffentlichen Auswahlverfahren vom
NIST\footnote{U.S. National Institute of Standards and Technology
(www.nist.gov)} bestimmte Nachfolger von DES (Data Encryption
Standard). Ein neuer Standard für Datenverschlüsselung wurde
notwendig, da es laut Wilkin (2004) der Electronic Frontier Foundation
1998 gelungen war, eine Maschine zu bauen, die DES mittels einer
Brute-Force-Attack aushebeln konnte.  Im Gegensatz zu DES war die
Auswahl von AES vollständig öffentlich. Jeder Interessierte konnte
seinen Vorschlag in Form eines Verschlüsselungsalgorithmus einschicken
oder sich an dem Test der Algorithmen beteiligen. Die NIST suchte den
besten Algorithmus aus, wobei folgende Kriterien in Betracht gezogen
wurden:

\begin{enumerate}

\item Sicherheit\\Hierbei handelte es sich um das wichtigste
Auswahlkriterium. Es sollten keine Algorithmen verwendet werden, die
mit einem bekannten Verfahren schneller als mit
Brute-Force-Attack\footnote{Bei dieser Form der Attacke werden alle
möglichen Passwörter durchprobiert. Ist das Password zufällig gewählt,
müssen im Mittel die Hälfte aller Passwörter durchprobiert werden, um
es zu finden. Einfachere Passwörter, wie Wörter aus einem Wörterbuch,
können mit dem durchprobieren aller bekannten Wörter schneller
gefunden werden als Zufallsstrings.}  ausgehebelt werden konnten. Es
ist allerdings nicht möglich nachzuweisen, dass ein Algorithmus sicher
ist. Nur das Gegenteil kann bewiesen werden.

\item Kosten

\begin{itemize}

\item Der Algorithmus sollte vollkommen (kosten-) frei verwendbar
sein. (frei von Patent- oder anderen Ansprüchen der Entwickler)

\item Die Implementierung und das Ver- bzw. Entschlüsseln sollte so
billig wie möglich sein.

\end{itemize}

\item Eigenschaften der Implementierung

\begin{itemize}

\item Der Algorithmus sollte sowohl in Hardware als auch in Software
mit geringsten möglichen Mitteln umgesetzt werden können, also
{\mbox Platform\-unabhängig} gestaltet sein.

\item Die Schlüssellänge sollte zwischen 128, 192 und 256 Bit gewählt
werden können.

\item Die Blockgröße sollte 128 Bit betragen.

\item Das Verfahren sollte einfach und verständlich sein.

\end{itemize}

\end{enumerate}



\subsection{Kandidaten und Auswahlverfahren}

Die folgende Tabelle gibt eine Übersucht über alle Algorithmen, welche
für den neuen Verschlüsselungsstandard AES vorgeschlagen wurden, von
wem sie vorgeschlagen wurden und in welcher Runde sie ausgeschieden
sind.

\begin{tabular}{|l|l|l|l|l|}
\hline
Name & eingereicht von & & ausge. Runde \\
\hline
CAST-256 & Entrust (CA) & Company & 1$^1$ \\
Crypton & Future Systems (KR) & Company & 1$^2$ \\
DEAL & Outerbride, Knudsen (USA-DK) & Forscher & 1$^{sp}$ \\
DFC & ENS-CNRS (FR) & Forscher & 1$^3$ \\
E2 & NTT (JP) & Company & 1$^4$\\
Frog & TecApro (CR) & Company & 1$^s$ \\
HPC & Schroeppel (USA) & Forscher & 1$^s$ \\
LOKI97 & Brown et al. (AU) & Forscher & 1$^s$ \\
Magenta & Deutsche Telekom (DE) & Company & 1$^{sp}$ \\
Mars & IBM (USA) & Company & 2 \\
RC6 & RSA (USA) & Company & 2 \\
Rijndael & Daemen and Rijmen (BE) & Forscher & WINNER \\
SAFER+ & Cylink (USA) & Company & 1$^p$ \\
Serpent & Anderson, Biham, Kundsen (UK-IL-DK) & Forscher & 2 \\
Twofish & Counterpane (USA) & Company & 2 \\
\hline
\end{tabular}
\begin{flushright}
Adaptiert von Daemen und Rijmen (2002).
\end{flushright}

1) Ausgeschieden in der ersten Runde. Auswahl der fünf Finalisten im März 1999.\\
2) Ausgeschieden in der zweiten Runde, Endausscheidung am 2. Oktober 2000\\
$^s$) Ausscheidung wegen massiver Sicherheitsprobleme\\
$^p$) Ausscheidung wegen massiver Leistungsprobleme\\
$^1$) Vergleichbar mit Serpent, Implementation aufwendiger.\\
$^2$) Vergleichbar mit Rijndael und Twofish aber unsicherer.\\
$^3$) Geringe Sicherheit, schlechte Performance außer auf 64-Bit Prozessoren.\\
$^4$) Vergleichbar mit der Struktur von Rijndael und Twofish,
aufwendigere Implementation\\

Alle Kandidaten mussten bis zum 15. Mai 1998 eingereicht werden. Am
20. August begann dann die erste Runde, welche im März 1999 mit der
Auswahl der fünf Finalisten endete. Am 2. Oktober 2000, nach einer
weiteren Auswahl-Runde, wurde schließlich der Gewinner gekürt:
Rijndael. Von nun an als AES bezeichnet. Dieser Algorithmus wurde Joan
Daemen und Vincent Rijmen, zwei belgischen Wissenschaftlern, als
Kandidat für die AES-Ausschreibung entwickelt.

Viele Beobachter waren darüber erstaunt, dass ein Algorithmus gewonnen
hat, der weder aus den USA stammt noch von einer Firma aus dem
Verschlüsselungsgeschäft entwickelt wurde. Von vielen Seiten wurde aus
diesem Grund auf ein objektives Auswahlverfahren geschlossen, welches
am Schluss den besten Algorithmus zum Gewinner kürte.

\subsection{Aufbau}

Die grundlegende Struktur des AES-Algorithmus ist in der folgenden
Weise aufgebaut:

\label{}
{\tt\footnotesize
\begin{lstlisting}
Rijndael(Data, Key) {
  KeyExpansion(Key, ExpandedKey);
  AddRoundKey(Data, ExpandedKey[0]);
  for (i = 0; i < N; i++) {
    Round(Data, ExpandedKey[i]);
  }
  FinalRound(Data, ExpandedKey[N]);
)

Round(Data, ExpandedKey) {
  SubBytes(Data);
  ShiftRows(Data);
  MixColums(Data);
  AddRoundKey(Data, ExpandedKey);
}

FinalRound(Data, ExpandedKey) {
  SubBytes(Data);
  ShiftRows(Data);
  AddRoundKey(Data, ExpandedKey);
}
\end{lstlisting}
}
\begin{flushright}
Adaptiert von Daemen und Rijmen (2002).
\end{flushright}


Daemen und Rijmen (2002) betrachten Blöcke in der folgenden
Weise. Es werden jeweils vier Bytes von oben nach unten
geschrieben. Beim fünften Byte wird nach rechts weitergegangen und
wieder oben angefangen.

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_6Aufb1Block.eps}
%\caption{}
\end{figure}

In der folgenden graphischen Darstellung wird von einer Blockgröße von
128 Bit ausgegangen. Die Blöcke ließen sich allerdings in
Vier-Byte-Schritten (32 Bit) bis auf 256 Bit ausweiten. Dasselbe gilt
für den Schlüssel. Daten-Blockgröße und Schlüssel-Block-Größe sind
vollkommen unabhängig voneinander. Im AES-Standard sind allerdings
lediglich Datenblockgrößen von 128 Bit und Schlüsselblocklängen von
128, 192 und 256 Bit vorgesehen. Dies ändert nichts daran, dass der
Rijndael-Algorithmus mehr kann, was aber nicht notwendiger
implementiert sein muss, wenn auf AES Bezug genommen ist.

Die graphische Darstellung verdeutlicht den Fluss der Daten:

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_6Aufb0Over.eps}
%\caption{}
\end{figure}
\begin{flushright}
Adaptiert von Daemen und Rijmen (2002).
\end{flushright}


\subsubsection{Anzahl der Runden}

Wie oben ersichtlich, wird die Funktion {\tt Round()} N mal
ausgeführt. Wobei N von der Schlüssel- und der Daten-Block-Größe
abhängt. Die folgende Tabelle stellt die Länge des Schlüssels der
Länge des Datenblockes gegenüber und gibt für jede Kombination eine
Anzahl von Runden an. Alle fett dargestellten Fälle sind durch den
AEStandard definiert. Die restlichen Fälle werden von Rijndael
unterstützt, sind aber im Standard nicht definiert.

\begin{tabular}{|c||c|c|c|c|c|}
\hline
 & \multicolumn{5}{c|}{Länge des Schlüssels} \\
Länge des Datenblockes & {\bf 128} & 160 & {\bf 192} & 224 & {\bf 256} \\
\hline
\hline
{\bf 128} & {\bf 10} & 11 & {\bf 12} & 13 & {\bf 14} \\
     160  &      11  & 11 &      12  & 13 &      14 \\
     192  &      12  & 12 &      12  & 13 &      14  \\
     224  &      13  & 13 &      13  & 13 &      14 \\
     256  &      14  & 14 &      14  & 14 &      14  \\
\hline
\end{tabular}

\subsubsection{Verwendung des Schlüssels: {\tt KeyExpansion()}, {\tt AddRoundKey()}}

Vor der ersten und nach jeder Runde wird der Datenblock mit einem
gleich großen Schlüsselblock ge{\tt XOR}t. Dies wird mit Hilfe der
Funktion {\tt AddRoundKey()} durchgeführt. Die XOR-Funktion kann als
eine Form des Summenverfahrens angesehen werden, welche im Abschnitt
\ref{Summenverfahren} behandelt wurde. 

Die Funktion {\tt KeyExpansion()} wurde implementiert, um den
Schlüssel auf die richtige Länge zu erweitern. Denn sowohl der
Schlüssel als auch der Datenblock können verschiedene, voneinander
unabhängige, Längen aufweisen. Die Funktion erweitert die Länge des
Schlüssels auf (Runden + 1) * Daten-Blockgröße, da vor der ersten und
nach jeder Runde einmal ein Teil-Schlüssel von der Länge des
Datenblockes gebraucht wird. Die hinzugefügten Bytes werden durch ein
reproduzierbares mathematisches Verfahren erzeugt, welches recht
unvorhersagbare vom Schlüssel abhängige Werte liefert. Diese Funktion
kann mit einem Pseudo-Zufallszahlen-Generator verglichen
werden. Derselbe Startwert führt immer zu der selben Abfolge von
Zahlen, welche aber möglichst zufällig sein soll. So wird ein
128-Bit-Schlüssel auf den richtigen Wert (Hier: (Runden + 1) *
Daten-Blockgröße) erweitert:

{\tt\footnotesize
\begin{lstlisting}
00000000,00000000,00000000,00000000
62636363,62636363,62636363,62636363
9b9898c9,f9fbfbaa,9b9898c9,f9fbfbaa
90973450,696ccffa,f2f45733,0b0fac99
ee06da7b,876a1581,759e42b2,7e91ee2b
7f2e2b88,f8443e09,8dda7cbb,f34b9290
ec614b85,1425758c,99ff0937,6ab49ba7
21751787,3550620b,acaf6b3c,c61bf09b
0ef90333,3ba96138,97060a04,511dfa9f
b1d4d8e2,8a7db9da,1d7bb3de,4c664941
b4ef5bcb,3e92e211,23e951cf,6f8f188e
      Uebernommen von Daemen und Rijmen (2002) und van Rees (2005)
\end{lstlisting}
}
%\begin{flushright}

%\end{flushright}


Der hier aufgeführte erweiterte Schlüssel entsteht, wenn der
übergebende Schlüssel aus Nullen (alle Bits sind Null) besteht.

Den Autor hat es verwundert, dass der Schlüssel nicht verwendet wurde,
um die verändernden Funktionen ({\tt SubBytes()}, {\tt ShiftRows()}
und {\tt MixColums()}) direkt zu steuern. Stattdessen werden diese
Funktionen immer in der gleichen Weise auf den Datenstrom
abgewendet. Die Abhängigkeit vom Schlüssel wird über die Funktion {\tt
AddRoundKey()} eingeführt.


\subsubsection{Permutationsschritt: {\tt ShiftRows()}}


Die Funktion {\tt ShiftRows()} wendet ein Permutationsverfahren
(siehe Abschnitt \ref{Permutationsverfahren}) auf den Datenstrom an.
In diesem Fall wird der Block zeilenweise betrachtet. Bis auf die
oberste wird jede Zeile um n Spalten nach links verschoben. Die
Weite der Verschiebung hängt von der Blockgröße und der Zeile ab.

Die folgende Tabelle stellt die (Daten)Blockgröße mit den Zeilen
gegenüber und gibt für jede Paarung einen Wert für die
Linksverschiebung an. Im AEStandard ist lediglich der Fall des
128-Bit-Blocks definiert. Da der Rijndael-Algorithmus mit größeren
Blöcken umgehen kann, ist dies hier ebenfalls aufgeführt.

\begin{tabular}{|c||c|c|c|c|c|}
\hline
 & \multicolumn{5}{c|}{Länge des Datenblockes} \\
Zeile & {\bf 128} & 160 & 192 & 224 & 256 \\
\hline
\hline
1 & {\bf 0} & 0 & 0 & 0 & 0 \\
2 & {\bf 1} & 1 & 1 & 1 & 1 \\
3 & {\bf 2} & 2 & 2 & 2 & 3 \\
4 & {\bf 3} & 3 & 3 & 4 & 4 \\
\hline
\end{tabular}

Die folgende Graphik versucht dies am Beispiel eines 128Bit Blockes zu
verdeutlichen.

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_7ShiftRow.eps}
%\caption{}
\end{figure}

Die inverse Funktion ({\tt InvShiftRows()}) schiebt die Zeilen um die
gleiche Anzahl von Bytes in die entgegengesetzte Richtung.




\subsubsection{Substitutionsschritt 1: {\tt SubBytes()}}

Die Funktionen {\tt SubBytes()} und {\tt MixColums()} wenden eine Form
von Substitutionsverfahren (siehe Abschnitt
\ref{Substitutionsverfahren}) auf den Datenstrom an. Es besteht jedoch
ein grundlegender Unterschied zu den in Abschnitt
\ref{Substitutionsverfahren} beschriebenden
Substitutionsverfahren. Die Substitution wird nicht wie beschrieben
durch den Schlüssel bestimmt, sondern ist fest vorgegeben. Wie bereits
erwähnt, wird die Abhängigkeit vom Schlüssel durch die XOR-Schritte
bewirkt.

{\tt SubBytes()} verarbeitet jedes Byte im Datenblock einzeln.

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_8SubBytes.eps}
%\caption{}
\end{figure}
\begin{flushright}
Adaptiert von Daemen und Rijmen (2002).
\end{flushright}

Es wird ein ``Alphabet'' von mit 256 ($2^8$ da 8Bit) Symbolen
verwendet. Jedes der Symbole wird durch ein anderes Symbol (ebenfalls
Teil des Alphabets) ersetzt. Dies Substitution ist durch den
folgenden mathematischen Zusammenhang bestimmt:

Zuerst werden die Bits ($a_7$ bis $a_0$) in dem Byte (a) als Polynom betrachtet:

$a = a_7a_6a_5a_4a_3a_2a_1a_0 \ne 0$ $\Rightarrow$ $f(x) = a_7x^7 +
a_6x^6 + a_5x^5 + a_4x^4 + a_3x^3 + a_2x^2 + a_1x^ + a_0$

Danach wird die Inverse dieses Polynoms gebildet. Diese Operation
wird in $GF(2^8) = GF(256)$ ausgeführt.

$g(x) = f(x)^{-1}$

Dann wird das so gewonnene Polynom wieder in ein Byte zurückgewandelt:

$g(x) = b_7x^7 + b_6x^6 + b_5x^5 + b_4x^4 + b_3x^3 + b_2x^2 + b_1x^ + b_0$ $\Rightarrow$ $b = b_7b_6b_5b_4b_3b_2b_1b_0$

Für den nicht definierten Fall, dass a gleich 0 ist, wird angenommen,
dass b ebenfalls 0 ist.

Danach werden die Bits des Bytes als Vektor betrachtet und der
folgenden Vektor-Matrix-Multiplikation mit anschließendem XOR
unterzogen:

$c = \left[ \begin{matrix} c_7 \\
c_6\\
c_5\\
c_4\\
c_3\\
c_2\\
c_1\\
c_0
\end{matrix} \right] = \left[ \begin{matrix} 1&1&1&1&1&0&0&0 \\
0&1&1&1&1&1&0&0\\
0&0&1&1&1&1&1&0\\
0&0&0&1&1&1&1&1\\
1&0&0&0&1&1&1&1\\
1&1&0&0&0&1&1&1\\
1&1&1&0&0&0&1&1\\
1&1&1&1&0&0&0&1
\end{matrix} \right]
\times \left[ \begin{matrix} b_7 \\
b_6\\
b_5\\
b_4\\
b_3\\
b_2\\
b_1\\
b_0
\end{matrix} \right] \oplus \left[ \begin{matrix} 0\\
1\\
1\\
0\\
0\\
0\\
1\\
1
\end{matrix} \right]
$


Die {\tt InvSubBytes()} macht den so eben beschriebenen Vorgang
rückgängig. Dazu wird zuerst die Vektor-Matrix-Multiplikation mit
anschließendem XOR invertiert durchgeführt:

$b = \left[ \begin{matrix} b_7 \\
b_6\\
b_5\\
b_4\\
b_3\\
b_2\\
b_1\\
b_0
\end{matrix} \right] = \left[ \begin{matrix} 0&1&0&1&0&0&1&0 \\
0&0&1&0&1&0&0&1\\
1&0&0&1&0&1&0&0\\
0&1&0&0&1&0&1&0\\
0&0&1&0&0&1&0&1\\
1&0&0&1&0&0&1&0\\
0&1&0&0&1&0&0&1\\
1&0&1&0&0&1&0&0
\end{matrix} \right]
\times \left[ \begin{matrix} c_7 \\
c_6\\
c_5\\
c_4\\
c_3\\
c_2\\
c_1\\
c_0
\end{matrix} \right] \oplus \left[ \begin{matrix} 0\\
0\\
0\\
0\\
0\\
1\\
0\\
1
\end{matrix} \right]
$

Danach wird das Ergebnis als Polynom betrachtet und
invertiert. Dieser Schritt führt auf das originale a zurück.

Im Allgemeinen ist das Nachschlagen eines Wertes schneller als das
Errechnen des selbigen. Dies trifft jedenfalls zu, wenn die Tabelle
relativ klein ist. Dieses Vorgehen ist ebenfalls eine bei der
Implementierung von AES angewendete Alternative zu der eben
beschriebenen Rechnung. Denn die Tabelle besteht aus lediglich 256
($2^8$) Einträgen. Praktisch kann die Liste in diesem Fall mit Hilfe
eines 256 Byte langen Arrays dargestellt werden. Dazu wird an der
jeweiligen Position im Array das zugehörige Ergebnis
gespeichert. Wenn, zum Beispiel, die oben beschriebende mathematische
Transformation mit einer Eingabe von 2 zu dem Ergebnis 119 führt, so
steht an der dritten Stelle des Arrays eine 119. (Es handelt sich um
die dritte Stelle, da im Computerbereich bei 0 angefangen wird zu
Zählen.) Heiße das Array S, so ergibt sich folgender Zusammenhang:

\label{}
{\tt\footnotesize
\begin{lstlisting}
output = S[input];
\end{lstlisting}
}

Wenn die Variable {\tt input} mit 2 initialisiert wurde, steht nach
dem Aufruf dieser Zeile 119 in {\tt output}. Im Allgemeinen wird
dieses Verfahren als Look-Up-Table bezeichnet. Die inverse
Transformation funktioniert entsprechend, nur dass das entsprechende
Array verwendet wird.

\subsubsection{Substitutionsschritt 2: {\tt MixColums()}}

{\tt MixColums()} wird jeweils auf 4-Bytes-Spalte angewendet. Wird
diese Funktion als Substitution betrachtet, besteht das ``Alphabet''
aus 4 294 967 296 ($= 2^{32} = 2^{4*8}$) Symbolen. Bei dieser Menge an
Symbolen ist an eine Verwendung einer Tabelle nicht mehr zu denken.

Die Umwandlung in diesem Schritt ist durch eine
Matrix-Vektor-Multiplikation bestimmt. In diesem Fall wird ein
Vektor von 4 Bytes mit einer Matrix von 4 $\times$ 4 Bytes
Multipliziert:

$b = \left[ \begin{matrix} b_{0,i} \\
b_{1,i}\\
b_{2,i}\\
b_{3,i}
\end{matrix} \right] = \left[ \begin{matrix} 02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02
\end{matrix} \right]
\times \left[ \begin{matrix} a_{0,i} \\
a_{1,i}\\
a_{2,i}\\
a_{3,i}
\end{matrix} \right]
$

Wobei $i$ der zu verarbeitenden Spalte entspricht. Im Falle eines 128
Bit Blockes sind vier Spalten zu verarbeiten.

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_9MixColums.eps}
%\caption{}
\end{figure}
\begin{flushright}
Adaptiert von Daemen und Rijmen (2002).
\end{flushright}

Um diese Umwandlung rückgängig zu machen, wurde die Funktion {\tt
InvMixColums()} entwickelt, die folgende mathematische Operation
ausführt:


$a = \left[ \begin{matrix} a_{0,i} \\
a_{1,i}\\
a_{2,i}\\
a_{3,i}
\end{matrix} \right] = \left[ \begin{matrix} 02 & 03 & 01 & 01 \\
0E & 0B & 0D & 09 \\
09 & 0E & 0B & 0D \\
0B & 0D & 09 & 0E
\end{matrix} \right]
\times \left[ \begin{matrix} b_{0,i} \\
b_{1,i}\\
b_{2,i}\\
b_{3,i}
\end{matrix} \right]
$

Die hier verwendete Matrix kann durch invertieren der in {\tt
MixColums()} verwendeten Matrix errechnet werden.

\subsubsection{Entschlüsselung}

Um die verschlüsselten Daten wieder in die Ausgangsdaten zurück zu
wandeln, wird folgendermaßen vorgegangen: Die Reihenfolge der Schritte
wird umgekehrt. Bei jedem Schritt wird der invertierende Schritt
angewendet. Zum Beispiel {\tt Inv\-Mix\-Colums()} statt {\tt
MixColums()}. Die folgende Graphik versucht dies deutlich zu machen
und stellt dazu den Ver- und Entschlüsselungsprozess gegenüber.

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_EntSchl.eps}
%\caption{}
\end{figure}
\begin{flushright}
Adaptiert von Daemen und Rijmen (2002).
\end{flushright}

Es wurde gerade davon gesprochen, alle Schritte in umgekehrter
Reihenfolge abzuarbeiten. In der Graphik wurden aber zwei Schritte
nicht vertauscht. Warum?

Es handelt sich um die letzten beiden Schritte bei der Verschlüsselung
oder um die ersten beiden bei der Entschlüsselung: {\tt ShiftRows()}
und {\tt SubBytes()}, bzw, {\tt InvShiftRows()} und {\tt
InvSubBytes()}. Dies kann ganz einfach erklärt werden: Es macht keinen
Unterschied, ob diese beiden Schritte getauscht sind oder nicht. {\tt
SubBytes()} wird auf jedes Byte einzeln angewendet, daher spielt es
keine Rolle, ob {\tt ShiftRows()} die Bytes vorher oder nachher
verschiebt. Diese und andere hier nicht erwähnte Möglichkeiten, die
Reihenfolge von Operationen zu vertauschen, werden zur Optimierung der
Implementation verwendet.





\newpage
\section{Anwendung grundlegender Modi auf AES}

AES verschlüsselt ``nur'' 128-Bit-Blöcke. Nur welche Nachrichten
bzw. Dateien sind schon 128 Bit (16 Byte) lang?

\subsection{ECB -- Electronic Code Book}

Es gibt die Möglichkeit, die zu verschlüsselnde Datei oder Nachricht
in 128-Bit-Blöcke aufzuteilen. Wird AES auf jeden dieser Blöcke
unabhängig angewendet, so nennt man dies das elektronische Code-Buch
Verfahren (engl. ECB -- Electronic Code Book):

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_M0ECB.eps}
%\caption{}
\end{figure}

Diese Unabhängigkeit der Blöcke führt dazu, dass identische
Klartext-Blöcke bei der Verschlüsselung die selben Chiffre-Blöcken
ergeben. Die Verschlüsselung könnte als eine Form der Substitution
vergleichen werden, nur dass das Alphabet in diesem Fall über
$340282366920938463463374607431768211456 = 2^{128} \approx 3.4 *
10^{38}$ Symbole verfügt. Es wäre also von der Kapazität her nicht
möglich, einer Liste mit dieser Menge an Einträgen zu
verwalten. Allerdings ist es möglich, häufig auftretende gleiche
Blöcke zu identifizieren. Dies ist ein möglicher Angriffspunkt auf die
Verschlüsselung.



\subsection{CBC -- Cipher Block Chaining}

Um diesem Effekt vorzubeugen, werden die Blöcke im CBC-Mode
voneinander abhängig gemacht. Dies geschieht, indem der Input vor der
Verschlüsselung mit dem Output der vorherigen Verschlüsselung geXORt
wird:

\begin{figure}[h]
\includegraphics[width=14.52cm]{RST_AES_M1CBC.eps}
%\caption{}
\end{figure}

Die Chiffre vom aktuellen Klartextblock ist in diesem Fall nicht nur
vom Klartextblock und dem Passwort abhängig, sondern zusätzlich vom
vorherigen Chiffre-Block. Dieser wiederum ist seinerseits wieder
abhängig vom Passwort, vom Klartextblock und vom vorherigen
Chiffre-Block. Der erste Chiffre-Block ist seinerseits vom Passwort,
dem Klartext-Block und dem IV abhängig. Der IV (Initial Vector) ist
ein Anfangswert, welcher als Ersatz für den vorherigen Block mit dem
Klartext geXORt wird. Die letzte Chiffre ist allerdings vom Password
und von allen vorherigen und dem letzten Klartext abhängig. Aus diesem
Grund könnte die letzte Chiffre auch als HASH-Wert des Datenstromes
betrachtet werden.



Nachteile dieser beiden Lösungen sind, dass 

\begin{itemize}

\item die Länge der Nachricht immer ein Vielfaches der Blockgröße
sein muss. Ist dies nicht der Fall, muss der letzte Block aufgefüllt
(engl. padding) werden. Bei einer Blockgröße von 16 Byte müssten
maximal 15 Bytes aufgefüllt werden, was in den meisten Fällen ein
vertretbarer Wert ist.

\item die Nachricht immer vollständig bis zu dem gewünschten Block
entschlüsselt werden muss. Soll, zum Beispiel, nur der letzte Block
einer Datei gelesen werden, muss trotzdem die gesamte Datei
entschlüsselt werden. Natürlich muss die Datei zu diesem Zweck
vollständig vorliegen. Ist ein Block der Datei beschädigt, sind dieser
und alle folgenden Blöcke unlesbar.

\end{itemize}

\subsection{Key Stream Generators}

Ein andere Möglichkeit ist, den Verschlüsselungsalgorithmus zu
verwenden, um einen Schlüsselstrom zu erzeugen. Die zu verschlüsselnden
Daten werden danach mit diesem Schlüsselstrom geXORt und somit
verschlüsselt:

%\begin{figure}[h]
\begin{center}
\includegraphics[width=12.4cm]{RST_AES_M2KeyStream.eps}
\end{center}
%\caption{}
%\end{figure}

Vorteil dieser Variante ist, dass die Länge der Nachricht kein
Vielfaches von der Blockgröße sein muss. Denn der letzte Block muss
nicht vollständig sein. Ist der Block nur ein Byte lang, so kann
dieses Byte mit dem ersten Byte aus dem aktuellen Keystream-Block
verschlüsselt werden. Die restlichen Bytes des Keystream-Blocks
bleiben dabei einfach ungenutzt.




\section{Konkrete Anwendung: Crypto-LOOP-Driver in Linux}

Der Loop\footnote{Das Wort ``Loop'' kommt aus dem Englischen und
bedeutet soviel wie Schleife.}-Driver unter Linux wurde entwickelt, um
normale Dateien oder andere Blockdevices\footnote{Schnittstelle zum
Zugriff auf blockorientierte Geräte wie Disketten, Festplatten
(Partitionen), CD-ROMs, etc. Blockorientiert bedeutet, dass nur
Blockweise auf diese Geräte zugegriffen werden kann.} als virtuelle
Blockdevices abzubilden. Dies ist notwendig, wenn ein
Image\footnote{Ein Image ist eine Abbildung eines Blockgerätes
(z.B. einer Partitionen) in Form einer Datei im Dateisystem}
gemountet\footnote{Mounten bezeichnet den Vorgang des Verbindens eines
Dateisystems auf einem Blockdevice mit einem Verzeichnis. Z.B. Mounten
einer Diskette nach /mnt: {\tt mount /dev/fd0 /mnt}} werden soll. Auf
Grund der blockorientierten Struktur kann eine Datei nicht direkt
gemountet werden.

Die folgende Graphik versucht diesen Zusammenhang nochmals zu
verdeutlichen. 

%\begin{figure}[h]
\begin{center}
\includegraphics[width=12.4cm]{RST_AES_O0Loop.eps}
\end{center}
%\caption{}
%\end{figure}
Auf der linken Seite ist die ``normale'' Zugriffsstruktur abgebildet:
Der Anwender greift auf das Dateisystem zu, welches in ein Verzeichnis
gemountet ist. Das Dateisystem seinerseits verwendet die Blockdevices
als Schnittstelle zur Hardware. Rechts wurde diese Struktur um ein
virtuelles Blockdevice (Loop-Device) erweitert. Das Dateisystem,
welches auf das virtuelles Blockdevice zugreift, sieht keinen
Unterschied zu einem ``normalem'' Blockdevice (Außer den Namen: {\tt
/dev/loop}). Dieses virtuelles Blockdevice kann seinerseits auf ein
anderes Blockdevice oder auf eine Datei in einem bereits gemounteten
Dateisystem zugreifen. Der erste Fall scheint auf den ersten Blick
sinnlos zu sein. Dies ist er allerdings ganz und gar nicht, da der
Loop-Treiber noch ein bisschen mehr leisteten kann, als ein
Blockdevice zu emulieren. Es kann nämlich ein Offset\footnote{Der
Anfang (Null Position) von {\tt /dev/loop} ist in der verbundenen
Datei (oder Blockdevice) nicht null, sondern um {\tt n} Bytes
verschoben.} schalten und verschlüsseln. Im folgenden wird auf die
zweite Erweiterung näher eingegangen.


\subsection{Eigenschaften des Crypto-LOOP-Drivers}

Der Crypto-Loop-Driver arbeitet mit einer Blockgröße von 512
Bytes. Soll ein Dateisystem verwendet werden, welches kein Vielfaches
dieser Blockgröße verwendet, sind Performanceeinbußen zu erwarten. Das
selbe gilt, wenn Offsets kein Vielfaches von 512 sind.

Auf jeden 512-Byte Block wird der Verschlüsselungsalgorithmus im
CBC-Mode unabhängig angewendet. Seit dem Kernel 2.6 ist AES im
Loop-Treiber offiziell integriert. 

%Schon fast ironisch klingt es, dass das gerade erst offiziell aufgenommende Loop-Crypt durch dm-crypt ersetzt werden soll. 

Bei der Verwendung von Journaling Dateisystemen mit Crypto-Loop ist
Vorsicht geboten, da Schreibzugriffe möglicherweise nicht sofort
durchgeleitet werden. Dies wird von einem Journaling Dateisystemen
aber normalerweise gefordert. Es gibt allerdings die Möglichkeit, dieses
Problem zu umgehen. Bei den weiter unten beschriebenen Versuchen wurde
tatsächlich festgestellt, dass Daten auch nach einem {\tt
sync}\footnote{Befehl um das schreiben aller vom Dateisystem
gepufferten Daten zu erzwingen} nicht immer sofort zurückgeschrieben
wurden. Das Problem liegt hierbei in der mehrfach gepufferten
Struktur, denn gepuffert wird vom Dateisystem und vom
Crypto-Loop-Treiber.

Um maximale Geschwindigkeit zu erreichen, wurde der AEStandard für
Intel x86 und AMD64 Prozessoren in Assembler implementiert. Diese
Optimierung kann allerdings nur auf diesen beiden Prozessoren
verwendet werden. Wird Linux auf einer anderen Plattform übersetzt,
wird der ``normale'' C-Code compiliert.

\subsection{Installation}

Wie bereits erwähnt, wurde Crypto-Loop im 2.6er Kernel offiziell
aufgenommen. Dies bedeutet, dass der Loop-Treiber AES
unterstützt\footnote{Voraussetzung hierfür ist, dass die Loop-AES
Unterstützung nicht bei der Übersetzung des Kernels abgeschaltet
wurde.}. Zusätzlich können folgende Algorithmen geladen werden:
Twofish, Blowfish, Serpent, Mars, rc6, und TripleDES.

Bevor mit der Installation begonnen wird, ist es auf jeden Fall
sinnvoll zu überprüfen, ob der aktuelle Kernel nicht doch schon
Crypto-Loop unterstützt. (Auch bei Kernelversionen vor 2.6.) Denn
viele Hersteller von Distributionen bauen Crypto-Loop selbständig in
ihre Kernel ein. Zur Überprüfung kann der weiter unten beschriebene
Weg gegangen werden, um ein verschlüsseltes Dateisystem zu erzeugen.

Sollte wieder Erwarten der Kernel kein Crypto-Loop unterstützen, kann
folgender Weg beschritten werden. Es ist dabei Voraussetzung, dass die
Kernel-Sourcen des aktuell verwendeten Kernels installiert sind. (Oder
des Kernels, welcher neu installiert werden soll) Zusätzlich müssen
diese richtig konfiguriert (Plattform, etc.) und übersetzt worden
sein. Zuerst ist die Datei {\tt loop-AES-latest.tar.bz2} von {\tt
http://loop-aes.sourceforge.net/} herunterzuladen und mit {\tt tar -xvjf
loop- AES-latest.tar.bz2} zu entpacken. Danach ist in das entstandene
Verzeichnis zu wechseln ({\tt cd loop-AES-v3.1c}) und {\tt make}
auszuführen. Im Normalfall erkennt make automatisch, wo die Kernel
Sourcen liegen.

Der manuellen Installation ist auf jeden Fall die automatische
Installation der verwendeten Distribution vorzuziehen. Unter Debian
kann der Kernel zum Beispiel folgendermaßen übersetzt werden. Zuerst
müssen die Kernel Quellcodes (z.B. {\tt kernel-source-2.4.27})
installiert werden. Zusätzlich sind die Quellcodes für Cryptoloop zu
installieren. (Paket {\tt loop-aes-source} und {\tt
loop-aes-ciphers-source}. Zweites nur, wenn zusätzliche Algorithmen
gewünscht werden.) Zum Schluss sind noch die Tools zum Verwenden des
Crypto-Loop-Treibers erforderlich: {\tt loop-aes-utils}. Es ist
natürlich auch möglich, die allerneuesten Kernelquellen von {\tt
www.kernel.org} herunter zu laden. Dabei muss allerdings auf die Namen
der Verzeichnisse geachtet werden.


Im folgenden wird davon ausgegangen, dass die {\tt bash}\footnote{\tt
http://www.gnu.org/software/bash/bash.html} als Shell
(Eingabeinterpreter) verwendet wurde und dass alle Befehle mit
Administrator-Rechten, also z.B. unter dem User {\tt root} auszuführt
werden.

Des weiteren wird davon ausgegangen, dass der Kernel 2.4.27 richtig
installiert und konfiguriert ist. Zusätzlich zu diesem Kernel wird
CryptoLOOP installiert. Der Kernel an sich wird nicht
verändert. Trotzdem ist das Vorhandensein der vollständigen Kernel
Quellen erforderlich.

{\tt\footnotesize
\begin{lstlisting}
apt-get install loop-aes-source        # Pakete installieren
apt-get install loop-aes-utils
apt-get install kernel-source-2.4.27
apt-get install kernel-package
cd /usr/src/                           # Auspacken
tar -xjf loop-aes.tar.bz2
tar -xjf kernel-source-2.4.27.tar.bz2
ln -s kernel-source-2.4.27 linux       # Damit auch wirklich jedes
                                       # Programm die Sourcen findet

cp /boot/config-2.4.27-2-686 /usr/src/linux/.config  # Konfig vom
                                       # aktuell installierten
                                       # Kernel übernehmen
cd /usr/src/linux/
make-kpkg configure                    # Kernel Konfigurieren,
                                       # Übersetzen und Debian
                                       # Pakete erzeugen
cd /usr/src/modules/loop-aes           # CryptoLOOP übersetzen
debian/rules KSRC=/usr/src/linux KVERS=2.4.27-2-686 kdist_image
                                       # ... und Installieren
dpkg -i /usr/src/modules/loop-aes-2.4.27-2-686_2.1c-1_i386.deb
\end{lstlisting}
}
\begin{flushright}
Adaptiert\footnote{Zu den übernommenden Befehlen wurden Kommentare
hinzugefügt.} von Wenzel (2005).
\end{flushright}

\subsection{Einrichten des CryptoLoop Drivers}

Der CryptoLoop Driver verwaltet in der Standardeinstellung ``nur''
acht virtuelle Blockdevices. Dies kann schnell zu wenig sein. Daher
empfiehlt es sich, das CryptoLoop Kernel Module ({\tt loop.o} oder
{\tt loop.ko} bei 2.6er Kerneln) mit dem Parameter {\tt max\_loop} zu
laden. Somit können bis zu 256 virtuelle Blockdevices verwendet
werden:

Laden des Crypto-Loop Kernel Modules mit 32 virtuellen Blockdevices.
{\tt\footnotesize
\begin{lstlisting}
insmod loop max_loop=32
\end{lstlisting}
}

Für jedes virtuelle Blockdevices ist ein Interface zu erstellen. Bei
diesem Interface handelt es sich um eine spezielle Datei mit dem Namen
{\tt /dev/loopX}. Die ersten acht sind normalerweise vorhanden. Mit
dem folgenden Befehl können Interface-Dateien für 32 virtuelle
Blockdevices erstellt werden:

{\tt\footnotesize
\begin{lstlisting}
# Erstellen der speziellen Dateien (Interface)
for i in 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15; do
  mknod /dev/loop$(printf %X $i) b 7 $i 2> /dev/null
done
for i in 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15; do
  mknod /dev/loop$(printf "1"%X $i) b 7 $[$i+16] 2> /dev/null
done
# Setzen der Zugriffsrechte
chown root /dev/loop*
chgrp disk /dev/loop*
chmod ug+rw,o-rwx /dev/loop*
\end{lstlisting}
}

Das Ergebnis dieser Operation sollte folgendes sein:
{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/dev > ls -al loop*
brw-rw----  1 root disk 7,  0 Jun 13  2005 loop0
brw-rw----  1 root disk 7,  1 Jun 13  2005 loop1
brw-rw----  1 root disk 7, 16 Jul 27  2005 loop10
brw-rw----  1 root disk 7, 17 Jul 27  2005 loop11
brw-rw----  1 root disk 7, 18 Jul 27  2005 loop12
brw-rw----  1 root disk 7, 19 Jul 27  2005 loop13
brw-rw----  1 root disk 7, 20 Jul 27  2005 loop14
brw-rw----  1 root disk 7, 21 Jul 27  2005 loop15
brw-rw----  1 root disk 7, 22 Jul 27  2005 loop16
brw-rw----  1 root disk 7, 23 Jul 27  2005 loop17
brw-rw----  1 root disk 7, 24 Jul 27  2005 loop18
brw-rw----  1 root disk 7, 25 Jul 27  2005 loop19
brw-rw----  1 root disk 7, 26 Jul 27  2005 loop1A
brw-rw----  1 root disk 7, 27 Jul 27  2005 loop1B
brw-rw----  1 root disk 7, 28 Jul 27  2005 loop1C
brw-rw----  1 root disk 7, 29 Jul 27  2005 loop1D
brw-rw----  1 root disk 7, 30 Jul 27  2005 loop1E
brw-rw----  1 root disk 7, 31 Jul 27  2005 loop1F
brw-rw----  1 root disk 7,  2 Jun 13  2005 loop2
brw-rw----  1 root disk 7,  3 Jun 13  2005 loop3
brw-rw----  1 root disk 7,  4 Jun 13  2005 loop4
brw-rw----  1 root disk 7,  5 Jun 13  2005 loop5
brw-rw----  1 root disk 7,  6 Jun 13  2005 loop6
brw-rw----  1 root disk 7,  7 Jun 13  2005 loop7
brw-rw----  1 root disk 7,  8 Feb 11  2004 loop8
brw-rw----  1 root disk 7,  9 Feb 11  2004 loop9
brw-rw----  1 root disk 7, 10 Feb 11  2004 loopA
brw-rw----  1 root disk 7, 11 Feb 11  2004 loopB
brw-rw----  1 root disk 7, 12 Feb 11  2004 loopC
brw-rw----  1 root disk 7, 13 Feb 11  2004 loopD
brw-rw----  1 root disk 7, 14 Feb 11  2004 loopE
brw-rw----  1 root disk 7, 15 Feb 11  2004 loopF
\end{lstlisting}
}

Bei bedarf können folgende Module nachgeladen werden, um weitere
Verschlüsselungsalgorithmen neben AES zu verwenden:

{\tt\footnotesize
\begin{lstlisting}
insmod loop_twofish loop_serpent loop_blowfish
\end{lstlisting}
}


\subsection{Einrichten eines Containers}

Ein Container ist eine Datei, in welchem sich ein verschlüsseltes
Dateisystem befindet.

\subsubsection{Erstellen des Containers -- der Imagedatei}

Um solch einen Container zu erstellen, muss zuerst eine Datei (ein
Image) erstellt werden. Es ist zu bedenken, dass es nicht möglich ist,
die Größe des Containers nachträglich zu verändern. Um eine
Größenänderung zu bewerkstelligen, ist ein neuer Container zu
erstellen. Danach sind alle Daten aus dem alten in den neuen
Container zu kopieren.

Der folgende Befehl erstellt die Image-Datei, welche das Dateisystem
enthalten soll. Die Datei wird mit Nullen (Byte {\tt 0x00})
aufgefüllt.

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > dd if=/dev/zero of=/Container.img bs=1M count=25
25+0 records in
25+0 records out
26214400 bytes transferred in 0.218848 seconds (119783549 bytes/sec)
\end{lstlisting}
}

{\tt dd} liest von der Eingabedatei (Input File), welche mit {\tt if}
spezifiziert ist und schreibt die gelesenen Daten nach {\tt of} (Output
File, Ausgabedatei). {\tt /dev/zero} ist eine spezielle Datei, welche
unendlich viele Nullen (Byte {\tt 0x00}) liefert. Der Container ist
hier mit {\tt /Container.img} benannt. Die Menge der Daten (die Größe
des Containers) wird errechnet, indem {\tt bs} (Block Size) mit {\tt
count} multipliziert wird. In diesem Fall handelt es sich um 25 MByte.

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > ls -alh /Container.img 
-rw-------  1 root root 25M Feb  9 09:14 Container.img
\end{lstlisting}
}

Mit Hilfe eines Hex-Editors kann an dieser Stelle nachgewiesen werden,
dass die erstellte Datei tatsächlich nur Nullen enthält. Ein {\tt
hexdump} soll den Hexeditor an dieser Stelle ersetzen.

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > hexdump /Container.img 
0000000 0000 0000 0000 0000 0000 0000 0000 0000
*
1900000
\end{lstlisting}
}

Glücklicherweise komprimiert {\tt hexdump} die Ausgabe
selbstständig. Das {\tt *} bedeutet, dass alle folgenden Zeilen mit
der Ersten identisch sind. Die erste Nummer jeder Zeile gibt die
Position der aktuellen Zeile in der Datei an. Es geht mit {\tt
0000000} los und endet mit {\tt 1900000}. 1900000 ist eine
Hexadezimalzahl und ist gleich 26214400 Bytes. Das sind $25*1024*1024$
Bytes, also 25 MByte.


\subsubsection{Besonderheiten bei Partitionen}

Die Erstellung einer verschlüsselten Partition weicht nicht weit von
dieser Beschreibung ab. Statt {\tt /Container.img} muss die Partition
(z.B. {\tt /dev/hda5} für die erste logische Partition auf der ersten
Festplatte) angegeben werden. Das Erstellen der ``Datei'' mittels {\tt
dd} entfällt. Sonst kann die hier gegebene Beschreibung angewendet
werden. Hinweis: Bei Partitionen ist mit äußerster Vorsicht zu
arbeiten, denn der Inhalt der verwendeten Partition wird
überschrieben. Daher den Namen des verwendeten Blockdevices immer
mehrmals überprüfen.


\subsubsection{Mappen des Images auf ein virtuellen Blockdevice}

Der nächste Schritt ist das Verbinden der Datei mit dem virtuellen
Blockdevice. Dies wird mit Hilfe von {\tt losetup} durchgeführt:

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ >  losetup -e AES256 -C 5000 /dev/loop4 /Container.img
Password: 
\end{lstlisting}
}

Der zu verwendende Verschlüsselungsalgorithmus wird mit {\tt -e}
bekanntgemacht. Bei der ersten übergebenen Datei muss es sich um das virtuelle
Blockdevice handeln. Die zweite ist die Datei, die auf das virtuelle
Blockdevice gemappt werden soll. Werden die Parameter {\tt -e} und
{\tt -C} weggelassen, so enthält {\tt /dev/loop4} exakt dieselben Daten
wie {\tt /Container.img}, nur mit dem Unterschied, dass {\tt
/dev/loop4} als Blockdevice gemountet werden kann.

In diesem Fall werden alle Daten, welche nach {\tt /dev/loop4}
geschrieben werden, mit dem eingegebenen Password\footnote{Oder
bessergesagt, mit einem aus dem Password errechneten Schlüssel}
verschlüsselt und dann nach {\tt /Container.img} weitergereicht. Der
Lesezugriff auf {\tt /dev/loop4} funktioniert umgekehrt. Die Daten
werden von {\tt /Container.img} gelesen, entschlüsselt und dann an den
lesenden Prozess weitergereicht.

Das Password wird nach der Eingabe gehasht. Dies führt dazu, dass der
Schlüsselraum\footnote{Menge alle möglicher Schlüssel.} optimaler
ausgenutzt wird. Denn Zahlen und Buchstaben stellen nur eine kleine
Auswahl des Zeichensatzes eines Computers dar. Durch Hashing wird eine
Zeichenkette erzeugt, welche alle Zeichen enthalten kann. Diese wird
dann als Schlüssel für AES verwendet.

Der Parameter {\tt -C} $n$ versucht, es möglichen Angreifern etwas
schwerer zu machen. Die Ausgabe der Hash-Funktion wird $1000 * n$ mal
mit AES256\footnote{AES Schlüssellänge: 256 Bit, aber AES Blockgröße
128Bit} verschlüsselt, bevor sie als Schlüssel für die eigentliche
Verschlüsselung dient. Bei Verwendung des Parameters {\tt -C 5000} ist
eine deutliche Verzögerung zwischen der Eingabe des Passwortes und der
Fertigstellung des Befehls zu beobachten. Wird der Parameter
weggelassen, kann keine nennenswerte Verzögerung festgestellt
werden. Diese Verzögerung ist im Normalfall nicht störend. Versucht
jedoch jemand die Verschlüsselung zu brechen, indem er alle Wörter
eines Wörterbuches durchprobiert, so wird ihm diese Verzögerung zum
Verhängnis. Denn sie tritt bei jedem Versuch auf und lässt die Zeit
zum Durchprobierten etwa um den Faktor $1000 * n$ steigen, was einen
Angriff erheblich erschwert.


Der folgende Befehl gibt den aktuellen Status eines virtuellen
Blockdevices aus. Es ist zu erkennen, dass AES zur Verschlüsselung
verwendet wird und dass die gemappte Datei {\tt /Container.img} ist.

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > losetup /dev/loop4
/dev/loop4: [0306]:1819 (/Container.img) encryption=AES0
\end{lstlisting}
}

Eine kleine Schleife kann auch hier eingesetzt werden, um alle Devices
abzufragen.

{\tt\footnotesize
\begin{lstlisting}
for i in /dev/loop*; do
  losetup $i
done
\end{lstlisting}
}

\subsubsection{Erstellen eines Dateisystems im Container}

Der nächste Schritt ist das Erstellen eines Dateisystems in dem
Container. In diesem Fall wird ein ext2-Dateisystem erstellt.

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > mke2fs /dev/loop4
mke2fs 1.37 (21-Mar-2005)
Filesystem label=
OS type: Linux
Block size=1024 (log=0)
Fragment size=1024 (log=0)
6400 inodes, 25600 blocks
1280 blocks (5.00%) reserved for the super user
First data block=1
4 block groups
8192 blocks per group, 8192 fragments per group
1600 inodes per group
Superblock backups stored on blocks: 
        8193, 24577

Writing inode tables: done                            
Writing superblocks and filesystem accounting information: done

This filesystem will be automatically checked every 27 mounts or
180 days, whichever comes first.  Use tune2fs -c or -i to override.
\end{lstlisting}
}

Es ist sinnvoll, das so eben erstellte Dateisystem noch etwas feiner
abzustimmen. Normalerweise werden 5\% des Speicherplatzes auf einem
Dateisystem für den User root reserviert, um sicherzustellen, dass alle
Systemdienste genug Speicherplatz haben. Hier wird davon ausgegangen,
dass keine Systemdienste im Container laufen. Daher werden mit {\tt
-m0} 0\% reserviert. Ext2 Dateisysteme werden nach eine einstellbaren
Anzahl von Tagen oder von mount-Operationen vollständig getestet. Dies
kann nicht abgeschaltet werden, aber es ist möglich, die größten
möglichen Werte einzustellen. Test einmal im Jahr (12Monate) {\tt -i
12m} und aller 9999 mounts {\tt -c 9999}

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > tune2fs -i 12m -m0 -c 9999 /dev/loop4
tune2fs 1.37 (21-Mar-2005)
Setting maximal mount count to 9999
Setting interval between check 31104000 seconds
Setting reserved blocks percentage to 0 (0 blocks)
\end{lstlisting}
}


\subsubsection{Mounten, testen und umounten des erstellten Dateisystems}

Nun ist das Dateisystem erstellt und kann gemountet werden. Dazu wird
vorher der mount-point\footnote{Verzeichnis, in welchem das neue
Dateisystem sichtbar werden soll} erstellt.

{\tt\footnotesize
\begin{lstlisting}
mkdir /crypto
mount /dev/loop4 /crypto
\end{lstlisting}
}

Der Container kann jetzt verwendet werden. In diesem Fall wurde
repräsentativ eine Datei in den Container kopiert:

{\tt\footnotesize
\begin{lstlisting}
cp /usr/src/modules/loop-aes/README /crypto/
\end{lstlisting}
}

Der Beginn dieser Datei wurde dann im Dateisystem gesucht und
ausgegeben:

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > hexdump -C -s 223232 -n 256 /dev/loop4
00036800  57 72 69 74 74 65 6e 20  62 79 20 4a 61 72 69 20  |Written by Jari |
00036810  52 75 75 73 75 20 3c 6a  61 72 69 72 75 75 73 75  |Ruusu <jariruusu|
00036820  40 75 73 65 72 73 2e 73  6f 75 72 63 65 66 6f 72  |@users.sourcefor|
00036830  67 65 2e 6e 65 74 3e 2c  20 4f 63 74 6f 62 65 72  |ge.net>, October|
00036840  20 32 36 20 32 30 30 34  0a 0a 43 6f 70 79 72 69  | 26 2004..Copyri|
00036850  67 68 74 20 32 30 30 31  2c 32 30 30 32 2c 32 30  |ght 2001,2002,20|
00036860  30 33 2c 32 30 30 34 20  62 79 20 4a 61 72 69 20  |03,2004 by Jari |
00036870  52 75 75 73 75 2e 0a 52  65 64 69 73 74 72 69 62  |Ruusu..Redistrib|
00036880  75 74 69 6f 6e 20 6f 66  20 74 68 69 73 20 66 69  |ution of this fi|
00036890  6c 65 20 69 73 20 70 65  72 6d 69 74 74 65 64 20  |le is permitted |
000368a0  75 6e 64 65 72 20 74 68  65 20 47 4e 55 20 50 75  |under the GNU Pu|
000368b0  62 6c 69 63 20 4c 69 63  65 6e 73 65 2e 0a 0a 0a  |blic License....|
000368c0  54 61 62 6c 65 20 6f 66  20 43 6f 6e 74 65 6e 74  |Table of Content|
000368d0  73 0a 7e 7e 7e 7e 7e 7e  7e 7e 7e 7e 7e 7e 7e 7e  |s.~~~~~~~~~~~~~~|
000368e0  7e 7e 7e 0a 31 2e 20 20  20 20 4c 6f 6f 70 20 64  |~~~.1.....Loop d|
000368f0  65 76 69 63 65 20 70 72  69 6d 65 72 0a 32 2e 20  |evice primer.2. |
\end{lstlisting}
}

Danach wurde die gleiche Stelle in der gemappten Datei untersucht

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > hexdump -C -s 223232 -n 256 /Container.img 
00036800  88 17 c4 78 15 18 1b 6a  68 6d 84 90 c7 01 5f d6  |...x...jhm..Ç._Ö|
00036810  2a 6c 5c 76 a9 83 ea a1  66 95 4e 87 f6 94 1a 42  |*l\v©.ê¡f.N.ö..B|
00036820  50 27 98 77 01 da ea cf  f3 02 ec dc df d1 aa 56  |P'.w.ÚêÏó.ìÜßÑªV|
00036830  8e 2c 9c 5a 9f 5b 88 b8  ad aa e0 d4 d0 22 e5 ed  |.,.Z.[.¸..àÔÐ"åí|
00036840  4a 6f 94 36 d7 fe 59 63  8f 90 1b 09 4f 71 cd 86  |Jo.6..Yc....OqÍ.|
00036850  a9 1d 8d e1 d0 7a ad eb  70 27 ae c4 9e 17 47 4f  |.....z..p'®Ä..GO|
00036860  ac 90 04 cd bc 7f d6 27  91 8e 90 a9 52 d8 4e 1b  |.......'....RØN.|
00036870  bb b6 05 6e f6 85 15 65  6e ed 74 48 91 ea 86 ef  |...nö..enítH.ê.ï|
00036880  d7 19 f4 59 c1 91 a3 18  9c 68 da f2 9b 94 a7 f5  |...YÁ.£..hÚò..§õ|
00036890  ad 61 45 16 c4 16 60 d6  72 54 30 c7 d7 bf 38 60  |­aE.Ä.`ÖrT0Ç.¿8`|
000368a0  30 e9 d9 1d 7c db fd 5c  46 5f 63 1a b2 f6 2e a9  |0...|..\F_c..ö.©|
000368b0  ae 49 f6 1c c1 27 73 03  9d ac 49 c4 36 04 12 fb  |.Iö.Á's...IÄ6..û|
000368c0  9e e1 e9 cc 38 ac 2d 8f  73 ec db 8f ab 77 0c 12  |....8...sìÛ.«w..|
000368d0  67 71 92 9c f5 10 49 7c  f2 03 eb 9c 95 74 62 38  |gq..õ.I|ò.ë..tb8|
000368e0  bd e9 2d f3 80 37 2f 05  48 06 2b e4 dd 28 80 cb  |..-..7/.H.+äÝ(.Ë|
000368f0  b6 62 43 b0 fe 06 8f da  95 63 f5 ad 05 41 92 1f  |.bC°þ..Ú.cõ..A..|
00036900
\end{lstlisting}
}

Es ist zu erkennen, dass die kopierte Datei als Klartext in das
Dateisystem, also auf das virtuellem Blockdevice geschrieben
wurde. Aufgrund der eingeschalteten Verschlüsselung ist an derselben
Stelle in der gemappten Datei nur ``Datenschrott'' vorzufinden.

Nach Benutzung eines Containers ist es wichtig, diesen wieder zu
umounten, da sonst jeder auf die enthaltenen Daten zugreifen
kann. Dabei ist es sehr wichtig daran zu denken, das virtuelle
Blockdevice wieder freizugeben. Ist dies nicht geschehen, kann ein
Angreifer durch Ausführen eines entsprechenden mount-Befehls auf die
Daten {\bf ohne Eingabe des Passwortes} zugreifen.

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > umount /crypto
root@LBlacky:/ > losetup -d /dev/loop4 
root@LBlacky:/ > losetup /dev/loop4 
loop: can't get info on device /dev/loop4: No such device or address
\end{lstlisting}
}

Der letzte Befehl fragt den Status des virtuellen Blockdevices
ab. Dies sollte nach der Freigabe in einer Fehlermeldung resultieren.


\subsection{Mounten und umounten mit je einem Befehl}

Das alles geht auch einfacher. Ist der Container erstellt, so kann er
direkt mit {\tt mount} gemountet werden. In diesem Fall kümmert sich
mount automatisch um die Vergabe und Freigabe des virtuellen
Blockdevices.

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > \
mount -o encryption=AES256,itercountk=5000 /Container.img /crypto
root@LBlacky:/ > diff /usr/src/modules/loop-aes/README /crypto/README
root@LBlacky:/ > for i in /dev/loop*; do losetup $i; done
/dev/loop0: [0306]:1819 (/Container.img) encryption=AES0
loop: can't get info on device /dev/loop1: No such device or address
[...]
root@LBlacky:/ > umount /crypto 
root@LBlacky:/ > for i in /dev/loop*; do losetup $i; done
loop: can't get info on device /dev/loop0: No such device or address
loop: can't get info on device /dev/loop1: No such device or address
[...]
\end{lstlisting}
}

Natürlich ist es an dieser Stelle sehr zu empfehlen, das Passwort zu
erinnern. {\tt itercountk} definiert das gleiche wie bei {\tt losetup}
der Parameter {\tt -C} und ist selbstverständlich identisch zu
wählen. {\tt diff} vergleicht die beiden übergebenden Dateien. Keine
Ausgabe bedeutet, dass beide Dateien identisch sind. Nach diesem
Vergleich werden die Zustände alle  virtuellen Blockdevices
ausgegeben. Mount wählte automatisch das erste freie, hier {\tt
/dev/loop0}. Das Freigeben des Containers geschieht mit {\tt umount
/crypto}. Wie zu erkennen ist, wurde das verwendete virtuelle
Blockdevice ebenfalls freigegeben.


\subsection{Swap-Partition und {\tt /tmp}}

Bei dem Verschlüsseln von Daten wird leicht vergessen, dass die
verschlüsselten Daten für die Benutzung entschlüsselt werden. Wer eine
geheime Datei von einer verschlüsselten Partition in den Editor lädt,
kopiert die geheime Datei unverschlüsselt in den Hauptspeicher des
Computers. Es ist daher darauf zu achten, dass keine Programme laufen,
die den Hauptspeicher auslesen könnten. Des weiteren besteht die
Gefahr, dass ein Teil des Hauptspeichers in die Swap-Partition
ausgelagert wird. Nun ist ein Teil der geheimen Datei wieder {\bf
unverschlüsselt} auf der Festplatte. Dies kann vermieden werden, indem
entweder keine Swap-Partition verwendet wird oder diese ebenfalls
verschlüsselt wird. Die Verschlüsselung führt an dieser Stelle
natürlich wieder zu Performanceverlust. Das gleiche Problem tritt bei
dem Verzeichnis für temporäre Dateien ({\tt /tmp}) auf. Viele Programme
speichern dort Dateien zwischen, was dazu führen kann, dass geheime
Dateien aus dem verschlüsselten Container unverschlüsselt auf der
Festplatte landen.

Swap-Partition verschlüsseln: 

Die folgende Zeile in der Datei {\tt /etc/fstab} muss erweitert werden:

{\tt /dev/hdXX none swap sw 0 0}

Erweiterte Zeile:

{\tt /dev/hdXX none swap sw,loop=/dev/loopX,encryption=AES128 0 0}

Es ist ratsam, die Swap-Partition mit einem Hexeditor zu
untersuchen. So kann schnell festgestellt werden, ob diese auch
tatsächlich verschlüsselt ist.

\subsection{An was noch zu denken ist}

Die Sicherheit der verschlüsselten Daten ist immer (nur) so gut wie
das Passwort. Ein zu einfaches Passwort kann schnell erraten
werden. Ein vergessenes Passwort schützt die Daten sehr effektiv vor
dem Eigentümer.

Wer Daten verschlüsselt, sollte sich darüber im klaren sein, dass er
womöglich nicht mehr auf seine Daten zugreifen kann, wenn etwas schief
gegangen ist. Es sollte daher selbstverständlich sein, immer
mindestens zwei Wege zu haben, um seine Daten zu entschlüsseln. Ein
einfacher und sehr guter ``zweiter Weg'' ist die Linux-Live-CD
Knoppix\footnote{http://www.knoppix.org/}. Von dieser CD kann ein
vollständiges Linux mit Crypto-Loop-Unterstützung gebootet werden. Es
ist sehr zu empfehlen, den Knoppix-Weg {\bf vor} einem Systemcrash
auszuprobieren. Denn dann ist sofort erkennbar, wenn etwas nicht
klappt. (Z.B. Passwort, Algorithmus oder {\tt itercountk}-Wert
falsch). Das Notieren dieser Werte an einem sicheren Ort ist ebenfalls
empfehlenswert. Denn nach einem halben Jahr ist der Algorithmus oder
{\tt itercountk}-Wert in Vergessenheit geraten, was zu Problemen
führen kann.

Backups zu erstellen ist auch immer eine gute Idee. Wenn überhaupt,
sollten Backups erst dann verschlüsselt werden, wenn man schon einige
Erfahrung mit Verschlüsselung hat (und wenn der zweite Weg ausprobiert
wurde). Auf jeden Fall sollte vor der Erstanwendung einer
Verschlüsselung der Datenbestand gesichert werden!



\subsection{Geschwindigkeitstest}

Um einen Überblick über die Performance von AES bzw. von Crypto-Loop
zu erhalten, wurde ein Performancevergleich durchgeführt.
Dieser Test wurde auf einem Pentium III 850 MHz Computer einmal mit
und einmal ohne Verschlüsselung durchgeführt. Es wurden jeweils
250MByte von der Festplatte gelesen.

Die Transferrate wurde mit Hilfe von {\tt dd} gemessen. Ausgabedatei
({\tt of}) war {\tt /dev/null}. Alles was auf dieses spezielle Device
geschrieben wird, hört schlicht und einfach auf zu existieren. Es wird
nicht weiter verarbeitet.

``Normales'' lesen von Festplatte:

{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > dd if=/dev/hda7 of=/dev/null bc=1M count=250
250+0 records in
250+0 records out
262144000 bytes transferred in 14.469067 seconds (18117547 bytes/sec)
\end{lstlisting}
}

Transferrate: ca. 17MByte/s. CPU-Last ca. 27\%

Lesen eines verschlüsseltem Bereiches von Festplatte (inklusive entschlüsseln).
{\tt\footnotesize
\begin{lstlisting}
root@LBlacky:/ > dd if=/dev/loopE of=/dev/null bs=1M count=250
250+0 records in
250+0 records out
262144000 bytes transferred in 21.277416 seconds (12320293 bytes/sec)
\end{lstlisting}
}

Transferrate: ca. 12MByte/s. CPU-Last ca. 64\%

Es ist zu erkennen, dass die Entschlüsselung den Datentransfer um gut
35\% verlangsamt und fast zweieinhalb mal soviel Rechenlast (CPU-Last)
erzeugt.

11MByte/s entspricht 24063 512\_Byte\_Blöcken/s

Wird nun davon ausgegangen, dass statt der Entschlüsslung jedes
512\_Byte\_Blockes, immer der selbe Block mit einem anderen Password
entschlüsselt wird, würde das Durchprobieren aller möglichen
Passwörter ca. $1.5 * 10^{66}$ Jahre dauern. In dieser Rechnung ist
weder das Analysieren des gewonnenen Klartextblockes
(z.B. vergleichen mit einem bekannten Klartextblock) noch das
Initialisieren des Verschlüsselungsalgorithmus inbegriffen. Diese
Faktoren würden die Zeit noch verlängern.

$\frac{2^{256} Moeglichkeiten}{22411
 \frac{256\_Byte\_Bloecke}{s}} * \frac{1}{60*60*24*7*53} \approx
1.5 * 10^{66} Jahre$ 

Wird davon ausgegangen, dass das Password aus nur einem Wort der
englischen Sprache besteht, welches im Oxford Dictionary steht, so
beschränkt sich die Anzahl der möglichen Passwörter auf
414800\footnote{Quelle: http://www.oed.com/about/facts.html}. Das
Durchprobieren aller dieser Möglichkeiten würde mit dem genannten
Rechner gerade mal ca. 17 Sekunden dauern.

$\frac{414800 Moeglichkeiten}{22411
 \frac{256\_Byte\_Bloecke}{s}} \approx 17s$

Es sind bei dem Crypto-Loop-Driver allerdings normalerweise nur
Passwörter mit 20 oder mehr Zeichen erlaubt. Wird nun angenommen, dass
das Password aus fünf Wörtern aus dem englischen Wörterbuch besteht,
so ergeben sich $414800^5 \approx 1.2 * 10^{28}$ Möglichkeiten. Unter
der Annahme, dass die Wörter rein zufällig zusammengesetzt wurden
(also keinen Satz bzw. Sinn ergeben müssen) folgt daraus, dass es etwa
$1.6 * 10^{16}$ Jahre dauern würde, alle Möglichkeiten durchzuprobieren.

$\frac{1.2 * 10^{28} Moeglichkeiten}{22411
 \frac{256\_Byte\_Bloecke}{s}} * \frac{1}{60*60*24*7*53} \approx
1.6 * 10^{16} Jahre$

Im statistischen Mittel wird es notwendig sein, die Hälfte alle
Passwörter durchzuprobieren, um das richtige zu finden. Das bedeutet,
dass im statistischen Mittel nur die Hälfte der errechneten Zeit
notwendig ist, um das Passwort zu finden.

Durch das Aktivieren der weiter oben genannten Option {\tt -C} bei
losetup bzw. {\tt itercountk} bei mount kann diese Form der Attacken
erheblich erschwert werden. Denn das Initialisieren des
Verschlüsselungsverfahrens wird erheblich aufwendiger und
langwieriger durch Einsatz dieses Parameters.
































%\newpage


\section{Bibliographie und Referenzen}
{\bf Corbet et al} (2004) A weak cryptoloop implementation in Linux?\newline
[Online] Available at {\tt http://lwn.net/Articles/67216/} (accessed
22. December)

{\bf Daemen, J.; Rijmen, V.} (2002) The Design of Rijndael. Berlin
Heidelberg: Springer-Verlag. ISBN 3-540-42580-2.

{\bf Deters, D.} (2002) Systematisierung der symmetrischen
kryptographischen Verfahren [Online] Available at\\ {\tt
http://www.informatik.hu-berlin.de/Forschung\_Lehre/algorithmenII/\\
Lehre/SS2002/Ana\_krypt\_Alg/02Systematisierung/Systematisierung.html}\\
(accessed 20. December 2005)

{\bf Hölzer, R.} (2004) Cryptoloop HOWTO. [Online] Available at\\ {\tt
http://www.tldp.org/HOWTO/Cryptoloop-HOWTO/} (accessed 22. December
2005)

{\bf Ruusu, J} (2004) ``{\tt README}'' von Loop-AES. [Online] Available at\\ {\tt
http://loop-aes.sourceforge.net/loop-AES.README}

{\bf  van Rees, J} (2005) Introduction to Cryptography and
Cryptosystems: Assignments [Online] Available at\\ {\tt
http://www.cs.umanitoba.ca/} $\tilde{} $ {\tt cs414/assignments/(test2output.txt)}\\
(accessed 26. December 2005)

{\bf Wenzel, R.} (2005) Verschluesselte Dateisysteme und
Container.\newline[Online] Available at\\ {\tt
http://www.ruwela.de/Linux-Befehls-Beispiele/node16.html} (accessed 22. December 2005)

{\bf Wilkin, C} (2004) Der Algorithmus des ``Advanced Encryption
Standard''.\newline[Online] Available at {\tt
http://www.ainformatik.fh-trier.de/} $\tilde{} $ {\tt scheerhorn/}\\
(accessed 20. December 2005)





\end{document}

