Format -bevarande kryptering ( FPE ) betyder kryptering där utdata ( chiffertext ) är i samma format som indata ( klartext ) . Innebörden av ordet "format" varierar. Vanligtvis menas endast ändliga mängder , till exempel:
För sådana ändliga mängder, och för diskussionen nedan, är chifferet ekvivalent med en permutation av N heltal {0, ... , N −1 }, där N är storleken på området.
Det första skälet till att använda FPE är problemen med att använda kryptering i befintliga applikationer med väldefinierade datamodeller. Ett typiskt exempel är ett kreditkortsnummer , till exempel 1234567812345670(16 byte, endast nummer).
Att lägga till kryptering till sådana applikationer kan vara svårt om datamodellen behöver ändras, eftersom det vanligtvis innebär ändringar av fältlängdsbegränsningen eller datatypen . Till exempel kommer blockkryptering av ett kreditkortsnummer att resultera i hexadecimala ( 0x96a45cbcf9c2a9425cde9e274948cb67, 34 byte, hexadecimala siffror) eller Base64 ( lqRcvPnCqUJc3p4nSUjLZw==, 24 byte, alfanumeriska och specialtecken). Detta kommer att bryta alla befintliga applikationer som förväntar sig ett 16-siffrigt kreditkortsnummer som inmatning.
Förutom enkla formateringsproblem, med AES-128-CBC, kan detta kreditkortsnummer kodas till ett hexadecimalt värde 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. Förutom problemet som orsakas av ogiltiga tecken eller storleksökning, ändrar data krypterad med CBC-läge värde när den dekrypteras och krypteras igen. Detta beror på att det slumpmässiga startvärdet , som används för att initiera krypteringsalgoritmen och ingår som det krypterade värdet, är olika för varje krypteringsoperation. Därför är det inte möjligt att använda data som har krypterats med CBC-läge som en unik nyckel för att identifiera en rad i en databas .
FPE är nödvändigt för att förenkla övergångsprocessen genom att bevara formateringen och längden på originaldata, vilket gör det möjligt att ersätta klartexten med dess kryptogram i de applikationer som används.
Generering av pseudoslumptalFormat Preserving Encryption (FPE) kan generera unika och icke-repeterbara nummer. Huvudsyftet med FPE är att kryptera en fil på ett sådant sätt att både originalfilen och den krypterade filen har samma format.
Till exempel, om en sekvens av nummer från 11111 till 88888 skapas, tar FPE det första värdet 11111 och krypterar det till ett annat 5-siffrigt nummer. Denna process fortsätter tills det sista värdet 88888 har lästs. Alla krypterade värden är unika och slumpmässiga. Dessa nummer används som serienyckel för produkten.
Även om en verkligt slumpmässig permutation är ett idealiskt FPE-chiffer, är det för stora uppsättningar inte möjligt att förgenerera och komma ihåg en verkligt slumpmässig permutation. Så, FPE-problemet är att generera en pseudo-slumpmässig permutation från en hemlig nyckel på ett sådant sätt att beräkningstiden för ett värde är liten (helst konstant, men viktigast av allt, mindre än O (N)).
N -bitars blockchiffer (t.ex. AES) är tekniskt sett en FPE på uppsättningen {0, ..., 2n -1 }. Om FPE behövs på en av standarduppsättningarna (där n = 128, 192, 256), kan du använda blockkryptering av önskad storlek.
Emellertid, i standardanvändning, används blockkryptering i ett läge som tillåter godtyckligt långa meddelanden att krypteras, och med användning av en initialiseringsvektor som diskuterats ovan. I detta läge är blockchiffer inte FPE.
I kryptografilitteraturen (se länkar nedan) bestäms "godheten" hos en FPE av om en angripare kan skilja FPE från en verkligt slumpmässig permutation. Angripare skiljer sig åt beroende på om de har tillgång till oraklet eller om de känner till ett par med chiffertext/klartext.
I de flesta av tillvägagångssätten som nämns ovan används ett välkänt blockchiffer (som AES ) som en idealisk slumpmässig funktion.
I ett sådant fall är det fördelaktigt enkelt att införa den hemliga nyckeln i algoritmen. Längre fram i texten kan vilket bra blockchiffer som helst användas istället för AES.
FPE-implementeringen som ligger till grund för blockchifferet användes först av kryptograferna John Black och Phillip Rogaway , [1] som beskrev tre sätt att göra detta. De har bevisat att var och en av dessa metoder är lika säker som blockchifferet som används för att konstruera dem. Detta innebär att en motståndare som kan dekryptera FPE-algoritmen också kan dekryptera AES-algoritmen. Därför, för pålitliga AES-algoritmer, är FPE-algoritmerna som bygger på dem också pålitliga. Härefter betecknar E AES-krypteringsoperationen, som används för att bygga FPE-algoritmen, och P betecknar FPE.
FPE baserat på prefixchifferEtt enkelt sätt att skapa en FPE-algoritm på uppsättningen {0,..., N -1} är att tilldela en pseudoslumpmässig vikt till varje heltal och sedan sortera efter vikt. Vikterna bestäms genom att tillämpa ett befintligt blockchiffer på varje heltal. Black och Rogoway kallar denna metod för "prefix chiffer".
Så för att skapa en FPE på uppsättningen {0,1,2,3} med en given nyckel K , tillämpa AES( K ) på varje heltal i vår uppsättning, till exempel,
weight(0) = 0x56c644080098fc5570f2b329323dbf62
weight(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7
weight(2) = 0x47d2e1bf72264fa01fb274465e56ba20
weight(3) = 0x077de40941c93774857961a8a772650d
Att sortera [0,1,2,3] efter vikt ger [3,1,2,0], så chiffret ser ut så här:
F(0) = 3
F(1) = 1
F(2) = 2
F(3) = 0.
Denna metod används endast för små värden på N. För stora värden blir storleken på uppslagstabellen och det antal kodningar som krävs för att initiera tabellen för stora.
FPE från cykelgångOm det finns en uppsättning M med giltiga värden inom den pseudo-slumpmässiga permutationsregionen P (till exempel kan P vara ett blockchiffer av typen AES), kan FPE-algoritmen genereras från blockchifferet genom att upprepade gånger tillämpa blockchifferet tills resultatet är ett av de giltiga värdena (inom M ).
CycleWalkingFPE(x) { om ''P''(x) är ett element av ''M'' returnera ''P''(x) annan return CycleWalkingFPE(''P''(x)) }Cykeln kommer definitivt att ta slut. (Eftersom P går efter varandra och mängden är ändlig, bildar upprepad tillämpning av P en cykel, så från en punkt i M kommer cykeln att stanna i M. )
Fördelen med denna metod är att elementen i mängden M inte behöver mappas till elementen i sekvensen {0,..., N -1} av heltal. Nackdelen är ett stort antal iterationer för varje operation om M är mycket mindre än mängden P . Om P är ett blockchiffer av en given storlek, såsom AES, så finns det en hård begränsning på M under vilken denna metod är effektiv.
Till exempel måste en applikation kryptera ett 100-bitars AES-värde så att utdata är ett annat 100-bitarsvärde. Med denna teknik kan AES-128-ECB-kryptering tillämpas tills den når ett värde med 28 mest signifikanta bitar lika med 0, vilket tar i genomsnitt 228 iterationer.
FPE baserad på Feistel-nätverketEn annan metod för att skapa en FPE-algoritm är baserad på användningen av Feistel-nätverket . Feistel-nätverket behöver en källa till pseudo-slumpmässiga värden för nycklarna för varje omgång, och utdata från AES-algoritmen kan användas som dessa värden. Den resulterande Feistel-konstruktionen är robust om tillräckligt många rundor används. [2]
Ett sätt att implementera en FPE-algoritm baserad på ett Feistel-nätverk och AES är att använda antalet bitar i utdata från AES-algoritmen som skulle vara lika med längden på den vänstra eller högra halvan av Feistel-nätverket. Till exempel, om ett 24-bitars värde behövs för nyckeln, kan de sista 24 bitarna av utdata från AES-algoritmen användas.
Denna metod kanske inte bevarar formatet, men det är möjligt att återanvända Feistel-nätverket på samma sätt som cykel-gångsmetoden tills formatet bevaras. Genom att justera storleken på ingången till Feistel-nätverket kan slingan slutföras snabbt. Till exempel finns det 10 16 (10 16 = 2 53,1 ) möjliga 16-siffriga kreditkortsnummer. Med hjälp av ett 54-bitars brett Feistel-nätverk och cykelvandring är det möjligt att skapa en FPE-algoritm som krypterar ganska snabbt.
Flera andra FPE-konstruktioner förlitar sig på olika metoder för att lägga till utdata från en standardchiffermodul till data som ska krypteras. Att lägga till modulo n är en ganska uppenbar lösning på FPE-krypteringsproblemet.
Avsnitt 8 i FIPS 74, Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard , [3] beskriver ett sätt att använda DES-krypteringsalgoritmen som bevarar dataformatet genom att lägga till modulo n. Denna standard togs bort den 19 maj 2005, så metoden är utfasad i termer av standarden.
En annan metod för formatbevarande kryptering var Peter Gutmans "Encrypting data with a restricted range of values", [4] som diskuterade en algoritm som också utförde modulo n addition med några justeringar.
Verket "Using Datatype-Preserving Encryption to Enhance Data Warehouse Security" [5] av Michael Brightwell och Harry Smith beskriver ett sätt att använda DES- krypteringsalgoritmen som bevarar klartextdataformatet. Denna metod använder inte modulo n addition.
Verket "Format-Preserving Encryption" [6] av Mihir Bellar och Thomas Ristenpart beskriver användningen av ett "nästan balanserat" Feistel-nätverk för att skapa en säker FPE-algoritm.
Ulf Mattssons Format Controlling Encryption Using Datatype Preserving Encryption [7] beskriver andra metoder för att implementera FPE-algoritmen.
Ett exempel på en FPE-algoritm är FNR ( Flexible Naor och Reingold ). [åtta]
NIST har publicerat Special Publication 800-38G, DRAFT Recommendation for Block Chipher Modes of Operation: Methods for Format-Preserving Encryption. [9] Denna publikation definierar tre metoder FF1, FF2 och FF3. Detaljer om dessa, samt information om patent och testkit, finns på webbplatsen NIST Block Cipher Modes Development. [tio]
| Symmetriska kryptosystem | |
|---|---|
| Streama chiffer | |
| Feistel nätverk | |
| SP nätverk | |
| Övrig | |
| Public key kryptosystem | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Algoritmer |
| ||||||||
| Teori |
| ||||||||
| Standarder |
| ||||||||
| Ämnen |
| ||||||||
| Hash-funktioner | |
|---|---|
| generell mening | |
| Kryptografisk | |
| Nyckelgenereringsfunktioner | |
| Kontrollnummer ( jämförelse ) | |
| Hashes |
|