285 lines
21 KiB
TeX
285 lines
21 KiB
TeX
% Diese Zeile bitte -nicht- aendern.
|
|
\documentclass[course=erap]{aspdoc}
|
|
\usepackage{listings}
|
|
\usepackage{float}
|
|
|
|
\newcommand{\theGroup}{199}
|
|
\newcommand{\theNumber}{A505}
|
|
\author{Dorian Zedler \and Finn Dröge \and Thomas Florian}
|
|
\date{Sommersemester 2022}
|
|
% Diese Zeile bitte -nicht- aendern.
|
|
\title{Gruppe \theGroup{} -- Abgabe zu Aufgabe \theNumber}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
|
|
\section{Einleitung}
|
|
Der Begriff \glqq Hashing\grqq{} bedeutet ursprünglich \glqq zerhacken und mischen\grqq. Das bedeutet, eine Hashfunktion zerhackt und mischt Informationen und leitet daraus ein Hash-Ergebnis ab \cite{hashing-techniques}.
|
|
1989 hat Ron Rivest die Hashfunktion Message-Digest 2 Algorithm (MD2) veröffentlicht. Für eine lange Zeit war der MD2-Funktion eine der meist verwendeten Hashfunktionen. Die Hauptanwendungsgebiete sind Passwortsicherung, Nachrichtenauthentifizierungscodes, digitale Signaturen und somit auch Zertifikate~\cite{notoneway}. 2004 wurde die Hashfunktion im Paper \glqq The MD2 Hash Function is Not One-Way\grqq{} von Frédéric Muller als unsicher erklärt \cite{notoneway}. \\
|
|
|
|
In dieser Arbeit wird auf die Eigenschaften von Hashfunktionen eingegangen, sowie deren Anwendungsbereich. Schwachpunkte der MD2-Funktion werden aufgezeigt und alternative Algorithmen werden genannt. Insbesondere wird die Berechnung des MD2-Hashes erklärt und die Performance verschiedener Implementierungen analysiert.
|
|
|
|
|
|
\subsection{Die Eigenschaften kryptografischer Hashfunktionen}
|
|
Sichere Hashfunktionen müssen 3 Kriterien erfüllen:
|
|
|
|
\subsubsection{Preimage-Resistance}
|
|
Preimage-Resistance besagt, dass eine Hashfunktion nur sehr schwer umkehrbar sein darf.
|
|
Das heißt, dass die zu einem Hash gehörige Eingabe nur mit sehr hohem Rechenaufwand bestimmt werden kann.~\cite{notoneway} \\
|
|
Mit gegebenem $y = H(x)$ sollte es schwer sein, ein $x' \neq x$ zu finden, sodass gilt: \\
|
|
$H(x') = y$.~\cite{preimage}
|
|
|
|
\subsubsection{Second-Preimage-Resistance}
|
|
Second-Preimage-Resistance ist dann gewährleistet, wenn es für eine gegebene Ein- und Ausgabe einer Hashfunktion sehr schwierig ist, eine weitere Eingabe zu finden, die dieselbe Ausgabe produziert.~\cite{notoneway} \\
|
|
Mit gegebenem $x$ und $y = H(x)$ sollte es schwer sein, ein $x' \neq x$ zu finden, sodass gilt:
|
|
$H(x') = y$.~\cite{preimage}
|
|
|
|
\subsubsection{Collision-Resistance}
|
|
Die Collision-Resistance ist dann erfüllt, wenn es nur sehr wenige gleiche Hashes für unterschiedliche Eingaben gibt.
|
|
Bei einer Hashfunktion mit einer hohen Collision-Resistance ist die Second-Preimage-Resistance auch hoch.
|
|
Wenn es nur wenige Kollisionen des Hashes gibt, ist es folglich auch schwerer, eine Eingabe zu finden, die denselben Hash produziert.~\cite{notoneway} \\
|
|
Es sollte schwer sein, ein $x$ und $x'$ zu finden, sodass gilt: $x \neq x'$ und $H(x) = H(x')$.~\cite{preimage}
|
|
|
|
\subsection{Angriffe auf Hashfunktion}
|
|
\label{section:geburtstagsparadoxon}
|
|
Zu jedem der oben genannten Kriterien gibt es einen entsprechenden Angriff. Der Preimage-Angriff und der Second-Preimage-Angriff kann über eine Brute-Force- \linebreak Implementierung mit einer Komplexität von $2^n$ durchgeführt werden, wobei n der Anzahl an Bits des Hashes entspricht. Da die MD2-Funktion einen 128 Bit großen Hash erstellt, hat dieser eine Komplexität von $2^{128}$. Aufgrund des Geburtstagsparadoxons hat der Brute-Force-Kollisionsangriff die Komplexität $2^{n/2}$ (für MD2: $2^{64}$).
|
|
Eine Hashfunktion gilt als sicher, wenn es keine effizienteren Angriffe als diese drei Brute-Force-Angriffe gibt.
|
|
~\cite{preimage}
|
|
|
|
\subsubsection{Preimage-Angriff}
|
|
Bei einem Preimage-Angriff soll zu einem gegebenen Hash die dazu passende Nachricht gefunden werden.
|
|
Der aktuell schnellste Preimage-Angriff auf MD2 wurde im Jahr 2008 von Søren S. Thomsen veröffentlicht~\cite{preimage}.
|
|
Dort wird beschrieben, wie die vorherigen Zwischenergebnisse, anhand eines entdeckten Musters in der Berechnung, wiederhergestellt werden können. Es kann durch die bijektive Eigenschaft von XOR aus zwei Elementen auf das dritte geschlossen werden ~\cite{collisionattack}. Dadurch gibt es weniger mögliche Permutationen, welche die Eingangsnachricht annehmen kann. Insgesamt reduziert dieses Verfahren die Komplexität des Preimage-Angriffs von $2^{128}$ auf $2^{73}$.
|
|
|
|
\subsubsection{Kollisionsangriff}
|
|
Basierend auf ähnlichen Mustererkennungen kann auch ein Kollisionsangriff auf den MD2-Hash durchgeführt werden.
|
|
Somit verringert sich die Komplexität des oben beschriebenen Kollisionsangriffs von $2^{64}$ auf $2^{54}$ mithilfe einer \glqq Collision Attack with Arbitrary Chaining Input\grqq ~\cite{collisionattack}.
|
|
|
|
|
|
|
|
\subsection{Alternativen zu MD2}
|
|
Wegen der oben genannten Angriffe gilt die MD2-Hashfunktion seit 2004 als unsicher. Mögliche Alternativen wären die Nachfolger von MD2, die auch von Ron Rivest entwickelt wurden: MD4 und MD5. MD4 wurde 1991, nur ein Jahr nach Veröffentlichung, bereits als unsicher erklärt und gilt daher nicht als Alternative~\cite{md4}. 2005 wurde MD5 als unsicher gegen Kollisionsattacken deklariert~\cite{md5}.
|
|
Gängige Alternativen sind die Secure Hashing Algorithms (SHA-1, SHA-2, SHA-256, etc.)~\cite{sha256}. Insbesondere SHA-256 gilt als sicher (Stand: August 2015)~\cite{sha265secure} und wird daher als weitverbreitete Alternative genutzt.
|
|
|
|
|
|
|
|
\subsection{Anwendungen von kryptografischen Hashfunktionen}
|
|
|
|
Das heutzutage wohl wichtigste Anwendungsgebiet von Hashes ist das Sichern von Passwörtern zur Authentifizierung an computergestützten Systemen~\cite{salt-password-hashes}.
|
|
Die Passwörter werden gehasht für den Fall, dass eine Datenbank mit den Passwörter-Hashes in die Hände Dritter gelangt. Durch das Hashing ist es praktisch unmöglich, den Klartext der Passwörter festzustellen.
|
|
Um eine Wörterbuch-Attacke vorzubeugen, wird oft zusätzlich vor dem Hashing noch ein \glqq salt\grqq{} (zufällige Daten) an das Passwort angehangen. \\
|
|
Eine weitere gängige Anwendung ist die digitale Signierung von Daten. Hierbei wird der aus den Daten gebildete Hash signiert~\cite{pgp-message-formats}. So kann sichergestellt werden, dass jene Daten nach der Signierung nicht mehr verändert wurden, da jede kleine Änderung an den Daten den Hash stark verändern würde. \\
|
|
Auch wenn es darum geht, eine Kette von Ereignissen kryptografisch zu fixieren, ist Hashing ein wichtiges Werkzeug. In einer sogenannten Blockchain enthält jedes Element (z.B. eine Überweisung) den Hash des vorherigen Elementes~\cite{what-is-blockchain}. Dadurch ist es möglich, die gesamte Kette an Überweisungen zu verifizieren. Ein praktisches Beispiel dafür sind Kryptowährungen wie Bitcoin. \\
|
|
|
|
|
|
|
|
\subsection{Berechnung von Prüfsumme und Hashwert in der MD2-Hashfunktion}
|
|
\label{section:berechnung}
|
|
Die MD2-Hashfunktion lässt sich in drei Schritte gliedern: Padding hinzufügen, Prüfsumme berechnen und einer finalen Berechnung.
|
|
|
|
\subsubsection{Padding}
|
|
\label{section:padding}
|
|
Damit eine Nachricht mit MD2 gehasht werden kann, muss die Länge der Nachricht zunächst ein Vielfaches von 16 sein.
|
|
MD2 benutzt dafür das Paddingverfahren PKCS\#7. Dieses fügt an eine Nachricht N Bytes mit dem Wert N an. \\
|
|
Im folgenden Beispiel ist N = 5:
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\includegraphics[width=1.0\columnwidth]{Padding.png}
|
|
\caption{Padding Beispiel}
|
|
\end{figure}
|
|
|
|
Bei dem Verfahren muss mindestens ein Byte eingefügt werden. Somit werden genau 16 Bytes mit dem Wert 16 angefügt, falls die Nachricht bereits ein Vielfaches von 16 ist. Damit stellt man sicher, dass das letzte Byte eindeutig zum Padding gehört. \\
|
|
Zudem wird ein trivialer Preimage-Angriff verhindert: \\
|
|
Zur Vereinfachung wird angenommen, dass das erwähnte Paddingverfahren die Nachrichtenlänge auf ein Vielfaches von 8 bringt. \\
|
|
Sei $m_1 = [01, 01, 01, 01, 01]$ die Eingabe. Dann wird $m_1$ mit diesem Paddingverfahren zu $p_1 = [01, 01, 01, 01, 01, 03, 03, 03]$ erweitert.\\
|
|
Existiert die Bedingung der Mindestpaddinggröße nicht, so könnte nun $m_2 = [01, 01, 01,$ \linebreak $01, 01, 03, 03, 03]$ als Nachricht gewählt werden. Dann ist $m_2$ inklusive Padding: \linebreak $m_2 = p_1 = [01, 01, 01, 01, 01, 03, 03, 03]$. Dadurch kommt es zu $hash(m_1) = hash(m_2)$, wobei $m_1 \neq m_2$.
|
|
Mit der Mindestpaddinggröße ergibt, sich $p'_2 = [01, 01, 01, 01, 01, 03, 03,$ \linebreak $03, 08, 08, 08, 08, 08, 08, 08, 08]$, was den Preimage-Angriff verhindert. In der Regel gilt dann $hash(m_1) \neq hash(m_2)$, weshalb kein trivialer Preimage-Angriff möglich ist. \\
|
|
Beim MD2-Hash gilt zusätzlich, dass für den Fall einer leeren Nachricht ein Padding mit 16 Bytes angefügt wird. Die Prüfsumme und der Hash können damit ohne eine Fallunterscheidung gebildet werden~\cite{md2man},~\cite{cmsman}.
|
|
|
|
\subsubsection{Substitutionsbox}
|
|
\label{section:substitution}
|
|
Zur weiteren Berechnung wird eine Substitutionsbox verwendet, die sich aus Nachkommastellen von $\pi$ zusammensetzen lässt.
|
|
Hierbei werden die Nachkommastellen mithilfe des Durstenfeld-Shuffle ausgewählt.~\cite{pidigits}.
|
|
Die Zahlen der Box werden als Zufallszahlen angesehen und werden verwendet, um das Ergebnis zu streuen.
|
|
|
|
\subsubsection{Prüfsumme}
|
|
An die Padding-Bytes werden 16 weitere Bytes angehängt, die sogenannte Prüfsumme. Diese Bytes werden zunächst mit 0 initialisiert.
|
|
Für die Berechnung der Prüfsumme wird für jedes n-te Byte der Prüfsumme die XOR-Operation auf das Byte selbst mit einem Wert von der Substitutionsbox $\pi$ ausgeführt:
|
|
\[ Pr"ufsumme[n] = Pr"ufsumme[n] \oplus \pi [k] \]
|
|
|
|
Der Index k der Substitutionsbox $\pi$ in dem i-ten Schleifendurchlauf ist das Ergebnis der XOR-Operation von dem $(i*16 + n)$-ten Byte der Nachricht (inklusive Padding) mit dem vorherigen Byte der Prüfsumme:
|
|
\[ k = Nachricht[i*16 + n] \oplus Pr"ufsumme[n-1 \mod 16] \]
|
|
|
|
Hierbei gilt es zu beachten, dass das erste Byte keinen Vorgänger hat. Hier wird das letzte Byte als Vorgänger verwendet. Deswegen ist die Formel für den Vorgänger von n als $n-1 \mod 16$ definiert. \\
|
|
In der folgenden Grafik wird die Berechnung des achten Bytes der Prüfsumme veranschaulicht:
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\includegraphics[width=1.0\columnwidth]{MD2Checksum.png}
|
|
\caption{MD2-Prüfsumme ~\cite{md2berechnung}}
|
|
\end{figure}
|
|
|
|
Beispielsweise wird im dritten Schleifendurchlauf das oben dargestellte achte Byte der Prüfsumme wie folgt berechnet:
|
|
\[ Pr"ufsumme[8] = Pr"ufsumme[8] \oplus \pi [k] \]
|
|
mit
|
|
\[ k = Nachricht[3*16 + 8] \oplus Pr"ufsumme[8-1 \mod 16] \]
|
|
|
|
|
|
\subsubsection{Finale Berechnung}
|
|
\label{section:mdupdate}
|
|
Zur finalen Berechnung werden zunächst weitere 48 Byte Speicher alloziert und mit dem Wert 0 initialisiert.
|
|
Im Folgenden werden diese 48 Bytes in 3 Blöcke unterteilt: Block A beschreibt die ersten 16 Byte, Block B die mittleren 16 Byte und Block C die letzten 16 Byte.
|
|
Die Daten des zuvor erzeugten Buffers aus Nachricht, Padding und Prüfsumme werden mithilfe von weiteren Operationen verarbeitet und in die entsprechenden Blöcke geschrieben. \\
|
|
Als Erstes wird vom Buffer ein 16-Byte Block in Block B kopiert.
|
|
Anschließend wird in Block C das Ergebnis der XOR-Operation in Block A und B geschrieben.
|
|
Danach werden alle Bytes der drei Blöcke 18 Mal durchlaufen.
|
|
Zur Berechnung eines Bytes wird die XOR-Operation auf ein Element der Substitutionsbox $\pi$ und das Byte selbst angewandt:
|
|
\[ Byte[k] = Byte[k] \oplus \pi [t] \]
|
|
Das ausgewählte Element der Substitutionsbox wird durch das vorherige Byte und den Schleifendurchlauf j bestimmt:
|
|
\[ t = (Byte[k-1] + j) \mod 256 \]
|
|
Somit ist jedes Byte von seinem Vorgänger abhängig. Da das erste Byte keinen Vorgänger hat, wird hier das letzte Byte als Vorgänger verwendet:
|
|
\[ Byte[0] = Byte[0] \oplus \pi [t] \]
|
|
mit
|
|
\[ t = (Byte[47] + j) \mod 256 \]
|
|
im ersten der 18 Schleifendurchläufe wird außerdem $t = 0$ gesetzt.
|
|
|
|
Dieses Verfahren wird für jeden 16-Byte Block des Buffers wiederholt.
|
|
Nach allen Iterationen steht der Hash in Block A.
|
|
Das beschriebene Verfahren wird in Abbildung \ref{md2finalehashberechnung} dargestellt.
|
|
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\includegraphics[width=1.0\columnwidth]{MD2HashBerechnung.png}
|
|
\caption{MD2 Finale Hash Berechnung ~\cite{md2berechnung}}
|
|
\label{md2finalehashberechnung}
|
|
\end{figure}
|
|
|
|
|
|
\section{Lösungsansatz}
|
|
|
|
\subsection{V0 - Basis-Implementierung}
|
|
Die Basis-Implementierung wurde mithilfe des Pseudocodes, welcher auf in der RFC1319 Spezifikation \cite{md2man} zu finden ist, erstellt. Sie folgt genau dem oben beschriebenen Schema (siehe Kapitel \ref{section:berechnung}).
|
|
|
|
|
|
|
|
\subsection{V1 - Optimierte Implementierung mit SIMD}
|
|
In dieser Implementierung wird der Code mittels SIMD-Operationen optimiert.
|
|
Eine for-Schleife zur Berechnung des Hashes wird durch 5 Intrinsics-Operationen ersetzt.
|
|
Beispielsweise wird in der Schleife eine XOR-Operation auf jedes Element eines Buffers ausgeführt.
|
|
Diese vielen iterativen Berechnungen werden durch den Befehl \texttt{\_mm\_xor\_si128(x,y)} ersetzt.
|
|
\\
|
|
Das Einsetzen des Paddings wird mithilfe einer LUT gemacht. Hierbei verbessert sich die Laufzeit jedoch nicht, weil trotzdem ein \texttt{memcpy()} aufrufen wird.
|
|
\\
|
|
Kleinere Optimierungen werden auch vorgenommen, wie das Ersetzen des Modulo-Operators durch ein logisches UND.
|
|
\\
|
|
Weitere SIMD-Optimierungen können nicht gemacht werden, da die Berechnungen von Elementen immer von der Berechnung ihres Vorgängers abhängen.
|
|
|
|
|
|
\subsection{V2 - Implementierung mit partiellem Einlesen der Datei}
|
|
In den anderen Implementierungen wird die gesamte Datei zu Beginn in den RAM geladen. Zusätzlich muss nochmals so viel Speicher alloziert werden, um Platz für das Padding und die Prüfsumme zu schaffen. Daher ist die Dateigröße auf maximal die Hälfte des Hauptspeichers abzüglich Padding und Prüfsumme beschränkt. Der Speicherbedarf ist also in $\mathcal{O}(n)$. \\
|
|
In dieser Implementierung wird die Datei in 16-Byte Blöcken geladen, welche jeweils einzeln verarbeitet und danach wieder aus dem Hauptspeicher gelöscht werden. Daher ist der Speicherbedarf hier in $\mathcal{O}(1)$ und es können beliebig große Dateien verarbeitet werden.
|
|
\\
|
|
Bei der Implementierung dieser Optimierung konnten die Vorgaben aus der Aufgabenstellung nicht eingehalten werden, da sie das vollständige Laden der Datei in den Hauptspeicher voraussetzen. Auch die Funktionen
|
|
\begin{lstlisting}
|
|
void md2_checksum(size_t len, uint8_t* buf)
|
|
\end{lstlisting} und
|
|
\begin{lstlisting}
|
|
void md2_hash(size_t len, const uint8_t buf[len], uint8_t out[16])
|
|
\end{lstlisting} konnten aus diesem Grund nicht so umgesetzt werden, da auch sie das Vorhandensein der gesamten Datei im Hauptspeicher voraussetzen.
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\includegraphics[width=0.8\columnwidth]{Performance10GB.png}
|
|
\caption{Vorteil der zweiten Implementierung}
|
|
\label{fig:impl2}
|
|
\end{figure}
|
|
|
|
Die Vorteile dieser Implementierung zeigen sich in Abbildung \ref{fig:impl2}. Nachdem die Größe der Eingabe ca. 6 Gigabyte überschreitet, funktioniert bei dem verwendeten Rechner nur noch diese Implementierung.
|
|
|
|
\subsection{V3 - Optimierte Implementierung mit Threading}
|
|
Bei dieser Implementierung soll die Berechnung des Hashes in zwei Threads aufgeteilt werden. Ein Thread soll sich um die Berechnung der Prüfsumme durchführen, während der zweite den Hash für die Nachricht berechnen soll. \\
|
|
Aus dem Main-Thread werden mithilfe der Funktion \texttt{pthread\_create()} diese beiden Threads erstellt. Sobald diese mit ihrer Berechnung fertig sind, werden die Threads wieder mittels \texttt{pthread\_join()} wieder in den Main-Thread zusammengeführt.\\
|
|
Durch das Aufteilen wurde die Prüfsumme noch nicht mit in den Hash gerechnet.
|
|
Deswegen wird die Funktion zur Berechnung des Hashes ein weiteres Mal aufgerufen. \\
|
|
Auch in dieser Implementierung konnten die Vorgaben der Aufgabenstellung nicht eingehalten werden. Die Funktionsköpfe mussten so angepasst werden, dass diese für Threads geeignet sind.
|
|
|
|
\subsection{V4 - Referenzimplementierung}
|
|
\label{referenzimplmentierung}
|
|
Als vierte Implementierung wurde die Referenzimplementierung aus der RFC1319 Spezifikation \cite{md2man} übernommen. Sie ist ein wichtiges Werkzeug, um die Korrektheit der anderen Implementierungen zu beurteilen.
|
|
|
|
\section{Korrektheit}
|
|
|
|
Um die Korrektheit der Implementierungen zu testen, wurden zwei Strategien angewendet: \\
|
|
Zuerst wurden Beispielwerte von der RFC1319 Spezifikation \cite{md2man} getestet. Zusätzlich wurden einige Dateien mit zufälligen Daten getestet und mit den Ergebnissen der Referenzimplementierung (siehe \ref{referenzimplmentierung}) verglichen. \\
|
|
Da schon kleine Fehler im Algorithmus zu sehr großen Abweichungen im Ergebnis führen würden, kann davon ausgegangen werden, dass die Implementierungen korrekt sind. \\
|
|
|
|
|
|
\section{Performance-Analyse}
|
|
|
|
Getestet wurde auf einem System mit einem Intel Core i7-2760QM Prozessor, 2.40GHz, 11GB Arbeitsspeicher, Ubuntu 20.04, 64Bit, Linux-Kernel 5.4. Kompiliert wurde mit GCC 9.3.0 mit der Option \texttt{-O3}.
|
|
Die Berechnungen wurden jeweils 3-mal durchgeführt und das arithmetische Mittel für jede Eingabegröße wurde berechnet.
|
|
|
|
|
|
Um einen groben Überblick über die Performance zu bekommen, wurde zunächst die Laufzeit der gesamten Berechnung des Hashes gemessen. \\
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\includegraphics[width=0.80\columnwidth]{Performance5GB.png}
|
|
\caption{Laufzeitanalyse}
|
|
\label{fig:benchmark1}
|
|
\end{figure}
|
|
|
|
In Abbildung \ref{fig:benchmark1} ist zu erkennen, dass die asymptotische Laufzeit aller Algorithmen in $\mathcal{O}(n)$ liegt. Dies lässt sich dadurch begründen, dass in verschachtelten for-Schleifen maximal eine der Schleifen über n iteriert. Alle anderen Schleifen iterieren über eine konstante Zahl. \\
|
|
|
|
Die größte Schwierigkeit bei der Optimierung des MD2-Algorithmus ist die zweite Schleife der finalen Berechnung. Diese Schleife lässt sich nicht optimieren und benötigt die meiste Zeit bei der Berechnung. Um diese Problematik genauer zu analysieren, wurde die zweite Performance-Analyse entwickelt.
|
|
Hierzu wird die Gesamtlaufzeit in drei Teil-Laufzeiten gegliedert: die Berechnung der Prüfsumme, der ersten sowie der zweiten Schleife im finalen Schritt.\\
|
|
Das Verhältnis dieser verschiedenen Laufzeiten ist in Abbildung \ref{fig:verhaeltnis} dargestellt.
|
|
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\includegraphics[width=0.8\columnwidth]{PiechartRuntime.png}
|
|
\caption{Verhältnis der Teil-Laufzeiten (in Prozent) ~\cite{md2berechnung}}
|
|
\label{fig:verhaeltnis}
|
|
\end{figure}
|
|
|
|
Gemessen wurde mit 100 Megabyte Eingabedaten und dem Durchschnitt über zehn Wiederholungen.\\
|
|
Mit diesem Test ist feststellbar, dass die zweite Schleife im finalen Schritt den Großteil der gesamten Laufzeit ausmacht. Das erklärt, weshalb der Effekt der oben beschriebenen Optimierungen minimal ist.
|
|
\\
|
|
In der dritten Implementierung (Threading) kann lediglich ein Speed-Up durch die Parallelisierung der Prüfsumme erreicht werden. Somit werden bei 100 Megabyte \linebreak maximal 2,31\% der Geschwindigkeit des Programms optimiert.
|
|
In der ersten Implementierung (SIMD) wird die erste Schleife mithilfe von SIMD-Operationen optimiert. Hier kann der Speed-Up maximal 1,56\% betragen.
|
|
Diese beiden Erkenntnisse lassen auch aus den Abbildungen \ref{fig:barchart1} und \ref{fig:barchart2} ablesen.
|
|
|
|
\begin{figure} [H]
|
|
\begin{minipage}[t]{0.5\linewidth}
|
|
\centering
|
|
\includegraphics[width=1\columnwidth]{BarchartNorm.png}
|
|
\caption{Normierte Laufzeitanalyse}
|
|
\label{fig:barchart1}
|
|
\end{minipage}
|
|
\begin{minipage}[t]{0.5\linewidth}
|
|
\centering
|
|
\includegraphics[width=1\columnwidth]{Barchart.png}
|
|
\caption{Vergrößerte Laufzeitanalyse}
|
|
\label{fig:barchart2}
|
|
\end{minipage}
|
|
\end{figure}
|
|
|
|
\newpage
|
|
Im ersten Balkendiagramm ist der Speed-Up kaum zu erkennen. Dies lässt sich mit der nicht optimierbaren zweiten Schleife begründen. Beim Vergrößern des Diagramms (siehe Abbildung \ref{fig:barchart2}) wird der oben beschriebene, geringe Speed-Up in Implementierung 3 erkennbar. Implementierung 1 hat einen noch kleineren Speed-Up, da mit SIMD nicht die vollen 1,56\% wegoptimiert werden können.
|
|
|
|
|
|
\section{Zusammenfassung und Ausblick}
|
|
Der MD2-Algorithmus wurde im Jahr 1989 entwickelt und war lange ein Standard-Hashverfahren für kryptografische Anwendungsbereiche. Er wurde 2004 aufgrund von Attacken als unsicher deklariert.
|
|
Während dem Implementieren hat sich herausgestellt, dass sich der Algorithmus nur schwer optimieren lässt. Kleine Optimierungen können bei großen Datenmengen mittels Threading umgesetzt werden.
|
|
Diese Schwerfälligkeit des Optimierens bringt aber auch Vorteile für den Algorithmus, denn Brute-Force-Angriffe müssen Permutationen ausprobieren, bis das gewünschte Ergebnis erreicht wird. Je zeitintensiver die Berechnung von Hashes sind, desto aufwendiger werden auch die entsprechenden Angriffe.\\
|
|
Weitere Optimierungsmöglichkeiten, welche in diesem Projekt nicht umgesetzt wurden, könnten möglicherweise aus dem Vorgehen der genannten Angriffe resultieren. Dabei könnte es möglich sein, das in den Angriffen erkannte Muster als Anlaufstelle für weitere Parallelisierungen im Code zu benutzen.\\
|
|
Durch Moore's Law kann davon ausgegangen werden, dass sich die Kosten eines Angriffes auf ein Kryptosystem alle 18 Monate halbieren~\cite{mooreslaw}. Deswegen ist es nötig immer komplexere und aufwändigere Hashfunktionen zu entwickeln. In der Zukunft müssen auch die genannten Alternativen zu MD2, so wie MD2 heute, durch solche neuen Hashfunktionen abgelöst werden.
|
|
|
|
|
|
\bibliographystyle{plain}
|
|
\bibliography{Ausarbeitung}{}
|
|
|
|
\end{document} |