Josep Portella

Criptograma inesperat

Juliol de 2011
Traduït: Març de 2012
Revisat: Setembre de 2015

© 2012, 2015 Josep Portella Florit
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”

Xifra Desxifra

—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 v5.3.6.
>

—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.

(define (sorted-frequencies nums)
  (sort (hash->list
         (sequence-fold
          (curryr hash-update add1 0)
          (hash) nums))
        < #:key cdr))

—Obtinguem el resultat utilitzant ambdós procediments.

> (sorted-frequencies (unarmor msg))
'((154 . 1) (152 . 1) (153 . 1) (159 . 1)
  (156 . 1) (157 . 1) (160 . 1) (167 . 1)
  (168 . 1) (176 . 1) (177 . 1) (183 . 1)
  (180 . 1) (193 . 1) (197 . 1) (200 . 1)
  (204 . 1) (211 . 1) (210 . 1) (213 . 1)
  (212 . 1) (141 . 2) (149 . 2) (174 . 2)
  (173 . 2) (178 . 2) (182 . 2) (187 . 2)
  (184 . 2) (205 . 2) (208 . 2) (143 . 3)
  (186 . 3) (185 . 3) (199 . 3) (198 . 3)
  (203 . 3) (181 . 4) (190 . 4) (188 . 4)
  (195 . 4) (194 . 4) (206 . 4) (145 . 5)
  (191 . 5) (192 . 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.