Hispanopedia WikiEn criptografía , el cifrado que preserva el formato ( FPE , por sus siglas en inglés) se refiere a cifrar de tal manera que la salida (el texto cifrado ) tenga el mismo formato que la entrada (el texto plano ). El significado de "formato" varía. Normalmente, solo se utilizan conjuntos finitos de caracteres: numéricos, alfabéticos o alfanuméricos. Por ejemplo:
- Encriptar un número de tarjeta de crédito de 16 dígitos de manera que el texto cifrado sea otro número de 16 dígitos.
- Encriptar una palabra en inglés de manera que el texto cifrado sea otra palabra en inglés.
- Encriptar un número de n bits de forma que el texto cifrado sea otro número de n bits (esta es la definición de un cifrado de bloques de n bits).
Para dominios finitos como estos, y para los fines de la discusión que sigue, el cifrado es equivalente a una permutación de N enteros {0, ..., N −1 } donde N es el tamaño del dominio.
Motivación
Longitudes o formatos de campo restringidos
Una de las motivaciones para usar 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 este tipo de aplicaciones puede resultar complicado si se modifican 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 (p. ej 0x96a45cbcf9c2a9425cde9e274948cb67., 34 bytes, dígitos hexadecimales) o Base64lqRcvPnCqUJc3p4nSUjLZw== (p. ej ., 24 bytes, caracteres alfanuméricos y especiales), lo que inutilizaría cualquier aplicación existente que espere que el número de tarjeta de crédito sea de 16 dígitos.
Además de los problemas de formato simples, al usar AES-128-CBC, este número de tarjeta de crédito podría cifrarse en su valor hexadecimal 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. Sumado a los problemas causados por la creación de caracteres no válidos y el aumento del tamaño de los datos, los datos cifrados con el modo CBC de un algoritmo de cifrado también cambian su valor al descifrarse y volver a cifrarse. Esto sucede porque el valor de semilla aleatoria que se usa para inicializar el algoritmo de cifrado y que se incluye como parte del valor cifrado es diferente en cada operación de cifrado. Por lo tanto, es imposible usar datos 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 conservando el formato y la longitud de los datos originales, lo que permite sustituir directamente los valores en texto plano por sus textos cifrados en las aplicaciones heredadas.
Comparación con permutaciones verdaderamente aleatorias
Si bien una permutación verdaderamente aleatoria es el cifrado FPE ideal, para dominios grandes es inviable pregenerar y recordar una permutación verdaderamente aleatoria. Por lo tanto, el problema de FPE consiste en 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 que sea menor que O(N) ).
Comparación con cifrados de bloques
Técnicamente, un cifrado de bloques de n bits es una FPE en el conjunto {0, ..., 2 n -1 }. Si se necesita una 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 bloques del tamaño adecuado.
Sin embargo, en su uso habitual, un cifrador de bloques se emplea en un modo de operación que le permite cifrar mensajes de longitud arbitraria, con un vector de inicialización como se mencionó anteriormente. En este modo, un cifrador de bloques no es un FPE (Frameful Expression Process).
Definición de seguridad
En la literatura criptográfica (véanse la mayoría de las referencias a continuación), la medida de una FPE "buena" es si un atacante puede distinguirla de una permutación verdaderamente aleatoria. Se postulan varios tipos de atacantes, dependiendo de si tienen acceso a oráculos o a pares conocidos de texto cifrado/texto plano.
Algoritmos
En la mayoría de los métodos aquí descritos, se utiliza un cifrado de bloques conocido (como AES ) como primitiva para reemplazar una función aleatoria ideal. Esto tiene la ventaja de que la incorporación de una clave secreta al algoritmo es sencilla. Cuando se menciona AES en la siguiente discusión, cualquier otro cifrado de bloques adecuado también funcionaría.
Las construcciones FPE de Black y Rogaway
La implementación de FPE con seguridad demostrablemente relacionada con la del cifrado de bloques subyacente fue abordada por primera vez en un artículo de los criptógrafos John Black y Phillip Rogaway , [ 1 ] que describió tres maneras de hacerlo. Demostraron que cada una de estas técnicas es tan segura como el cifrado de bloques utilizado 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, ya que un adversario capaz de derrotar el algoritmo FPE también puede derrotar el 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 que sigue, 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.
FPE de un cifrado de prefijo
Una forma sencilla de crear un algoritmo FPE sobre {0, ..., N -1} consiste en asignar un peso pseudoaleatorio a cada entero y, a continuación, ordenarlos según su peso. Los pesos se definen aplicando un cifrado de bloques existente a cada entero. Black y Rogaway denominan a esta técnica "cifrado de prefijo" y demostraron que era tan eficaz como el cifrado de bloques utilizado.
Por lo tanto, para crear un FPE en el dominio {0,1,2,3}, dada una clave K, aplique AES( K ) a cada entero, obteniendo, 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 cifrado 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 mayores, el tamaño de la tabla de búsqueda y la cantidad de cifrados necesarios para inicializarla se vuelven demasiado grandes para ser prácticos.
FPE de andar en bicicleta
Si existe un conjunto M de valores permitidos dentro del dominio de una permutación pseudoaleatoria P (por ejemplo, P puede ser un cifrado de bloques como AES), se puede crear un algoritmo FPE a partir del cifrado de bloques aplicando repetidamente el cifrado de bloques 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á. (Como P es biyectiva 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 terminará finalmente en M ).
Esto tiene la ventaja de que los elementos de M no necesitan ser mapeados a una secuencia consecutiva {0,..., N -1} de enteros. Sin embargo, cuando M es mucho menor que el dominio de P , puede requerir demasiadas iteraciones para cada operación. Si P es un cifrador de bloques de tamaño fijo, como AES, esto supone una restricción importante en los tamaños de M para los que este método resulta eficiente.
Por ejemplo, una aplicación podría querer cifrar valores de 100 bits con AES de forma que se genere otro valor de 100 bits. Con esta técnica, se puede aplicar el cifrado AES-128-ECB hasta alcanzar un valor cuyos 28 bits más significativos estén a 0, lo que requerirá un promedio de 2²⁸ iteraciones .
FPE de una red Feistel
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 puede utilizarse 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 consiste en usar tantos bits de la 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 usar los 24 bits menos significativos de la salida AES para este valor.
Esto puede no resultar en 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 recorrido cíclico para asegurar 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 (teniendo en cuenta el dígito de control redundante ), y como 10 15 ≈ 2 49.8 , usar una red Feistel de 50 bits de ancho junto con el recorrido cíclico creará un algoritmo FPE que cifra bastante rápido en promedio.
El barajado de Thorp
Una baraja de Thorp es como una baraja de cartas idealizada, o equivalentemente un cifrado Feistel máximamente desequilibrado donde un lado es un solo bit. Es más fácil demostrar la seguridad de los cifrados Feistel desequilibrados que de los equilibrados. [ 3 ]
Modo VIL
Para tamaños de dominio que son potencia de dos, y un cifrado de bloques existente con un tamaño de bloque menor, se puede crear un nuevo cifrado utilizando el modo VIL como lo describen Bellare y Rogaway. [ 4 ]
Cifrado de pudín apresurado
El cifrado Hasty Pudding utiliza construcciones personalizadas (que no dependen de cifrados de bloques existentes como primitivas) para cifrar dominios pequeños y finitos arbitrarios.
El modo FFSEM/FFX de AES
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 clave y se ajusta ligeramente para cada ronda.
A partir de febrero de 2010, FFSEM fue reemplazado por el modo FFX escrito por Mihir Bellare , Phillip Rogaway y Terence Spies. (especificación, [ 6 ] [ 7 ] Desarrollo de modos de cifrado por bloques del NIST , 2010).
FPE para cifrado JPEG 2000
En el estándar JPEG 2000 , los códigos de marcador (en el rango de 0xFF90 a 0xFFFF) no deben aparecer en el texto plano ni en el texto cifrado. La técnica modular simple 0xFF90 no se puede aplicar para resolver el problema de cifrado de JPEG 2000. Por ejemplo, las palabras de texto cifrado 0x23FF y 0x9832 son válidas, pero su combinación 0x23FF9832 se vuelve inválida, ya que introduce el código de marcador 0xFF98. De manera similar, la técnica de ciclo simple no se puede aplicar para resolver el problema de cifrado de JPEG 2000, ya que dos bloques de texto cifrado válidos pueden dar como resultado un texto cifrado inválido al combinarse. 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 "Efficient and Secure Encryption Schemes for JPEG2000" [ 8 ] de Hongjun Wu y Di Ma se presentan 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" durante el cifrado y el descifrado. Un mecanismo de cifrado de JPEG 2000 realiza una suma módulo n con cifrado de flujo ; otro mecanismo de cifrado de JPEG 2000 realiza la técnica de ciclo de pasos con cifrado de bloques.
Otras construcciones FPE
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, utilizando diversos métodos para corregir el sesgo del resultado. La suma módulo n, común a muchas de estas construcciones, es la solución más evidente al problema FPE (de ahí su uso en varios casos), siendo las principales diferencias los mecanismos de corrección empleados.
La sección 8 de la norma FIPS 74, Publicación de 1981 de las Normas Federales de Procesamiento de la Información, Directrices para la Implementación y el Uso del Estándar de Cifrado de Datos del NBS , [ 9 ] describe una forma de utilizar el algoritmo de cifrado DES que preserva el formato de los datos mediante la suma módulo n seguida de una operación de corrección de sesgos. Esta norma fue retirada el 19 de mayo de 2005, por lo que la técnica debe considerarse obsoleta como norma formal.
Otro mecanismo temprano para el cifrado que preserva el formato fue el de Peter Gutmann , "Encrypting data with a restricted range of values" [ 10 ], que nuevamente realiza una suma 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 «Uso del cifrado que preserva el tipo de datos para mejorar la seguridad de los almacenes de datos » [ 11 ], de Michael Brightwell y Harry Smith, describe una forma de utilizar el algoritmo de cifrado DES que preserva el formato del texto plano. Esta técnica no parece aplicar un paso de eliminación de sesgos, a diferencia de 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 "Format Controlling Encryption Using Datatype Preserving Encryption" [ 13 ] de Ulf Mattsson describe otras formas de crear algoritmos FPE.
Un ejemplo de algoritmo FPE es FNR ( Flexible Naor y Reingold ). [ 14 ]
Aceptación de los algoritmos FPE por parte de las autoridades de normalización.
La publicación especial 800-38G del NIST, «Recomendación para modos de operación de cifrado por bloques: métodos para 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 por bloques del NIST [ 16 ] , incluyendo información sobre patentes y vectores de prueba. Hay valores de muestra disponibles para FF1 y FF3 [ 17 ] .
- FF1 es FFX[Radix] "Modo de cifrado basado en Feistel que preserva el formato", que también se encuentra en procesos de estandarización bajo ANSI X9 como X9.119 y X9.124. Fue presentado al NIST por Mihir Bellare de la Universidad de California, San Diego, Phillip Rogaway de la Universidad de California, Davis, y Terence Spies de Voltage Security Inc. Se proporcionan vectores de prueba y partes del mismo están patentadas. (BORRADOR SP 800-38G Rev 1) [ 18 ] requiere que el tamaño mínimo del dominio de los datos que se están cifrando sea de 1 millón (anteriormente 100).
- FF3 es BPS nombrado en honor a sus autores. Fue presentado al NIST por Éric Brier , Thomas Peyrin y Jacques Stern de Ingenico en Francia. Los autores declararon al NIST que su algoritmo no está patentado. [ 19 ] El producto CyberRes Voltage , aunque afirma poseer patentes también para el modo BPS. [ 20 ] [ 21 ] El 12 de abril de 2017, el NIST concluyó que FF3 "ya no es adecuado como método FPE de propósito general" porque los investigadores encontraron una vulnerabilidad. [ 22 ]
- FF3-1 (BORRADOR SP 800-38G Rev 1) [ 18 ] reemplaza a FF3 y requiere que el tamaño mínimo del dominio de los datos que se cifran sea de 1 millón (anteriormente 100). El 3 de febrero de 2025, el NIST retiró FF3 por completo en la segunda revisión del borrador (BORRADOR SP 800-38G Rev 2) declarando: "Un ataque de Beyne [2021] contra FF3 y FF3-1 provocó la eliminación de FF3". [ 23 ]
En el borrador de la guía del NIST se incluyó otro modo de funcionamiento, pero se eliminó antes de su publicación final.
- FF2 es un esquema VAES3 para FFX: un apéndice a "El modo de operación FFX para preservar el cifrado": una colección de parámetros para cifrar cadenas de base arbitraria con operación de subclave para extender la vida útil de la clave de cifrado. Fue presentado al NIST por Joachim Vance de VeriFone Systems Inc. Los vectores de prueba no se proporcionan por separado de FF1 y partes de este están patentadas. Los autores han presentado un algoritmo modificado como DFF [ 24 ] que está siendo evaluado activamente por el NIST.
Corea también ha desarrollado un estándar FPE, FEA-1 y FEA-2.
Implementaciones
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 .
Referencias
- ↑ John Black y Philip Rogaway, Cifrados con dominios arbitrarios, Actas de RSA-CT, 2002, págs. 114–130. http://citeseer.ist.psu.edu/old/black00ciphers.html ( http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf )
- ↑ Jacques Patarin, Luby-Rackoff: 7 Rounds Are Enough for 2 n(1-epsilon) Security, Proceedings of CRYPTO 2003, Lecture Notes in Computer Science, Volumen 2729, Oct 2003, pp. 513–529. https://www.iacr.org/archive/crypto2003/27290510/27290510.pdf ; también Jaques Patrin: Security of Random Feistel Schemes with 5 or more Rounds. https://www.iacr.org/archive/crypto2004/31520105/Version%20courte%20Format%20Springer.pdf
- ↑ Morris, Ben; Rogaway, Phillip; Stegers, Till (2009), "Cómo cifrar mensajes en un dominio pequeño" (PDF) , CRYPTO
- ↑ Bellare, Mihir; Rogaway, Phillip (1999), Sobre la construcción de cifrados de longitud de entrada variable (PDF)
- ↑ Terence Spies, Feistel, Modo de cifrado de conjunto finito http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf
- ↑ Mihir Bellare, Phillip Rogaway, Terence Spies: El modo de operación FFX para el cifrado que preserva el formato (PDF) , 2010
- ↑ Mihir Bellare, Phillip Rogaway, Terence Spies: Anexo a "El modo de operación FFX para el cifrado que preserva el formato" (PDF) , 2010
- ↑ Hongjun Wu, Di Ma, "Esquemas de cifrado eficientes y seguros para JPEG2000", Conferencia Internacional sobre Acústica, Habla y Procesamiento de Señales (ICASSP 2004). MSP-L 1.6, Vol. V, págs. 869–872. http://www3.ntu.edu.sg/home/wuhj/research/publications/2004_ICASSP_JPEG2000.pdf Archivado el 19 de febrero de 2018 en Wayback Machine
- ↑ FIPS 74, Publicación de 1981 de las Normas Federales de Procesamiento de la Información: Directrices para la implementación y el uso del Estándar de Cifrado de Datos del NBS http://www.itl.nist.gov/fipspubs/fip74.htm Archivado el 3 de enero de 2014 en Wayback Machine
- ↑ Peter Gutmann, "Encrypting data with a restricted range of values", 23 de enero de 1997, https://groups.google.com/group/sci.crypt/browse_thread/thread/6caf26496782e359/e576d7196b6cdb48
- ↑ Michael Brightwell y Harry Smith, "Uso del cifrado que preserva el tipo de datos para mejorar la seguridad de los almacenes de datos", Actas de la Conferencia Nacional de Seguridad de Sistemas de Información de 1997 https://portfolio.du.edu/portfolio/getportfoliofile?uid=135556 Archivado el 19 de julio de 2011 en Wayback Machine
- ↑ Mihir Bellare y Thomas Ristenpart, Cifrado que preserva el formato http://eprint.iacr.org/2009/251
- ↑ Ulf Mattsson, Cifrado con control de formato mediante cifrado que preserva el tipo de datos http://eprint.iacr.org/2009/257
- ^ Sashank Dara, Scott Fluhrer. «Naor flexibles y Reingold» . Cisco Systems Inc.
- ↑ Dworkin, Morris (2016), Publicación especial 800-38G del NIST, Recomendación para los modos de operación de cifrado por bloques: métodos para el cifrado que preserva el formato , doi : 10.6028/NIST.SP.800-38G
- ↑ Desarrollo de modos de cifrado por bloques del NIST , 4 de enero de 2017
- ↑ Ejemplos de algoritmos del kit de herramientas criptográficas del NIST , 29 de diciembre de 2016
- 1 2 "SP 800-38G Rev. 1 (BORRADOR) Recomendación para modos de operación de cifrado por bloques: métodos para cifrado que preserva el formato" . NIST . Febrero de 2019. Recuperado el 1 de abril de 2019 .
- ↑ Declaración de patente de los autores de BPS (PDF) , 4 de enero de 2017
- ↑ Reivindicaciones de patentes de HPE Voltage
- ↑ Carta de garantía revisada para las reivindicaciones de patente esenciales Modo de operación FFX para el cifrado que preserva el formato (PDF)
- ↑ "Criptoanálisis reciente de FF3" . NIST . 12 de abril de 2017. Consultado el 5 de mayo de 2020 .
- ↑ "NIST SP 800-38G Rev. 1" . NIST . 3 de febrero de 2025. Consultado el 19 de febrero de 2025 .
- ↑ FF2 Anexo DFF (PDF)
- Cifrados de bloques
- Criptografía
