it-swarm-eu.dev

Was ist ein kryptografisches Orakel?

Ich bin auf den Begriff "kryptografisches Orakel" gestoßen, und trotz ein wenig googeln konnte ich keine klare, präzise Definition finden. Was ist ein kryptografisches Oracle und was macht es? Kann jemand ein Beispiel geben?

35
josh-cain

Ein Oracle ist eine Person, die die persönliche Handynummer eines Gottes kennt. Dies ermöglicht es ihm (oder ihr), einige Informationen zu erhalten, die normalerweise als unerreichbar für bloße Sterbliche angesehen werden, wie beispielsweise Einblicke in die Zukunft. In der Kryptographie ist das dasselbe, außer dass keine Gottheit beteiligt ist: Ein Oracle ist ein beliebiges System, das zusätzliche Informationen zu einem System liefern kann, die sonst nicht verfügbar wären.

Betrachten Sie beispielsweise die asymmetrische Verschlüsselung mit RSA . Der Standard, auf den ich verweise, gibt an, wie ein Datenelement mit einem öffentlichen Schlüssel verschlüsselt werden soll. Insbesondere beginnt die Verschlüsselung mit einer Auffüllung Operation, bei der das Datenelement zuerst durch Hinzufügen eines Headers erweitert wird, sodass die aufgefüllte Datenlänge mit der Länge des öffentlichen RSA-Schlüssels übereinstimmt. Der Header sollte mit den zwei Bytes 0x00 0x02 Beginnen, gefolgt von mindestens acht zufälligen Bytes ungleich Null und einem weiteren 0x00. Sobald die Daten aufgefüllt wurden, ist es Zeit, die mathematische Operation anzuwenden, die den Kern der RSA-Operation bildet (modulare Exponentiation). Details der Polsterung sind wichtig für die Sicherheit.

Das Verschlüsselungsergebnis ist ein Ganzzahlmodul, das RSA-Modul, eine große Ganzzahl, die Teil des öffentlichen Schlüssels ist. Für einen 1024-Bit-RSA-Schlüssel ist der Modul n ein ganzzahliger Wert größer als 21023, aber kleiner als 21024. Ein ordnungsgemäß verschlüsselter Datenblock mit RSA ergibt einen ganzzahligen Wert zwischen 1 und n-1. Das Auffüllen impliziert jedoch eine Struktur, wie oben gezeigt. Die Entschlüsselungspartei MUSS bei der Entschlüsselung einen ordnungsgemäß gebildeten PKCS # 1-Header finden, der mit den Bytes 0x00 0x02 Beginnt, gefolgt von mindestens acht Bytes ungleich Null, und es muss einen 0x00 Geben markiert das Ende der Kopfzeile. Daher sind nicht alle Ganzzahlen zwischen 1 und n-1 Gültige RSA-verschlüsselte Nachrichten (weniger als 1 alle 65000 solcher Ganzzahlen würden bei der Entschlüsselung eine ordnungsgemäße Auffüllung ergeben ).

Wissen ob ein gegebenes ganzzahliges Modulo n bei Entschlüsselung eine gültige Auffüllstruktur ergeben würde, soll für jeden, der den privaten Schlüssel nicht kennt, nicht durchführbar sein. Der private Schlüsselbesitzer (die Gottheit) erhält diese Informationen und vieles mehr: Wenn die Entschlüsselung funktioniert, erhält der private Schlüsselbesitzer tatsächlich die Nachricht, bei der es sich um den Entschlüsselungspunkt handelt. Angenommen, es gibt irgendwo is eine Entität, die Ihnen sagen kann, ob ein gegebenes ganzzahliges Modulo n ein gültig verschlüsseltes Datenelement mit RSA ist; Diese Entität würde Ihnen nicht das vollständige Entschlüsselungsergebnis liefern, sondern nur sagen, ob die Entschlüsselung funktionieren würde oder nicht. Das ist eine Ein-Bit-Information, ein reduzierter Blick darauf, was die Gottheit erhalten würde. Die Entität ist Ihr Oracle: Sie gibt Teile der Informationen zurück, die normalerweise nur dem privaten Schlüsselbesitzer zur Verfügung stehen.

Es stellt sich heraus , dass es bei Zugriff auf ein solches Oracle möglich ist, den privaten Schlüssel neu zu erstellen, indem speziell gestaltete Ganzzahlen gesendet werden. Modulo n (es dauert eine Million oder so von solchen Werten und ziemlich viel Mathematik, aber es kann getan werden). Es stellt sich auch heraus, dass die meisten SSL/TLS Implementierungen dieser Zeit (das war 1999) unfreiwillig als Orakel fungierten: Wenn Sie als Client eine ungültig RSA-verschlüsselte ClientKeyExchange-Nachricht an den Server gesendet haben antwortete mit einer bestimmten Fehlermeldung ("duh, Ihre ClientKeyExchange-Nachricht stinkt"), während der Server bei funktionierender Entschlüsselung mit dem Protokoll fortfuhr und den entschlüsselten Wert verwendete (normalerweise dem Client unbekannt, wenn der Client einen zufälligen Wert gesendet hat Das Protokoll schlug später fehl, aber der Client konnte den Unterschied zwischen einer gültigen und einer ungültigen Auffüllung erkennen. Daher könnte ein Angreifer mit einer solchen Implementierung (nach etwa einer Million fehlgeschlagener Verbindungen) den privaten Serverschlüssel neu erstellen, was normalerweise als schlecht angesehen wird.

Das sind Orakel: eine mathematische Beschreibung eines Datenlecks, die in Sicherheitsnachweisen verwendet werden soll. Im Fall von RSA zeigt dies, dass das Wissen, ob ein Wert eine ordnungsgemäße Auffüllung hat oder nicht, dem Erlernen des privaten Schlüssels entspricht (wenn Sie den privaten Schlüssel kennen, können Sie die Entschlüsselung versuchen und die Auffüllung selbst sehen; der Bleichenbacher-Angriff zeigt dies) dass es auch umgekehrt funktioniert).

67
Thomas Pornin

Kryptografische Orakel sind eine Black-Box-Eingabe-/Ausgabemethode.

Es reagiert auf jede Eingabe mit einer Pseudozufallsantwort, gibt jedoch immer die gleiche Ausgabe für eine bestimmte Eingabe.

Sie werden im Allgemeinen für Hash-Funktionen verwendet, bei denen Zufälligkeit für eine höhere Sicherheit wichtig ist.

Offensichtlich wird es immer noch Sicherheitsprobleme geben, da es sich nur um eine mathematische Funktion handelt, die scheinbar pseudozufällige Zahlen zurückgibt, aber sie sind offensichtlich stärker als einige ihrer weniger zufälligen Gegenstücke.

Hier ist ein solides Papier über sie und ihr Design - http://cseweb.ucsd.edu/users/mihir/papers/ro.pdf

1
doyler