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 – 50 points
- RSA Destroyer – 200 points
- Lost curve – 200 points
- Hashy Parmentier – 200 points
- Revaulting – 500 points
- SmeaLog – 500 points
- Trappy Skippy – 500 points
MACAQUE – 50 POINTS
DESCRIPTION
Retrouvez le flag avec l'accès à ce service distant.
nc challenges1.france-cybersecurity-challenge.fr 6000
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.")
RESOLUTION
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
; - The last block of the AES-CBC encryption of the message using an all zero IV and unknown key
.
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 
and 
, we can forge a message 
(where 
denotes the block 
of 
), whose tag will be 
.
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 
, 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 
:
# 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 of our new message 
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 – 200 POINTS
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}")
RESOLUTION
The code is actually not needed to solve this challenge.
By looking at the hexadecimal representation of 
, we can see a particular pattern:
0xbf0a8dd7d8f16cad000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000 000000001002c0b6fc6c3c2949b0a1e097f3c51eff2e8919800000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f 110eb
This is a strong indicator that the structure of looks like this : 
.
The particular structure of can be explained by looking at the generation of 
and 
:
![\[\begin{split} p &= a(2^{1024} - e) + u \\ &= a2^{1024} - ae + u \\ &= a2^{1024} + b \end{split}\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-b13d7a6313c8a9cfb178641b760514ce_l3.png "Rendered by QuickLaTeX.com")
With :
![\[b = u - ae\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-c8728ffc9ce45c3d74f72def598dcc47_l3.png "Rendered by QuickLaTeX.com")
We can easily rewrite like :
n = 0xbf0a8dd7d8f16cad*2**2048 + 0x1002c0b6fc6c3c2949b0a1e097f3c51eff2e89198*2**1024 + 0x526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f110eb
Let’s define 
, we get a polynomial representation of :
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 the roots for 
, we’ll recover the factors and .
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 – 200 POINTS
DESCRIPTION
J'ai perdu l'équation de ma courbe elliptique : pouvez-vous m'aider à la retrouver ? nc challenges1.france-cybersecurity-challenge.fr 6002
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!")
RESOLUTION
When connecting to the service, we are greeted with two points on a newly generated curve and asked to provide it’s parameters 
:
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 
, we can use the point doubling formula and recover .
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}\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-4b8acdcb16c5a729a7a4ba7a1d66ecef_l3.png "Rendered by QuickLaTeX.com")
With 
a special value that we do not need to detail here. We do not know and we can’t compute it as it depends on the value of 
.
Recall that the above equations hold modulo .
The idea to recover is to manipulate those equations in order to produce a multiple of .
From the first equation we have 
.
Let’s define 
.
From the second equation we have 
, which implies 
.
Using the result of the first equation, we get 
.
Rewritten as 
, we see that this is a multiple of and we have all the necessary information to compute it.
Once computed, 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 
with two unknowns and 
. We have the coordinates of two points on the curve, thus we can recover and 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}\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-d5fc69ff72d45153106801148da88862_l3.png "Rendered by QuickLaTeX.com")
This system of linear equations can be represented by a 2×2 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 – 200 POINTS
DESCRIPTION
Mon professeur de cryptographie a dit qu'une fonction de hachage cryptographique compresse les données : mais est-ce que cela peut introduire des problèmes ?
nc challenges1.france-cybersecurity-challenge.fr 6001
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!")
RESOLUTION
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 
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)\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-84c1b9c271766b520fa6da730b2b0284_l3.png "Rendered by QuickLaTeX.com")
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 (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 
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 – 500 POINTS
DESCRIPTION
On nous informe que ce service de coffre-fort n'est pas suffisamment sécurisé. Pouvez-vous le prouver en accédant à son contenu ?
nc challenges1.france-cybersecurity-challenge.fr 6003
SHA256(revaulting) = 83c64fc43428fa7492d2e2ea255c5b17c921271fc4415bbbe82d24b094627046.
As this is also a reverse engineering challenge, only the service’s binary is provided and not the sources.
RESOLUTION
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 
are the same. This should allow us to rewrite :
![\[\begin{split}k &= b + b2^l \\ &= b(2^l + 1)\end{split}\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-0745516e5de02fd925beec4e62f5989e_l3.png "Rendered by QuickLaTeX.com")
with 
and an unknown small value (compared to the order 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 
and the curve parameters 
. Actually, this will produce two public keys as 
and 
are both valid points that could have produced 
:
# 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 – 500 POINTS
DESCRIPTION
Pourrez-vous résoudre ce logarithme discret ?
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()}")
RESOLUTION
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 
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 
instead, but the order 
of is only :
q_ = E_.order()
q_
1614926806643
if we solve the ECDLP on , we will find 
:
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 
.
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 
:
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 using . But we can’t solve it modulo 
on because we can’t multiply any point by 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 :
is our curve ;
is our curve ;
is the ring of integers modulo ;
is our point on ;
is defined in the paper as the canonical projection ;
is thus our point 
on ;- is the order of , which we have called ;
The hard part was understanding the right side of the tuple. it says to divide the x and y coordinates of 
, but as we saw earlier, Sage refuses to perform the multiplication because we cannot divide by a multiple of .
HOMOGENUOUS COORDINATES
The coordinates of an EC point in sage are always represented by 3 coordinates 
, with 
. 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)\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-4b7e4116c2f5c4f91d8bb924dffc7592_l3.png "Rendered by QuickLaTeX.com")
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 :
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 into an element of 
, let’s call it 
. We can do the same for the point 
.
Since 
, we have 
and so we can recover 
by simply multiplying 
with the invert of :
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}\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-7c074d6413219f72c0062593c90b28de_l3.png "Rendered by QuickLaTeX.com")
We just have to use the Chinese remainder theorem to reconstruct 
:
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 – 500 POINTS
DESCRIPTION
Skippy le grand gourou vous met au défi de déchiffrer son 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)
RESOLUTION
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 
the bit 
of the input and 
the bit 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}\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-93833e38a64073dd20d3859c668f2703_l3.png "Rendered by QuickLaTeX.com")
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}\]](https://bitsdeep.com/wp-content/ql-cache/quicklatex.com-03f72222d24794a33180fe3ace13b1dd_l3.png "Rendered by QuickLaTeX.com")
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 
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 
chance of finding one randomly. Once a related key is found we have 
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}
I dont even understand anything from your writeup but jeezz this thing is awesome! i recently into solving crypto challenges and seeing these kind of writeups amaze me!
Really thankful for your writeup! your awesome!!
Salut, merci infiniment pour avoir fait les writeups du FCSC. Je veux que tu saches que ça m’a vraiment beaucoup aidé à comprendre. Cependant j’aimerai savoir comment tu as eu le réflexe pour le challenge “RSA Destroyer” de factoriser le modulus en polynôme du second degré et pour le challenge “Lost Curve” d’arranger la formule de “point doubling” pour obtenir p. J’aimerai comprendre ta démarche, c’est à dire : est ce que tu connaissais déjà la solution par un précédent challenge similaire et donc tu as réutilisé la solution ou alors si ce raisonnement vient de ta réflexion. Donc si ce raisonnement vient bien de toi j’aimerai savoir comment tu as eu le réflexe. J’espère que j’ai été compréhensible :’). Merci du temps que tu vas accordé à ma question.
Salut, merci pour ton message.
Pour “RSA Destroyer” c’est en regardant la représentation hexadécimale que j’ai vu le motif particulier, après c’est juste un jeu d’écriture pour le transformer en polynôme. La méthode plus rigoureuse est celle que je décris en se basant sur la formule utilisée pour générer p et q.
Pour “Lost Curve”, j’ai pu utiliser la formule de “point doubling” uniquement parce que Q = 2*P. Si ça avait été n’importe quel autre nombre, cela aurait été bien plus difficile, car pour passer du point P au point Q, il y aurait eu 2 formules différentes impliquées. Pour passer de la formule de “point doubling” à la valeur de p, j’ai cherché un moyen de faire resurgir p. Pour ça il n’y a pas de miracle, il faut jouer avec les équations comme des legos, là je ne montre que la solution. Quand on a plusieurs multiples de p et utiliser le gcd, mais ce n’est pas le cas ici, donc j’ai eu l’idée de factoriser celui que j’ai construit.
J’espère que ça a répondu à tes questions.
Salut je te remercie longtemps après ta réponse. Je m’entraîne en ce moment pour le prochain FCSC et tes writeups m’aident beaucoup pour m’entraîner. Sinon j’ai d’autres questions : pour le challenge reveaulting sur les signatures ECDSA tu as repris une attaque qui utilise la réduction de réseau (LLL) mais de ce que j’ai compris tu as un peu modifier la matrice qui sert de base pour que ça colle au challenge. Je voudrais savoir, comment construire une matrice qui répond à notre question (pourquoi cette configuration de matrice et pas une autre) en appliquant l’algo LLL. Autre question : dans le challenge Smealog, pour retrouver s sur p³ tu multiples le point Q par l’inverse de P. Je n’ai jamais entendu parler de l’inverse d’un point sur une courbe elliptique. Est ce que tu aurais des ressources qu’il l’explique ?
PS : rectification : * je n’ai jamais entendu parler de la multiplication entre deux points sur une courbe elliptique ( donc aussi de la multiplication d’un point et de l’inverse d’un point)