zakigeyanzakigeyan

TJCTF 2023 - Crypto

  • May 28, 2023

In this post, I will write my solutions to the following 3 crypto challenges:

  1. keysmith
  2. aluminum-isopropoxide
  3. drm-1

keysmith (128 points, 30 solves)

We are given a service nc tjc.tf 31103 and 2 attachment files msg.txt and server.py. Let’s take a look at server.py source code.

#!/usr/local/bin/python3.10 -u
from Crypto.Util.number import getPrime
flag = open("flag.txt", "r").read()

po = getPrime(512)
qo = getPrime(512)
no = po * qo
eo = 65537

msg = 762408622718930247757588326597223097891551978575999925580833
s = pow(msg,eo,no)

print(msg,"\n",s)

try:
    p = int(input("P:"))
    q = int(input("Q:"))
    e = int(input("E:"))
except:
    print("Sorry! That's incorrect!")
    exit(0)

n = p * q
d = pow(e, -1, (p-1)*(q-1))
enc = pow(msg, e, n)
dec = pow(s, d, n)
if enc == s and dec == msg:
    print(flag)
else:
    print("Not my keys :(")

The service asks for 3 integers $ p $, $ q $, and $ e $ from user input, then will check if $ m^e = s \pmod n $ and $ s^d = m \pmod n $. If both conditions satisfy, then the service will give us the flag.

Solution

The $ m $ here is a constant integer, so every time we connect to the service, $ m $ will always be the same. But, $ s $ will always change because the two primes used will be regenerated every time we connect to the service, which of course causes the modulus $ n $ to change as well. In 2 checks above, we can control both the prime and public exponents used to encrypt $ m $. We could have assigned non-prime numbers to $ p $ and $ q $, but because of the calculation $ d = e^{-1} \pmod{(p-1)(q-1)} $ and the check $ m^{e d} = m \pmod n $, then we have to insert prime integers $ p $ and $ q $ to satisfy the condition.

Because we can also control the public exponent $ e $ here, the thing that came to my mind was the Discrete Log Problem. The idea is that we have to find $ e $ that satisfies $ m^e = s \pmod n $ where $ m $, $ n $, and $ s $ are known. The $ e $ can be calculated using the discrete log $ s $ base $ m $ in $ \mathbb{Z}/n\mathbb{Z} $. The problem is, the integer $ n $ must be greater than $ s $ (must be ≥ 1024-bit), so of course finding the discrete log in this case sounds impossible to do in a very limited time and resource. The good thing is, since we can control $ n $ ($ p $ and $ q $), then we can choose weak primes $ p $ and $ q $ so that the discrete log calculation in $ \mathbb{Z} /n\mathbb{Z} $ becomes possible. We can choose smooth prime for $ p $ and $ q $, then calculate the discrete log $ s $ base $ m $ in $ \mathbb{F}_p $ and $ \mathbb{F}_q $, finally combine both results using Chinese Remainder Theorem algorithm.

Implementation

from deom import *
import math

def gen_smooth_prime():
    while 1:
        arr = [getPrime(32) for _ in range(17)]
        p = math.prod(arr) * 2 + 1
        if isPrime(p):
            return arr, int(p)


# _, p = gen_smooth_prime()
# _, q = gen_smooth_prime()
p = 280366744730270375197084239866659515425537864261978492493879940524515933944843895935256245743408781545457487177381729051907185655213072767827690139117717509663259
q = 565241237098819030851349822040714002257356739352788887054962581065286370254261944451408281009287595519953201012450206538540410484761840989491756815520165517661047
n = p * q

assert int(p).bit_length() > 512
assert int(q).bit_length() > 512
assert int(n).bit_length() > 1024

print(f"{p = }")
print(f"{q = }")
print(f"{n = }")
print()

m = 762408622718930247757588326597223097891551978575999925580833

while 1:
    # io = process("python3 server.py".split(), level="warn")
    io = remote("tjc.tf", 31103, level="warn")

    io.recvuntil(b"\n ")
    s = int(io.recvline(0).decode())
    print(f"{s = }")

    try:
        F = GF(p); sol_p = int(F(s).log(F(m))); print(f"{sol_p = }")
        F = GF(q); sol_q = int(F(s).log(F(m))); print(f"{sol_q = }")
        e = int(crt([sol_p, sol_q], [p - 1, q - 1])); print(f"{e = }")
        assert pow(m, e, n) == s

        io.sendlineafter(b"P:", str(p).encode())
        io.sendlineafter(b"Q:", str(q).encode())
        io.sendlineafter(b"E:", str(e).encode())

        print(io.recvline(0))
        io.close()
        break

    except Exception as e:
        print(f"Exception: {e}\n")
        io.close()

$ sage solve.sage
p = 280366744730270375197084239866659515425537864261978492493879940524515933944843895935256245743408781545457487177381729051907185655213072767827690139117717509663259
q = 565241237098819030851349822040714002257356739352788887054962581065286370254261944451408281009287595519953201012450206538540410484761840989491756815520165517661047
n = 158474845632706828218047122882397237182609097732939314657156826349198220490564323654289899420987820161567820461587548083531620439110659701728756364173575299996605575689343896056117350566096866890284582044541418869311174130495126722019189750565471730985767947292127870566182987335888437068613488229047504027376420250271372173

...

s = 19426321752621795191719090530804223401063348110228736070992633430537042042847976910171213446615606287040164622783389557770516410108736618361260032970617339395726305166186421646893215980952681377727200949513917381730459324603535165714389107024482254155489825152997612947148218066711436977431775698854502264797
sol_p = 224847797122422352408083055419845058043528624404381518675606293976167080454241498274229489910295075992467243576127848870879030790592063885680952312156074157301401
sol_q = 87046266658803775012408401803031147702300133795373049334016438602627755073588192299960958516003330439271176306394327234027391610157463852654341625758883253947319
e = 11935274781408693469628707663076753730704069650270441509561955374698133893233286701929806669692620063625798853853175687335063529829065150103174091483876538177232778798193006148491519172053715113707869938621006076591182849387141144628473630834111983802434774543038352156740613498366327420046095356121736752399690958167553877
b'tjctf{lock-smith_289378972359}'

Flag

tjctf{lock-smith_289378972359}

aluminum-isopropoxide (168 points, 22 solves)

We are given 4 attachments flag1.txt.enc, flag2.txt.enc, flag.txt.enc, and main.cpp. Let’s take a look at main.cpp code.

#include <iostream>
#include <cinttypes>
#include <string>
#include <filesystem>
#include <fstream>
#include <sys/stat.h>
#include <vector>
#include <cstring>
using namespace std;
using namespace std::filesystem;

typedef uint8_t Byte;

void make_key(Byte *S, const std::string &key)
{
  for (int i = 0; i < 255; i++)
    S[i] = i;

  Byte j = 0;
  for (int i = 0; i < 255; i++)
  {
    j = (j ^ S[i] ^ key[i % key.length()]) % 256;
    std::swap(S[i], S[j]);
  }
}

Byte S_box[256] = {24, 250, 101, 19, 98, 246, 141, 58, 129, 74, 227, 160, 55, 167, 62, 57, 237, 156, 32, 46, 90, 67, 22, 3, 149, 212, 36, 210, 27, 99, 168, 109, 125, 52, 173, 184, 214, 86, 112, 70, 5, 252, 6, 170, 30, 251, 103, 43, 244, 213, 211, 198, 16, 242, 65, 118, 68, 233, 148, 18, 61, 17, 48, 80, 187, 206, 72, 171, 234, 140, 116, 35, 107, 130, 113, 199, 51, 114, 232, 134, 215, 197, 31, 150, 247, 79, 26, 110, 142, 29, 9, 117, 248, 186, 105, 120, 15, 179, 207, 128, 10, 254, 83, 222, 178, 123, 100, 39, 228, 84, 93, 97, 60, 94, 180, 146, 185, 38, 203, 235, 249, 89, 226, 1, 106, 12, 216, 221, 8, 45, 13, 2, 14, 75, 49, 33, 127, 163, 111, 85, 255, 253, 166, 151, 40, 23, 194, 34, 139, 95, 145, 193, 159, 133, 69, 245, 196, 102, 91, 11, 157, 96, 47, 152, 154, 59, 181, 28, 126, 200, 158, 88, 224, 231, 41, 190, 240, 191, 188, 143, 164, 189, 217, 54, 66, 241, 209, 104, 78, 87, 82, 230, 182, 220, 53, 147, 21, 136, 76, 0, 115, 169, 71, 44, 223, 175, 92, 25, 177, 64, 201, 77, 138, 144, 204, 229, 81, 20, 183, 205, 124, 243, 4, 172, 174, 108, 132, 176, 135, 161, 162, 7, 236, 195, 238, 56, 42, 131, 218, 155, 121, 153, 239, 50, 219, 225, 37, 202, 63, 137, 192, 208, 119, 122, 165, 73};

void enc(Byte *S, Byte *out, int amount)
{
  Byte i = 0;
  Byte j = 0;
  int ctr = 0;
  while (ctr < amount)
  {
    i = (i * j) % 256;
    j = (i + S[j]) % 256;
    // std::swap(S[i],S[j]);
    Byte K = (S[i] & S[j]);
    out[ctr] ^= S_box[K];
    ctr++;
  }
}

Byte key[256];
int main()
{

  std::string path = current_path();

  std::vector<std::string> files;
  for (const auto &file : directory_iterator(path))
    files.push_back(std::string(file.path()));

  for (const auto &file : files)
  {
    std::cout << file << "\n";
    struct stat results;
    std::ifstream in(file);
    std::ofstream out(file + ".enc", std::ofstream::binary);
    if (stat(file.c_str(), &results) == 0)
    {
      uint8_t *buffer = new uint8_t[results.st_size];
      in.read((char *)buffer, results.st_size);

      make_key(key, std::to_string(rand()));
      enc(key, buffer, results.st_size);

      out.write((char *)buffer, results.st_size);
      delete[] buffer;
    }
    in.close();
    out.close();
  }

  return 0;
}

Solution

As its name, the make_key function will produce a key which is a random element from the array S = {0, 1, 2, …, 253, 254, 255}. This key will later be used by the enc function to encrypt the message in the following code:

Byte K = (S[i] & S[j]);
out[ctr] ^= S_box[K];

At first glance, the make_key and enc functions look like modified RC4 ciphers. After analyzing the code, it can be concluded that:

  • The i in enc function will always be zero, so the S[i] used will always be the same
  • Message bytes are getting xored using S_box[K], where K comes from S[i] & S[j]
  • Since S[i] is always the same, the probability of the same K appearing repeatedly is relatively high
  • The probability of K being small is also relatively high because K is obtained from the & operation

The chall description says that the files flag1.txt.enc, flag2.txt.enc, flag.txt.enc are from 3 different filenames, but the contents are identical. The contents of the file are of course printable chars, so we can bruteforce all possible bytes by comparing them with the first n-elements of S_box.

from deom import *

S_box = [24, 250, 101, 19, 98, 246, 141, 58, 129, 74, 227, 160, 55, 167, 62, 57, 237, 156, 32, 46, 90, 67, 22, 3, 149, 212, 36, 210, 27, 99, 168, 109, 125, 52, 173, 184, 214, 86, 112, 70, 5, 252, 6, 170, 30, 251, 103, 43, 244, 213, 211, 198, 16, 242, 65, 118, 68, 233, 148, 18, 61, 17, 48, 80, 187, 206, 72, 171, 234, 140, 116, 35, 107, 130, 113, 199, 51, 114, 232, 134, 215, 197, 31, 150, 247, 79, 26, 110, 142, 29, 9, 117, 248, 186, 105, 120, 15, 179, 207, 128, 10, 254, 83, 222, 178, 123, 100, 39, 228, 84, 93, 97, 60, 94, 180, 146, 185, 38, 203, 235, 249, 89, 226, 1, 106, 12, 216, 221, 8, 45, 13, 2, 14, 75, 49, 33, 127, 163, 111, 85, 255, 253, 166, 151, 40, 23, 194, 34, 139, 95, 145, 193, 159, 133, 69, 245, 196, 102, 91, 11, 157, 96, 47, 152, 154, 59, 181, 28, 126, 200, 158, 88, 224, 231, 41, 190, 240, 191, 188, 143, 164, 189, 217, 54, 66, 241, 209, 104, 78, 87, 82, 230, 182, 220, 53, 147, 21, 136, 76, 0, 115, 169, 71, 44, 223, 175, 92, 25, 177, 64, 201, 77, 138, 144, 204, 229, 81, 20, 183, 205, 124, 243, 4, 172, 174, 108, 132, 176, 135, 161, 162, 7, 236, 195, 238, 56, 42, 131, 218, 155, 121, 153, 239, 50, 219, 225, 37, 202, 63, 137, 192, 208, 119, 122, 165, 73]

f0 = open("flag.txt.enc", "rb").read()
f1 = open("flag1.txt.enc", "rb").read()
f2 = open("flag2.txt.enc", "rb").read()

chars = string.ascii_letters + string.digits + '}_{-'

################################################################

for x, y in zip(f0, b'tjctf{'):
    print(S_box.index(x ^ y), end=" ")
print()

print('#'*64)

for x, y in zip(f1, b'tjctf{'):
    print(S_box.index(x ^ y), end=" ")
print()

print('#'*64)

for x, y in zip(f2, b'tjctf{'):
    print(S_box.index(x ^ y), end=" ")
print()


$ python3 test.py
0 1 18 16 23 4 
################################################################
1 5 4 4 5 5 
################################################################
56 56 32 32 24 16

From the results above, we can assume that:

  • The K value when encrypting the flag.txt is always less than 32
  • The K value when encrypting the flag1.txt is always less than 16
  • The K value when encrypting the flag2.txt is always less than 64

Implementation

from deom import *

S_box = [24, 250, 101, 19, 98, 246, 141, 58, 129, 74, 227, 160, 55, 167, 62, 57, 237, 156, 32, 46, 90, 67, 22, 3, 149, 212, 36, 210, 27, 99, 168, 109, 125, 52, 173, 184, 214, 86, 112, 70, 5, 252, 6, 170, 30, 251, 103, 43, 244, 213, 211, 198, 16, 242, 65, 118, 68, 233, 148, 18, 61, 17, 48, 80, 187, 206, 72, 171, 234, 140, 116, 35, 107, 130, 113, 199, 51, 114, 232, 134, 215, 197, 31, 150, 247, 79, 26, 110, 142, 29, 9, 117, 248, 186, 105, 120, 15, 179, 207, 128, 10, 254, 83, 222, 178, 123, 100, 39, 228, 84, 93, 97, 60, 94, 180, 146, 185, 38, 203, 235, 249, 89, 226, 1, 106, 12, 216, 221, 8, 45, 13, 2, 14, 75, 49, 33, 127, 163, 111, 85, 255, 253, 166, 151, 40, 23, 194, 34, 139, 95, 145, 193, 159, 133, 69, 245, 196, 102, 91, 11, 157, 96, 47, 152, 154, 59, 181, 28, 126, 200, 158, 88, 224, 231, 41, 190, 240, 191, 188, 143, 164, 189, 217, 54, 66, 241, 209, 104, 78, 87, 82, 230, 182, 220, 53, 147, 21, 136, 76, 0, 115, 169, 71, 44, 223, 175, 92, 25, 177, 64, 201, 77, 138, 144, 204, 229, 81, 20, 183, 205, 124, 243, 4, 172, 174, 108, 132, 176, 135, 161, 162, 7, 236, 195, 238, 56, 42, 131, 218, 155, 121, 153, 239, 50, 219, 225, 37, 202, 63, 137, 192, 208, 119, 122, 165, 73]

f0 = open("flag.txt.enc", "rb").read()
f1 = open("flag1.txt.enc", "rb").read()
f2 = open("flag2.txt.enc", "rb").read()

chars = string.ascii_letters + string.digits + '}_{-'

for idx in range(len(f0)):
    print(idx, end=" ")
    poss = []
    for ch in chars:
        if f0[idx] ^ ord(ch) in S_box[:32] \
        and f1[idx] ^ ord(ch) in S_box[:16] \
        and f1[idx] ^ ord(ch) in S_box[:64]:
            poss.append(ch)
    print(poss)

$ python3 solve.py
0 ['t']
1 ['f', 'j']
2 ['c']
3 ['t']
4 ['f', 's']
5 ['{']
6 ['f']
7 ['l']
8 ['a']
9 ['g']
10 ['_']
11 ['u']
12 ['n']
13 ['d']
14 ['e', 'i']
15 ['r']
16 ['_']
17 ['m']
18 ['o']
19 ['u']
20 ['n']
21 ['s', 't']
22 ['a']
23 ['i', 'p']
24 ['n']
25 ['p', 'y', 'T', '}', '_']
26 ['o']
27 ['f']
28 ['S', '_']
29 ['d', 'E', 'K']
30 ['u']
31 ['s']
32 ['t', 'U']
33 ['}']

Combine these chars to form a complete flag. In some indexes, there is more than one possible flag character, but this is quite easy to handle by ensuring that the words formed by the flag are words that ‘make sense’ and an English word.

Flag

tjctf{flag_under_mountain_of_dust}

drm-1 (216 points, 16 solves)

We are given a web service drm.tjc.tf and 2 attachments app.py and client.zip. Let’s take a look at app.py code.

from flask import Flask
import time
from Crypto.Hash import SHA256

app = Flask(__name__)

hash_key = open("hash_key", "rb").read()[:32]
flag = open("flag.txt", "r").read().strip()


@app.route('/buy/<user>')
def buy(user):
    return "No"


@app.route('/song/<user>')
def song(user):
    return open("user/"+user+".drmsong", "rb").read().hex()


@app.route('/unlock/<meta>/<hmac>')
def unlock(meta, hmac):
    meta = bytes.fromhex(meta)

    user = None
    t = None
    for word in meta.split(b","):
        if b"user" in word:
            user = str(word[word.index(b":")+1:])[2:-1]
        if b"made" in word:
            t = float(str(word[word.index(b":")+1:])[2:-1])

    h = SHA256.new()
    h.update(hash_key)
    h.update(meta)
    if h.hexdigest() == hmac:
        if time.time() - t < 1000:
            drm_key = open("user/"+user+".drmkey", "rb").read().hex()
            drm_n = open("user/"+user+".drmnonce", "rb").read().hex()
            return drm_key + " " + drm_n + " " + flag
        else:
            return "Expired :(... pay us again"
    else:
        return "Bad Hash"


if __name__ == '__main__':
    app.run()

Extract client.zip file. There are 4 extracted files: drm_exe, drm.pyc, hash.dat, and meta.dat.

$ tree
.
├── app.py
├── client
│   ├── drm_exe
│   ├── drm.pyc
│   ├── hash.dat
│   └── meta.dat
└── client.zip

Solution

To make sure there was no information missing, I first tried to decompile the drm.pyc file first using uncompyle6.

# uncompyle6 version 3.7.4
# Python bytecode 3.8 (3413)
# Decompiled from: Python 3.8.10 (default, Mar 13 2023, 10:26:41) 
# [GCC 9.4.0]
# Embedded file name: src/drm.py
# Compiled at: 2023-05-26 20:25:01
# Size of source mod 2**32: 722 bytes
import requests, sys
if len(sys.argv) != 2:
    print('Usage: drm.pyc <url>')
    exit(1)
else:
    meta = open('meta.dat', 'r').read().strip()
    hash = open('hash.dat', 'r').read().strip()
    url = sys.argv[1]
    get_data_url = f"{url}/unlock/{meta}/{hash}"
    get_song_url = f"{url}/song/daniel-kpdfgo"
    recved = requests.get(get_data_url).text.split(' ')
    song = requests.get(get_song_url).text
    if len(recved) == 1:
        print(recved[0])
    else:
        if len(recved) != 2:
            print(' '.join(recved))
        else:
            key = bytes.fromhex(recved[0])
            nonce = bytes.fromhex(recved[1])
            open('drm.key', 'wb+').write(key)
            open('drm.nonce', 'wb+').write(nonce)
            open('enc_song.dat', 'wb+').write(bytes.fromhex(song))
            print('successful')
# okay decompiling drm.pyc

Here we can see that the user name used is daniel-kpdfgo with the meta and hash taken from the meta.dat and hash.dat files. Back to the main code, we can see how meta and hash are used in the unlock function. Let’s look at the meta payload contained in meta.dat by converting it to bytes.

In [1]: meta = '6d6164653a302c757365723a64616e69656c2d6b706466676f'                                                   

In [2]: bytes.fromhex(meta)                                                                                           
Out[2]: b'made:0,user:daniel-kpdfgo'

The goal is that we must be able to change the value made:0 to made:t where t is the epoch time that satisfies the condition time.time() - t < 1000. We can’t just change it because there is a SHA256 check of the payload that we send with an unknown prefix. The prefix information that we know is only the length of the prefix, which consists of 32 bytes. When we change the payload that is sent, we cannot simply regenerate the SHA256 because the prefix is unknown. This is where the Hash Length Extension attack plays its role. This time I used hash_extender. The idea is, we will add the suffix ,user:daniel-kpdfgo,made:1685193037 to the meta payload so that the final payload will look like this:

made:0,user:daniel-kpdfgo????????????????????????????????,user:daniel-kpdfgo,made:1685193037

where the ? characters above are the characters that will be generated by hash_extender. Thus, the parts made:0 and user:daniel-kpdfgo????... will be replaced by suffixes because there is no check whether the variables user and t are set more than once in the following code below:

for word in meta.split(b","):
    if b"user" in word:
        user = str(word[word.index(b":")+1:])[2:-1]
    if b"made" in word:
        t = float(str(word[word.index(b":")+1:])[2:-1])

Implementation

import hashlib, os, re, requests, time

meta_dat = open("client/meta.dat").read().strip()
hash_dat = open("client/hash.dat").read().strip()

data = bytes.fromhex(meta_dat).decode()
secret = 32
append = f",user:daniel-kpdfgo,made:{int(time.time())}"

cmd = f"~/Repos/hash_extender/hash_extender --data \"{data}\" --secret {secret} --append \"{append}\" --signature {hash_dat} --format sha256"
print(cmd)

hle_result = os.popen(cmd).read()

new_sign = re.findall(r"New signature: (\w+)\n", hle_result)[0]
new_data = re.findall(r"New string: (\w+)\n", hle_result)[0]
print(new_sign)
print(new_data)

url = f"https://drm.tjc.tf/unlock/{new_data}/{new_sign}"
resp = requests.get(url).text
print(resp)

$ python3 solve.py 
~/Repos/hash_extender/hash_extender --data "made:0,user:daniel-kpdfgo" --secret 32 --append ",user:daniel-kpdfgo,made:1685193037" --signature da1e3623a12b16e0a36c3d966c6d560f81e988ecf9040f99f1ac717ae444d417 --format sha256
bac6c375bd5a00be3091585195af7c9dab0f37b734571eaf0321b98d99e361f7
6d6164653a302c757365723a64616e69656c2d6b706466676f80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001c82c757365723a64616e69656c2d6b706466676f2c6d6164653a31363835313933303337
7031722c0feeb22a568fe3ea49f6a9e43978b9a0cfad3ce074c0a1562ced0b53 8bf202be03aca01e tjctf{wh0_n33ds_sp0t1fy_a7dfd3e5}

Flag

tjctf{wh0_n33ds_sp0t1fy_a7dfd3e5}