130 lines
10 KiB
TeX
130 lines
10 KiB
TeX
\chapter{Hashfunktionen}\label{Hashfunktionen}
|
|
Eine Hashfunktion dient als \say{digitaler Fingerabdruck} einer Nachricht.
|
|
Es wird für jede nachricht ein (nahezu) eindeutiger Wert einer festen Länge bestimmt.
|
|
Eine Abbildung $H:\mathscr M \rightarrow {\mathbb{Z}_2}^l$,
|
|
die von der Nachrichtenmenge $mathscr M$ auf eine Bitfolge mit fester Länge $l$ abbildet,
|
|
wird als Hashfunktion bezeichnet, falls gilt:
|
|
\begin{enumerate}
|
|
\item $H$ ist eine \say{Einwegsfunktion} (es gibt keinen effizienten Algorithmus zum Auffinden eines Urbilds)
|
|
\item $H$ ist \say{kollisionsfrei} (es gibt keinen effizienten Algorithmus zum Finden weiterer Nachrichten mit dem gleichen Hashwert)
|
|
\end{enumerate}
|
|
Die beiden Eigenschaften stehen in keiner Verbindung zueinander (Einwegsfunktion $\not\Leftrightarrow$ kollisionsfrei).
|
|
\vspace{2mm}
|
|
Hashfunktionen haben üblicherweise die folgenden Eigenschaften:
|
|
\begin{itemize}
|
|
\item Die Berechnung der Hashwerte ist effizient möglich und die Berechnungzeit ist im Wesentlichen proportional zur Nachrichtenlänge ($O(n)$)
|
|
\item $\mathscr M$ ist eine Teilmenge von $\mathscr Z ^{\ge 0}$ ($\mathscr Z = {\mathbb{Z}_2}^8$),
|
|
wobei die maximale Länge der in $\mathscr M$ vorkommenden Bytefolgen durch eine sehr große Zahl $N\in\mathbb{N}$ beschränkt ist ($\mathscr M=({\mathbb{Z}_2}^8)^{\le N}$).
|
|
In der Regel ist $N$ so groß, dass alle Nachrichten eine kleinere Länge haben.
|
|
\item Die Bitlänge $l$ des Hashwertes ist ein Vielfaches von 8.
|
|
\end{itemize}
|
|
Hashfunktionen sind wie die meisten Verschlüsselungsverfahren (Ausnahme OTP (siehe \ref{otp})) nicht \textbf{beweisbar} sicher.
|
|
Beispielsweise wurden für MD5 und SHA1 Algorithmen gefunden, die effizienter als durch Brute-Force eine Kollision finden.
|
|
|
|
\section{schwache Kollisionsfreiheit}\label{schwache Kollisionsfreiheit}
|
|
Eine Hashfunktion $H:\mathscr M \rightarrow {\mathbb{Z}_2}^l$ ist schwach-kollisionsfrei, falls es keinen effizienten Algorithmus gibt, der zu einem beliebigen $m\in \mathscr M$ ein $\tilde{m}\in \mathscr m$ findet, für das gilt:
|
|
$$\tilde{m}\ne m \text{ und }H(\tilde{m})=H(m)$$
|
|
Sie unterscheidet sich von der starken Kollisionsfreiheit darin, dass $m$ vorgegeben wird.
|
|
|
|
\section{\texttt{MessageDigest}-Instanzen: Hashfunktionen in Java}
|
|
siehe Skript 2 Kapitel 4.2 (Seite 56(62)).
|
|
|
|
\section{Anwendungsbeispiele}
|
|
\subsection{Anwendungsbeispiel: Passwortdatei}
|
|
Damit ein IT-System erkennt, ob ein vom Nutzer genanntes Passwort korrekt ist muss es Informationen über dieses Passwort abspeichern.
|
|
Am Einfachsten wäre es alle Passwörter in Plain-Text in einer Datenbank abzuspeichern.
|
|
Sollte diese Datenbank allerdings gehackt werden könnte der Hacker auf alle Nutzerkonten zugreifen.
|
|
Um dies zu verhindern müssen die Passwörter auf eine verifizierbare Art und Weise verschlüsselt (gehashed) werden.
|
|
Dies schützt allerdings nicht vor Wörterbuchangriffen, da es einem Angreifer möglich ist eine sortierte Liste der Hashwerte der häufig verwendeten Passwörter zu erstellen und abzugleichen.
|
|
|
|
\subsubsection{Anwendungsbeispiel: Passwortdatei mit Salt und Iteration Count}
|
|
Zur Abwehr von Wörterbuchangriffen ist es üblich das Passwort $p_i$ mit einem für jeden Nutzer unterschiedlichen Salt-Wert $s_i$ zu verrechnen.
|
|
Dieser Saltwert wird ebenfalls in der Datenbank abgespeichert und führt dazu, dass jeweils $H(p_i||s_i)$ statt $H(p_i)$ bestimmt wird.
|
|
Eine Attacke ist somit nur noch Nutzerspezifisch durchführbar.
|
|
Um dies weiter zu erschweren wird die Hashfunktion häufig mehrmals hintereinander angewandt:
|
|
$$H^c(p_i||s_i)=\underbrace{H(H(...H(}_{c}p_i||s_i)...))$$
|
|
Die Zahl $c$ wird als Iteration Count bezeichnet.
|
|
Hierdurch verzögert sich sowohl die reguläre Überprüfung von Passwörtern als auch die Laufzeit eines Angriffs um den Faktor $c$.
|
|
Für die Überprüfung ist dies meist kaum relevant (Verfahren wird einmal durchgeführt), während es für den Angriff einen großen Mehraufwand bedeutet (Verfahren wird \textbf{sehr} häufig durchgeführt).
|
|
|
|
\subsection{Anwendungsbeispiel: Integritätsschutz von Dateien}
|
|
Um ein Rechnersystem vor der Ausführung von Schadsoftware zu schützen ist es Praxis, die Hashwerte der zur Ausführung zugelassenen Programme in einer Whitelist zu speichern.
|
|
Ein Angreifer kann Schadsoftware nur dann ausführen, wenn sie den gleichen Hashwert wie ein Programm auf der Whitelist hat.
|
|
|
|
\subsection{Anwendungsbeispiel: Integritätsschutz bei einem Dateidownload}
|
|
Auf Webseiten wird häufig ein Hashwert für eine zu downloadenende Datei angegeben.
|
|
Dieser lässt sich dann nach dem Download mit der selbst aus der gedownloadeten Datei errechneten Hashwert überprüfen.
|
|
Dies bietet allerdings nur minimalen Schutz, da ein Angreifer, der die Webseite übernommen hat ebensogut den angegebenen Hashwert ändern kann.
|
|
Dies lässt sich erreichen, falls die Hashwerte der Datei auf mehreren Webseiten angegeben werden.
|
|
|
|
\section{Brute-Force-Angriffe auf Hashfunktionen}
|
|
Ein Brute-Force-Angriff sucht nach einem Konflikt oder einem Urbild, indem alle möglichen Nachrichten durchprobiert werden.
|
|
|
|
\subsection{Brute-Force-Urbildsuche}
|
|
Ein Angriff auf die Urbildresistenz stellt einen Angriff auf die schwache Kollisionsfreiheit (siehe \ref{schwache Kollisionsfreiheit}) dar.
|
|
D.h. es wird nach einem zweiten Urbild für ein bekanntes ($m,H(m)$)-Paar gesucht.
|
|
Hierfür werden die Hashwerte für alle $\tilde{m}\in \mathscr M\setminus\{m\}$ berechnet und mit $H(m)$ verglichen.
|
|
Um zu bestimmen, wie viele Versuche $r$ notwendig sind um mit einer Wahrscheinlichkeit $p$ ein $\tilde{m}$ kann die folgende Formel verwendet werden:
|
|
$$\begin{aligned}
|
|
r\ge&\frac{\ln(1-p_0)}{\ln(1-\frac{1}{n})}\\
|
|
r\ge&|\ln(1-p_0)|\cdot n\\
|
|
\end{aligned}$$
|
|
mit $p\ge p_0$, $n=2^l\ge 2$.
|
|
Diese Formel ergibt für die folgenden Beispiele:
|
|
$$\begin{aligned}
|
|
r&\approx ln(2)\cdot 2^l &\approx 0,7\cdot 2^l \hspace{5mm} &\text{für } p=0,5\\
|
|
r&\approx ln(10)\cdot 2^l &\approx 2,3\cdot 2^l \hspace{5mm} &\text{für } p=0,9\\
|
|
r&\approx ln(100)\cdot 2^l &\approx 4,6\cdot 2^l \hspace{5mm} &\text{für } p=0,99\\
|
|
\end{aligned}$$
|
|
|
|
\subsection{Brute-Force-Kollisionssuche}
|
|
Ein Angriff auf die starke Kollisionsfreiheit (siehe \ref{schwache Kollisionsfreiheit}), bei der zwei verschiedene Elemente $m_1,m_2\in \mathscr M$ gesucht werden, für die gilt:
|
|
$$H(m_1)=H(m_2)$$
|
|
Hierbei werden alle $m\in \mathscr M$ ausprobiert und die zugehörigen Hashwerte $H(m)$ solange in eine Tabelle geschrieben, bis ein Hashwert doppelt vorkommt.
|
|
Hierdurch ist die Anforderung an den verfügbaren Speicher nicht zu vernachlässigen.
|
|
Auch hierfür lässt sich ebenfalls eine Formel errechnen, die vorgibt, wie viele Versuche $r$ zu erwarten sind, bis sich ein Hashwert $H$ mit einer Wahrscheinlichkeit $p$ wiederholt:
|
|
$$r\ge\sqrt{-2\cdot \ln(1-p_0)\cdot n+\frac{1}{4}}+\frac{1}{2}\hspace{10mm}\text{für } c(n,r)\ge p_0, r\le \sqrt{2n}$$
|
|
Dies ergibt beispielhaft für die Kollisionswahrscheinlichkeit $p=c(n,r)=\frac{1}{2}$ die zwei mögliche Ungleichungen:
|
|
$$\begin{aligned}
|
|
r&\ge \sqrt{\ln(4)}\cdot\sqrt{n}+1\\
|
|
r&\ge \sqrt{\ln(4)\cdot n+\frac{1}{4}}+\frac{1}{2}
|
|
\end{aligned}$$
|
|
|
|
\section{Konstruktionsverfahren von Hashfunktionen}
|
|
Im allgemeinen Bestehen Hashfunktionen aus 2 Teilen:
|
|
\begin{enumerate}
|
|
\item eine iterative Anwendung einer \textbf{Kompressionsfunktion} $f:{\mathbb{Z}_2}^{r+s}\rightarrow{\mathbb{Z}_2}^s$ auf $r$ Bits von $m$ und ein internes Zustandsregister $s$
|
|
\item eine einmalige Ausführung einer \textbf{Ausgabefunktion} $g:{\mathbb{Z}_2}^s\rightarrow{\mathbb{Z}_2}^l$
|
|
\end{enumerate}
|
|
Bei vielen Verfahren ist $l=s$ und es ist keine Ausgabefunktion nötig.\\
|
|
Mithilfe von $f$, $g$ und einem Initialisierungswert $t_0\in{\mathbb{Z}_2}^s$ für das Zustandsregister wird $H(m)$ wie folgt berechnet:
|
|
\begin{enumerate}
|
|
\item $m$ wird durch ein Padding-Verfahren so erweitert, dass für $l(m||\text{pad})=l(m)+l(\text{pad})$ gilt: $r|l(m||\text{pad})$
|
|
\item $m$ wird in Blöcke $m_1,...,m_n$ zerlegt, die alle $r$ Bit lang sind.
|
|
\item der Wert des Zustandsregisters $t$ wird durch iteratives Anwenden der Kompressionsfunktion $f$ auf den jeweiligen Block $m_i$ berechnet:
|
|
$$t_i:=f(m_i||t_{i-1})\hspace{10mm}\text{für }i=1,...,n$$
|
|
\item der Hashwert wird ausgegeben: $H(m):=g(t_n)$
|
|
\end{enumerate}
|
|
Die unterschiedlichen Hashfunktionen unterscheiden sich in der Bitlänge der Hashwerte, Blöcke und Zustandsregister:
|
|
\begin{center}
|
|
\begin{tabular}{c|c|c|c|c}
|
|
$H$ & $l=l(H(m))$ & $r=l(m_i)$ & $s=l(t_i)$ & $\min\{l(\text{pad})\}$\\
|
|
\hline
|
|
\hline
|
|
MD5 & 128 & 512 & 128 & 65\\
|
|
\hline
|
|
SHA-1 & 160 & 512 & 160 & 65\\
|
|
\hline
|
|
SHA-224 & 224 & 512 & 256 & 65\\
|
|
SHA-256 & 256 & 512 & 256 & 65\\
|
|
SHA-512/224 & 224 & 1024 & 512 & 129\\
|
|
SHA-512/256 & 256 & 1024 & 512 & 129\\
|
|
SHA-384 & 384 & 1024 & 512 & 129\\
|
|
SHA-512 & 512 & 1024 & 512 & 129\\
|
|
\hline
|
|
SHA3-224 & 224 & 1152 & 1600 & 4\\
|
|
SHA3-256 & 256 & 1088 & 1600 & 4\\
|
|
SHA3-384 & 384 & 832 & 1600 & 4\\
|
|
SHA3-512 & 512 & 576 & 1600 & 4\\
|
|
\end{tabular}
|
|
\end{center} |