Cifrado que conserva el formato - Format-preserving encryption

En criptografía , el cifrado que conserva el formato ( FPE ) se refiere al cifrado de tal manera que la salida (el texto cifrado ) tiene 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érico, alfabético o alfanumérico. Por ejemplo:

  • Cifrar un número de tarjeta de crédito de 16 dígitos para que el texto cifrado sea otro número de 16 dígitos.
  • Cifrar una palabra en inglés para que el texto cifrado sea otra palabra en inglés.
  • Cifrar un número de n bits para que el texto cifrado sea otro número de n bits (esta es la definición de un cifrado en bloque de n bits).

Para tales dominios finitos, y para los propósitos de la discusión a continuación, 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 motivación 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 tales aplicaciones puede ser un desafío si se van a cambiar los modelos de datos, ya que generalmente implica cambiar los límites de longitud de campo o los tipos de datos. Por ejemplo, la salida de un cifrado de bloque típico convertiría el número de la tarjeta de crédito en un valor hexadecimal (p 0x96a45cbcf9c2a9425cde9e274948cb67. Ej. , 34 bytes, dígitos hexadecimales) o un valor Base64 (p lqRcvPnCqUJc3p4nSUjLZw==. Ej. , 24 bytes, caracteres alfanuméricos y especiales), lo que romperá cualquier aplicación existente que espere el crédito. El número de tarjeta debe ser 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 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 mediante el modo CBC de un algoritmo de cifrado también cambian su valor cuando se descifran y cifran de nuevo. Esto sucede porque el valor de semilla 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 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, lo que permite un reemplazo directo de los valores de texto sin formato con sus textos cifrados en aplicaciones heredadas.

Comparación con permutaciones verdaderamente aleatorias

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. 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, más pequeño que O (N) ).

Comparación con cifrados en bloque

Un n de bloques de cifrado bits técnicamente es un FPE en el conjunto {0, ..., 2 n -1 }. Si es necesario un FPE en uno de estos conjuntos de tamaño estándar (por ejemplo, n = 64 para DES y n = 128 para AES) un cifrado de bloques del tamaño adecuado puede ser utilizado.

Sin embargo, en el uso típico, se usa un cifrado de bloque en un modo de operación que le permite cifrar mensajes arbitrariamente largos y con un vector de inicialización como se discutió anteriormente. En este modo, un cifrado de bloque no es un FPE.

Definición de seguridad

En la literatura criptográfica (ver la mayoría de las referencias a continuación), la medida de un "buen" FPE 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.

Algoritmos

En la mayoría de los enfoques enumerados aquí, se utiliza un cifrado de bloque bien entendido (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 fácil. Donde se menciona AES en la siguiente discusión, cualquier otro buen cifrado de bloques funcionaría también.

Las construcciones FPE de Black y Rogaway

La implementación de FPE con seguridad probablemente relacionada con la del cifrado de bloques subyacente fue realizada por primera vez en un documento por los criptógrafos John Black y Phillip Rogaway , que describían tres formas de hacer esto. Demostraron que cada una de estas técnicas es tan segura como el cifrado de bloques que se utiliza para construirla. Esto significa que si el algoritmo AES se utiliza 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, los algoritmos FPE construidos a partir de él también son seguros. En todo lo siguiente, 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 a partir de un cifrado de prefijo

Una forma sencilla de crear un algoritmo FPE en {0, ..., N -1} es asignar un peso pseudoaleatorio a cada 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 entero, dando, por ejemplo, 

weight(0) = 0x56c644080098fc5570f2b329323dbf62
weight(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7
weight(2) = 0x47d2e1bf72264fa01fb274465e56ba20
weight(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 sólo es útil para valores pequeños de N . Para valores más grandes, el tamaño de la tabla de búsqueda y el número requerido de encriptaciones para inicializar la tabla es demasiado grande para ser práctico.

FPE de la marcha en bicicleta

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) {
    if P(x) is an element of M then
        return P(x)
    else
        return 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 al comenzar 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 enteros. Tiene la desventaja, cuando M es mucho más pequeño que el dominio de P , que pueden ser necesarias demasiadas iteraciones para cada operación. Si P es un cifrado de bloque de un tamaño fijo, como AES, esta 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 manera que cree otro valor de 100 bits. Con esta técnica, se puede aplicar el cifrado AES-128-ECB hasta que alcance un valor que tenga todos sus 28 bits más altos establecidos en 0, lo que tomará un promedio de 2 28 iteraciones para que suceda.

FPE de una red Feistel

También es posible hacer un algoritmo FPE usando una red Feistel . Una red Feistel necesita una fuente de valores pseudoaleatorios para las subclaves para cada ronda, y la salida del algoritmo AES puede usarse como estos valores pseudoaleatorios. Cuando se hace esto, la construcción de Feistel resultante es buena si se utilizan suficientes rondas.

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 de Feistel conserve el formato de la entrada, pero es posible iterar la red de Feistel de la misma manera que lo hace la técnica de marcha 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 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 números posibles 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 , utilizando una red Feistel de 50 bits de ancho junto con la caminata en bicicleta creará un algoritmo FPE que encripta con bastante rapidez en promedio.

La baraja de Thorp

Una baraja de Thorp es como una baraja de cartas idealizada, o lo que es lo mismo, un cifrado de Feistel con desequilibrio 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.

Modo VIL

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.

Cifrado de pudín apresurado

El Hasty Pudding Cipher utiliza construcciones personalizados (no en función de cifrado por bloques existentes como primitivas) para cifrar arbitraria finitos pequeños dominios.

El modo FFSEM / FFX de AES

El modo FFSEM de AES (especificación) que ha sido aceptado para su consideración por NIST usa la construcción de red Feistel de Black y Rogaway descrita anteriormente, con AES para la función redonda, con una pequeña modificación: se usa una sola tecla y se ajusta 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, Desarrollo de modos de cifrado de bloques 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 sin formato ni en el texto cifrado. La sencilla técnica modular-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 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 bytes "... 30FF" y el segundo bloque de texto cifrado comienza con bytes "9832 ...", entonces el código de marcador "0xFF98" aparecerá en el texto cifrado.

En el documento "Esquemas de cifrado eficientes y seguros para JPEG2000", de Hongjun Wu y Di Ma, se dieron dos mecanismos para el cifrado de JPEG 2000 que conserva el formato. Para realizar el cifrado que conserva 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 de módulo n con cifrado de flujo; otro mecanismo de cifrado JPEG 2000 realiza la técnica de ciclo de caminata con cifrado de bloques.

Otras construcciones FPE

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 eliminar el sesgo del resultado. La adición de módulo-n compartida por muchos de los constructos es la solución inmediatamente obvia al problema de FPE (por lo tanto, su uso en varios casos), con las principales diferencias en los mecanismos de no sesgo utilizados.

La sección 8 de FIPS 74, Publicación de estándares federales de procesamiento de información de 1981, Pautas para implementar y usar el estándar de cifrado de datos NBS , describe una forma de utilizar el algoritmo de cifrado DES de una manera que preserva el formato de los datos mediante la adición de módulo n seguida de una operación imparcial. Este estándar fue retirado el 19 de mayo de 2005, por lo que la técnica debe considerarse obsoleta en términos de ser un estándar formal.

Otro mecanismo temprano para el cifrado que preserva el formato fue el "Cifrado de datos con un rango restringido de valores" de Peter Gutmann , que nuevamente realiza una adición de módulo-n en cualquier cifrado con algunos ajustes para que el resultado sea uniforme, con el cifrado resultante tan fuerte como el algoritmo de cifrado subyacente en el que se basa.

El documento "Uso del cifrado que conserva el tipo de datos para mejorar la seguridad del almacén de datos" de Michael Brightwell y Harry Smith describe una forma de utilizar el algoritmo de cifrado DES de una manera que conserva 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 documento "Cifrado que preserva el formato" de Mihir Bellare y Thomas Ristenpart describe el uso de redes Feistel "casi equilibradas" para crear algoritmos FPE seguros.

El documento "Formato que controla el cifrado mediante el tipo de datos que preserva el cifrado" de Ulf Mattsson describe otras formas de crear algoritmos FPE.

Un ejemplo de algoritmo FPE es FNR ( Flexible Naor y Reingold ).

Aceptación de algoritmos FPE por las autoridades de estándares

La publicación especial 800-38G del NIST, "Recomendación para los modos de operación de cifrado de bloques: métodos para el cifrado de conservación de formato" especifica dos métodos: FF1 y FF3. Los detalles sobre las propuestas enviadas para cada uno se pueden encontrar en el sitio de Desarrollo de Modos de Cifrado en Bloque de NIST, incluida la información sobre patentes y vectores de prueba. Los valores de muestra están disponibles para FF1 y FF3.

  • FF1 es FFX [Radix] "Modo de cifrado basado en Feistel que preserva el formato", que también se encuentra en los procesos estándar 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 suministran vectores de prueba y partes de ellos están patentados. (DRAFT SP 800-38G Rev 1) requiere que el tamaño mínimo de dominio de los datos que se cifran sea de 1 millón (anteriormente 100).
  • FF3 es BPS que lleva el nombre de los autores. Fue presentado al NIST por Eric Brier, Thomas Peyrin y Jacques Stern de Ingenico, Francia. Los autores declararon al NIST que su algoritmo no está patentado. El producto CyberRes Voltage , aunque afirma poseer patentes también para el modo BPS. El 12 de abril de 2017, NIST concluyó que FF3 "ya no es adecuado como método FPE de propósito general" porque los investigadores encontraron una vulnerabilidad.
  • FF3-1 (DRAFT SP 800-38G Rev 1) reemplaza a FF3 y requiere que el tamaño mínimo de dominio de los datos que se cifran sea de 1 millón (anteriormente 100).

Se incluyó otro modo en el borrador de la guía del NIST, pero se eliminó antes de la publicación final.

  • FF2 es el esquema VAES3 para FFX: un anexo al "Modo de operación FFX para preservar el cifrado": una colección de parámetros para cadenas de cifrado de base arbitraria con operación de subclave para prolongar 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 suministran por separado de FF1 y algunas de sus partes están patentadas. Los autores han presentado un algoritmo modificado como DFF que está bajo consideración activa por parte del 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