Formatbevarande kryptering
Inom kryptografi syftar formatbevarande kryptering ( FPE ) på kryptering på ett sådant sätt att utdata (chiffertexten ) är i samma format som indata (klartexten ) . Innebörden av "format" varierar. Vanligtvis används endast ändliga uppsättningar tecken; numeriska, alfabetiska eller alfanumeriska. Till exempel:
- Kryptera ett 16-siffrigt kreditkortsnummer så att chiffertexten blir ett annat 16-siffrigt nummer.
- Kryptera ett engelskt ord så att chiffertexten är ett annat engelskt ord.
- Kryptera ett n -bitars nummer så att chiffertexten är ett annat n -bitars nummer (detta är definitionen av ett n -bitars blockchiffer).
För sådana finita domäner, och för diskussionen nedan, är chifferet ekvivalent med en permutation av N heltal {0, ... , N −1 } där N är storleken på domänen.
Motivering
Begränsade fältlängder eller format
Ett motiv för att använda FPE kommer från problemen med att integrera kryptering i befintliga applikationer, med väldefinierade datamodeller. Ett typiskt exempel skulle vara ett kreditkortsnummer , till exempel 1234567812345670 (16 byte långt, endast siffror).
Att lägga till kryptering till sådana applikationer kan vara en utmaning om datamodeller ska ändras, eftersom det vanligtvis innebär att ändra fältlängdsgränser eller datatyper. Till exempel skulle utdata från ett typiskt blockchiffer förvandla kreditkortsnummer till ett hexadecimalt (t.ex. 0x96a45cbcf9c2a9425cde9e274948cb67 , 34 byte, hexadecimala siffror) eller Base64- värde ( t.ex. lqRcvPnCqUJc, LQRcvPnCqUJc, LqRcvPnCqUJc,LpfNsUJc,Lpwc ,Lpw3,L,L,L,L,L,L,L,L,L,L,2,L,L,L,L,L; tecken), vilket kommer att bryta alla befintliga applikationer som förväntar sig att kreditkortsnumret ska vara ett 16-siffrigt nummer.
Förutom enkla formateringsproblem, med AES-128-CBC, kan detta kreditkortsnummer krypteras till det hexadecimala värdet 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df . Utöver de problem som orsakas av att skapa ogiltiga tecken och öka storleken på data, ändrar data som krypteras med CBC-läget för en krypteringsalgoritm också dess värde när den dekrypteras och krypteras igen. Detta händer eftersom det slumpmässiga startvärdet som används för att initiera krypteringsalgoritmen och som ingår som en del av det krypterade värdet är olika för varje krypteringsoperation. På grund av detta är det omöjligt att använda data som har krypterats med CBC-läget som en unik nyckel för att identifiera en rad i en databas.
FPE försöker förenkla övergångsprocessen genom att bevara formateringen och längden på originaldata, vilket tillåter en drop-in ersättning av klartextvärden med deras chiffertexter i äldre applikationer.
Jämförelse med verkligt slumpmässiga permutationer
Även om en verkligt slumpmässig permutation är det ideala FPE-chifferet, är det för stora domäner omöjligt att förgenerera och komma ihåg en verkligt slumpmässig permutation. Så problemet med FPE är att generera en pseudoslumpmässig permutation från en hemlig nyckel, på ett sådant sätt att beräkningstiden för ett enstaka värde är liten (helst konstant, men viktigast av allt mindre än O(N) ) .
Jämförelse med blockchiffer
Ett n -bitars blockchiffer är tekniskt sett en FPE på uppsättningen {0, ..., 2n -1 } . Om en FPE behövs på en av dessa standardstorlekar (till exempel n = 64 för DES och n = 128 för AES) kan ett blockchiffer av rätt storlek användas.
Vid typisk användning används emellertid ett blockchiffer i ett funktionssätt som tillåter det att kryptera godtyckligt långa meddelanden och med en initialiseringsvektor som diskuterats ovan. I detta läge är ett blockchiffer inte en FPE.
Definition av säkerhet
I kryptografisk litteratur (se de flesta av referenserna nedan) är måttet på en "bra" FPE om en angripare kan skilja FPE från en verkligt slumpmässig permutation. Olika typer av angripare postuleras, beroende på om de har tillgång till orakel eller kända chiffertext/klartext-par.
Algoritmer
används ett välförstått blockchiffer (som AES ) som en primitiv för att ta platsen för en idealisk slumpmässig funktion. Detta har fördelen att inkorporering av en hemlig nyckel i algoritmen är lätt. Där AES nämns i följande diskussion, skulle alla andra bra blockchiffer fungera också.
FPE-konstruktionerna av Black och Rogaway
Implementering av FPE med säkerhet som bevisligen är relaterad till den för det underliggande blockchifferet genomfördes först i en artikel av kryptograferna John Black och Phillip Rogaway , som beskrev tre sätt att göra detta. De bevisade att var och en av dessa tekniker är lika säker som blockchifferet som används för att konstruera den. Detta betyder att om AES-algoritmen används för att skapa en FPE-algoritm, så är den resulterande FPE-algoritmen lika säker som AES eftersom en motståndare som kan besegra FPE-algoritmen också kan besegra AES-algoritmen. Därför, om AES är säkert, så är FPE-algoritmerna konstruerade från det också säkra. I allt det följande E AES-krypteringsoperationen som används för att konstruera en FPE-algoritm och F betecknar FPE-krypteringsoperationen.
FPE från ett prefixchiffer
Ett enkelt sätt att skapa en FPE-algoritm på {0, ..., N -1} är att tilldela en pseudoslumpmässig vikt till varje heltal och sedan sortera efter vikt. Vikterna definieras genom att tillämpa ett befintligt blockchiffer på varje heltal. Black och Rogaway kallar denna teknik för ett "prefixchiffer" och visade att det förmodligen var lika bra som blockchifferet som användes.
För att skapa en FPE på domänen {0,1,2,3}, med en nyckel K tillämpa AES( K ) på varje heltal, vilket t.ex.
vikt (0) = 0x56c644080098fc5570f2b329323dbf62 vikt (1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 vikt (2) = 0x47d2627bf401f vikt 0x077de40941c93774857961a8a772650d
Att sortera [0,1,2,3] efter vikt ger [3,1,2,0], så chiffret är
F (0) = 3 F (1) = 1 F (2) = 2 F (3) = 0
Denna metod är endast användbar för små värden på N . För större värden blir storleken på uppslagstabellen och det antal krypteringar som krävs för att initiera tabellen för stor för att vara praktisk.
FPE från cykelgång
Om det finns en uppsättning M av tillåtna värden inom domänen för en pseudoslumpmässig permutation P (till exempel P kan vara ett blockchiffer som AES), kan en FPE-algoritm skapas från blockchifferet genom att upprepade gånger tillämpa blockchifferet tills resultatet är ett av de tillåtna värdena (inom M ).
CycleWalkingFPE(x) { om P ( x) är ett element av M returnerar P (x) annars returnerar CycleWalkingFPE( P (x)) }
Rekursionen kommer garanterat att upphöra. (Eftersom P är en-till-en och domänen är ändlig, bildar upprepad tillämpning av P en cykel, så från och med en punkt i M kommer cykeln så småningom att avslutas i M .)
Detta har fördelen att elementen i M inte behöver mappas till en på varandra följande sekvens {0,..., N -1} av heltal. Det har nackdelen, när M är mycket mindre än P :s domän, att för många iterationer kan krävas för varje operation. Om P är ett blockchiffer med en fast storlek, såsom AES, är detta en allvarlig begränsning av storlekarna på M för vilka denna metod är effektiv.
Till exempel kan ett program vilja kryptera 100-bitars värden med AES på ett sätt som skapar ytterligare ett 100-bitars värde. Med denna teknik kan AES-128-ECB-kryptering tillämpas tills den når ett värde som har alla sina 28 högsta bitar inställda på 0, vilket i genomsnitt tar 2 28 iterationer att hända.
FPE från ett Feistel-nätverk
Det är också möjligt att göra en FPE-algoritm med hjälp av ett Feistel-nätverk . Ett Feistel-nätverk behöver en källa med pseudo-slumpmässiga värden för undernycklarna för varje runda, och utdata från AES-algoritmen kan användas som dessa pseudo-slumpmässiga värden. När detta är gjort är den resulterande Feistel-konstruktionen bra om tillräckligt många rundor används.
Ett sätt att implementera en FPE-algoritm med hjälp av AES och ett Feistel-nätverk är att använda så många bitar av AES-utdata som behövs för att vara lika med längden på den vänstra eller högra halvan av Feistel-nätverket. Om ett 24-bitars värde behövs som en undernyckel, till exempel, är det möjligt att använda de lägsta 24 bitarna av utdata från AES för detta värde.
Detta kanske inte resulterar i att utdata från Feistel-nätverket bevarar formatet på ingången, men det är möjligt att iterera Feistel-nätverket på samma sätt som cykelvandringstekniken gör för att säkerställa att formatet kan bevaras. Eftersom det är möjligt att justera storleken på ingångarna till ett Feistel-nätverk, är det möjligt att göra det mycket troligt att denna iteration slutar väldigt snabbt i genomsnitt. När det gäller kreditkortsnummer, till exempel, finns det 10 15 möjliga 16-siffriga kreditkortsnummer (som står för den överflödiga kontrollsiffran ), och eftersom 10 15 ≈ 2 49.8 använder ett 50-bitars brett Feistel-nätverk tillsammans med cykling kommer att skapa en FPE-algoritm som krypterar ganska snabbt i genomsnitt.
Thorp shuffle
En Thorp-shuffle är som en idealiserad kort-shuffle, eller motsvarande ett maximalt obalanserat Feistel-chiffer där en sida är en enda bit. Det är lättare att bevisa säkerhet för obalanserade Feistel-chiffer än för balanserade.
VIL-läge
För domänstorlekar som är en potens av två, och ett befintligt blockchiffer med en mindre blockstorlek, kan ett nytt chiffer skapas med VIL-läge som beskrivs av Bellare, Rogaway.
Hasty Pudding Chiffer
Hasty Pudding Cipher använder anpassade konstruktioner (inte beroende av befintliga blockchiffer som primitiver) för att kryptera godtyckliga ändliga små domäner.
FFSEM/FFX-läget för AES
FFSEM-läget för AES (specifikation) som har godkänts för övervägande av NIST använder Feistel-nätverkskonstruktionen av Black och Rogaway som beskrivs ovan, med AES för den runda funktionen, med en liten modifiering: en enda nyckel används och justeras något för varje omgång.
Från och med februari 2010 har FFSEM ersatts av FFX-läget skrivet av Mihir Bellare , Phillip Rogaway och Terence Spies. (specifikation, NIST Block Cipher Modes Development , 2010 ).
FPE för JPEG 2000-kryptering
I JPEG 2000- standarden ska markörkoderna (i intervallet 0xFF90 till 0xFFFF) inte visas i klartext och chiffertext. Den enkla modulära-0xFF90-tekniken kan inte användas för att lösa JPEG 2000-krypteringsproblemet. Till exempel är chiffertextorden 0x23FF och 0x9832 giltiga, men deras kombination 0x23FF9832 blir ogiltig eftersom den introducerar markörkoden 0xFF98. På liknande sätt kan den enkla cykelgångstekniken inte användas för att lösa JPEG2000-krypteringsproblemet eftersom två giltiga chiffertextblock kan ge ogiltig chiffertext när de kombineras. Till exempel, om det första chiffertextblocket slutar med byte "...30FF" och det andra chiffertextblocket börjar med byte "9832...", så skulle markörkoden "0xFF98" visas i chiffertexten.
Två mekanismer för formatbevarande kryptering av JPEG 2000 gavs i tidningen "Efficient and Secure Encryption Schemes for JPEG2000" av Hongjun Wu och Di Ma. För att utföra formatbevarande kryptering av JPEG 2000 är tekniken att utesluta byten "0xFF" i krypteringen och dekrypteringen. Sedan utför en JPEG 2000-krypteringsmekanism modulo-n-addition med strömchiffer; en annan JPEG 2000-krypteringsmekanism utför cykelvandringstekniken med blockchiffer.
Andra FPE-konstruktioner
Flera FPE-konstruktioner är baserade på att lägga till utdata från ett standardchiffer, modulo n, till data som ska krypteras, med olika metoder för att göra resultatet opartiskt. Modulo-n-tillägget som delas av många av konstruktionerna är den omedelbart uppenbara lösningen på FPE-problemet (därav dess användning i ett antal fall), med huvudskillnaderna är de opartiska mekanismer som används.
Avsnitt 8 i FIPS 74, Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard , beskriver ett sätt att använda DES-krypteringsalgoritmen på ett sätt som bevarar dataformatet via modulo-n-tillägg följt av en opartisk operation. Denna standard drogs tillbaka den 19 maj 2005, så tekniken bör anses vara föråldrad när det gäller att vara en formell standard.
En annan tidig mekanism för formatbevarande kryptering var Peter Gutmanns "Encrypting data with a restricted range of values" som återigen utför modulo-n-addition på vilket chiffer som helst med några justeringar för att göra resultatet enhetligt, med den resulterande krypteringen som är lika stark som den underliggande krypteringsalgoritmen som den är baserad på.
Uppsatsen "Using Datatype-Preserving Encryption to Enhance Data Warehouse Security" av Michael Brightwell och Harry Smith beskriver ett sätt att använda DES- krypteringsalgoritmen på ett sätt som bevarar formatet för klartexten. Den här tekniken verkar inte tillämpa ett opartiskt steg som de andra modulo-n-teknikerna som refereras till här.
Tidningen "Format-Preserving Encryption" av Mihir Bellare och Thomas Ristenpart beskriver hur man använder "nästan balanserade" Feistel-nätverk för att skapa säkra FPE-algoritmer.
Uppsatsen "Format Controlling Encryption Using Datatype Preserving Encryption" av Ulf Mattsson beskriver andra sätt att skapa FPE-algoritmer.
Ett exempel på FPE-algoritm är FNR ( Flexible Naor och Reingold) .
Godkännande av FPE-algoritmer av standardiseringsmyndigheter
NIST Special Publication 800-38G, "Recommendation for Block Chipher Modes of Operation: Methods for Format-Preserving Encryption" specificerar två metoder: FF1 och FF3. Detaljer om förslagen som lämnats in för varje kan hittas på NIST Block Cipher Modes Development-webbplatsen, inklusive patent- och testvektorinformation. Exempelvärden är tillgängliga för både FF1 och FF3.
- FF1 är FFX[Radix] "Format-bevarande Feistel-based Encryption Mode" som också finns i standardprocesser under ANSI X9 som X9.119 och X9.124. Den skickades till NIST av Mihir Bellare från University of California, San Diego, Phillip Rogaway från University of California, Davis och Terence Spies från Voltage Security Inc. Testvektorer tillhandahålls och delar av den är patenterade. (DRAFT SP 800-38G Rev 1) kräver att minsta domänstorlek för data som krypteras är 1 miljon (tidigare 100).
- FF3 är BPS uppkallad efter författarna. Den lämnades in till NIST av Eric Brier, Thomas Peyrin och Jacques Stern från Ingenico, Frankrike. Författare förklarade för NIST att deras algoritm inte är patenterad. CyberRes Voltage-produkten , men hävdar att de äger patent även för BPS-läge. Den 12 april 2017 drog NIST slutsatsen att FF3 "inte längre är lämplig som en allmän FPE-metod" eftersom forskare hittat en sårbarhet.
- FF3-1 (DRAFT SP 800-38G Rev 1) ersätter FF3 och kräver att minsta domänstorlek för data som krypteras är 1 miljon (tidigare 100).
Ett annat läge inkluderades i utkastet till NIST-vägledning men togs bort innan den slutliga publiceringen.
- FF2 är ett VAES3-schema för FFX: Ett tillägg till "FFX-driftsläget för att bevara kryptering": En parametersamling för kryptering av strängar av godtycklig radix med undernyckeloperation för att förlänga livslängden för krypteringsnyckeln. Den skickades till NIST av Joachim Vance från VeriFone Systems Inc. Testvektorer levereras inte separat från FF1 och delar av den är patenterade. Författare har skickat in en modifierad algoritm som DFF som är under aktiv övervägande av NIST.
Korea har också utvecklat en FPE-standard, FEA-1 och FEA-2.
Genomföranden
Open Source-implementeringar av FF1 och FF3 är offentligt tillgängliga i C-språk , Go-språk , Java , Node.js , Python , C#/.Net och Rust