In November of 2023, Hex-Rays published their second CTF challenge: “Madame De Maintenon’s Cryptographic Pursuit – Unmasking the Traitors”.
In the heart of Versailles, an unexpected discovery sent ripples through the palace. Madame de Maintenon (the IDA Lady), the secret wife of Louis XIV, stumbled upon an unusual letter, containing a hidden plot for a coup. This letter, with its strange symbols, triggered a quest for answers. With unwavering determination, Madame de Maintenon (aka Françoise d’Aubigné or Marquise de Maintenon), set out to uncover its secrets – very much like you, the adventurous participants of this CTF challenge. Each passing day brought new discoveries. Clues emerged, and with every piece found, the suspense deepened. Francoise’s journey reflects your own – a testament to preservance and intellect. As you delve into the story, remember that your goal is to uncover the location of the traitors, just as she sought the truth behind the enigmatic letter.
Once, the fate of France hung in the balance. Now, it is your expertise and ingenuity that will determine the outcome of this "manhunt".
The challenge consists of a singular binary file. Rather than a flag, the challenge introduction suggests we’re looking for some kind of location.
madame (30944 bytes)
ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=ab32392967c6b82b041dc3389df9e226916506ed, for GNU/Linux 3.2.0, stripped
md5: f4cc7f4e8849fc83d34dbe1b2d9a44e1
Starting the binary presents us with something that resembles a text-based adventure game.
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?
Well, what do we do? Opening the challenge up in IDA, as Hexrays would want us to, we readily identify a main function with four functions. After minor cleanup and appending the function tail at 0x402640, we get:
void __fastcall main(int a1, char **a2, char **a3)
{
char *v3; // rax
char v4[32]; // [rsp-20h] [rbp-28h] BYREF
puts(aYouHaveHeardRu);
sub_401870();
sub_401A50();
sub_401CD0();
sub_401F50();
if ( dword_408488 && dword_408484 )
{
if ( dword_408480 )
{
v3 = strncpy(&v4, byte_40838A, 32uLL);
sub_4017C0(v3, byte_4050A0);
}
}
}
The first puts call is responsible for the introductory text. Then we dive into sub_401870.
This is the first stage. Going through this function shows us what command we need to enter to proceed. After cleaning it up a bit, we’re left with the following decompilation.
int page1()
{
char *resp_ptr; // rdx
int v1; // ecx
unsigned int v2; // eax
unsigned __int8 *output_ptr; // rbx
_BYTE *c_ptr; // r12
unsigned __int8 *c_block; // rdi
_BYTE aes_key[32]; // [rsp+0h] [rbp-838h] BYREF
char dest[32]; // [rsp+20h] [rbp-818h] BYREF
char resp[200]; // [rsp+40h] [rbp-7F8h] BYREF
char aes_key_struct[256]; // [rsp+110h] [rbp-728h] BYREF
_BYTE output[1536]; // [rsp+210h] [rbp-628h] BYREF
memset(resp, 0, sizeof(resp));
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?");
get_response(resp);
resp_ptr = resp;
do
{
v1 = *(_DWORD *)resp_ptr;
resp_ptr += 4;
v2 = ~v1 & (v1 - 0x1010101) & 0x80808080;
}
while ( !v2 );
if ( (~v1 & (v1 - 0x1010101) & 0x8080) == 0 )
{
v2 >>= 16;
resp_ptr += 2;
}
if ( (unsigned __int64)(&resp_ptr[-__CFADD__((_BYTE)v2, (_BYTE)v2) - 3] - resp) <= 18
|| memcmp("Head to the library", resp, 19uLL) )
{
wrap_puts_exit(
"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(resp_1, resp, 200uLL);
memset(aes_key, 0, sizeof(aes_key));
output_ptr = output;
strncpy(aes_key, resp_1, 19uLL);
memset(output, 0, sizeof(output));
strncpy(dest, aes_key, 32uLL);
AES_set_decrypt_key(aes_key, 256, aes_key_struct);
c_ptr = aes_ciphertext_1;
do
{
c_block = c_ptr;
c_ptr += 16;
AES_decrypt(c_block, output_ptr, aes_key_struct);
output_ptr += 16;
}
while ( c_ptr != &aes_ciphertext_1[1536] );
RSA_func();
return puts(output);
}
The fragment memcmp("Head to the library", resp, 19uLL) is pretty clear about it: we should head to the library. Remark that the weird bitwise operations before it appear to be an inlined strlen function; if we squint a bit, we can see similarities to the glibc implementation. The comparison to 18 makes sense.
If we’ve given it the correct command (i.e, Head to the library), the first 19 characters are used as an AES key to decrypt the next bit of storyline. Additionally, a weird function that does some RSA operation is called. Let’s label it RSA_func for now.
You locate the section of the library where the diary was rumoured to have been stored, but its place is empty. After a few minutes browsing, you find it! A single page, but one that holds the key to a fascinating mystery.
The page reads:
_______________
21 October 1684
Dear Diary,
Today, an unsettling discovery came my way. A letter, it was, with ominous tidings of a plot against our cherished Louis XIV. The message was unlike any other, its meaning hidden behind unfamiliar symbols.
Within the letter lay a clue, 01000010, a piece of the puzzle. It hinted at more secrets, and I felt compelled to uncover them. But where to find the next piece?
Yours in devotion,
Madame De Maintenon
_______________
The page was lying on the shelf in the open, maybe it fell from somewhere. You see a few more loose pages sticking out of some other books around you. What happened here?
What do you do?
Well, let’s have a look at the next function to figure that out.
int page2()
{
_BYTE *c_ptr; // rbx
_BYTE *output_ptr; // r12
_BYTE *c_block; // rdi
_BYTE key[32]; // [rsp+0h] [rbp-838h] BYREF
char dest[32]; // [rsp+20h] [rbp-818h] BYREF
_BYTE resp[200]; // [rsp+40h] [rbp-7F8h] BYREF
char aes_key_struct[256]; // [rsp+110h] [rbp-728h] BYREF
_BYTE output[1536]; // [rsp+210h] [rbp-628h] BYREF
memset(resp, 0, sizeof(resp));
puts("What do you do?\n");
get_response(resp);
if ( !(unsigned int)sub_402560(resp) )
wrap_puts_exit(
"You were unable to locate the second page of the diary, after many hours of searching you give up and return home");
strncpy(resp_2, resp, 200uLL);
const_A[0] = _mm_load_si128(const_B);
const_A[1] = _mm_load_si128(&const_B[1]);
const_A[2] = _mm_load_si128(&const_B[2]);
c_ptr = aes_ciphertext_2;
const_A[3] = _mm_load_si128(&const_B[3]);
const_A[4] = _mm_load_si128(&const_B[4]);
const_A[5] = _mm_load_si128(&const_B[5]);
const_A[6] = _mm_load_si128(&const_B[6]);
const_A[7] = _mm_load_si128(&const_B[7]);
const_A[8] = _mm_load_si128(&const_B[8]);
const_A[9] = _mm_load_si128(&const_B[9]);
const_A[10] = _mm_load_si128(&const_B[10]);
const_A[11] = _mm_load_si128(&const_B[11]);
const_A[12] = _mm_load_si128(&const_B[12]);
const_A[13] = _mm_load_si128(&const_B[13]);
const_A[14] = _mm_load_si128(&const_B[14]);
const_A[15] = _mm_load_si128(&const_B[15]);
memset(key, 0, sizeof(key));
strncpy(key, resp_2, 29uLL);
memset(output, 0, sizeof(output));
strncpy(dest, key, 32uLL);
AES_set_decrypt_key(key, 256, aes_key_struct);
output_ptr = output;
do
{
c_block = c_ptr;
c_ptr += 16;
AES_decrypt(c_block, output_ptr, aes_key_struct);
output_ptr += 16;
}
while ( c_ptr != &aes_ciphertext_2[1536] );
RSA_func();
return puts(output);
}
It appears the response is checked in sub_402560. Additionally, there’s some constants being copied over, but other than that the structure is roughly the same as for page 1.
After some more tidying, sub_402560 indeed shows us how the next command is checked.
__int64 __fastcall sub_402560(char *input)
{
char *inbuf_ptr; // rax
char *xorkey_ptr; // rdx
char xorbyte; // cl
char *input_ptr_; // rdi
__int64 j; // rax
char i; // dl
_BYTE ref[32]; // [rsp+0h] [rbp-148h]
_BYTE xorkey[32]; // [rsp+20h] [rbp-128h] BYREF
_BYTE in_buf[256]; // [rsp+40h] [rbp-108h] BYREF
*(_QWORD *)&ref[16] = 0xED3BF4E402F3B0CFLL;
*(__m128i *)xorkey = _mm_load_si128(xorkey_xmm_const);
*(_DWORD *)&ref[24] = 0x90EC7F44;
*(__m128i *)&xorkey[16] = _mm_load_si128(&xorkey_xmm_const[1]);
ref[28] = 0x9F;
*(__m128i *)ref = _mm_load_si128(&ref_xmm_const);
inbuf_ptr = strncpy(in_buf, input, 256uLL);
xorkey_ptr = &xorkey[1];
xorbyte = 0x44;
input_ptr_ = inbuf_ptr;
while ( 1 )
{
*inbuf_ptr ^= xorbyte;
if ( ++inbuf_ptr == &in_buf[29] )
break;
xorbyte = *xorkey_ptr++;
}
j = 0LL;
for ( i = 7; ; i = ref[j] )
{
if ( input_ptr_[j] != i )
goto LABEL_10;
if ( ++j == 29 )
break;
}
if ( strlen(input) > 0x1D )
LABEL_10:
wrap_puts_exit("You were unable to locate the next page of the diary");
return 1LL;
}
Note that both xorkey and cmp are 32-byte sequences. xorkey is loaded entirely from memory using movdqa instructions, but cmp is a bit more subtle: carefully dissecting the assembly instructions shows how it is build up out of immediate values. By fixing the stack variables, IDA recognizes the assignments.
.text:000000000040256E mov rax, 0ED3BF4E402F3B0CFh
[..]
.text:000000000040258F mov qword ptr [rsp+148h+ref+10h], rax
[..]
.text:00000000004025A1 mov dword ptr [rsp+148h+ref+18h], 90EC7F44h
[..]
.text:00000000004025AE movdqa xmm0, xmmword ptr cs:ref_xmm_const
.text:00000000004025B6 mov [rsp+148h+ref+1Ch], 9Fh
.text:00000000004025BB movaps xmmword ptr [rsp+148h+ref], xmm0
ref by using a debugger. Setting a tracepoint at the cmp [rdi+rax], dl instruction and patching out the jnz makes it easy to quickly print the reference bytes. Only after I knew what the bytes were did I pause long enough to properly locate them in the code.
We see that the input is xored with xorkey and then compared to ref; figuring out the correct input is a matter of xoring xorkey with ref.
>>> xorkey = bytes.fromhex("443663c81c2884a08d3a2f39f7ee924fa7d5d36c818c4fcd371789fcf91cc21b")
>>> ref = bytes.fromhex("075e06ab7708e6cfe2515c199880b23bcfb0f302e4f43bed447fec909f")
>>> bytes(a ^ b for a, b in zip(xorkey, ref))
b'Check books on the next shelf'
We check the books on the next shelf.
What luck! While going through the books on the next shelf over, you find another page stuck under them, similarly weathered to the first one. The message is hard to decipher due to it's age, but after some careful analysis you manage to decode it.
It reads:
_______________
24 October 1684
Beloved Diary,
As I delved into the code, a new piece surfaced, 00110111. It whispered of hidden truths, yet it also hinted that there was more to uncover. The puzzle remained incomplete.
Yours eternally,
Madame De Maintenon
_______________
Another clue, what could it mean? And where are the rest?
What do you do?
Onwards to page 3. It’s almost identical to page 2, but for a different check and a different constant.
int page3()
{
_BYTE *c_ptr; // rbx
_BYTE *output_ptr; // r12
_BYTE *c_block; // rdi
_BYTE key[32]; // [rsp+0h] [rbp-838h] BYREF
char dest[32]; // [rsp+20h] [rbp-818h] BYREF
_BYTE resp[200]; // [rsp+40h] [rbp-7F8h] BYREF
char aes_key_struct[256]; // [rsp+110h] [rbp-728h] BYREF
_BYTE output[1536]; // [rsp+210h] [rbp-628h] BYREF
memset(resp, 0, sizeof(resp));
puts("What do you do?\n");
get_response(resp);
if ( !sub_401300(resp) )
wrap_puts_exit(
"Where could the third page possibly be? How could your fellow historian have been so careless with such a priceless artifact???");
strncpy(resp_3, resp, 200uLL);
const_A[0] = _mm_load_si128(const_C);
const_A[1] = _mm_load_si128(&const_C[1]);
const_A[2] = _mm_load_si128(&const_C[2]);
c_ptr = aes_ciphertext_3;
const_A[3] = _mm_load_si128(&const_C[3]);
const_A[4] = _mm_load_si128(&const_C[4]);
const_A[5] = _mm_load_si128(&const_C[5]);
const_A[6] = _mm_load_si128(&const_C[6]);
const_A[7] = _mm_load_si128(&const_C[7]);
const_A[8] = _mm_load_si128(&const_C[8]);
const_A[9] = _mm_load_si128(&const_C[9]);
const_A[10] = _mm_load_si128(&const_C[10]);
const_A[11] = _mm_load_si128(&const_C[11]);
const_A[12] = _mm_load_si128(&const_C[12]);
const_A[13] = _mm_load_si128(&const_C[13]);
const_A[14] = _mm_load_si128(&const_C[14]);
const_A[15] = _mm_load_si128(&const_C[15]);
memset(key, 0, sizeof(key));
strncpy(key, resp_3, 25uLL);
memset(output, 0, sizeof(output));
strncpy(dest, key, 32uLL);
AES_set_decrypt_key(key, 256, aes_key_struct);
output_ptr = output;
do
{
c_block = c_ptr;
c_ptr += 16;
AES_decrypt(c_block, output_ptr, aes_key_struct);
output_ptr += 16;
}
while ( c_ptr != &aes_ciphertext_3[1536] );
RSA_func();
return puts(output);
}
The check function is an intimidating but surprisingly straight-forward list of conditions.
_BOOL8 __fastcall sub_401300(_BYTE *a1)
{
int n; // [rsp+14h] [rbp-4h]
n = (unsigned __int8)(*a1 + 15) == 98;
if ( (a1[1] ^ 0x3B) == 94 )
++n;
if ( (unsigned __int8)(a1[2] + 57) == 154 )
++n;
if ( (a1[3] ^ 0x38) == 74 )
++n;
if ( (a1[4] ^ 0x74) == 23 )
++n;
if ( (a1[5] ^ 0x3B) == 83 )
++n;
if ( (unsigned __int8)(a1[6] + 3) == 35 )
++n;
if ( (unsigned __int8)(a1[7] - 67) == 49 )
++n;
if ( (unsigned __int8)(a1[8] + 9) == 113 )
++n;
if ( (unsigned __int8)(a1[9] + 12) == 113 )
++n;
if ( (unsigned __int8)(a1[10] + 90) == 122 )
++n;
if ( (unsigned __int8)(a1[11] - 16) == 82 )
++n;
if ( (unsigned __int8)(a1[12] + 123) == 234 )
++n;
if ( (a1[13] ^ 0x29) == 70 )
++n;
if ( (unsigned __int8)(a1[14] - 127) == 236 )
++n;
if ( (a1[15] ^ 2) == 34 )
++n;
if ( (unsigned __int8)(a1[16] + 84) == 186 )
++n;
if ( (a1[17] ^ 0xB0) == 223 )
++n;
if ( (unsigned __int8)(a1[18] + 102) == 216 )
++n;
if ( (unsigned __int8)(a1[19] - 109) == 179 )
++n;
if ( (a1[20] ^ 0x20) == 67 )
++n;
if ( (unsigned __int8)(a1[21] + 111) == 219 )
++n;
if ( (unsigned __int8)(a1[22] + 24) == 141 )
++n;
if ( (unsigned __int8)(a1[23] + 9) == 110 )
++n;
if ( (unsigned __int8)(a1[24] + 48) == 163 )
++n;
if ( (unsigned __int8)(a1[25] - 19) == 237 )
++n;
if ( (unsigned __int8)(a1[26] - 61) == 195 )
++n;
if ( (unsigned __int8)(a1[27] - 109) == 147 )
++n;
if ( (unsigned __int8)(a1[28] - 118) == 138 )
++n;
if ( (unsigned __int8)(a1[29] + 126) == 126 )
++n;
if ( (unsigned __int8)(a1[30] + 42) == 42 )
++n;
if ( (a1[31] ^ 0x5C) == 92 )
++n;
return n == 32;
}
While I hear that some decompilers clean up the math a bit more, Hex-Rays leaves us with some computations to do. Through some find-and-replace kung fu in Sublime Text (careful with the asymmetrical additions and subtractions), this quickly turns into:
>> a1 = [0] * 32
>> a1[0] = 98 - 15
>> a1[1] = 94 ^ 0x3B
>> a1[2] = 154 - 57
>> a1[3] = 74 ^ 0x38
>> a1[4] = 23 ^ 0x74
>> a1[5] = 83 ^ 0x3B
>> a1[6] = 35 - 3
>> a1[7] = 49 + 67
>> a1[8] = 113 - 9
>> a1[9] = 113 - 12
>> a1[10] = 122 - 90
>> a1[11] = 82 + 16
>> a1[12] = 234 - 123
>> a1[13] = 70 ^ 0x29
>> a1[14] = 236 + 127
>> a1[15] = 34 ^ 2
>> a1[16] = 186 - 84
>> a1[17] = 223 ^ 0xB0
>> a1[18] = 216 - 102
>> a1[19] = 179 + 109
>> a1[20] = 67 ^ 0x20
>> a1[21] = 219 - 111
>> a1[22] = 141 - 24
>> a1[23] = 110 - 9
>> a1[24] = 163 - 48
>> a1[25] = 237 + 19
>> a1[26] = 195 + 61
>> a1[27] = 147 + 109
>> a1[28] = 138 + 118
>> a1[29] = 126 - 126
>> a1[30] = 42 - 42
>> a1[31] = 92 ^ 0x5C
>> a1
[83, 101, 97, 114, 99, 104, 32, 116, 104, 101, 32, 98, 111, 111, 363, 32, 102, 111, 114, 288, 99, 108, 117, 101, 115, 256, 256, 256, 256, 0, 0, 0]
>> bytes(a & 0xFF for a in a1)
b'Search the book for clues\x00\x00\x00\x00\x00\x00\x00'
So, clearly, we search the book for clues.
From the lack of dust on the book you found, it's clear these were recently borrowed. Maybe the pages got mixed up with the books when being reshelved?
You look up the name of the last borrower, and look up what other books they may have checked out. There you find the diary records mentioned, as well as one other book.
Finding that book on the shelves yields another page!
_______________
30 October 1684
Dearest Diary,
Another fragment emerged, 10110010. It was a step closer to the full picture, but it also held a hint. The rest of the location, it suggested, was not far away.
Yours eternally,
Madame De Maintenon
_______________
What do you do?
Another page, another decryption function.
int page4()
{
_BYTE *c_ptr; // rbx
_BYTE *output_ptr; // r12
_BYTE *c_block; // rdi
_BYTE v4[32]; // [rsp+0h] [rbp-838h] BYREF
char dest[32]; // [rsp+20h] [rbp-818h] BYREF
_BYTE resp[200]; // [rsp+40h] [rbp-7F8h] BYREF
char aes_key_struct[256]; // [rsp+110h] [rbp-728h] BYREF
_BYTE output[1536]; // [rsp+210h] [rbp-628h] BYREF
memset(resp, 0, sizeof(resp));
puts("What do you do?\n");
get_response(resp);
if ( !sub_4016F0(resp) )
wrap_puts_exit("You're so close to the final page! You survey all three pages you discovered in despair. So close yet so far.");
strncpy(resp_4, resp, 200uLL);
const_C[0] = _mm_load_si128(const_B);
const_C[1] = _mm_load_si128(&const_B[1]);
const_C[2] = _mm_load_si128(&const_B[2]);
c_ptr = aes_ciphertext_4;
const_C[3] = _mm_load_si128(&const_B[3]);
const_C[4] = _mm_load_si128(&const_B[4]);
const_C[5] = _mm_load_si128(&const_B[5]);
const_C[6] = _mm_load_si128(&const_B[6]);
const_C[7] = _mm_load_si128(&const_B[7]);
const_C[8] = _mm_load_si128(&const_B[8]);
const_C[9] = _mm_load_si128(&const_B[9]);
const_C[10] = _mm_load_si128(&const_B[10]);
const_C[11] = _mm_load_si128(&const_B[11]);
const_C[12] = _mm_load_si128(&const_B[12]);
const_C[13] = _mm_load_si128(&const_B[13]);
const_C[14] = _mm_load_si128(&const_B[14]);
const_C[15] = _mm_load_si128(&const_B[15]);
memset(v4, 0, sizeof(v4));
strncpy(v4, resp_4, 19uLL);
memset(output, 0, sizeof(output));
strncpy(dest, v4, 0x20uLL);
AES_set_decrypt_key(v4, 256, aes_key_struct);
output_ptr = output;
do
{
c_block = c_ptr;
c_ptr += 16;
AES_decrypt(c_block, output_ptr, aes_key_struct);
output_ptr += 16;
}
while ( c_ptr != &aes_ciphertext_4[1536] );
RSA_func();
return puts(output);
}
We dive right into the check in sub_4016F0.
_BOOL8 __fastcall sub_4016F0(char *input)
{
_BYTE *c_ptr; // r14
_BYTE *output_ptr; // rsi
_BYTE *c_block; // rdi
size_t input_len; // rax
_BYTE key[32]; // [rsp+0h] [rbp-748h] BYREF
char aes_key_struct[256]; // [rsp+20h] [rbp-728h] BYREF
char ciphertext[1536]; // [rsp+120h] [rbp-628h] BYREF
char v10; // [rsp+720h] [rbp-28h] BYREF
qmemcpy(ciphertext, ciphertext_ref_page4, sizeof(ciphertext));
*(__m128i *)key = _mm_load_si128(resp_3);
*(__m128i *)&key[16] = _mm_load_si128(&resp_3[1]);
c_ptr = ciphertext;
AES_set_decrypt_key(key, 256, aes_key_struct);
do
{
output_ptr = c_ptr;
c_block = c_ptr;
c_ptr += 16;
AES_decrypt(c_block, output_ptr, aes_key_struct);
}
while ( &v10 != c_ptr );
qmemcpy(ciphertext_ref_page4, ciphertext, 0x600uLL);
input_len = strlen(input);
return strncmp(input, ciphertext_ref_page4, input_len) == 0;
}
This check uses our previous response to decrypt a ciphertext, and compares our input to the first bytes of the resulting plaintext.
While we could do this statically, this is the kind of thing debuggers were made for. Setting a breakpoint right after the AES decryption step, we note that the expected plaintext is Turn over the page.
Turning the page over, you find the final entry to the diary!
_______________
9 November 1684
Beloved Diary,
Today, the last piece fell into place, 00000101. With it came the realization that the remaining location lay elsewhere, a mystery yet to be unraveled. Our mission is clear, my dear diary; we must decipher the rest to protect our homeland.
Yours in devotion,
Madame de Maintenon
_______________
What does this mean? You've worked so hard but yet still don't have the information you seek? What now?
You have all four pages your rival claimed to have found, and yet are no closer to the truth.
After several hours of fruitlessly searching for meaning in the messages, you give up and turn to leave in defeat.
This is where the trail ends; we have recovered four pages, containing four sequences of seemingly meaningless bits; 01000010 00110111 10110010 00000101. No more ‘What do you do?’
There are still a few loose threads to pull, though. The main function has a fifth subroutine (sub_4017C0), and each page function called a function we’ve labeled RSA_func and ignored so far.
Let’s first look at RSA_func.
int RSA_func()
{
void *RSA_struct; // rax
void *RSA_struct_1; // r12
int result; // eax
__int64 bn_n; // [rsp+0h] [rbp-128h] BYREF
__int64 bn_e; // [rsp+8h] [rbp-120h] BYREF
_BYTE to[256]; // [rsp+10h] [rbp-118h] BYREF
bn_n = 0LL;
bn_e = 0LL;
RSA_struct = (void *)RSA_new();
memset(to, 0, sizeof(to));
RSA_struct_1 = RSA_struct;
BN_hex2bn(&bn_n, RSA_N);
BN_hex2bn(&bn_e, "3");
RSA_set0_key(RSA_struct_1, bn_n, bn_e, 0LL);
RSA_public_encrypt(256, (unsigned __int8 *)&resp_1, to, RSA_struct_1, 3);
result = memcmp(to, const_A, 256uLL);
if ( !result )
{
if ( flag_A )
{
result = flag_B;
if ( flag_B )
flag_C = 1;
else
flag_B = 1;
}
else
{
flag_A = 1;
}
}
return result;
}
It appears this function loads an RSA public key from the global RSA_N, and uses it to encrypt resp_1 (remember: this is our response when decrypting the first page!). It then compares the result to const_A. We’ve also seen const_A before: it is written to in page2 and page3, but that’s after the first call to RSA_func! If memcmp outputs an agreeable result, a flag is set; every call to RSA_func sets a new flag.
Checking in a debugger reveals that simply letting it encrypt our initial message Head to the library is no good. If we take a closer look at the comparison in page1(), we note that it only checks if our message starts with Head to the library. We can append an arbitrary tail; it will copy the first 200 bytes.
As $e = 3$ and the message $m$ is not padded, we may be able to perform a cube root attack: in general, if $m^3 < n$, we can simply compute $\sqrt[3]{c} = \sqrt[3]{m^e} = \sqrt[3]{m^3} = m$. However, in our case, our message starts with non-zero bytes (Head to the library). That means it’s already quite close to $n$, so $m^3$ definitely exceeds $n$.
Looking for cross-references for the flags used in RSA_func, we find that they’re used in get_response.
int __fastcall get_response(_BYTE *output)
{
__int64 inlen; // rbx
int c; // eax
if ( flag_A )
qmemcpy(RSA_N, &RSA_N_2, sizeof(RSA_N));
if ( flag_B )
qmemcpy(RSA_N, &RSA_N_3, sizeof(RSA_N));
inlen = 0LL;
while ( 1 )
{
c = getc(stdin);
if ( (_BYTE)c == '\n' || !(_BYTE)c )
break;
if ( (unsigned __int8)(c - ' ') > 94u )
wrap_puts_exit("The other patrons of the library are alarmed by the weird noises you're making?!!?");
output[inlen++] = c;
if ( inlen == 199 )
return c;
}
output[(int)inlen] = 0;
return c;
}
We’ve previously not paid much attention to this function, but in addition to getting our input, it appears it also replaces RSA_N. Following the control flow, the flags imply that RSA_N_2 is used in RSA_func in page2, and RSA_N_3 is used in page3.
Let’s rename const_A to $c_A$, and RSA_N to $N_1$, et cetera. We can formulate the three checks as:
\begin{align} m^e &\equiv c_A \mod{N_1} \\ m^e &\equiv c_B \mod{N_2} \\ m^e &\equiv c_C \mod{N_3} \\ \end{align}
This very much looks like Chinese remainder theorem material; we can use this to find $x$ such that $x \equiv m^e \mod{N_1N_2N_3}$. As we have $e = 3$ and likely $m < N_i$ (which, crucially, implies $m^3 < N_1N_2N_3$), we should be able to find $m$ by computing $m = \sqrt[3]{x}$. Now to implement the attack!
We collect the relevant values simply by clicking Edit > Export data for the relevant globals. This is easily done after creating an array. Remark that RSA_N is an ASCII string of hexadecimal values; we’ll have to decode it twice.
from decimal import Decimal, getcontext
const_A = bytes.fromhex(
"7D9E6B093218080A5A34349C0DB3C3C986B102D98C14CDA70BB241B5A838394CABB132D9789DEADE34CA28A3967B77E1DA56C428F40C7D601BE4AE2CB98FEE1B8C8DCB22EEEDFC4BB6462A9C24D4FD45854D5DC04F58E5BC701B6CAC9ED6D02BA05B8935C7FE26F84086CD49D0D66BCB6575AAA791F81BE84768B5961F3FF105EE5EC56FCDAF46A1C7369DD4D58ECD2CE28C7ABB0F35E0DC0752A11B8916969AF491F6BAAFBFFE0877FAE05BA18D6DAF385BCCD88951D72E6B8A4CCCA00FA3BF451F512EAEBF8A20BAAD68E04CAAE68B8FA1DBCBD1AE377B5CF26A7C90B6348569036D76D838B5BCD0E6C423581265EDCCF32279A0B629FAB0FCD485A38B4205"
)
const_B = bytes.fromhex(
"67512E54FF9CD853AB645A69EC8F64009FAD60EEE84CE5D9A5DB8754813D5F9C9C038DA9476CAF9F1B543A289613D02A4ADDC2948B94A965B2DCE0CB93B771236A7F1CF879C86C4F9C07F26BBBD773A7D9EDF6B3981E4F96F355ECDD7407506672E5025EC2C915CA1D5F35D1CCC35679AFF91B833A07FC6BFAD06C9ACF053870E5F52D3DC8F1757355EA4C8DA81D88C37D4B68EBE50274566CB683C19CF5FA6D8851F92D9F9ABD5FD0CBB67551C3FA2018555B9A2995DA96443D9746399FBB86ACA121FE4EBE97D8468DB22A0BD087A1E3FC289C5633157BDC0BCD677FAA26B1FA4BE84285A408EDD28E48AB47535465DCE281111B0B70855CAE188AA6FDAA85"
)
const_C = bytes.fromhex(
"1B48F3DE27DB0A80FFA291B161FFE9CA6CEE79DB559C8047579920CB23C130311A366F8561EE5966EE0A72293671C3587074011759DE78B837B676303C0179DB6CFC6E5D883835738249BC61F8EBC6A6CADE877EEE27F2F74C510F9AC6C723E53F76A8D45DB5D6918CEE530DB1A2102781A481CD0930875B5F40C61A35E685364C5EC883BF5899238EDDC22BA12CB58FCEE49E943C58B13F5CD893FF4C02CDB583EA3359CD26B8360A1873498B4D650C580E5F2EA31F2472A7F8D9A5EE30237C4ADDC4876961AB80F2923E807DBC319D7E4AAEC4C63E1402F68D9D11FF0365A70328E62AA5DA8F1D1B62035381B1A05744E78AB06D1D69BFD45EB41E4E902338"
)
RSA_N = bytes.fromhex(
bytes.fromhex(
"3865343439363237313431343436643530613362666162356439666330643538633662396636343633306430313163623563383331633539383934303264653166353533616537306339663864646566623432663030316535353366653764383532626230386365633665666562653439306562343063393139353562303230313539633636383336613564376435333634646137636162333264656666346561366563316534316264646137623763323938646136386434626537376534373530626638366435643234656436373531316262333761313035626334646130653365633063643439363061316165323938366664343032313031303631643239306632393230333062636632316133386437376462646537363064303161336661616132313065333461346534373166613065616335353138643266303166616137303635396635383261396532313166663662343338623062623161626234396634626234353861636566643762626363386636386564376364313231626631366164316435653063643533383462346533343431646537643565633363313063353265643932363366666533633661663562613530386630623737346539333264656365326638346330353366393732636133316136386331636431333636386462366164623365323332306339336130623036616531373337616439"
).decode("utf-8")
)
RSA_N_2 = bytes.fromhex(
bytes.fromhex(
"3637386463633634636366376332396666653634383338613830313936626439306232643632343765346437313263623630633661346133613039616330383862396431623139353138343531636531613239356361363133346136356362353137363038333834396531316365613233636635643663333033656539356430326631616632366637343131333164303363346538363836366532366230393036396330626535633731383239386564316366633031343933643738353230393537653235633264393231663662363531386566356566363038653230396434643961643631336664623661326562343135366339303663383935383339343963613037363331326336613235386631343739346565383532613631663237666532613662313762316561383564653365343061323633366663343433306539323065643864633638386165626462366635653633313430663738343466333539376338323730343534356333303861333665323065623934653030623335656165653836303833356332663231333935366266623739626231376439623931343532346135623133336265356166343636376361303731303432306361366264393063323837363162613164353265643764383364393237323435663533643435623335663266313732396666363032323731616262306562663763653562"
).decode("utf-8")
)
RSA_N_3 = bytes.fromhex(
bytes.fromhex(
"6231623735316264656635373237383632633066366264646361613938303237323262323439396337363065303264376262346333383632393333393139343433316462656234316136323232653031646361306661386537393235363263636339626366396335373534393033376134346562343934356461663434343061633466346161623362646631353636613339363163383865386364623932353837306536386539303634333534353638333335656566633632333434666461633036353933626464386334646336336330616639333266356461623938363931396634616362346236303238393662613138393663336430626330306139626436343038613835653365383736366266643434616630616231353164333533376332623239353565656265396362636436383731313436353234323533653134653337346364646131363665386232393839333236393563373734616238663861633333326139326661343963393166363563653161303162313265336430353639393063393534613363366661393334366136373831396262633736643963666265626666393831303834313831306363666464336133373733636332346561643332363635623865363637623162306238313766306262336438643763613137333432653662326430323437363265326563626638393761663963623135"
).decode("utf-8")
)
const_A = int.from_bytes(const_A, byteorder="big")
const_B = int.from_bytes(const_B, byteorder="big")
const_C = int.from_bytes(const_C, byteorder="big")
RSA_N = int.from_bytes(RSA_N, byteorder="big")
RSA_N_2 = int.from_bytes(RSA_N_2, byteorder="big")
RSA_N_3 = int.from_bytes(RSA_N_3, byteorder="big")
def CRT(equations):
N = 1
for _, n in equations:
N *= n
x = 0
for a, n in equations:
N_other = N // n
x += a * pow(N_other, -1, n) * N_other
return x % N
def cube_root(n):
getcontext().prec = 1000
return int((Decimal(n) ** (Decimal(1) / Decimal(3))).to_integral_exact())
c = CRT([(const_A, RSA_N), (const_B, RSA_N_2), (const_C, RSA_N_3)])
m = cube_root(c)
m = m.to_bytes(length=256, byteorder="big")
print(m)
This instantly presents us with the message Head to the library. Upon entering, politely ask the librarian if they are aware of any extra documents refering to Madame De Maintenon. Could it be..?
As you move to leave, the librarian comes running!
'I found this in the back room for you, it was a page we found lying around after procesing the most recent batch of new books but we weren't sure what it was for! But look at the signature!'
She hands you a fifth, almost completely blank new page. The aging of the paper looks near identical to the other four pages you found from the diary!
All the page says on it is:
_______________
The other key:
01000000110111000011011000000000
M d. M
_______________
You thank the librarian, and take your leave. You have much to think on. All these 1's and 0's, how do they encode the location of the final target???
#########################
Congratulations! If you've found all 5 pages of the diary you have everything you need! Convert the values you found into coordinates, (hint: IEEE-754 Floating Point), and send those coordinates in an email to marketing@hex-rays.com!
To locally verify your coordinates, the md5 of the coordinates, with 4 decimal places, (including potential leading zeros) in the form:
xx.xxxx, yy.yyyy
Has an md5 of fe72f3730186f24d983a1c2ed1bc1da7 when pasted as a 16 character string into https://www.md5hashgenerator.com/
Right, the binary values. From page 1 to 4, we collected 01000010001101111011001000000101, and page 5 has given us 01000000110111000011011000000000.
>>> import struct
>>>
>>> xb = '01000010001101111011001000000101'
>>> struct.unpack('f', struct.pack('I', int(xb, 2)))
(45.92384719848633,)
>>> yb = '01000000110111000011011000000000'
>>> struct.unpack('f', struct.pack('I', int(yb, 2)))
(6.881591796875,)
Rounding to 4 decimals places, we get 45.9238, 06.8816, which leads us to the incorrect md5 digest 4d365ddff88bed48bd97e9037077d3ee. If we truncate rather than round the y-coordinate and use 45.9238, 06.8815, we do indeed get fe72f3730186f24d983a1c2ed1bc1da7. Hooray!