Table of Content
Intro
Arab Security Conference was held this year from 18th till 19th of September and as always the last day was for the cyber wargames competition where ten qualified teams compete with each other and solve sophisticated real life challenges in 6 different categories. In this write-up, we’re going to discuss and solve the 5 crypto challenges in the competition. The challenges was easy-medium and hard ones, but full of tricks for those who aren’t aware of the encryption algorithms and techniques. However, I’ll show you my thought process and how to divide the challenge into sub-challenges in order to attack the algorithm or find a solution.
:DISCLAIMER:
As usual, you’re not gonna find here all the tips and tricks in cryptography since I wanted to leave some space for you to think and ask. So, feel free to think more about the challenge before jumping right into the solution.
| Challenge | Difficulty | Points |
|---|---|---|
| Randomeness | Warmup | 150 |
| Double | Easy | 300 |
| Log Out | Medium | 600 |
| In Between | Medium | 600 |
| Square Group | Hard | 900 |
Randomness
Description:
Random everywhere.
It’s a warmup challnege and pretty known attack, but need to be
aware of the algorithm used in the encryption, so let’s have a
look at the the files given
output.txt
text file and
randomness.py
a python script.
0x3ada728da2811b7928cb46cb97d9d905d6ef274f2535a361a549dcd99d26461d7e88ea5178c374339e0ada83487b8a1fc8ef6aea65e3f24b61
0x133c7655470ef0b4d0bb6bcbe741117f1b372e14adc69211a6ef6fbc8fd8d3de0ba19a2214b64876b058cad79707b6f127fadbe16e906f18c8
0x589645936cac16c433f6c15a6929f222d5b58f140009e43a1766cc56a3b5ec859529f3220115302acb51186d5e5e308a60b8891f888fafa552
...The text file contains around 63 hex encoded lines. Let’s look at the script:
from Crypto.Util.number import \*
from secret import plains
plain = b'I wanna look closer, but my glasses are broken!'
class GDSA:
def **init**(self):
self.p = self.genPrime() # 71500532584610353335967572228576961622670888049686244244336530474941226340958441170979183862795117652159440106046491327947803659173888001
self.x = getRandomInteger(256)
self.g = 7
self.A = pow(self.g, self.x, self.p)
self.k = getRandomInteger(128)
while GCD(self.k, self.p-1) != 1:
self.k = getRandomInteger(128)
def sign(self, msg):
m = bytes_to_long(msg)
r = pow(self.g, self.k, self.p)
s = (pow(self.k, -1, self.p-1) * (m - self.x*r)) % (self.p - 1)
return r, s
def genPrime(self):
p = 0
while not isPrime(p+1):
p = 2
for _ in range((2<<2)):
p *= getRandomInteger(50)
p *= getRandomInteger(64)
return p+1
obj = GDSA()
sigs = []
for plain in plains:
r, s = obj.sign(plain)
sigs += [hex(s)]
sigs += [hex(r)]
with open('output.txt', 'wb') as f:
for s in sigs:
f.write(s.encode()+b'\n')
The script contains one class called GDSA with
2 functions
sign
and
genPrime. It first generate a radom prime with the
genPrime
function, then it computes some parameters \(A = g^x \pmod p\)
where \(x\) is a random 256-bit integer, \(g=7\) kind of a base,
and \(p\) is a random odd prime. It also calcultes a random
128-bit integer \(k\) and check the \(gcd(k, p-1) = 1\).
Next, the
genPrime
function calculates 464-bit odd prime and it seems that the
integers generated the prime are 50-bit long so it most probably
a weak prime. The next function
sign,
it takes a plain message \(m\) and calculate \(r = g^k \pmod p\)
and \(sk = m-xr \pmod{p-1}\), then it returns \(r\) and \(s\).
Actually, the last thing this script does is, it signs the
plains
that maybe contains a list of plain texts and the
plain = b'I wanna look closer, but my glasses are
broken!'
looks one of them.
Solution
The challenge has 2 vulnerablilities the first one is the weak prime and you can use it to calculate the random variable \(k\) and the second one is using the same \(k\) to sign multiple messages. Apparantly, the easy way is that you can search about this knwon attack on El Gamal signature scheme.
\(r_i = g^k \pmod p\) \(s_ik = m_i - xr_i \pmod{p-1}\)
So, if you take 2 signatures signed with the same random key, you can get the message back \(s_1k = m_1 - xr_1 \pmod{p-1}\) and \(s_2k = m_2 - xr_1 \pmod{p-1}\), then by subtracting the eqautions will give you \(s_1k - s_2k = m_1 - m_2 \pmod{p-1}\). Finally, you have all the variables except one of the \(m_i\), but you can bruteforce the other message to get the flag.
- Using DLP to get the random key \(k = 45252513931146808668347235459955660091\).
- Bruteforce the list of signatures to get the flag.
with open('output.txt', 'rb') as f:
sigs = [int(l.strip().decode()[2:],16) for l in f.readlines()]
r = sigs[-1]
sigs = sigs[:-1]
p = 71500532584610353335967572228576961622670888049686244244336530474941226340958441170979183862795117652159440106046491327947803659173888001
k = 45252513931146808668347235459955660091
for i in range(0, len(sigs)-1):
for j in range(i+1, len(sigs)):
s1, s2 = sigs[i], sigs[j]
m = (k\*(s1 - s2)+btl(plain)) % (p-1)
if b'ASCWG{' in ltb(m):
print(ltb(m).decode('latin-1'))
Flag:
ASCWG{H17719_7H3_W0r1d_0f_W33k_Pr1m3_E1G4m@1_$16n47ur3s}
Double
Description:
I’ve tried to mess up with the scheme a little bit, but I think using 2 ciphertexts is secure enough.
This one was easy given a powershell
double.ps1
script and an
output.txt
files. Let’s look at the script first:
# greatest common divisor
function GCD([bigint]$a, [bigint]$b) {
while ($b -ne 0) {
$a, $b = $b, ($a % $b)
}
return $a
}
function \_Gen() {
[bigint]$p = [bigint]::Parse("[REDACTED]")
[bigint]$q = [bigint]::Parse("[REDACTED]")
[bigint]$N = $p*$q
[bigint]$e = Get-Random -Minimum 2 -Maximum $N
[bigint]$g = GCD $e $N
while($g -ne 1) {
[bigint]$e = Get-Random -Minimum 2 -Maximum $N
}
[bigint]$r1 = Get-Random -Minimum 2 -Maximum $N
[bigint]$r2 = Get-Random -Minimum 2 -Maximum $N
[bigint]$a1 = [bigint]::ModPow($e, $r1*($p-1), $N)
[bigint]$a2 = [bigint]::ModPow($e, $r2*($q-1), $N)
$pub = [ordered]@{a1 = $a1; a2 = $a2; N = $N}
$priv = [ordered]@{p = $p; q = $q; r1 = $r1; r2 = $r2}
return $pub, $priv
}
function Encrypt ([bigint]$m) {
$pub, $priv = _Gen
[bigint]$s1 = Get-Random -Minimum 2 -Maximum $pub.N
[bigint]$s2 = Get-Random -Minimum 2 -Maximum $pub.N
[bigint]$d1 = [bigint]::ModPow($pub.a1, $s1, $pub.N)
[bigint]$d2 = [bigint]::ModPow($pub.a2, $s2, $pub.N)
[bigint]$c1 = $m*$d1 % $pub.N
[bigint]$c2 = $m*$d2 % $pub.N
return [ordered]@{c1 = $c1; c2 = $c2; pub = $pub}
}
$Result = Encrypt "[REDACTED]"
Out-File -FilePath .\output.txt -InputObject $Result.Values
The function
_Gen
it first parse a redacted primes \(p\) and \(q\), then generates
a random integer \(e\) and checks the \(gcd(e, N) = 1\), then
generates integer pairs \(r_1\) and \(r_2\), and calculates
\(a_1 = e^{r_1(p-1)} \pmod{N}\), \(a_2 = e^{r_2(q-1)}
\pmod{N}\). Finally, returns \((a_1, a_2, N)\) as public key and
\((p, q, r_1, r_2)\) as private key.
Second function
Encrypt
it takes an integer \(m\) and generates a random pair \(s_1\)
and \(s_2\), then computes \(d_1 = a_1^{s_1} \pmod N\) and \(d_2
= a_2^{s_2} \pmod N\). After that, it calculate the ciphertexts
\(c_1 = md_1 \pmod N\) and \(c_2 = md_2 \pmod N\) and write out
the output into a text file
output.txt.
Solution
From the
_Gen
function you can notice that \(a_1 = e^{r_1(p-1)} \pmod{N}\) and
if you can recall that
Fermat’s Little Theorem
that \(x^{p-1} = 1 \pmod p\) for any arbirary \(x\). So, if we
can use it to some how get one of the factors of \(N\).
First, we can reorder the equation in order to get it exactly what we need \(a_1 = e^{r_1(p-1)} = 1 \pmod p\) and vice versa for \(a_2\), that is \(a_1 - 1 = 0 \pmod p\) which means that this value can divide \(p\), so subtracting \(a_1\) by 1 it gives a multiple of \(p\), thus \(gcd(a_1 - 1, N)\) is one of the factors.
Second, you know that \(c_i = md_i \pmod N\) and \(d_i = a_i^{s_i} \pmod N\), then you can compute \(c_1 = m \pmod p\) and \(c_2 = m \pmod q\), since \(a_1 = 1 \pmod p\) and \(a_2 = 1 \pmod q\).
Finaly, \(m = c_1 \pmod p\) and \(m = c_2 \pmod q\) this is a linear modular equation that can be solved by CRT to get the flag.
from Crypto.Util.number import \*
from sympy.ntheory.modular import crt
N = 118668704021991818349473680192223330422816228468750943595381082314526050113696380807584760546007047678131969252670742664045859564002270909023859216439518114223967366083739005529699291141394204380772133322697864571619729422536029697598505413459898192967998598101655904127997255253467376305279937967927007502679
a1 = 90776977107449858385443758684442059641945999507299313330252819907558682299012274632127933880137958091084773046807425787489001724881817788815591177692784408706685784050224038774376770317829373320769691511381734535671635221319263406471410617846315198327518237604001149726830794649465985570494228797379448498927
c1 = 6195249196454318189426748893437014217552608859756027615756624850269174100512987973139389433240944467740665747379606613850959142514227272665726030526141820783149433517571484830412752949115120491998636349010167878422854196170920795258210423564644389158199632339637707701033463855032399261894761531192528141533
c2 = 36394983520778694746453349314125103778319956095037786845977975871195630823579330406427772373191300990672834473643822146541572711871337222201983386956653850943180058112595015124238527155928970536405040561393558156774450093806082156321669898136685900478208806747232019988936048555941851561561959786849518834025
p = GCD(a1-1, N)
q = N//p
print(isPrime(p), q)
print(long_to_bytes(crt([p, q], [c1, c2])[0]))
Flag:
ASCWG{D3_F3rm47_7h3_l1ttl3_7H30rY_0f_R5A}
Log Out
Description:
A cryptographer has invented a protocol for authentication, but when he tried to test it out something went wrong.
This one needs a solid understanding of how modular
exponentiation work. Given a
log_out.py
script that has the following code.
from Crypto.Util.number import \*
from secret import FLAG
BITS = 358
p = getPrime(BITS) # 458831312996324044306144898299845370771994439995921953739842657870615957299268933078781055225998534731979521
print(p)
def gen(p):
e = getRandomNBitInteger(BITS >> 1) % (p-1)
d = inverse(e, p-1)
return e, d
Alice = e1, d1 = gen(p)
Bob = e2, d2 = gen(p)
assert e1*d1 % (p-1) == 1
assert e2*d2 % (p-1) == 1
m = bytes_to_long(FLAG)
one = pow(m,e1,p) # 61931188702156649671605655073486391182782890630770517291203521771853183608276742802393948908853893282002240
two = pow(one,e2,p) # 30961102159927747611133998031126561891432030459135102738698401883176384849554325319024060345831531631633754
three = pow(two,d1,p) # 31905239398903218257458412804055017253162990574306516376045451484133505407415750776680499099863816940837544
print(one, two, three)
The script has only one function
gen
that takes a prime \(p\) and generates a random 179-bit integer
\(e\) and an integer \(e_id_i = 1 \pmod{p-1}\). Then, the script
gets 2 painrs of (\(e_1,d_1\)) and \((e_2, d_2)\) and encrypts
the flag as
\(one = m^{e_1} \pmod p\) \(two = one^{e_2} \pmod p\) \(three = two^{d_1} \pmod p\)
Solution
Actually, if you take a closer look at the script it’s just implements 3 Pass Protocol and if you know how things can get wrong here you can easly break it. So, from here we know that it uses modualr exponentiation over prime field and if this prime was weak it can break the protocol and get the plain message. A weak prime is an odd prime that its euler totient can be factored as small prime numbers and you can check this one easly on your machine or Alpertron.
factor(p-1) = 2^8 × 3 × 5 × 7 × 13 × 19^2 × 53 × 113 × 167 × 2617 × 4649 × 6581 × 8501 × 13597 × 37897 × 79939 × 181639 × 240173 × 3730801 × 7011233 × 16829834759 × 28159186127651 × 239850655476463133Now, we can use the defined equations to solve the DLP to get the random key \(e_2\), since \(two = one^{e_1} = m^{e_1e_2} \pmod p\), then use the third equation to get the flag.
\(three = one^{e_2d_1} = m^{e_1e_2d_1} = m^{e_2} \pmod p\) \(m = three^{d_2} = m^{e_2d_2} \pmod p\)
from Crypto.Util.number import \*
p = 458831312996324044306144898299845370771994439995921953739842657870615957299268933078781055225998534731979521
one = 61931188702156649671605655073486391182782890630770517291203521771853183608276742802393948908853893282002240
two = 30961102159927747611133998031126561891432030459135102738698401883176384849554325319024060345831531631633754
three = 31905239398903218257458412804055017253162990574306516376045451484133505407415750776680499099863816940837544
e2 = 716487297247009701312843013478492214587216006472061211
d2 = inverse(e2, p-1)
m = pow(three,d2,p)
print(long_to_bytes(m))
Flag:
ASCWG{3Pa$$$$_7h3_5h4m1r_l095_Pr070c0l}
In Between
Description:
I found some sort of smooth encryption scheme until I noticed what I’ve did wrong.
This one was an interesting challenge uses broken RSA, the
description has a big hint and you have to dig a little deeper
researching how this works. Given 3 files 2 encrypted ones and
between.py
a python script.
from Crypto.Util.number import getPrime, long_to_bytes as ltb, bytes_to_long as btl, GCD, isPrime, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import sha1
from random import getrandbits
from secret import FLAG
BITS = 512
def gen(p):
r = 0
while not isPrime(r+1):
r = getrandbits(30)
if r & 1:
r _= 2
r _= p
for \_ in range(12):
r \*= getrandbits(30)
return r+1
def encrypt(plain, secret):
key = sha1(ltb(secret)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC)
return key, cipher.encrypt(pad(plain, 16)), cipher.iv
p = getPrime(BITS)
q = gen(p)
e = 0x10001
N = p\*q
secret = getPrime(BITS)
enc = pow(secret, e, N)
with open('flag.jpg', 'rb') as fi, open('flag.jpg.enc', 'wb') as fo, open('secret.enc', 'wb') as sw:
m = fi.read()
k, ct, iv = encrypt(m, secret) # iv: 060c341af2e010640dab4e36da52a0bf
fo.write(ct)
sw.write(ltb(enc))
Looking at the script, it has 2 functions the first one
encrypt
that takes a plain text and a secret key and encryptes the text
with AES-CBC and the other
gen
function takes a prime \(p\) and generates another odd prime
based on it.
So, it generates a 512-bit prime \(p\) and another prime \(q =
2r_1pr_i + 1\), then continues to generate the public RSA key
\(e=65537\) and \(N=pq\). Next, it generates a secret 512-bit
prime and encrypts it using the generated public key. The last
step, it encrypts the flag image file using the generated secret
prime and write the encrypted secret and the encryped flag into
another files
flag.jpg,enc
and
secret.enc
respectively.
Solution
If you know exactly how RSA works, you would notice that \(gcd(pq, (p-1)(q-1)) \neq 1\) which violates the RSA scheme. Now, obviously \(q-1\) cannot divide \(p\) and so we must have \(p\) divides \(q-1\), therefore \(q-1 = kp\) for some integer \(k > 1\). Next, the description says that it uses a smooth encryption, so it has something to do with smooth numbers. Digging deeper about this you would find that RSA under some conditions has a weakness called powersmooth. A B-powersmooth number is a product of coprime numbers less than B.
Suppose that \(k\) is B-powersmooth for small B, then we have \(M = \alpha k\) and \(M\) is a product of prime powers up to \(B\). Thus, for any arbitrary number \(a^{MN} = a^{Mpq} = a^{\alpha (kp)q} = a^{(q-1)p} = 1\pmod q\), so we can get the one of the factor as \(gcd(a^{MN} - 1, N) = q\).
The attack constructed as follows:
- Find the correct \(B\).
- Get all the primes powers less that \(B\).
- Compute the \(gcd(a^{MN} - 1, N)\) and check if it’s one of the factors or not.
# sage script
B = [1e8, 2e8, 3e8]
def attack(n, B=35000000):
M = prod([p^int(log(B)//log(p)) for p in prime_range(B+1)])
X = pow(2, M\*n, n)-1
g = gcd(X, n)
return g if g != 1 else -1
for b in B:
print(attack(N, int(b)))After almost 10 minutes you’ll get the correct factor with \(B=3e8\).
p = 9996930395710692308723580739714839673824098096948372397222427386572812982902478682725969655560512983970656202579690730301194267797899776213369834530408843
q = 13676546176221391845743984276096814665020986169532351881058926805368552212755389915876704203234021829266073063940714414760663706386188058384359455852297083418573870417737220019120715742271178904257599420856869702284679302607307220546439558652235458513126014250188801
N = p*q
phi = (p-1)*(q-1)
d = inverse(e, phi)
def decrypt(ciphertext, secret, iv):
key = sha1(ltb(secret)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
return unpad(cipher.decrypt(ciphertext), 16)
with open('secret.enc', 'rb') as s:
secret_enc = btl(s.read())
secret = pow(secret_enc, d, N)
print(secret)
with open('flag.jpg.enc', 'rb') as h, open('flag_out.jpg', 'wb') as h2:
iv = bytes.fromhex('060c341af2e010640dab4e36da52a0bf')
ct = h.read()
m = decrypt(ct, secret, iv)
h2.write(m)
This attack works since the product of primes of a B-powersmooth number contains a subset that equal to a one of prime factors.
Flag:
ASCWG{P0wer1n9_7h3_$m00th_0f_W33k_R5A_$ch3m3}
Square Group
I’ve implemented this super secure algorithm can you break it?
Actually, this challenge is the hardest one and it uses a El
Gamal encryption using galois field. Given 2 files
output.txt
file and
square_group.py
a python sage script, let’s have a look.
from secret import a, b, FLAG
from Crypto.Util.number import *
p = random_prime(2^292)
F.<g> = GF(p^2, 'g')
A = F(g^a)
B = F(g^b)
m = bytes_to_long(FLAG)
assert m.bit_length() == 319, "[BIT SIZE ERROR]"
k = getrandbits(256)
c1 = F(g^k)
c2 = F(m*A^k)Obviously, the script generates a 292-bit odd prime \(p\), then creates a finite field of size \(p^2\) with a group generator \(g\). After that, it calculates \(A = g^a\) and \(B = g^b\) in the galois group. A finite field \(F_{p^2}\) is a group of finite number of elements (of size \(p^2\)) and each element on the form \(F = {x+yg : x,y \in GF(p)}\) where \(g\) is the group generator.
Next, it converts the flag to an integer and generates a random 256-bit integer \(k\), then calculates \(c_1 = g^k\) and \(c_2 = mA^k\) also in the group which means addition, multiplication and subtraction operations are calculated inside the group \(F = GF(p^2)\).
Let’s have a look at the other file.
p=7808808261360015401937185698517396439966052041595570744555697660178736409406537821914879
A=994624118599273439394621380260612024769574069295856347262583816949463093938694374068048*g + 7347506893480480577445421299579485948782959433446893691339909418080574816261902573328140
B=7450126928612503418678909312968592367965743905872306342210513251189577325432751921786867*g + 3752222068062758274773375759463057208078916797550789238029540291244899472217195194466577
c1=7136735687590692247979294876477005084364049400865084776707060016253284318462817092615593*g + 6657675541958696150178558992705236561443142637506941735336975375664763127345451697731719
c2=901435522984016617934008187902137349351958662418525525352377028097054635214542797226798*g + 6638201617319780555547138472700118770064559112794745161877570466029555182078290145046491Solution
It’s obvious that the script uses El Gamal encryption scheme, but you would notice that the flag has 319 bits while the prime has only 292 bit, thus the encryption here is not correct and the decryption will get a compressed integere rather than the flag. Now, the attack goes as following:
- Try to get the values of \(a\) and \(b\) using DLP.
- Decrypt the corrupted flag, then bruteforcing to get the correct numbers of bits.
If you start searching about
DLP
over finite field in Sage, you would get that it has 2 functions
the first one is direct DLP
discrete_log
and the other solves it under some condition
linear_relation. So, of course you shall first try the easier one in case it
can get the correct solution quick. (You may be stuck at this
point if you don’t know sage or the condition that the second
function would work under. So, during the competition you should
ask the admin about any hints he would give).
p = 7808808261360015401937185698517396439966052041595570744555697660178736409406537821914879
F.<g> = GF(p^2, 'g')
A = 994624118599273439394621380260612024769574069295856347262583816949463093938694374068048*g + 7347506893480480577445421299579485948782959433446893691339909418080574816261902573328140
B = 7450126928612503418678909312968592367965743905872306342210513251189577325432751921786867*g + 3752222068062758274773375759463057208078916797550789238029540291244899472217195194466577
b, a = linear_relation(A, B, '\*')
# (616571192307631787633959367126579, 1808360367944820210034920030960081223)Now, let’s see what happpens if we decrypt the values \(c_1\) and \(c_2\) by
\(c_2c_1^{a}^{-1} = mA^kg^{ak}^{-1} = mg^{ak}g^{ak}^{-1} = m\).
c1 = 7136735687590692247979294876477005084364049400865084776707060016253284318462817092615593*g + 6657675541958696150178558992705236561443142637506941735336975375664763127345451697731719
c2 = 901435522984016617934008187902137349351958662418525525352377028097054635214542797226798*g + 6638201617319780555547138472700118770064559112794745161877570466029555182078290145046491
d = int(((c1^a)^-1)\*c2)
print(long_to_bytes(d))
# b'~Fy\xa5 K\xf1\xf3\xaf-\xb42\xdd\xeeE\x15\xfb\xb5P;\x8b8Z\xb3\xb0\x85\xab\xe3\x9a\xe1B\x84\xf4\xae\xa0p'
Until that moment everything is going well and we already knew
that this values if the compressed flag bits module \(p\).
Suppose that \(d\) is the compressed bits, then \(m = rp + d\)
and you know that the corerect flag is 319-bit long. Now,
319-292=27is the remaining bits of the multiple \(r\) to get the correct
value of the flag.
Finally, we can bruteforce this value and get the correct flag bits.
for r in range(2**26, 2**27 - 1):
if b'ASCWG{' in long_to_bytes(r*p + d):
print(r, long_to_bytes(r*p + d))
break
Flag:
ASCWG{b17in9_0v3r_ElG@m41_G4l0i$_Gr0up5}
Conclusion
In this writeup, I’ve demostrated a detailed analysis of all the crypto challenges I’ve created in the competition as well as, my thought process of how I could solve the problem. I hope you’ve enjoyed the competition and learned something from the challenges that are created by me or even my teammates. Lastly, congrats to the first 3 teams, to every team who played fairly until the end and wish you all the best.