En criptografía , el cifrado que preserva el formato ( FPE ), se refiere al cifrado de tal manera que la salida (el texto cifrado ) esté en el mismo formato que la entrada (el texto sin formato ). El significado de "formato" varía. Normalmente sólo se utilizan conjuntos finitos de caracteres; numérico, alfabético o alfanumérico. Por ejemplo:
Para tales dominios finitos, y para los propósitos de la discusión siguiente, el cifrado es equivalente a una permutación de N enteros {0,..., N −1 } donde N es el tamaño del dominio.
Una motivación para utilizar FPE proviene de los problemas asociados con la integración del cifrado en aplicaciones existentes, con modelos de datos bien definidos. Un ejemplo típico sería un número de tarjeta de crédito , como por ejemplo 1234567812345670(16 bytes de longitud, solo dígitos).
Agregar cifrado a este tipo de aplicaciones puede resultar complicado si se van a cambiar los modelos de datos, ya que normalmente implica cambiar los límites de longitud de los campos o los tipos de datos. Por ejemplo, la salida de un cifrado de bloque típico convertiría el número de tarjeta de crédito en un valor hexadecimal (p. ej. 0x96a45cbcf9c2a9425cde9e274948cb67, 34 bytes, dígitos hexadecimales) o Base64 (p. ej. lqRcvPnCqUJc3p4nSUjLZw==, 24 bytes, caracteres alfanuméricos y especiales), lo que interrumpirá cualquier aplicación existente que espere el crédito. El número de tarjeta será un número de 16 dígitos.
Aparte de los simples problemas de formato, al utilizar AES-128-CBC, este número de tarjeta de crédito puede cifrarse con el valor hexadecimal 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. Además de los problemas causados por la creación de caracteres no válidos y el aumento del tamaño de los datos, los datos cifrados utilizando el modo CBC de un algoritmo de cifrado también cambian su valor cuando se descifran y se cifran nuevamente. Esto sucede porque el valor inicial aleatorio que se utiliza para inicializar el algoritmo de cifrado y se incluye como parte del valor cifrado es diferente para cada operación de cifrado. Debido a esto, es imposible utilizar datos que hayan sido cifrados con el modo CBC como clave única para identificar una fila en una base de datos.
FPE intenta simplificar el proceso de transición preservando el formato y la longitud de los datos originales, permitiendo un reemplazo directo de valores de texto sin formato con sus textos cifrados en aplicaciones heredadas.
Aunque una permutación verdaderamente aleatoria es el cifrado FPE ideal, para dominios grandes no es factible pregenerar y recordar una permutación verdaderamente aleatoria. Entonces, el problema de FPE es generar una permutación pseudoaleatoria a partir de una clave secreta, de tal manera que el tiempo de cálculo para un solo valor sea pequeño (idealmente constante, pero lo más importante es menor que O(N) ).
Un cifrado de bloque de n bits técnicamente es un FPE en el conjunto {0, ..., 2 n -1 }. Si se necesita un FPE en uno de estos conjuntos de tamaño estándar (por ejemplo, n = 64 para DES y n = 128 para AES), se puede utilizar un cifrado de bloque del tamaño correcto.
Sin embargo, en el uso típico, un cifrado de bloque se utiliza en un modo de operación que le permite cifrar mensajes arbitrariamente largos y con un vector de inicialización como se analizó anteriormente. En este modo, un cifrado de bloque no es un FPE.
En la literatura criptográfica (consulte la mayoría de las referencias a continuación), la medida de un FPE "bueno" es si un atacante puede distinguir el FPE de una permutación verdaderamente aleatoria. Se postulan varios tipos de atacantes, dependiendo de si tienen acceso a oráculos o pares conocidos de texto cifrado/texto plano.
En la mayoría de los enfoques enumerados aquí, se utiliza un cifrado de bloque bien entendido (como AES ) como primitivo para reemplazar una función aleatoria ideal. Esto tiene la ventaja de que es fácil la incorporación de una clave secreta al algoritmo. Cuando se mencione AES en la siguiente discusión, cualquier otro buen cifrado de bloque también funcionaría.
La implementación de FPE con seguridad demostrablemente relacionada con la del cifrado de bloque subyacente se llevó a cabo por primera vez en un artículo de los criptógrafos John Black y Phillip Rogaway , [1] que describía tres formas de hacerlo. Demostraron que cada una de estas técnicas es tan segura como el cifrado de bloque que se utiliza para construirla. Esto significa que si se utiliza el algoritmo AES para crear un algoritmo FPE, entonces el algoritmo FPE resultante es tan seguro como AES porque un adversario capaz de derrotar al algoritmo FPE también puede derrotar al algoritmo AES. Por lo tanto, si AES es seguro, entonces los algoritmos FPE construidos a partir de él también lo son. En todo lo siguiente, E indica la operación de cifrado AES que se utiliza para construir un algoritmo FPE y F indica la operación de cifrado FPE.
Una forma sencilla de crear un algoritmo FPE en {0, ..., N -1} es asignar un peso pseudoaleatorio a cada número entero y luego ordenarlo por peso. Los pesos se definen aplicando un cifrado de bloque existente a cada número entero. Black y Rogaway llaman a esta técnica un "cifrado de prefijo" y demostraron que probablemente era tan bueno como el cifrado de bloque utilizado.
Por lo tanto, para crear un FPE en el dominio {0,1,2,3}, dada una clave K , aplique AES( K ) a cada número entero, dando, por ejemplo,
peso (0) = 0x56c644080098fc5570f2b329323dbf62 peso (1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 peso (2) = 0x47d2e1bf72264fa01fb274465e56ba20 peso (3) = 0x07 7de40941c93774857961a8a772650d
Ordenar [0,1,2,3] por peso da [3,1,2,0], por lo que el cifrado es
F (0) = 3 F (1) = 1 F (2) = 2 F (3) = 0
Este método sólo es útil para valores pequeños de N. Para valores mayores, el tamaño de la tabla de búsqueda y la cantidad requerida de cifrados para inicializar la tabla son demasiado grandes para ser prácticos.
Si hay un conjunto M de valores permitidos dentro del dominio de una permutación pseudoaleatoria P (por ejemplo, P puede ser un cifrado de bloque como AES), se puede crear un algoritmo FPE a partir del cifrado de bloque aplicando repetidamente el cifrado de bloque hasta que el resultado sea uno de los valores permitidos (dentro de M ).
CycleWalkingFPE(x) { si P (x) es un elemento de M entonces devuelve P (x) en caso contrario devuelve CycleWalkingFPE( P (x))}Se garantiza que la recursividad terminará. (Debido a que P es uno a uno y el dominio es finito, la aplicación repetida de P forma un ciclo, por lo que comenzando con un punto en M el ciclo eventualmente terminará en M ).
Esto tiene la ventaja de que los elementos de M no tienen que asignarse a una secuencia consecutiva {0,..., N -1} de números enteros. Tiene la desventaja, cuando M es mucho más pequeño que el dominio de P , de que podrían ser necesarias demasiadas iteraciones para cada operación. Si P es un cifrado de bloque de un tamaño fijo, como AES, esto supone una restricción severa en los tamaños de M para los cuales este método es eficiente.
Por ejemplo, es posible que una aplicación desee cifrar valores de 100 bits con AES de manera que se cree otro valor de 100 bits. Con esta técnica, el cifrado AES-128-ECB se puede aplicar hasta alcanzar un valor en el que todos sus 28 bits más altos estén establecidos en 0, lo que tardará un promedio de 228 iteraciones en ocurrir.
También es posible crear un algoritmo FPE utilizando una red Feistel . Una red Feistel necesita una fuente de valores pseudoaleatorios para las subclaves de cada ronda, y la salida del algoritmo AES se puede utilizar como estos valores pseudoaleatorios. Cuando se hace esto, la construcción Feistel resultante es buena si se utilizan suficientes rondas. [2]
Una forma de implementar un algoritmo FPE usando AES y una red Feistel es usar tantos bits de salida AES como sean necesarios para igualar la longitud de las mitades izquierda o derecha de la red Feistel. Si se necesita un valor de 24 bits como subclave, por ejemplo, es posible utilizar los 24 bits más bajos de la salida de AES para este valor.
Es posible que esto no dé como resultado que la salida de la red Feistel conserve el formato de la entrada, pero es posible iterar la red Feistel de la misma manera que lo hace la técnica de caminar en bicicleta para garantizar que se pueda conservar el formato. Debido a que es posible ajustar el tamaño de las entradas a una red Feistel, es posible hacer muy probable que esta iteración finalice muy rápidamente en promedio. En el caso de los números de tarjetas de crédito, por ejemplo, hay 10 15 posibles números de tarjetas de crédito de 16 dígitos (teniendo en cuenta el dígito de control redundante ), y debido a que 10 15 ≈ 2 49,8 , se utiliza una red Feistel de 50 bits de ancho junto con Caminar en bicicleta creará un algoritmo FPE que se cifra con bastante rapidez en promedio.
Una baraja de Thorp es como una baraja de cartas idealizada o, equivalentemente, un cifrado Feistel con máximo desequilibrio en el que un lado es un solo bit. Es más fácil demostrar la seguridad de los cifrados Feistel desequilibrados que de los equilibrados. [3]
Para tamaños de dominio que son una potencia de dos y un cifrado de bloque existente con un tamaño de bloque más pequeño, se puede crear un nuevo cifrado usando el modo VIL como lo describe Bellare, Rogaway. [4]
Hasty Pudding Cipher utiliza construcciones personalizadas (que no dependen de los cifrados de bloque existentes como primitivos) para cifrar dominios pequeños finitos arbitrarios.
El modo FFSEM de AES (especificación [5] ) que ha sido aceptado para su consideración por NIST utiliza la construcción de red Feistel de Black y Rogaway descrita anteriormente, con AES para la función redonda, con una ligera modificación: se usa una sola clave y se modificado ligeramente para cada ronda.
En febrero de 2010, FFSEM ha sido reemplazado por el modo FFX escrito por Mihir Bellare , Phillip Rogaway y Terence Spies. (especificación, [6] [7] Desarrollo de modos de cifrado de bloques NIST, 2010).
En el estándar JPEG 2000 , los códigos de marcador (en el rango de 0xFF90 a 0xFFFF) no deben aparecer en texto sin formato ni en texto cifrado. La técnica simple modular-0xFF90 no se puede aplicar para resolver el problema de cifrado JPEG 2000. Por ejemplo, las palabras de texto cifrado 0x23FF y 0x9832 son válidas, pero su combinación 0x23FF9832 deja de ser válida ya que introduce el código de marcador 0xFF98. De manera similar, la técnica simple de caminar en bicicleta no se puede aplicar para resolver el problema de cifrado JPEG2000, ya que dos bloques de texto cifrado válidos pueden dar un texto cifrado no válido cuando se combinan. Por ejemplo, si el primer bloque de texto cifrado termina con los bytes "...30FF" y el segundo bloque de texto cifrado comienza con los bytes "9832...", entonces el código de marcador "0xFF98" aparecerá en el texto cifrado.
En el artículo "Esquemas de cifrado eficientes y seguros para JPEG2000" [8] de Hongjun Wu y Di Ma se ofrecen dos mecanismos para el cifrado que preserva el formato de JPEG 2000 . Para realizar el cifrado que preserva el formato de JPEG 2000, la técnica consiste en excluir el byte "0xFF" en el cifrado y descifrado. Luego, un mecanismo de cifrado JPEG 2000 realiza una suma módulo-n con cifrado de flujo; otro mecanismo de cifrado JPEG 2000 realiza la técnica de caminar en bicicleta con cifrado de bloques.
Varias construcciones de FPE se basan en agregar la salida de un cifrado estándar, módulo n, a los datos que se van a cifrar, con varios métodos para no sesgar el resultado. La adición de módulo-n compartida por muchas de las construcciones es la solución inmediatamente obvia al problema de FPE (de ahí su uso en varios casos), siendo la principal diferencia los mecanismos insesgados utilizados.
La sección 8 de FIPS 74, Publicación de estándares federales de procesamiento de información de 1981, Directrices para implementar y utilizar el estándar de cifrado de datos NBS , [9] describe una forma de utilizar el algoritmo de cifrado DES de una manera que preserve el formato de los datos a través de módulo-n. suma seguida de una operación insesgada. Esta norma fue retirada el 19 de mayo de 2005, por lo que la técnica debe considerarse obsoleta en cuanto a ser una norma formal.
Otro mecanismo temprano para el cifrado que preserva el formato fue "Cifrar datos con un rango restringido de valores" de Peter Gutmann [10], que nuevamente realiza una suma módulo-n en cualquier cifrado con algunos ajustes para que el resultado sea uniforme, siendo el cifrado resultante tan fuerte como el algoritmo de cifrado subyacente en el que se basa.
El artículo "Using Datatype-Preserving Encryption to Enhance Data Warehouse Security" [11] de Michael Brightwell y Harry Smith describe una forma de utilizar el algoritmo de cifrado DES de manera que preserve el formato del texto sin formato. Esta técnica no parece aplicar un paso imparcial como lo hacen las otras técnicas de módulo n a las que se hace referencia aquí.
El artículo "Format-Preserving Encryption" [12] de Mihir Bellare y Thomas Ristenpart describe el uso de redes Feistel "casi equilibradas" para crear algoritmos FPE seguros.
El artículo "Control de formato de cifrado mediante cifrado de preservación del tipo de datos" [13] de Ulf Mattsson describe otras formas de crear algoritmos FPE.
Un ejemplo de algoritmo FPE es FNR ( Flexible Naor y Reingold ). [14]
La publicación especial del NIST 800-38G, "Recomendación para modos de operación de cifrado en bloque: métodos para el cifrado con preservación de formato" [15] especifica dos métodos: FF1 y FF3. Los detalles sobre las propuestas presentadas para cada uno se pueden encontrar en el sitio de desarrollo de modos de cifrado de bloques del NIST, [16] incluida información sobre patentes y vectores de prueba. Los valores de muestra están disponibles tanto para FF1 como para FF3. [17]
Se incluyó otro modo en el borrador de la guía del NIST, pero se eliminó antes de la publicación final.
Corea también ha desarrollado un estándar FPE, FEA-1 y FEA-2.
Las implementaciones de código abierto de FF1 y FF3 están disponibles públicamente en lenguaje C, lenguaje Go, Java, Node.js, Python, C#/.Net y Rust.