Criptosistemas de Bloque

Primitivas de Cifrado en Bloque

Están definidos para mensajes de tamaño fijo

• $K=\{0,1{\}}^n$, $C=P=\{0,1{\}}^b$
• Gen: $k\leftarrow K$
• Enc: ${\text{enc}}_k(m)=c$
• Dec: ${\text{dec}}_k(c)=m$

No son criptosistemas, pero si los forman al combinarse en otros modos.

Extensión y Encadenamiento

Cuando el mensaje a cifrar es más chico que el tamaño de bloque, se lo extiende sistemáticamente:

• Simple Pad es un padding ambiguo, donde se completa con ceros. Es necesario conocer el tamaño real del mensaje, pues si no no se puede reconocer donde termina el archivo real.
• Des Pad es un padding no ambiguo, donde se agrega un bit 1 y luego se completa con 0s. Puede llegar a agregar un bloque completo de padding.

Cuando tenemos mensajes más grandes dividimos los mensajes en bloques, y extendemos el ultimo bloque con padding.

Modos de Encadenamiento

Son utilizadas para extender una primitiva de cifrado a bloques mayores a su tamaño

Electronic Code Book (ECB)

Trata al mensaje original como un conjunto de bloques independientes, encriptando cada uno con la key original.

No es CPA-Secure

Es deterministico, pues si los bloques son iguales terminan encriptados al mismo cyphertext.

Cipher Block Chaining (CBC)

Utiliza la salida de un bloque como entrada para el próximo. Esto disminuye el traspaso de información, y requiere solo un valor inicial (IV) aleatorio que debe ser enviado junto al resto del mensaje. Esto se aprovecha del hecho de que lo que sale de un algoritmo de cifrado debería ser indistinguible de algo aleatorio. Si en la transmisión se modifica algún bit, entonces no se propaga mucho el error, si no que se limita al bloque afectado, y al bloque siguiente cuando se trata de usar el cifrado modificado para xorear lo encriptado y conseguir el bloque original.

Cipher Feedback (CFB)

Utiliza solo la función Enc, lo que resulta en menor complejidad para dispositivos embebidos. Es más barato de implementar pues no se necesita implementar la función de descifrado. Permite generar una transformación de flujo a partir de una de bloque

Output Feedback (OFB)

Construye una transformación de flujo a partir de una de bloque, y permite calcular los bits de transformación por adelantado en comparación a CFB.

Counter

La idea es utilizar un contador para generar secuencias de bits de clave, lo que permite acceso aleatorio. Esto es muy útil en ambientes con capacidad de procesamiento paralelo.

Counter with CBC-MAC

Basada en Counter y CBC-MAC, es una forma de Cifrado Autentificado, que tiene una prueba de seguridad especifica que determina que si el IV y el nonce no coinciden ni se reutilizan, la construcción es CCA-Secure usando la misma clave k para la encripción y el MAC.

La idea es “Authenticate-then-encrypt”, por lo que la función de encripción es ${\text{e}}_k({\text{cbc-mac}}_k(M)||m)$. El problema que tiene es que hay que recorrer el mensaje dos veces, una para el cbc y otra para encriptar.

GCM

Basada en Counter, es una forma de encadenar un criptosistema de bloque para formar un Cifrado Autentificado.

Seguridad

Las pruebas son por reducción a propiedades de la primitiva subyacente, y requieren que la primitiva se comporte como una función pseudoaleatoria. Asumiendo que la primitiva es una función pseudoaleatoria:

• CBC es CPA-Secure si los IVs son aleatorios
• OFB y CFB son CPA-Secure con IVs aleatorios
• Counter es CPA-Secure si no se repite (k, nonce)

Oops

No esta demostrado que existan las funciones pseudoaleatorias.

Data Encryption Standard (DES)

Fue un método desarrollado por IBM, adoptado por el gobierno de USA como standard para usos no militares. Fue la primera función de cifrado pública apoyada por un gobierno, y alcanzo uso comercial masivo. Trabaja con textos planos binarios, tiene una entrada de 64 bits, una clave de 64 bits (56 bits efectivos) y una salida de 64 bits. Es considerada obsoleta por el tamaño del espacio de claves, como estaba hecho en una época donde la memoria de las computadoras era mucho más falible, usa bits de la clave para su paridad. Esto quiere decir que tiene 2^56 posibles claves. Utiliza un modelo para construir un criptosistema de bloque a partir de una función más chica. $F$ es una función de sustitución de la que depende la seguridad de DES.

Función Transformación

Primero se usa una función $E$ de expansión que expande la mitad del bloque de 32 bits a 48 bits, para que coincida con la subkey. Luego se realizan sustituciones de bloques de 6 bits a 4 bits, con perdida de información, y después se permutan. Dependiendo de las sustituciones, se puede volver mucho más inseguro.

Generación de Subclaves

Se seleccionan 56 bits, con los 8 bits restantes para paridad.

Evolución

El nivel teórico de seguridad es de 56 bits. Genero desconfianza debido a cuestiones de diseño confidenciales (las sustituciones). En 1990 aparece el criptoanálisis diferencial, que permite atacar a DES en $2^{47}$ intentos. Gran parte del diseño de DES disminuye el impacto de este ataque, pese a que otros sistemas fueron inmediatamente quebrados. En 1990 aparece el criptoanálisis lineal, que permite atacar a DES a $2^{43}$ intentos, lo cual ya es posible ejecutar en una computadora común.

3-DES

Es una variante más fuerte de DES, que consiste en seleccionar 3 claves independientes y calcular: $c={\text{Enc}}_{k1}({\text{Dec}}_{k2}({\text{Enc}}_{k3}(p)))$ Brinda una seguridad del orden de 112 bits, que es menos a 168 bits, debido a un ataque conocido como meet-in-the-middle. Es inmune a criptoanálisis diferencial y lineal, pero es 3 veces más lenta que DES pues se realizan tres operaciones. Se descifra en la segunda operación, pese a que seria igual de seguro si se encriptara tres veces seguidas, por una razón ingenieril. Esto permite trabajar con tanto la variante simple como la variante triple al mismo tiempo, solo con usar $k_2=k_3$, pues eso devuelve $p$. Es considerado seguro hoy en dia.

Advanced Encryption Standard (AES)

Convocaron a todas las universidades del mundo, de forma que sea abierto al resto del mundo. La idea era encontrar un reemplazo de DES.