Criptografía

Un acumulador criptográfico es un algoritmo criptográfico que tiene como un entrada un conjunto amplio de elementos, X, y devuelve un sólo valor, Acc, de tamaño constante y normalmente reducido. Este valor puede usarse para representar al conjunto. Este valor, junto con otro valor llamado testigo, T, permite probar eficientemente, a través de un algoritmo de verificación si un elemento, x, pertenece al conjunto de partida X.^1 2 Es decir, el elemento x ha sido acumulado (o no) en Acc.

Para gestionar el acumulador suele ser necesaria la presencia de una entidad a la que se llama Gestor del acumulador que es el que se encarga de manipular dicho acumulador. Por tanto se encarga por ejemplo de hacer que se calcule valor del acumulador, gestionar los valores testigos o, si se trata de un acumulador dinámico, de borrar o insertar elementos en el conjunto.

Introducidos en 1993 por Josh Benaloh y Michael de Mare³ los acumuladores criptográficos se han usado como primitiva criptográfica en muy distintos tipos de aplicaciones como: Sellado de tiempo, listas negras, compresión, revocación de permisos, diccionarios autenticables.

Clasificación

Podemos clasificar los acumuladores criptográficos en función a varios criterios^5 4

Según la variabilidad de los conjuntos iniciales

Podemos clasificar los acumuladores criptográficos en función de la variabilidad de los conjuntos iniciales en:

• Estáticos.- No se puede hallar el valor que le corresponde a un conjunto, a partir de resultados anteriores. El conjunto inicial es fijo
• Dinámicos.- Para hallar el valor final que le corresponde a un conjunto se pueden usar resultados anteriores. Es decir, se puede hallar el nuevo valor de un conjunto resultado de insertar y/o borrar elementos del conjunto anterior. A veces, para realizar estas gestiones de añadir/borrar elementos es necesario cierto conocimiento. Por tanto es necesario la presencia de una entidad encargada de este tarea a la que se llama Gestor del acumulador.

Según la confianza en el Gestor del acumulador

Según la confianza que hay que tener en el Gestor del acumulador en podemos clasificar a los acumuladores criptográficos dinámicos en:

• Débiles.- Requieren que el gestor del acumulador sea confiable.
• Fuertes.- No requieren confiar en el gestor del acumulador.

Según su comportamiento con los elementos que no pertenecen al conjunto inicial

Podemos decir que un acumulador criptográfico es Universal si se puede demostrar eficientemente que cierto elemento no pertenece al conjunto inicial.

Akelarre es el nombre de un cifrador por bloques propuesto en 1996 que combinaba desarrollos de IDEA y RC5. Se demostró que era susceptible a un ataque incluso sólo con texto cifrado en el 2000 (Knudsen y Rijmen). Akelarre cifra en bloques de 128 bits de longitud con un tamaño variable de clave, que debe ser múltiplo de 64 bits. El número de rondas es variable, pero 4 son las sugeridas. Las operaciones en las rondas es similar a la usada en IDEA.

Alice y Bob son personajes ficticios usados en explicaciones criptográficas, Teoría de juegos y físicas,¹ especialmente las provenientes del inglés. Los nombres son usados por conveniencia, dado que explicaciones del tipo "La persona A quiere mandar un mensaje a la persona B" rápidamente comienzan a ser difíciles de seguir. Los nombres, políticamente correctos al usar ambos sexos, cortan la carga ambigua al usar en la explicación los adjetivos, artículos, etc. adecuados a cada sexo. Los nombres han sido elegidos de tal manera que concuerden con las primeras letras del alfabeto (persona A es Alice, persona B es Bob).

Lista de caracteres

Un ejemplo de la analogía de "Alice y Bob" usada en criptografía.

Diagrama de Alice y Bob usada para explicar la criptografía de clave pública.

Esta lista se extrae principalmente del libro Applied Cryptography por Bruce Schneier. Alice y Bob son arquetipos en la criptografía; Eva también es común. Nombres más abajo en el alfabeto son menos comunes.

• Alice y Bob. Generalmente, Alice quiere enviar un mensaje a Bob. Estos nombres fueron utilizados por Ron Rivest en 1978 en un artículo de Comunicaciones de la ACM presentando el sistema de cifrado RSA,² y en un método para obtener las firmas digitales y clave pública-Criptosistemas publicada el 4 de abril de 1977, revisado 01 de septiembre 1977, como memo técnico LCS/TM82.
• Carol, Carlos o Charlie, como tercero participante en las comunicaciones.
• Chuck, como un tercer participante generalmente de mala intención.³
• Craig, un ladrón de contraseñas (por lo general se encuentra en situaciones con contraseñas almacenadas con hash/salteadas).
• Dan o Dave, un cuarto participante.
• Erin, un quinto participante. (Es raro ver a Erin; E es generalmente reservado para Eva.)

• Eva, una espía, es por lo general un atacante pasivo. Aunque ella puede escuchar en los mensajes entre Alice y Bob, ella no puede modificarlos. En la criptografía cuántica, Eva también puede representar el medio ambiente.
• Faythe, un asesor, mensajero o intermediario de confianza (Repositorio de servicio clave, mensajero de secretos compartidos Puede ser una función de una máquina o un rol humano. Es utilizado con poca frecuencia, significa Fe o Fiel).
• Frank, sexto participante (y así sucesivamente alfabéticamente).

• Mallet^4 5 6 7 o Mallory,⁸ es un atacante malicioso (menos comúnmente llamado Trudy, un intruso); a diferencia de la pasiva Eva, éste es el atacante activo en los ataques man-in-the-middle que puede modificar los mensajes, sustituir sus propios mensajes, reproducir mensajes antiguos, y así sucesivamente. La dificultad de obtener un sistema contra Mallet/Mallory es mucho mayor que en contra de Eva.
• Oscar, es un oponente, similar a Mallet/Mallory, pero no necesariamente malicioso. Podría ser un sombrero blanco, pero todavía interesado en descifrar, modificar, sustituir o reproducir mensajes.
• Peggy, es un comprobador, y Víctor,⁸ un verificador, a menudo deben interactuar de alguna manera de demostrar que la transacción prevista ha tenido lugar en realidad. A menudo se encuentran en pruebas de conocimiento cero. Los nombres alternativos para el comprobador y el verificador son Pat y Vanna⁹ por Pat Sajak y Vanna White, los anfitriones de la rueda de la fortuna.
• Sam y Sally.¹⁰ Los observadores en diferentes marcos inerciales en la cinemática relativista.
• Sybil, es un atacante que controla un gran número de identidades seudónimas, por ejemplo, subvertir un sistema de reputación. Ver ataques Sybil.
• Trent, es un árbitro de confianza, es una especie de tercera parte neutral, cuyo papel exacto varía con el protocolo en discusión.
• Walter, es un guardián, puede ser necesario para proteger a Alice y Bob en algunos aspectos, dependiendo del protocolo que se discute.
• Wendy, es un denunciante, un interno con acceso a información privilegiada, que pueda estar en condiciones de divulgar la información.

Aunque un sistema de prueba interactiva no es exactamente un protocolo criptográfico, es suficientemente relacionados mencionar el elenco de personajes de sus características de la literatura:

• Arturo y Merlín: En los sistemas de prueba interactivos, el demostrador tiene capacidad computacional sin límites y, por tanto, se asocian a Merlín, el magopoderoso. Afirma la verdad de un enunciado, y Arturo, el rey sabio, le hace preguntas para verificar la reclamación. Estos dos personajes también dan el nombre de dos clases de complejidad, a saber, MA y AM.
• Un par similar de caracteres son Paul y Carole. Los personajes fueron introducidos en la solución del problema Veinte Preguntas,¹¹ donde "Paul", es quien hace las preguntas, lo fue por Paul Erdös y "Carole", quien las responde: era un anagrama de "oracle" ("oráculo" en inglés). Fueron utilizados más en ciertos juegos combinatorios en las investigaciones de Empujador y Selector respectivamente, y desde entonces se han utilizado en varios roles. 

análisis de frecuencias consiste en el aprovechamiento de estudios sobre la frecuencia de las letras o grupos de letras en los idiomas para poder establecer hipótesis para aprovecharlas para poder descifrar un texto cifrado sin tener la clave de descifrado (romper). Es un método típico para romper cifrados clásicos.

El análisis de frecuencias está basado en el hecho de que, dado un texto, ciertas letras o combinaciones de letras aparecen más a menudo que otras, existiendo distintas frecuencias para ellas. Es más, existe una distribución característica de las letras que es prácticamente la misma para la mayoría de ejemplos de ese lenguaje. Por ejemplo, en inglés la letra E es muy común, mientras que la X es muy rara. Igualmente, las combinaciones ST, NG, TH y QU son pares de letras comunes, mientras que NZ y QJ son raros. La frase mnemotécnica "ETAOIN SHRDLU" agrupa las doce letras más frecuentes en los textos ingleses. En español, las vocales son muy frecuentes, ocupando alrededor del 45 % del texto, siendo la E y la A las que aparecen en más ocasiones, mientras que la frecuencia sumada de F, Z, J, X, W y K no alcanza el 2 %. La regla mnemotécnica para el español sería "EAOSR NIDLC" o bien "EAOSN RILDUT".

En algunos cifradores, las propiedades naturales del texto plano se preservan en el texto cifrado. Dichos esquemas pueden ser potencialmente objeto de ataques de sólo texto cifrado.

Análisis de frecuencia para algoritmos de sustitución simple

En un algoritmo de sustitución simple, cada letra del texto plano se reemplaza por otra y una letra dada del texto plano siempre será transformada en la misma letra en el mensaje cifrado. Por ejemplo, todas las e se convertirán en X. Un texto cifrado con una alta frecuencia de letras X podría sugerir al criptoanalista que la X representa a la letra e.

El uso básico del análisis de frecuencias consiste en primero calcular la frecuencia de las letras que aparecen en el texto cifrado y luego asociar letras de texto plano a ellas. Una gran frecuencia de X podría sugerir que las X son e, pero esto no es siempre cierto, ya que las letras a y o tienen una frecuencia muy alta también en español. Sin embargo, si será difícil que lasX representen, en este caso a la k o a la w. Por ello, el criptoanalista podría tener que intentar varias combinaciones hasta descifrar el texto.

Estadísticas más complejas podrían ser usadas, como considerar los pares de letras o incluso tríos. Esto se realiza para proporcionar más información al criptoanalista. Por ejemplo, las letras q y u van casi siempre juntas en español, mientras que la q sola es muy rara.

Uso en la Historia

Primera página de Un manuscrito para el descifrado de mensajes criptográficos, de Al-Kindi.

La primera explicación bien documentada del análisis de frecuencias (de hecho de cualquier tipo de criptoanálisis) fue dada en elsiglo IX por el filósofo árabe Al-Kindi en Un manuscrito para el descifrado de mensajes criptográficos (Ibraham, 1992). Se ha sugerido que el estudio intento del Corán desveló que el árabe tenía una característica frecuencia de letras. Su uso se extendió y fue tan usado en Europa durante el Renacimiento que se inventaron pautas para tratar de burlar el estudio de las frecuencias. Éstas incluían:

• El uso de alternativas para las letras más comunes. Así, por ejemplo, las letras X e Y encontradas en el texto cifrado podrían significar E en el texto plano.
• Cifrado polialfabético, esto es, el uso de varios alfabetos para el cifrado. Leone Alberti parece ser el primero en sugerir esto.
• Sustitución poligráfica, esquemas donde pares o tríos de letras eran cifradas como una única unidad. Por ejemplo, elcifrado de Playfair, inventado por Charles Wheatstone a mediados del siglo XIX.

Una desventaja de todos estos intentos de derrotar el análisis de frecuencias es que complicaban tanto el cifrado como el descifrado de los datos, provocando errores.

Las máquinas de rotores de la primera mitad del siglo XX (por ejemplo, Enigma) eran esencialmente inmunes al análisis de frecuencias directo, aunque otros tipos de análisis consigueron decodificar los mensajes de tales aparatos.

El análisis de frecuencias sólo requiere un conocimiento básico de las estadísticas del texto plano y cierta pericia resolviendo problemas. Durante la Segunda Guerra Mundial, tanto los británicos como los estadounidenses reclutaron rompecódigos colocando puzzles y crucigramas en los periódicos y realizando concursos para ver quien los resolvía más rápidamente. Muchos de los cifrados usados por el Eje eran vulnerables al análisis de frecuencias (por ejemplo, algunos de los mensajes cifrados usados por los consulados japoneses). Los métodos mecánicos del conteo de letras y el análisis de las estadísticas (generalmente máquinas de tarjetas perforadas deIBM) fueron usadas durante la II Guerra Mundial, siendo probablemente los miembros del SIS norteamericano los pioneros. Hoy en día, el trabajo de contar letras y analizar frecuencias ha sido dejado a programas informáticos, que pueden realizar esas cuentas en segundos. Con la potencia computacional actual, los métodos de cifrado clásico proveen poca protección real para la privacidad de los mensajes.

Frecuencia de las letras en un texto inglés.

Frecuencia de las letras en un texto español.