Sicherheitsmodelle für das Ajtai-Dwork-Kryptosystem

Ziel der Diplomarbeit war es, zu untersuchen, welche Sicherheitsmodelle durch das Ajtai-Dwork-Kryptosystem erfuellt werden. Dazu wurden verschiedene Absichten und Faehigkeiten eines potentiellen Angreifersvorgestellt. Als zu untersuchende Sicherheitsmodelle kristallisierten sich die von Bellare, Desai, Pointcheval und Rogaway in [BDPR98] bzw. [BDPR01] vorgeschlagenen Sicherheitsmodelle heraus. Dies lag zum einen daran, dass andere Angriffe - wie der Ciphertext-Verification-Angriff von Halevi und Krawczyk [HK99] oder der Reaktionsangriff von Hall, Goldberg und Schneier [HGS99] - sich auf Chosen-Plaintext-Angriffe zurueckfuehren liessen. Zum anderen konnten andere Sicherheitsziele wie bspw. Plaintext-Awareness nicht in passender Weise auf das Ajtai-Dwork-Kryptosystem angewandt werden. Also wurden die verschiedenen Varianten des Ajtai-Dwork-Kryptosystems daraufhin untersucht, ob sie Indistinguishability oder Non-Malleability unter Chosen-Plaintext-Angriffen und (non-)adaptive Chosen-Ciphertext- Angriffen bieten koennen. Dabei stellte sich heraus, dass keine der Varianten sicher im Sinne von Non-Malleability unter Chosen-Plaintext-Angriffen (NM-CPA) oder sicher im Sinne von Indistinguishability unter non-adaptive Chosen-Ciphertext-Angriffen (IND-CCA1) ist. Im Falle der beschraenkten Variante reichte es dazu aus, die Idee des Reduktionsbeweises von Ajtai und Dwork zu betrachten. Der Reduktionsbeweis zeigt, dass ein Angreifer, der in der Lage ist, Verschluesselungen von Null und Eins zu unterscheiden, auch in der Lage ist, den privaten Schluessel zu errechnen. Da sich Non-Malleability unter Chosen-Plaintext-Angriffen auf Indistinguishability unter Parallel-Angriffen zurueckfuehren laesst, steht dem Angreifer in beiden Faellen ein Entschluesselungsorakel zur Verfuegung. Damit kann er Verschluesselungen von Null von Verschluesselungen von Eins unterscheiden und somit den privaten Schluessel erlangen. Bei der unbeschraenkten Variante war dies nur fuer Indistinguishability unter non-adaptive Chosen-Ciphertext-Angriffen moeglich. Wir konnten jedoch einen Parallel-Angriff auf die Indistinguishability der unbeschraenkten Variante zeigen. Dieser macht sich zu Nutze, dass Ciphertexte Punkte im n- dimensionalen Raum sind und Punkte, die dicht beieinander liegen, mit hoher Wahrscheinlichkeit als Verschluesselungen desselben Klartextes betrachtet werden koennen. Der Angreifer kann also das Entschluesselungsorakel nach entsprechenden Punkten fragen und so Informationen ueber den zu entschuesselnden Ciphertext erhalten. Der Reduktionsbeweis der Hauptvariante des Ajtai-Dwork-Kryptosystems konnte jedoch nicht direkt fuer einen non-adaptive Chosen-Ciphertext-Angriff auf die Indistinguishability genutzt werden. Stattdessen konnten wir aber den von Hall, Goldberg und Schneier in [HGS99] gezeigten Reaktionsangriff auf die Variante nach Goldreich, Goldwasser und Halevi in einen erfolgreichen Angriff auf die Hauptvariante aendern. Die Idee des Angriffes ist, durch Anfragen an das Entschluesselungsorakel die Laenge des privaten Schluesselvektors zu approximieren. Ist die Laenge jeder Dimension bekannt, so kann durch weitere Anfragen an das Orakel das Vorzeichen der jeweiligen Dimension und so der private Schluessel herausgefunden werden. Chosen-Plaintext-Angriffe auf die Non-Malleability liessen sich aehnlich den Angriffen in der unbeschraenkten Variante durchfuehren. Fuer non-adaptive Chosen-Ciphertext-Angriffe auf die Indistinguishability der Variante nach Goldreich, Goldwasser und Halevi konnte der eben beschriebene Reaktionsangriff von Hall, Goldberg und Schneier direkt verwendet werden. Allerdings mussten noch zwei Fehler aus der Darstellung in [HGS99] beseitigt werden. Auch bei dieser Variante liessen sich Chosen- Plaintext-Angriffe auf die Non-Malleability aehnlich den Angriffen in der unbeschraenkten Variante durchfuehren. Da alle hier gezeigten Angriffe elementare Eigenschaften des Ajtai-Dwork- Kryptosystems nutzen, ist fuer keine der vier Varianten eine 'Reparatur' des Kryptosystems durch einfache Modifikationen moeglich. Wie in der Einleitung schon angedeutet, wiegt jedoch schwerer, dass auch Chosen-Plaintext-Angriffe auf das Ajtai-Dwork-Kryptosystem von Nguyen und Stern [NS98, NS99] gefunden wurden. Dazu wurden Gitterbasisreduktionsalgorithmen benutzt, um das Shortest-Vector-Problem zu approximieren und so den privaten Schluessel zu errechnen. Wie Nguyen und Stern aufzeigen, benoetigt man dadurch so immens grosse Schluessel, dass der praktische Einsatz des Ajtai-Dwork-Kryptosystems nicht in Frage kommt. Als Ausblick verweisen wir auf das von Regev entwickelte Kryptosystem [Reg03b], dessen Sicherheit auf der Worst-Case Schwierigkeit des n^(1.5) - unique Shortest-Vector-Problem beruht. Eine gruendliche Untersuchung dieses Systems konnte im Rahmen dieser Diplomarbeit nicht erfolgen. Der Angriff auf die Non-Malleability unter Chosen-Plaintext-Angriffen konnte jedoch vom Ajtai-Dwork-Kryptosystem auf Regevs System uebertragen werden.

@Thesis{pape04thesis,
  author   = {Sebastian Pape},
  title    = {Sicherheitsmodelle f\"ur das {Ajtai-Dwork-Kryptosystem}},
  month    = {01},
  year     = {2004},
  doi      = {X},
  keywords = {crypto},
  school   = {Lehrstuhl f\"ur Kryptographie und Computeralgebra, Fachbereich Informatik der Technischen Universit\"at Darmstadt},
}