Optimal Asymmetric Encryption Padding

Optimal Asymmetric Encryption Padding, auf Deutsch etwa Optimales asymmetrisches Verschlüsselungs-Padding, oft auch abgekürzt als OAEP, ist ein kryptographisches Paddingverfahren. Es ist eine spezielle Form eines Feistelnetzwerks, mit welchem im Zufallsorakel-Modell aus einer beliebigen Falltürpermutation ein gegen Gewählter-Klartext-Angriffe semantisch sicheres Verschlüsselungsverfahren gebaut werden kann. Wenn OAEP mit der Falltürpermutation RSA verwendet wird, ist das nun RSA-OAEP genannte Verfahren sogar sicher gegen Gewähltes-Chiffrat-Angriffe (IND-CCA). Das Verfahren wurde 1994 von Mihir Bellare und Phillip Rogaway veröffentlicht.<ref name="BR">{{#invoke:Vorlage:Literatur|f}} <templatestyles src="Webarchiv/styles.css" />{{#if:20181105145454

      | {{#ifeq: 20181105145454 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Optimal Asymmetric Encryption – How to encrypt with RSA. | {{#invoke:WLink|getEscapedTitle|Optimal Asymmetric Encryption – How to encrypt with RSA.}} | {{#invoke:Webarchiv|getdomain|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20181105145454}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Optimal Asymmetric Encryption – How to encrypt with RSA. | {{#invoke:WLink|getEscapedTitle|Optimal Asymmetric Encryption – How to encrypt with RSA.}} | {{#invoke:Webarchiv|getdomain|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2022-12-24 02:56:06 InternetArchiveBot | 2022-12-24 02:56:06 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20181105145454}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Optimal Asymmetric Encryption – How to encrypt with RSA. | {{#invoke:WLink|getEscapedTitle|Optimal Asymmetric Encryption – How to encrypt with RSA.}} | {{#invoke:Webarchiv|getdomain|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2022-12-24 02:56:06 InternetArchiveBot | 2022-12-24 02:56:06 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Optimal Asymmetric Encryption – How to encrypt with RSA. | {{#invoke:WLink|getEscapedTitle|Optimal Asymmetric Encryption – How to encrypt with RSA.}} | {{#invoke:Webarchiv|getdomain|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2022-12-24 02:56:06 InternetArchiveBot | 2022-12-24 02:56:06 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Optimal Asymmetric Encryption – How to encrypt with RSA. | {{#invoke:WLink|getEscapedTitle|Optimal Asymmetric Encryption – How to encrypt with RSA.}} | {{#invoke:Webarchiv|getdomain|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf}} }} (Memento{{#if: {{#if: 2022-12-24 02:56:06 InternetArchiveBot | 2022-12-24 02:56:06 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Optimal Asymmetric Encryption – How to encrypt with RSA. | {{#invoke:WLink|getEscapedTitle|Optimal Asymmetric Encryption – How to encrypt with RSA.}} | {{#invoke:Webarchiv|getdomain|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf}} }}  
                 }}}}}}}}{{#if:2022-12-24 02:56:06 InternetArchiveBot
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20181105145454|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Optimal Asymmetric Encryption – How to encrypt with RSA.
    | {{#if: {{#invoke:WLink|isBracketedLink|Optimal Asymmetric Encryption – How to encrypt with RSA.}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://cseweb.ucsd.edu/~mihir/papers/oae.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} cseweb.ucsd.edu</ref>

Verfahren (Grundvariante)

Datei:Oaep-diagram-20080305.png

Ablauf der OAEP-Schemas in der CCA-Variante (siehe Abschnitt Varianten). In der Grundversion des Verfahrens ist k₁=0, d. h., es werden keine Nullen angehängt.
Die Ausgabe X, Y dient als Eingabewert für die Falltürpermutation f.

Es sei <math>n</math> ein Sicherheitsparameter, und <math>k_0</math> so groß, dass ein Angreifer nur deutlich weniger als <math>2^{k_0}</math> Rechenschritte ausführen kann.

Weiter seien <math>F</math> eine Familie von Falltürpermutationen <math>f:\{0,1\}^n\mapsto\{0,1\}^n</math> auf Nachrichten mit <math>n</math> Bits, und <math>k=n-k_0</math> die Länge der Nachrichten, welche übertragen werden sollen.

Schließlich seien <math>G:\{0,1\}^{k_0}\mapsto\{0,1\}^k</math> und <math>H:\{0,1\}^k\mapsto\{0,1\}^{k_0}</math> kryptographische Hashfunktionen. Das Verschlüsselungsverfahren <math>F</math>-OAEP ist nun wie folgt definiert. Die Schlüsselerzeugung besteht in der Wahl von <math>f, f^{-1}</math>.

Verschlüsselung

Um eine <math>k</math>-Bit Nachricht <math>m</math> zu verschlüsseln, verfährt man nun wie folgt:

Man wählt <math>r\in\{0,1\}^{k_0}</math> als eine zufällige Folge von <math>k_0</math> Bits.
Dann berechnet man
- <math>X = m\oplus G(r)</math> und <math>Y=r\oplus H(m\oplus G(r))</math>.
Der Schlüsseltext <math>c</math> ist dann gegeben als:
- <math>c = f(X||Y)</math>,
  wobei <math>||</math> hier für Konkatenation steht.

Entschlüsselung

Um die Nachricht <math>m</math> zu rekonstruieren, führt man die folgenden Schritte aus:

Zuerst verwendet man die Falltür, um zu berechnen:
- <math>Z=(X||Y)=f^{-1}(c)</math>
Nun rekonstruiert man den Zufallswert <math>r</math> als
- <math>r=Y\oplus H(X)</math>.
Schließlich erhält man die Nachricht <math>m</math> wieder als
- <math>m=X\oplus G(r)</math>.

Varianten

Durch eine einfache Modifikation des obigen Protokolls kann man auch IND-CCA1 Sicherheit, also Sicherheit gegen Gewählte-Schlüsseltext-Angriffe erreichen. Dazu reduziert man die Länge der Nachricht <math>m</math> auf <math>k-k_1</math> Bits, und konkateniert sie mit <math>k_1</math> Nullen. Beim Entschlüsseln prüft man, ob der rekonstruierte Wert die korrekte Form hat, und bricht ansonsten ab.

Victor Shoup präsentierte eine Erweiterung des Verfahrens, mit welcher für jede beliebige Falltürpermutation auch IND-CCA2 Sicherheit erreicht werden kann.<ref name="Shoup">{{#invoke:Vorlage:Literatur|f}}</ref>

RSA-OAEP

Der Grund für die Entwicklung von OAEP war die Suche nach einer Möglichkeit, mit RSA sicher (im Sinn von IND-CCA2-Sicherheit) zu verschlüsseln. Wird bei OAEP als Falltürpermutation RSA verwendet, so wird das Verfahren als RSA-OAEP bezeichnet. Obwohl OAEP im allgemeinen Fall IND-CCA2-Sicherheit nicht erreicht, ist dies für RSA-OAEP im Zufallsorakel-Modell und unter der RSA-Annahme der Fall.<ref name="FOPS" />

Da das Ergebnis des OAEP-Encodings eine Zahl zwischen 0 und <math>2^n</math> ist, der <math>n</math>-bit RSA-Modulus <math>N</math> aber kleiner als <math>2^n</math> ist, kann es vorkommen, dass das Ergebnis des OAEP-Encodings einen größeren numerischen Wert hat als der RSA-Modulus. Dies darf aber nicht passieren, da in diesem Fall die Entschlüsselung nicht mehr eindeutig ist. Daher muss in einem solchen Fall das OAEP-Encoding mit neuem Zufall <math>r</math> wiederholt werden.

RSA-OAEP wurde in PKCS#1 und RFC 3447<ref>Vorlage:RFC-Internet</ref> standardisiert, wobei die verwendete Hashfunktion ein Parameter des Verfahrens ist, also nicht festgelegt wurde. Unter diesen Umständen, also ohne Zufallsorakel, ist RSA-OAEP unter der Phi-Hiding-Annahme IND-CPA sicher, falls die verwendete Hashfunktion t-wise independent ist.<ref name="KONS" /> Bei der Standardisierung wurde allerdings eine Änderung vorgenommen, durch die das Verfahren nicht mehr beweisbar sicher ist: Um das oben angesprochene Wiederholen des OAEP-Encodings zu vermeiden wurde festgelegt, dass das Ergebnis von OAEP um 8 Bit kürzer sein muss als der RSA-Modulus; die ersten 8 Bit werden mit 0 aufgefüllt. Der Empfänger muss beim Entschlüsseln überprüfen, ob die ersten 8 Bit den Wert 0 haben, und abbrechen, falls nicht. Falls ein Angreifer unterscheiden kann, ob eine Entschlüsselung aus diesem oder aus einem anderen Grund abgebrochen wurde, gibt es einen Angriff, der ohne den geheimen Schlüssel den kompletten Klartext zurückgewinnt.<ref name="Manger" /> Dafür benötigt er nur ca. 1000 Anfragen an ein Fehlerorakel, das lediglich ausgibt, ob und aus welchem Grund ein Entschlüsselungsversuch gescheitert ist. Solche Orakel können beispielsweise bei TLS/SSL-Verbindungen auftreten, dort wurde der Angriff auch in der Praxis durchgeführt.

Einzelnachweise

<references> <ref name="FOPS"> {{#invoke:Vorlage:Literatur|f}} </ref> <ref name="Manger"> {{#invoke:Vorlage:Literatur|f}} </ref> <ref name="KONS"> {{#invoke:Vorlage:Literatur|f}} </ref> </references>