Boletín ENIGMA - nº 32
1 Abril 2005
Boletín del Taller de Criptografía
de Arturo Quirantes Sierra
Dirección original: http://www.cripto.es/enigma/boletin_enigma_32.htm
CRIPTOGRAFÍA HISTÓRICA - Frecuencias y coincidencias (I)
CRIPTOGRAFÍA HISTÓRICA - Frecuencias y coincidencias (II)
CRIPTOGRAFÍA IMPRESENTABLE - Microseguridad para micropagos
LIBERTAD VIGILADA - La vertiente económica de "Echelon"
Nuevo mes, nuevo boletín. Ya vamos por el número 32, lo que en notación binaria
es 100000 (¿a que así suena más gordo?). Hoy los norteamericanos celebran el día
de los tontos (Fool´s Day), así que en esta ocasión tenemos una buena tontería
procedente de esas tierras. En "microseguridad para micropagos" tenemos un buen
ejemplo de una buena idea combinada con un mal algoritmo de cifrado, con los
resultados que ya podéis imaginaros. Pero como no todos los usamericanos son
tontos (!ni mucho menos!), hoy traemos a uno de los más ilustres: William
Friedman. De este genio de la criptografía, vencedor de la Púrpura japonesa,
traemos hoy una interesante pareja de artículos sobre uno de sus principales
descubrimientos: el Índice de Coincidencia (IC). Friedman fue uno de los
primeros en darse cuenta de la potencia que tienen las matemáticas como
herramienta de ruptura de códigos.
Seguro que más de uno querrá aplicar lo aprendido en esos artículos para hacer
programas informáticos. Os animo a ello. De hecho, sin comerlo ni beberlo, me he
encontrado con varios programas que implementan la segunda cifra de Garbo. Como
bien me habéis hecho notar, la solución que al problema que os planteé en el
boletín número 29 estaba equivocado. Lo corregí en el número anterior ... !y se
me coló otro fallo! Realmente esto dice mucho acerca del propio Garbo y las
penalidades que tuvo que soportar. Pero por fortuna, diversos lectores
programadores se pusieron a manos a la obra. El resultado es que ahora tengo
cuatro programas diferentes que emulan la cifra de Garbo. Así que he
desempolvado un viejo proyecto y he aprovechado para crear una nueva sección.
Bienvenidos a "La caja de herramientas", donde irán entrando todo tipo de
programas sobre criptografía y criptoanálisis. Por supuesto, daremos preferencia
a las creaciones de vosotros, amables enigmáticos, así que ya tardamos. Abrimos
boca con los cuatro programas Garbo: uno ejecutable y tres en código fuente (C++
y Perl).
Pero no me he parado aquí. Marchando otra vieja aspiración de este que escriba:
una sección de libros. En boletines anteriores han ido apareciendo diversas
críticas sobre libros del ramo. Los tenéis enlazados en la "Sección de libros",
junto con mi muy prestigiosa clasificación. ¿Acaso los hoteles no tienen
estrellas, y los hoteles tenedores? Pues aquí tenemos la clasificación de
rotores, hala. Y no se quedará en ello, sino que también iré incluyendo textos
digitales, ya sea en archivo o como enlace. Tenía una buena colección que
descargué de la biblioteca de Kriptópolis, pero los he perdido y el propio KP,
al cambiar de formato, también. Pero tranquis, que ya irán apareciendo. También
he recuperado un enlace antiguo a mi Tribuna Digital, algo desactualizada pero
aún en vigor (no tengo ni idea de por qué quité el enlace en la página
principal, sin duda un error por mi parte).
Por cierto, que ya que hablaba del "día de los tontos" (equivalente
norteamericano del 28 de diciembre, día de Inocentes, español), parece que nos
hayan gastado una inocentada los chinos que decían haber reventado el SHA-1. Un
mes después, sus noticias brillan por su ausencia. Parece que se los hubiese
tragado la tierra, porque no se sabe nada de sus supuestos logros. A ver si nos
han engañado como a chinos...
!Casi se me olvida! El jefe del Taller (ése soy yo) participará el próximo mes
de abril en las IV Jornadas sobre Seguridad de la Información, Ciberguerra y
Ciberterrorismo, que se celebrarán en las Islas Baleares los días 22 y 23. Se
celebrarán por videoconferencia en diversas ubicaciones de la Universidad
Nacional de Educación a Distancia (UNED). Servidor actuará el sábado 23 desde
Mahón (Menorca). Así que ya saben dónde me tienen: por la mañana en el Centro
Asociado de la UNED en Mahón, y por la tarde ... bueno, depende de dónde me
pille la playa más cercana.
CRIPTOGRAFÍA HISTÓRICA - Frecuencias y coincidencias (I)
Cifrar un texto es como barajar un mazo de cartas: hay que tomar un sistema
perfectamente ordenado y convertirlo en un segundo sistema lo más desordenado
posible por medio de una operación conocida y reversible. Si dicha operación
depende de un parámetro, éste es lo que llamamos "clave". Lo ideal sería que el
mensaje cifrado se confundiese con un batiburrillo perfectamente aleatorio. Pero
esto no es fácil de hacer. Desdibujar todos los patrones y pautas que subyacen
en todo idioma resulta tan difícil como borrar un texto escrito a lápiz sin
dejar la menor huella.
El problema se hace doblemente difícil si tenemos en cuenta que el ser humano
está dotado de una extraordinaria habilidad para descubrir esos patrones y
huellas. Unir los puntos de un dibujo es un entretenimiento para niños, pero a
poco que crecemos nos damos cuenta fácilmente de que forman un barquito velero
sin necesidad de usar el lápiz, ya que nuestro cerebro lo hace solito. Que le
pregunten al "descubridor" de los canales de Marte si no estaba convencido de
ver el Plan Hidrológico Marciano.
Un criptoanalista puede aprovecharse de la regularidad de normas en un idioma, y
por eso los mejores criptoanalistas de la historia han sido también buenos
literatos, artistas y filósofos. Un libro publicado en España en 1620 (!para
enseñar a entender a los mudos!) advierte contra el uso de sistemas de
sustitución monoalfabética sencilla. En español, por ejemplo, está bien claro
que si una palabra comienza por "qu", la siguiente letra sólo puede ser una
vocal como "e" (que, querer ...) o la "i" (quince, quinientos, Quirantes...).
Podemos incluso caracterizar la regularidad de un idioma mediante diversos
parámetros matemáticos. Si desde el siglo XVI se sabía que un sistema de
sustitución monoalfabética era vulnerable es precisamente porque sabían que
ciertas letras eran más frecuentes que otras. Un alfabeto que transformase la
letra E en otra distinta, digamos la V, nos daría un texto cifrado cuya letra
más probable sería la V (ya que la E es la letra más frecuente en el alfabeto
español). Es decir, los textos cifrados presentarían la letra V con tanta
frecuencia como aparecería la E en el lenguaje no cifrado. Y lo mismo vale para
las demás letras.
De hecho, una de las herramientas más valiosas para un ataque criptoanalítico es
el análisis de frecuencias. Consiste, sencillamente, en contar las frecuencias
del texto cifrado e intentarlas comparar con las del texto llano. Esto nos
plantea el primer problema de "contar" letras en el idioma español. ¿Cómo lo
hacemos? Normalmente se toman diversos libros del idioma, sean obras de ficción
o diccionarios. Esto hace que las frecuencias calculadas por diversos autores se
diferencien entre sí. Con todo, esas diferencias no son muy grandes.
Como ejemplo, vamos a dar las frecuencias de las letras en español, dadas por
dos autores. En primer lugar, Joaquín García Carmona (JGC), tal como las
presenta en su famoso Tratado de Criptografía de 1894; según el autor, la cuenta
la hizo él mismo a partir de varias páginas del Reglamento de Campaña. Por otro
lado, el libro Cryptanalysis de Helen Fouché Gaines (HFG), de 1939, basa sus
porcentajes en 10.000 letras de varias "páginas literarias". El signo - indica
un porcentaje muy bajo para calcularlo.
Estas son las frecuencias:
Letra A B C
D E F G H
I J K L M N Ñ
%(JGC) 11.9 1.1 4.8 5.0 14.6 0.7 1.3 0.3 7.1 0.6 - 5.5 2.8 7.2 0.1
%(HFG) 12.7 1.4 3.9 5.6 13.2 0.5 1.2 1.2 11.3 - - 5.9 2.7 7.0 -
Letra O P Q R S
T U V W X Y Z
%(JGC) 9.1 3.1 0.5 6.6 7.2 4.6 3.3 0.9 - 0.2 1.1 0.4
%(HFG) 9.5 2.4 1.2 6.3 7.6 3.9 4.6 1.1 - 0.1 1.1 0.4
Como ven, hay diferencias entre ambos conteos, ya que éstos se hicieron usando
textos diferentes, escasos en números, y en épocas diferentes. Seguro que hay
por ahí conteos de frecuencias mejores, y animo a los lectores a que me envíen
alguno. Pero incluso aquí podemos ver que hay ciertamente letras más y menos
frecuentes. De hecho, si ordenásemos las letras según su frecuencia, los datos
de ambos autores serían muy similares:
JGC: E A O S N I R L D C T U P M G B Y V F J Q Z
H X K W
HFG: E A O S N I R L D U C T M P B H Q G V Y J F Z X Ñ K W
(Gaines no incluye la Ñ en sus cuentas). Está claro que las letras E,A,O,S,N son
las "superpotencias", formando casi la mitad de todo el texto. Por contra, las
letras X,K,W prácticamente no se comen una rosca en español (por supuesto, en
otros idiomas la situación puede cambiar drásticamente).
Esto significa que los signos más frecuentes en un cifrado por sustitución
monoalfabética simple tienen todas las papeletas de corresponder a las letras E,
A, O. Tampoco significa que el signo más frecuente tenga que ser la E
necesariamente, ya que en mensajes cortos las frecuencias pueden no ser
estadísticamente significativas. Pero como mínimo, nos da un conjunto de
posibilidades bastante reducido. Curiosamente, son las letras menos frecuentes
las que a menudo marcan la diferencia. Por ejemplo, una palabra de tres letras
"123", donde 2 es un signo medianamente frecuente, 3 es muy frecuente y 1 es
bastante raro puede corresponder a la palabra QUE.
Podríamos hacer todo un curso sobre peculiaridades del lenguaje. Tratados de
criptoanálisis como los del español Carmona lista los conjuntos más numerosos de
dos, tres o cuatro letras, los comienzos y finales de palabra más frecuentes,
qué letra es más probable que acompañe a la letra E, sea por delante o por
detrás. Es el tipo de conocimiento que ha ayudado a los criptoanalistas hasta
prácticamente la Segunda Guerra Mundial. Pero no quiero convertir este boletín
en un aburrido tratado lingüístico. En su lugar, vamos a dar una sencilla
herramienta matemática llamada índice de coincidencia, descubierta por el
norteamericano Friedman en 1920. El IC nos indica hasta qué punto un texto
cifrado es aleatorio.
Supongamos un mensaje totalmente aleatorio. Vamos a suponer el alfabeto típico
español de 26 letras (contando la ñ, pero no las letras dobles rr, ll, ni la
letra w por ser extraordinariamente rara). Si miramos una letra cualquiera, la
probabilidad de que sea, digamos, una A es de 1/26, o el 3.85%. La siguiente
letra puede ser otra A, o bien ser otra cualquiera, con idéntica probabilidad.
Eso quiere decir que la probabilidad de obtener dos letras A seguidas es de
1/(26*26). También podemos decir que la probabilidad de obtener dos letras
seguidas iguales (sean las que sean) es de 1/26, ya que no nos interesa que sean
dos A, dos G, o dos letras en concreto.
Por contra, el lenguaje español no funciona así. Las diferentes letras no son
igualmente probables. Si tomamos dos letras de un texto en español (no seguidas,
sino de diferentes lugares del texto), es más probable que sean dos A que dos N.
Tomemos los datos de Carmona. La letra A aparece con una probabilidad del 12%, y
la N con una del 7%. Eso significa que la probabilidad de obtener dos A es del
12*12/(100*100), esto es, el 1.44%; la de obtener dos H es del
7*7/(100*100)=0.49%; la de obtener una A y una H es del 12*7/(100*100)=0.84%.
En lugar de preocuparnos por la probabilidad de cada ocurrencia de una letra, o
de un par de letras, vamos a promediar un poco. Vamos a responder a la siguiente
pregunta: ¿cuál es la probabilidad de encontrar dos letras cualesquiera iguales
en dos puntos cualesquiera de un texto escrito en el idioma español? Cuando el
texto era aleatorio, la probabilidad era de 1/26 = 0.0385 (el 3.85%). Ahora la
cosa está más liada, ya que tendremos que ver qué probabilidad hay de que salga
AA; de que salga BB; de que salga CC; y así hasta ZZ.
Parece un poco complicado, pero es sencillo de calcular si partimos de las
frecuencias de ocurrencia de las letras en particular. Si p(A) es la
probabilidad de que aparezca una A (lo que, en español, hemos visto que es igual
al 12%), basta calcular la siguiente suma:
Kp =
p(A)*p(A)+p(B)*p(B)+p(C)*p(C)+ ... +p(Y)*p(Y)+p(Z)*p(Z)
El resultado de la suma, que se denota como Kp (y se lee "kappa sub p") es
característico de cada idioma. He aquí unos ejemplos:
LENGUAJE KAPPA
Español 0,0775
Inglés 0,0667
Francés 0,0778
Alemán 0,0762
Italiano 0,0738
Ruso 0,0529
Aleatorio 0,0385 (para alfabeto de 26 letras)
Los datos están sacado del "Handbook of Applied Cryptography" de Menezes, van
Oorschot y Vanstone; David Kahn cita los mismos números en su Codebreakers, y
los toma de la obra original de Friedman ("The Index of Coincidence and its
Applications in Cryptography", Riverbank Publications nº 22, 1920). Como verá
fácilmente el lector, los kappa de los lenguajes occidentales son bastante
similares, con excepción del ruso, cuyo alfabeto tiene 30 caracteres. Lo más
llamativo es que cualquiera de estos lenguajes tiene un kappa sensiblemente
superior al de un texto aleatorio. Es decir, kappa es un indicativo de que el
texto sigue un patrón regular.
Kappa es un valor característico del lenguaje. Podemos usar algo parecido para
un texto en concreto. Imagínense un texto en español de N letras de longitud.
Vamos a contar el número de letras A que contiene, y sea f(A) ese número. De
modo análogo, f(B) será el número de veces que aparece la B, f(C) el ... bueno,
creo que ya lo han pillado. Definimos el ÍNDICE DE COINCIDENCIA (IC) del mensaje
como:
IC = [f(A)*(f(A)-1) + f(B)*(f(B)-1) ... -
f(Z)*(f(Z)-1)]/[N*(N-1)]
El IC tiene diversas aplicaciones en criptoanálisis. Vamos a verlas en la
segunda parte.
CRIPTOGRAFÍA HISTÓRICA - Frecuencias y coincidencias (II)
Una de las preguntas que se hacen los aficionados a la criptografía es ¿cómo sé
si un texto está descifrado? Imagínense que se está montando un ataque de fuerza
bruta contra DES. Imaginemos que probamos las 2^56 claves posibles. ¿Qué
hacemos, leemos los mensajes descifrados uno por uno hasta dar con el correcto?
El IC nos da un indicativo muy útil. Basta con ir calculando el IC de cada
mensaje descifrado. Si se parece al de un texto aleatorio (0,0385) es que no
hemos acertado, pero si se parece al de un lenguaje conocido es una primera
señal indicativa. No es a prueba de fallos, pero al menos un IC del orden de
0.07 será para nosotros como una luz roja, un aviso de "eh, aquí tenemos algo"
Esto es lo que hizo, por ejemplo, James J. Gillogly en 1995. En un artículo
publicado en Cryptologia, se dedicó a simular todas las posiciones de una
máquina Enigma. Para cada una de ellas, intentaba descifrar un texto cifrado con
anterioridad; el IC le iba indicando cuándo atinaba con la posición correcta de
los rotores. El éxito dependía tanto de la longitud del texto como del número de
conexiones en el tablero de la Enigma. Suponiendo que no había conexiones en el
tablero, el porcentaje de éxito era del 30% para mensajes de 160 letras, y hasta
del 80% para mensajes más largos (600-800 letras). Gillogly alabó la costumbre
alemana de cifrar mensajes cortos y usar varias conexiones en el tablero, lo que
reducía sensiblemente la eficacia de este ataque por fuerza bruta. No parece que
los alemanes estuviesen al tanto del truco del IC, pero de todos modos era una
buena práctica criptográfica. Con todo, considerando que los operadores alemanes
se saltaban esas normas a la torera en tiempos de guerra, Gillogly concluyó que
este ataque estaba dentro de los límites de los criptólogos de Bletchley Park.
Además de indicarnos el grado de "aleatoriedad" de los mensajes, en ocasiones el
IC puede darnos una idea de cómo es el cifrado. Imagínense, por ejemplo, que
tenemos un sistema de sustitución monoalfabética simple. Ahora las letras han
sido cambiadas por signos diferentes, pero la frecuencia de esos signos
permanece. Es decir, si cambiamos A por + , el signo + aparecerá tantas veces en
el texto cifrado como la A en el texto llano. Esto nos da un interesante
resultado: El IC de una cifra de sustitución monoalfabética simple es igual que
la del idioma que cifra. Bueno, debería haber dicho "aproximadamente igual", ya
que en un texto dado las frecuencias de las letras pueden no ser exactamente
iguales a las que se les supone. Pero si el texto es razonablemente largo, las
diferencias serán mínimas.
En el caso de un sistema polialfabético, la cosa cambia. En los sistemas
polialfabéticos no se usa un sólo alfabeto para cifrar, sino varios. En la
primera cifra de Garbo (ver Boletín ENIGMA nº 28) se usaban cinco alfabetos. En
ese caso, la cosa se tuerce, porque una A en un texto cifrado podía corresponder
a las letras G,E,A,Q,D, dependiendo del alfabeto que se utilice. La cifra de
Vigenère (ver Boletín ENIGMA nº 13) no es más que una serie de cifras de César,
de forma que sabiendo cuántas letras tiene la palabra clave se puede desmontar
fácilmente. La necesidad de atacar la cifra de Vigenère dio lugar al llamado
test de Kasiski, o test kappa, que engloba en su seno la teoría del IC.
Kasiski se dio cuenta de que, en ocasiones, se cifran partes iguales de un texto
con la misma porción de la clave. Copiando el ejemplo de David Kahn, supongamos
el texto "to be or not to be" cifrado con una Vigenère con clave RUN:
Clave:
RUNRUNRUNRUNRUNRUNRUNRUNRUNRUN
Texto llano: tobeornottobethatisthequestion
Texto cifrado: KEIVIEEIGKIOVNURNVJNUVKHVMGZIA
Véase como, en dos ocasiones, el texto "tobe" se cifra con la clave "RUNR" para
dar el mismo texto cifrado "KEIV". Asimismo, el texto "th" se cifra en dos
ocasiones con la clave "UN" para dar el texto cifrado "NU". Una forma de romper
una cifra polialfabética es tomar dos mensajes cifrados con la misma clave, y
escribir uno debajo del otro. El problema era que los mensajes han de estar
"alineados", de forma que las letras de la misma columna hayan sido cifradas con
la misma parte de la clave.
Como lo mejor es un buen ejemplo, voy a piratear a David Kahn de nuevo (lo
siento, David, hoy estoy de un vago subido). Vamos a usar como clave la frase
THE BARD OF AVON IS THE AUTHOR OF THESE MILES. Cifremos dos textos de la
siguiente forma:
Clave:
THEBARDOFAVONISTHEAUTHOROFTH
Texto llano 1: ifmusicbethefoodofloveplayon
Texto cifrado 1: BMQVSZFPJTCSSWGWVJLIOLDCODHU
Clave:
EBARDOFAVONISTHEAUTHOROFTHESE
Texto llano 2: nowisthewinterofourdiscontent
Texto cifrado 2: RPWZVHMERWABWKVJOOKKWJQTGAIFX
El criptoanalista solamente conoce ambos textos cifrados. Como verá el lector,
los dos textos han sido cifrado con partes diferentes de la frase clave. Puede
que el cifrador lo haya hecho adrede para dificultarnos la tarea. Nuestro
criptoanalista supondrá que ambos mensajes han sido cifrados con la misma clave
(si no es así, qué se le va a hacer), y que están alineados correctamente. Es
decir, partamos del supuesto que la clave para el texto 2 es la misma:
THEBARDOF... Si eso fuese así, significaría que la primera letra de cada texto
cifrado (B,R) han sufrido la misma sustitución monoalfabética. Análogamente, las
segundas letras (M,P) formarían parte de una segunda sustitución monoalfabética.
Si en lugar de dos textos tuviésemos muchos textos alineados, cada columna
formaría una sustitución monoalfabética que sería fácil de obtener.
En nuestro caso, tendríamos:
Texto cifrado 1: BMQVSZFPJTCSSWGWVJLIOLDCODHU
Texto cifrado 2: RPWZVHMERWABWKVJOOKKWJQTGAIFX
Y ahora viene lo interesante. Si hemos acertado, la probabilidad de que en una
columna dada tengamos las mismas letras es la misma que la del idioma de
partida. Pero si no, la probabilidad sería más cercana a la de un texto
aleatorio. Así que vamos a ver cuántas columnas tienen letras iguales. Pondremos
un asterisco para denotar los lugares de coincidencia. Pero aquí no hay ninguna
coincidencia. Así que estos textos no están alineados.
Como ejemplo a los incrédulos, vamos a superponer dos líneas de este mismo
artículo. Tomaré una frase al azar del primer párrafo, una del segundo, y vamos
a contar las coincidencias. Ambas frases tendrán una longitud de 66 letras, así
que si no les miento habremos de obtener un promedio de 66*0,0775~5
coincidencias. Lo que sale es:
hemosacertadoperosiseparecealdeunlenguajeconocidoesunaprimeraseñal
conexioneseneltableroloquereduciasensiblementelaeficaciadeesteataq
** * *
*
Cinco coincidencias, tal como os prometí. Y juro por mi oso de peluche que lo he
hecho al azar, no sabía cuántas iban a salir. Podía haber obtenido cuatro, o
seis, o incluso siete, pero en esta ocasión lo hemos niquelado.
Volvamos a nuestros textos cifrados. Probemos desplazando el texto cifrado 2 una
posición hacia la derecha.
Texto cifrado 1: BMQVSZFPJTCSSWGWVJLIOLDCODHU
Texto cifrado 2: RPWZVHMERWABWKVJOOKKWJQTGAIFX
Coincidencias:
*
Bueno, ya tenemos una. ¿Es esto significativo? Veamos. La kappa de un texto en
inglés es de 0,0667, y para un texto aleatorio es de 0,0385. Tenemos 27
caracteres alineados, de forma que cabría esperar 27*0,0667=1,8 coincidencias,
es decir, unas 2. En el caso de un mal alineamiento, saldrían en promedio
27*0,0385=1,03, o sea, 1. En este caso, el texto no es tan largo como para poder
estar seguros, y es posible que hayamos acertado pero tengamos sólo una
coincidencia en lugar de dos por puro azar. Es decir, esto no parece estar
alineado, pero tampoco podemos poner la mano en el fuego.
Vamos, entonces, a poner esa alineación en el apartado de "posibles", y probemos
otra posibilidad:
Texto cifrado 1: BMQVSZFPJTCSSWGWVJLIOLDCODHU
Texto cifrado 2: RPWZVHMERWABWKVJOOKKWJQTGAIFX
Coincidencias: *
**
!Bingo! Tres coincidencias. Y resulta que en este caso es el alineamiento
correcto. En efecto, para el texto cifrado 2 la clave que se usaba comenzaba
comenzaba por la tercera letra de la frase de contraseña, en tanto que el texto
cifrado 1 usaba la primera:
Clave (texto 1): THEBARDOFAVONISTHEAUTHOROFTH
Clave (texto 2): EBARDOFAVONISTHEAUTHOROFTHESE
Texto cifrado 1: BMQVSZFPJTCSSWGWVJLIOLDCODHU
Texto cifrado 2: RPWZVHMERWABWKVJOOKKWJQTGAIFX
Ahora tenemos los mensajes alineados. El test kappa, basado en coincidencias,
puede usarse para textos y claves mucho más largos. Permite así obtener mensajes
alineados (o "mensajes en profundidad") para reventar la clave.
Veamos otra aplicación. Supongamos que tenemos tres textos cifrados. Sabemos que
los tres son sistemas de sustitución monoalfabética simple, pero no sabemos si
son la misma sustitución para cada texto o no. Podemos usar el text kappa para
ver si están correlacionados. El mecanismo es similar al anterior.
Podemos incluso usar el truco de las coincidencias para determinar en ocasiones
si el sistema es polialfabético. Supongamos que tenemos un texto de L caracteres
de longitud. Sea n el número de caracteres del lenguaje (n=26 para el español),
Ka el valor de kappa para un texto aleatorio (1/n = 1/26 = 0,0385), Ke el valor
de kappa para el idioma considerado (Ke=0,0775 para el español), y supongamos
que el texto está cifrado mediante un sistema polialfabético que emplea X
alfabetos (si X=1, tenemos la sustitución monoalfabética de toda la vida). En
ese caso, el valor estimado del IC para dicho texto viene dada por la fórmula:
1 L-X
X-1 L
E(IC) = - * ----- * Ke + ----- * ----- * Ka
X
L-1 X
L-1
Si el texto es lo bastante largo, podríamos tabular E(IC) para varios valores de
X, y contrastarlo con el valor del IC. El valor de X correcto sería aquél para
el que E(IC) se aproxime más a IC. Como podréis comprobar, no es a prueba de
fallos. Necesitamos un texto largo, y también que X no tenga un valor demasiado
largo, ya que de lo contrario se aproximaría mucho a un texto aleatorio y no
sería fácil distinguirlo. Pero como mínimo, nos sirve de primer intento. Podemos
comprobar fácilmente si la sustitución es monoalfabética (X=1) o no, por
ejemplo.
Imagino que a estas alturas habréis captado la importancia de las coincidencias
para la ayuda en la resolución de mensajes. El IC y el asociado test de kappa
fueron una gran ayuda para convencer a los criptoanalistas de que la matemática
era una herramienta tan potente en su trabajo como la lingüística. Y, como
seguro que estáis a estas alturas con ganas de aplicar estas nuevas
herramientas, os reto a que plasméis vuestras ideas. Podéis fácilmente
implementar un programa (o una hoja de cálculo) que calcule el valor de kappa
para un texto cualquiera, o el valor estimado E(IC) para calibrar si la cifra
puede ser monoalfabética o no. Podéis atreveros a alinear diversos textos, o
incluso a calcular las frecuencias de letras y el IC de un texto en español,
para poder comprobar si los datos de IC que os doy son correctos. A lo mejor,
los textos de los médicos y de los abogados tienen valores de IC levemente
distintos. Que funcione la imaginación. ¿Quién es el primero que se apunta?
CRIPTOGRAFÍA IMPRESENTABLE - Microseguridad para micropagos
Uno de los aspectos menos desarrollados en el mundo del comercio electrónico es
el de los micropagos. En la actualidad, las páginas web seguras (https) nos
permiten hacer compras on-line con razonables garantías de seguridad. Pero no
vamos por ahí con nuestro ordenador a cuestas, ¿verdad? Existen muchas
circunstancias en las que sería deseable un medio seguro para hacer pagos
pequeños: máquinas expendedoras de bebidas, billetes de autobús o metro,
quioscos de prensa ... la lista es muy larga. Los beneficios económicos son muy
grandes, y también las ventajas al usuario en cuanto a comodidad: no tener que
parar en el peaje de la autopista, prescindir de las incómodas monedas, acabar
con los típicos problemas de "no tengo cambio", y suma y sigue.
En la actualidad, se están desarrollando sistemas de micropago usando el
teléfono móvil. El móvil es una tecnología conocida, muy introducida en el
público en general, y micropagar con móviles se vería como un servicio más. La
seguridad sería relativamente alta (los algoritmos de cifrado GSM son
vulnerables, pero no entremos ahora en esto). Pero ¿qué pasa con los que no
tenemos móviles, o no queremos llevarlos encima todo el rato? Necesitamos
dispositivos novedosos que nos permitan comprar electrónicamente por la calle,
en cantidades pequeñas, y con seguridad. Y eso no es fácil. Imagínense una
sencilla tarjeta monedero, como las que se compran para llamar desde teléfonos
públicos, pero que pueda servir para todo tipo de pago. Algunos podrían
argumentar que falsificar una de estas tarjetas es una tontería, ya que el valor
económico que obtendría el falsificador sería escaso. A fin de cuentas, nadie se
dedica a falsificar monedas.
Pero la falsificación de medios de micropago puede hacerse con mayor facilidad
que los billetes. Al contrario que los billetes o las monedas, que precisaría de
ingenios de alta tecnología o difíciles de obtener (prensas, tinta y papel
especiales, marcas de agua, etc), una tarjeta puede duplicarse con menos medios.
Los expertos seguro que podrán discutírmelo, pero el caso es que la copia de las
bandas magnéticas de las tarjetas de crédito son el pan nuestro de cada día, así
que seguro que no me equivoco por mucho. Y se están desmantelando redes de
falsificación de billetes de euros (los más seguros que supuestamente existen),
así que el problema de los micropagos resulta tema nada baladí.
Existe, además, la pretensión de que los micropagos sean sencillos. Eso
significa que no tengamos que coger la tarjeta y meterla en un tarjetero, sino
que el lector se active a distancia. Esto se conseguiría mediante dispositivos
RFID (Identificadores mediante radiofrecuencia). Los RFID están en la actualidad
a punto de saltar a la arena comercial como medio para facilitar el inventariado
de bienes y para facilitar la compra en el cajero del supermercado, algo así
como un código de barras avanzado. Otras aplicaciones incluyen su uso en
documentos de identificación como DNI o pasaportes, que podrían incluir
identificadores biométricos. Esta tecnología está siendo muy cuestionada por sus
potenciales amenazas contra la privacidad de los usuarios.
Pero otro día hablaremos de este problema, apasionante donde los haya. Volvamos
a los micropagos. Lo que quiero comentarles hoy es una noticia que salió hace
poco tiempo. Se refiere a un dispositivo denominado Digital Signature
Transponder (DST). Se trata de un medio de micropago desarrollado por Texas
Instruments para, entre otras aplicaciones, pagar gasolina en las estaciones de
servicio o como inmovilizador electrónico. En la actualidad, el sistema DST se
aplica en más de 150 millones de inmovilizadores electrónicos de coches, o sea
que estamos hablando de usos a lo grande; por no hablar de los más de 10.000
lugares donde se pueden usar para comprar combustible. Utiliza tecnología RFID,
de forma que el usuario solamente tiene que acercar su llave de encendido al
surtidor, y éste le "microcobrará" sin necesidad de contacto físico. Una vez
hecho, el conductor toma su llave, la activa, monta en su coche y se va feliz y
contento.
Esa es la teoría. En la práctica ... sí, seguro que ya ha averiguado usted por
dónde van a ir los tiros. Investigadores de la Universidad John Hopkins y de los
RSA Laboratories publicaron un ataque contra el sistema DST. Usando sus propias
palabras "lo conseguimos usando equipos baratos de baja tecnología, y con
conocimientos mínimos en radiofrecuencia. Esto sugiere que un atacante con
recursos modestos puede emular un DST después de un breve barrido de corto
alcance ... concluimos que la protección criptográfica proporcionada por el
dispositivo DST es débil".
¿Protección criptográfica? Vamos a ver cómo funciona. La idea es que el
inmovilizador efectúa una serie de interrogatorios electrónicos a un
traspondedor RFID insertado en la llave de ignición. Si el interrogatorio no se
lleva a cabo correctamente, el sistema de inyección de combustible del coche se
bloquea. Si lo queremos usar para pagar el combustible, se efectúa una cadena de
interrogatorios similares.
Supongamos un aparato lector, sea el que bloquea el coche, o bien el surtidor de
gasolina donde haremos el pago. El DST responde al típico "¿quién es?" emitiendo
un identificador de 24 bits. Sería el equivalente del "soy yo, abre". Claro que
cualquiera puede decir que soy yo, así que el DST tiene que autenticarse, es
decir, convencer al lector de que es él. Para eso, el DST tiene una clave
secreta de 40 bits. El proceso sería el siguiente:
1) El lector envía una cadena de bits denominada reto ("challenge") al
dispositivo DST. Sería algo así como una pregunta a responder.
2) El DST cifra el "reto" con una clave secreta de 40 bits que almacena en su
interior. El resultado se trunca, y los primeros 24 bits formarán la respuesta
que se envía al lector.
3) El lector recibe la respuesta. Si es correcta, todo va bien. Si no, ya puede
usted ir poniendo las manos en alto y llamar a su abogado.
La seguridad del proceso de interrogatorio digital reside, por tanto, en la
fortaleza del cifrado. Si fuese perfecto, necesitaríamos 2^40 pruebas para dar
con la clave secreta correcta. Y por supuesto sería difícil que tal intento
pasase desapercibido. Sin embargo, los investigadores consiguieron recuperar la
clave secreta. ¿Cómo? Pues como siempre, trasteando el algoritmo de cifra y
buscando sus puntos débiles. Descubrieron que podían obtener la clave mediante
un conjunto de interrogatorios que llevarían una hora. En el caso de
interrogatorios más cuidadosamente escogidos, y dependientes de los intentos
anteriores (lo que se denomina un ataque de texto llano escogido), se puede
reducir el tiempo a pocos minutos ... incluso segundos si se utiliza un PC en
lugar de sistemas FPGA.
No dan muchos detalles, ya que lo dejan para "una versión futura de este
trabajo". Esperemos que las leyes norteamericanas se lo permitan. Con todo,
afirman que, tras recuperar la clave, "clonar" un DST (es decir, simular una
respuesta para engañar a un aparato lector) estaba chpuado. De hecho, lo
comprobaron extrayendo una clave de uno de los propios investigadores. Es decir,
uno de ellos hizo de conejillo de indias y compró gasolina en una estación de
ExxonMobil múltiples veces, y con éxito. Otro conejillo, digo investigador,
cedió su Ford Escape para hacer otra prueba. Con una copia tradicional de la
llave (es decir, solamente la pieza de metal) y su ataque criptoanalítico,
pusieron en marcha el vehículo. Así de sencillo.
Afortunadamente, esta gente es del bando honrado. O al menos eso afirman. Por un
lado, pretenden reforzar una vez más la idea de que la seguridad mediante
oscuridad no es una buena idea. En efecto, pretender que nadie va a saber cómo
es el algoritmo de cifra es una estupidez. ¿Acaso los fabricantes no conocen las
técnicas de ingeniería inversa? Pues nada, que no. Creen que, si no publican las
especificaciones en papel, nadie logrará descubrir lo que contiene la caja
negra. Citan incluso uno de los primeros ejemplos conocidos de ingeniería
inversa: la reconstrucción de la máquina japonesa de cifra Purple por William
Friedman durante la Segunda Guerra Mundial.
Por otro lado, dan ideas para mejorar la eficacia del sistema. Como ellos mismos
dicen "nuestro ataque de la cifra DST no significa para nada que se haya
desmantelado por completo la seguridad de la red SpeedPass, ni implica el robo
fácil de automóviles." Otros diseños de la red (como estudios del comportamiento
del comprador en busca de patrones sospechosos) interactúan para aumentar la
seguridad del sistema. Tras indicar diversos casos en los que un atacante puede
salirse con la suya, estos investigadores dan una solución sencilla: pasen de
cifras bobas de 40 bits y pásense a algoritmos más sólidos como el AES (Advanced
Encryption Standard, sucesor del DES) con su bonita clave de 128 bits. Será un
problema cambiar todos los DST, lectores y demás parafernalia, pero eso es
problema de los fabricantes. De hecho, hay un sistema similar, el SECT de
Philips, que usa una clave de 128 bits; por desgracia no se conoce el algoritmo
de cifra, pero muestra que puede irse más allá de los risibles 40 bits de la
criptografía débil.
No mostraré aquí los detalles del ataque a la cifra de 40 bits. El lector que
quiera aburrirse con ella puede leer el artículo "Security Analysis of a
Cryptographically-Enabled RFID Device", de Steve Bono, Matthew Green, Adam
Stubblefield, Ari Juels, Avi Rubin y Michael Szydlo, disponible en
http://rfidanalysis.org/. Si es usted de
esos que presume de abrir la puerta del coche a distancia pulsando un botoncito
en la llave de ignición de su coche, le sugiero que se lo piense dos veces. Y
por supuesto, para pagar la gasofa, pasta o plástico. Feliz viaje.
LIBERTAD VIGILADA - La vertiente económica de "Echelon"
[Extraído del libro "Libertad Vigilada", de Nacho García Mostazo, con permiso
del autor]
Primera parte, capítulo 22:
El volumen elaborado por Duncan Campbell dedicaba un capítulo especial al
espionaje económico, que se iniciaba recordando cómo los eurodiputados había
participado en el debate sobre las tecnologías aplicadas al control político
previsto para septiembre de 1998. La discusión en aquel Pleno acabó centrándose
en "las relaciones transatlánticas y el sistema 'Echelon' ", debido sobre todo
al impacto que había causado entre los diputados el descubrimiento de "Echelon"
a través del informe de la Fundación Omega. En ese debate estuvo presente el
comisario de Telecomunicaciones de la Comisión Europea, Martin Bangeman, quien
afirmó que "si existiera este sistema, sería un ataque intolerable contra las
libertades individuales, la competencia y la seguridad de los Estados". El
"informe Campbell" reproducía aquella categórica afirmación de Bangeman y, a
continuación, afirmaba con cierta ironía: "La existencia de 'Echelon' se ha
descrito más arriba en el capítulo 3." El efecto buscado por el investigador
escocés logró su objetivo. Las palabras del comisario europeo sobre el ataque a
la competencia resonaban una y otra vez según Campbell desgranaba su informe y
añadía nuevos datos, pruebas y documentos para demostrar que Estados Unidos
favorece a sus empresas gracias a "Echelon". [1]
Norteamérica empezó a usar la inteligencia con fines económicos en 1970, según
el periodista escocés. En esa fecha, el Consejo Asesor de Inteligencia Exterior
de Estados Unidos recomendó que "se considere el espionaje económico un aspecto
de la seguridad nacional, con un grado de prioridad equivalente al espionaje
diplomático, militar o tecnológico". Para demostrarlo, citaba al antiguo
director ejecutivo del Consejo, que lo confirmó al Canal 4 del Reino Unido en
1993. Así, la NSA, la CIA y el Departamento de Comercio de Estados Unidos
crearon un nuevo departamento secreto: la "Oficina de Enlace de Inteligencia".
Su misión "era gestionar el 'espionaje exterior' de interés para el Departamento
de Comercio", según Duncan Campbell, quien también asegura que "su reglamento
general demuestra que estaba autorizada a recibir y gestionar información
secreta de la NSA. La creación de esta oficina instituyó un mecanismo formal por
el que podía utilizarse la información obtenida por la Agencia de Seguridad
Nacional en apoyo de los intereses económicos y comerciales" de Estados Unidos.
[2]
La existencia de este operativo de espionaje económico está probada incluso por
los medios de comunicación norteamericanos. El "informe Campbell" recogía una
noticia publicada en noviembre de 1996 por el periodista Scott Shane, del diario
Baltimore Sun, donde aseguraba que "antiguos funcionarios de los servicios de
inteligencia y otros expertos afirman que el Departamento de Comercio filtra
regularmente información obtenida por medio de espionaje a las empresas
estadounidenses [...] para ayudarlas a obtener contratos en el extranjero".
Entre las pruebas obtenidas por Shane se citan las "actas de una reunión
celebrada en agosto de 1994 en el Departamento de Comercio para identificar
contratos importantes sujetos a concurso público de licitación en Indonesia con
el fin de ayudar a las empresas estadounidenses a conseguir su adjudicación. Un
empleado de la CIA [...] habló en dicha reunión; 5 de las 16 personas incluidas
en la lista de distribución rutinaria de las actas pertenecían a la CIA". [3]
Duncan Campbell expuso más casos concretos de espionaje económico. Por ejemplo,
afirmó que "en 1994, la NSA interceptó llamadas telefónicas entre (la empresa
francesa) Thomson-CSF y (el Gobierno de) Brasil en relación con SIVAM, un
sistema de vigilancia (vía satélite) de 1.300 millones de dólares para la selva
tropical amazónica. Esta empresa habría sobornado presuntamente a miembros del
comité de selección del Gobierno brasileño. El contrato se adjudicó a la empresa
estadounidense Raytheon Corporation, que posteriormente declaró (a través de una
nota de prensa) que 'el Departamento de Comercio trabajó intensamente en este
proyecto en apoyo de la industria estadounidense' ". Para demostrar la relación
que une esta empresa con la Agencia de Seguridad Nacional, Duncan Campbell
desvelaba que "Raytheon presta servicios de ingeniería y mantenimiento a la
estación de interceptación de satélites 'Echelon' que tiene la NSA en Sugar
Grove". [4]
Otra noticia publicada también por el diario Baltimore Sun y citada en el
"informe Campbell" afirmaba que "la NSA interceptó todos los faxes y llamadas
telefónicas transmitidos a través de un satélite de telecomunicaciones comercial
entre el consorcio europeo Airbus, la compañía aérea nacional saudí y el
Gobierno de Arabia Saudí. La agencia descubrió que los agentes de Airbus
ofrecían sobornos a un funcionario saudí y pasó la información a los
funcionarios estadounidenses que presionaban a favor de la oferta de Boeing Co.
y McDonell Douglas Corp., que acabó por adjudicarse el concurso de 6.000
millones de dólares". [5]
El informe elaborado por el periodista escocés también mencionaba que la
legislación británica obliga al GCHQ, su agencia de inteligencia de señales, a
interceptar las comunicaciones internacionales "en interés del bienestar
económico del Reino Unido [...] en relación con las acciones o intenciones de
personas residentes fuera de las islas británicas". Como consecuencia, el
Gobierno británico remitió una carta a la Comisión Europea donde admitía que la
Ley de Interceptación de las Comunicaciones de 1984 permite espiar el tráfico de
señales por "seguridad nacional, salvaguarda del bienestar económico nacional y
prevención y detección de crímenes graves", aunque negaba haber cooperado con
Estados Unidos para espiar en contra de los intereses de empresas europeas. La
misiva llevaba fecha del 31 de marzo de 2000, apenas un mes después de que se
presentara el "informe Campbell", y fue remitida al entonces comisario europeo
de Empresas, Erkki Liikanen, quien compareció el 30 de marzo ante el Parlamento
Europeo para explicar su contenido. Liikanen dijo que el Ejecutivo de Londres
también admitía la cooperación "con sus socios de ultramar, incluido Estados
Unidos" pero subrayaba que "todas las operaciones llevadas a cabo por las
fuerzas estadounidenses estacionadas en territorio británico lo son con pleno
conocimiento y consentimiento del Gobierno y son realizadas conforme a las
legislaciones británica y estadounidense". [6]
[1]. Duncan Campbell, "Interception Capabilities 2000". Op. cit.
[2]. Reportaje "The Hill" para el programa Dispatches. Channel 4 Television
(Reino Unido), 6 de octubre de 1993. Citado en Duncan Campbell, "Interception
Capabilities 2000". Op. cit.
[3]. Scott Shane, "Mixing Business with Spying. Secret Information is Passed
Routinely to U.S.". Baltimore Sun, 1 de noviembre de 1996. Citado en Duncan
Campbell, "Interception Capabilities 2000". Op. cit.
[4]. Duncan Campbell, "Interception Capabilities 2000". Op. cit.
[5]. Scott Shane y Tom Bowman, "America´S Fortress of Spies". Baltimore Sun, 3
de diciembre de 1995. Citado en Duncan Campbell, "Interception Capabilities
2000". Op. cit.
[6]. Agencia Efe. "UE-ESPIONAJE / Londres admite que puede espiar por su
bienestar económico." Teletipo. Bruselas, 30 de marzo de 2000.
El
boletín ENIGMA es una publicación gratuita del Taller de Criptografía, y se rige
por las normas de la licencia de Creative Commons Reconocimiento-NoComercial-CompartirIgual.
Se permite su libre copia, distribución y comunicación para fines no lucrativos,
citando nombre y referencia.
Para más información, véase la licencia Creative Commons en sus formas reducida
y completa:
http://www.cripto.es/licencia/deed.es.htm
http://creativecommons.org/licenses/by-nc-sa/2.5/es/legalcode.es
PARA DARSE DE ALTA: envíe un mensaje a la dirección alta arroba cripto.es
añadiendo las palabras alta_enigma en el asunto (subject).
PARA DARSE DE BAJA, envíe un mensaje a la dirección baja arroba cripto.es
añadiendo las palabras baja_enigma en el asunto (subject)
Para comentarios a este boletín (dudas, preguntas, consultas, críticas,
noticias, colaboraciones, etc.), estoy a su disposición en la dirección
noticias arroba cripto.es
Página del Boletín Enigma (incluyendo números atrasados):
http://www.cripto.es/enigma.htm
(c) Arturo Quirantes 2007
Vuelta a la Página principal del Boletín ENIGMA