Dock12/Madame De Maintenon’s Cryptographic Pursuit – Unmasking the Traitors

Created by Cesare Pizzi Wed, 20 Dec 2023 10:13:37 +0100 Modified Wed, 20 Dec 2023 10:13:37 +0100
1349 Words
ctf reversing crypto rsa

In November 2023 Hex-Rays published a CTF challenge. We thought it would be a good opportunity to learn something new and so we decided to give it a try. Here we’d like to propose you an unusual writeup of the solution where we are going to explain how we solved it, but we are also trying to go a bit deeper in some aspects of crypto algorithms (RSA to be more specific).

Overview

The challenge comes in a form of an ELF 64-bit executable: madame

Running it, we can understand the basic structure of the challenge:

You have heard rumours that the diary of Madame de Maintenon contained the secrets to a legendary plot.
Good luck on your journey to uncovering the truth behind this mystery!
You have heard that a rival historian recently discovered a copy of a chapter of the diary of Madame de Maintenon at the local library. But being unable to solve the mystery, returned it in frustration. Having long been fascinated by her history, you can't wait to investigate. What do you do?

It looks like an old-school text adventure, where we need to type in actions to proceed.

Opening the madame executable in IDA Free and looking at the decompiled code, shows the main structure:

  puts(s);
  sub_401870(s, a2);
  sub_401A50();
  sub_401CD0();
  sub_401F50();
  JUMPOUT(0x402640LL);

So it seems we have 4 steps and then a final jump to a routine. Diving into the code show that every step have a similar structure:

 puts(
    "You have heard that a rival historian recently discovered a copy of a chapter of the diary of Madame de Maintenon at"
    " the local library. But being unable to solve the mystery, returned it in frustration. Having long been fascinated b"
    "y her history, you can't wait to investigate. What do you do?");
  sub_402370(src);
  v0 = src;
  do
  {
    v1 = *(_DWORD *)v0;
    v0 += 4;
    v2 = ~v1 & (v1 - 16843009) & 0x80808080;
  }
  while ( !v2 );
  if ( (~v1 & (v1 - 16843009) & 0x8080) == 0 )
  {
    v2 >>= 16;
    v0 += 2;
  }
  if ( (unsigned __int64)(&v0[-__CFADD__((_BYTE)v2, (_BYTE)v2) - 3] - src) <= 0x12
    || memcmp("Head to the library", src, 0x13uLL) )
  {
    sub_402350(
      "without a clear plan of action, your thoughts eventually pass on to more pressing matters, and you return to watch"
      "ing subway surfer tik-toks. May another, more focussed mind, solve this mystery.");
  }
  strncpy(::src, src, 0xC8uLL);
  memset(v7, 0, sizeof(v7));
  v3 = s;
  strncpy((char *)v7, ::src, 0x13uLL);
  *(_OWORD *)s = 0LL;
  memset(v24, 0, sizeof(v24));
  strncpy(dest, (const char *)v7, 0x20uLL);
  AES_set_decrypt_key(v7, 256LL, v22);
  v4 = (char *)&unk_407A60;
  do
  {
    v5 = v4;
    v4 += 16;
    AES_decrypt(v5, v3, v22);
    v3 += 16;
  }
  while ( v4 != (char *)&unk_407A60 + 1536 );
  sub_4021E0();
  return puts(s);

To summarize, we have:

  • print of a message (puts)
  • input read (sub_402370)
  • some checks on the input
  • decryption of the next stage (AES_decrypt)

The verification on the input differs for each step, from the first comparison in clear text (Head to the library) to more complicated checks. None of these is too complicated: the easiest is the first one listed above, the others require a bit of work. We are not going to cover them in the article since they are a bit out-of-scope in our case and we leave them as an exercise.

Once reversed all the checks, we have now the 4 inputs we need to type to go ahead in the game:

Head to the library
Check books on the next shelf
Search the book for clues
Turn over the page

But this is not going to solve the challenge: we get some hints (like the 4 binary numbers 01000010, 00110111, 10110010, 00000101) but nothing more. If we look at the last JUMPOUT we notice something more:

.text:0000000000402640                 endbr64
.text:0000000000402644                 mov     ecx, cs:dword_408488
.text:000000000040264A                 test    ecx, ecx
.text:000000000040264C                 jz      short loc_402662
.text:000000000040264E                 mov     edx, cs:dword_408484
.text:0000000000402654                 test    edx, edx
.text:0000000000402656                 jz      short loc_402662
.text:0000000000402658                 mov     eax, cs:dword_408480
.text:000000000040265E                 test    eax, eax
.text:0000000000402660                 jnz     short loc_402670

So, after the 4 steps there is an additional check of 3 variables (dword_4084..). If all of them are set to 1, an additional AES decryption is done. Forcing the values at execution time is useless, because the decryption is probably done with the wrong password.

Going back to the code, we see an additional function which went unnoticed before, sub_4021E0(); this function is performing some RSA operation and also setting the variables mentioned before. Also, the very first check done by the program (the one listed above with Head to the library string), does not check for the exact string, but for a string beginning with these words. That means we need probably to add something to that string. Let’s have a look to sub_4021e0():

 BN_hex2bn(&v3, &unk_4077A0);
 BN_hex2bn(&v4, "3");
 RSA_set0_key(v1, v3, v4, 0LL);
 RSA_public_encrypt(256LL, src, s1, v1, 3LL);
 result = memcmp(s1, &xmmword_4076A0, 0x100uLL);

The code is called at least 3 times, encrypting the same plaintext with 3 different moduli. This is suspect and it point to a CRT algorithm application (Chinese Reminder Theorem).

But at a first try this didn’t worked: extracting the 3 moduli from the &unk_4077A0 variable and using them for CRT didn’t decrypted the clear text. So, additional investigations were required. I decided to understand how the BN_hex2bn was working.

Looking at the openssl source code I noticed that the input value is saved in a structure like this:

struct bignum_st {
    BN_ULONG *d;                /*
                                 * Pointer to an array of 'BN_BITS2' bit
                                 * chunks. These chunks are organised in
                                 * a least significant chunk first order.
                                 */
    int top;                    /* Index of last used d +1. */
    /* The next are internal book keeping for bn_expand. */
    int dmax;                   /* Size of the d array. */
    int neg;                    /* one if the number is negative */
    int flags;
};

The important parts here are the first pointer to the array and the number of chunks used.

Inspecting the structure at runtime (for example for the first check) we see:

00000000  60 9c 40 00 00 00 00 00 20 00 00 00 20 00 00 00  |`.@..... ... ...|
00000010  00 00 00 00 01 00 00 00 11 01 00 00 00 00 00 00  |................|
00000020  d9 7a 73 e1 6a b0 a0 93 0c 32 e2 b3 ad b6 8d 66  |Ùzsáj° ..2â³.¶.f|
00000030  13 cd c1 68 1a a3 2c 97 3f 05 4c f8 e2 ec 2d 93  |.ÍÁh.£,.?.Løâì-.|
00000040  4e 77 0b 8f 50 ba f5 6a 3c fe 3f 26 d9 2e c5 10  |Nw..Pºõj<þ?&Ù.Å.|
...[SNIP]...

The number of chunks used is 20 (at offset 8 and 12) and the array begins with D9 7A...

At this point I converted the 20 chunks from the array following the comment hint (“least significant chunk first order”) by using the Python script dechunk.py (see Appendix A).

I obtained 3 different integers:

17959660585528350981087229833089087041215560187382316556746957230355059483594891125958802753322256257649447632402129029221065425525334504258002011875275617974513210516911283016842516199205910434732830087983613243378091698457834303983135768350431128028922526385291185694222918445013448701212463971358419972795505836767533655330094785786703996887878883462207083750246247477039516771331044758698538522337835475815304954718664442606513177428924650236459427770081040441646825089395104770560828304370337271939281080874605399233579629714861133171223893824189664592421533550662441784661913277996034676529944162994600046459609

13072468815082586647862658273655323247412092009677227879535387171962000285965368607244319621581261186127104470304686902538295138033951934647726604446168657176552275691798599597433942749647105708330816133717129129669921505081122358741803255099841001655615379245575842007977759626031851668795363817630741718776763846933181644035334871401319019833611524327416238319541763988641554471521764738899933853847725465226580139054847549550546156747007665996645734012837544860452041742732386997746653703368214814504870572642220947797796861268422098575216871961291854391489282690923686055605046308553653176902145971851292577353307

22434578097189302614139644874467353905751203927383435839833778479475571590489398475642666590809955083696753806303335092436124366586602780079156343318947956668608846439968845667625417548925806150987082706325912738826505357080025249859716295819147520443977637064356855621932445652656764474004264543999266968275993206631028017377796472012678533468383291539582882220585761947815646692634320613781352942681096924274039493624680619005832597571704855982661605582747223547612849785569766052963889841431093906938248551219204557224282379442642425850054222294605863045545560169261263340682073786357713763347999499620773348887317

I used these 3 integers (which are pairwise co-prime) to apply the CRT-RSAHastad attack (https://github.com/JulesDT/RSA-Hastad) on the ciphertexts and I obtained the clear text sentence which was expected as a first input:

Head to the library. Upon entering, politely ask the librarian if they are aware of any extra documents refering to Madame De Maintenon.

With this the last AES was correctly decrypted and I obtained the second part of the coordinates.

Appendix A

def bytes_to_int(bytes_data, bn_bits2):
    """
    Convert a sequence of bytes into an integer. The bytes are assumed to be ordered
    with the least significant chunk first. Each chunk is 'bn_bits2' bits.
    """
    int_representation = 0
    bytes_per_chunk = bn_bits2 // 8

    # Process each chunk and shift it into its correct position
    for i in range(0, len(bytes_data), bytes_per_chunk):
        chunk = bytes_data[i:i+bytes_per_chunk]
        chunk_value = int.from_bytes(chunk, byteorder='little')
        int_representation += chunk_value << (i * 8)

    return int_representation

# Example usage
# Replace this with the actual byte array you have:

bytes_data = b'\xd9\x7a\x73\xe1\x6a\xb0\xa0\x93\x0c\x32\xe2\xb3\xad\xb6\x8d\x66\x13\xcd\xc1\x68\x1a\xa3\x2c\x97\x3f\x05\x4c\xf8\xe2\xec\x2d\x93\x4e\x77\x0b\x8f\x50\xba\xf5\x6a\x3c\xfe\x3f\x26\xd9\x2e\xc5\x10\x3c\xec\xd5\xe7\x1d\x44\xe3\xb4\x84\x53\xcd\xe0\xd5\xd1\x6a\xf1\x1b\x12\xcd\xd7\x8e\xf6\xc8\xbc\x7b\xfd\xce\x8a\x45\xbb\xf4\x49\xbb\x1a\xbb\xb0\x38\xb4\xf6\x1f\x21\x9e\x2a\x58\x9f\x65\x70\xaa\x1f\xf0\xd2\x18\x55\xac\x0e\xfa\x71\xe4\xa4\x34\x0e\x21\xaa\xfa\xa3\x01\x0d\x76\xde\xdb\x77\x8d\xa3\x21\xcf\x0b\x03\x92\xf2\x90\xd2\x61\x10\x10\x02\xd4\x6f\x98\xe2\x1a\x0a\x96\xd4\x0c\xec\xe3\xa0\x4d\xbc\x05\xa1\x37\xbb\x11\x75\xd6\x4e\xd2\xd5\x86\xbf\x50\x47\x7e\xe7\x4b\x8d\xa6\x8d\x29\x7c\x7b\xda\xbd\x41\x1e\xec\xa6\x4e\xff\xde\x32\xab\x7c\xda\x64\x53\x7d\x5d\x6a\x83\x66\x9c\x15\x20\xb0\x55\x19\xc9\x40\xeb\x90\xe4\xeb\xef\xc6\xce\x08\xbb\x52\xd8\xe7\x3f\x55\x1e\x00\x2f\xb4\xef\xdd\xf8\xc9\x70\xae\x53\xf5\xe1\x2d\x40\x89\x59\x1c\x83\x5c\xcb\x11\xd0\x30\x46\xf6\xb9\xc6\x58\x0d\xfc\xd9\xb5\xfa\x3b\x0a\xd5\x46\x14\x14\x27\x96\x44\x8e'

#bytes_data = b'\x5b\xce\xf7\xeb\xb0\xab\x71\x22\x60\xff\x29\x17\x2f\x5f\xb3\x45\x3d\xf5\x45\x72\x92\x3d\xd8\xd7\x2e\xd5\xa1\x1b\x76\x28\x0c\xd9\x6b\xca\x20\x04\x71\xa0\x7c\x66\xf4\x5a\xbe\x33\xb1\xa5\x24\x45\x91\x9b\x7d\xb1\x9b\xb7\xbf\x56\x39\x21\x2f\x5c\x83\x60\xe8\xae\x5e\xb3\x00\x4e\xb9\x0e\xe2\x36\x8a\x30\x5c\x54\x04\x27\xc8\x97\x35\x4f\x84\xf7\x40\x31\xe6\xf5\xb6\xbd\xae\x88\xc6\x8d\xed\x20\xe9\x30\x44\xfc\x36\x26\x0a\xe4\xe3\x5d\xa8\x1e\x7b\xb1\xa6\xe2\x7f\xf2\x61\x2a\x85\xee\x94\x47\xf1\x58\xa2\xc6\x12\x63\x07\xca\x49\x39\x58\x89\x6c\x90\x6c\x15\xb4\x2e\x6a\xdb\x3f\x61\xad\xd9\xd4\x09\xe2\x08\xf6\x5e\xef\x18\x65\x6b\x1f\x92\x2d\x5c\xe2\x57\x09\x52\x78\x3d\x49\x01\xfc\x1c\xed\x98\x82\x71\x5c\xbe\xc0\x69\x90\xb0\x26\x6e\x86\x86\x4e\x3c\xd0\x31\x11\x74\x6f\xf2\x1a\x2f\xd0\x95\xee\x03\xc3\xd6\xf5\x3c\xa2\xce\x11\x9e\x84\x83\x60\x17\xb5\x5c\xa6\x34\x61\xca\x95\xa2\xe1\x1c\x45\x18\x95\xb1\xd1\xb9\x88\xc0\x9a\xa0\xa3\xa4\xc6\x60\xcb\x12\xd7\xe4\x47\x62\x2d\x0b\xd9\x6b\x19\x80\x8a\x83\x64\xfe\x9f\xc2\xf7\xcc\x64\xcc\x8d\x67'

#bytes_data = b'\x15\xcb\xf9\x7a\x89\xbf\xec\xe2\x62\x47\x02\x2d\x6b\x2e\x34\x17\xca\xd7\xd8\xb3\x0b\x7f\x81\x0b\x1b\x7b\x66\x8e\x5b\x66\x32\xad\x4e\xc2\x3c\x77\xa3\xd3\xfd\xcc\x10\x18\x84\x10\x98\xff\xeb\xfb\x9c\x6d\xc7\xbb\x19\x78\xa6\x46\x93\xfa\xc6\xa3\x54\xc9\x90\x69\x05\x3d\x2e\xb1\x01\x1a\xce\x65\x1f\xc9\x49\xfa\x92\x2a\x33\xac\xf8\xb8\x4a\x77\x5c\x69\x32\x89\x29\x8b\x6e\x16\xda\xcd\x74\xe3\x14\x3e\x25\x24\x65\x14\x71\x68\xcd\xcb\xe9\xeb\x5e\x95\xb2\xc2\x37\x35\x1d\x15\xab\xf0\x4a\xd4\xbf\x66\x87\x3e\x5e\xa8\x08\x64\xbd\xa9\x00\xbc\xd0\xc3\x96\x18\xba\x96\x28\x60\x4b\xcb\x4a\x9f\x91\x86\xb9\xda\xf5\x32\xf9\x0a\x3c\xc6\x4d\x8c\xdd\x3b\x59\x06\xac\xfd\x44\x23\xc6\xef\x5e\x33\x68\x45\x35\x64\x90\x8e\xe6\x70\x58\x92\xdb\x8c\x8e\xc8\x61\x39\x6a\x56\xf1\xbd\xb3\xaa\xf4\xc4\x0a\x44\xf4\xda\x45\x49\xeb\x44\x7a\x03\x49\x75\xc5\xf9\xbc\xc9\xcc\x62\x25\x79\x8e\xfa\xa0\xdc\x01\x2e\x22\xa6\x41\xeb\xdb\x31\x44\x19\x39\x93\x62\x38\x4c\xbb\xd7\x02\x0e\x76\x9c\x49\xb2\x22\x27\x80\xa9\xca\xdd\x6b\x0f\x2c\x86\x27\x57\xef\xbd\x51\xb7\xb1'

# Set BN_BITS2
bn_bits2 = 64

# Convert to integer
integer_representation = bytes_to_int(bytes_data, bn_bits2)
print("Integer representation:", integer_representation)