Introduction#
In this post, I’ll present my write-ups for all the challenges listed in the crypto category, in the order I solved them during the competition.
The challenges are:
Macaque#
Play on HackropoleDifficulty :
Points : 50
Solves : ?
Description :
Recover the flag using the remote service.
The service’s source code was provided :
#!/usr/bin/env python3
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from flag import flag
class Macaque():
def __init__(self, k1, k2):
self.k1 = k1
self.k2 = k2
self.bs = AES.block_size
self.zero = b"\x00" * self.bs
def tag(self, m):
m = pad(m, self.bs)
c1 = AES.new(self.k1, AES.MODE_CBC, iv = self.zero).encrypt(m)
c2 = AES.new(self.k2, AES.MODE_CBC, iv = self.zero).encrypt(m)
return c1[-self.bs:] + c2[-self.bs:]
def verify(self, m, tag):
return self.tag(m) == tag
def usage():
print("Commands are:")
print("|-> t: Authenticate a message")
print("|-> v: Verify a couple (message, tag)")
print("|-> q: Quit")
if __name__ == "__main__":
S = set()
singe = Macaque(os.urandom(16), os.urandom(16))
while True:
usage()
cmd = input(">>> ")
if not len(cmd):
exit(1)
if cmd not in ['t', 'v', 'q']:
usage()
continue
if cmd == 'q':
exit(0)
if cmd == 't':
if len(S) < 3:
print("Message (hex):")
message = bytes.fromhex(input(">>> "))
if not len(message):
exit(1)
tag = singe.tag(message)
print(f"Tag (hex): {tag.hex()}")
S.add(message)
else:
print("Error: you cannot use this command anymore.")
elif cmd == 'v':
print("Message (hex):")
message = bytes.fromhex(input(">>> "))
print("Tag (hex):")
tag = bytes.fromhex(input(">>> "))
check = singe.verify(message, tag)
if check and message not in S:
print(f"Congrats!! Here is the flag: {flag}")
elif check and message in S:
print("Valid!")
else:
print("Wrong tag. Try again.")
The aim of the challenge is to provide a message with a valid tag, that was not generated by the service. We have to perform a forgery attack.
By looking at how the Macaque class computes the tag, we see that it is composed of two parts:
- The last block of the AES-CBC encryption of the message using an all zero IV and unknown key $k_1$;
- The last block of the AES-CBC encryption of the message using an all zero IV and unknown key $k_2$.
Each part is actually an AES-CBC-MAC tag of the message with a different key.
We can provide 3 messages of any length to the service. CBC-MAC is known to be weak against variable-length messages. The wikipedia article explains in detail why this is the case by showing how tag forgery can be achieved.
Basically if we know a pair of messages and tags $(m, t)$ and $(m’, t’)$, we can forge a message $m’’ = m || m’_1 \oplus t || m’_2 || … || m’_x$ (where $m’_x$ denotes the block $x$ of $m’$), whose tag will be $t’$.
We can apply the same technique on both parts of our tag individually to forge a new one.
Forging the tag
To simplify, we’ll use a single block message $m = 0000…0001_{16}$, because the service automatically pads our input :
m = b'\x00'*15 + b'\x01'
# message will be padded
t = gettag(m[:15])
t1 = t[:16]
t2 = t[16:]
Using the first part of the tag, we can forge the first part for our new message $m||m’$:
# ask for tag of m ^ t1 || pad
# this implies that m' = m || pad
tag = gettag(strxor(t1, m))
t1_ = tag[:16]
Similarly, we can forge the second part:
# ask for tag of m ^ t2 || pad
tag = gettag(strxor(t2, m))
t2_ = tag[16:]
# reconstruct t'
t_ = (t1_ + t2_).hex()
Now we know the tag $t’$ of our new message $m’’ = m||m’ = m||m||pad$ and we can recover the flag :
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.strxor import strxor
from pwn import *
conn = remote("challenges1.france-cybersecurity-challenge.fr", 6000)
def gettag(m):
conn.recvuntil(">>> ")
conn.sendline("t")
conn.recvuntil(">>> ")
conn.sendline(m.hex())
conn.recvuntil(': ')
t = conn.recvline().strip().decode()
return bytes.fromhex(t)
# ask for tag of m
m = b'\x00'*15 + b'\x01'
# message will be padded
t = gettag(m[:15])
t1 = t[:16]
t2 = t[16:]
# ask for tag of m ^ t1 || pad
# this implies that m' = m || pad
tag = gettag(strxor(t1, m))
t1_ = tag[:16]
# ask for tag of m ^ t2 || pad
tag = gettag(strxor(t2, m))
t2_ = tag[16:]
# reconstruct t'
t_ = (t1_ + t2_).hex()
# validate
conn.recvuntil(">>> ")
conn.sendline("v")
conn.recvuntil(">>> ")
conn.sendline((m*2).hex())
conn.recvuntil(">>> ")
conn.sendline(t_)
flag = conn.recvline()
print(flag)
conn.close()
FCSC{f7c50c0e5ad148a3321d9dd0e72c91420e243b42c9c803814f6d8554163b6260}
RSA Destroyer#
Play on HackropoleDifficulty :
Points : 200
Solves : ?
Description :
This destroyes the RSA cryptosystem.
We were given the following output file :
e = 65537
n = 444874973852804286630293120525019547982392964519934608680681255396764239795499482860997657663742247333836933457910503642061679607999128792657151145831533603267962151902191791568052924623477918783346790554917615006885807262798511378178431356140169891510484103567017335784087168191133679976921108092647227149255338118895695993606854195408940572577899625236666854544581041490770396755583819878794842828965377818593455075306655077757834318066860484956428681524881285058664687568640627516452658874124048546780999256640377399347893644988620246748059490751348919880389771785423781356133657866769589669296191804649195706447605778549172906037483
c = 95237912740655706597869523108017194269174342313145809624317482236690453533195825723998662803480781411928531102859302761153780930600026069381338457909962825300269319811329312349030179047249481841770850760719178786027583177746485281874469568361239865139247368477628439074063199551773499058148848583822114902905937101832069433266700866684389484684637264625534353716652481372979896491011990121581654120224008271898183948045975282945190669287662303053695007661315593832681112603350797162485915921143973984584370685793424167878687293688079969123983391456553965822470300435648090790538426859154898556069348437896975230111242040448169800372469
And the following source code:
# **This** destroyes the RSA cryptosystem.
from Crypto.Util.number import isPrime, bytes_to_long
from Crypto.Random.random import getrandbits
def fastPrime(bits, eps = 32):
while True:
a, e, u = getrandbits(eps), getrandbits(eps), getrandbits(4 * eps)
p = a * (2 ** bits - e) + u
if isPrime(p):
return p
def generate(bits = 2048):
p = fastPrime(bits // 2)
q = fastPrime(bits // 2)
return p * q, 2 ** 16 + 1
n, e = generate()
p = bytes_to_long(open("flag.txt", "rb").read())
c = pow(p, e, n)
print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")
The code is actually not needed to solve this challenge.
By looking at the hexadecimal representation of $n$, we can see a particular pattern:
0xbf0a8dd7d8f16cad000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000001002c0b6fc6c3c2949b0a1e097f3c51eff2e8919800000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f
110eb
This is a strong indicator that the structure of $n$ looks like this : $(a2^x + b)(c2^x + d)$.
The particular structure of $n$ can be explained by looking at the generation of $p$ and $q$:
$$ \begin{split} p &= a(2^{1024} - e) + u \\ &= a2^{1024} - ae + u \\ &= a2^{1024} + b \end{split}$$
With : $$b = u - ae$$
We can easily rewrite $n$ like :
n = 0xbf0a8dd7d8f16cad*2**2048 + 0x1002c0b6fc6c3c2949b0a1e097f3c51eff2e89198*2**1024 + 0x526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f110eb
Let’s define $x = 2^{1024}$, we get a polynomial representation of $n$ :
poly = 0xbf0a8dd7d8f16cad*x**2 + 0x1002c0b6fc6c3c2949b0a1e097f3c51eff2e89198*x + 0x526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f110eb
Polynoms are way easier to factor than numbers. We can ask Sage to factor this polynom for us, and by evaluating both factors for $x = 2^{1024}$, we’ll recover $p$ and $q$.
r1, r2 = poly.factor_list()
p = int(r1[0](x=2**1024))
q = int(r2[0](x=2**1024))
assert p*q == n
With that we can recover the private key and decrypt the flag :
FCSC{cd43566923980e47f6630e82c2d9a55b388f01043bc78b9ce3354ce02acf22e8}
Lost Curve#
Play on HackropoleDifficulty :
Points : 200
Solves : 33
Description :
I lost the equation defining my elliptic curve: can you help me recover it?
The service’s source code was provided :
from fastecdsa.curve import Curve
from fastecdsa.point import Point
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange
BITS = 80
while True:
p = getPrime(BITS)
if p % 4 == 3:
break
a, b = randrange(1, p), randrange(1, p)
C = Curve("FCSC", p, a, b, 0, 0, 0)
while True:
xP = randrange(1, p)
yP = (xP ** 3 + a * xP + b) % p
if pow(yP, (p - 1) // 2, p) == 1:
break
yP = pow(yP, (p + 1) // 4, p)
assert (xP ** 3 + a * xP + b - yP ** 2) % p == 0
P = Point(xP, yP, C)
Q = 2 * P
print(a, b, p)
print("Can you find my secret curve equation: y^2 = x^3 + a*x + b (mod p)?")
print("I will give you two points:")
print(f"P = ({P.x}, {P.y})")
print(f"Q = ({Q.x}, {Q.y})")
try:
a = int(input(">>> a = "))
b = int(input(">>> b = "))
p = int(input(">>> p = "))
C = Curve("Check", p, a, b, 0, 0, 0)
check = True
check &= p.bit_length() >= BITS
check &= (P.x ** 3 + a * P.x + b - P.y ** 2) % p == 0
check &= (Q.x ** 3 + a * Q.x + b - Q.y ** 2) % p == 0
check &= (2 * Point(P.x, P.y, C) == Point(Q.x, Q.y, C))
if check:
print("Congratulations!! Here is your flag:")
print(open("flag.txt", "r").read())
else:
print("That's not it!")
except:
print("That's not it!")
When connecting to the service, we are greeted with two points on a newly generated curve and asked to provide it’s parameters $(p, a, b)$:
Can you find my secret curve equation: y^2 = x^3 + a*x + b (mod p)?
I will give you two points:
P = (439149843541918969442740, 726090390425959343034446)
Q = (860028547748438377464756, 183868916835552788256477)
Curve parameter recovery is easy given two points and the modulus, but in this case the modulus is unknown.
Luckily for us, those points are not random. Because $Q = 2*P$, we can use the point doubling formula and recover $p$.
Recovering the modulus
The point doubling formula is the following :
$$ \begin{cases} Q_x = D^2 - 2P_x \\ Q_y = D(P_x - Q_x) - P_y \end{cases}$$
With $D$ a special value that we do not need to detail here. We do not know $D$ and we can’t compute it as it depends on the value of $a$.
Recall that the above equations hold modulo $p$.
The idea to recover $p$ is to manipulate those equations in order to produce a multiple of $p$.
From the first equation we have $D^2 = Q_x + 2P_x$.
Let’s define $C = P_x - Q_x$.
From the second equation we have $DC = Q_y + P_y$, which implies $D^2 C^2 = (Q_y + P_y)^2$.
Using the result of the first equation, we get $(Q_x + 2P_x)C^2 = (Q_y + P_y)^2$.
Rewritten as $(Q_x + 2P_x)C^2 - (Q_y + P_y)^2 = 0$, we see that this is a multiple of $p$ and we have all the necessary information to compute it.
Once computed, $p$ should be the only 80-bit factor.
def recoverP(P, Q):
# point doubling equation
D2 = Q[0] + 2*P[0]
c = P[0] - Q[0]
Y2 = (Q[1] + P[1])**2
kp = D2*c**2-Y2
f = factor(kp)
for e, i in f:
if int(e).bit_length() == 80:
return e
p = 1180642197641892357421067
Recovering the other parameters
The curve equation is $y^2 = x^3 + ax + b \mod p$ with two unknowns $a$ and $b$. We have the coordinates of two points on the curve, thus we can recover $a$ and $b$ by solving a simple system of two linear equations :
$$\begin{cases} - aP_x - b = P_x^3-P_y^2 \\ -aQ_x - b = Q_x^3 - Q_y^2\end{cases}$$
This system of linear equations can be represented by a 2x2 Matrix containing the coefficients for the unknowns and a Vector containing the right side of the equation :
points = [P, Q]
F = GF(p)
l = []
v = []
for xy in points:
x = xy[0]
y = xy[1]
l.append([-x, -1])
v.append(x ** 3 - y ** 2)
M = Matrix(F, l)
V = vector(v)
a, b = [int(x) for x in M.solve_right(V)]
For the example above, we get :
a = 182525855477625044927892
b = 265776093310811435124473
We have all we need to get the flag :
FCSC{3e244ae57e01787c60ef5d3a5c8aa87d3c945855289e40d375aad955da8f8bb4}
Hashy Parmentier#
Play on HackropoleDifficulty :
Points : 200
Solves : ?
Description :
My cryptography professor said that a cryptographic hash function compresses data: but can it introduce problems?
The service’s source code was provided :
import sys
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
N = 64
class Hash:
def __init__(self):
self.h = b"\x00" * 4
def update(self, data):
assert len(data) % 4 == 0 # TODO
for i in range(0, len(data), 4):
block = data[i:i+4] * 4
h = self.h * 4
self.h = strxor(strxor(h, block), AES.new(h, AES.MODE_ECB).encrypt(block))[:4]
return self
def digest(self):
return self.h
S = set()
for i in range(4, 4 * (N + 1), 4):
try:
m = input(">>> Message #{:d}: ".format(i // 4))
m = bytes.fromhex(m)
assert len(m) == i
H = Hash()
S.add(H.update(m).digest())
except:
print("Error input.")
exit(1)
if len(S) <= 6:
print("Congratulations!! Here is your flag:")
print(open("flag.txt", "r").read().strip())
elif len(S) < 12:
print("Almost there!")
elif len(S) < 36:
print("Keep it up!")
elif len(S) < 64:
print("This is a good start, try again")
else:
print("Nope!")
The service asks for 64 messages in a row and store their hashes in a set. Each input should be 4 bytes longer than the previous one, starting with a 4-byte message. If at the end there are only 6 or less different hashes in the set, we get the flag.
We have to find collisions for this simple hash function.
The first thing we notice is that the internal state $h$ is quite small, only 4 bytes.
It is updated after having handled 4 bytes of data like this :
$$h = h \oplus block \oplus AES_h(block)$$
If we can find a block of data that does not change the state, we will have an easy solution, but this implies finding a block of data that encrypts to itself under the key $h$ (only for the first 4 bytes). We have to find a 4-bytes fixed point in AES.
This can be easily done by testing all the $256^4$ blocks, but there is no guarantee that a fixed point exists for every key.
I decided to perform the search in C, to speed things up. I took an open source AES implementation and modified the main function :
int main(void)
{
// state*4 after having hashed b'\x00'*4
uint8_t key[16] = { 102, 233, 75, 212, 102, 233, 75, 212, 102, 233, 75, 212, 102, 233, 75, 212 };
uint8_t buffer[16];
uint16_t d0, d1, d2, d3;
for (d0=0; d0<256; d0++) {
printf("Progress : %d/256\n", d0);
for (d1=0; d1<256; d1++) {
for (d2=0; d2<256; d2++) {
for (d3=0; d3<256; d3++) {
uint8_t plain_text[64] = { (uint8_t) d0, (uint8_t) d1, (uint8_t)d2, (uint8_t)d3, (uint8_t)d0, (uint8_t)d1, (uint8_t)d2, (uint8_t)d3, (uint8_t)d0, (uint8_t)d1, (uint8_t)d2, (uint8_t)d3, (uint8_t)d0, (uint8_t)d1, (uint8_t)d2, (uint8_t)d3 };
AES_ECB_encrypt(plain_text, key, buffer, 16);
if (memcmp(buffer, plain_text, 4) == 0) {
phex(plain_text);
}
}
}
}
}
return 0;
}
I didn’t get any result for the all zero key (initial state), so I tried for the state after having hashed 4 Null bytes and I got a fixed point :
Progress : 219/256
db6cbf0bdb6cbf0bdb6cbf0bdb6cbf0b
Progress : 220/256
We can check that it actually works:
print(Hash().update(b'\x00'*4+bytes.fromhex("db6cbf0b")).digest())
# b'f\xe9K\xd4'
print(Hash().update(b'\x00'*4+bytes.fromhex("db6cbf0b")*2).digest())
# b'f\xe9K\xd4'
print(Hash().update(b'\x00'*4+bytes.fromhex("db6cbf0b")*20).digest())
# b'f\xe9K\xd4'
Now it’s easy to get the flag :
from pwn import *
conn = remote("challenges1.france-cybersecurity-challenge.fr", 6001)
for i in range(64):
conn.recvuntil(":")
conn.sendline("00"*4+"db6cbf0b"*i)
conn.interactive()
FCSC{b400aabf21470544850632fb99c4fd06df6b69c07fd02fc2ef685a71b57afd99}
Revaulting#
Play on HackropoleDifficulty :
Points : 500
Solves : ?
Description :
We are being told that this online safe is not secure enough. Can you prove it by accessing its contents?
As this is also a reverse engineering challenge, only the service’s binary is provided and not the sources.
The service allows you to create tokens and login with them :
What do you want to do?
[1] Create user token
[2] Log in with token
>>> 1
Enter your login:
>>> test
Here is your token:
F7IVcG5yPEnqrgbzubdV4ALrzps7+5upG4J+knKEez/HTAiB3gOIj6uTXY+/esuVaqyOGC3X53QOo3t1n7a0mg==
What do you want to do?
[1] Create user token
[2] Log in with token
>>> 2
Enter your login:
>>> test
Enter your token:
>>> F7IVcG5yPEnqrgbzubdV4ALrzps7+5upG4J+knKEez/HTAiB3gOIj6uTXY+/esuVaqyOGC3X53QOo3t1n7a0mg==
Welcome back, test!
What do you want to do?
[1] Create user token
[2] Log in with token
>>> 1
Enter your login:
>>> admin
Error: You cannot request an admin token. Bye bye.
The aim of the challenge is to login as “admin”, but the server refuse to create such a token.
Patching the binary locally so that it creates an “admin” token is easy, but tokens are only valid for the same session.
We have to understand what is going on.
Reverse engineering
This step was painful and slow. The binary is a stripped Position Independent Executable (PIE), making use of Bignums.
Static analysis of Bignum functions is mission impossible, dynamic analysis of stripped PIE is not so fun either. After 2 days of reverse engineering, I almost got everything figured out, but some things stayed a mystery.
Here is a picture of the start of the main function after having cleaned it up :
See those weird numbers at the start ? At this point I still didn’t know what they meant, I saw that some of them were prime, but nothing else. I decided to google the first one (which I should have done right away !) and that’s when it all made sense.
That’s FRP256v1’s modulus ! I felt dumb for loosing 2 days when this step could have been done in a matter of hours…
Now that I understand we are dealing with curve points, looking at the getToken function made more sense:
This is simply an ECDSA signature !
So the decodeToken function is an ECDSA signature verification:
To summerize what the service is doing:
- It generates a random 256-bit number : the server’s private key;
- It uses this private key to compute the server’s public key;
- When the user requests a token, the SHA256 hash of the username is computed;
- This hash is used for the ECDSA signature creation process;
- The ECDSA nonce is the MD5 hash of a huge random number, repeated twice (to be 256-bit long);
- The resulting token, is the ECDSA signature encoded in Base64;
- When the user asks to login with a token, the signature is verified with the server’s public key.
The server’s public key is never given to us.
The exploit
The ECDSA signature is correctly implemented, but the construction of the nonce is bad. It is clear that the nonce has only 128 bits of entropy instead of 256. It is also well known that ECDSA signature greatly suffers from weak nonce generation.
This stackexchange answer explains well how we can recover the private key using partial knowledge of the nonce’s LSB (or MSB).
In our case, we do not know the nonce’s LSB (or MSB), but we do know that both halves of the nonce $k$ are the same. This should allow us to rewrite :
$$ \begin{split}k &= b + b2^l \\ &= b(2^l + 1)\end{split}$$
with $l = 128$ and $b$ an unknown small value (compared to the order $q$ of the curve). This is almost the same scenario as when half of the LSB are 0.
We can construct the same lattice as for biased nonces, but with a small adaptation :
def make_matrix(rsh):
# rsh is a list of tuple : [(r1, s1, h1), (r2, s2, h2), ...]
m = len(rsh)
tm = 0
um = 0
# Matrix size
matrix = Matrix(QQ, m + 2, m + 2)
# Fill diagonal with order
for i in range(0, m):
matrix[i, i] = q * (2 ** 128 + 1)
# Add last row of Ti and Ui
for i in range(0, m):
r, s, h = rsh[i]
# Ti = r*(s*2**l)^-1
x0 = (r * inverse_mod(s * (2 ** 128 + 1), q)) * (2 ** 128 + 1)
x0 -= tm
# Ui = h * (s*2**l)^-1
x1 = (h * inverse_mod(s * (2 ** 128 + 1), q)) * (2 ** 128 + 1)
x1 -= um
matrix[m + 0, i] = x0
matrix[m + 1, i] = x1
# Add sentinel values CT and CU
CU = q
CT = 1
matrix[m + 0, i + 1] = CT
matrix[m + 0, i + 2] = 0
matrix[m + 1, i + 1] = 0
matrix[m + 1, i + 2] = CU
return matrix
The service allows us to request 30 tokens before asking to login. With a 128-bit nonce bias, this should be enough to recover the private key, but before, we need to obtain the public key.
The public key can be recomputed from a single ECDSA signature $(r, s)$ and the curve parameters $(a, b, p)$. Actually, this will produce two public keys as $(x, y)$ and $(x, -y)$ are both valid points that could have produced $r$ :
# recover pulic key
r, s = rsh[0][:2]
y1 = sage.all.mod(r ** 3 + a * r + b, p).sqrt()
y2 = -y1
R1 = E(r, y1)
R2 = E(r, y2)
r_inv = int(inverse_mod(r, q))
h = rsh[0][2]
# recover the two possible public keys
k1 = r_inv*(s*R1 - h*G)
k2 = r_inv*(s*R2 - h*G)
We have all we need to perform the attack. We gather 30 signatures, construct the matrix and apply the LLL algorithm. The private key should appear in the resulting matrix. If not, the nonces may appear, which would allow to recover the private key :
def ecdsaBiasedNonce(modulus, curveParams, Gxy, Axy, A2xy, rsh):
from sage.all import EllipticCurve, GF, Matrix, QQ, inverse_mod
E = EllipticCurve(GF(modulus), curveParams)
G = E(Gxy)
# public keys
A = E(Axy)
A2 = E(A2xy)
order = G.order()
# lattice reduction
matrix = make_matrix(rsh)
new_matrix = matrix.LLL()
# try to recover private key directly
key = None
for row in new_matrix:
if row[-1] == order:
key = int(row[-2]) % order
if key is not None and (key*G == A or key*G == A2):
return key
# search for the nonce values, sometimes the private key is not found directly but the nonce is.
keys = []
for row in new_matrix:
potential_nonce_1 = row[0]
try:
potential_priv_key = inverse_mod(rsh[0][0], order) * ((potential_nonce_1 * rsh[0][1]) - rsh[0][2])
key = potential_priv_key % order
if key not in keys:
keys.append(key)
except Exception as e:
pass
for k in keys:
if k*G == A or k*G == A2:
return k
Once the private key is recovered, we can use it to sign a token for the user “admin” and get the flag :
import base64
from sage.all import *
from pwn import *
import hashlib
from Crypto.Util.number import long_to_bytes as ntos
# FRP256v1
p = 0xF1FD178C0B3AD58F10126DE8CE42435B3961ADBCABC8CA6DE8FCF353D86E9C03
a = 0xF1FD178C0B3AD58F10126DE8CE42435B3961ADBCABC8CA6DE8FCF353D86E9C00
b = 0xEE353FCA5428A9300D4ABA754A44C00FDFEC0C9AE4B1A1803075ED967B7BB73F
E = EllipticCurve(GF(p), [a, b])
# générateur
Gx = 0xB6B3D4C356C139EB31183D4749D423958C27D2DCAF98B70164C97A2DD98F5CFF
Gy = 0x6142E0F7C8B204911F9271F0F3ECEF8C2701C307E8E4C9E183115A1554062CFB
G = E(Gx, Gy)
# ordre
q = 0xF1FD178C0B3AD58F10126DE8CE42435B53DC67E140D2BF941FFDD459C6D655E1
def getToken(user):
conn.sendline("1")
conn.recvuntil(">>> ")
conn.sendline(user)
conn.recvline()
token = conn.recvline()
conn.recvuntil(">>> ")
return token
def signM(m, d):
k = int(hashlib.sha256(m).hexdigest(), 16)
r = int((k*G).xy()[0])
h = int(hashlib.sha256(m).hexdigest(), 16) % q
s = int((h+r*d)*inverse_mod(k, q))%q
return r, s, h
conn = remote("challenges1.france-cybersecurity-challenge.fr", 6003)
conn.recvuntil(">>> ")
# gather 30 signatures
rsh = []
for i in range(20, 20+30):
t = base64.b64decode(getToken(bytes([i])))
r = int(t[:32].hex(), 16)
s = int(t[32:].hex(), 16)
h = int(hashlib.sha256(bytes([i])).hexdigest(), 16) % q
rsh.append((r, s, h))
# recover public key
r, s = rsh[0][:2]
y1 = sage.all.mod(r ** 3 + a * r + b, p).sqrt()
y2 = -y1
R1 = E(r, y1)
R2 = E(r, y2)
r_inv = int(inverse_mod(r, q))
h = rsh[0][2]
# recover the two possible public keys
k1 = r_inv*(s*R1 - h*G)
k2 = r_inv*(s*R2 - h*G)
# recover private key
d = ecdsaBiasedNonce(p, [a, b], G.xy(), k1.xy(), k2.xy(), rsh)
# get the flag
if d is not None:
r, s, _ = signM(b"admin", d)
token = base64.b64encode(ntos(r)+ntos(s))
conn.sendline("2")
conn.recvuntil(">>> ")
conn.sendline("admin")
conn.recvuntil(">>> ")
conn.sendline(token)
conn.recvuntil(">>> ")
conn.sendline("3")
flag = conn.recvline()
print(flag)
conn.close()
FCSC{35f56b385f739dfe47da9aa0c7a9aed1d1721086e3a420e8d210d761f995159b}
SmeaLog#
Play on HackropoleDifficulty :
Points : 500
Solves : 8
Description :
Can you solve this discrete logarithm?
We were given the following output file :
E = Elliptic Curve defined by y^2 = x^3 + 4692450611853470576530915318823703839138750803615*x + 5114351683655764329253106245428582084587536640503 over Ring of integers modulo 6801613388087663669990064996614506238369534296081
P = (4818298608029665051393880712825109209819975611403 : 3354976854279375487312341201850051023143236550702 : 1)
s*P = (6276672712837100206846077340854087747993984369352 : 5153262096245606021857753027994479500306746041453 : 1)
iv = 0564fc638153e8b1ef1b7b5f52c539cc
c = a808e9122d2e0f398bec32a8864d7352fe0bd1d3d6690ba52d2c5bad92fecd2cebab044f312a951aa5bdc1a23f7a925a89c38901e4b546e3a065b6cb57975efb5e2c874273f050d214e178deef8dbc3a
And the following source code:
import os
from hashlib import sha256
from Crypto.Cipher import AES
from secret import FLAG
def gen_curve(bits = 40, k = 4):
assert bits*k >= 160, "Error: p**k must be at least 160 bits."
p = random_prime(2 ** (bits + 1) - 1, lbound = 2 ** bits)
R = Zmod(p**k)
while True:
a, b = R.random_element(), R.random_element()
d = 4 * a ** 3 + 27 * b ** 2
if d.is_unit():
E = EllipticCurve(R, [a, b])
E_ = EllipticCurve(GF(p), [a, b])
if E_.order().is_prime():
return E
def gen_random_point(E):
R = E.base_ring()
a, b = E.a4(), E.a6()
while True:
x = R.random_element()
t = x ** 3 + a * x + b
if is_square(t):
y = choice([-1, 1]) * sqrt(t)
return E([x, y])
def gen_pair(E):
N = E.base_ring().characteristic()
s = ZZ.random_element(N)
P = gen_random_point(E)
return P, s
def encrypt(s):
k = sha256(str(s).encode()).digest()
iv = os.urandom(16)
c = AES.new(k, AES.MODE_CBC, iv).encrypt(FLAG)
return iv, c
E = gen_curve()
print(f"E = {E}")
P, s = gen_pair(E)
print(f"P = {P}")
print(f"s*P = {s * P}")
iv, c = encrypt(s)
print(f"iv = {iv.hex()}")
print(f"c = {c.hex()}")
We are asked to solve the ECDLP on a ring of integers modulo a prime power. This shouldn’t be too difficult right ?
From the challenge description we have :
p = 1614927334829
k = 4
a = 4692450611853470576530915318823703839138750803615
b = 5114351683655764329253106245428582084587536640503
E = EllipticCurve(Zmod(p**k), [a, b])
E_ = EllipticCurve(GF(p), [a, b])
P = E(4818298608029665051393880712825109209819975611403, 3354976854279375487312341201850051023143236550702)
Q = E(6276672712837100206846077340854087747993984369352, 5153262096245606021857753027994479500306746041453)
By doing some tests, it is easy to see that $E \rightarrow E\_$ is a canonical projection (I didn’t know this term before writing this) :
s = 111111111111111111111111111111111111111111111111111
R = P*s
P_ = E_(P.xy())
R_ = P_ * s
assert R_ == E_(R.xy())
This means, we can solve the ECDLP on $E\_$ instead, but the order $q\_$ of $E\_$ is only :
q_ = E_.order()
q_
# 1614926806643
if we solve the ECDLP on $E\_$, we will find $s \mod q\_$:
s_ = discrete_log(R_, P_, operation='+')
assert s_ == s % q_
discrete_log(Q_, P_, operation='+')
# 1330461465055
This is good, but not enough.
The next thing to do is find the order of $E$.
Finding the order of the curve
Sage can’t answer this question sadly.
I found it for curves over smaller rings by brute force and found out that it is always $q = q\_ * p^{k-1}$ :
P * (q_ * p**3)
# (0 : 1 : 0)
This was also confirmed when I found this paper later (Lemma 13).
Solving the ECDLP
We already have solved the ECDLP modulo $q\_$ using $E\_$. But we can’t solve it modulo $p^3$ on $E$ because we can’t multiply any point by $q\_$ as some inverses do not exist in this ring :
P * q_
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call last)
...
ZeroDivisionError: Inverse of 760382977411273368060224531891894701675880351771 does not exist (characteristic = 6801613388087663669990064996614506238369534296081 = 1614927334829*4211714819235422071841592904178204789)
assert 760382977411273368060224531891894701675880351771 % p == 0
That’s where I got stuck for a while, before finding the paper linked above after hours of googling.
The answer to our problem is given in proposition 19 :
- $E_{A,B}(\mathbb{Z}/p^e\mathbb{Z})$ is our curve $E$;
- $E_{A,B}(\mathbb{F}_p)$ is our curve $E\_$;
- $\mathbb{Z}/p^{e-1}\mathbb{Z}$ is the ring of integers modulo $p^3$;
- $P$ is our point $P$ on $E$;
- $\pi$ is defined in the paper as the canonical projection $E \rightarrow E\_$;
- $\pi(P)$ is thus our point $P\_$ on $E\_$;
- $q$ is the order of $E\_$, which we have called $q\_$;
The hard part was understanding the right side of the tuple. it says to divide the x and y coordinates of $q\_*P$, but as we saw earlier, Sage refuses to perform the multiplication because we cannot divide by a multiple of $p$.
Homogenuous coordinates
The coordinates of an EC point in sage are always represented by 3 coordinates $(x, y, z)$, with $z = 1$. That’s because the point is represented in affine coordinates. In homogeneous coordinates (or projective coordinates), we defer the divisions of the addition formula by multiplying them into a denominator. The denominator is represented by a new coordinate. Only at the very end do we perform a single division to convert from projective coordinates back to affine coordinates :
$$ (x, y, z) \rightarrow (\frac{x}{z}, \frac{y}{z}, 1)$$
I wrote a function that performs the addition of two points given in affine coordinates and returns the result in projective coordinates :
def projectiveAdd(A, B):
t0 = A[1]
t1 = B[1]
u0 = A[0]
u1 = B[0]
t = t0 - t1
u = u0 - u1
u2 = u * u
w = t * t - u2 * (u0 + u1)
u3 = u * u2
rx = u * w
ry = t * (u0 * u2 - w) - t0 * u3
rz = u3
return rx, ry, rz
Now we can compute $q\_*P$:
x, y, z = projectiveAdd(P*(q_-1), P)
x, y, z
# (4276438851576022122535265285550574021585027887743, 4000347389106578613918355849949257566366146636154, 4982894687970550317551718990447945942865561414241)
And we can perform the final mapping :
int(x/y)/p
# 476541879624199886450264142848291748
We now have converted our point $P$ into an element of $\mathbb{Z}/p^3\mathbb{Z}$, let’s call it $P\_\_$. We can do the same for the point $Q$.
Since $Q = s*P$, we have $Q\_\_ = s*P\_\_$ and so we can recover $s \mod p^3$ by simply multiplying $Q\_\_$ with the invert of $P\_\_$:
def map(P):
# can't multiply by q_ directly
A = P*(q_-1)
qP = projectiveAdd(A.xy(), P.xy())
return int(qP[0]/qP[1])/p
map(Q)/map(P) % p**3
1330777078199761105051498230654082901
Combining the partial solutions
We have found :
$$ \begin{cases} s = 1330777078199761105051498230654082901 \mod p^3 \\ s = 1330461465055 \mod q\_ \end{cases}$$
We just have to use the Chinese remainder theorem to reconstruct $s \mod (q\_ * p^3) = s \mod q$:
s = crt([1330461465055, 1330777078199761105051498230654082901], [q_, p**3])
assert Q == P*s
Now we can decrypt the flag :
from hashlib import sha256
from Crypto.Cipher import AES
k = sha256(str(s).encode()).digest()
iv = bytes.fromhex("0564fc638153e8b1ef1b7b5f52c539cc")
c = bytes.fromhex("a808e9122d2e0f398bec32a8864d7352fe0bd1d3d6690ba52d2c5bad92fecd2cebab044f312a951aa5bdc1a23f7a925a89c38901e4b546e3a065b6cb57975efb5e2c874273f050d214e178deef8dbc3a")
print(AES.new(k, AES.MODE_CBC, iv).decrypt(c))
FCSC{b761f352662f739c2a91e92db5af5f7a4e7a3466d0e594eda07eea4046fb6658}
Trappy Skippy#
Play on HackropoleDifficulty :
Points : 500
Solves : ?
Description :
Skippy the great guru challenges you to decrypt his flag.
We were given the following data in separate files :
# skippy.txt
p1 = b'Tout bien que tu d\xc3\xa9tiens est un souci qui te retient,\net Skippy est l\xc3\xa0 pour nous enlever tout nos soucis !\n'
# skippy.txt.enc
c1 = b"\x16\xcb\x13p9f\$\r\xac\x80L\xecD\x93Z4\$*\x98(\x19m\x01I\xc8\xeb\x8d\xa1y\x0b\xb3\x9b\xa5\xb7\xd4\x8e\xe8\x8e\xdds,wx\xc3?\xbc\x1d\x05s\r\x99\xacd\xf1\x90,E'\xa9S\xd0\x18\xa9\xb9\xedX\x89\x1a23i\xc7\x08\x92*T\x0b\xbf\xe2\xb3\x8a\xef\x9a\x16\x07)s\xd2P\x84<\xc8\xf5\xbd\x07\x8b@P\xeey,9y&\xc5\xde\xfaP\xef\xdei\x93"
# flag.txt.enc
c2 = b'\xeb\x83\tG\xb8M\xcb\xa9o\xf8\x01\xb9\xca\x17\x87(\xf6\xbfm\xfd\xe4ub\xf7\xf6\xd7W?\x85\x88\x9e2\xc3\x98\xea\xbf\x0c\x9b\x97\xf5\x87\xd1\x9a\x12\xf2\xf6\\\xf2\xe5\xf4\x12\xf7\x80\x94\x02\x17K(\xa7\x981u\x1b\xad\xdc\xce\xad\xd8\xac\xad\xbf\xa5'
And the following source code :
import os
class Skippy:
Sbox = [
0x81, 0x3f, 0xab, 0x3d, 0xa4, 0xb4, 0x31, 0x9e,
0xba, 0xee, 0x90, 0xec, 0x9f, 0x50, 0x85, 0x62,
0xb8, 0xde, 0xa2, 0xf4, 0x08, 0x78, 0x0a, 0xc5,
0xb3, 0x15, 0xa9, 0x27, 0x96, 0xac, 0x33, 0x11,
0xa0, 0xdc, 0x05, 0x7b, 0xaf, 0xdd, 0xad, 0x7a,
0x14, 0x9a, 0xb1, 0xaa, 0x29, 0x3b, 0x03, 0x23,
0x99, 0x82, 0x3c, 0x98, 0x2b, 0x13, 0xa6, 0x21,
0x2d, 0x63, 0x88, 0x51, 0x10, 0xc7, 0x9d, 0xf5,
0x4c, 0x58, 0xf3, 0xd5, 0x65, 0x06, 0xc0, 0x91,
0x5c, 0xd0, 0x76, 0xfa, 0xe6, 0x1a, 0xfc, 0x2a,
0x5e, 0x6f, 0xd3, 0xf8, 0x6b, 0x97, 0x59, 0x18,
0xf1, 0x68, 0xc3, 0x6a, 0xe8, 0x2e, 0x4d, 0x1c,
0xd1, 0x5f, 0x44, 0x47, 0xcc, 0x00, 0xe4, 0xbf,
0x7e, 0xcf, 0xe9, 0xcd, 0x7f, 0x04, 0x55, 0x89,
0x7c, 0x40, 0xdb, 0x5a, 0x7d, 0x34, 0x67, 0x2c,
0xe3, 0x5d, 0x46, 0xe2, 0xfe, 0x02, 0x69, 0x32,
0x52, 0x87, 0xf7, 0x20, 0x79, 0x1d, 0x4b, 0x1f,
0x09, 0x8e, 0x39, 0x1b, 0xa8, 0x0e, 0x0f, 0x0c,
0xae, 0xbe, 0x0b, 0x19, 0x0d, 0x83, 0xb0, 0x26,
0x48, 0x22, 0xef, 0x12, 0x49, 0x37, 0xf6, 0x92,
0xb6, 0x94, 0x86, 0x01, 0x25, 0x3e, 0x17, 0x24,
0xed, 0xb7, 0x60, 0xb5, 0x61, 0x35, 0xc6, 0x2f,
0xdf, 0x3a, 0x4a, 0x38, 0x53, 0x8a, 0xc4, 0x07,
0x84, 0xbc, 0x9c, 0x8c, 0xb2, 0x16, 0x80, 0x9b,
0xbd, 0x71, 0x30, 0x73, 0xca, 0xe1, 0x75, 0x74,
0xbb, 0xf0, 0x36, 0xea, 0xfd, 0x4e, 0xff, 0x64,
0x8b, 0x4f, 0x1e, 0xc2, 0x70, 0x56, 0x72, 0x54,
0xa5, 0xd6, 0xa7, 0xd4, 0x6d, 0xc9, 0x45, 0xf9,
0xa3, 0xd8, 0xa1, 0xda, 0xd7, 0xeb, 0xe7, 0xd9,
0x28, 0x41, 0x8d, 0x5b, 0xe0, 0xfb, 0xc8, 0x6e,
0x95, 0xce, 0x8f, 0x43, 0xd2, 0xcb, 0x77, 0x6c,
0xb9, 0xf2, 0x93, 0x57, 0xe5, 0xc1, 0x42, 0x66,
]
def __init__(self, key):
self._key = key + key[:2]
def _g(self, k, w):
g1 = w >> 8
g2 = w & 0xff
g3 = self.Sbox[g2 ^ self._key[(4 * k + 0) % 10]] ^ g1
g4 = self.Sbox[g3 ^ self._key[(4 * k + 1) % 10]] ^ g2
g5 = self.Sbox[g4 ^ self._key[(4 * k + 2) % 10]] ^ g3
g6 = self.Sbox[g5 ^ self._key[(4 * k + 3) % 10]] ^ g4
return (g5 << 8) ^ g6
def _skip(self, b):
w1 = (b[0] << 8) ^ b[1]
w2 = (b[2] << 8) ^ b[3]
w3 = (b[4] << 8) ^ b[5]
w4 = (b[6] << 8) ^ b[7]
k = 0
for t in range(2):
for i in range(8):
gw1 = self._g(k, w1)
w1, w2, w3, w4 = gw1 ^ w4 ^ (k + 1), gw1, w2, w3
k += 1
for i in range(8):
gw1 = self._g(k, w1)
w1, w2, w3, w4 = w4, gw1, w1 ^ w2 ^ (k + 1), w3
k += 1
return bytes([
w1 >> 8, w1 & 0xff,
w2 >> 8, w2 & 0xff,
w3 >> 8, w3 & 0xff,
w4 >> 8, w4 & 0xff,
])
def encrypt(self, m):
if len(m) % 8:
m += b"\x00" * (8 - len(m) % 8)
return b"".join(self._skip(m[i:i+8]) for i in range(0, len(m), 8))
k = os.urandom(8)
gourou = Skippy(k)
m = open("skippy.txt", "rb").read()
c = gourou.encrypt(m)
open("skippy.txt.enc", "wb").write(c)
m = open("flag.txt", "rb").read()
c = gourou.encrypt(m)
open("flag.txt.enc", "wb").write(c)
The first thing I tried is googling the first line of the S-box. If it’s an existing cipher, this should reveal which one. Sadly, there was no result. Either this is a completely custom encryption scheme or the S-box is custom. The latter seemed more resonable.
Because I had no clue Skippy is a reference to this, I searched for ciphers named “Skippy” and I found one. I noticed that it was very similar to the one of the challenge. It is based on SKIPJACK, so I search for the specification. This is exaclty was we have here, except the S-box is custom.
Because we do not have the decrypt function, I wrote it myself :
def ginv(self, k, w):
g5 = w >> 8
g6 = w & 0xff
g4 = self.Sbox[g5 ^ self._key[(4 * k + 3) % 10]] ^ g6
g3 = self.Sbox[g4 ^ self._key[(4 * k + 2) % 10]] ^ g5
g2 = self.Sbox[g3 ^ self._key[(4 * k + 1) % 10]] ^ g4
g1 = self.Sbox[g2 ^ self._key[(4 * k + 0) % 10]] ^ g3
return (g1 << 8) ^ g2
def skipinv(self, b):
w1 = (b[0] << 8) ^ b[1]
w2 = (b[2] << 8) ^ b[3]
w3 = (b[4] << 8) ^ b[5]
w4 = (b[6] << 8) ^ b[7]
k = 32
for t in range(2):
for i in range(8):
gw2 = self.ginv(k - 1, w2)
w1, w2, w3, w4 = gw2, gw2 ^ w3 ^ (k), w4, w1
k -= 1
for i in range(8):
gw2 = self.ginv(k - 1, w2)
w1, w2, w3, w4 = gw2, w3, w4, w1 ^ w2 ^ (k)
k -= 1
return bytes([
w1 >> 8, w1 & 0xff,
w2 >> 8, w2 & 0xff,
w3 >> 8, w3 & 0xff,
w4 >> 8, w4 & 0xff,
])
def decrypt(self, m):
return b"".join(self.skipinv(m[i:i + 8]) for i in range(0, len(m), 8))
Searching for a vulnerability
The original SKIPJACK cipher has been partially broken using impossible differencial cryptanalysis. This however seems not applicable in our case as we only have 14 known plaintext/ciphertext pairs.
More generally, because we can’t have chosen plaintexts, attacks based on differential cryptanalysis seemed not applicable. Linear cryptanalysis however, seemed more promising as we have known plaintexts, but generaly we would need way more than 14 pairs. This also seemed like a dead-end, but I decided to give it a try.
Linear cryptanalysis
We are interested in the linear characteristics of the only non-linear component of the cipher, the S-box (F-table in SKIPJACK).
We can compute a linear approximation table (LAT), which will show the linear dependency between the input of the S-box and the outputs :
from sage.crypto.sbox import SBox
s = SBox(SKippy([]).Sbox)
LAT = s.linear_approximation_table()
Because this representation is not very telling, we usually represent it as a picture. In this tutorial they call it a “Jackson Pollock representation”, but there does not seem to be an official name :
def save_pollock(mat,
color_scheme="CMRmap_r",
file_name="pollock",
vmin=0,
vmax=20,
folder=None,
frame=True,
visible_axes=True,
colorbar=True,
file_type="png"):
import matplotlib.pyplot as plt
fig, p = plt.subplots(figsize=(15,15))
if isinstance(mat, list):
abs_mat = [[abs(mat[i][j]) for j in xrange(0, len(mat[0]))]
for i in xrange(0, len(mat))]
else:
abs_mat = [[abs(mat[i][j]) for j in xrange(0, mat.ncols())]
for i in xrange(0, mat.nrows())]
axes = p.imshow(
abs_mat,
interpolation="none",
cmap=plt.cm.get_cmap(color_scheme, 100),
vmin=vmin,
vmax=vmax,
)
if colorbar:
fig.colorbar(axes, orientation='vertical', fraction=0.046, pad=0.04)
p.set_aspect('equal')
p.get_xaxis().set_visible(visible_axes)
p.get_yaxis().set_visible(visible_axes)
p.patch.set_alpha(0)
p.set_frame_on(frame)
if folder == None:
name_base = "{}."+file_type
else:
name_base = folder + "/{}." + file_type
fig.savefig(name_base.format(file_name))
Using this representation for the LAT of our S-box yields this :
The left picture is our S-box, whereas the right picture is the original F-table.
We can clearly see the white stripes indicating a linear bias.
I extracted all the linear relations form the LAT and kept only those which affected the same bits for the input and output, because it seemed easier to track the propagation this way. Let’s note $X_i$ the bit $i$ of the input and $Y_i$ the bit $i$ of the S-box output, starting at 0. We have the following useful relations :
$$ \begin{cases} X_1 \oplus Y_1 = 1 & with\ proba\ 0.25 \\ X_0 \oplus X_5 \oplus Y_0 \oplus Y_5 = 1 & with\ proba\ 0.75 \\ X_0 \oplus X_1 \oplus X_5 \oplus Y_0 \oplus Y_1 \oplus Y_5 = 1 & with\ proba\ 0.75 \\ X_1 \oplus X_5 \oplus X_7 \oplus Y_1 \oplus Y_5 \oplus Y_7 = 1 & with\ proba\ 0.75\end{cases}$$
There are more, but those seemed more useful than the others. There is no relation with a probability greater than 0.75 (or under 0.25). This is a problem as this probability will decrease for each additional round that we want to approximate, and there are 32 of them.
I used those relations to deduce relations for the _g function. For example I got those relations :
$$\begin{cases}X_9 \oplus Y_1 = 0 & with\ proba\ 0.625\ (or\ 0.375) \\ X_1 \oplus Y_9 = 0 & with\ proba\ 0.5625\ (or\ 0.4375)\end{cases}$$
The above probabilities depend on the value of the key, but as the key is fixed, they do not change from one encryption to the other.
Using the above relations, I tried to approximate 5 rounds of the cipher, but at this point the probabilities were already too low to be noticed experimentally.
This confirmed that linear cryptanalysis is a dead end. From what I read online, it seems that linear cryptanalysis is not a good approach against unbalanced feistel networks, which SKIPJACK is.
I reverted to differential cryptanalysis.
Differential cryptanalysis
Just like before, we are interested in the properties of the S-box. This time we compute a Difference Distribution Table (DDT) :
from sage.crypto.sbox import SBox
s = SBox(SKippy([]).Sbox)
DDT = s.difference_distribution_table()
Once again, here is the comparaison with the original F-table:
The black dots indicate a strong relation between the difference in the input bits and the difference in the output bits. Because this time I didn’t want to build relations starting from the S-box until the final round of the cipher, I decided to search for relations between the plaintext and ciphertext experimentally :
from Crypto.Util.strxor import strxor
def getDiff(j):
k = os.urandom(8)
s = Skippy(k)
m = os.urandom(8)
c = s.encrypt(m)
m2 = strxor(m, bytes([j]*8))
c2 = s.encrypt(m2)
return strxor(c, c2)
for j in range(1, 256):
COUNT = [0]*64
N = 100
for _ in range(N):
d = getDiff(j)
d = bin(int(d.hex(), 16))[2:].rjust(64, "0")
for i in range(64):
COUNT[i] += int(d[i])
# only show relations that do not affect a bit
if 0 in COUNT:
print(f"{j} : {COUNT}")
Which gave some results :
2 : [44, 0, 49, 51, 52, 44, 50, 44, 49, 0, 42, 50, 45, 49, 45, 49, 40, 0, 50, 52, 56, 40, 51, 40, 54, 0, 51, 44, 51, 54, 47, 54, 48, 0, 53, 51, 54, 48, 42, 48, 57, 0, 46, 51, 50, 57, 54, 57, 49, 0, 53, 49, 45, 49, 47, 49, 50, 0, 45, 51, 50, 50, 41, 50]
24 : [51, 0, 46, 49, 48, 51, 44, 51, 46, 0, 45, 53, 48, 46, 53, 46, 47, 0, 52, 57, 46, 47, 48, 47, 54, 0, 54, 49, 53, 54, 47, 54, 52, 0, 47, 53, 50, 52, 52, 52, 41, 0, 54, 50, 53, 41, 49, 41, 56, 0, 49, 53, 50, 56, 56, 56, 52, 0, 51, 48, 47, 52, 51, 52]
26 : [48, 0, 49, 57, 50, 48, 46, 48, 51, 0, 47, 58, 46, 51, 45, 51, 44, 0, 52, 53, 51, 44, 59, 44, 37, 0, 51, 52, 54, 37, 53, 37, 49, 0, 43, 45, 51, 49, 50, 49, 46, 0, 53, 53, 56, 46, 37, 46, 41, 0, 45, 58, 50, 41, 39, 41, 61, 0, 52, 43, 36, 61, 54, 61]
40 : [46, 0, 36, 49, 57, 46, 47, 46, 45, 0, 52, 56, 53, 45, 52, 45, 51, 0, 43, 51, 57, 51, 43, 51, 48, 0, 52, 54, 46, 48, 55, 48, 43, 0, 52, 41, 54, 43, 39, 43, 46, 0, 52, 47, 49, 46, 50, 46, 46, 0, 49, 62, 55, 46, 53, 46, 52, 0, 43, 40, 53, 52, 48, 52]
42 : [57, 0, 45, 49, 47, 57, 54, 57, 46, 0, 54, 40, 48, 46, 51, 46, 53, 0, 50, 53, 52, 53, 47, 53, 60, 0, 43, 41, 54, 60, 53, 60, 47, 0, 46, 56, 49, 47, 55, 47, 48, 0, 39, 48, 43, 48, 44, 48, 51, 0, 58, 47, 50, 51, 50, 51, 43, 0, 53, 58, 54, 43, 55, 43]
48 : [49, 0, 54, 55, 54, 49, 56, 49, 49, 0, 43, 45, 61, 49, 51, 49, 56, 0, 53, 54, 51, 56, 53, 56, 52, 0, 46, 58, 52, 52, 43, 52, 44, 0, 54, 56, 58, 44, 45, 44, 49, 0, 45, 43, 51, 49, 56, 49, 48, 0, 52, 48, 48, 48, 51, 48, 52, 0, 58, 49, 41, 52, 55, 52]
50 : [52, 0, 50, 54, 54, 52, 48, 52, 51, 0, 59, 47, 49, 51, 45, 51, 53, 0, 42, 51, 48, 53, 45, 53, 52, 0, 55, 57, 44, 52, 57, 52, 51, 0, 50, 45, 56, 51, 57, 51, 53, 0, 47, 45, 57, 53, 48, 53, 44, 0, 54, 50, 52, 44, 54, 44, 55, 0, 46, 47, 54, 55, 46, 55]
141 : [55, 0, 52, 52, 49, 55, 53, 55, 61, 0, 44, 45, 54, 61, 46, 61, 52, 0, 46, 48, 48, 52, 52, 52, 50, 0, 48, 55, 53, 50, 56, 50, 61, 0, 47, 41, 55, 61, 53, 61, 41, 0, 52, 53, 48, 41, 49, 41, 51, 0, 44, 55, 48, 51, 59, 51, 55, 0, 47, 50, 52, 55, 61, 55]
143 : [54, 0, 41, 50, 45, 54, 47, 54, 58, 0, 48, 51, 57, 58, 42, 58, 57, 0, 56, 56, 55, 57, 50, 57, 57, 0, 52, 51, 50, 57, 43, 57, 46, 0, 51, 55, 40, 46, 42, 46, 47, 0, 49, 56, 52, 47, 45, 47, 51, 0, 47, 50, 46, 51, 51, 51, 36, 0, 52, 54, 50, 36, 47, 36]
149 : [52, 0, 44, 50, 56, 52, 40, 52, 50, 0, 44, 44, 62, 50, 50, 50, 48, 0, 51, 45, 48, 48, 42, 48, 50, 0, 56, 39, 55, 50, 47, 50, 49, 0, 52, 57, 50, 49, 51, 49, 50, 0, 45, 60, 51, 50, 52, 50, 54, 0, 51, 47, 42, 54, 55, 54, 44, 0, 51, 52, 53, 44, 51, 44]
151 : [39, 0, 44, 48, 41, 39, 50, 39, 56, 0, 44, 44, 44, 56, 51, 56, 46, 0, 58, 55, 55, 46, 53, 46, 51, 0, 48, 42, 51, 51, 59, 51, 44, 0, 50, 44, 48, 44, 45, 44, 53, 0, 44, 46, 49, 53, 48, 53, 56, 0, 45, 44, 59, 56, 52, 56, 40, 0, 60, 47, 53, 40, 41, 40]
165 : [54, 0, 46, 50, 48, 54, 50, 54, 50, 0, 49, 51, 50, 50, 54, 50, 46, 0, 40, 54, 52, 46, 53, 46, 57, 0, 50, 55, 46, 57, 57, 57, 51, 0, 49, 42, 48, 51, 48, 51, 51, 0, 54, 48, 57, 51, 48, 51, 53, 0, 57, 50, 38, 53, 48, 53, 51, 0, 46, 56, 55, 51, 51, 51]
167 : [49, 0, 45, 49, 49, 49, 46, 49, 47, 0, 39, 45, 51, 47, 54, 47, 44, 0, 55, 52, 55, 44, 45, 44, 61, 0, 49, 56, 48, 61, 53, 61, 50, 0, 53, 45, 50, 50, 47, 50, 57, 0, 54, 42, 57, 57, 51, 57, 43, 0, 49, 44, 56, 43, 49, 43, 48, 0, 43, 47, 56, 48, 53, 48]
189 : [46, 0, 54, 51, 45, 46, 49, 46, 49, 0, 52, 56, 49, 49, 58, 49, 53, 0, 45, 58, 50, 53, 51, 53, 49, 0, 47, 42, 46, 49, 48, 49, 51, 0, 45, 46, 52, 51, 53, 51, 53, 0, 50, 46, 57, 53, 55, 53, 50, 0, 49, 50, 55, 50, 52, 50, 49, 0, 53, 52, 62, 49, 46, 49]
191 : [57, 0, 46, 49, 56, 57, 42, 57, 56, 0, 56, 61, 53, 56, 43, 56, 42, 0, 48, 54, 48, 42, 48, 42, 54, 0, 52, 54, 54, 54, 56, 54, 53, 0, 49, 48, 44, 53, 48, 53, 52, 0, 48, 51, 47, 52, 50, 52, 51, 0, 44, 48, 51, 51, 46, 51, 44, 0, 47, 61, 44, 44, 57, 44]
What this means is that if we XOR any input byte with a value from this list :
values = [0, 2, 24, 26, 40, 42, 48, 50, 141, 143, 149, 151, 165, 167, 189, 191]
The second bit of any byte of the ciphertext never changes.
This is really interesting as it leaks info on the plaintext, sadly we do not have enough pairs to abuse this fact.
A relation involving the key would be more useful. That’s why I did the same experiment, but inducing a difference in the key :
def getDiff(j):
k = os.urandom(8)
s = Skippy(k)
m = os.urandom(8)
c = s.encrypt(m)
k = strxor(k, bytes([j]*8))
s = Skippy(k)
m2 = s.decrypt(c)
return strxor(m, m2)
The result is identical to the previous one, surprisingly !
Applying a XOR on any key byte with a value from the list keeps the second bit of any byte of the cipher text unchanged.
Let’s say we wanted to test a candidate for the first byte of the key, we could XOR it with all the values and see if the second bit of all the bytes of the cipher text changes. If they do not change for any value, it’s a valid candidate. This would however require that the other key bytes are already valid candidates.
Related key attack
There are 16 possibilities in the list of values. This means that if we pick a random bytes, we have a $\frac{16}{256} = \frac{1}{16}$ chance of having a valid candidate for this byte. If we have a key which is composed of 8 valid candidates, this key will be related to the real key by the relation we found earlier.
We can test if a key is related to the real key like this :
def testKey(k, c, p):
# k : key candidate
# p : known plaintext
# c : known plaintext encrypted with the real key
s = Skippy(k)
p2 = s.decrypt(c)
x = int(strxor(p, p2).hex(), 16)
return x & 0b0100000001000000010000000100000001000000010000000100000001000000 == 0
Finding a related key requires finding 8 valid candidates, thus we have a $\frac{1}{16^8}$ chance of finding one randomly. Once a related key is found we have $16^8$ possibilities for the real key.
This is certainly not the prettiest exploit and might not even be the intended solution, but at least it’s doable in a reasonable amount of time and at this point I had no other idea.
Searching for a related key
I used the following python script for the search :
from Crypto.Util.strxor import strxor
import os
data = [
b'Tout bie',
b'n que tu',
b' d\xc3\xa9tien',
b's est un',
b' souci q',
b'ui te re',
b'tient,\ne',
b't Skippy',
b' est l\xc3\xa0',
b' pour no',
b'us enlev',
b'er tout ',
b'nos souc',
b'is !\n\x00\x00\x00']
encrypted_data = [
b'\x16\xcb\x13p9f\$\r',
b'\xac\x80L\xecD\x93Z4',
b'\$*\x98(\x19m\x01I',
b'\xc8\xeb\x8d\xa1y\x0b\xb3\x9b',
b'\xa5\xb7\xd4\x8e\xe8\x8e\xdds',
b',wx\xc3?\xbc\x1d\x05',
b's\r\x99\xacd\xf1\x90,',
b"E'\xa9S\xd0\x18\xa9\xb9",
b'\xedX\x89\x1a23i\xc7',
b'\x08\x92*T\x0b\xbf\xe2\xb3',
b'\x8a\xef\x9a\x16\x07)s\xd2',
b'P\x84<\xc8\xf5\xbd\x07\x8b',
b'@P\xeey,9y&',
b'\xc5\xde\xfaP\xef\xdei\x93']
def testKey(k, c, p):
s = Skippy(k)
p2 = s.decrypt(c)
x = int(strxor(p, p2).hex(), 16)
return x & 0b0100000001000000010000000100000001000000010000000100000001000000 == 0
while True:
k = os.urandom(8)
good = True
for i in range(14):
if not testKey(k, encrypted_data[i], data[i]):
good = False
break
if good:
print(k)
To speed things up, I launched it in 8 separated tabs on my computer to make use of my 8 cores. Now it’s was just a matter of time until a related key was found.
After 13 hours of searching, I finally got this related key :
b'\x03~\xad\x95@\x0bNM'
Recovering the real key
During the never ending phase of waiting for a related key, I had plenty of time to prepare the next step, recovering the real key. This time I decided to do the search in C to really speed things up. I copied an existing SKIPJACK implementation and modified the S-box and the main function :
byte PLAIN[8] = {84, 111, 117, 116, 32, 98, 105, 101};
byte ENC[8] = {22, 203, 19, 112, 57, 102, 36, 13};
byte DIFFS[16] = {0, 2, 24, 26, 40, 42, 48, 50, 141, 143, 149, 151, 165, 167, 189, 191};
// prints string as hex
static void phex(byte* str, int size)
{
unsigned char i;
for(i = 0; i < size; ++i)
printf("%.2x", str[i]);
printf("\n");
}
static int testKey(byte *key, byte *plain, byte *cipher) {
byte tab[10][256];
byte enc[8];
makeKey(key, tab);
decrypt(tab, cipher, enc);
int sum = 0;
for (int i=0; i<8; i++) {
sum += (enc[i] ^ plain[i]) & 0b01000000;
}
return sum == 0;
}
static void recoverKey(byte *candidate) {
byte key[10];
byte tab[10][256];
byte enc[8];
int same;
// change the range of i between instances to split the search
for (int i=0; i<16; i++) {
for (int j=0; j<16; j++) {
for (int k=0; k<16; k++) {
for (int l=0; l<16; l++) {
for (int m=0; m<16; m++) {
for (int n=0; n<16; n++) {
for (int o=0; o<16; o++) {
for (int p=0; p<16; p++) {
key[0] = candidate[0] ^ DIFFS[i];
key[1] = candidate[1] ^ DIFFS[j];
key[2] = candidate[2] ^ DIFFS[k];
key[3] = candidate[3] ^ DIFFS[l];
key[4] = candidate[4] ^ DIFFS[m];
key[5] = candidate[5] ^ DIFFS[n];
key[6] = candidate[6] ^ DIFFS[o];
key[7] = candidate[7] ^ DIFFS[p];
key[8] = key[0];
key[9] = key[1];
makeKey(key, tab);
decrypt(tab, ENC, enc);
same = 1;
for (int a=0; a<8; a++) {
if (enc[a] != PLAIN[a]) {
same = 0;
break;
}
}
if (same == 1) {
phex(key, 10);
}
}
}
}
}
}
}
}
}
}
int main() {
byte key[10] = { 3, 126, 173, 149, 64, 11, 78, 77, 3, 126 };
recoverKey(key);
return 0;
}
I split the search space between my 8 cores and this time it took only 2 hours to recover the real key :
94DB3AA76823665594DB
Now we can decrypt the flag:
k = bytes.fromhex("94DB3AA76823665594DB")[:8]
s = Skippy(k)
print(s.decrypt(c2))
FCSC{2965c0554797e479476bb50418f4b73ee2128645688c7da6a4e051d1323b4f69}