Josep Portella
Criptograma inesperat
Juliol de 2011
Traduït: març de 2012
Revisat: setembre de 2015 i gener de 2020
Aquesta obra està sota una llicència de
Reconeixement-SenseObraDerivada 3.0 Creative Commons.
Arriba un missatge xifrat
—Menelau, t'ha arribat un email d'un tal Paris.
—Paris? És un vell amic meu.
—Mira el contingut de l'email.
-----BEGIN BLAISE MESSAGE-----
B8 C0 CB B2 9A BC B2 C7 BA C6 AE D5 9C 91 D3 98
BF C2 B0 CB BE BD 8D D0 B5 C3 9F B5 BF C2 BD BE
B9 C3 BF AD BD B6 AD 91 BF C3 C0 99 C1 BB 8D CD
B9 BD CB C0 CC 8F BD BE C7 CD BC CE B1 91 D0 C6
BF 8F B5 BE 95 BD BC CE B5 B8 D4 C5 A8 8F B7 BA
95 C8 BC A0 C0 C6 C2 91 BB B6 C2 BA C3 CE AE D2
9D B9 CE 91 C7 B4 C0 A7
-----END BLAISE MESSAGE-----
—Sembla que es tracta d'un missatge xifrat, però per què me l'envia? Fa
uns dies em vaig trobar amb ell després d'anys sense veure'l i vam estar
parlant sobre… Ah, clar, recordo que li vaig explicar que últimament no
estic molt motivat; que no entren treballs que suposin un repte
intel·lectual. Crec que deu haver enviat això per que tingui alguna cosa
interessant en que pensar. Molt amable per part seva!
—Intentaràs desxifrar-lo?
—Les altres feines que tenim en marxa no son especialment urgents, així
que no veig per què no hauria de fer-ho. Comencem. Què és el que podem
dir d'aquest missatge a primera vista?
—El més obvi és que té una marca d'on comença i un altre d'on acaba.
—Sí, i a més sembla que s'ha generat amb un sistema de xifrat anomenat
BLAISE.
—No el conec.
—Jo tampoc. Cerquem a Internet a veure si podem trobar el programari.
El sistema de xifrat “BLAISE”
—Ja veig, escrius un text i una contrasenya i et permet xifrar-lo o
desxifrar-lo. Anem a veure què passa si introduïm el missatge xifrat
d'en Paris i intentam desxifrar-lo amb una contrasenya qualsevol… Per
suposat, es converteix en deixalles. Continuem estudiant el missatge
xifrat. Què podem dir sobre el que hi ha entre les marques d'inici i
final del missatge?
—Semblen octets en notació hexadecimal.
—Exacte. Posem en marxa el REPL de Racket per fer
proves.
menelau@esparta:~$ racket
Welcome to Racket v7.5.
>
—Guardem el contingut del missatge a una variable.
(define msg "
B8 C0 CB B2 9A BC B2 C7 BA C6 AE D5 9C 91 D3 98
BF C2 B0 CB BE BD 8D D0 B5 C3 9F B5 BF C2 BD BE
B9 C3 BF AD BD B6 AD 91 BF C3 C0 99 C1 BB 8D CD
B9 BD CB C0 CC 8F BD BE C7 CD BC CE B1 91 D0 C6
BF 8F B5 BE 95 BD BC CE B5 B8 D4 C5 A8 8F B7 BA
95 C8 BC A0 C0 C6 C2 91 BB B6 C2 BA C3 CE AE D2
9D B9 CE 91 C7 B4 C0 A7
")
—Definim un procediment per obtenir el missatge xifrat en cru: tindrà que dividir la cadena per on hi hagi espais o noves línies i convertir cada número hexadecimal resultant a un enter.
(define (unarmor str)
(sequence-map (curryr string->number 16)
(string-split str)))
—Escriguem també un procediment per obtenir la freqüència de cada valor de forma ordenada.
(require math/statistics)
(define (sorted-frequencies nums)
(sort (hash->list (samples->hash nums))
< #:key cdr))
—Obtinguem el resultat utilitzant ambdós procediments.
> (sorted-frequencies (unarmor msg))
'((157 . 1) (200 . 1) (183 . 1) (154 . 1)
(176 . 1) (168 . 1) (177 . 1) (160 . 1)
(152 . 1) (212 . 1) (197 . 1) (204 . 1)
(153 . 1) (213 . 1) (180 . 1) (210 . 1)
(159 . 1) (211 . 1) (156 . 1) (167 . 1)
(193 . 1) (174 . 2) (149 . 2) (184 . 2)
(205 . 2) (178 . 2) (187 . 2) (173 . 2)
(141 . 2) (182 . 2) (208 . 2) (199 . 3)
(185 . 3) (198 . 3) (186 . 3) (143 . 3)
(203 . 3) (206 . 4) (188 . 4) (195 . 4)
(181 . 4) (194 . 4) (190 . 4) (191 . 5)
(192 . 5) (145 . 5) (189 . 6))
—Podem veure que la freqüència dels valors no està distribuïda de forma
regular.
—I què significa això?
—Que no es tracta d'un sistema criptogràfic fort; segurament l'ha
dissenyat un aficionat.
Enginyeria inversa
—Xifrant el text AAAA amb la contrasenya AB ens dona el text xifrat
AE AF AE AF. Si xifram BBBB amb la mateixa contrasenya tenim
AF B0 AF B0, és a dir, el mateix que abans però amb cada valor
incrementat en una unitat.
—Què es dedueix d'això?
—Que cada octet del text xifrat s'obté aplicant una funció a un caràcter
del text en clar i un caràcter de la contrasenya. El primer caràcter del
text amb el primer de la contrasenya, el segon amb el segon i així fins
que s'acaba la contrasenya. Llavors es torna començar amb el primer
caràcter de la contrasenya. Només falta descobrir una cosa: el número
màgic.
—El número màgic?
—Un número fix que també es fa servir a la funció, que esbrinarem
restant l'octet del text xifrat amb el valor dels seus caràcters
corresponents del text en clar i de la contrasenya.
> (- #xAE (char->integer #\A) (char->integer #\A))
44
> (- #xAF (char->integer #\A) (char->integer #\B))
44
—Ho veus? En ambdós casos el número màgic és 44. Ara ja podem
escriure el procediment de desxifrat.
(define (decrypt nums keys)
(sequence-map
(lambda (n k)
(integer->char (modulo (- n k 44) 128)))
(in-parallel
nums (in-cycle (sequence-map char->integer
keys)))))
Atac de diccionari
—Anem a provar un atac de diccionari. Com que el programari només accepta paraules en majúscules i sense accents, necessitarem un procediment per adaptar les paraules del diccionari així com es van llegint.
(define normalize-word
(compose (curryr string-replace #px"\\W+" "")
string-upcase string-normalize-nfkd))
—I per últim, un procediment que intenti desxifrar el text xifrat amb cada una de les paraules del diccionari. A cada resultat cercarà un prefix per determinar si és la paraula correcta, i si coincideix retornarà la paraula.
(define (attack nums word-list prefix)
(with-input-from-file word-list
(lambda ()
(for/first
((w (sequence-map normalize-word
(in-lines)))
#:when
(sequence-andmap
eqv? (in-parallel (decrypt nums w)
prefix)))
w))))
—Cerquem un fitxer amb un llistat de paraules en català a Internet… Val, aquest servirà. Ara només falta
decidir quin prefix ha de cercar.
—Què tal si cerca HOLA MENELAU?
—Pot ser que funcioni. Provem.
> (attack (unarmor msg) "catala.txt"
"HOLA MENELAU")
Text en clar
—Vaja, em pregunto per què en Paris haurà escollit aquesta paraula com a contrasenya. Bé, només queda utilitzar-la per desxifrar el missatge.
En Menelau va llegir el missatge desxifrat i durant uns segons es va quedar pensatiu. De sobte va empal·lidir, es va aixecar bruscament i va agafar el mòbil.