Writeup DGSE - preliminaries - cryptography

In this article we will look at the first of the 4 preliminary challenges: cryptography.

Introduction

Here is what Antoine Rossignol tells us.

Agent 42, félicitations pour votre affectation sur l'affaire Friang ! Je pense avoir une piste sérieuse. Mais avant toute chose, voici les échanges avec votre prédécesseur.

Antoine Rossignol 29/09/2020 : "Un des nos agents a intercepté du matériel de chiffrement et un message chiffré émis par Evil Chems qui doit contenir des informations capitales sur la livraison de produits chimiques."

Agent 40 30/09/2020 : "OK, on s'occupe de démonter le matériel pour analyse."

Agent 40 08/10/2020 : "C'est plus compliqué que prévu! Le processeur ne fait qu'échanger des données avec un circuit intégré dédié (ASIC). On suppose qu'il contient l'algorithme de chiffrement et que la clé y est stockée en dur."

Antoine Rossignol 08/10/2020 : " Envoyez en urgence l'ASIC à Eve Descartes d'ESIEE-Paris pour une rétro-conception matérielle"

Agent 40 12/10/2020 : "Eve Descartes a bien reçu le circuit. Elle s'en occupe en priorité."

Antoine Rossignol 23/10/2020 : "Voici le compte-rendu d'Eve avec la cartographie de la zone étudiée. Il devient urgent de déchiffrer le message."

He also tells us the following.

Eve Descartes est une spécialiste des attaques matérielles. Elle travaille dans les salles blanches d'ESIEE Paris et elle nous donne un coup de main de temps en temps. C'est la meilleure dans son domaine.

It gives us the following files: archive_chiffree, layout.pdf and compte_rendu_eve.pdf.

Finally, he says.

Comme vous pouvez le voir, le fichier que nous a envoyé Eve est protégé par un mot de passe et elle ne répond plus. Trouvez un moyen de la contacter pour déchiffrer le fichier.

Start

So we have 3 files:

At the end of the file she tells us that we should not hesitate to contact her by e-mail or phone for any further information.

I decided to call her because it’s much faster than an e-mail: the first thing I hear is a serie of beeps, stops, longer beeps… it immediately makes me think of Morse code.

After calling her a few times, and scribbling down what I heard, I get to the following Morse code.

.-. . ... .. ... - .- -. -.-. .

Decoding and decryption

Since I think I frustrated some people before not to have made a code to decipher the Caesar code, here is one to transform a Morse code into text.

#! /usr/bin/env python

def morse(txt):
    d = {'A':'.-','B':'-...','C':'-.-.','D':'-..','E':'.',
         'F':'..-.','G':'--.','H':'....','I':'..','J':'.---',
         'K':'-.-','L':'.-..','M':'--','N':'-.','O':'---',
         'P':'.--.','Q':'--.-','R':'.-.','S':'...','T':'-',
         'U':'..-','V':'...-','W':'.--','X':'-..-','Y':'-.--',
         'Z':'--..', ' ':'.....'}
    translation = ''

    if txt.startswith('.') or txt.startswith('−'):
        d_encrypt = dict([(v, k) for k, v in d.items()])
        txt = txt.split(' ')
        for x in txt:
            translation += d_encrypt.get(x)

    else:
        txt = txt.upper()
        for x in txt:
            translation += d.get(x) + ' '
    return translation.strip()

print(morse('.-. . ... .. ... - .- -. -.-. .'))

Test it.

python morse.py
RESISTANCE

The password for layout.pdf would therefore be RESISTANCE. Well, not exactly… In fact I only understood afterwards but I still sent an email to the address indicated and an automatic reply is set up. This answer (translated to English) gives a funny information about this password.

I am currently unavailable. If you have any problem, even if it's tiny, don't hesitate to contact me by phone.

In French, replace tiny by “minuscule”, lowercase in English.

So the password is resistance.

Once the PDF is unlocked, we can see the 256 micro-fuses as Eve told us. In her report, she tells us that she didn’t have time to analyze the bit order and the position of the Most Significant Bit (MSB). Let’s do it for her!

By zooming on the image, it is possible to see that some micro-fuses are cut and others are not. We all know that in electronics, when electricity goes through it corresponds to 1 and when it doesn’t go through it corresponds to 0.

Here is what it gives me.

0000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000100001011000010101000100000010001101100101011000100110000000100110010101010001010000010

If I turn this string into ASCII it gives me this.

cat bin.txt | perl -lpe '$_=pack"B*",$_'
B¢lLʢ

It’s not great, since we don’t know the order of the bits, we’ll try to invert.

0100000101000101010100110010000000110010001101010011011000100000010001010100001101000010001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000

If I turn this string into ASCII it gives me this.

cat bin.txt | perl -lpe '$_=pack"B*",$_'
AES 256 ECB

What an interesting thing!

I’m not teaching you anything if I tell you that AES is a symmetrical encryption algorithm. It means that the encryption key is the same as the decryption key. But what is ECB?

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation (encryption or decryption) of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher’s single-block operation to securely transform amounts of data larger than a block. The Electronic CodeBook (ECB) is the simplest encryption mode. The message is divided into blocks, and each block is encrypted separately.

Let’s try something simple. OpenSSL allows you to encrypt and decrypt using several algorithms. Assuming that the archive has not been encrypted with an [initialization vector][initialization_vector], we can use the following command.

openssl aes-256-ecb -d -nosalt -in archive_chiffree -out archive.zip
enter aes-256-ecb decryption password:
*** WARNING : deprecated key derivation used.
Using -iter or -pbkdf2 would be better.
bad decrypt
139825409733440:error:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decrypt:crypto/evp/evp_enc.c:588:

It’s quite clear, the password to decrypt the archive is not the right one.

I spare you the several minutes of thinking. It turns out that the decryption key is the hexadecimal representation of the binary found earlier. So first of all, the binary string must be converted to hexadecimal.

python -c "print(hex(int('0100000101000101010100110010000000110010001101010011011000100000010001010100001101000010001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000', 2)))"
0x4145532032353620454342202020202020202020202020202020202020202020

We can now use the -K flag to pass the decryption key in hexadecimal format.

openssl aes-256-ecb -d -nosalt -in archive_chiffree -out archive.zip -K 4145532032353620454342202020202020202020202020202020202020202020

No message, it smells pretty good!

file archive.zip
archive.zip: Zip archive data, at least v2.0 to extract

It’s unbearable, we have to extract this archive!

unzip archive.zip -d archive
Archive:  archive.zip
   creating: archive/archive/
  inflating: archive/archive/code_acces.pdf
  inflating: archive/__MACOSX/archive/._code_acces.pdf
  inflating: archive/archive/._code_acces.pdf
  inflating: archive/archive/message.pdf
  inflating: archive/__MACOSX/archive/._message.pdf
  inflating: archive/archive/._message.pdf

First nice victory, but it’s not over yet.

We have now two files.

file archive/archive/code_acces.pdf
archive/archive/code_acces.pdf: PDF document, version 1.6
file archive/archive/message.pdf
archive/archive/message.pdf: PDF document, version 1.3

The file code_access.pdf is password protected but not message.pdf.

Globally, the content of this file asks us the following equation where \(x\) is the password to decrypt the file.

\[x = \left\{ \begin{array}{ll} x^3 \equiv 573[8387] \\ x^3 \equiv 98[9613] \\ x^3 \equiv 2726[7927] \\ \end{array} \right.\]

To solve this equation, we need to solve the Chinese Remainders Theorem (CRT). I wrote this script to do the computation.

#! /usr/bin/env python

def crt(n):
    if (n * n * n) % 8387 != 573:
        return False
    if (n * n * n) % 9613 != 98:
        return False
    if (n * n * n) % 7927 != 2726:
        return False
    return True

i = 0

while not crt(i):
    i += 1

print(i)

Test it.

python crt.py
5622

If I did things right, the password seems to be 5622.

That’s right! The code_access.pdf file is now unlocked. Last but not least is this new challenge presented in this file.

We have a password: 0xAF3A5E20A63AD0, encrypted by mono-alphabetic substitution. Each ASCII character is replaced by its inverse in the following relation.

\[GF(256) = \mathbf{Z}_2[X]/(X^8+X^4+X^3+X+1)\]

Plain text is the access code to the desired information.

When I had to solve this last step I was a bit stuck because I had never thought about finite fields. The idea is to define the four operations on bytes (\(256=2^8\)) using the polynomials of \(\mathbb{Z}/2\mathbb{Z}[X]\).

Each byte can be associated bijectively with a polynomial. For example to \((175)_{10}=(AF)_{16}=(10101111)_2\) we associate the polynomial \(X^7+X^5+X^3+X^2+X+1\).

No problem for addition: the addition of the polynomials of two bytes is the polynomial associated with the XOR (\(\oplus\)) of the two bytes.

On the other hand, the product of two polynomials of degrees strictly lower than 8 is not always a polynomial of degree strictly lower than 8. One thus chooses an irreducible polynomial of degree 8 of \(\mathbb{Z}/2\mathbb{Z}[X]\) as modulus. The remainder of the Euclidean division of the polynomial produced by this module is a polynomial of degree strictly lower than 8 which corresponds, by definition, to the product of the two bytes.

The modulus polynomial must be irreducible for the quotient ring to be a field.

Note that Joan Daemen and Vincent Rijmen, the designers of the Advanced Encryption Standard (AES), have chosen as module the polynomial \(X^8 + X^4 + X^3 + X + 1\).

If another irreducible polynomial of degree 8 is chosen, the numerical values are different: it is therefore necessary to specify the polynomial used as module. Nevertheless the fields obtained with different modules are all isomorphic.

The easiest way is to use the inverse table given at the end of this page.

The encrypted password is 0xAF3A5E20A63AD0.

The binary representation of these bytes are:

It is possible to solve this challenge with SageMath. If you are on Arch Linux and you don’t have this tool, you can install it as follows.

yay -S sagemath

First, let’s define the field in which we are going to work.

sage: R.<x> = PolynomialRing(GF(2))
sage: S.<xbar> = R.quo(x^8 + x^4 + x^3 + x + 1)

Then you have to invert the polynomials. For the first byte, the polynomial representation is done as follows.

sage: p1 = S(x^7 + x^5 + x^3 + x^2 + x +1)

Each 1 corresponds to a power of \(x\), from 7 on the left to 0 on the right. And finally we reconvert the obtained polynomial into a byte.

sage: p1^-1
xbar^6 + xbar^5 + xbar

To interpret this result, you have to set a 1 at the position that corresponds to the power of xbar. So for this result, it gives the following byte: 01100010 which corresponds to the hexadecimal value 62, so b in ASCII.

For the second byte, this is what it looks like.

sage: p2 = S(x^5 + x^4 + x^3 + x)
sage: p2^-1
xbar^5

The binary representation is: 00100000, which corresponds to the hexadecimal value 20, so a space in ASCII.

By applying this transformation on all bytes, we obtain the following password: b c:e z.

Once the password is sent to Antoine Rossignol, here is what he gives us as information.

C'est ça ! Tiens, ça me fait penser à Enigma. Notez-le ça pourrait vous servir ultérieurement...
On sait maintenant qu'Evil Country va utiliser du VX contre sa propre population, connectez-vous sur cette plateforme top secrète pour continuer l'enquête : /7a144cdc500b28e80cf760d60aca2ed3, on ne peut pas prendre le risque qu'un agent double ne s'en rende compte.

The real CTF challenge starts at the given URL but I wanted to keep warming up, so the next article will be the second preliminary challenge: web.