Crypto CTF 2020
I was ranked 19th in Crypto CTF 2020.
Generally, problems are fun. I solved Abbot, Amsterdam, gambler, madhat, model, one_line_crypto, three_ravens, Trailing_Bits.
Break the hash
First, many problems had to break the hash earlier, so I was coding in C++ for breaking the hash. Because 3 byte brute-forcing takes time too long in Python.
//g++ -o solve solve.cpp -lcrypto
#include <openssl/sha.h>
#include <sstream>
#include <string>
#include <iomanip>
#include <iostream>
#include <random>
#include <ctime>
using namespace std;
string sha256(const string str)
{
unsigned char hash[SHA256_DIGEST_LENGTH];
SHA256_CTX sha256;
SHA256_Init(&sha256);
SHA256_Update(&sha256, str.c_str(), str.size());
SHA256_Final(hash, &sha256);
stringstream ss;
for(int i = SHA256_DIGEST_LENGTH-3; i < SHA256_DIGEST_LENGTH; i++)
{
ss << hex << setw(2) << setfill('0') << (int)hash[i];
}
return ss.str();
}
void gen_random(char *s, const int len) {
static const char alphanum[] =
"0123456789"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
for (int i = 0; i < len; ++i) {
s[i] = alphanum[rand() % (sizeof(alphanum) - 1)];
}
s[len] = 0;
}
int main(int argc, char **argv){
const int len = atoi(argv[1]);
string value(argv[2]);
for (int i=0;i<0x1000000;i++){
char s[len] = { 0 };
gen_random(s, len);
string ss(s);
string a = sha256(ss);
if(a.compare(value) == 0){
cout << ss << endl;
break;
}
}
}
I’m terrible coder so I just consider sha256.
Abbot
It isn't the big troubles in life that require character. Anybody can rise to a crisis and face a crushing tragedy with courage, but to meet the petty hazards of the day with a laugh.
This problem gives abbot.py, output.txt.
Solution
Analyze encryption function, me, you, us. And make decryption function!
function me(msg)
If msg is “ABCDE”, return the value like,
\[\text{A}+\frac{1}{\text{B}+\frac{2}{\text{C}+\frac{3}{D+...}}}\]function you(msg)
If msg is “ABCDE”, return the value like,
\[\text{A}+\frac{1}{\text{B}-\frac{1}{\text{C}+\frac{1}{D-...}}}\]function us(msg)
If msg is “ABCDE”, return the value like,
\[\text{A}+\frac{1}{\text{B}+\frac{1}{\text{C}+\frac{1}{D+...}}}\]It’s easy to make decrypt function.
Here is my code.
#!/usr/bin/env python2
import string
from fractions import Fraction as frac
enc = [
(4874974328610108385835995981839358584964018454799387862, 72744608672130404216404640268150609115102538654479393),
(39640220997840521464725453281273913920171987264976009809, 366968282179507143583456804992018400453304099650742276),
(145338791483840102508854650881795321139259790204977, 1529712573230983998328149700664285268430918011078),
(84704403065477663839636886654846156888046890191627, 717773708720775877427974283328022404459326394028),
(287605888305597385307725138275886061497915866633976011, 8712550395581704680675139804565590824398265004367939)]
for i in range(len(enc)):
if i == 2 or i == 3:
a, b = enc[i][0], enc[i][1]
if a <= b:
continue
red = 1
flag = ""
flag += chr(a//b)
a, b = b, a - (a//b)*b
while b > 0:
flag += chr(a//b)
red += 1
a, b = b, (a - (a//b)*b)
if b % red == 0:
b //= red
else:
a *= red
print(flag)
for i in range(len(enc)):
if i == 1 or i == 4:
a, b = enc[i][0], enc[i][1]
red = 1
flag = ""
flag += chr(a//b)
a, b = b, a - (a//b)*b
while b > 0:
red *= -1
if red == -1:
flag += chr((a+b-1)//b)
a, b = b, ((a+b-1)//b)*b-a
else:
flag += chr(a//b)
a, b = b, a-(a//b)*b
print(flag)
for i in range(len(enc)):
if i != 0:
continue
a, b = enc[i][0], enc[i][1]
red = 1
flag = ""
flag += chr(a//b)
a, b = b, a - (a//b)*b
while b > 0:
flag += chr(a//b)
a, b = b, a-(a//b)*b
print(flag)
flag = [0 for i in range(5)]
flag[0] = "CCTF{This_13_n0t_Arthur_Who_"
flag[1] = "l0ves_Short_st0ries_This_IS_"
flag[2] = "__ASIS___Crypto_CTF____with_"
flag[3] = "very_m0d3rn_arthur_Enc0d1ng!"
flag[4] = "!_D0_you_Enj0y_IT_as_w311??~}"
print(''.join(x for x in flag))
Amsterdam
Is it normal to have such encoding?
This problem gives amsterdam.py, output.txt.
Solution
Recover m from c and recover msg from m. I don’t know k exactly so just brute-force with k.
Here is my code.
from Crypto.Util.number import *
from functools import reduce
import operator
def comb(n, k):
if k > n :
return 0
k = min(k, n - k)
u = reduce(operator.mul, range(n, n - k, -1), 1)
d = reduce(operator.mul, range(1, k + 1), 1)
return u // d
c = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493
x = []
while c > 0 :
x.append(c%3)
c //= 3
x = x[::-1]
m = 0
for c in x:
m *= 2
if c % 3 == 1:
m += 1
elif c % 3 == 2:
m -= 1
m = bin(m)[2:]
n = len(m)
for k in range(218):
flag = 0
for i in range(2, n+1):
if m[i-1] == '1':
flag += comb(n-i, k)
k -= 1
flag = long_to_bytes(flag)
if b'CCTF' in flag:
print(flag)
Gambler
Gamble as an ancient Philossepher!
nc 05.cr.yp.toc.tf 33371
This problem gives only ip and port. We should break the hash for getting the problem.
Encryption Function
def encrypt(m, p, a, b):
assert m < p and isPrime(p)
return (m ** 3 + a * m + b) % p
Also, I can give m to oracle and get output. It gives encryption of flag.
Solution
Solving modular univariate polynomials by LLL!! Actually, there is more simple solve but didn’t think about it.
We can know \(a\), \(b\), \(p\) by some output.
\(m=0\) : output is \(b\).
\(m=1\) : output is \(1+a+b\). so we can solve \(a\).
\(m=100\) : output is \(100^3+100a+b \mod{p}\).
I calculate \(100^3+100a+b\) and the difference between the two values is divided by p.
I use CRT(Chinese Remainder Theorem) for maxmize p for LLL.
\[f(x)=x^3+Ax+D\mod{N}\]When I use 4 values of p, I succeed to get the flag.
Here is my code.
from Crypto.Util.number import *
a=[8181936642004158599376291358611928788331876895778617966980826710095331252596777337497658819635030844867673900133794632276456263146562909413587444661218537, 6787533119351859432568311293136550274798419739118234163251614869712249806653530106458857217644112474858180330870316193235759181463247064337517050556570928, 9861490703705862391865965044840824634948162013170343290010975811146402401464461888250382849503438780147377997403915177423619271986813366720568649005518288,6786375245373034922597531781246389095300741453880754286026587767485911655529048285020803635641256057038020818398939360683187430842442095738160842216195987]
d=[5588670736355432971577484143148471636582582997568901522465215021144714599136528191869183220048624977117762678580370052666634830025536775332560080229098770, 5453747712747347887522679915927799297157933287387643476062511908880836058451798655790672661685527177333408626411892351536765685193807899533676308198262930, 5735270482337781025039897984977704443971476222703495396760650262783073486438558936532074003706296611508021027677556835110603899205979592003777675875271045,6932922795833406040946983304207392724039463928345051242621502068559121236611326128755966933760253224819512053924513436761117620745119662197044343474827145]
p=[8304673992130926311815246705471848811798171190105719129878540586301785729433428107198825042028125966101249966279102714550477480418251564770100559135033019, 8117923556023410910197034188149830550359022137649416784706070128432792316612381556724791896351867378696914460914355389456009007510391517775262760434610251, 11800577729344879689245485383195893316197963668378648861495239146822860820250144846245412875632559821016286086407171259214575186590015765822883264561783767,9546479433345742747666915364705666189289260017034246862185286084229553606803104523699495422853312792451518584437109618870881825705906566072523340740563607]
N = 1
for prime in p:
N *= prime
M = []
for i in range(len(p)):
M.append(N//p[i])
A, D = 0, 0
for i in range(len(p)):
A += a[i]*inverse(M[i], p[i])*M[i]
D += d[i]*inverse(M[i], p[i])*M[i]
P.<x> = PolynomialRing(ZZ)
f = x^3+A*x+D
delta = f.degree()
epsilon = 0.167
X = ceil(1/2*N**(1/delta-epsilon))
m = ceil(1/(delta*epsilon))
g=[]
for i in range(1,m+1):
j = delta-1
while j >= 0:
g.append((x*X)**j * N**i * f(x*X)**(m-i))
j -= 1
rank = m*delta
M = Matrix(ZZ, rank)
for i in range(rank):
for j in range(rank):
M[i, rank-1-j] = g[i][j]
M = M.LLL()
f_new = 0
for i in range(rank):
f_new += M[0][i] * x**(rank-1-i) / X**(rank-1-i)
try:
print(long_to_bytes(f_new.roots()[0][0]))
except:
print("FAIL")
Mad hat
A dream is not reality, but who's to say which is which?
This problem gives madhat.py, output.txt.
Solution
\(p\) must be 75 or 37 in order for the ciphertext to be 76 length.
\[c=m\cdot M-\text{key}[1]\]M has only two cases.
\[m=(c+\text{key}[1])\cdot M^{-1}\]\(\text{key}[1]\) also has a small possible range.
\[-\text{min}(c)-128\times 76<\text{key}[1]<-\text{max}(c)+128\times76\]Just brute-force the key!
Here is my code.
cipher = [[-3459749918754130611, -3459749918754138177, -3459749918754137803, -3459749918754138385, -3459749918754138025, -3459749918754138097, -3459749918754138073, -3459749918754138245, -3459749918754138183, -3459749918754138445, -3459749918754137991, -3459749918754138597, -3459749918754138309, -3459749918754138309, -3459749918754138279, -3459749918754138771, -3459749918754138327, -3459749918754138485, -3459749918754138233, -3459749918754138389, -3459749918754138207, -3459749918754138555, -3459749918754138141, -3459749918754138501, -3459749918754138677, -3459749918754138297, -3459749918754138563, -3459749918754138439, -3459749918754138429, -3459749918754138041, -3459749918754138611, -3459749918754138469, -3459749918754138217, -3459749918754138585, -3459749918754138403, -3459749918754138177, -3459749918754137777, -3459749918754138587, -3459749918754138231, -3459749918754138677, -3459749918754138127, -3459749918754138679, -3459749918754137789, -3459749918754138305, -3459749918754138025, -3459749918754138301, -3459749918754137941, -3459749918754138489, -3459749918754137583, -3459749918754138297, -3459749918754137949, -3459749918754138475, -3459749918754137879, -3459749918754138813, -3459749918754137981, -3459749918754138395, -3459749918754138201, -3459749918754138459, -3459749918754138195, -3459749918754138617, -3459749918754138003, -3459749918754138557, -3459749918754138429, -3459749918754138499, -3459749918754137951, -3459749918754138673, -3459749918754137975, -3459749918754138341, -3459749918754138121, -3459749918754138375, -3459749918754137869, -3459749918754138459, -3459749918754137739, -3459749918754138405, -3459749918754137921, -3459749918754138775]]
p = 37
Q = []
for i in range(p):
q = []
for j in range(p):
if i == j:
q.append(0)
elif pow((i-j), int ((p-1) // 2), p) == 1:
q.append(1)
else:
q.append(-1)
Q.append(q)
H = []
r = []
r.append(0)
r.extend([1 for i in range(p)])
H.append(r)
for i in range(1, p + 1):
r = []
for j in range(p + 1):
if j == 0:
r.append(1)
else:
r.append(Q[i-1][j-1])
H.append(r)
H2 = [[0 for j in range(2*(p+1))] for i in range(2*(p+1))]
for i in range(0, p+1):
for j in range(0, p+1):
if H[i][j] == 0:
H2[i*2][j*2] = 1
H2[i*2][j*2+1] = -1
H2[i*2+1][j*2] = -1
H2[i*2+1][j*2+1] = -1
elif H[i][j] == 1:
H2[i*2][j*2] = 1
H2[i*2][j*2+1] = 1
H2[i*2+1][j*2] = 1
H2[i*2+1][j*2+1] = -1
else:
H2[i*2][j*2] = -1
H2[i*2][j*2+1] = -1
H2[i*2+1][j*2] = -1
H2[i*2+1][j*2+1] = +1
I0 = Matrix(H2)
I1 = Matrix(H2)*(-1)
I0 = I0.inverse()
I1 = I1.inverse()
M = max(cipher[0])
m = min(cipher[0])
for d in range(-m-128*76, -M+128*76):
print(d)
flag = Matrix([cipher[0][i]+d for i in range(76)])
if d % 2 != 0:
matrix = flag*I1
else:
matrix = flag*I0
flag = ''
try:
for i in range(76):
x = matrix[0][i]
flag += chr(x)
if "CCTF" in flag:
print(flag)
break
except:
continue
Model
The encryption validation thread model is invalid!
nc 04.cr.yp.toc.tf 8001
This problem gives just ip, port.
Key generation
def genkey(nbit):
while True:
p, q = getPrime(nbit), getPrime(nbit)
if gcd((p-1) // 2, (q-1) // 2) == 1:
P, Q = (q-1) // 2, (p-1) // 2
r = inverse(Q, P)
e = 2 * r * Q - 1
return(p, q, e)
Encrypt Function
def encrypt(msg, pubkey):
e, n = pubkey
return pow(bytes_to_long(msg), e, n)
We can get the ciphertext of flag and public key.
Solution
\[d=e\]Done. Just decrypt! No code.
One Line Crypto
A profile, a look, a voice, can capture a heart ♥ in no time at all.”
This problem gives one_line_crypto.py, flag.enc.
Solution
It is not uncommon to satisfy this condition,
p, q = x**(m+1) - (x+1)**m, y**(n+1) - (y+1)**n
assert isPrime(p) and isPrime(q) and p < q < p << 3 and len(bin(p*q)[2:]) == 2048
I just did brute-forcing when \(x\) and \(m\) is in range(2,1000).
Here is my code.
from Crypto.Util.number import *
from math import gcd
'''
for x in range(1000):
for m in range(1000):
p = x**(m+1)-(x+1)**m
if len(bin(p)[2:]) > 1025:
break
elif len(bin(p)[2:]) == 1025:
if isPrime(p) == True:
print(x, m, p)
'''
p = 57317700419715468513185509060583512178200535449200562119327466031665644769904333354067160157145008150370597520080962086380559115254150287086026192349765034581949024305095306399787645130021756225377516198895786544717767497375889752986343077823214180643260929105311546605264454435411893914316040420635895658369
q = 294214241043210847882633628460406569791004369248219469864868650839944892041552240115071921799516814453729223636385495706851064791673605812405426598104306214287211381632931839743688359795486667731446998689421253087437104672397328045443587236120188583037287351172306262921448876283904175440304649379775701352449
assert len(bin(p*q)[2:]) == 2048
assert p < q < p << 3
c = 14608474132952352328897080717325464308438322623319847428447933943202421270837793998477083014291941466731019653023483491235062655934244065705032549531016125948268383108879698723118735440224501070612559381488973867339949208410120554358243554988690125725017934324313420395669218392736333195595568629468510362825066512708008360268113724800748727389663826686526781051838485024304995256341660882888351454147057956887890382690983135114799585596506505555357140161761871724188274546128208872045878153092716215744912986603891814964771125466939491888724521626291403272010814738087901173244711311698792435222513388474103420001421
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
assert gcd(e, phi) == 1
d = inverse(e, phi)
flag = pow(c, d, N)
print(long_to_bytes(flag))
Three Ravens
There were three ravens sat on a tree, Downe a downe, hay downe, a downe, They were as black as they might be.
This problem gives three_ravens.py, output.txt.
Solution
Let \(s = p+q+r\).
If \(m < s\), solve \(d\) by \(d=e^{-1} \mod{s-1}\), then,
\[m^{ed}=m \mod{s}\]It gives me the flag! Simple. No code.
Trailing Bits
The text that includes the flag is transmitted while unfortunately both of its head and tail bits are lost 😟
This problem gives only output.txt.
No solution. Simple.
Here is my code.
from Crypto.Util.number import *
output = "01001000000110001001100001011100110110100101100011001000000111010101101110011010010111010000100000011011110110011000100000011010010110111001100110011011110111001001101101011000010111010001101001011011110110111000100000011010010110111000100000011000110110111101101101011100000111010101110100011010010110111001100111001000000110000101101110011001000010000001100100011010010110011101101001011101000110000101101100001000000110001101101111011011010110110101110101011011100110100101100011011000010111010001101001011011110110111001110011001011100010000001010100011010000110010100100000011011100110000101101101011001010010000001101001011100110010000001100001001000000111000001101111011100100111010001101101011000010110111001110100011001010110000101110101001000000110111101100110001000000110001001101001011011100110000101110010011110010010000001100100011010010110011101101001011101000010111001011011001100010101110100100000010101000110100001100101001000000110001001101001011101000010000001110010011001010111000001110010011001010111001101100101011011100111010001110011001000000110000100100000011011000110111101100111011010010110001101100001011011000010000001110011011101000110000101110100011001010010000001110111011010010111010001101000001000000110111101101110011001010010000001101111011001100010000001110100011101110110111100100000011100000110111101110011011100110110100101100010011011000110010100100000011101100110000101101100011101010110010101110011001011100010000001010100011010000110010101110011011001010010000001110110011000010110110001110101011001010111001100100000011000010111001001100101001000000110110101101111011100110111010000100000011000110110111101101101011011010110111101101110011011000111100100100000011100100110010101110000011100100110010101110011011001010110111001110100011001010110010000100000011000010111001100100000011001010110100101110100011010000110010101110010001000000011000001101111011100100011000100101100001000000110001001110101011101000010000001101111011101000110100001100101011100100010000001110010011001010111000001110010011001010111001101100101011011100111010001100001011101000110100101101111011011100111001100100000011100110111010101100011011010000010000001100001011100110010000001110100011100100111010101100101001011110110011001100001011011000111001101100101001011000010000001111001011001010111001100101111011011100110111100101100001000000010101100101111111000101000100010010010001011000010000001101111011100100010000001101111011011100010111101101111011001100110011000100000011000010111001001100101001000000110001101101111011011010110110101101111011011100010111000001010010101000110100001100101001000000110011001101100011000010110011100100000011010010111001100100000010000110100001101010100010001100111101101101001011101000011010101011111001100110110111000110000011101010011100101101000010111110110101001010101001101010101010001011111011101000100111101011111011100110100100000110001011001100111010001011111010011010011001101111101000010100101010001101000011001010010000001100011011011110111001001110010011001010111001101110000011011110110111001100100011001010110111001100011011001010010000001100010011001010111010001110111011001010110010101101110001000000111010001101000011001010111001101100101001000000111011001100001011011000111010101100101011100110010000001100001011011100110010000100000011101000110100001100101001000000111000001101000011110010111001101101001011000110110000101101100001000000111001101110100011000010111010001100101011100110010000001101111011001100010000001110100011010000110010100100000011101010110111001100100011001010111001001101100011110010110100101101110011001110010000001110011011101000110111101110010011000010110011101100101001000000110111101110010001000000110010001100101011101100110100101100011011001010010000001101001011100110010000001100001001000000110110101100001011101000111010001100101011100100010000001101111011001100010000001100011011011110110111001110110011001010110111001110100011010010110111101101110001011000010000001100001011011100110010000100000011001000110100101100110011001100110010101110010011001010110111001110100001000000110000101110011011100110110100101100111011011100110110101100101011011100111010001110011001000000110110101100001011110010010000001100010011001010010000001110101011100110110010101100100001000000110010101110110011001010110111000100000011101110110100101110100011010000110100101101110001000000111010001101000011001010010000001110011011000010110110101100101001000000110010001100101011101100110100101100011011001010010000001101111011100100010000001110000011100100110111101100111011100100110000101101101001011100010000001001001011101000010000001101101011000010111100100100000011000100110010100100000011100000110100001111001011100110110100101100011011000010110110001101100011110010010000001101001011011010111000001101100011001010110110101100101011011100111010001100101011001000010000001110111011010010111010001101000001000000110000100100000011101000111011101101111001011010111001101110100011000"
for i in range(8):
flag = output+'0'*i
flag = int(flag, 2)
if "CCTF" in flag:
print(long_to_bytes(flag))