Relleno (criptografía)

En criptografía , el relleno es una serie de prácticas distintas que incluyen la adición de datos al principio, al medio o al final de un mensaje antes del cifrado. En la criptografía clásica, el relleno puede incluir la adición de frases sin sentido a un mensaje para ocultar el hecho de que muchos mensajes terminan de formas predecibles, por ejemplo, " atentamente" .

Los mensajes oficiales suelen empezar y terminar de forma predecible: Mi estimado embajador, Informe meteorológico, Atentamente , etc. El uso principal del relleno con cifrados clásicos es evitar que el criptoanalista utilice esa previsibilidad para encontrar texto simple conocido ^[1] que ayude a descifrar el cifrado. El relleno de longitud aleatoria también evita que un atacante conozca la longitud exacta del mensaje de texto simple.

Un ejemplo famoso de relleno clásico que causó un gran malentendido es el incidente de "las maravillas del mundo", que casi provocó una pérdida aliada en la batalla de Samar durante la Segunda Guerra Mundial , parte de la batalla más grande del Golfo de Leyte . En ese ejemplo, el almirante Chester Nimitz , comandante en jefe de la Flota del Pacífico de los EE. UU . en la Segunda Guerra Mundial, envió el siguiente mensaje al almirante Bull Halsey , comandante de la Fuerza de Tarea Treinta y Cuatro (la principal flota aliada) en la batalla del Golfo de Leyte, el 25 de octubre de 1944: ^[2]

¿Dónde está, repito, dónde está la Fuerza de Tarea Treinta y Cuatro? ^[3]

Con relleno (en negrita) y metadatos agregados, el mensaje quedó así:

TURKEY TROTS TO WATER GG FROM CINCPAC ACTION COM THIRD FLEET INFO COMINCH CTF SEVENTY-SEVEN X WHERE IS RPT WHERE IS TASK FORCE THIRTY FOUR RR THE WORLD WONDERS^[3]

El operador de radio de Halsey confundió parte del relleno con el mensaje y así el almirante Halsey terminó leyendo el siguiente mensaje:

¿Dónde está, repito, dónde está la Fuerza de Tareas Treinta y Cuatro? El mundo se pregunta ^[3]

El almirante Halsey interpretó la frase de relleno "the world wonders" como una reprimenda sarcástica, lo que le provocó un arrebato emocional y luego se encerró en su puente y se enfurruñó durante una hora antes de mover sus fuerzas para ayudar en la batalla frente a Samar. ^[2] El operador de radio de Halsey debería haber sido avisado por las letras RR de que "the world wonders" era una frase de relleno; todos los demás operadores de radio que recibieron el mensaje del almirante Nimitz eliminaron correctamente ambas frases de relleno. ^[2]

Muchos cifrados clásicos organizan el texto simple en patrones particulares (por ejemplo, cuadrados, rectángulos, etc.) y, si el texto simple no encaja exactamente, suele ser necesario añadir letras adicionales para completar el patrón. El uso de letras sin sentido para este propósito tiene el beneficio adicional de dificultar algunos tipos de criptoanálisis.

La mayoría de las funciones hash criptográficas modernas procesan los mensajes en bloques de longitud fija; todas, salvo las primeras, incluyen algún tipo de esquema de relleno. Es fundamental que las funciones hash criptográficas empleen esquemas de terminación que impidan que un hash sea vulnerable a ataques de extensión de longitud .

Muchos esquemas de relleno se basan en agregar datos predecibles al bloque final. Por ejemplo, el relleno podría derivarse de la longitud total del mensaje. Este tipo de esquema de relleno se aplica comúnmente a algoritmos hash que utilizan la construcción Merkle–Damgård, como MD-5 , SHA-1 y la familia SHA-2, como SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 y SHA-512/256 ^[4]

El modo de encadenamiento de bloques de cifrado (CBC) es un ejemplo de modo de funcionamiento de cifrado de bloques . Algunos modos de cifrado de bloques (CBC y PCBC, básicamente) para algoritmos de cifrado de clave simétrica requieren una entrada de texto sin formato que sea un múltiplo del tamaño del bloque, por lo que es posible que haya que rellenar los mensajes para que tengan esta longitud.

La exactitud fáctica de esta sección está en disputa . Se puede encontrar discusión relevante en la página de discusión . Por favor, ayude a garantizar que las afirmaciones en disputa tengan fuentes confiables . ( Enero de 2016 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Actualmente ^{[ ¿cuándo? ]} se está produciendo un cambio hacia el uso del modo de funcionamiento en streaming en lugar del modo de funcionamiento en bloque. ^{[ cita requerida ]} Un ejemplo de cifrado en modo streaming es el modo de funcionamiento en contador . ^[5] Los modos de funcionamiento en streaming pueden cifrar y descifrar mensajes de cualquier tamaño y, por lo tanto, no requieren relleno. Las formas más complejas de finalizar un mensaje, como el robo de texto cifrado o la terminación de bloques residuales, evitan la necesidad de relleno.

Una desventaja del relleno es que hace que el texto simple del mensaje sea susceptible a ataques de oráculo de relleno . Los ataques de oráculo de relleno permiten al atacante obtener conocimiento del texto simple sin atacar el primitivo de cifrado de bloque en sí. Los ataques de oráculo de relleno se pueden evitar asegurándose de que un atacante no pueda obtener conocimiento sobre la eliminación de los bytes de relleno. Esto se puede lograr verificando un código de autenticación de mensaje (MAC) o una firma digital antes de eliminar los bytes de relleno, o cambiando a un modo de operación de transmisión.

El relleno de bits se puede aplicar a mensajes de cualquier tamaño.

Se añade un solo bit "1" al mensaje y luego se añaden tantos bits "0" como se requiera (posiblemente ninguno). La cantidad de bits "0" añadidos dependerá del límite del bloque al que se debe extender el mensaje. En términos de bits, esto es "1000... 0000".

Este método se puede utilizar para rellenar mensajes que tengan cualquier cantidad de bits de longitud, no necesariamente un número entero de bytes. Por ejemplo, un mensaje de 23 bits que se rellena con 9 bits para llenar un bloque de 32 bits:

... | 1011 1001 1101 0100 0010 011 1 0000 0000 |

Este relleno es el primer paso de un esquema de relleno de dos pasos que se utiliza en muchas funciones hash , incluidas MD5 y SHA . En este contexto, se especifica en el paso 3.1 de RFC1321.

Este esquema de relleno está definido por ISO/IEC 9797-1 como Método de relleno 2.

El relleno de bytes se puede aplicar a mensajes que se pueden codificar como un número entero de bytes .

En ANSI X9.23, siempre se agregan entre 1 y 8 bytes como relleno. El bloque se rellena con bytes aleatorios (aunque muchas implementaciones usan 00) y el último byte del bloque se establece en la cantidad de bytes agregados. ^[6]

Ejemplo: En el siguiente ejemplo, el tamaño del bloque es de 8 bytes y se requiere relleno de 4 bytes (en formato hexadecimal).

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 04 |

La norma ISO 10126 (retirada en 2007 ^{[7] [8]} ) especifica que el relleno debe realizarse al final de ese último bloque con bytes aleatorios, y el límite de relleno debe especificarse mediante el último byte.

Ejemplo: En el siguiente ejemplo, el tamaño del bloque es de 8 bytes y se requiere relleno de 4 bytes.

... | DD DD DD DD DD DD DD DD | DD DD DD DD 81 A6 23 04 |

PKCS#7 se describe en RFC 5652.

El relleno se realiza en bytes completos. El valor de cada byte añadido es la cantidad de bytes que se añaden, es decir, se añaden N bytes, cada uno de valor N. La cantidad de bytes añadidos dependerá del límite del bloque al que se debe extender el mensaje.

El relleno será uno de los siguientes:

0102 0203 03 0304 04 04 0405 05 05 05 0506 06 06 06 06 06etc.

Este método de relleno (así como los dos anteriores) está bien definido si y solo si N es menor que 256.

Ejemplo: En el siguiente ejemplo, el tamaño del bloque es de 8 bytes y se requiere relleno de 4 bytes.

... | DD DD DD DD DD DD DD DD | DD DD DD DD 04 04 04 04 |

Si la longitud de los datos originales es un múltiplo entero del tamaño del bloque B , entonces se añade un bloque adicional de bytes con el valor B. Esto es necesario para que el algoritmo de descifrado pueda determinar con certeza si el último byte del último bloque es un byte de relleno que indica la cantidad de bytes de relleno añadidos o parte del mensaje de texto sin formato. Considere un mensaje de texto sin formato que es un múltiplo entero de B bytes con el último byte de texto sin formato siendo 01. Sin información adicional, el algoritmo de descifrado no podrá determinar si el último byte es un byte de texto sin formato o un byte de relleno. Sin embargo, al añadir B bytes cada uno de valor B después del byte de texto sin formato 01 , el algoritmo de descifrado siempre puede tratar el último byte como un byte de relleno y quitar la cantidad apropiada de bytes de relleno del final del texto cifrado; dicha cantidad de bytes se quitará en función del valor del último byte.

El relleno PKCS#5 es idéntico al relleno PKCS#7, excepto que solo se ha definido para cifrados de bloque que utilizan un tamaño de bloque de 64 bits (8 bytes). En la práctica, ambos pueden utilizarse indistintamente.

El tamaño máximo de bloque es 255, ya que es el número más grande que un byte puede contener.

La norma ISO/IEC 7816-4 :2005 ^[9] es idéntica al esquema de relleno de bits, aplicado a un texto simple de N bytes. Esto significa en la práctica que el primer byte es un byte obligatorio con valor '80' (hexadecimal) seguido, si es necesario, de 0 a N  − 1 bytes configurados con el valor '00', hasta que se alcanza el final del bloque. La norma ISO/IEC 7816-4 es en sí misma un estándar de comunicación para tarjetas inteligentes que contienen un sistema de archivos y, en sí misma, no contiene ninguna especificación criptográfica.

Ejemplo: En el siguiente ejemplo, el tamaño del bloque es de 8 bytes y se requiere relleno de 4 bytes.

... | DD DD DD DD DD DD DD DD | DD DD DD DD 80 00 00 00 |

El siguiente ejemplo muestra un relleno de solo un byte.

... | DD DD DD DD DD DD DD DD | DD DD DD DD DD DD DD 80 |

Todos los bytes que se deben rellenar se rellenan con ceros. El esquema de relleno con ceros no se ha estandarizado para el cifrado, ^{[ cita requerida ]} aunque se especifica para hashes y MAC como Método de relleno 1 en ISO/IEC 10118-1 ^[10] e ISO/IEC 9797-1 . ^[11]

Ejemplo: En el siguiente ejemplo, el tamaño del bloque es de 8 bytes y se requiere relleno de 4 bytes.

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 00 |

El relleno con ceros puede no ser reversible si el archivo original termina con uno o más bytes cero, lo que hace imposible distinguir entre bytes de datos de texto sin formato y bytes de relleno. Se puede utilizar cuando la longitud del mensaje se puede derivar fuera de banda . A menudo se aplica a cadenas codificadas en binario ^{[ aclaración necesaria ]} ( cadena terminada en nulo ) ya que el carácter nulo generalmente se puede eliminar como espacio en blanco .

El relleno de ceros también se conoce a veces como "relleno nulo" o "relleno de bytes cero". Algunas implementaciones pueden agregar un bloque adicional de bytes cero si el texto sin formato ya es divisible por el tamaño del bloque. ^{[ cita requerida ]}

En criptografía de clave pública , el relleno es el proceso de preparación de un mensaje para su cifrado o firma mediante una especificación o esquema como PKCS#1 v2.2, OAEP , PSS , PSSR, IEEE P1363 EMSA2 y EMSA5. Una forma moderna de relleno para primitivas asimétricas es OAEP aplicado al algoritmo RSA , cuando se utiliza para cifrar una cantidad limitada de bytes.

La operación se denomina "relleno" porque, originalmente, simplemente se añadía material aleatorio al mensaje para hacerlo lo suficientemente largo para el primitivo. Esta forma de relleno no es segura y, por lo tanto, ya no se aplica. Un esquema de relleno moderno tiene como objetivo garantizar que el atacante no pueda manipular el texto sin formato para explotar la estructura matemática del primitivo y, por lo general, estará acompañado de una prueba, a menudo en el modelo de oráculo aleatorio , de que romper el esquema de relleno es tan difícil como resolver el problema difícil subyacente al primitivo.

Incluso si se utilizan rutinas criptográficas perfectas, el atacante puede obtener información sobre la cantidad de tráfico que se generó. Es posible que el atacante no sepa de qué hablaban Alice y Bob , pero puede saber que hablaban y cuánto hablaban. En algunas circunstancias, esta filtración puede ser muy comprometedora. Por ejemplo, cuando un ejército está organizando un ataque secreto contra otra nación: puede bastar con alertar a la otra nación para que sepa simplemente que se está llevando a cabo una gran cantidad de actividad secreta.

Como otro ejemplo, al cifrar transmisiones de voz sobre IP que utilizan codificación de velocidad de bits variable, no se oculta la cantidad de bits por unidad de tiempo, y esto se puede aprovechar para adivinar frases habladas. ^[12] De manera similar, los patrones de ráfaga que producen los codificadores de video comunes suelen ser suficientes para identificar de forma única el video en streaming que está viendo un usuario. ^[13] Incluso el tamaño total de un objeto por sí solo, como un sitio web, un archivo, una descarga de un paquete de software o un video en línea, puede identificar de forma única un objeto, si el atacante conoce o puede adivinar un conjunto conocido del que proviene el objeto. ^{[14] [15] [16]} El canal lateral de longitud de contenido cifrado se utilizó para extraer contraseñas de comunicaciones HTTPS en los conocidos ataques CRIME y BREACH . ^[17]

El relleno de un mensaje cifrado puede dificultar el análisis del tráfico al ocultar la longitud real de su contenido. La elección de la longitud con la que se rellenará un mensaje puede hacerse de forma determinista o aleatoria; cada enfoque tiene sus puntos fuertes y débiles que se aplican en diferentes contextos.

Se puede añadir un número aleatorio de bits o bytes de relleno adicionales al final de un mensaje, junto con una indicación al final de cuánto relleno se añadió. Si la cantidad de relleno se elige como un número aleatorio uniforme entre 0 y un M máximo, por ejemplo, entonces un espía no podrá determinar la longitud del mensaje con precisión dentro de ese rango. Si el relleno máximo M es pequeño en comparación con el tamaño total del mensaje, entonces este relleno no añadirá mucha sobrecarga , pero el relleno oscurecerá solo los bits menos significativos de la longitud total del objeto, dejando la longitud aproximada de los objetos grandes fácilmente observable y, por lo tanto, todavía potencialmente identificable de forma única por su longitud. Si el relleno máximo M es comparable al tamaño de la carga útil, por el contrario, la incertidumbre de un espía sobre el tamaño real de la carga útil del mensaje es mucho mayor, a costa de que el relleno pueda añadir hasta un 100% de sobrecarga ( 2× explosión) al mensaje.

Además, en escenarios comunes en los que un espía tiene la oportunidad de ver muchos mensajes sucesivos del mismo remitente, y esos mensajes son similares en formas que el atacante conoce o puede adivinar, entonces el espía puede usar técnicas estadísticas para disminuir e incluso eventualmente eliminar el beneficio del relleno aleatorio. Por ejemplo, supongamos que la aplicación de un usuario envía regularmente mensajes de la misma longitud, y el espía sabe o puede adivinar el hecho basándose en la identificación de la aplicación del usuario, por ejemplo. Alternativamente, un atacante activo podría ser capaz de inducir a un punto final a enviar mensajes regularmente, como si la víctima fuera un servidor público. En tales casos, el espía puede simplemente calcular el promedio de muchas observaciones para determinar la longitud de la carga útil del mensaje regular.

Un esquema de relleno determinista siempre rellena una carga útil de mensaje de una longitud dada para formar un mensaje cifrado de una longitud de salida correspondiente particular. Cuando muchas longitudes de carga útil se asignan a la misma longitud de salida rellenada, un espía no puede distinguir ni obtener ninguna información sobre la longitud real de la carga útil dentro de uno de estos intervalos de longitud , incluso después de muchas observaciones de los mensajes de longitud idéntica que se transmiten. En este sentido, los esquemas de relleno deterministas tienen la ventaja de no filtrar ninguna información adicional con cada mensaje sucesivo del mismo tamaño de carga útil.

Por otra parte, supongamos que un espía puede beneficiarse de conocer pequeñas variaciones en el tamaño de la carga útil, como, por ejemplo, un byte más o menos en un ataque de adivinación de contraseñas. Si el remitente del mensaje tiene la mala suerte de enviar muchos mensajes cuyas longitudes de carga útil varían en solo un byte, y esa longitud está exactamente en el límite entre dos de las clases de relleno deterministas, entonces estas longitudes de carga útil de más o menos uno producirán también longitudes de relleno diferentes (más o menos un bloque, por ejemplo), filtrando exactamente la información de grano fino que desea el atacante. Contra tales riesgos, el relleno aleatorio puede ofrecer más protección al ocultar de forma independiente los bits menos significativos de las longitudes de los mensajes.

Los métodos de relleno deterministas comunes incluyen el relleno a un tamaño de bloque constante y el relleno a la siguiente potencia más grande de dos. Sin embargo, al igual que el relleno aleatorio con una pequeña cantidad máxima  M , el relleno determinista a un tamaño de bloque mucho más pequeño que la carga útil del mensaje oculta solo los bits menos significativos de la longitud real del mensaje, dejando la longitud aproximada real del mensaje en gran parte desprotegida. El relleno de mensajes a una potencia de dos (o cualquier otra base fija) reduce la cantidad máxima de información que el mensaje puede filtrar a través de su longitud de O (log M ) a O (log log M ) . Sin embargo, el relleno a una potencia de dos aumenta la sobrecarga del tamaño del mensaje hasta en un 100%, y el relleno a potencias de bases enteras más grandes aumenta aún más la sobrecarga máxima.

El esquema PADMÉ, propuesto para blobs aleatorios uniformes acolchados o PURBs , rellena de manera determinista los mensajes a longitudes representables como un número de punto flotante cuya mantisa ya no es (es decir, no contiene más bits significativos) que su exponente. ^[16] Esta restricción de longitud asegura que un mensaje pierda como máximo O (log log M ) bits de información a través de su longitud, como el relleno a una potencia de dos, pero incurre en una sobrecarga mucho menor de como máximo 12% para mensajes pequeños y disminuye gradualmente con el tamaño del mensaje.

• Mezclando y descartando grandes cantidades de tonterías antes de enviarlas
• Robo de texto cifrado , otro enfoque para tratar los mensajes que no son múltiplos de la longitud del bloque
• Vector de inicialización , sal (criptografía) , que a veces se confunden con el relleno
• Encapsulación de claves , una alternativa al relleno para sistemas de claves públicas utilizados para intercambiar claves simétricas
• PURB o blob aleatorio uniforme acolchado , una disciplina de cifrado que minimiza la fuga de metadatos o de longitud.
• La cópula rusa , otra técnica para evitar los cuneros

• XCBC: csrc.nist.gov/groups/ST/toolkit/BCM/documents/workshop2/presentations/xcbc.pdf