Formaatbehoudende encryptie - Format-preserving encryption

In cryptografie , vorm-behoud codering ( FPE ), heeft betrekking op het coderen zodanig dat de uitgang (de cijfertekst ) in hetzelfde formaat als de ingang (de platte tekst ). De betekenis van "formaat" varieert. Gewoonlijk worden alleen eindige reeksen tekens gebruikt; numeriek, alfabetisch of alfanumeriek. Bijvoorbeeld:

  • Een 16-cijferig creditcardnummer versleutelen zodat de cijfertekst nog een 16-cijferig nummer is.
  • Een Engels woord versleutelen zodat de cijfertekst een ander Engels woord is.
  • Een n- bits getal versleutelen zodat de cijfertekst een ander n- bits getal is (dit is de definitie van een n- bits blokcijfer).

Voor dergelijke eindige domeinen, en voor de doeleinden van de onderstaande bespreking, is het cijfer equivalent aan een permutatie van N gehele getallen {0, ... , N −1 } waarbij N de grootte van het domein is.

Motivatie

Beperkte veldlengtes of formaten

Een motivatie voor het gebruik van FPE komt van de problemen die gepaard gaan met het integreren van encryptie in bestaande applicaties, met goed gedefinieerde datamodellen. Een typisch voorbeeld is een creditcardnummer , zoals 1234567812345670(16 bytes lang, alleen cijfers).

Het toevoegen van codering aan dergelijke toepassingen kan een uitdaging zijn als gegevensmodellen moeten worden gewijzigd, omdat dit meestal gepaard gaat met het wijzigen van veldlengtelimieten of gegevenstypen. Uitvoer van een typisch blokcijfer zou bijvoorbeeld het creditcardnummer veranderen in een hexadecimale (bijv 0x96a45cbcf9c2a9425cde9e274948cb67. 34 bytes, hexadecimale cijfers) of Base64- waarde (bijv lqRcvPnCqUJc3p4nSUjLZw==. 24 bytes, alfanumerieke en speciale tekens), waardoor bestaande applicaties die het krediet verwachten, worden verbroken kaartnummer een 16-cijferig nummer zijn.

Afgezien van eenvoudige formatteringsproblemen, kan dit creditcardnummer bij gebruik van AES-128-CBC worden versleuteld naar de hexadecimale waarde 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. Naast de problemen die worden veroorzaakt door het creëren van ongeldige tekens en het vergroten van de gegevens, veranderen gegevens die zijn versleuteld met behulp van de CBC-modus van een versleutelingsalgoritme ook hun waarde wanneer ze worden ontsleuteld en opnieuw versleuteld. Dit gebeurt omdat de willekeurige seed-waarde die wordt gebruikt om het versleutelingsalgoritme te initialiseren en is opgenomen als onderdeel van de versleutelde waarde, voor elke versleutelingsbewerking anders is. Hierdoor is het onmogelijk om gegevens die zijn versleuteld met de CBC-modus als unieke sleutel te gebruiken om een ​​rij in een database te identificeren.

FPE probeert het overgangsproces te vereenvoudigen door de opmaak en lengte van de originele gegevens te behouden, waardoor een drop-in vervanging van leesbare tekstwaarden door hun cijferteksten in oudere toepassingen mogelijk wordt.

Vergelijking met echt willekeurige permutaties

Hoewel een echt willekeurige permutatie de ideale FPE-codering is, is het voor grote domeinen onhaalbaar om een ​​echt willekeurige permutatie vooraf te genereren en te onthouden. Het probleem van FPE is dus om een ​​pseudo-willekeurige permutatie van een geheime sleutel te genereren, op zo'n manier dat de rekentijd voor een enkele waarde klein is (idealiter constant, maar vooral kleiner dan O(N) ).

Vergelijking met blokcijfers

Een n -bit blokversleuteling technisch is een FPE op de verzameling {0, ..., 2 n -1 }. Als een FPE nodig is op een van deze sets met standaardafmetingen (bijvoorbeeld n = 64 voor DES en n = 128 voor AES), kan een blokcijfer van de juiste grootte worden gebruikt.

In typisch gebruik wordt echter een blokcijfer gebruikt in een werkingsmodus die het mogelijk maakt om willekeurig lange berichten te versleutelen, en met een initialisatievector zoals hierboven besproken. In deze modus is een blokcijfer geen FPE.

Definitie van beveiliging

In cryptografische literatuur (zie de meeste referenties hieronder) is de maatstaf voor een "goede" FPE of een aanvaller de FPE kan onderscheiden van een echt willekeurige permutatie. Er worden verschillende soorten aanvallers gepostuleerd, afhankelijk van of ze toegang hebben tot orakels of bekende ciphertext/plaintext-paren.

Algoritmen

In de meeste van de hier genoemde benaderingen wordt een goed begrepen blokcijfer (zoals AES ) gebruikt als een primitief om de plaats van een ideale willekeurige functie in te nemen. Dit heeft als voordeel dat het opnemen van een geheime sleutel in het algoritme eenvoudig is. Waar AES in de volgende bespreking wordt genoemd, zou elk ander goed blokcijfer ook werken.

De FPE-constructies van Black en Rogaway

Het implementeren van FPE met beveiliging die waarschijnlijk verband houdt met die van het onderliggende blokcijfer, werd voor het eerst gedaan in een paper van cryptografen John Black en Phillip Rogaway , waarin drie manieren werden beschreven om dit te doen. Ze bewezen dat elk van deze technieken net zo veilig is als het blokcijfer dat wordt gebruikt om het te construeren. Dit betekent dat als het AES-algoritme wordt gebruikt om een ​​FPE-algoritme te maken, het resulterende FPE-algoritme net zo veilig is als AES, omdat een tegenstander die het FPE-algoritme kan verslaan, ook het AES-algoritme kan verslaan. Daarom, als AES veilig is, zijn de FPE-algoritmen die daaruit zijn opgebouwd ook veilig. In al het volgende duidt E de AES-coderingsbewerking aan die wordt gebruikt om een ​​FPE-algoritme te construeren en geeft F de FPE-coderingsbewerking aan.

FPE van een voorvoegselcijfer

Een eenvoudige manier om een ​​FPE-algoritme op {0, ..., N -1} te maken, is door aan elk geheel getal een pseudowillekeurig gewicht toe te kennen en vervolgens op gewicht te sorteren. De gewichten worden gedefinieerd door een bestaand blokcijfer toe te passen op elk geheel getal. Black en Rogaway noemen deze techniek een "voorvoegselcijfer" en toonden aan dat het waarschijnlijk net zo goed was als het gebruikte blokcijfer.

Dus, om een ​​FPE te creëren op het domein {0,1,2,3}, gegeven een sleutel K, pas AES( K ) toe op elk geheel getal, wat bijvoorbeeld geeft, 

weight(0) = 0x56c644080098fc5570f2b329323dbf62
weight(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7
weight(2) = 0x47d2e1bf72264fa01fb274465e56ba20
weight(3) = 0x077de40941c93774857961a8a772650d

Sorteren van [0,1,2,3] op gewicht geeft [3,1,2,0], dus het cijfer is 

F(0) = 3
F(1) = 1
F(2) = 2
F(3) = 0

Deze methode is alleen bruikbaar voor kleine waarden van N . Voor grotere waarden wordt de grootte van de opzoektabel en het vereiste aantal versleutelingen om de tabel te initialiseren te groot om praktisch te zijn.

FPE van fietsen

Als er een reeks M toegestane waarden is binnen het domein van een pseudo-willekeurige permutatie P (bijvoorbeeld P kan een blokcijfer zijn zoals AES), kan een FPE-algoritme worden gemaakt op basis van het blokcijfer door het blokcijfer herhaaldelijk toe te passen totdat het resultaat is een van de toegestane waarden (binnen M ). 

CycleWalkingFPE(x) {
    if P(x) is an element of M then
        return P(x)
    else
        return CycleWalkingFPE(P(x))
}

De recursie wordt gegarandeerd beëindigd. (Omdat P één-op-één is en het domein eindig is, vormt herhaalde toepassing van P een cyclus, dus beginnend met een punt in M zal de cyclus uiteindelijk eindigen in M .)

Dit heeft als voordeel dat de elementen van M niet afgebeeld hoeven te worden op een opeenvolgende reeks {0,..., N -1} van gehele getallen. Het heeft het nadeel dat, wanneer M veel kleiner is dan het domein van P , te veel iteraties nodig kunnen zijn voor elke bewerking. Als P een blokcijfer is met een vaste grootte, zoals AES, is dit een ernstige beperking op de grootten van M waarvoor deze methode efficiënt is.

Een toepassing kan bijvoorbeeld 100-bits waarden met AES willen versleutelen op een manier die een andere 100-bits waarde creëert. Met deze techniek kan AES-128-ECB-codering worden toegepast totdat deze een waarde bereikt waarbij alle 28 hoogste bits op 0 zijn ingesteld, wat gemiddeld 2 28 iteraties zal vergen .

FPE van een Feistel-netwerk

Het is ook mogelijk om een ​​FPE-algoritme te maken met behulp van een Feistel-netwerk . Een Feistel-netwerk heeft een bron van pseudo-willekeurige waarden nodig voor de subsleutels voor elke ronde, en de uitvoer van het AES-algoritme kan worden gebruikt als deze pseudo-willekeurige waarden. Wanneer dit is gebeurd, is de resulterende Feistel-constructie goed als er voldoende rondes worden gebruikt.

Een manier om een ​​FPE-algoritme te implementeren dat AES en een Feistel-netwerk gebruikt, is door zoveel bits AES-uitvoer te gebruiken als nodig zijn om de lengte van de linker- of rechterhelften van het Feistel-netwerk te evenaren. Als er bijvoorbeeld een 24-bits waarde als subsleutel nodig is, is het mogelijk om voor deze waarde de laagste 24 bits van de uitvoer van AES te gebruiken.

Dit leidt er misschien niet toe dat de uitvoer van het Feistel-netwerk het formaat van de invoer behoudt, maar het is mogelijk om het Feistel-netwerk op dezelfde manier te herhalen als de fiets-wandeltechniek om ervoor te zorgen dat het formaat behouden kan blijven. Omdat het mogelijk is om de grootte van de ingangen aan te passen aan een Feistel-netwerk, is het mogelijk om het zeer waarschijnlijk te maken dat deze iteratie gemiddeld zeer snel eindigt. In het geval van creditcardnummers zijn er bijvoorbeeld 10 15 mogelijke 16-cijferige creditcardnummers (rekening houdend met het redundante controlecijfer ), en omdat de 10 15 ≈ 2 49.8 , met behulp van een 50-bits breed Feistel-netwerk samen met fietsen zal een FPE-algoritme creëren dat gemiddeld vrij snel versleutelt.

De Thorp-shuffle

Een Thorp-shuffle is als een geïdealiseerde kaartshuffle, of equivalent een maximaal ongebalanceerd Feistel-cijfer waarbij één kant een enkel bit is. Het is gemakkelijker om de veiligheid te bewijzen voor ongebalanceerde Feistel-cijfers dan voor gebalanceerde.

VIL-modus

Voor domeingroottes met een macht van twee en een bestaand blokcijfer met een kleinere blokgrootte, kan een nieuw cijfer worden gemaakt met behulp van de VIL-modus zoals beschreven door Bellare, Rogaway.

Hasty Pudding Cipher

De Hasty Pudding Cipher gebruikt aangepaste constructies (niet afhankelijk van bestaande blokcijfers als primitieven) om willekeurige eindige kleine domeinen te versleutelen.

De FFSEM/FFX-modus van AES

De FFSEM-modus van AES (specificatie) die door NIST ter overweging is geaccepteerd, maakt gebruik van de Feistel-netwerkconstructie van Black en Rogaway zoals hierboven beschreven, met AES voor de ronde functie, met één kleine wijziging: een enkele toets wordt gebruikt en wordt enigszins aangepast voor elke ronde.

Met ingang van februari 2010 is FFSEM vervangen door de FFX-modus geschreven door Mihir Bellare , Phillip Rogaway en Terence Spies. (specificatie, NIST Block Cipher Modes Development , 2010).

FPE voor JPEG 2000-codering

In de JPEG 2000- standaard mogen de markeringscodes (in het bereik 0xFF90 tot en met 0xFFFF) niet verschijnen in de leesbare tekst en cijfertekst. De eenvoudige modulaire 0xFF90-techniek kan niet worden toegepast om het JPEG 2000-coderingsprobleem op te lossen. De cijfertekstwoorden 0x23FF en 0x9832 zijn bijvoorbeeld geldig, maar hun combinatie 0x23FF9832 wordt ongeldig omdat het de markeringscode 0xFF98 introduceert. Evenzo kan de eenvoudige fiets-wandeltechniek niet worden toegepast om het JPEG2000-coderingsprobleem op te lossen, aangezien twee geldige cijfertekstblokken ongeldige cijfertekst kunnen geven wanneer ze worden gecombineerd. Als het eerste cijfertekstblok bijvoorbeeld eindigt met bytes "...30FF" en het tweede cijfertekstblok begint met bytes "9832...", dan verschijnt de markeringscode "0xFF98" in de cijfertekst.

Twee mechanismen voor formaatbehoudende encryptie van JPEG 2000 werden gegeven in de paper "Efficient and Secure Encryption Schemes for JPEG2000" door Hongjun Wu en Di Ma. Om formaatbehoudende codering van JPEG 2000 uit te voeren, is de techniek om de byte "0xFF" uit te sluiten in de codering en decodering. Vervolgens voert een JPEG 2000-coderingsmechanisme modulo-n-toevoeging uit met stroomcodering; een ander JPEG 2000-coderingsmechanisme voert de fietswandeltechniek uit met blokcodering.

Andere FPE-constructies

Verschillende FPE-constructies zijn gebaseerd op het toevoegen van de uitvoer van een standaardcijfer, modulo n, aan de te versleutelen gegevens, met verschillende methoden om het resultaat onpartijdig te maken. De modulo-n-toevoeging die door veel van de constructies wordt gedeeld, is de onmiddellijk voor de hand liggende oplossing voor het FPE-probleem (en dus het gebruik ervan in een aantal gevallen), met als belangrijkste verschillen de onbevooroordeelde mechanismen die worden gebruikt.

Sectie 8 van de FIPS 74, Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Use the NBS Data Encryption Standard , beschrijft een manier om het DES-coderingsalgoritme te gebruiken op een manier die het formaat van de gegevens behoudt via modulo-n-toevoeging gevolgd door een onpartijdige operatie. Deze norm is op 19 mei 2005 ingetrokken, dus de techniek moet als achterhaald worden beschouwd in termen van een formele norm.

Een ander vroeg mechanisme voor formaatbehoudende encryptie was Peter Gutmann 's "Encrypting data with a limited range of values", die opnieuw modulo-n-toevoeging uitvoert op elke codering met enkele aanpassingen om het resultaat uniform te maken, waarbij de resulterende codering zo sterk is het onderliggende coderingsalgoritme waarop het is gebaseerd.

Het artikel "Using Datatype-Preserving Encryption to Enhance Data Warehouse Security" door Michael Brightwell en Harry Smith beschrijft een manier om het DES- coderingsalgoritme te gebruiken op een manier die het formaat van de leesbare tekst behoudt. Deze techniek lijkt geen onpartijdige stap toe te passen zoals de andere modulo-n-technieken waarnaar hier wordt verwezen.

De paper "Format-Preserving Encryption" door Mihir Bellare en Thomas Ristenpart beschrijft het gebruik van "bijna gebalanceerde" Feistel-netwerken om veilige FPE-algoritmen te creëren.

Het artikel "Format Controlling Encryption Using Datatype Preserving Encryption" door Ulf Mattsson beschrijft andere manieren om FPE-algoritmen te creëren.

Een voorbeeld van een FPE-algoritme is FNR ( Flexibele Naor en Reingold ).

Acceptatie van FPE-algoritmen door normalisatie-instanties

NIST Special Publication 800-38G, "Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption" specificeert twee methoden: FF1 en FF3. Details over de ingediende voorstellen voor elk zijn te vinden op de NIST Block Cipher Modes Development-site, inclusief patent- en testvectorinformatie. Voorbeeldwaarden zijn beschikbaar voor zowel FF1 als FF3.

  • FF1 is FFX[Radix] "Format-preserving Feistel-based Encryption Mode" die ook in standaardprocessen onder ANSI X9 als X9.119 en X9.124 zit. Het werd ingediend bij NIST door Mihir Bellare van de Universiteit van Californië, San Diego, Phillip Rogaway van de Universiteit van Californië, Davis en Terence Spies van Voltage Security Inc. Testvectoren worden geleverd en delen ervan zijn gepatenteerd. (DRAFT SP 800-38G Rev 1) vereist dat de minimale domeingrootte van de gegevens die worden versleuteld 1 miljoen is (voorheen 100).
  • FF3 is BPS genoemd naar de auteurs. Het werd ingediend bij NIST door Eric Brier, Thomas Peyrin en Jacques Stern van Ingenico, Frankrijk. Auteurs verklaarden aan NIST dat hun algoritme niet gepatenteerd is. Het CyberRes Voltage-product , hoewel claimt ook patenten te bezitten voor de BPS-modus. Op 12 april 2017 concludeerde NIST dat FF3 "niet langer geschikt is als een algemene FPE-methode" omdat onderzoekers een kwetsbaarheid hebben gevonden.
  • FF3-1 (DRAFT SP 800-38G Rev 1) vervangt FF3 en vereist dat de minimale domeingrootte van de gegevens die worden versleuteld 1 miljoen is (voorheen 100).

Een andere modus was opgenomen in de concept-NIST-richtlijn, maar werd verwijderd vóór de definitieve publicatie.

  • FF2 is een VAES3-schema voor FFX: een aanvulling op "The FFX Mode of Operation for Preserving Encryption": een parameterverzameling voor coderingsreeksen van willekeurige radix met subsleutelbewerking om de levensduur van de coderingssleutel te verlengen. Het is ingediend bij NIST door Joachim Vance van VeriFone Systems Inc. Testvectoren worden niet afzonderlijk van FF1 geleverd en delen ervan zijn gepatenteerd. Auteurs hebben een aangepast algoritme ingediend als DFF dat actief wordt overwogen door NIST.

Korea heeft ook een FPE-standaard ontwikkeld, FEA-1 en FEA-2.

Implementaties

Open Source-implementaties van FF1 en FF3 zijn openbaar beschikbaar in C-taal , Go-taal , Java , Node.js , Python , C#/.Net en Rust

Referenties