This post contains my solutions to 3 crypto challs:
- keysmith
- aluminum-isopropoxide
- drm-1
keysmith (128 points, 30 solves)
We get a service at nc tjc.tf 31103 and two files: msg.txt and server.py. Let’s look at server.py:
#!/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 numbers: $ p $, $ q $, and $ e $. It checks if $ m^e = s \pmod n $ and $ s^d = m \pmod n $. If both are true, then we get the flag.
Solution
The message $ m $ is always the same, but $ s $ changes each time because new primes are generated. We can control both the primes and public exponent. We need to use prime numbers for $ p $ and $ q $ because of the calculation $ d = e^{-1} \pmod{(p-1)(q-1)} $ and the check $ m^{e d} = m \pmod n $.
Since we control $ e $, we can use the Discrete Log Problem. We need to find $ e $ where $ m^e = s \pmod n $. We can calculate $ e $ using discrete log of $ s $ base $ m $ in $ \mathbb{Z}/n\mathbb{Z} $. The problem is that $ n $ must be at least 1024 bits, making discrete log calculation too slow. However, we can choose weak primes $ p $ and $ q $ to make the calculation possible. We can use smooth primes for $ p $ and $ q $, then find the discrete log in $ \mathbb{F}_p $ and $ \mathbb{F}_q $, and combine the results using the Chinese Remainder Theorem.
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 get 4 files: flag1.txt.enc, flag2.txt.enc, flag.txt.enc, and main.cpp. Let’s look at main.cpp:
#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
The make_key function creates a key from the array S = {0, 1, 2, …, 255}. This key is used by the enc function to encrypt messages:
Byte K = (S[i] & S[j]);
out[ctr] ^= S_box[K];
The code looks like a modified RC4 cipher. After analysis:
iin theencfunction is always zero, soS[i]is constant- Message bytes are xored with
S_box[K], whereKcomes fromS[i] & S[j] - Since
S[i]is constant, the sameKvalue appears often Kis likely to be small because it comes from an&operation
The chall says that flag1.txt.enc, flag2.txt.enc, and flag.txt.enc have different filenames but identical content. Since the content is printable text, 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
Kvalue when encrypting theflag.txtis always less than 32 - The
Kvalue when encrypting theflag1.txtis always less than 16 - The
Kvalue when encrypting theflag2.txtis 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 char, 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 get a web service at drm.tjc.tf and 2 files: app.py and client.zip. Let’s look at app.py:
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()
After extracting client.zip, we get 4 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
First, I decompiled drm.pyc using uncompyle6 to check for any missing information:
# 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
The code shows that it uses the username daniel-kpdfgo and gets meta and hash from meta.dat and hash.dat. Looking at the unlock function, we need to check how meta and hash are used. Let’s convert the meta payload from meta.dat to bytes:
In [1]: meta = '6d6164653a302c757365723a64616e69656c2d6b706466676f'
In [2]: bytes.fromhex(meta)
Out[2]: b'made:0,user:daniel-kpdfgo'
We need to change made:0 to made:t where t is a timestamp that satisfies time.time() - t < 1000. We can’t just change it because there’s a SHA256 check with an unknown 32-byte prefix. When we change the payload, we can’t regenerate the SHA256 because we don’t know the prefix. This is where the Hash Length Extension attack comes in. I used hash_extender for this. The plan is to add the suffix ,user:daniel-kpdfgo,made:1685193037 to the meta payload, making it look like:
made:0,user:daniel-kpdfgo????????????????????????????????,user:daniel-kpdfgo,made:1685193037
where the ? chars will be generated by hash_extender. The parts made:0 and user:daniel-kpdfgo?????... will be ignored because the code doesn’t check if user and t are set multiple times:
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}