In March 2024, SandboxAQ proposed a CTF around Post-Quantum Cryptography (and more specifically Kyber's key exchange) for the RWPQC workshop. Here is our write-up of the solutions to the challenges.
Introduction
In March 2024, SandboxAQ proposed a capture the flag composed of 4 challenges involving cryptography. More precisely, the goal was to test participants on their knowledge of post-quantum cryptography, where 3 out of the 4 challenges involved the CRYSTALS-Kyber key exchange mechanism, finalist of the NIST standardization competition.
Challenge 1: Breaking baby Kyber.
The challenge description gives an instantiation of Kyber with very small parameters (a.k.a Baby Kyber). A very nice description of how Kyber (and especially Baby Kyber) works is given here. In short, we have access to the public keys (A,t), the encryption outputs of a message (u,v), and the goal is to recover the message m.
Step 1: From MLWE (to LWE) to SVP
As explained in the Kyber submission, the theoretical security of Kyber is the security of the MLWE problem (Module Learning with Errors) which relies on a lattice problem called the Shortest Vector Problem (SVP). There exists a certain number of publications and tools about attacking LWE instances by finding the shortest vector of a well-formed lattice, given an LWE sample. In the context of this challenge, we are given an MLWE sample, a.k.a., the public matrix A and the corresponding vector t.
From MLWE to LWE.
A first step is to transform the MLWE sample from the challenge into an LWE sample. The literature is very opaque on exactly how this process should be done in practice. We found out through some digging and querying experts that A needs to be transformed into its negacyclic form in order to obtain a LWE sample. To do so, as the process was very experimental for us, we decided to have a deep look at how the project LWE with Hints4 generated Kyber instances of LWE. There, the following portion of the code where the matrix A is generated, gave us a way to transform our matrix A into its negacyclic form as follows:
"""
Returns the rotation matrix of poly, i.e.,
the matrix consisting of the coefficient vectors of
poly, X * poly, X^2 * poly, ..., X^(deg(poly)-1) * poly
modulo X^n-1.
If cyclotomic = True, then reduction mod X^n+1 is applied, instead of X^n-1.
"""
def rotMatrix(poly, cyclotomic=False):
n = len(poly)
A = np.array( [[0]*n for _ in range(n)] )
for i in range(n):
for j in range(n):
c = 1
if cyclotomic and j < i:
c = -1
A[i][j] = c * poly[(j-i)%n]
return A
"""
Given a list of polynomials poly = [p_1, ...,p_n],
this function returns a rows*cols matrix,
consisting of the rotation matrices of p_1, ..., p_n.
"""
def module( polys, rows, cols ):
if rows*cols != len(polys):
raise ValueError("len(polys) has to equal rows*cols.")
n = len(polys[0])
for poly in polys:
if len(poly) != n:
raise ValueError("polys must not contain polynomials of varying degrees.")
blocks = []
for i in range(rows):
row = []
for j in range(cols):
row.append( rotMatrix(polys[i*cols+j], cyclotomic=True) )
blocks.append(row)
return np.block( blocks )
and then A is generated as follows in the key generation function:
polys = []
for i in range(k*k):
polys.append( A[i] )
A = module(polys, 2, 2)
From LWE to SVP. The two main tools that we found to solve the SVP are the ones of Julian Nowakowski 4 and Ducas et al.5 Using the latter, we can get an estimation of the complexity of the attack. Plugging the correct inputs from the challenge, we got the following estimation:
n = 32
sage: m = 32
sage: D_e = {-1:0.33, 0:0.33, 1:0.33}
sage: D_s = {0:0.5, 1:0.5}
sage: D_e = {-1:0.33, 0:0.33, 1:0.34}
sage: A,t, dbdd = initialize_from_LWE_instance(DBDD_predict, n, q, m, D_e, D_s)
Build DBDD from LWE
n= 32 m= 32 q=251
sage: beta, delta = dbdd.estimate_attack()
Attack Estimation
dim= 65 δ=1.045280 β=2.00
However, despite using both tools and numerous trial-and-errors in SageMath, we were never able to recover s and e from the sample A and t.
Step 2: Bruteforcing s
The cryptographer's shame: when maths fails, just use the computer to fix it. We then decided to bruteforce s as the parameter settings and the fact that s coefficients were drawn in [0,1], allowed it. The code is rather straightforward: we look for all possible s such that
t - A*s yields a result for which the coefficients are either -1, 0, or 1. For that we used the NTL C++ library 1 to represent polynomials over the polynomial ring X^16+1 mod 256 and OpenMP for parallelization. The code is as follows:
#include <iostream>
#include <NTL/ZZ_pX.h>
#include <omp.h>
#define MODULE 251
#define DEGREE 16
using namespace std;
using namespace NTL;
bool isSmall(const ZZ_pX& poly) {
for (int i = 0 ; i < DEGREE ; ++i) {
if ((coeff(poly, i) != 0) && (coeff(poly, i) != (MODULE - 1)) && (coeff(poly, i) != 1) && (coeff(poly, i) != -1)) {
return false;
}
}
return true;
}
void numberToPoly(ZZ_pX& poly, long n) {
for (int i = 0 ; i < DEGREE ; ++i) {
if ((n>>i) & 1) {
SetCoeff(poly, i, 1);
} else {
SetCoeff(poly, i, 0);
}
}
}
int main() {
// Initialization
ZZ q_zz(MODULE);
ZZ_pInfo = new ZZ_pInfoT(q_zz);
ZZ_pX t, a1, a2;
long a1_vec[16] = {180, 198, 3, 194, 39, 34, 122, 189, 209, 91, 209, 5, 88, 25, 229, 195};
long a2_vec[16] = {229, 246, 105, 8, 222, 24, 73, 11, 212, 71, 138, 77, 30, 58, 83, 187};
long t_vec[16] = {9, 145, 210, 114, 215, 36, 243, 174, 134, 22, 205, 240, 177, 107, 188, 109};
for (int i = 0 ; i < DEGREE ; ++i) {
SetCoeff(a1, i, a1_vec[i]);
SetCoeff(a2, i, a2_vec[i]);
SetCoeff(t, i, t_vec[i]);
}
// Polynomial X^N + 1
ZZ_pX XNplus1;
SetCoeff(XNplus1, DEGREE, 1);
SetCoeff(XNplus1, 0, 1);
// Bruteforce to test all possible s1 and s2
#pragma omp parallel for
for (long s1_n = 1; s1_n < (1 << DEGREE); s1_n++) {
ZZ_pX s1, s2, temp1, temp2;
ZZ_pX to_test;
// segfault protection when using OpenMP
long q2 = MODULE;
ZZ q_zz2(q2);
ZZ_pInfo = new ZZ_pInfoT(q_zz2);
numberToPoly(s1, s1_n);
for (long s2_n = 1; s2_n < (1 << DEGREE); s2_n++) {
// Construction of polynomials s1 and s2 from their integer form
numberToPoly(s2, s2_n);
temp1 = MulMod(a1, s1, XNplus1);
temp2 = MulMod(a2, s2, XNplus1);
to_test = t - (temp1 + temp2);
// Verify if the t - A*s yields a small equation (aka solution in [-1,0,1])
if (isSmall(to_test)) {
cout << "FOUND s1 = " << s1_n << " and s2 = " << s2_n << endl;
}
}
}
cout << "Bruteforce over" << endl;
return 0;
}
After a couple of hours (or way less depending on your configurations), we obtain the following solution for s: FOUND s1 = 51423 and s2 = 59857. We verified that the obtained s yields a correct instantiation in SageMath and recovered the message m with the use of u and v as follows:
K = 2
N = 16
q = 251
R.<x> = Zmod(q)[]
RR = R.quotient(x^N +1)
RR
# Keygen outputs:
A1 = RR(195*x^15+229*x^14+25*x^13+88*x^12+5*x^11+209*x^10+91*x^9+209*x^8+189*x^7+122*x^6+34*x^5+39*x^4+194*x^3+3*x^2+198*x+180)
A2 = RR(187*x^15+83*x^14+58*x^13+30*x^12+77*x^11+138*x^10+71*x^9+212*x^8+11*x^7+73*x^6+24*x^5+222*x^4+8*x^3+105*x^2+246*x+229)
A3 = RR(84*x^15+95*x^14+224*x^13+177*x^12+43*x^11+155*x^10+63*x^9+246*x^8+232*x^7+177*x^6+53*x^5+243*x^4+41*x^3+111*x^2+73*x+234)
A4 = RR(3*x^15+85*x^14+143*x^13+51*x^12+177*x^11+116*x^10+247*x^9+222*x^8+181*x^7+33*x^6+78*x^5+196*x^4+188*x^3+216*x^2+170*x+64)
A = matrix(RR, [[A1,A2], [A3,A4]])
t1 = RR(109*x^15+188*x^14+107*x^13+177*x^12+240*x^11+205*x^10+22*x^9+134*x^8+174*x^7+243*x^6+36*x^5+215*x^4+114*x^3+210*x^2+145*x+9)
t2 = RR(198*x^15+159*x^14+120*x^13+184*x^12+217*x^11+224*x^10+96*x^9+124*x^8+30*x^7+155*x^6+247*x^5+34*x^4+224*x^3+154*x^2+240*x+235)
t = matrix(RR, [t1,t2])
# Encryption outputs:
u1= RR([49, 227, 248, 198, 5, 218, 34, 86, 30, 121, 37, 124, 19, 243, 118, 49])
u2= RR([112, 190, 242, 199, 70, 141, 85, 141, 128, 82, 224, 218, 28, 147, 70, 41])
u = matrix(RR, [u1,u2])
v = RR([29, 156, 77, 121, 232, 189, 96, 34, 16, 86, 80, 165, 81, 72, 206, 78])
# decompress function
def decompress(m_n):
res = [1]*16
for i in range(16):
e = m_n[0][0].list()[i]
if e in range(-q//4, q//4):
res[i] = 0
return res
# results of the bruteforce
s1 = RR([1,1,1,1,1,0,1,1,0,0,0,1,0,0,1,1])
s2 = RR([1,0,0,0,1,0,1,1,1,0,0,1,0,1,1,1])
s = matrix(RR, [s1,s2])
err = t.transpose() - A * s.transpose()
print(err[0][0].list())
print("error in -1,0,1:", all(coeffs in [0,1,250] for coeffs in err[0][0].list()))
m_n = v - s * u.transpose() #decryption
print("flag:", decompress(m_n)) #decompression
which outputs
[0, 0, 1, 0, 1, 0, 1, 1, 250, 250, 250, 1, 0, 0, 250, 0]
error in -1,0,1: True
flag: [1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1]
If anyone managed to solve it using BKZ, please contact me :).
Challenge 2: Attack on Trained Logistic Regression Model.
We will not go into much detail about this challenge as it did not involve cryptography at all. The proposed subject is of major interest in the field of machine learning and was very interesting to tackle. To briefly summarize the approach, our solver was based on the Theorem 1. of the paper Reconstructing Training Data with Informed Adversaries 2, for which we had to adjust slightly the formulas and do some trial-and-errors until a satisfying delta (equal to 0.0001 at the end) was found between the given thetas and the recovered ones.
Challenge 3: Breaking a real PQC implementation.
The goal of the challenge is to decrypt the communications between a client and a server logged in a pcap file. Two executables are provided, one for the client and one for the server, to be reverse engineered. A clear and detailed description of the behavior of the client and of the server, on top of the appropriate commands and arguments we can use, are provided.
The server is a program that continuously listens on an address and port (default one or specified), and upon reception of a client's command, will start a key exchange protocol using Kyber with the security level specified by the first argument of the client's command. After that, secure communication exchanges using AES-ECB are done between the client and the server, depending on the command used. The possible commands are PUT (upload file), GET (download file), and DIR (list directory). An additional information is provided that specifies that each secure communication exchange (client -> server or server -> client) ends with the "END" block.
The library used for the post-quantum KEM is liboqs.
Step 1: Analyzing the two executables and pcap file
Decompiling in Ghidra
A first glance at the provided executable with Ghidra shows us that the OQS_version function is on version 0.9.0 (which is not the latest). We then used BinDiff to compare the library with the executable but we did not find any major difference from which a cryptographic bug could be inferred. Scanning the mains in Ghidra quickly raised a warning: in fact, before the key establishment protocol starts, the program makes a call to OQS_randombytes_switch_algorithm(OQS_RAND_alg_nist_kat);. If you are familiar with NIST's competition, this function is a NIST provided function that upon instantiation with a seed will produce deterministic randomness. This mode is used when test vectors need to be created. Moreover, the latest tag of liboqs has removed the direct support for this function.
Following this clue on the potential use of a predictable randomness generator throughout the program, we ran the two executables and got the following output from the server:
dgoudarzi@xxxxx ~/c3> ./ctf_server
Serving on default port 1337
Socket created
Socket bind succeed
Socket listening
Client connected
orig seed = 000000000000000000000000000000000000000000000000010101010001010000000101000100000001010100000001
Shared secret successfully received
Secure AES256 established
Looking at the decompiled code, we can see that the output seed corresponds to the seed with which the OQS random generator is initialized. This means that with knowledge of this seed, we can predict all the randomness used and therefore the server's key pair. Especially, from the form of the seed, it seems that it was formed with very weak entropy.
Extract the PCAP info
Using scapy and a well-suited script, we were able to display the different relevant communications between the client and the server. From the patterns, the size of the data (and the knowledge of the size of Kyber instances), it is easy to understand that the pcap file represents 4 communications between the server with the following Kyber instances: NS1, NS3, NS5, and NS5. For each one of these communications, the pcap file contains the data sent between the server and the client: first the Kyber instance value given by the client, then the server's public key, third the client's ciphertext, and finally some AES-ECB encrypted communications of which the first part are the commands encrypted. We show hereafter a cropped display of a communication between the server and the client:
[+] Data of each packets:
[+]
[+] Src addr: 127.0.0.1:47826 (client)
[+] Dst addr: 127.0.0.1:1337 (server)
[+]
[+] Data size: 16
[+] Data content:
[+] 00000000 4e 53 31 00 00 00 00 00 00 00 00 00 00 00 00 00 |N S 1 . . . . . . . . . . . . .|
[+]
[+] ----------------------------------------------------------------------------------------------------
[+]
[+] Src addr: 127.0.0.1:1337 (server)
[+] Dst addr: 127.0.0.1:47826 (client)
[+]
[+] Data size: 800
[+] Data content:
[+] 00000000 4f a6 1e 20 97 84 18 14 c1 3f d3 90 b1 a7 b0 dc |O . . . . . . . ? . . . . . .|
......................
[+] 00000310 61 f8 d4 ca eb a1 7c cc db b3 a2 45 98 cb 5b 78 |a . . . . . | . . . . E . . [ x|
[+]
[+] ----------------------------------------------------------------------------------------------------
[+]
[+] Src addr: 127.0.0.1:47826 (client)
[+] Dst addr: 127.0.0.1:1337 (server)
[+]
[+] Data size: 768
[+] Data content:
[+] 00000000 af 38 0d 94 fa 86 23 bc ce 15 96 67 52 58 9b cf |. 8 . . . . # . . . . g R X . .|
......................
[+] 000002f0 c7 c0 37 75 dc ef 65 b9 8e 83 d0 8f f9 49 65 74 |. . 7 u . . e . . . . . . I e t|
[+]
[+] ----------------------------------------------------------------------------------------------------
[+]
[+] Src addr: 127.0.0.1:47826 (client)
[+] Dst addr: 127.0.0.1:1337 (server)
[+]
[+] Data size: 48
[+] Data content:
[+] 00000000 59 13 79 db 74 e2 d5 d6 da 92 59 c8 7d 30 c7 42 |Y . y . t . . . . . Y . } 0 . B|
[+] 00000010 d9 1c 3d 4c 23 ca 9d 28 20 c9 fd db 6a 91 b7 e6 |. . = L # . . ( . . . j . . .|
[+] 00000020 8e 0d 9e 14 7b 07 6f ec 44 25 0a 6b a6 4f 75 9e |. . . . { . o . D % . k . O u .|
[+]
[+] ----------------------------------------------------------------------------------------------------
[+]
[+] Src addr: 127.0.0.1:1337 (server)
[+] Dst addr: 127.0.0.1:47826 (client)
[+]
[+] Data size: 16
[+] Data content:
[+] 00000000 32 68 1c 94 ee f7 38 a1 36 ac 49 d4 9f ae 64 38 |2 h . . . . 8 . 6 . I . . . d 8|
[+]
[+] ----------------------------------------------------------------------------------------------------
[+]
[+] Src addr: 127.0.0.1:1337 (server)
[+] Dst addr: 127.0.0.1:47826 (client)
[+]
[+] Data size: 368
[+] Data content:
[+] 00000000 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 00000010 d9 1c 3d 4c 23 ca 9d 28 20 c9 fd db 6a 91 b7 e6 |. . = L # . . ( . . . j . . .|
[+] 00000020 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 00000030 5e 37 60 21 a9 fc 00 dd c2 27 f8 33 43 2e 53 3f |^ 7 ` ! . . . . . ' . 3 C . S ?|
[+] 00000040 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 00000050 99 8a 6f 5f 71 1b 17 43 92 90 2d ff 24 0f 2b bf |. . o _ q . . C . . - . $ . + .|
[+] 00000060 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 00000070 a7 35 81 2d 11 d1 59 ca 1b d2 86 09 2a 27 d7 98 |. 5 . - . . Y . . . . . * ' . .|
[+] 00000080 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 00000090 ee 99 f6 c5 c4 48 17 1f 95 1d 1c 85 2d bd 98 90 |. . . . . H . . . . . . - . . .|
[+] 000000a0 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 000000b0 73 57 22 51 18 39 01 92 2c b2 08 c0 ec ff 4e c1 |s W " Q . 9 . . , . . . . . N .|
[+] 000000c0 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 000000d0 d4 3c 61 00 67 4f 00 f6 a7 a7 df a6 80 c8 5a 7a |. < a . g O . . . . . . . . Z z|
[+] 000000e0 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 000000f0 80 74 8c bf 8a fc 6d 7f 4c 34 f4 36 5c 80 4a 82 |. t . . . . m L 4 . 6 \ . J .|
[+] 00000100 da 34 bd fb 15 6c b7 8c d6 82 3b 60 1e 59 11 4d |. 4 . . . l . . . . ; ` . Y . M|
[+] 00000110 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 00000120 bb bf 81 99 04 0f 0c 11 f7 62 be e2 9a 97 77 b7 |. . . . . . . . . b . . . . w .|
[+] 00000130 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 00000140 e6 dc 48 d4 97 94 20 04 f5 c8 09 5f 67 89 53 70 |. . H . . . . . . . _ g . S p|
[+] 00000150 5a 18 c7 f5 31 30 50 aa 7c ef 0f 22 d4 64 d7 43 |Z . . . 1 0 P . | . . " . d . C|
[+] 00000160 8e 0d 9e 14 7b 07 6f ec 44 25 0a 6b a6 4f 75 9e |. . . . { . o . D % . k . O u .|
[+]
[+] ----------------------------------------------------------------------------------------------------
Step 2: Exploiting deterministic RNG initialized with weak entropy
Further analysis with gdb on the server and Ghidra on the executables confirmed our thought process: the seed is smashed with the mask 0x101010101010101 as shown in the extracted code from Ghidra:
orig_seed = local_78;
OQS_randombytes(orig_seed);
local_78 = (undefined [16])0x0;
auVar2._8_8_ = 0;
auVar2._0_8_ = local_68._8_8_ & 0x101010101010101;
local_68 = auVar2 << 0x40;
local_58._8_8_ = local_58._8_8_ & 0x101010101010101;
local_58._0_8_ = local_58._0_8_ & 0x101010101010101;
So instead of having a seed of entropy 2^96 as intended since it is the output of the system's random generator, we have only 2^23 possible seeds after application of those masks. Moreover, since we got the server's public keys from the pcap, we can easily mount a brute-force attack to recover the server's keypair as follows:
- instantiate randomness with seed
i - compute a Kyber keypair with the desired security level
- check if the generated public key corresponds to the pcap public key
- restart with next seed candidate
The code in C is the following, and due to the rapidity of it, we did not even bother to optimize or parallelize it:
// brute force part
int rc, res;
struct AES_ctx ctx;
for (size_t i=0; i<16777216; i++) {
for (size_t j=0; j<24; j++){
entropy_input[24+j] = (i>>j) & 1;
}
OQS_randombytes_nist_kat_init_256bit(entropy_input, NULL);
rc = OQS_KEM_kyber_1024_keypair(public_key,secret_key);
res = memcmp(public_key, test_public_key, OQS_KEM_kyber_1024_length_public_key);
if (res == 0) {
for (size_t j=0; j<24; j++) {
printf("%d, ", entropy_input[24+j]);
}
return 0;
}
}
which provides us the 4 seeds used for each of the communication exchange.
Step 3: Decrypting the communications
From this point, having recovered the four server private keys (one for each communication), the rest of the challenge is straightforward. Having access to the ciphertext from the pcap file, we can use the OQS_KEM_kyber_NS_decaps function to recover the 32-byte shared secret. Here is the example code for the case NS5.
// // recovering pcap communications
OQS_randombytes_nist_kat_init_256bit(entropy_input, NULL);
int rc = OQS_KEM_kyber_1024_keypair(public_key, secret_key);
rc = OQS_KEM_kyber_1024_decaps(shared_secret, ciphertext, secret_key);
for (size_t i=0; i<32; i++) {
printf("%02X", shared_secret[i]);
}
The only part that was misleading is that throughout the challenge, it is highly implied that AES-ECB-256 is used, especially since the shared secret is 32 bytes long and ECB is used. However, the AES used by the executable is AES-ECB-128, which was caught while running gdb on the server executable during the key expansion. It is also worth noting that since liboqs does not implement AES decryption, the executables are using another external library and judging from what we saw, it was the tiny-aes implementation. From there, we just need to decrypt the encrypted communications which yields the following (concatenating the four communications):
DIR.ENDb.txt
.
d.txt
c.txt
ctf_server
abc
bfg
..
server_secret.txt
a.txt
abc.txt
ENDPUTclient_secret.txtEND1337h@x0r
ENDDIR.ENDb.txt
.
d.txt
c.txt
ctf_server
client_secret.txt
abc
bfg
..
server_secret.txt
a.txt
abc.txt
ENDGETserver_secret.txtENDMy v0ice is my p@ssport.
END
Challenge 4: Dancing by Xyber.
The goal of this challenge is to establish a TLS communication with a server using the adequate configuration which will trigger the server to send the flag.
Step 1: Analyzing the queries
Using the provided client written in Python and logging the communications via Wireshark, we quickly notice that the Server sends a Alert (Level: Fatal, Description: Illegal Parameter). Playing with the tlslite source, we removed the support of Kyber-related Key shares. This triggers the Server to send a Hello Retry Request to the client, which corresponds to the use case where acceptable parameters are not found for the key exchange.
More precisely, the server asks for:
- ciphersuite:
TLS_AES_128_GCM_SHA256 - supported_groups:
X25519Kyber768Draft00
This means that the server wants to perform an hybrid key exchange using X25519 and Kyber-768, which is consistent with the summary of the challenge and its name. We modified the tls/handshakesettings.py initialization function to enforce that the Key share group is the one of X25519Kyber768 by default as follows:
def _init_key_settings(self):
...
self.defaultCurve = "x25519kyber768draft00"
self.keyShares = ["x25519kyber768draft00"]
...
However, having a quick glance at the provided tlslite implementation, we noticed that the hybrid key exchange was not implemented.
Step 2: Fixing the tlslite implementation
In Section 3 of the RTF draft on X25519Kyber768Draft00 hybrid post-quantum key agreement 3, the exact details on how to implement the key exchange are provided. This simply consists in doing the key exchange for X25519 and Kyber768 respectively, and concatenating the correct outputs at each step. The following functions were modified in tlslite/keyexchange.py and tlslite/tlsconnection.py
def calc_shared_key(self, private, peer_share):
"""Calculate the shared key,"""
if self.group in self._x_groups:
...
elif self.group == GroupName.x25519kyber768draft00:
x25519_ps = peer_share[:32]
kyber_ps = peer_share[32:]
S = x25519(private[:32], x25519_ps)
self._non_zero_check(S)
kb = kyber.Kyber(kyber.DEFAULT_PARAMETERS['kyber_768'])
skb = kb.dec(kyber_ps, private[32:])
return S+skb
@classmethod
def _genKeyShareEntry(cls, group, version):
"""Generate KeyShareEntry object from randomly selected private value.
"""
kex = cls._getKEX(group, version)
private = kex.get_random_private_key()
share = kex.calc_public_value(private)
kb = kyber.Kyber(kyber.DEFAULT_PARAMETERS['kyber_768'])
pub, priv = kb.keygen()
return KeyShareEntry().create(group, share + pub, private + priv)
Running the client again will then result in a Handshake success and the server sending the flag:
Handshake success
Received data: HTTP/1.1 200 OK
Date: Wed, XX Mar 2024 XX:XX:XX GMT
Content-Length: 78
Content-Type: text/plain; charset=utf-8
The flag is: 5443184089537ac26d77f5605e1d0c8271597ca097ef1b40be77c7a7bbd62d90.
Acknowledgement
I would like to thank my co-workers who were of tremendous help in my journey into my first real CTF (especially when they had to tell me that pcap files are supposed to be opened with WireShark and are not some weird encrypted file format :)) and former ones for the quick lattice reminder.