cryptomethods.tex

a very popular packet of cryptography tools,it encloses the most common used algorithm and protocols

% $Id: cryptomethods.tex 1205 2005-07-04 13:58:13Z koy $
% ............................................................................
%             V E R S C H L U E S S E L U N G S V E R F A H R E N
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\section{Verschl"usselungsverfahren}
\hypertarget{Kapitel_1}{}
(Bernhard Esslinger, Mai 1999, Updates: Dez. 2001, Feb. 2003, June 2005)


Dieses Kapitel soll einen eher beschreibenden Einstieg bieten und die
Grundlagen ohne Verwendung von allzuviel Mathematik vermitteln.


% --------------------------------------------------------------------------
% \subsection{Verschl"usselung}

Sinn der Verschl"usselung \index{Verschl""usselung} ist es, Daten so zu
ver"andern, dass nur ein autorisierter Empf"an\-ger in der Lage ist,
den Klartext zu rekonstruieren. Das hat den Vorteil, dass verschl"usselte
Daten offen "ubertragen werden k"onnen und trotzdem keine Gefahr besteht,
dass ein Angreifer die Daten unberechtigterweise lesen kann. Der
autorisierte Empf"anger ist im Besitz einer geheimen Information, des
sogenannten Schl"ussels, die es ihm erlaubt, die Daten zu entschl"usseln,
w"ahrend sie jedem anderen verborgen bleiben.\par \vskip + 3pt

Es gibt ein beweisbar sicheres Verschl"usselungsverfahren, 
das \index{One-Time-Pad} {\em One-Time-Pad}. Dieses weist allerdings
einige praktische Nachteile auf (der verwendete Schl"ussel muss zuf"allig
gew"ahlt werden und mindestens so lang wie die zu sch"utzende Nachricht sein),
so dass es au"ser in geschlossenen Umgebungen, zum Beispiel beim hei"sen
Draht zwischen Moskau und Washington, kaum eine Rolle spielt.\par \vskip + 3pt

F"ur alle anderen Verfahren gibt es (theoretische) M"oglichkeiten, sie
zu brechen. Bei guten Verfahren sind diese jedoch so aufw"andig, dass sie
praktisch nicht durchf"uhrbar sind und diese Verfahren als (praktisch)
sicher angesehen werden k"onnen.\par \vskip + 3pt

Einen sehr guten "Uberblick zu den Verfahren bietet das Buch von Bruce Schneier \cite{Schneier1996cm}. Grunds"atzlich unterscheidet man zwischen symmetrischen und 
asymmetrischen Verfahren zur Verschl"usselung.

% --------------------------------------------------------------------------
\subsection[Symmetrische Verschl"usselung]
{Symmetrische Verschl"usselung\footnotemark}
        \footnotetext{% XXX dieses Prozent ist n鰐ig, sonst startet die Fu遪ote mit einem Blank !
        Mit CrypTool\index{CrypTool} k"onnen Sie "uber das Men"u
        {\bf Ver-/Entschl"usseln \textbackslash{} Symmetrisch (modern)} folgende 
        modernen symmetrischen Verschl"usselungsverfahren ausf"uhren: \\
        IDEA, RC2, RC4, DES (ECB), DES (CBC), Triple-DES (ECB), Triple-DES (CBC),
        MARS (AES-Kandidat), RC6 (AES-Kandidat), Serpent (AES-Kandidat), 
        Twofish (AES-Kandidat), Rijndael (offizielles AES-Verfahren).
        }

Bei der {\em symmetrischen} Verschl"usselung 
\index{Verschl""usselung!symmetrisch} m"ussen Sender und Empf"anger
"uber einen gemeinsamen (geheimen) Schl"ussel verf"ugen, den sie vor
Beginn der eigentlichen Kommunikation ausgetauscht haben. Der Sender
benutzt diesen Schl"ussel, um die Nachricht zu verschl"usseln und der
Empf"anger, um diese zu entschl"usseln.\par \vskip + 3pt

Alle klassischen Verfahren sind von diesem Typ. Beispiele dazu finden Sie im
Programm CrypTool, im Kapitel  \ref{Kapitel_PaperandPencil} 
(Papier- und Bleistift-Verschl"usselungsverfahren) in diesem Skript oder 
in \cite{Nichols1996}. 
Im folgenden wollen wir jedoch nur die moderneren Verfahren betrachten.

Vorteile von symmetrischen Algorithmen sind die hohe
Geschwindigkeit, mit denen Daten ver- und entschl"usselt werden.
Ein Nachteil ist das Schl"usselmanagement. Um miteinander
vertraulich kommunizieren zu k"onnen, m"ussen Sender und
Empf"anger vor Beginn der eigentlichen Kommunikation "uber einen
sicheren Kanal einen Schl"ussel ausgetauscht haben. Spontane
Kommunikation zwischen Personen, die sich vorher noch nie begegnet
sind, scheint so nahezu unm"oglich. Soll in einem Netz mit $ n $
Teilnehmern jeder mit jedem zu jeder Zeit spontan kommunizieren
k"onnen, so muss jeder Teilnehmer vorher mit jedem anderen der
$n - 1$ Teilnehmer einen Schl"ussel ausgetauscht haben. Insgesamt
m"ussen also $n(n - 1)/2$ Schl"ussel ausgetauscht werden.\par \vskip + 3pt

Das bekannteste symmetrische Verschl"usselungsverfahren ist der \index{DES} 
DES-Algorithmus. Der DES-Algorithmus ist eine Entwicklung von IBM 
in Zusammenarbeit mit der National Security Agency \index{NSA} (NSA). 
Er wurde 1975 als Standard ver"offentlicht. Trotz seines relativ hohen
Alters ist jedoch bis heute kein  ~\glqq effektiver\grqq~ Angriff auf
ihn gefunden worden. Der effektivste Angriff besteht aus dem Durchprobieren
(fast) aller m"oglichen Schl"ussel, bis der richtige gefunden wird 
({\em brute-force-attack})\index{Angriff!Brute-force}. Aufgrund der relativ kurzen
Schl"ussell"ange von effektiv 56 Bits (64 Bits, die allerdings 8 Parit"atsbits enthalten),
sind in der Vergangenheit schon mehrfach mit dem DES verschl"usselte Nachrichten gebrochen worden, so dass
er heute als nur noch bedingt sicher anzusehen ist. Symmetrische Alternativen zum DES sind zum Beispiel die Algorithmen
IDEA \index{IDEA} oder Triple-DES.\par \vskip + 3pt

Hohe Aktualit"at besitzt das symmetrische AES-Verfahren: \index{AES} 
Der dazu geh"orende Rijndael-Algo"-rithmus wurde am 2. Oktober 2000 zum
Gewinner der AES-Ausschreibung erkl"art und ist damit Nachfolger
des DES-Verfahrens.

N"aheres zum AES-Algorithmus und den AES-Kandidaten der letzten Runde finden
Sie in der CrypTool-Online-Hilfe\index{CrypTool}%
\footnote{%
      CrypTool-Online-Hilfe\index{CrypTool}: das Stichwort {\bf AES} im Index
      f"uhrt auf die 3 Hilfeseiten: {\bf AES-Kandidaten}, 
      {\bf Der AES-Gewinner Rijndael} und {\bf Der AES-Algorithmus Rijndael}.
  }.


% --------------------------------------------------------------------------
\subsubsection{Neue Ergebnisse zur Kryptoanalyse von AES}
\index{Kryptoanalyse} \label{NeueAES-Analyse}

Im Anschluss finden Sie einige Informationen, die das AES-Verfahren in letzter Zeit in Zweifel zogen -- unserer Ansicht nach aber (noch) unbegr"undet. Die folgenden Informationen beruhen auf den unten angegebenen Originalarbeiten und auf \cite{Wobst-iX2002} und \cite{Lucks-DuD2002}.

Der AES bietet mit einer Mindestschl"ussell"ange von 128 Bit gegen Brute-force-Angriffe auch auf l"angere Sicht gen"ugend Sicherheit -- es sei denn, es st"unden entsprechend leistungsf"ahige Quantencomputer zur Verf"ugung. Der AES war immun gegen alle bis dahin bekannten Kryptoanalyse-Verfahren, die vor allem auf statistischen "Uberlegungen beruhen und auf DES angewandt wurden: man konstruiert aus Geheim- und Klartextpaaren Ausdr"ucke, die sich nicht rein zuf"allig verhalten, sondern R"uckschl"usse auf den verwendeten Schl"ussel zulassen. Dazu waren aber unrealistische Mengen an abgeh"orten Daten n"otig.

Bei Kryptoverfahren bezeichnet man solche Kryptoanalyseverfahren als ''akademischen Erfolg'' oder als ''kryptoanalytischen Angriff'', da sie theoretisch schneller sind als das Durchprobieren aller Schl"ussel, das beim Brute-force-Angriff\index{Angriff!Brute-force} verwendet wird. Im Fall des AES mit maximaler Schl"ussell"ange (256 Bit) braucht die ersch"opfende Schl"usselsuche im Durchschnitt $2^{255}$ Verschl"usselungsoperationen. Ein kryptoanalytischer Angriff muss diesen Wert unterbieten. Als aktuell gerade noch praktikabel (z.B. f"ur einen Geheimdienst) gilt ein Aufwand von $2^{75}$ bis $2^{90}$ Verschl"usselungsoperationen.

Eine neue Vorgehensweise wurde in der Arbeit von Ferguson, Schroeppel und Whiting im Jahre 2001 \cite{Ferguson2001} beschrieben: sie stellten AES als geschlossene Formel (in der Form einer Art Kettenbruch) dar, was aufgrund seiner ''relativ'' "ubersichtlichen Struktur gelang. Da diese Formel aus rund 1 Billiarde Summanden besteht, taugt sie zun"achst nicht f"ur die Kryptoanalyse. Dennoch war die wissenschaftliche Neugier geweckt. Bereits bekannt war, dass sich der 128-Bit-AES als ein "uberbestimmtes System von rund 8000 quadratischen Gleichungen ("uber algebraischen Zahlk"orpern) mit rund 1600 Variablen (einige Unbekannte sind die Schl"usselbits) darstellen l"asst -- solch gro"se Gleichungssysteme sind praktisch nicht l"osbar. Dieses Gleichungssystem ist relativ d"unn besetzt (''sparse''), d.h. von den insgesamt etwa 1.280.000 m"oglichen quadratischen Termen tauchen nur relativ wenige "uberhaupt im Gleichungssystem auf.

Die Mathematiker Courois und Pieprzyk \cite{Courtois2002} ver"offentlichten 
2002 eine Arbeit, die in der Krypto-Szene stark diskutiert wird: Sie 
entwickelten das auf der Eurocrypt 2000 von Shamir et al. vorgestellte 
XL-Verfahren (eXtended Linearization) weiter zum XSL-Verfahren 
(eXtended Sparse Linearization). Das XL-Verfahren ist eine heuristische 
Technik, mit der es manchmal gelingt, gro"se nicht-lineare Gleichungssysteme 
zu l"osen und die bei der Analyse eines asymmetrischen Algorithmus (HFE) 
angewandt wurde.  Die Innovation von Courois und Pieprzyk war, das 
XL-Verfahren auf symmetrische Verfahren anzuwenden: das XSL-Verfahren kann
auf spezielle Gleichungssysteme angewandt werden. Damit k"onnte ein 
256-Bit-AES-Verfahren in rund $2^{230}$ Schritten geknackt werden. Dies ist 
zwar immer noch ein rein akademischer Angriff, aber er ist richtungsweisend
f"ur eine ganze Klasse von Blockchiffren. Das generelle Problem mit diesem
Angriff besteht darin, dass man bisher nicht angeben kann, unter welchen
Umst"anden er zum Erfolg f"uhrt: die Autoren geben in ihrer Arbeit notwendige
Bedingungen an; es ist nicht bekannt, welche Bedingungen hinreichend sind.
Neu an diesem Angriff war erstens, dass dieser Angriff nicht auf Statistik,
sondern auf Algebra beruhte. Dadurch erscheinen Angriffe m"oglich, die nur
geringe Mengen von Geheimtext brauchen. Zweitens steigt damit die Sicherheit
eines Produktalgorithmus\index{Produktalgorithmus}%
\footnote{%
Ein Geheimtext kann selbst wieder Eingabe f"ur eine Chiffrierung sein. Eine
Mehrfachverschl"usselung (cascade cipher)\index{Mehrfachverschl\""usselung}
entsteht aus einer Komposition von mehreren Verschl"usselungstransformationen.
Die Gesamtchiffrierung wird Produktalgorithmus oder Kaskadenalgorithmus
genannt (manchmal ist die Namensgebung abh"angig davon, ob die verwendeten
Schl"ussel statistisch abh"angig oder unabh"angig sind).\\
Nicht immer wird die Sicherheit eines Verfahrens durch Produktbildung 
erh"oht.\\
Diese Vorgehen wird auch {\em innerhalb} moderner Algorithmen angewandt:
Sie kombinieren in der Regel einfache und, f"ur sich genommen, kryptologisch
relativ unsichere Einzelschritte in mehreren Runden zu einem leistungsf"ahigen
Gesamtverfahren. Die meisten modernen Blockchiffrierungen (z.B. DES, IDEA)
sind Produktalgorithmen.\\
Als Mehrfachverschl"usselung wird auch das Hintereinanderschalten desselben
Verfahrens mit verschiedenen Schl"usseln wie bei Triple-DES bezeichnet. 
}
nicht mehr exponentiell mit der Rundenzahl.

Aktuell wird sehr intensiv auf diesem Gebiet geforscht: z.B. stellten Murphy und Robshaw auf der Crypto 2002 ein Papier vor \cite{Robshaw2002a}, das die Kryptoanalyse drastisch verbessern k"onnte: der Aufwand f"ur 128-Bit-Schl"ussel wurde auf $2^{100}$ gesch"atzt, indem sie AES als Spezialfall eines Algorithmus BES (Big Encryption System) darstellten, der eine besonders ''runde'' Struktur hat. Aber auch $2^{100}$ Rechenschritte liegen jenseits dessen, was praktisch in absehbarer Zeit realisierbar ist. Bei 256 Bit Schl"ussell"ange sch"atzen die Autoren den Aufwand f"ur den XSL-Angriff auf $2^{200}$ Operationen.

Weitere Details dazu stehen unter:
% nur \href r"uckt nicht ein, deshalb \item dazu !
\vspace{-10pt}
\begin{itemize}
  \item[] \href{http://www.cryptosystem.net/aes}
               {\texttt{http://www.cryptosystem.net/aes}} \\
          \href{http://www.minrank.org/aes/}
               {\texttt{http://www.minrank.org/aes/}}
\end{itemize}

F"ur 256-AES w"are der Angriff ebenfalls viel besser als Brute-force\index{Angriff!Brute-force}, 
aber auch noch weiter au"serhalb der Reichweite realisierbarer Rechenpower.

\begin{sloppypar}
Die Diskussion ist z.Zt. sehr kontrovers: Don Coppersmith (einer der DES-Erfinder) 
z.B. bezweifelt die generelle Durchf"uhrbarkeit des Angriffs: XLS liefere f"ur 
AES gar keine L"osung \cite{Coppersmith2002}. Dann w"urde auch die Optimierung von 
Murphy und Robshaw \cite{Robshaw2002b} nicht greifen.
\end{sloppypar}

% --------------------------------------------------------------------------
\subsubsection{Aktueller Stand der Brute-force-Angriffe auf 
symmetrische Verfahren (RC5)}
\index{Angriff!Brute-force}
\index{RC5}
\label{Brute-force-gegen-Symmetr}

Anhand der Blockchiffre RC5 kann der aktuelle Stand von Brute-force-Angriffen
auf symmetrische Verschl"usselungsverfahren gut erl"autert werden.

\begin{sloppypar}
Als Brute-force-Angriff (exhaustive search, trial-and-error) bezeichnet man das vollst"andige Durchsuchen des Schl"usselraumes: dazu m"ussen keine besonderen Analysetechniken eingesetzt werden. Stattdessen wird der Ciphertext mit allen m"oglichen Schl"usseln des Schl"usselraums entschl"usselt und gepr"uft, ob der resultierende Text einen sinnvollen Klartext ergibt. Bei einer Schl"ussell"ange von 64 Bit sind dies maximal $2^{64}$ = 18.446.744.073.709.551.616 oder rund 18 Trillionen zu "uberpr"ufende Schl"ussel\index{CrypTool}%
\footnote{%
Mit CrypTool\index{CrypTool} k"onnen Sie "uber das Men"u
        {\bf Analyse \textbackslash{} Symmetrische Verschl"usselung (modern)}
ebenfalls Brute-force-Analysen von modernen symmetrischen Verfahren durchf"uhren
(unter der schw"achsten aller m"oglichen Annahmen: der Angreifer kennt nur den
Geheimtext, er f"uhrt also einen Ciphertext only-Angriff durch). 
Um in einer sinnvollen Zeit auf einem Einzel-PC ein Ergebnis zu erhalten, sollten
Sie nicht mehr als 20 Bit des Schl"ussels als unbekannt kennzeichnen.
}.
\end{sloppypar}

Um zu zeigen, welche Sicherheit bekannte symmetrische Verfahren wie DES, Triple-DES oder RC5 haben, veranstaltet z.B. RSA Security sogenannte Cipher-Challenges\footnote{\href{http://www.rsasecurity.com/rsalabs/challenges/secretkey/index.html}{\tt http://www.rsasecurity.com/rsalabs/challenges/secretkey/index.html}}. Unter kontrollierten Bedingungen werden Preise ausgelobt, um Ciphertexte 
(verschl"usselt mit verschiedenen Verfahren und verschiedenen Schl"ussell"angen) zu entschl"usseln und den symmetrischen Schl"ussel zu ermitteln. Damit werden theoretische Resultate praktisch best"atigt.

Dass das "`alte"' Standard-Verfahren DES mit der fixen Schl"ussell"ange von 56 Bit nicht mehr sicher ist, wurde schon im Januar 1999 von der Electronic Frontier Foundation (EFF) demonstriert, als sie mit Deep Crack eine DES-verschl"usselte Nachricht in weniger als einem Tag knackten\footnote{\href{http://www.rsasecurity.com/rsalabs/challenges/des3/index.html}{\tt http://www.rsasecurity.com/rsalabs/challenges/des3/index.html}}.

Der aktuelle Rekord f"ur starke symmetrische Verfahren liegt bei 64 Bit langen Schl"usseln. Dazu wurde das Verfahren RC5 benutzt, eine Blockchiffre mit variabler Schl"ussell"ange. 

Die RC5-64 Challenge wurde im September 2002 nach 5 Jahren vom distributed.net-Team gel"ost\footnote{\href{http://distributed.net/pressroom/news-20020926.html}{\tt http://distributed.net/pressroom/news-20020926.html}}. Insgesamt arbeiteten 331.252 Personen gemeinsam "uber das Internet zusammen. Getestet wurden rund 15 Trillionen Schl"ussel, bis der richtige Schl"ussel gefunden wurde.

Damit ist gezeigt, dass symmetrische Verfahren (auch wenn sie keinerlei kryptographische Schw"a"-chen haben) mit 64 Bit langen Schl"usseln keine geeigneten Verfahren mehr sind, um sensible Daten l"anger geheim zu halten.

"Ahnliche Cipher-Challenges gibt es auch f"ur asymmetrische Verfahren (siehe Kapitel \ref{NoteFactorisation}).




% --------------------------------------------------------------------------
\subsection[Asymmetrische Verschl"usselung]
{Asymmetrische Verschl"usselung\footnotemark}
        \footnotetext{%
        Mit CrypTool\index{CrypTool} k"onnen Sie "uber das Men"u
        {\bf Ver-/Entschl"usseln \textbackslash{} Asymmetrisch} mit RSA 
        ver- und entschl"usseln. In beiden F"allen m"ussen Sie ein 
        RSA-Schl"usselpaar ausw"ahlen. Nur bei der Entschl"usselung wird der 
        geheime RSA-Schl"ussel ben"otigt: deshalb wird nur hier die PIN
        abgefragt. 
        }

Bei der {\em asymmetrischen} Verschl"usselung
\index{Verschl""usselung!asymmetrisch} hat jeder Teilnehmer 
ein pers"onliches Schl"usselpaar, % Schl"us\-selpaar, be_24.5.03: so vorher und kam auch richtig raus! 
das aus einem {\em geheimen} \index{Schl""ussel!geheim} und einem 
{\em "offentlichen} Schl"ussel \index{Schl""ussel!""offentlich} besteht.
Der "offentliche Schl"ussel wird, der Name deutet es an,
"offentlich bekanntgemacht, zum Beispiel in einem Schl"usselverzeichnis
im Internet.\par \vskip + 3pt

M"ochte Alice\index{Alice}%