Writeup DGSE - CTF - Stranger RSA

This article describes my solution for the 200-point challenge called “Stranger RSA”.

Introduction

Un de nos agents est parvenu à dérober une clé privée et un fichier chiffré à Evil Gouv.
Retrouvez l'information, avec un peu d'imagination
Le flag est juste une chaîne de caractères (sans le DGESIEE{})

If you want to test it yourself, private.pem file is available here and EVIL-FILE.txt.enc is available here.

Start

So we have a private key and an encrypted file. We don’t know if the file has been encrypted with the delivered key.

Analysis

As a first step it is useful to look at the key information that can be retrieved through OpenSSL.

openssl pkey -in private.pem -noout -text | less
RSA Private-Key: (10375 bit, 2 primes)

The first very unusual thing is its size: 10375 bit!

Another important thing to try is to use the key to read the encrypted message. We don’t know if the message has been encrypted with it, but if they come together…

openssl rsautl -decrypt -in EVIL-FILE.txt.enc -out EVIL-FILE.txt -inkey private.pem
echo $status
0

No error message and the return code is 0, that’s pretty good.

cat EVIL-FILE.txt
221 x 7

In this decrypted file, there is only 221 x 7 . I don’t know what to deduce from this. The universal answer? No, it’s 42…

Well, since it requires some imagination to solve this challenge and since I’ve already tweaked some RSA keys, I extracted the information one by one (the modulo, the private exponent, prime1, prime2, exponent 1, exponent 2 and the coefficient) converted them into decimal and I saw nothing special except for prime1. I only display the part we are interested in.

cat private.pem | openssl rsa -text -noout
prime1:
    02:91:09:7c:c4:99:b5:bb:b9:da:2a:e2:ff:1b:84:
    b3:ea:15:a9:1c:21:8f:f4:fc:ff:59:1b:a2:e6:76:
    f5:67:a2:b6:6b:43:0f:61:38:28:74:09:0c:74:8b:
    92:94:93:d0:50:a8:0f:06:98:3e:f4:52:04:6b:48:
    aa:6c:56:38:d8:2c:bf:4c:00:96:c5:5e:65:95:31:
    f8:81:af:dd:75:91:8e:7b:84:8a:27:00:41:d1:2c:
    a6:ef:40:73:8f:12:e7:24:84:21:1c:fd:54:8d:e2:
    32:ec:67:58:45:81:b9:f7:4d:12:2c:23:44:f6:c3:
    73:5e:3e:69:55:f2:23:a3:af:f4:af:61:c9:62:d6:
    0c:28:d9:fa:f5:87:8e:63:8e:17:ba:dc:b1:09:e2:
    f7:96:78:4e:4a:4c:e6:53:99:2e:6f:70:2a:04:c9:
    5c:65:3c:90:60:af:ce:23:d7:79:ae:cc:f4:09:ee:
    10:d5:36:3f:81:d7:2f:f1:c1:fe:57:2c:34:ba:27:
    a0:55:ce:d1:4a:49:a9:12:f0:fb:a4:54:f7:a6:15:
    9e:56:1a:0d:9f:d1:f5:82:92:2b:e1:ff:7e:d7:a8:
    02:55:05:30:d6:a9:d7:9d:16:97:a8:73:34:d3:19:
    85:0a:46:51:3d:e3:7d:ca:87:e9:31:ed:c9:b3:5e:
    e3:26:97:dc:34:96:8f:e7:04:fa:df:97:60:ac:6f:
    ef:e3:db:1f:d1:8a:a8:be:63:df:ef:6e:0c:9f:d0:
    04:cf:b1:41:3a:64:18:c5:fe:0d:6b:c7:c2:41:47:
    04:30:ea:e7:27:b7:07:cd:91:37:0e:89:5f:59:2e:
    df:82:65:e4:da:43:f4:6b:0f:89:eb:bb:36:62:75:
    04:aa:7d:f2:d4:33:eb:c2:30:53:80:0f:08:c2:18:
    b3:2a:7c:8a:03:df:2c:a1:c1:d3:23:ca:5a:8c:6a:
    90:e3:e3:27:14:c9:44:4c:c1:52:ca:99:f2:98:c3:
    fd:1b:57:7c:5e:12:b4:40:2e:3b:b1:da:fb:f0:40:
    95:0b:f0:d3:a6:4b:a3:fd:ff:5d:1f:5f:7b:f9:e5:
    01:66:39:e7:c9:4b:cc:02:2c:8a:83:99:41:6f:70:
    76:21:96:8e:7f:f1:51:bd:72:fe:98:f1:b0:0a:03:
    22:f5:dd:92:0a:e1:47:33:a8:c4:8a:63:09:76:74:
    0c:aa:40:36:b2:a7:be:d2:81:3b:45:f3:36:53:bb:
    ef:c0:27:3c:c6:44:26:32:aa:77:c0:ea:cc:db:25:
    ae:3a:0b:16:92:61:38:30:b1:46:3f:f3:b0:fc:df:
    d0:e2:0c:64:f5:25:80:67:f5:82:7a:09:2e:01:13:
    e5:3d:f7:0e:8e:72:d1:ba:02:ac:a8:37:ec:f3:46:
    4f:de:4e:e3:cd:f0:df:9c:ca:e4:0e:4e:0b:6f:c6:
    58:df:b5:e5:57:5d:f7:d1:39:3e:36:e2:23:49:be:
    23:f7:2a:5a:f1:e5:3b:8e:23:03:ed:a7:80:cf:ec:
    68:31:90:f1:0d:de:56:a5:00:92:51:a1:6d:1b:65:
    f5:29:8e:cd:6c:e3:df:2b:6b:56:e1:6b:26:5b:7c:
    52:3b:4e:11:fe:0a:38:3b:7f:7e:4d:a8:12:e8:f9:
    8c:71:bc:12:b4:0d:65:66:e4:e2:03:fc:6c:d0:51:
    5e:01:08:8d:86:cd:c6:cd:f5:24:9b:00:92:91:12:
    6a:65:7d:13

In this format, nothing shocking, it is after having transformed it into base 16 that it becomes intriguing. If you want to try it by yourself, I’ll let you do it because it won’t do any good if I post it below. Replace PRIME1_HERE with the value of prime1 shown just above. Be sure to keep the \ to prevent the python command from closing prematurely.

python -c "print(int(\"PRIME1_HERE\".replace(':','').replace(' ',''), 16))"

In decimal format, this key is composed mostly of 8, 7 and 1. I have a rather small font in my terminal and I have seen some drawing letter shapes. So I immediately thought of some ASCII art.

Obviously these letters looked more or less like something understandable if I enlarged my font. I remembered what I had extracted from the number file: 221 x 7, that looks like a resolution, doesn’t it?

#! /usr/bin/env python

# replace PRIME1_DECIMAL by the return of the previous command
message = "PRIME1_DECIMAL"

for i in range(7):
    print(message[221*i:221*(i+1)])

If you run this script, it won’t look great and barely readable.

In fact, the key is 1562 characters long, so you have to get as close as possible to this value for the characters to fit perfectly in the resolution. It turns out that 223*7=1561. Thus it is the resolution that you have to choose.

So now our code looks more like this.

#! /usr/bin/env python

# replace PRIME1_DECIMAL by the return of the previous command
message = "PRIME1_DECIMAL"

for i in range(7):
    print(message[223*i:223*(i+1)])

When executing this code, you will clearly see the following characters: AD26F7D346A2CA64 which corresponds to the flag of this challenge.