A modo de continuación de la serie de post sobre criptografía en Python, hoy veremos como hacer criptoanálisis Vigenère y Autoclave. Es importante que os miréis el primer post, ya que partiremos de la implementación de Vigenère vista anteriormente.
El cifrado de Vigenère es un método de cifrado por sustitución polialfabética que utiliza una serie de diferentes cifrados de sustitución monoalfabéticos basados en el uso de una clave secreta. El cifrado de Vigenère fue desarrollado en el siglo 16 por Blaise de Vigenère, y fue conocida como la cifra indescifrable durante casi 3 siglos, o al menos así fue hasta que apareció el ataque de Kasiski. Vigenère emplea una clave de longitud menor o igual que el texto, si la clave es menor se repite hasta tener la misma longitud. La clave se usa para determinar qué letra del alfabeto se usa para cifrar cada letra del mensaje original empleando el cifrado cesar. A modo de ejemplo:
ej: m:HOLAATODOS --> HOLAATODOS
c:dos --> DOSDOSDOSD
m: --> KCDDOLRRGV
Podemos ver que se trata de una sustitución poli alfabética, ya que la «A» se sustituye en una ocasión por la «D» y en otra por la «O». Al ser un cifrado de sustitución poli alfabético no es posible aplicar directamente el método de «análisis de frecuencia» que empleábamos para el criptoanálisis de cesar, debido a que no existe una correlación tan clara entre el texto clave y cifrado.
Identificando cifrados polialfabéticos: Index Of Coincidence
A la hora de empezar el criptoanálisis de un texto, lo primero que nos interesa saber es el tipo de cifrado que se ha empleado, para ello nos podemos valer del Índice de Coincidencia (Index of Coincidence). Emplearemos este índice para analizar la variación de las frecuencias relativas de cada letra, respecto a una distribución uniforme.
Las letras en un lenguaje natural no se distribuyen uniformemente, el IC es más alto para tales textos que para cadenas de texto uniformemente aleatorias. Lo interesante es que si estamos frente a un cifrado de sustitución monoalfabéticos, se obtiene el mismo IC que el texto en lenguaje natural, lo que nos permite rápidamente detectar si nos encontramos frente a un cifrado de sustitución poli alfabética.
| Índice de coincidencia | Descripción |
| 0.0770 | Texto en castellano |
| 0.0686 | Texto en Ingles |
| 0.047 | Vigenere |
| 0.0385 | Texto aleatorio o sustitución polialfabetica |
Formula de Índice de coincidencia:
Código en Python:
En primer lugar, se implementa una función que recoja en un dict las frecuencias relativas a cada letra del texto (También es posible implementar esta función usando Counter del módulo Collections).
def frequency_analisys(text):
frequency_len = {}
count = 0
for i in range(len(text)):
if text[i] not in frequency_len:
frequency_len[text[i]] = 1
else:
frequency_len[text[i]] = frequency_len[text[i]]+1
count+=1
return frequency_lenUna vez tengamos el diccionario con las frecuencias, pasamos a implementar la formula del IC.
def ic(freq_list,lon):
ind = 0
for i in freq_list.values():
ind += i *(i-1)
ind /= lon*(lon-1)
return ind
freq = frequency_analisys(textocifrado)
ioc = ic(freq,len(textocifrado))Para ilustrar un poco mejor, os dejo aquí el resultados de calcular el IC de un mismo texto plano en distintos cifrados de sustitución:
Descifrando Vigenere: Obteniendo la longitud de la clave con Método Kasiski
El método Kasiski consiste en la búsqueda de palabras repetidas en el texto cifrado para determinar la longitud de la clave en un cifrado Vigenère. Aplicando este método es posible obtener la longitud de la clave empleada y descomponer el criptograma cifrado con Vigenère en los subcriptogramas cifrados con cesar.
Para que este método sea efectivo debemos tener un texto de longitud mayor o igual a 3 veces el tamaño del alfabeto, así que comenzaremos implementando esta comprobación, para ello definiremos una función auxiliar que nos indique si el texto tiene la longitud necesaria.
alphabet ="ABCDEFGHIJKLMNRSTUVWXYZ" # Alfabeto a utilizar
MIN_LEN = 3 *len(alphabet) # Longitud mínima para que funcione kasiski
def check_min_len(text):
if len(text) < MIN_LEN: # 3 veces el alfabeto
print("[!]El texto es demasiado corto los resultados pueden no ser fiables")
return False
else:
return True
Otra función que necesitaremos, será una que normalice el texto, el texto cifrado puede contener caracteres especiales como comas y puntos que no forman parte del alfabeto, por lo que necesitaremos eliminar estos caracteres antes de continuar.
def normalize_text(text):
result = ""
text = text.replace(" ", "").upper() #Quitamops espacios y los transformamos a mayusculas
for c in text:
if c in alfabeto: #Añadimos solo los caracteres que estan en el alfabeto
result+=c
return resultAhora ya podemos comenzar con el procedimiento principal de kasiski, Suponed que tenemos el siguiente texto en español cifrado con Vigenere:
Pn we tjzac dg ci Btnnhc, um rnyz nqdjgx nz qwzmgh anotuigfe, yo jr ujvhz tkvueh qfe xzdíp nn sifrtvh dp lqj lt eayzc vv plttlnvzd, tdlrir icmiruc, iwríg fwaef g vtlro efzgxdzr. Wei dell dg rtvh mád vcti fne natemgh, sllrzkóc ead máu ewraed, dwvtdl y bugszpgtzs nfa háuaoou, cicmeuau cwh oiprpva, pegúy pccwbbnz dg rñisbdfrc cwh woxipxwh, voyswdíic ead ttva etreeu um hn hlckvvst.
El primer paso consiste en buscar los trigramas repetidos. Encontrarnos con un bloque de 3 o más letras repetidas en un texto cifrado equivale o a que se ha empleado el mismo texto plano o la mismas letras de la clave, por lo que la posición de los trigramas estará a una distancia múltiplo de la longitud de la clave.
def identify_repeat_chains(text):
i = 0
dist = [] # Lista de tuplas (cadena,distancia)
while i < len(text):
cad= text[i:i+3] # Cojemos los 3 caracteres y comprobamos longitud
lcad = len(cad)
if lcad == 3:
for j in range(i+1,len(text)): #Recorremos el texto
if text[i:i+lcad] == text[j:j+lcad]: # si encontramos otra cadena de 3 igual, buscamos mas
while text[i:i+lcad] == text[j:j+lcad]:
lcad = lcad + 1
lcad = lcad -1
dist.append((text[i:i+3],j - i)) # Tenemos una tupla con la cadena y la distancia
i = i + lcad-3+1
else:
i+=1
return distCon la función anterior obtendremos una lista de tuplas con las cadenas repetidas en el texto, y la distancia entre la primera aparición del trigrama y la segunda.
Tuplas devueltas para nuestro texto:
[('MGH', 128), ('RTV', 72), ('TDL', 86), ('ICM', 104), ('UCI', 97), ('DGR', 96), ('CEA', 96), ('CWH', 32), ('CCW', 16)]
Ahora que tenemos los trigramas, obtendremos todas las combinaciones posibles de distancias en grupos de 2 y para cada posible combinación hallaremos su máximo común divisor. Crearemos un dict en el que almacenaremos el máximo común divisor y su frecuencia de aparición
import math
from itertools import combinations
def frequency_distance_repeat(tuples):
frequency_len = {} #Dict con {mcd:frecuencia}
distancias = []
for i in range(len(tuples)): #Iteramos la lista de tuplas
distancias.append(tuples[i][1]) # añadimos el valor a la lista de distancias
comb = combinations(distancias,2) # Obtenemos las combinaciones posibles de distancias 2 a 2
for i in list(comb): # Para cada posible combinación
gcd = math.gcd(i[0],i[1]) #obtenemos maximo comun divisor y la frecuencia de aparición
if gcd not in frequency_len and gcd > 1:
frequency_len[gcd] = 1
else:
if gcd > 1:
frequency_len[gcd] = frequency_len[gcd]+1
return frequency_lenResultado de ejecutar la función:
#Combinaciones 2 a 2 posibles
[(128, 72), (128, 86), (128, 104), (128, 97), (128, 96), (128, 96), (128, 32), (128, 16), (72, 86), (72, 104), (72, 97), (72, 96), (72, 96), (72, 32), (72, 16), (86, 104), (86, 97), (86, 96), (86, 96), (86, 32), (86, 16), (104, 97), (104, 96), (104, 96), (104, 32), (104, 16), (97, 96), (97, 96), (97, 32), (97, 16), (96, 96), (96, 32), (96, 16), (96, 32), (96, 16), (32, 16)]
#Maximo comun divisor: frecuencia
{8: 9, 2: 7, 32: 5, 16: 4, 24: 2, 96: 1}
Para obtener la longitud de la clave únicamente debemos obtener el valor más grande del dict que nos devolvió la función anterior, pues la longitud de la clave será el máximo común divisor que aparece con más frecuencia.
def get_long(l):
for key, value in l.items():
if value == max(l.values()):
return keyAhora obtendremos un subcriptograma por cada posición de la clave, de forma que en el subcriptograma 1 tengamos el texto que se cifró con la primera letra de la clave y así sucesivamente.
def get_subcriptogram(text,lon):
criptograms = []
for i in range(lon): #Creamos tantas listas como longitud de la clave
criptograms.append([])
for i in range(len(text)):
criptograms[i % lon].append(text[i])
for i in range(len(criptograms)):
criptograms[i] = ("".join(criptograms[i]))
return criptograms
Lista de subcriptogramas:
0 : PCNZZNYZFSPYTLRWRZLDNLDDBZOUPYZFXYDEL
1 : NDHNQOOTEILZLRUAORDVALMDUSOARPDRISTEC
2 : WGCQWTJKXFQCNICEEWGCTRUWGNUUPCGCPWTUK
3 : ECUDZURVZRJVVRIFFERTEZEVSFCCVCRCXDVUV
4 : TIMJMIUUDTLVZIWGZITIMKWTZAIWAWIWWIAMV
5 : JBRGGGJEPVTPDCRVGDVFGCRDPHCHPBSHHCEHS
6 : ZTNXHFVHNHELTMGTXEHNHEALGUMOEBBWVETNT
7 : ANYNAEHQNDATDIFLDLMESAEYTAEIGNDOOARH
Averiguando la longitud: Index Of Coincidence
El método kasiski no es la única forma de obtener la longitud de la clave, también nos podemos valer del IC para ello. El planteamiento es sencillo, probaremos todas las longitudes posibles de 2 a 12, en donde para cada longitud posible dividiremos el criptograma en «n» subcriptogramas , sobre los que calcularemos el IC de todos y le realizaremos la media, la longitud que maximice la media del IC de los subcriptogramas será también la longitud de la clave.
def guess_len_ic(ciphertext):
maxdeltaioc = 0
pos = 0
for i in range(2,12):
criptos = get_subcriptogram(ciphertext,i)
iclist = []
for j in criptos:
freq = frequency_analisys(j)
ioc = ic(freq,len(j))
iclist.append(ioc)
#calculate delta ioc
deltaioc = sum(iclist)/len(iclist)
if deltaioc > maxdeltaioc:
maxdeltaioc = deltaioc
pos = i
return pos
Descifrando los subcriptogramas con analisis de frequencia
Ahora que ya tenemos los subcriptogramas, nos enfrentamos a 8 cifrados cesar monoalfebéticos, y frente a cesar sí que podemos emplear análisis de frecuencia. Únicamente necesitaremos la frecuencia de las letras en español y un método que nos permita medir la diferencia con las frecuencias del texto cifrado respecto a las letras en español.
#Creamos un dict con la frecuencia de aparición de las letras en español
letter_freq_sp={"A":11.72,"B":1.49,"C":3.87,"D":4.67,"E":13.72,"F":0.69,"G":1.00,"H":1.18,"I":5.28,"J":0.52,"K":0.11,"L":5.24,"M":3.08,"N":6.83,"Ñ":0.17,"O":8.44,"P":2.89,"Q":1.11,"R":6.41,"S":7.20,"T":4.60,"U":4.55,"V":1.05,"W":0.04,"X":0.14,"Y":1.09,"Z":0.47} Implementamos una función para obtener un score de que tanto se desvía la frecuencia del criptograma cesar respecto a la frecuencia de las letras en español.
def score_difference(text):
counter = Counter(text)
return sum([abs(counter.get(letter,0)* 100 /len(text)-letter_freq_sp[letter]) for letter in alfabeto]) / len(alfabeto)
Para intentar obtener la clave de los subcriptogramas, iremos probando cada desplazamiento posible de la «A» a la «Z», de forma que nos quedaremos con el desplazamiento que minimice la score de diferencia.
def guess_key(criptograms):
keys = []
for c in criptograms:
scoremin = 10
key = ""
for i in range(len(alfabeto)):
text = caesar_decipher(c,i)
score = score_difference(text)
if score < scoremin:
scoremin = score
key = alfabeto[i]
keys.append(key)
return "".join(keys)Con lo visto hasta ahora ya tenemos más que suficiente para descifrar textos cifrados con Vigenere, os animo a probar con el texto de ejemplo 🙂
Una versión mejorada de Vigenere: Cifrado Autoclave
Autoclave es la versión mejorada de vigenere, el principal cambio es que en vez de repetir cíclicamente la clave se incorpora el texto original como clave. Como consecuencia de la incorporación del texto, la distribución de las letras ya no dependerá de la clave, lo que nos impide realizar ataques sobre la longitud de la clave. Ni kasiski ni el IC nos van a ayudar a obtener la longitud, es por ello que Autoclave se considera más robusto que Vigenere. A modo de ejemplo:
Mensaje: NOSVEMOSELVIERNES (desconocido) Clave: CRIPTANOSVEMOSELV (desconocido) Cifrado: PFAKXMBGWGZUSJRPN (conocido)
Código en Python para el cifrado:
def autokey_cipher(plain,clave):
result = ""
key = clave+plain[0:len(clave)]+plain[len(clave):-len(clave)]
key = normalize_text(key)
plain = normalize_text(plain)
res = vigenere_cipher(plain,key)
return res Código en Python para el descifrado:
def autokey_decipher(cipher,clave):
result = []
i = 0
for letter in cipher:
x = alfabeto.index(letter)
if i < len(clave):
y = alfabeto.index(clave[i].upper())
else:
y = alfabeto.index(result[i-len(clave)])
desp = (((x-y)+26)%26)
result.append(alfabeto[desp])
i+=1
return "".join(result)Ataques de fuerza bruta y diccionario contra Autoclave
Que el IC no nos valga para averiguar la longitud de la clave, no implica que no pueda seguir siendo útil para atacar Autoclave. El IC sigue siendo un buen indicador de la distribución del texto cifrado y por ende nos puede ser útil para validar que clave es correcta. Al igual que el caso anterior, suponed que tenemos el siguiente texto en español cifrado con Autoclave.
ORSRYOTLLJECDQLNOHNFLCXCQHMAOFQOFUHWULWETCRFOIPEEALNABCTIVPSFXSCJSLCZDIPVHCQHTJOOKZRWOSDDRKARMAWGIDEMCZEUORJARTTITNIXICZBHTNHZYIOJMONUFTSUFVXBRIYLOOPAOKOXGGHAUVQWESUVPEIBWRZHINDVNOFXAKZOUUSUKYWOIWJEMCRLEOKOFECKDOTSDPSOOFEEWTWUOKGWWMVIJNPYUYVUYDMTBALROQEDVDXZDFFSOCELBSWFICFUIZAUZTAFERWLGEJIEJWIKXLSWPEPLE
Una aproximación por fuerza bruta podría ser ir probando las permutaciones posibles del alfabeto para distintas longitudes, aquella combinación que maximice el IC posiblemente sea la clave empleada. El IC no es el único indicador que nos vale para este propósito, también se podría emplear la función de score_difference(), ya que aquella combinación que minimice el score puede ser una clave potencial
from itertools import permutations
def guess_autokey(ciphertext,minlen,maxlen):
for keylen in range(minlen,maxlen+1):
mindelta = 0
mindkey = ""
for i in permutations(alfabeto,keylen):
key = ''.join(i)
pt = autokey_decipher(ciphertext,key)
freq = frequency_analisys(pt)
dioc = ic(freq,len(pt))
if dioc > mindelta:
mindelta = dioc
mindkey = key
return mindkey
key = guess_autokey(textocifrado,2,3)Recorrer todo el espacio de claves, solo es factible si la clave empleada es de longitud corta, ya que el tiempo necesario para recorrerlo crece exponencialmente con la longitud. Una aproximación más eficiente es emplear una wordlist que incluya un subconjunto de claves posibles. Usaremos como indicador el score, aunque también podríamos usar el IC.
def guess_dict_autokey(ciphertext):
minscore = 100
key = ""
with open('words.txt') as f:
for i in f:
i = i[:-1] #eliminamos salto de linea
pt = autokey_decipher(ciphertext,i)
diff = score_difference(pt)
if diff < minscore:
minscore = diff
key = i
return keyUna mejora sencilla sobre estos códigos, sería que no fuese necesario probar todas las combinaciones, sino que al detectar la clave dejase de iterar. Para ello podemos considerar que si el valor absoluto del IC calculado menos el IC de en español es menor que un margen de error razonable (ej. 0.05), posiblemente hayamos hallado la clave. Con el score podríamos plantear que si el score es menor que 1 posiblemente estemos frente a la clave.
Criptoanálisis a Autoclave
Por otro lado, independientemente de los ataques de fuerza bruta o diccionario, también es posible el criptoanálisis Autoclave. No quiero que este post sea excesivamente largo, por lo que no tocaremos la implementación en Python (quizás en otro post) lo que si quiero comentar por encima el proceso de criptoanálisis de Autoclave.
Autoclave tiene un fallo crucial y es que el texto plano forma parte de la clave, eso implica que la clave posiblemente contenga palabras comunes en varios puntos. La clave puede ser atacada mediante un ataque de diccionario con palabras, bigramas, trigramas o n-gramas frecuentes. Iterando cada n-grama por cada posición del texto hasta obtener un fragmento que sea potencialmente legible en el texto resultante . Como el propio texto se emplea como clave, un fragmento correcto de texto plano aparecerá en la clave, desplazado a la derecha por la longitud de la clave, lo que nos permitirá inferir la longitud empleada.
Por ejemplo, supongamos que tenemos el siguiente texto en español cifrado con Autoclave «OPYXLQNEUMEPSTLRWE»
Empezaremos probando bigramas comunes que nos podemos encontrar en un texto en Español, por ejemplo comenzaremos probando el bigrama «VA», en todas las posiciones posibles y desplazamientos posibles.
VA -> [] OP YX LQ NE UM EP ST LR WE (texto) VA VA VA VA VA VA VA VA VA (clave) -------------------------- TP DX QQ SE ZM JP XT QR BE
Con «VA» no parece que haya bigramas posibles en español, podemos observar resultados como «QQ» que directamente no son posibles en este idioma. Por lo que tenemos que seguir probando con otro bigrama para obtener más información.
Ahora probaremos «QU» y podemos vemos que «ES» aparece en la posición 9 en el texto en claro. El bigrama «ES» es bastante mas probable que sea parte de un texto en español que bigramas como «QQ»
QU -> [ES:9] #bigrama:posición OP YX LQ NE UM EP ST LR WE (texto) QU QU QU QU QU QU QU QU QU (clave) ------------------------------ YV ID VW XK ES OV CZ VX GK
Si suponemos que realmente se ha empleado la clave «QU» en esta posición, y que «ES» forma parte del texto plano, este se debería emplear como clave en una posición desplazada a la derecha por la longitud de la clave. Por lo que probaremos ahora con «ES».
ES -> [QU:9] OP YX LQ NE UM EP ST LR WE (texto) ES ES ES ES ES ES ES ES ES (clave) -------------------------- KX UF HY JM QU AX OB HZ SM ES +1 -> [VA:7,CI:9,LA:12]x OP YX LQ NE UM EP ST LR WE (texto) .E SE SE SE SE SE SE SE SE (clave) -------------------------. .L GT TM VA CI ML AP TN EA
Los bigramas que podrían ser posibles en español son «QU»,»VA»,»CI» y «LA» pero únicamente «LA» se encuentra en una posición más a la derecha, por lo que de ser correcta esta suposición tendríamos que:
plain: OP YX LQ NE UM EP ST LR WE key: -- -- -- -- QU -E S- -- -- msg: -- -- -- -- ES -L A- -- --
Además, ya podemos inferir la longitud de la clave, la cual ha de ser de 3 (12-9). Si todo lo que suponemos es correcto, «LA» ha de emplearse como clave en la posición 15 (12+3) y «QU» ser el texto plano de la posición 6 (9-3). Miraremos ahora el bigrama «LA».
LA ->[AQ:5,AR:15] X OP YX LQ NE UM EP ST LR WE LA LA LA LA LA LA LA LA LA --------------------------- DP NX AQ CE JM TP HT AR LE LA+1 -> [ES:12,SI:13] OP YX LQ NE UM EP ST LR WE .L AL AL AL AL AL AL AL AL --------------------------- .E YM LF NT UB EE SI LG WT
Observamos que en la posición 15 se obtiene el bigrama «AR» , sabiendo que la longitud de la clave es de 3, podemos inferir (si la suposición es correcta) que la «A» será la clave de la posición 18 (15+3).
plain: OP YX LQ NE UM EP ST LR WE key: -- -- -- -- QU -E S- LA -A msg: -- -- -- -- ES -L A- AR -E
También sabemos que «QN» se debería descifrar por «QU» , así que busquemos un bigrama que cumpla esta condición. En este caso será «AT».
TA -> [QU:6,UE:7,DE:17]x OP YX LQ NE UM EP ST LR WE TA TA TA TA TA TA TA TA TA --------------------------- VP FX SQ UE BM LP ZT SR DE TA+1 -> [EL:4,SA:14] OP YX LQ NE UM EP ST LR WE .T AT AT AT AT AT AT AT AT -------------------------- .W YE LX NL UT EW SA LY WL
Si la suposición es correcta y «AT» se usa como clave en la posición 6, tuvo que aparecer como parte del texto plano en la posición 3. Teniendo en cuenta que la longitud de la clave es de 3 podemos deducir que la «X» de la posición 4 de se traduce por una «T»
plain: OP YX LQ NE UM EP ST LR WE key: -- -E -A T- QU -E S- LA -A msg: E- AT -Q U- ES -L A- AR -E
Si observamos este último bigrama, vemos que hay más combinaciones que podrían ser parte de la clave, como se emplea una «T» en la posición 7 de la clave, «TA» es una posibilidad muy prometedora, siempre y cuando UE tenga sentido en esa posición 7 (que en este caso tendría sentido). Además, en la posición 3 se obtiene «EL», que también cuadra muy bien con la suposición de que «X» se traduce por «T», ya que eso implica que «E» debe ser clave en la posición 3. Otras opciones a considerar es que el bigrama de texto plano final es «DE», ya que cuadra con la suposición de que «E» es la última letra y el bigrama «SA» que cuadra con la «S» que teníamos en la clave.
plain: OP YX LQ NE UM EP ST LR WE key: -- -E LA TA QU EE SA LA TA msg: EL AT AQ UE ES AL AT AR DE
Por lo que el texto descifrado seria: EL ATAQUE ES A LA TARDE.
Referencias:
- http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-autokey-cipher/
- https://medium.com/@momohakarish/caesar-cipher-and-frequency-analysis-with-python-635b04e0186f
- http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-vigenere-cipher/
- https://en.wikipedia.org/wiki/Autokey_cipher
La Cripta del Hacker 
Deja un comentario