Beweisbare Sicherheit

Beweisbare Sicherheit ist ein Konzept in der modernen Kryptologie. In der Geschichte der Kryptographie gibt es viele Beispiele von Systemen, die von ihren Erfindern für sicher gehalten wurden, aber dennoch gebrochen werden konnten. Es ist daher wünschenswert, sich durch einen Beweis auf formalem Weg von der Sicherheit eines Systems zu überzeugen. Dazu muss sowohl das kryptographische System als auch die zu erreichende Sicherheit formalisiert werden.

Perfekte Sicherheit

Claude Shannon konnte 1949 die Sicherheit der One-Time-Pad-Verschlüsselung (OTP) beweisen. Er zeigte, dass ein Angreifer, der einen OTP-verschlüsselten Geheimtext erhält, nicht mehr Informationen über den Klartext hat als einer, der nur die Länge des Geheimtextes kennt. Der Beweis beruhte auf einem informationstheoretischen Argument und garantiert daher die Vertraulichkeit gegen jeden beliebigen Angreifer.

Asymptotische Sicherheit

Ein informationstheoretischer Beweis garantiert Sicherheit auch gegen Angreifer die in ihrer Rechenleistung nicht beschränkt sind. Ein solcher Angreifer könnte jedoch bei einem Verfahren wie AES einfach alle möglichen Schlüssel durchprobieren. Mit real existierenden Computern würde das aber zu lange dauern. Um den Sicherheitsbegriff realistischer zu gestalten, wird daher der Angreifer in seiner Rechenleistung beschränkt, und zwar abhängig von der verwendeten Schlüssellänge. Dann wird gezeigt, dass das System gegen einen solchen Angreifer sicher ist. Gezeigt wird also nur, dass der Aufwand für einen Angreifer sehr viel schneller wächst, als der Aufwand für die Benutzer. Durch passendes Wählen der Schlüssellänge können Angriffe so praktisch ausgeschlossen werden. Die Schlüssellänge muss aber der verfügbaren Rechenkraft angepasst werden, was einer der Gründe dafür ist, dass die früher für RSA verwendete Schlüssellänge von 768 Bit heute als unsicher gilt. Weil hier nur das asymptotische Verhalten untersucht wird, heißt die Sicherheit ebenfalls asymptotisch oder komplexitätstheoretisch.

Für die meisten kryptographischen Verfahren kann die Sicherheit des Systems nicht ohne weitere Annahmen bewiesen werden. Eine der frühesten verwendeten Annahmen ist die, dass das Faktorisierungsproblem schwer ist. Der Sicherheitsbeweis ist dann eine Reduktion zwischen dem Brechen des Systems und dem Lösen des Problems. Beispielsweise lässt sich beweisen, dass jeder Angreifer, der aus dem öffentlichen Schlüssel des RSA-Kryptosystems den geheimen berechnen kann, auch das Faktorisierungsproblem lösen kann (genauer gesagt, lässt sich aus einem erfolgreichen Angreifer ein effizienter Löser konstruieren). Da es einen solchen Löser laut Annahme aber nicht geben kann, kann es auch keinen erfolgreichen Angreifer geben. Sicherheit bedeutet hier also nicht mehr, dass es für den Angreifer völlig unmöglich ist, das System zu brechen, sondern dass dies praktisch unmöglich ist. Anders ausgedrückt, ist seine Erfolgswahrscheinlichkeit vernachlässigbar klein.

Diskussion

Das Paradoxon der beweisbaren Sicherheit ist, dass ein als sicher bewiesenes System nicht notwendigerweise wirklich sicher ist. Das liegt daran, dass für einen Beweis mehrere Annahmen und Formalisierungen nötig sind. Das System, der Angreifer und das Sicherheitsziel müssen formal beschrieben werden (wie beispielsweise IND-CPA Sicherheit für Verschlüsselungen) und der Beweis ist nur eine Reduktion eines Problems, dessen Schwere angenommen wurde. Ein Angreifer, der stärker ist als der im Beweis angenommene, kann das System also möglicherweise brechen. Genauso kann es vorkommen, dass das Sicherheitsziel nicht ausreichend formuliert wurde, also dem Angreifer schon ein geringerer Erfolg ausreicht. Wenn das Sicherheitsziel beispielsweise ist „Kein Angreifer soll aus einem Geheimtext den Klartext ableiten können“, so trifft der Beweis keine Aussage über einen Angreifer, der nur die ersten drei Buchstaben des Klartextes lernen will. Ein weiteres Problem ist, dass das reale Kryptosystem nicht genau das formale abbildet, weil entweder bei der Implementierung des formalen oder bei der Formalisierung eines bereits existierenden Systems Fehler gemacht wurden. Ein eher unwahrscheinlicher Weg, das System dennoch zu brechen, ist das Lösen des mathematischen Problems, das der Sicherheit zugrunde liegt. Zu guter Letzt kann natürlich auch einfach der Beweis falsch sein. Trotz dieser zahlreichen Probleme sind Sicherheitsbeweise in der modernen Kryptologie ein wertvolles Hilfsmittel.