El cifrado Hasty Pudding ( HPC ) es un cifrado de bloque de tamaño de bloque variable diseñado por Richard Schroeppel , que no fue un candidato exitoso en la competencia para seleccionar el Estándar de cifrado avanzado de EE. UU . (AES). Tiene una serie de propiedades inusuales para un cifrado de bloque: el tamaño del bloque de entrada y la longitud de la clave son variables e incluye un parámetro de entrada adicional llamado "spice" para usar como clave secundaria no secreta. El cifrado Hasty Pudding fue el único candidato AES diseñado exclusivamente por criptógrafos estadounidenses. [1] [2]
General | |
---|---|
Diseñadores | Richard Schroeppel |
Publicado por primera vez | Junio de 1998 |
Detalle de cifrado | |
Tamaños de clave | Variable |
Tamaños de bloque | Variable |
El cifrado Hasty Pudding es de dominio público . [3]
El cifrado
El cifrado Hasty Pudding consta de 5 subcifrados diferentes: [4]
HPC-Tiny | 0–35 bits |
HPC corto | 36–64 bits |
HPC-Medio | 65-128 bits |
HPC-largo | 129–512 bits |
HPC-Extendido | 513+ bits |
Todos los algoritmos de cifrado de Hasty Pudding utilizan internamente palabras de 64 bits. El cifrado está diseñado para ejecutarse en máquinas de 64 bits , que pueden realizar fácilmente operaciones simples en palabras de 64 bits.
Expansión clave
El cifrado Hasty Pudding puede tomar una clave de cualquier número de bits para cualquiera de los cinco subcifradores. El cifrado en sí usa una tabla de claves de 16 384 bits (256 palabras de 64 bits). Para derivar la tabla de claves a partir de la clave, la función de expansión de claves utiliza el siguiente algoritmo: [4]
- Las primeras tres palabras, KX [0], KX [1], KX [2] se establecen en función de las constantes, el subcifrado y la longitud de la clave. KX [1] se calcula con una multiplicación; las otras operaciones involucradas son una adición y un pequeño cambio.
- Cada palabra sucesiva, KX [ i ], se determina a partir de las tres palabras anteriores mediante una fórmula recursiva eficaz.
- Los bits de clave se aplican mediante XOR a los bits de la tabla de claves, comenzando en KX [0], hasta que se utilizan todos los bits de clave. (Las claves de más de 8.192 bits utilizan un procedimiento más complicado).
- Se realizan varias pasadas sobre la mesa de llaves. Cada vez, se aplica una "función de agitación" a cada palabra de la tabla de teclas, en secuencia. La función de agitación utiliza ocho variables internas y utiliza 14 operaciones de bits lógicos, cambios de 5 bits y 14 sumas / restas. Cada uso de la función de agitación modifica una palabra en la tabla de claves, en función de su valor anterior, los valores de algunas otras palabras y las variables internas de la función de agitación. (3 pases totales es el valor predeterminado).
Cifrado y descifrado
Cada uno de los subcifradores usa un algoritmo diferente, pero existen ciertas similitudes. Se utilizan tres entradas para determinar el texto cifrado: el texto sin formato (en varias palabras de 64 bits más un "fragmento"), la especia (ocho palabras de 64 bits, con valor predeterminado 0) y la tabla de claves. Las operaciones dentro del cifrado consisten en agitar , que combina variables internas de varias formas con valores de la tabla de claves y especias a intervalos regulares. HPC-Short usa dos permutaciones fijas además, y HPC-Tiny consta de muchos sub-casos especiales.
El descifrado implica deshacer los pasos del cifrado uno por uno. Muchas operaciones se deshacen fácilmente (por ejemplo, s 0 = s 0 + s 1 se deshace calculando s 0 = s 0 - s 1). Otras operaciones son más complejas de deshacer. Algunas de las ideas involucradas incluyen:
- Una operación como x = x ( x >> 17) se deshace mediante un proceso de dos pasos: (1) x = x ( x >> 17), seguido de (2) x = x ( x >> 34).
- El cifrado utiliza búsquedas dependientes del valor en la tabla de claves. Estos se pueden deshacer, ya que la búsqueda depende solo de los últimos 8 bits de una variable, y cuando sea necesario buscar el valor de la tabla de claves en el descifrado, los últimos 8 bits del valor en un cierto punto anterior en el los cálculos son predecibles, incluso cuando esas operaciones no se pueden deshacer sin el valor de la tabla clave. Por ejemplo, si la búsqueda de k se basa en los últimos 8 bits de x , entonces cuando queremos deshacer un paso como x = x ( k << 8), podemos buscar k notando que los últimos 8 bits de x no cambian con esta operación.
El cifrado Hasty Pudding también se puede utilizar para cifrar valores en un rango que no se traduce en cadenas con un número entero de bits; por ejemplo, se puede cifrar un número de 0 a N mediante la producción de otro número de 0 a N . Hace esto usando el subcifrador más pequeño que puede manejar la entrada como una cadena de bits y aplicándola a la entrada como una cadena de bits, repetidamente, hasta que la salida está en el rango adecuado. [4]
Actuación
Schroeppel afirmó que el cifrado Hasty Pudding era el candidato AES más rápido en una arquitectura de 64 bits; [5] Schroeppel afirmó que era dos veces más rápido que su competidor más cercano, DFC , y tres veces más rápido que los otros candidatos, y que su rendimiento en una máquina de 32 bits era adecuado. [5] Los comentarios de otros no apoyaron esta opinión; por ejemplo, el análisis de Schneier et al. clasificó el cifrado Hasty Pudding en cuarto lugar como el mejor (376 ciclos) en una máquina de 64 bits, aunque para Rijndael y Twofish , el rendimiento solo se estimó. [6] En un Pentium de 32 bits , el cifrado Hasty Pudding fue calificado por Schneier et al. a 1600 ciclos de reloj, el décimo mejor de los 15 candidatos. [6] Schneier et al., Y Schroeppel, señalaron que la velocidad del cifrado se vería afectada significativamente en una máquina de 32 bits debido a su uso intensivo de operaciones de 64 bits, particularmente cambios de bits. [3] [6]
La configuración de la clave del cifrado Hasty Pudding se calificó como relativamente lenta; 120000 ciclos en un Pentium. [6]
El cifrado fue criticado por su desempeño en tarjetas inteligentes . Específicamente, algunos comentarios señalaron la dificultad de mantener más de 2 KB de RAM para la tabla de claves. [7]
Más trabajo
Ha habido relativamente pocos resultados al atacar el cifrado Hasty Pudding. Al principio del proceso de AES, David Wagner notó que las clases relativamente grandes de claves de Hasty Pudding eran equivalentes en el sentido de que conducían a la misma tabla de claves. [8] Esto fue ampliado por D'Halluin et al., Quienes observaron que para claves de 128 bits, aproximadamente 2120 claves son claves débiles y cada una tiene 2 30 claves equivalentes cada una. [9] En respuesta a este ataque, Schroeppel modificó el algoritmo de expansión clave para incluir un paso adicional. [4]
A pesar de la relativa falta de criptoanálisis, el cifrado Hasty Pudding fue criticado por su diseño difícil de entender y su falta de base en los resultados de la investigación. [8] [10] Schroeppel ha ofrecido una botella de champán Dom Pérignon al mejor periódico que presenta el progreso en el cifrado de Hasty Pudding. [3] No hizo la segunda ronda de consideración para AES. [11]
El cifrado Hasty Pudding se considera el primer cifrado de bloque modificable . [12]
Referencias
- ^ Eli Biham , Una nota sobre la comparación de los candidatos de AES , abril de 1999, comentario público sobre AES.
- ^ Susan Landau , Seguridad de las comunicaciones para el siglo XXI: El estándar de cifrado avanzado , Avisos del AMS, vol. 47, número 4, 2000.
- ↑ a b c Rich Schroeppel y Hilarie Orman, An Overview of the Hasty Pudding Cipher , julio de 1998.
- ^ Un b c d Schroeppel, Rich (junio de 1998), Hasty Pudding Cipher Especificación (Revisado en mayo de 1,999 mil ed.), Archivado del original en 2011-07-17 , recuperada 2009-06-10
- ↑ a b Rich Schroeppel, The Hasty Pudding Cipher: One Year Later , consultado el 1 de septiembre de 2008
- ^ a b c d Bruce Schneier , John Kelsey , Doug Whiting , David Wagner , Chris Hall y Niels Ferguson , Comparación de rendimiento de las presentaciones de AES , Segunda conferencia de candidatos de AES, 1999.
- ^ Emanoil Daneliuc, Comentario público sobre candidatos AES , febrero de 1999.
- ^ a b David Wagner, Equivalent keys for HPC , charla en la sesión de grupa en la 2da Conferencia de AES, Roma , marzo de 1999.
- ^ Carl D'Halluin, Gert Bijnens, Bart Preneel y Vincent Rijmen , Claves equivalentes de HPC , Avances en criptología - Actas de ASIACRYPT 1999, 1999.
- ^ Olivier Baudron, Henri Gilbert , Louis Granboulan, Helena Handschuh , Antoine Joux , Phong Nguyen , Fabrice Noilhan, David Pointcheval , Thomas Pornin, Guillaume Poupard, Jacques Stern y Serge Vaudenay , Informe sobre los candidatos AES , Segunda Conferencia AES, marzo de 1999 .
- ^ James Nechvatal, Elaine Barker, Lawrence Bassham, William Burr, Morris Dworkin, James Foti y Edward Roback, Informe sobre el desarrollo del estándar de cifrado avanzado (AES) ,lanzamiento oficial de NIST , 2 de octubre de 2000.
- ^ Moses Liskov, Ronald Rivest y David Wagner , cifrados de bloque modificables , en Advances in Cryptology - Proceedings of CRYPTO '02, 2002.
Ver también
- Cifrado que conserva el formato