Autor: Old Gocs, Berlin 1/2016
Informatiker erreichen das "Kronjuwel" der Kryptographie
Erica Klarreich
Wissenschaft
15.11.2020 08:00 Uhr
Informatiker erreichen das "Kronjuwel" der
Kryptographie
Jahrelang schien ein Master-Tool namens
Undistinguishability-Verschleierung zu gut, um wahr zu sein. Drei
Forscher haben herausgefunden, dass es funktionieren kann.
Video: Kiel Mutschelknaus/Quanta Magazin
Im Jahr 2018 wird Aayush Jain, ein Doktorand
an der University of California, Los Angeles, reiste nach Japan, um
einen Vortrag über ein leistungsfähiges kryptografisches Werkzeug zu
halten, das er und seine Kollegen entwickelten. Als er den Ansatz des
Teams zur Ununterscheidbarkeitsverschleierung (kurz iO) erläuterte, hob
ein Zuschauer verwirrt die Hand.
Originalgeschichte mit Genehmigung des Quanta
Magazine, einer redaktionell unabhängigen Publikation der Simons
Foundation, deren Aufgabe es ist, das öffentliche Verständnis der
Wissenschaft zu verbessern, indem Forschungsentwicklungen und Trends in
Mathematik und Denphysik und Biowissenschaften untersucht werden.
"Aber ich dachte, iO gibt es nicht?", sagte
er.
Damals war eine solche Skepsis weit
verbreitet. Ununterscheidbarkeit sifschifkbarkeit, wenn es gebaut werden
könnte, wäre in der Lage, nicht nur Sammlungen von Daten zu verbergen,
sondern das innere Funktionieren eines Computerprogramms selbst, eine
Art kryptografisches Master-Tool zu schaffen, aus dem fast jedes andere
kryptografische Protokoll erstellt werden könnte. Es sei "ein
kryptografischer Primitiv, sie alle zu regieren", sagte Boaz Barak von
der Harvard University. Aber für viele Informatiker, diese Macht machte
iO zu gut scheinen, um wahr zu sein.
Informatiker stellen ab 2013
Kandidatenversionen von iO vor. Aber die intensive Aufregung, die diese
Konstruktionen erzeugten, verpuffte allmählich, als andere Forscher
herausgefunden, wie sie ihre Sicherheit brechen können. Als sich die
Angriffe häuften, "konnte man eine Menge negativer Stimmungen sehen",
sagte Yuval Ishai von der Technion in Haifa, Israel. Die Forscher
fragten sich, er sagte: "Wer wird gewinnen: die Macher oder die
Brecher?"
"Es gab die Leute, die die Eiferer waren, und
sie glaubten an [iO] und arbeiteten weiter daran", sagte Shafi
Goldwasser, Direktor des Simons Institute for the Theory of Computing an
der University of California, Berkeley. Aber im Vorbeigehen, sagte sie,
"gab es immer weniger dieser Leute."
Nun hat Jain – zusammen mit Huijia Lin von der
University of Washington und Amit Sahai, Jains Berater an der UCLA –
eine Flagge für die Macher gepflanzt. In einem am 18. August online
veröffentlichten Artikel zeigen die drei Forscher erstmals, wie man
ununterscheidbare Verschleierung unter Verwendung nur
"Standard"-Sicherheitsannahmen erstellt.
aayush jain
Aayush Jain, Student an der University of
California, Los Angeles, in Oakland in diesem Monat. Foto: Eleena
Mohanty
Alle kryptografischen Protokolle stützen sich
auf Annahmen – einige, wie der berühmte RSA-Algorithmus, hängen von der
weit verbreiteten Überzeugung ab, dass Standardcomputer niemals in der
Lage sein werden, das Produkt zweier großer Primzahlen schnell zu
berücksichtigen. Ein kryptografisches Protokoll ist nur so sicher wie
seine Annahmen, und frühere Versuche mit iO wurden auf ungetesteten und
letztlich wackeligen Fundamenten aufgebaut. Das neue Protokoll hingegen
hängt von Sicherheitsannahmen ab, die in der Vergangenheit weit
verbreitet und untersucht wurden.
"Abgesehen von einer wirklich überraschenden
Entwicklung werden diese Annahmen Bestehen haben", sagte Ishai.
Neuigkeiten der Zukunft, jetzt. News of the
future, now. Holen Sie sich WIRED für so niedrig wie 5 $. Jetzt
abonnieren
Obwohl das Protokoll noch lange nicht bereit
ist, in realen Anwendungen bereitgestellt zu werden, bietet es
theoretisch eine sofortige Möglichkeit, eine Reihe von kryptografischen
Tools zu erstellen, die zuvor außer Reichweite waren. Zum Beispiel
ermöglicht es die Erstellung einer "leugbaren" Verschlüsselung, bei der
Sie einen Angreifer plausibel davon überzeugen können, dass Sie eine
völlig andere Nachricht gesendet haben als die, die Sie wirklich
gesendet haben, und eine "funktionale" Verschlüsselung, bei der Sie
ausgewählten Benutzern verschiedene Zugriffsebenen geben können, um
Berechnungen mit Ihren Daten durchzuführen.
Das neue Ergebnis sollte die iO-Skeptiker
endgültig zum Schweigen bringen, sagte Ishai. "Jetzt wird es keine
Zweifel mehr an der Existenz einer ununterscheidbaren Verschleierung
geben", sagte er. "Es scheint ein Happy End zu sein."
Das Kronjuwel
Jahrzehntelang fragten sich Informatiker, ob
es eine sichere, allumfassende Möglichkeit gibt, Computerprogramme zu
verschleiern, die es den Menschen ermöglichen, sie zu benutzen, ohne
ihre inneren Geheimnisse herauszufinden. Programmverschleierung würde
eine Vielzahl nützlicher Anwendungen ermöglichen: Sie könnten z. B. ein
verschleiertes Programm verwenden, um bestimmte Aufgaben innerhalb Ihrer
Bank oder E-Mail-Konten an andere Personen zu delegieren, ohne sich
Sorgen zu machen, dass jemand das Programm in einer Weise verwenden
könnte, die nicht für Ihre Kontokennwörter vorgesehen war oder sie
ausliest (es sei denn, das Programm wurde für die Ausgabe entwickelt).
Doch bisher sind alle Versuche, praktische
Obfuscators zu bauen, gescheitert. "Die, die im wirklichen Leben
herausgekommen sind, sind lächerlich gebrochen, ... in der Regel
innerhalb von Stunden nach der Freisetzung in die Wildnis", sagte Sahai.
Im besten Fall bieten sie Angreifern einen Geschwindigkeitsschub, sagte
er.
Auch 2001 kam es theoretisch zu schlechten
Nachrichten: Die stärkste Form der Verschleierung ist unmöglich. Als
Blackbox-Verschleierung bezeichnet, verlangt es, dass Angreifer in der
Lage sein sollten, absolut nichts über das Programm zu lernen, außer was
sie beobachten können, indem sie das Programm verwenden und sehen, was
es ausgibt. Einige Programme, Barak, Sahai und fünf andere Forscher
zeigten,offenbaren ihre Geheimnisse so entschlossen, dass sie unmöglich
sind, vollständig zu verschleiern.
https://www.wired.com/story/computer-scientists-achieve-the-crown-jewel-of-cryptography/#intcid=_wired-category-right-rail_a95d87bb-4762-45fa-9998-880b2a622d4f_popular4-1