Messenger.zone (4 solves)

At this ctf we took the third place

Actually Messenger.zone wasn’t difficult crypto, just difficult exploitation challenge. I don’t have any english words to describe exploitation, but in russian it sounds like “через три пизды”.

Introduction

Source code and task description:

We developed secure messenger based on signal specification. We also used only secure analogs of known algorithms. But our comminications has been compromised. An attacker was able to intercepted the message with flag (flag.pcapng). He knows that it was 8th message between clients and they had started chat about 1 min before intercepted message. Can he decrypt the flag?

We got 8th message between clients:

POST /send HTTP/1.1
Host: localhost:7777
User-Agent: python-requests/2.31.0
Accept-Encoding: gzip, deflate
Accept: */*
Connection: keep-alive
Content-Length: 531
Content-Type: application/json

{
"from_m": "B",
"to_m": "A", 
"header": "10007557092155308918620703319005578742802155531542215927047486636897385017421026687658302411228112816312151375158019561914808361055666669789420151300043193;6987718573966126734765996266581284255829614508168823941052245373167186664467200288000376804417263861590165057549101655594459771412333345116018563168510146;1;0", 
"message": "b3f3ca9e16fc1c33c86bb08e9ecee860462cdd6716dd2c32a6701b978c76035ec2973e2c6eac490d54f7918a0167179037459cbda47e4abcd5028a405d8374ada62fd23e3fcb29ab1e36e44ef7cfa438"
}

HTTP/1.1 201 Created
Server: TornadoServer/6.1
Content-Type: application/json; charset=UTF-8
Date: Sun, 16 Jul 2023 21:53:34 GMT
Content-Length: 33

{"message": "Save msg on server"}

we have basic client-server messenger and 2 clients A and B:

Client: B
1 - Change client
2 - Send msg
3 - Pull msgs
q - quit
>

Initial analysis

Server side is just database logic that is not interesting for us. If we look at client we can see 400 lines of code with some strange crypto GOSTs(russian state standard):

Scared? Me too. But with detailed review we can see that most of this code its just bullshit.

First thing we need to notice - usage of random.seed:

size=64
start_time = int(time.time())
random.seed(start_time)

def generate_bytes(n=size):
    return random.randbytes(n)

If we set start_time to some constant and run, then we can see all generated parameters are the same. I ran 2 instances and sent messages “avtor_ti_cho_tvorish???” and “eto rofls” with start_time=1337: As you can see headers are the same, but encrypted messages aren’t.

Lets look at header generation:

class Server:
    def store_message(self, from_m, to_m, header, message):
        print('Save msg on server')
        print('To:',to_m)
        print('From:',from_m)
        print('header:',header)
        print('message:',message)

        data = {'from_m':from_m, 'to_m':to_m, 'header': header_to_string(header), 'message':message.hex()}
        print(data)
        r = requests.post(server_url+send_api, json=data)
        print(r.json())
        return r.json()['message'] == 'Save msg on server'

# by XREFs on store_message we can find this:
class Client:
    def __init__(self, ...):
        ...
        self.RATCHET_dict = dict()
        ...

    def send(self, m_to, msg, send=True):
        if m_to not in self.RATCHET_dict.keys():
            self.start_x3dh(m_to)

        msg = pad2(msg, block_size)
        AD = (self.name + m_to).encode('utf-8')
        head, cipher = self.RATCHET_dict[m_to].RatchetEncrypt(msg, AD)

        if send:
            print('SEND', header_to_string(head).encode('utf-8'), cipher, AD)
            self.server.store_message(self.name, m_to, head, cipher)
        return True

# found by XREFs on RatchetEncrypt
class Ratchet:
    def RatchetEncrypt(self, plaintext, AD):
        self.CKs, mk = KDF_CK(self.CKs)
        header = HEADER(self.DHs, self.PN, self.Ns)
        self.Ns += 1 # Number of Sended messages
        return header, ENCRYPT(mk, plaintext, CONCAT(AD, header))

# client.send -> server.store_message
# client.send(msg) -> RatchetEncrypt(msg) which uses header

On this moment we have pseudocode of send_msg function:

self.RATCHET_dict = {}
# doing some things with RATCHET_dict
def send_msg(msg,from_m, to_m):
    head, cipher = self.RATCHET_dict[m_to].RatchetEncrypt(msg)
    return {"header": header_to_string(head), "msg": cipher, ...}

Lets check header_to_string realization:

def header_to_string(header):
    print([header.dh, header.pn, header.n])
    return ';'.join([str(header.dh[0]), str(header.dh[1]), str(header.pn), str(header.n)])

def HEADER(dh_pair, pn, n):
    a = Header()
    a.dh = dh_pair[1]
    a.pn = pn
    a.n = n
    return a

class Header(object):
    pass

Lets look at header’s format 376876138...04158;666457945261308...71871794;0;2 By playing with code we can see that last two parameters are count of received and sent messages. First two are more interesting. As we saw

class Ratchet:
    def RatchetEncrypt(self, plaintext, AD):
        self.CKs, mk = KDF_CK(self.CKs)
        header = HEADER(self.DHs, self.PN, self.Ns)
        self.Ns += 1
        return header, ENCRYPT(mk, plaintext, CONCAT(AD, header))

This means header_to_string format looks like "self.DHs[0];self.DHs[1];to_m_count;from_m_count". I found two places of self.DHs generation:

in _DHRatchet which used in RatchetDecrypt necessary for pulling messages (we’ll come back to that later.)

class Ratchet:
    def _DHRatchet(self, header):
        self.PN = self.Ns                          
        self.Ns = 0
        self.Nr = 0
        self.DHr = header.dh
        self.RK, self.CKr = KDF_RK(self.RK, DH(self.DHs, self.DHr))
        self.DHs = GENERATE_DH()
        self.RK, self.CKs = KDF_RK(self.RK, DH(self.DHs, self.DHr))

in start_x3dh which used in first client.send call (actually self.DHs modifying in receive_x3dh but it also uses GENERATE_DH algo)

class Client:
    def start_x3dh(self, m_to):
        ...
        DHs_A=GENERATE_DH()
        RK_A, CKs_A = KDF_RK(SK, DH(DHs_A, PK_B))
        self.RATCHET_dict[m_to] = Ratchet(DHs=DHs_A, DHr=PK_B, RK=RK_A, CKs=CKs_A)

    def send(self, m_to, msg, send=True):
        if m_to not in self.RATCHET_dict.keys():
           self.start_x3dh(m_to)
        ...

Look at GENERATE_DH function:

def GENERATE_DH():
    prv_key = gost3410.prv_unmarshal(generate_bytes(64))
    pub_key = gost3410.public_key(CURVE, prv_key)
    return (prv_key, pub_key)

Omg, it uses generate_bytes, which uses random.randbytes. This is why we got same header with fixed seed.

Let’s hook generate_bytes

start_time = 1337 #int(time.time())
random.seed(start_time)
size=64
MSG_NUM = 1

def generate_bytes(n=size):
    global MSG_NUM
    rand = random.randbytes(n)
    print('MSG_NUM CALLED', MSG_NUM)
    print('GENERATED rand', debug_print_dh(rand))
    MSG_NUM+=1
    return rand

def debug_print_dh(rand):
    prv_key = gost3410.prv_unmarshal(rand)
    pub_key = gost3410.public_key(CURVE, prv_key)
    return pub_key[0]

yeah, that’s correct. At this moment we know that all parameters generated with random module and we know algo which used for that.

Second attempt to recover random seed (Success)

From task description we know He knows that it was 8th message between clients and they had started chat about 1 min before intercepted message. Ok, Date: Sun, 16 Jul 2023 21:53:34 GMT -> unix timestamp 1689544414. Lets bruteforce time and compare our GENERATE_DH() results with original header:

from pygost import gost3410
import random

search = "10007557092155308918620703319005578742802155531542215927047486636897385017421026687658302411228112816312151375158019561914808361055666669789420151300043193"
start_time = 1689544414  # int(time.time())
random.seed(start_time)
CURVE = gost3410.CURVES["id-tc26-gost-3410-2012-512-paramSetA"]

def generate_bytes(n=64):
    return random.randbytes(n)

def GENERATE_DH():
    prv_key = gost3410.prv_unmarshal(generate_bytes(64))
    pub_key = gost3410.public_key(CURVE, prv_key)
    return (prv_key, pub_key)

for j in range(200):
    t = start_time - j
    print(j)
    random.seed(t)
    arr = [str((GENERATE_DH()[1])[0]) for i in range(20)] # pub_key[0]
    if search in arr:
        print("SEED RECOVERED", t)
        print("MSG_NUM CALLED", arr.index(search)+1) # because MSG_NUM beggining from 1
        break

and we see

64
65
66
SEED RECOVERED 1689544348
MSG_NUM CALLED 10

then we have this GENERATE_DH, in which we need

[
 '9264589598917214570356576028637286965316409427254818227493078254039255165721359928330096074586822045454591272668453788514652534124577717080803397323837753',
 '5882838151079707917212895213006119673676890363161552333914448586032078639206645580866944258673556248686928883063120090222874182146824264129454879986035719',
 '6356725936561061752235179817746125611162703105753208009200752643649999618267446822075106985582287873377398980657379412925058956059861218407756501430626927',
 '2887626599271120182764806265394113921448284156247717458149074760790256212900772489341554363321357077449592555181818332405145513141515880148664404651010552',
 '2216900006373410088238948423035178444110439136989098412941526318911086854342633422828594482332725423331627448229960406207026042091000046928246514259533395',
 '2065978910820990851915215841599391978415392480535782437522299103928746742945880018832732484334365811051266269087678987390370004457623474476295627178062519',
 '12580783417477889603032614422211297881357618632629370530972814208266292685499754494342954304811493970406677227245281245667848862501108323925026691208119146',
 '11118815991327334922664302532246147692704095619978833554028959589828597949540394350413685937115099333628326943518745314022450906666032282699751140012678971',
 '649690232490058282951690312227812912664432393914555704120385988873130546340547752604856744054079240351159264632950984887792529728373140985426012556105651',
# original header:
 '10007557092155308918620703319005578742802155531542215927047486636897385017421026687658302411228112816312151375158019561914808361055666669789420151300043193'
]

Repeat traffic

Since we know all encryption keys, it will be easiest just repeat the same actions that the clients performed and decrypt the 8th message.

Let’s patch encryption function by adding flag decryption:

def RatchetEncrypt(self, plaintext, AD):
    self.CKs, mk = KDF_CK(self.CKs)
    header = HEADER(self.DHs, self.PN, self.Ns)
    self.Ns += 1
    enc = ENCRYPT(mk, plaintext, CONCAT(AD, header))

    decrypted_text = DECRYPT(mk, enc, CONCAT(AD, header))
    # print('MK = ', mk)
    print('decrypted: ', decrypted_text)
    ff = unhexlify('b3f3ca9e16fc1c33c86bb08e9ecee860462cdd6716dd2c32a6701b978c76035ec2973e2c6eac490d54f7918a0167179037459cbda47e4abcd5028a405d8374ada62fd23e3fcb29ab1e36e44ef7cfa438')
    print('FLAG', DECRYPT(mk, ff, CONCAT(AD, header))) # try to decrypt encrypted flag
    
    return header, enc

But if we run client.py with correct seed, we can see this is not original header

But why this header is not original? Why can’t we make some more calls GENERATE_DH and then get correct header? The reason for this is that when sending multiple messages, the header is fixed after the first one.

At this time we need to remember that we did not used pull messages option yet.

When i tried use this option During CTF in most cases it failed

I thought we need to send msg from B at the end. For this reason we can only connect, send msg from A, pull messages from A. But in sum it gives 4+2+1=7, not 9.

I removed unpad function and it works well this time. But i can’t understand why author left bug in the source code, and hence i thought that we should not use this function.

Get back to the task. As we remember we have to_m_count and from_m_count fields in header.

By playing with client we can see that in original header to_m_count=2 (A->B) and from_m_count=1 or 0 (B->A). But as we’ll see later, this was another bug lol.

Time to play with client.py again (here we go again). I guessed that if we send 2 1 3 (send msg + change client + pull msg) two times, then we can generate new header for client

Why it works? As we saw before, self.DHs changes here, and it is used when constructing the header

    def RatchetDecrypt(self, header, ciphertext, AD):
        plaintext = self._TrySkippedMessageKeys(header, ciphertext, AD)
        if plaintext != None:
            return plaintext
        if header.dh != self.DHr:                 
            self._SkipMessageKeys(header.pn)
            self._DHRatchet(header)
        self._SkipMessageKeys(header.n)             
        self.CKr, mk = KDF_CK(self.CKr)
        self.Nr += 1
        return DECRYPT(mk, ciphertext, CONCAT(AD, header))
    
    def _DHRatchet(self, header):
        self.PN = self.Ns                          
        self.Ns = 0
        self.Nr = 0
        self.DHr = header.dh
        self.RK, self.CKr = KDF_RK(self.RK, DH(self.DHs, self.DHr))
        print('HERE WE GO')
        self.DHs = GENERATE_DH()
        self.RK, self.CKs = KDF_RK(self.RK, DH(self.DHs, self.DHr))

if we run we can see HERE WE GO when we pull messages.

Final payload: 213 213 213 213 2.

Epilogue

Task author told me that it was really Signal specification:

-btw, did it really use the Signal specification?

-Yeah you can look at it here. It was interesting to write it from scratch.))

https://signal.org/docs/

The first attempt to recover random seed (Fail)

On this step i lost more than 6 hours. Since pull messages options was broken, I thought to use only send msg. And since only 8 messages are needed, it was easier to bruteforce all the combinations of sending them A->B or B->A (it need only 2^8 runs, but one run is ~5 seconds) and then we would get the right one. Of course it didn’t work

You can see this shit here

Last modified on 2023-08-17