En criptografía , el cifrado con preservación de formato ( FPE ) se refiere a cifrar de tal manera que la salida (el texto cifrado ) tenga el mismo formato que la entrada (el texto sin formato ). El significado de "formato" varía. Normalmente, solo se utilizan conjuntos finitos de caracteres: numéricos, alfabéticos o alfanuméricos. Por ejemplo:
Para tales dominios finitos, y para los fines de la discusión a continuación, el cifrado es equivalente a una permutación de N números enteros {0, ..., N −1 } donde N es el tamaño del dominio.
Una de las razones 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 1234567812345670(16 bytes de longitud, solo dígitos).
Agregar cifrado a dichas aplicaciones puede resultar complicado si se deben modificar los modelos de datos, ya que generalmente implica cambiar los límites de longitud de los campos o los tipos de datos. Por ejemplo, la salida de un cifrado de bloques típico convertiría el número de tarjeta de crédito en un valor hexadecimal (por ejemplo 0x96a45cbcf9c2a9425cde9e274948cb67, 34 bytes, dígitos hexadecimales) o Base64 (por ejemplo lqRcvPnCqUJc3p4nSUjLZw==, 24 bytes, caracteres alfanuméricos y especiales), lo que interrumpiría cualquier aplicación existente que espere que el número de tarjeta de crédito sea un número de 16 dígitos.
Aparte de los problemas de formato simples, al usar AES-128-CBC, este número de tarjeta de crédito podría encriptarse al 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 encriptados usando el modo CBC de un algoritmo de encriptación también cambian su valor cuando se desencriptan y se encriptan nuevamente. Esto sucede porque el valor de semilla aleatorio que se usa para inicializar el algoritmo de encriptación y se incluye como parte del valor encriptado es diferente para cada operación de encriptación. Debido a esto, es imposible usar datos que han sido encriptados con el modo CBC como una 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, lo que permite un reemplazo directo de los valores de texto simple con sus textos cifrados en aplicaciones heredadas.
Aunque una permutación verdaderamente aleatoria es el cifrado FPE ideal, para dominios grandes no es factible generar previamente y recordar una permutación verdaderamente aleatoria. Por lo tanto, 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 único valor sea pequeño (idealmente constante, pero lo más importante es que sea menor que O(N) ).
Un cifrador de bloque de n bits es técnicamente 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 cifrador de bloque del tamaño adecuado.
Sin embargo, en el uso habitual, un cifrador de bloques se utiliza en un modo de funcionamiento que le permite cifrar mensajes de longitud arbitraria y con un vector de inicialización como el que se ha explicado anteriormente. En este modo, un cifrador de bloques no es un FPE.
En la literatura criptográfica (ver 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 de texto cifrado/texto sin formato conocidos.
En la mayoría de los enfoques que se enumeran aquí, se utiliza un cifrador de bloques bien entendido (como AES ) como primitivo para reemplazar una función aleatoria ideal. Esto tiene la ventaja de que es fácil incorporar una clave secreta al algoritmo. Cuando se menciona AES en la siguiente discusión, cualquier otro cifrador de bloques bueno también funcionaría.
La implementación de FPE con una seguridad demostrablemente relacionada con la del cifrado de bloque subyacente fue abordada 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 son seguros. En todos los siguientes, E denota la operación de cifrado AES que se utiliza para construir un algoritmo FPE y F denota 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 entero y luego ordenar por peso. Los pesos se definen aplicando un cifrado de bloque existente a cada entero. Black y Rogaway denominan a esta técnica "cifrado de prefijo" y demostraron que probablemente era tan buena como el cifrado de bloque utilizado.
Así, para crear una FPE en el dominio {0,1,2,3}, dada una clave K, aplique AES( K ) a cada entero, dando, por ejemplo,
peso (0) = 0x56c644080098fc5570f2b329323dbf62 peso (1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 peso (2) = 0x47d2e1bf72264fa01fb274465e56ba20 peso (3) = 0x077de40941c93774857961a8a772650d
Ordenar [0,1,2,3] por peso da [3,1,2,0], por lo que el código es
F (0) = 3 F (1) = 1 F (2) = 2 F (3) = 0
Este método solo es útil para valores pequeños de N. Para valores más grandes, el tamaño de la tabla de búsqueda y la cantidad de cifrados necesarios para inicializar la tabla se vuelven 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) de lo contrario devuelve CycleWalkingFPE( P (x))}Se garantiza que la recursión 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 ser mapeados a una secuencia consecutiva {0,..., N -1} de números enteros. Tiene la desventaja de que, cuando M es mucho más pequeño que el dominio de P , pueden ser necesarias demasiadas iteraciones para cada operación. Si P es un cifrador de bloque de un tamaño fijo, como AES, esto es una restricción severa en los tamaños de M para los cuales este método es eficiente.
Por ejemplo, una aplicación puede querer cifrar valores de 100 bits con AES de forma que se cree otro valor de 100 bits. Con esta técnica, se puede aplicar el cifrado AES-128-ECB hasta que se alcance un valor que tenga todos sus 28 bits más altos configurados en 0, lo que llevará un promedio de 2 28 iteraciones para que suceda.
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 utilizando AES y una red Feistel es utilizar tantos bits de salida de 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.
Esto puede no resultar en que la salida de la red Feistel preserve 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 ciclo para garantizar que se pueda preservar el formato. Debido a que es posible ajustar el tamaño de las entradas a una red Feistel, es posible hacer que sea muy probable que esta iteración termine 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 (tomando en cuenta el dígito de control redundante ), y debido a que 10 15 ≈ 2 49.8 , el uso de una red Feistel de 50 bits de ancho junto con caminar en ciclo creará un algoritmo FPE que encripta bastante rápido en promedio.
Una mezcla de Thorp es como una mezcla idealizada de cartas o, equivalentemente, un cifrado Feistel desequilibrado al máximo, 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 utilizando el modo VIL como lo describen Bellare, Rogaway. [4]
El cifrado Hasty Pudding utiliza construcciones personalizadas (que no dependen de 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 de ronda, con una ligera modificación: se utiliza una sola tecla y se modifica ligeramente para cada ronda.
A partir de 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 del NIST, 2010)).
En el estándar JPEG 2000 , los códigos de marcador (en el rango de 0xFF90 a 0xFFFF) no deben aparecer en el texto simple ni en el texto cifrado. La técnica modular simple 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 porque 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 porque 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ía en el texto cifrado.
En el artículo "Esquemas de cifrado seguros y eficientes para JPEG2000" [8] de Hongjun Wu y Di Ma se dieron 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. A continuación, un mecanismo de cifrado JPEG 2000 realiza la adición módulo-n con cifrado de flujo; otro mecanismo de cifrado JPEG 2000 realiza la técnica de recorrido cíclico con cifrado de bloque.
Varias construcciones FPE se basan en sumar la salida de un cifrado estándar, módulo n, a los datos que se van a cifrar, con varios métodos para desviar el resultado. La suma módulo n que comparten muchas de las construcciones es la solución obvia al problema de FPE (de ahí su uso en varios casos), y las principales diferencias son los mecanismos de desviar el resultado utilizados.
La Sección 8 de la FIPS 74, Publicación de Normas Federales de Procesamiento de Información de 1981, Pautas para la Implementación y Uso del Estándar de Cifrado de Datos NBS , [9] describe una manera de utilizar el algoritmo de cifrado DES de una manera que preserva el formato de los datos a través de una adición módulo-n seguida de una operación de imparcialidad. Esta norma fue retirada el 19 de mayo de 2005, por lo que la técnica debe considerarse obsoleta en términos de ser una norma formal.
Otro mecanismo temprano para el cifrado que preserva el formato fue "Cifrado de datos con un rango restringido de valores" de Peter Gutmann [10], que nuevamente realiza una adición módulo n en cualquier cifrado con algunos ajustes para hacer 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 forma que se preserve el formato del texto sin formato. Esta técnica no parece aplicar un paso de imparcialidad 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 del cifrado mediante cifrado que preserva el 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 800-38G del NIST, "Recomendación para los modos de operación de cifrado en bloque: métodos para el cifrado que preserva el 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 en bloque del NIST, [16] incluyendo información sobre patentes y vectores de prueba. Hay valores de muestra 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.