Crittografia con conservazione del formato - Format-preserving encryption
Nella crittografia , la crittografia con conservazione del formato ( FPE ), si riferisce alla crittografia in modo tale che l'output (il testo cifrato ) sia nello stesso formato dell'input (il testo in chiaro ). Il significato di "formato" varia. In genere vengono utilizzati solo insiemi finiti di caratteri; numerico, alfabetico o alfanumerico. Per esempio:
- Cifratura di un numero di carta di credito a 16 cifre in modo che il testo cifrato sia un altro numero a 16 cifre.
- Crittografia di una parola inglese in modo che il testo cifrato sia un'altra parola inglese.
- Crittografare un numero a n bit in modo che il testo cifrato sia un altro numero a n bit (questa è la definizione di un cifrario a blocchi a n bit).
Per tali domini finiti, e per gli scopi della discussione seguente, il cifrario è equivalente a una permutazione di N interi {0, ... , N −1 } dove N è la dimensione del dominio.
Motivazione
Lunghezze o formati dei campi limitati
Una motivazione per l'utilizzo di FPE deriva dai problemi associati all'integrazione della crittografia nelle applicazioni esistenti, con modelli di dati ben definiti. Un tipico esempio potrebbe essere un numero di carta di credito , ad esempio 1234567812345670(16 byte di lunghezza, solo cifre).
L'aggiunta della crittografia a tali applicazioni potrebbe essere difficile se i modelli di dati devono essere modificati, poiché di solito comporta la modifica dei limiti di lunghezza del campo o dei tipi di dati. Ad esempio, l'output di un tipico cifrario a blocchi trasformerebbe il numero della carta di credito in un valore esadecimale (ad es 0x96a45cbcf9c2a9425cde9e274948cb67. 34 byte, cifre esadecimali) o in un valore Base64 (ad es lqRcvPnCqUJc3p4nSUjLZw==. 24 byte, caratteri alfanumerici e speciali), che interromperà qualsiasi applicazione esistente in attesa del credito il numero della carta deve essere un numero di 16 cifre.
A parte i semplici problemi di formattazione, utilizzando AES-128-CBC, questo numero di carta di credito potrebbe essere crittografato con il valore esadecimale 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. Oltre ai problemi causati dalla creazione di caratteri non validi e dall'aumento delle dimensioni dei dati, i dati crittografati utilizzando la modalità CBC di un algoritmo di crittografia cambiano anche il loro valore quando vengono decifrati e crittografati nuovamente. Ciò accade perché il valore di inizializzazione casuale utilizzato per inizializzare l'algoritmo di crittografia e incluso come parte del valore crittografato è diverso per ogni operazione di crittografia. Per questo motivo, è impossibile utilizzare dati crittografati con la modalità CBC come chiave univoca per identificare una riga in un database.
FPE tenta di semplificare il processo di transizione preservando la formattazione e la lunghezza dei dati originali, consentendo una sostituzione rapida dei valori di testo normale con i loro testi cifrati nelle applicazioni legacy.
Confronto con permutazioni veramente casuali
Sebbene una permutazione veramente casuale sia il cifrario FPE ideale, per domini di grandi dimensioni è impossibile pre-generare e ricordare una permutazione veramente casuale. Quindi il problema di FPE è generare una permutazione pseudocasuale da una chiave segreta, in modo tale che il tempo di calcolo per un singolo valore sia piccolo (idealmente costante, ma soprattutto più piccolo di O(N) ).
Confronto con i cifrari a blocchi
Un cifrario a blocchi di n bit tecnicamente è un FPE sull'insieme {0, ..., 2 n -1 }. Se è necessario un FPE su uno di questi set di dimensioni standard (ad esempio, n = 64 per DES e n = 128 per AES), è possibile utilizzare un codice a blocchi della dimensione corretta.
Tuttavia, nell'uso tipico, un cifrario a blocchi viene utilizzato in una modalità operativa che gli consente di crittografare messaggi arbitrariamente lunghi e con un vettore di inizializzazione come discusso sopra. In questa modalità, un cifrario a blocchi non è un FPE.
Definizione di sicurezza
Nella letteratura crittografica (vedi la maggior parte dei riferimenti di seguito), la misura di un "buon" FPE è se un utente malintenzionato può distinguere l'FPE da una permutazione veramente casuale. Vengono postulati vari tipi di aggressori, a seconda che abbiano accesso a oracoli o coppie note di testo cifrato/testo in chiaro.
Algoritmi
Nella maggior parte degli approcci qui elencati, un cifrario a blocchi ben compreso (come AES ) viene utilizzato come primitiva per prendere il posto di una funzione casuale ideale. Questo ha il vantaggio che l'incorporazione di una chiave segreta nell'algoritmo è facile. Laddove AES è menzionato nella discussione seguente, funzionerebbe anche qualsiasi altro buon cifrario a blocchi.
Le costruzioni FPE di Black e Rogaway
L'implementazione di FPE con sicurezza probabilmente correlata a quella del cifrario a blocchi sottostante è stata intrapresa per la prima volta in un articolo dei crittografi John Black e Phillip Rogaway , che descriveva tre modi per farlo. Hanno dimostrato che ognuna di queste tecniche è sicura quanto il cifrario a blocchi utilizzato per costruirla. Ciò significa che se l'algoritmo AES viene utilizzato per creare un algoritmo FPE, l'algoritmo FPE risultante è sicuro quanto AES perché un avversario in grado di sconfiggere l'algoritmo FPE può anche sconfiggere l'algoritmo AES. Pertanto, se AES è sicuro, anche gli algoritmi FPE costruiti da esso sono sicuri. In tutto quanto segue, E indica l'operazione di crittografia AES utilizzata per costruire un algoritmo FPE e F indica l'operazione di crittografia FPE.
FPE da un codice prefisso
Un modo semplice per creare un algoritmo FPE su {0, ..., N -1} consiste nell'assegnare un peso pseudocasuale a ciascun numero intero, quindi ordinare in base al peso. I pesi sono definiti applicando una cifratura a blocchi esistente a ciascun intero. Black e Rogaway chiamano questa tecnica un "cifrario prefisso" e hanno mostrato che era probabilmente buono quanto il cifrario a blocchi utilizzato.
Quindi, per creare un FPE sul dominio {0,1,2,3}, data una chiave K applicare AES( K ) ad ogni intero, dando, ad esempio,
weight(0) = 0x56c644080098fc5570f2b329323dbf62 weight(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 weight(2) = 0x47d2e1bf72264fa01fb274465e56ba20 weight(3) = 0x077de40941c93774857961a8a772650d
Ordinando [0,1,2,3] in base al peso si ottiene [3,1,2,0], quindi il cifrario è
F(0) = 3 F(1) = 1 F(2) = 2 F(3) = 0
Questo metodo è utile solo per piccoli valori di N . Per valori più grandi, la dimensione della tabella di ricerca e il numero richiesto di crittografie per inizializzare la tabella diventano troppo grandi per essere pratici.
FPE dalla camminata in bicicletta
Se c'è un insieme M di valori consentiti all'interno del dominio di una permutazione pseudocasuale P (per esempio P può essere un cifrario a blocchi come AES), è possibile creare un algoritmo FPE dalla cifratura a blocchi applicando ripetutamente la cifratura a blocchi finché il risultato è uno dei valori consentiti (entro M ).
CycleWalkingFPE(x) {
if P(x) is an element of M then
return P(x)
else
return CycleWalkingFPE(P(x))
}
La ricorsione è garantita per terminare. (Poiché P è uno a uno e il dominio è finito, l'applicazione ripetuta di P forma un ciclo, quindi partendo da un punto in M il ciclo finirà in M .)
Questo ha il vantaggio che gli elementi di M non devono essere mappati su una sequenza consecutiva {0,..., N -1} di interi. Ha lo svantaggio, quando M è molto più piccolo del dominio di P , che potrebbero essere necessarie troppe iterazioni per ogni operazione. Se P è un cifrario a blocchi di dimensione fissa, come AES, si tratta di una restrizione severa sulle dimensioni di M per cui questo metodo è efficiente.
Ad esempio, un'applicazione potrebbe voler crittografare valori a 100 bit con AES in modo da creare un altro valore a 100 bit. Con questa tecnica, la crittografia AES-128-ECB può essere applicata fino a raggiungere un valore che ha tutti i suoi 28 bit più alti impostati su 0, il che richiederà una media di 2 28 iterazioni.
FPE da una rete Feistel
È anche possibile realizzare un algoritmo FPE utilizzando una rete Feistel . Una rete Feistel necessita di una fonte di valori pseudo-casuali per le sottochiavi per ogni round e l'output dell'algoritmo AES può essere utilizzato come questi valori pseudo-casuali. Quando questo è fatto, la costruzione Feistel risultante è buona se vengono utilizzati abbastanza round.
Un modo per implementare un algoritmo FPE utilizzando AES e una rete Feistel consiste nell'utilizzare tanti bit di output AES quanti sono necessari per eguagliare la lunghezza delle metà sinistra o destra della rete Feistel. Se è necessario un valore a 24 bit come sottochiave, ad esempio, è possibile utilizzare i 24 bit più bassi dell'uscita di AES per questo valore.
Ciò potrebbe non comportare che l'output della rete Feistel conservi il formato dell'input, ma è possibile iterare la rete Feistel nello stesso modo in cui lo fa la tecnica della camminata in bicicletta per garantire che il formato venga preservato. Poiché è possibile adattare la dimensione degli ingressi a una rete Feistel, è possibile rendere molto probabile che questa iterazione termini in media molto rapidamente. Nel caso dei numeri di carta di credito, ad esempio, ci sono 10 15 possibili numeri di carta di credito a 16 cifre (che rappresentano la cifra di controllo ridondante ) e poiché 10 15 ≈ 2 49,8 , utilizzando una rete Feistel a 50 bit insieme a la camminata in bicicletta creerà un algoritmo FPE che crittografa in media abbastanza rapidamente.
Il riordino di Thorp
Un rimescolamento di Thorp è come un rimescolamento di carte idealizzato, o equivalentemente un cifrario di Feistel massimamente sbilanciato in cui un lato è un singolo bit. È più facile dimostrare la sicurezza per i cifrari Feistel non bilanciati che per quelli bilanciati.
Modalità VIL
Per dimensioni di dominio che sono una potenza di due e un cifrario a blocchi esistente con una dimensione di blocco più piccola, è possibile creare un nuovo codice utilizzando la modalità VIL come descritto da Bellare, Rogaway.
Cifrario del budino frettoloso
L' Hasty Pudding Cipher utilizza costruzioni personalizzate (non dipendenti dai cifrari a blocchi esistenti come primitive) per crittografare piccoli domini arbitrari finiti.
La modalità FFSEM/FFX di AES
La modalità FFSEM di AES (specifica) che è stata accettata in considerazione dal NIST utilizza la costruzione della rete Feistel di Black e Rogaway descritta sopra, con AES per la funzione rotonda, con una leggera modifica: viene utilizzato un solo tasto e viene leggermente modificato per ogni turno.
A partire da febbraio 2010, FFSEM è stato sostituito dalla modalità FFX scritta da Mihir Bellare , Phillip Rogaway e Terence Spies. (specifiche, NIST Block Cipher Modes Development , 2010).
FPE per crittografia JPEG 2000
Nello standard JPEG 2000 , i codici marker (nell'intervallo da 0xFF90 a 0xFFFF) non dovrebbero apparire nel testo in chiaro e nel testo cifrato. La semplice tecnica modular-0xFF90 non può essere applicata per risolvere il problema della crittografia JPEG 2000. Ad esempio, le parole del testo cifrato 0x23FF e 0x9832 sono valide, ma la loro combinazione 0x23FF9832 diventa non valida poiché introduce il codice marcatore 0xFF98. Allo stesso modo, la semplice tecnica della camminata in bicicletta non può essere applicata per risolvere il problema della crittografia JPEG2000 poiché due blocchi di testo cifrato validi possono fornire un testo cifrato non valido quando vengono combinati. Ad esempio, se il primo blocco di testo cifrato termina con i byte "...30FF" e il secondo blocco di testo cifrato inizia con i byte "9832...", nel testo cifrato apparirà il codice marcatore "0xFF98".
Due meccanismi per la crittografia a conservazione del formato di JPEG 2000 sono stati forniti nel documento "Efficient and Secure Encryption Schemes for JPEG2000" di Hongjun Wu e Di Ma. Per eseguire la crittografia a conservazione del formato di JPEG 2000, la tecnica consiste nell'escludere il byte "0xFF" nella crittografia e nella decrittografia. Quindi un meccanismo di crittografia JPEG 2000 esegue l'aggiunta modulo-n con la cifratura a flusso; un altro meccanismo di crittografia JPEG 2000 esegue la tecnica della camminata in bicicletta con cifratura a blocchi.
Altre costruzioni FPE
Diversi costrutti FPE si basano sull'aggiunta dell'output di un cifrario standard, modulo n, ai dati da crittografare, con vari metodi di imparzialità del risultato. L'addizione modulo-n condivisa da molti dei costrutti è la soluzione immediatamente ovvia al problema FPE (quindi il suo utilizzo in un certo numero di casi), con le principali differenze nei meccanismi di imparzialità utilizzati.
La sezione 8 della FIPS 74, Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard , descrive un modo per utilizzare l'algoritmo di crittografia DES in modo da preservare il formato dei dati tramite addizione modulo-n seguita da un'operazione imparziale. Questo standard è stato ritirato il 19 maggio 2005, quindi la tecnica dovrebbe essere considerata obsoleta in termini di standard formale.
Un altro meccanismo iniziale per la crittografia a conservazione del formato era "Crittografia dei dati con un intervallo di valori ristretto" di Peter Gutmann che esegue di nuovo l'aggiunta modulo-n su qualsiasi cifrario con alcune modifiche per rendere uniforme il risultato, con la crittografia risultante forte quanto l'algoritmo di crittografia sottostante su cui si basa.
Il documento "Using Datatype-Preserving Encryption to Enhance Data Warehouse Security" di Michael Brightwell e Harry Smith descrive un modo per utilizzare l' algoritmo di crittografia DES in modo da preservare il formato del testo in chiaro. Questa tecnica non sembra applicare un passaggio imparziale come fanno le altre tecniche modulo-n a cui si fa riferimento qui.
Il documento "Format-Preserving Encryption" di Mihir Bellare e Thomas Ristenpart descrive l'utilizzo di reti Feistel "quasi bilanciate" per creare algoritmi FPE sicuri.
Il documento "Format Controlling Encryption Using Datatype Preserving Encryption" di Ulf Mattsson descrive altri modi per creare algoritmi FPE.
Un esempio di algoritmo FPE è FNR ( Flessibile Naor e Reingold ).
Accettazione degli algoritmi FPE da parte delle autorità di normazione
La pubblicazione speciale del NIST 800-38G, "Raccomandazione per le modalità operative della crittografia a blocchi: metodi per la crittografia con conservazione del formato" specifica due metodi: FF1 e FF3. I dettagli sulle proposte presentate per ciascuno possono essere trovati sul sito NIST Block Cipher Modes Development, comprese le informazioni sui brevetti e sui vettori di test. I valori campione sono disponibili sia per FF1 che per FF3.
- FF1 è FFX[Radix] "Modalità di crittografia basata su Feistel che preserva il formato" che è anche nei processi standard sotto ANSI X9 come X9.119 e X9.124. È stato presentato al NIST da Mihir Bellare dell'Università della California, San Diego, Phillip Rogaway dell'Università della California, Davis e Terence Spies di Voltage Security Inc. I vettori di prova sono forniti e parti di essi sono brevettate. (DRAFT SP 800-38G Rev 1) richiede che la dimensione minima del dominio dei dati da crittografare sia 1 milione (in precedenza 100).
- FF3 è BPS che prende il nome dagli autori. È stato presentato al NIST da Eric Brier, Thomas Peyrin e Jacques Stern di Ingenico, Francia. Gli autori hanno dichiarato al NIST che il loro algoritmo non è brevettato. Il prodotto CyberRes Voltage , sebbene affermi di possedere brevetti anche per la modalità BPS. Il 12 aprile 2017, il NIST ha concluso che FF3 "non è più adatto come metodo FPE generico" perché i ricercatori hanno riscontrato una vulnerabilità.
- FF3-1 (DRAFT SP 800-38G Rev 1) sostituisce FF3 e richiede che la dimensione minima del dominio dei dati da crittografare sia 1 milione (in precedenza 100).
Un'altra modalità è stata inclusa nella bozza della guida del NIST, ma è stata rimossa prima della pubblicazione finale.
- FF2 è lo schema VAES3 per FFX: un'aggiunta a "The FFX Mode of Operation for Preserving Encryption": una raccolta di parametri per stringhe di cifratura di radice arbitraria con operazione di sottochiave per allungare la vita della chiave di cifratura. È stato presentato al NIST da Joachim Vance di VeriFone Systems Inc. I vettori di test non sono forniti separatamente da FF1 e parti di esso sono brevettate. Gli autori hanno presentato un algoritmo modificato come DFF che è attivamente preso in considerazione dal NIST.
La Corea ha anche sviluppato uno standard FPE, FEA-1 e FEA-2.
implementazioni
Le implementazioni Open Source di FF1 e FF3 sono disponibili pubblicamente in linguaggio C , linguaggio Go , Java , Node.js , Python , C#/.Net e Rust
