Skip to content

Instantly share code, notes, and snippets.

@Riatre

Riatre/0writeup.md Secret

Created July 18, 2022 23:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Riatre/743da601776d3d10d430dcd9d6a80dc9 to your computer and use it in GitHub Desktop.
Save Riatre/743da601776d3d10d430dcd9d6a80dc9 to your computer and use it in GitHub Desktop.
Download ZIP
Google CTF 2022 Electric Mayhem PQC
Raw
0writeup.md

Electric Mayhem PQC

The challenge requires us to perform power analysis attack against PQClean's KYBER-512-90S implementation on an (emulated) Cortex-M0 processor to recover the private key. KYBER-512 is a lattice-based post-quantum cryptography scheme, if this does not make sense for you, don't worry. We don't have to understand it to solve the challenge.

The challenge gives 8000 power traces of the target device running one KYBER-512 KEM with a fixed, unknown private key. It gives xor(flag, session_key) for all 8000 runs, so recovering any single session key uncovers the flag. The power traces are not generated on real device, but ELMO is used instead. The traces also has some unknown noise mixed in to avoid being too unrealistic as by default ELMO outputs very stable signal.

We mainly followed the ideas in this paper, with a few improvements.

Basically, the idea is that the power consumtpion of executing an "add" instruction is correlated to the hamming weight of the add result. By finding a suitable target instruction with one side derived from the ciphertext and the other side derived from partial private key, we could make guess on the covered part of the private key and validate by checking how the hamming weight of the add result in our guess for all traces is correlated to the power consumption.

In the first round of the kem_dec operation of KYBER-512-90S, the ciphertext and the private key (in polynomial form) is mixed together in such a function:

/*************************************************
* Name:        PQCLEAN_KYBER51290S_CLEAN_basemul
*
* Description: Multiplication of polynomials in Zq[X]/(X^2-zeta)
*              used for multiplication of elements in Rq in NTT domain
*
* Arguments:   - int16_t r[2]: pointer to the output polynomial
*              - const int16_t a[2]: pointer to the first factor
*              - const int16_t b[2]: pointer to the second factor
*              - int16_t zeta: integer defining the reduction polynomial
**************************************************/
void PQCLEAN_KYBER51290S_CLEAN_basemul(int16_t r[2], const int16_t a[2], const int16_t b[2], int16_t zeta) {
    r[0]  = fqmul(a[1], b[1]);
    r[0]  = fqmul(r[0], zeta);
    r[0] += fqmul(a[0], b[0]);
    r[1]  = fqmul(a[0], b[1]);
    r[1] += fqmul(a[1], b[0]);
}

/*************************************************
* Name:        PQCLEAN_KYBER51290S_CLEAN_poly_basemul_montgomery
*
* Description: Multiplication of two polynomials in NTT domain
*
* Arguments:   - poly *r: pointer to output polynomial
*              - const poly *a: pointer to first input polynomial
*              - const poly *b: pointer to second input polynomial
**************************************************/
void PQCLEAN_KYBER51290S_CLEAN_poly_basemul_montgomery(poly *r, const poly *a, const poly *b) {
    size_t i;
    for (i = 0; i < KYBER_N / 4; i++) {
        PQCLEAN_KYBER51290S_CLEAN_basemul(&r->coeffs[4 * i], &a->coeffs[4 * i], &b->coeffs[4 * i], PQCLEAN_KYBER51290S_CLEAN_zetas[64 + i]);
        PQCLEAN_KYBER51290S_CLEAN_basemul(&r->coeffs[4 * i + 2], &a->coeffs[4 * i + 2], &b->coeffs[4 * i + 2], -PQCLEAN_KYBER51290S_CLEAN_zetas[64 + i]);
    }
}

where a is a slice of the private key and b is a slice of the ciphertext. $0 \leq a_i, b_i \lt KYBER_Q$ where KYBER_Q = 3329.

We targetted the second += (on r[1]). To do so, we replicated the crypto_kem_dec process up until the poly_basemul_montgomery call. Then, for each loop iteration, search over all $3329^2$ possibilities of a->coeffs[2*i] and a->coeffs[2*i+1]. Since we don't know the alignment, we have to try all possible sample index starting from the end of last basemul call. This leads to a problem: we had to distinguish the two +=, otherwise we may have two plasuible answers for each pair of a->coeffs[2*i] and a->coeffs[2*i+1]. We did so by first locating where fqmul(a[0], b[1]) and fqmul(a[1], b[0]) was computed, in a similar way of power analysis (trying to find correlation between hamming weights of the mul result and power cosumption) and then only looking for += matches after both. We then picked the answer with highest spearman correlation.

The solution is reasonably fast, it finishes in about 15 minutes with 256 vCPU.

Raw
1solve.cc
#include <algorithm>
#include <cstdint>
#include <gsl/gsl_statistics.h>
#include <gsl/gsl_statistics_double.h>
#include <gsl/gsl_vector.h>
#include <map>
#include <rapidjson/document.h>
#include <rapidjson/filereadstream.h>
#include <set>
#include <stdio.h>
#include <string>
#include <string_view>
#include <vector>
extern "C" {
#include "api.h"
#include "params.h"
#include "poly.h"
#include "polyvec.h"
#include "reduce.h"
}
constexpr size_t kNSessions = 200;
constexpr size_t kNSamples = 8344;
uint8_t g_public_key[PQCLEAN_KYBER51290S_CLEAN_CRYPTO_PUBLICKEYBYTES];
struct Session {
polyvec ciphertext_b_ntt;
// poly ciphertext_v;
uint8_t flag_xor_ss[32];
std::vector<double> pm;
};
std::vector<Session> g_sessions;
double pm_matrix[kNSamples][kNSessions];
namespace {
void LoadData(const std::string &filename) {
char buf[65536];
FILE *fp = fopen(filename.c_str(), "r");
rapidjson::FileReadStream fis(fp, buf, sizeof(buf));
rapidjson::Document doc;
doc.ParseStream(fis);
assert(!doc.HasParseError());
assert(doc.IsObject());
assert(doc.HasMember("pk"));
auto pk = doc["pk"].GetArray();
assert(pk.Size() == sizeof(g_public_key));
for (size_t i = 0; i < pk.Size(); i++) {
g_public_key[i] = pk[i].GetUint();
}
assert(doc["sessions"].Size() == kNSessions);
g_sessions.reserve(doc["sessions"].Size());
for (auto &session : doc["sessions"].GetArray()) {
Session s;
auto ct = session["ct"].GetArray();
assert(ct.Size() == KYBER_INDCPA_BYTES);
uint8_t ct_data[KYBER_INDCPA_BYTES];
for (size_t i = 0; i < ct.Size(); i++) {
ct_data[i] = ct[i].GetUint();
}
PQCLEAN_KYBER51290S_CLEAN_polyvec_decompress(&s.ciphertext_b_ntt, ct_data);
PQCLEAN_KYBER51290S_CLEAN_polyvec_ntt(&s.ciphertext_b_ntt);
auto ss = session["flag_xor_ss"].GetArray();
assert(ss.Size() == sizeof(s.flag_xor_ss));
for (size_t i = 0; i < ss.Size(); i++) {
s.flag_xor_ss[i] = ss[i].GetUint();
}
s.pm.reserve(session["pm"].Size());
for (auto &pm : session["pm"].GetArray()) {
s.pm.emplace_back(pm.GetDouble());
}
g_sessions.emplace_back(s);
}
for (size_t i = 0; i < kNSamples; i++) {
for (size_t j = 0; j < kNSessions; j++) {
pm_matrix[i][j] = g_sessions[j].pm[i];
}
}
fclose(fp);
}
static int16_t fqmul(int16_t a, int16_t b) {
return PQCLEAN_KYBER51290S_CLEAN_montgomery_reduce((int32_t)a * b);
}
std::vector<double> HammingWeightOfMulsGuess(size_t vec_idx, size_t offset,
int b_which, int16_t a_guess) {
assert(vec_idx < KYBER_K);
assert(offset < KYBER_N / 2);
assert(b_which == 0 || b_which == 1);
std::vector<double> result;
result.reserve(g_sessions.size());
for (auto &sess : g_sessions) {
auto b = sess.ciphertext_b_ntt.vec[vec_idx].coeffs[2 * offset + b_which];
result.push_back(__builtin_popcount((int32_t)a_guess * b));
}
return result;
}
std::vector<double> HammingWeightOfAdd(size_t vec_idx, size_t offset,
int16_t a0_guess, int16_t a1_guess) {
assert(vec_idx < KYBER_K);
assert(offset < KYBER_N / 2);
std::vector<double> result;
result.reserve(g_sessions.size());
for (auto &sess : g_sessions) {
auto b0 = sess.ciphertext_b_ntt.vec[vec_idx].coeffs[2 * offset + 0];
auto b1 = sess.ciphertext_b_ntt.vec[vec_idx].coeffs[2 * offset + 1];
result.push_back(
__builtin_popcount(fqmul(a0_guess, b1) + fqmul(a1_guess, b0)));
}
return result;
}
std::vector<std::tuple<double, int16_t, int>>
FindCandidate(size_t vec_idx, size_t offset, int b_which, int align_start) {
std::vector<std::tuple<double, int16_t, int>> matches;
constexpr int kAlignSearchSize = 100;
int align_freq[kAlignSearchSize] = {0};
int tot = 0;
for (int a_guess = 1; a_guess < KYBER_Q; a_guess++) {
for (int align = align_start; align < align_start + kAlignSearchSize;
align++) {
auto w = HammingWeightOfMulsGuess(vec_idx, offset, b_which, a_guess);
double pearson =
gsl_stats_correlation(pm_matrix[align], 1, w.data(), 1, kNSessions);
if (pearson > 0.5) {
matches.emplace_back(pearson, a_guess, align);
align_freq[align - align_start]++;
tot++;
}
}
}
int align_pos = -1;
for (int i = kAlignSearchSize - 1; i > 0; i--) {
if ((align_freq[i] + align_freq[i - 1]) * 5 > tot) {
align_pos = (align_freq[i] > align_freq[i - 1]) ? (i + align_start)
: (i - 1 + align_start);
break;
}
}
if (align_pos == -1) {
for (int i = 0; i < kAlignSearchSize; i++) {
fprintf(stderr, "freq[%d] = %d\n", align_start + i, align_freq[i]);
}
}
assert(align_pos != -1);
std::vector<std::tuple<double, int16_t, int>> good_a0;
std::vector<std::pair<double, int>> bestfit(KYBER_Q);
for (auto &[pearson, a_guess, align] : matches) {
if (std::abs(align - align_pos) > 1)
continue;
bestfit[a_guess] = std::max(bestfit[a_guess], {pearson, align});
}
for (int a_guess = 0; a_guess < KYBER_Q; a_guess++) {
auto [pearson, align] = bestfit[a_guess];
if (align == 0)
continue;
good_a0.emplace_back(pearson, a_guess, align);
}
sort(good_a0.begin(), good_a0.end());
reverse(good_a0.begin(), good_a0.end());
return good_a0;
}
std::pair<std::array<int16_t, 2>, int> SolveOne(size_t vec_idx, size_t idx,
int align_start) {
auto good_a0 =
FindCandidate(vec_idx, idx, 1, align_start); // fqmul(a[0], b[1])
fprintf(stderr, "a0 Total: %zu Max: %.6f Min: %.6f\n", good_a0.size(),
std::get<0>(good_a0[0]), std::get<0>(good_a0.back()));
auto good_a1 =
FindCandidate(vec_idx, idx, 0, align_start); // fqmul(a[1], b[0])
fprintf(stderr, "a1 Total: %zu Max: %.6f Min: %.6f\n", good_a1.size(),
std::get<0>(good_a1[0]), std::get<0>(good_a1.back()));
// good_a1 = {{1, 3080, 30}};
std::map<std::pair<int16_t, int16_t>, std::pair<double, int>> good_cross;
std::array<int16_t, 2> ans;
#pragma omp parallel for
for (auto [_p0, a0, a0align] : good_a0) {
for (auto [_p1, a1, a1align] : good_a1) {
if (a1align <= a0align)
continue;
auto begin = std::max(a0align, a1align) + 1;
auto end = begin + 5;
for (int add_align = begin; add_align <= end; add_align++) {
auto w = HammingWeightOfAdd(vec_idx, idx, a0, a1);
double pearson = gsl_stats_correlation(pm_matrix[add_align], 1,
w.data(), 1, kNSessions);
if (pearson > 0.6) {
#pragma omp critical(good_cross)
{
good_cross[{a0, a1}] =
std::max(good_cross[{a0, a1}], {pearson, add_align});
fprintf(stderr, "hitcross %d %d %d %d %d %.6f\n", a0, a1, a0align,
a1align, add_align, pearson);
}
}
}
}
}
double crossmaxx = -2;
int align_end = -1;
for (const auto [val, tans] : good_cross) {
auto [a0, a1] = val;
auto [pearson, add_align] = tans;
if (pearson > crossmaxx) {
crossmaxx = pearson;
ans = {a0, a1};
align_end = add_align;
}
}
fprintf(stderr, "Total: %zu Max: %.6f\n", good_cross.size(), crossmaxx);
return {ans, align_end};
}
} // namespace
int main(int argc, char *argv[]) {
if (argc < 3) {
printf("Usage: %s <data.json> <vec_idx>\n", argv[0]);
return 1;
}
LoadData(argv[1]);
int vec_idx = atoi(argv[2]);
int tail = 0;
if (vec_idx == 1)
tail = 3350;
for (int i = 0; i < 128; i++) {
auto [res, cur_tail] = SolveOne(vec_idx, i, tail);
fprintf(stderr, "Tail: %d\n", cur_tail);
printf("%d: %d %d\n", i, res[0], res[1]);
fflush(stdout);
tail = cur_tail + 1;
}
return 0;
}
Raw
2decode_flag.cc
#include <algorithm>
#include <cstdint>
#include <set>
#include <stdio.h>
#include <string.h>
#include <string>
#include <string_view>
#include <vector>
extern "C" {
#include "api.h"
#include "params.h"
#include "poly.h"
#include "polyvec.h"
#include "reduce.h"
#include "sha2.h"
}
const int16_t sk0[256] = {
775, 1834, 2279, 3188, 271, 1234, 2824, 2485, 754, 3280, 1314, 2805,
2227, 1722, 2229, 710, 815, 3056, 2631, 7, 2403, 364, 1113, 3232,
3121, 1432, 1076, 673, 1438, 180, 27, 403, 171, 1168, 8, 2863,
1568, 345, 2776, 1755, 998, 1311, 280, 2499, 2680, 1265, 292, 1792,
676, 725, 2485, 2018, 761, 2437, 1968, 1216, 3245, 2153, 2618, 1581,
602, 459, 1676, 1792, 3325, 1116, 813, 907, 725, 144, 800, 2375,
1702, 2732, 3236, 2341, 1240, 1055, 1026, 1209, 239, 238, 1936, 1928,
2834, 1377, 256, 2902, 2174, 2741, 444, 25, 3098, 1833, 160, 207,
1426, 1033, 450, 2964, 1052, 1141, 97, 2913, 2780, 2707, 516, 2668,
3014, 2109, 648, 278, 32, 3059, 1059, 2298, 2524, 2065, 2747, 3244,
2841, 3085, 644, 1929, 1524, 368, 740, 2882, 520, 409, 2559, 1653,
963, 76, 1099, 622, 121, 119, 590, 2448, 2693, 3327, 1609, 2230,
1386, 2252, 2005, 2708, 375, 90, 2248, 2929, 2423, 277, 2006, 1410,
2938, 1033, 1317, 907, 1330, 675, 752, 1897, 2968, 291, 1621, 529,
1753, 2397, 1569, 3035, 62, 604, 997, 3183, 1437, 1774, 1717, 247,
1637, 2173, 3233, 2364, 1471, 2318, 2309, 1761, 2145, 728, 163, 2804,
2669, 170, 2717, 933, 2038, 874, 2588, 610, 1663, 3291, 1444, 460,
1641, 1399, 2771, 1576, 2720, 3102, 629, 245, 193, 1478, 380, 590,
493, 1510, 1390, 1834, 1782, 2953, 2228, 1624, 3303, 179, 321, 77,
2210, 76, 3323, 2094, 2894, 640, 1476, 1580, 1027, 1854, 3235, 2647,
2606, 287, 854, 1450, 1647, 2299, 1606, 839, 3241, 2338, 254, 247,
1365, 1538, 2526, 3148};
const int16_t sk1[256] = {
308, 918, 2485, 92, 535, 1490, 3173, 1704, 409, 2116, 1647, 1080,
628, 2455, 1409, 1424, 1264, 2856, 1491, 2440, 2859, 2426, 950, 459,
2987, 2700, 1828, 2984, 2256, 468, 1833, 1718, 1093, 363, 1607, 2529,
196, 1003, 1891, 2165, 2244, 722, 587, 1114, 3130, 117, 2743, 747,
1510, 595, 628, 120, 3119, 1441, 604, 1868, 2313, 819, 2782, 2982,
1784, 1174, 1060, 870, 2909, 761, 1223, 977, 824, 739, 2771, 346,
2166, 1929, 2245, 3306, 2711, 767, 2205, 1567, 886, 2508, 1496, 1530,
883, 424, 1736, 1171, 2686, 1280, 1498, 50, 1998, 378, 2703, 729,
1113, 373, 479, 2030, 353, 371, 2258, 2237, 2113, 969, 3239, 1752,
678, 1794, 353, 2950, 937, 32, 1303, 559, 2922, 934, 252, 640,
1860, 3302, 1505, 2824, 2011, 2829, 60, 1802, 348, 170, 1202, 1343,
1062, 3031, 1028, 3307, 2263, 434, 1154, 1509, 1748, 667, 350, 559,
484, 2085, 321, 54, 2176, 1333, 1140, 661, 422, 1686, 181, 371,
869, 403, 1646, 3219, 1550, 2930, 2282, 2296, 2840, 2295, 1534, 455,
790, 2037, 3307, 3001, 2270, 837, 249, 683, 1319, 1585, 692, 1935,
3250, 41, 2864, 1634, 384, 2997, 730, 2482, 1713, 1392, 3227, 3086,
2838, 370, 2695, 2018, 2688, 3019, 191, 3153, 3174, 1340, 646, 591,
3293, 719, 2318, 2982, 2429, 810, 543, 1986, 1951, 1742, 2037, 2252,
2251, 1839, 1475, 2143, 2732, 1292, 3269, 2629, 2136, 3318, 1318, 17,
2332, 2208, 941, 1897, 1484, 2850, 3024, 3003, 2748, 1762, 2695, 3032,
1266, 2917, 195, 2054, 1226, 2452, 1746, 166, 41, 1266, 2851, 3318,
1390, 2281, 2009, 1178};
const uint8_t ct[PQCLEAN_KYBER51290S_CLEAN_CRYPTO_CIPHERTEXTBYTES] = {
0x6A, 0x94, 0x99, 0xD3, 0x0A, 0x4C, 0xEE, 0x8B, 0x18, 0x7B, 0x92, 0xEA,
0xD8, 0x35, 0x1A, 0x78, 0x7F, 0x9B, 0x80, 0x13, 0x1D, 0xDD, 0xAB, 0x1C,
0xB9, 0x90, 0x09, 0xCD, 0x25, 0x23, 0xF5, 0x47, 0xB1, 0x7B, 0x04, 0x89,
0xDD, 0x3D, 0x5E, 0xCB, 0xB7, 0x20, 0x2D, 0x3B, 0xFA, 0xE0, 0x80, 0x0A,
0xA3, 0x16, 0x80, 0x5A, 0x39, 0xDD, 0x9F, 0xFB, 0x8C, 0xAF, 0xBA, 0x7F,
0x10, 0x3D, 0xDD, 0x1E, 0x7D, 0x98, 0xB1, 0x54, 0xB0, 0x2F, 0x6D, 0xB1,
0xCC, 0x8D, 0x9D, 0x64, 0x0F, 0x5D, 0x80, 0x26, 0x46, 0x99, 0xAA, 0x67,
0x17, 0x70, 0x1C, 0x1B, 0x21, 0x29, 0x30, 0x53, 0xBE, 0x65, 0xF9, 0x06,
0x29, 0x12, 0xA4, 0x2B, 0x99, 0xA8, 0xD0, 0xE7, 0x93, 0xB3, 0x8C, 0x1A,
0x45, 0x2E, 0x55, 0x66, 0xBE, 0x0D, 0x93, 0xED, 0x07, 0xCB, 0xAC, 0xAA,
0x0C, 0x87, 0x28, 0xBE, 0xDB, 0xDF, 0xFA, 0x40, 0x8A, 0x02, 0x5C, 0xF4,
0x46, 0x55, 0x44, 0x78, 0x57, 0xBE, 0x09, 0x61, 0xA4, 0x99, 0x82, 0x87,
0x13, 0x37, 0xC6, 0x2A, 0xE3, 0xF7, 0x77, 0x4D, 0x1F, 0x12, 0xAE, 0xB3,
0xB6, 0x74, 0x20, 0x1B, 0x92, 0xB7, 0x9C, 0x1F, 0x70, 0x6E, 0x95, 0xD4,
0x15, 0x35, 0x93, 0xB0, 0xC4, 0xE9, 0xBB, 0x23, 0x4B, 0x54, 0x6A, 0x1D,
0x36, 0x1C, 0x55, 0x0D, 0x26, 0xF3, 0x43, 0xA9, 0xB5, 0x9D, 0x93, 0x2E,
0x79, 0xC0, 0xC3, 0x12, 0xCF, 0x84, 0x92, 0x91, 0x14, 0x16, 0xCA, 0xCB,
0xEF, 0x35, 0x6D, 0x11, 0x90, 0x58, 0xBD, 0xBE, 0x75, 0xB7, 0x5E, 0x42,
0x83, 0x00, 0x7F, 0x0D, 0x0C, 0xE2, 0x83, 0xDB, 0x20, 0xFD, 0x17, 0x8E,
0xF7, 0xB8, 0xDF, 0x22, 0xC5, 0xF0, 0xC4, 0xBD, 0xA6, 0xCE, 0x71, 0xEF,
0xF9, 0xDC, 0xA2, 0x7C, 0x7D, 0x00, 0x7E, 0x85, 0x87, 0xF8, 0xEB, 0x9E,
0xB8, 0x86, 0x5A, 0xD5, 0x58, 0xB1, 0x84, 0x64, 0xE9, 0xF0, 0xDD, 0xA5,
0x57, 0xB5, 0x20, 0xCE, 0x81, 0x53, 0xB1, 0x73, 0x6A, 0xFE, 0xD6, 0xDF,
0x7A, 0x41, 0xAE, 0xAB, 0x9F, 0x13, 0xCC, 0xA2, 0x60, 0x7E, 0xE3, 0x75,
0x19, 0xD1, 0x2D, 0xF4, 0x96, 0xCC, 0xAD, 0x48, 0x6A, 0x55, 0xB0, 0x7D,
0xF3, 0x22, 0xDF, 0xE0, 0x5C, 0x29, 0xC9, 0x67, 0x18, 0x34, 0x62, 0x3B,
0xFA, 0x09, 0x48, 0xB8, 0x27, 0x58, 0x2B, 0x6A, 0xC0, 0x16, 0x44, 0x36,
0x42, 0x4F, 0x77, 0x92, 0xC9, 0xC2, 0x1A, 0xEC, 0x07, 0xD0, 0xF3, 0x17,
0x87, 0xE4, 0x2B, 0x52, 0x14, 0xC8, 0xAF, 0x09, 0xE7, 0xBF, 0xA8, 0xD7,
0xC1, 0x36, 0x4D, 0x5F, 0x4D, 0x5E, 0x04, 0x53, 0xB2, 0xC7, 0x43, 0x01,
0xDC, 0x89, 0x54, 0x4A, 0x3B, 0x9A, 0x27, 0xC7, 0x27, 0x45, 0x81, 0x6F,
0x0C, 0x47, 0x9A, 0x9D, 0x88, 0xBD, 0xA9, 0x13, 0x68, 0x8D, 0x7D, 0xCE,
0x0C, 0x67, 0xA9, 0x86, 0xD3, 0xC7, 0x43, 0x09, 0x05, 0xA6, 0x30, 0xCB,
0x62, 0xE0, 0x6D, 0xD0, 0x93, 0xF7, 0x80, 0x5B, 0xF6, 0x8D, 0xC3, 0x68,
0x2A, 0xEF, 0xC7, 0xAE, 0xD5, 0x6F, 0x01, 0xC4, 0x65, 0x58, 0x8E, 0x12,
0x6B, 0xF5, 0x3F, 0xF8, 0x0A, 0xF7, 0x4B, 0x3E, 0x74, 0xFE, 0x8B, 0xA1,
0x42, 0xFB, 0xB9, 0x32, 0x16, 0xAF, 0xFC, 0x51, 0xE0, 0xD1, 0x78, 0x72,
0x5D, 0x85, 0x0E, 0xEF, 0xEC, 0x75, 0x57, 0xE6, 0x26, 0xB4, 0xD9, 0x0A,
0x58, 0x7D, 0xC5, 0x84, 0x12, 0xE2, 0x74, 0xD8, 0xD8, 0x09, 0x25, 0x03,
0x99, 0x93, 0x2C, 0x48, 0xC7, 0xB9, 0x1E, 0x34, 0xDD, 0xEB, 0xCD, 0xBA,
0x2C, 0x11, 0x5C, 0xBD, 0x59, 0x16, 0x5C, 0xCE, 0x69, 0x2E, 0x32, 0x9C,
0x6C, 0xE9, 0x33, 0xEB, 0x95, 0x8E, 0x39, 0x96, 0x4F, 0x1B, 0x6D, 0x06,
0x4E, 0x33, 0x8F, 0xA3, 0x63, 0x14, 0x61, 0xE1, 0xD1, 0xB2, 0xE7, 0x8D,
0xD5, 0xE3, 0x27, 0xE6, 0x1C, 0xF9, 0x9E, 0x34, 0x7F, 0x5B, 0x67, 0xB0,
0x93, 0x99, 0x00, 0xDB, 0x45, 0xD7, 0xD1, 0x41, 0xDC, 0x5D, 0x71, 0x1C,
0xAC, 0x67, 0x72, 0x85, 0x9D, 0x83, 0x02, 0x04, 0xB7, 0x8F, 0x5D, 0x54,
0x81, 0x94, 0xD6, 0xCD, 0xB6, 0x45, 0xD6, 0xB8, 0x95, 0x02, 0x8F, 0x30,
0xCB, 0xCC, 0x3F, 0x34, 0x2B, 0xD1, 0x22, 0xD3, 0x48, 0xCA, 0x7E, 0xE5,
0xED, 0xE3, 0xA5, 0xAA, 0x86, 0xFA, 0xF5, 0x32, 0x71, 0xF6, 0x24, 0x62,
0xF9, 0x69, 0x27, 0xF7, 0xAB, 0xEE, 0x03, 0x31, 0x95, 0x1F, 0x7D, 0x65,
0x67, 0x8B, 0x4B, 0xCB, 0x6D, 0x7E, 0x90, 0xE0, 0x47, 0x82, 0x5E, 0x19,
0x1F, 0x24, 0x8C, 0xE8, 0x26, 0x10, 0x1D, 0x87, 0x41, 0xE2, 0x35, 0x0E,
0x1C, 0x3C, 0x2D, 0x8C, 0x63, 0xD3, 0x6E, 0x22, 0xFB, 0xDA, 0xC7, 0x26,
0x37, 0xC5, 0x96, 0xA4, 0xA5, 0xC8, 0x5C, 0x61, 0x3F, 0x73, 0x76, 0x9F,
0xF2, 0x0C, 0x0C, 0x69, 0x89, 0xB9, 0xEA, 0x28, 0xBE, 0x42, 0xD1, 0x24,
0x16, 0xC5, 0x2B, 0xEF, 0x73, 0xBF, 0x71, 0xAE, 0x2A, 0x7F, 0x17, 0xB8,
0x80, 0x5A, 0xE6, 0xB8, 0x3A, 0xF1, 0x7F, 0x58, 0xE7, 0xC6, 0xAB, 0x15,
0x9A, 0x51, 0xA6, 0xA3, 0x8F, 0xC8, 0x78, 0xE8, 0xAE, 0xF9, 0x52, 0x8F,
0x6C, 0x3B, 0x84, 0x7B, 0xE7, 0x48, 0x85, 0xD0, 0x70, 0x90, 0x93, 0xDA,
0x26, 0xFD, 0x5F, 0x35, 0x9D, 0x62, 0xA6, 0xEC, 0x8A, 0x1B, 0xD4, 0x2D,
0x7C, 0x63, 0x36, 0x93, 0x2F, 0x35, 0x35, 0x74, 0xF7, 0x07, 0x65, 0xE8,
0xED, 0x35, 0x5F, 0x1C, 0x94, 0x1C, 0x0A, 0xE0, 0xE9, 0x18, 0x11, 0xEB,
0x06, 0xE2, 0x6B, 0xEC, 0x35, 0x87, 0x25, 0xE2, 0x1B, 0x16, 0x5B, 0x71,
0x5D, 0x9B, 0x1B, 0x6E, 0x31, 0xEA, 0xFE, 0x4B, 0xDA, 0x30, 0x28, 0x9D};
const uint8_t flag_xor_ss[PQCLEAN_KYBER51290S_CLEAN_CRYPTO_BYTES] = {
0x0E, 0xE5, 0x27, 0xE2, 0x4A, 0x22, 0x7C, 0x73, 0x85, 0xF4, 0xE3,
0x4D, 0x81, 0x2C, 0xAC, 0x4B, 0xF0, 0x98, 0xAC, 0x64, 0x7E, 0xAC,
0xA9, 0x73, 0xED, 0x47, 0x7F, 0xA0, 0x60, 0x7B, 0xBE, 0x24};
const unsigned char pk[800] = {
0x31, 0xEA, 0xCE, 0x14, 0x54, 0x30, 0x1E, 0xDA, 0x7C, 0x49, 0xCC, 0x67,
0x75, 0x24, 0x0E, 0xE3, 0xE4, 0xCF, 0x74, 0x22, 0xB5, 0xD3, 0x76, 0x9E,
0x0B, 0x27, 0xBD, 0x6A, 0x98, 0xA7, 0x63, 0xEA, 0xC1, 0x5A, 0x08, 0x6C,
0x6C, 0x11, 0xB7, 0x2F, 0x83, 0x8C, 0x32, 0x64, 0xAD, 0x91, 0x2B, 0x1D,
0x3D, 0x55, 0x21, 0x6F, 0x80, 0x12, 0x1A, 0x77, 0x43, 0x61, 0xEA, 0xCA,
0x0D, 0xC2, 0x3E, 0xE0, 0x37, 0xA5, 0x79, 0x5A, 0xAE, 0x88, 0xE9, 0x7C,
0xAE, 0x1B, 0x26, 0x38, 0x58, 0x0E, 0x25, 0x3A, 0x95, 0xDD, 0xC1, 0x41,
0xF0, 0xA6, 0x9C, 0x1E, 0xFB, 0x1D, 0x52, 0xE1, 0x8A, 0x99, 0xD4, 0x56,
0x92, 0xF2, 0x7F, 0x7B, 0x56, 0xA1, 0xF0, 0x41, 0x30, 0x1C, 0x42, 0x3A,
0xED, 0x46, 0xC6, 0x1E, 0x06, 0x11, 0x8C, 0xA8, 0xCD, 0x39, 0xD8, 0x1D,
0x89, 0x72, 0x2D, 0xBB, 0x88, 0x8E, 0x5D, 0x28, 0x4B, 0xFF, 0xE1, 0x5D,
0xF8, 0x92, 0xAE, 0xCE, 0x88, 0x5E, 0x74, 0x46, 0x5E, 0xF1, 0xF5, 0x6A,
0x63, 0x21, 0x61, 0x88, 0x6B, 0xB4, 0xB3, 0xF6, 0x6B, 0x00, 0x80, 0xCA,
0x4C, 0xCA, 0x2B, 0x9F, 0x20, 0x8E, 0xDB, 0x30, 0x71, 0xCF, 0x23, 0x39,
0x46, 0xD0, 0xB8, 0x71, 0x16, 0x8A, 0x0E, 0x66, 0x33, 0xBC, 0x64, 0x38,
0xE5, 0x97, 0x98, 0x0D, 0x46, 0xA9, 0x92, 0x7A, 0x09, 0xD0, 0xCB, 0x73,
0xC3, 0x00, 0xC0, 0xE3, 0xAB, 0xB6, 0xD3, 0xD8, 0x69, 0x4D, 0x91, 0x80,
0x09, 0x54, 0x70, 0xDC, 0x56, 0x43, 0xCA, 0x45, 0x72, 0xEE, 0x62, 0x79,
0x25, 0x71, 0x6A, 0x6D, 0x83, 0xAC, 0x6F, 0xB8, 0x7A, 0x74, 0xE1, 0xC3,
0xB3, 0xF5, 0x72, 0x3A, 0x3A, 0x6C, 0x4D, 0x46, 0x9F, 0xD7, 0xA8, 0x6F,
0x44, 0x73, 0x7F, 0x02, 0xCA, 0x0E, 0xFF, 0x30, 0x50, 0xB4, 0xD5, 0x07,
0x74, 0xCC, 0x54, 0x65, 0xA8, 0xB7, 0x1A, 0x8C, 0x61, 0xC1, 0xFC, 0x81,
0x54, 0x65, 0x56, 0x8F, 0x79, 0xAC, 0x0F, 0x50, 0x4C, 0x99, 0xF9, 0xC8,
0xE7, 0x09, 0x3A, 0x0F, 0xCC, 0x33, 0x63, 0x40, 0xC6, 0x40, 0x45, 0xA9,
0x61, 0x24, 0x68, 0x08, 0x9B, 0xAF, 0xC8, 0x2C, 0x2A, 0x4F, 0xDA, 0x84,
0xE5, 0x89, 0xA9, 0xA1, 0x4A, 0xC5, 0x47, 0x37, 0x58, 0xF7, 0x91, 0x5E,
0x75, 0x64, 0x7C, 0xF5, 0xF1, 0x97, 0x89, 0x99, 0x48, 0x73, 0xBB, 0x33,
0xB1, 0x22, 0x9F, 0x49, 0x93, 0x64, 0x00, 0xDA, 0x64, 0x92, 0xA6, 0x8D,
0x89, 0xDA, 0x46, 0xED, 0x58, 0x1E, 0x07, 0x36, 0x97, 0x47, 0x62, 0x0F,
0xAB, 0xAC, 0x63, 0x1B, 0x08, 0x60, 0xD7, 0x41, 0x4B, 0xEA, 0x07, 0xAE,
0xA0, 0x1C, 0x1C, 0x48, 0x71, 0x9A, 0x7A, 0x85, 0x54, 0xD7, 0x70, 0x43,
0x44, 0x38, 0x73, 0xC1, 0x10, 0x5D, 0x38, 0xE7, 0x2E, 0xA0, 0x38, 0x76,
0x0A, 0x56, 0x85, 0xDE, 0x73, 0xC3, 0xDB, 0xF9, 0x94, 0x34, 0x0C, 0xB3,
0xDE, 0x0B, 0xA5, 0xD0, 0x63, 0x2A, 0x3B, 0x98, 0x7E, 0x16, 0xAB, 0x3F,
0x04, 0xE3, 0x48, 0x79, 0x51, 0x77, 0x2A, 0x95, 0x82, 0xC4, 0x95, 0x75,
0xBE, 0x5A, 0x36, 0xD3, 0x84, 0xC5, 0xC5, 0x46, 0x36, 0x47, 0xCB, 0xB1,
0xBF, 0xE9, 0xAB, 0x97, 0x09, 0x23, 0xAE, 0x41, 0x7A, 0x9D, 0x94, 0x2E,
0xB5, 0x75, 0xC9, 0x03, 0x5A, 0x97, 0x9E, 0x71, 0x86, 0x81, 0x69, 0x34,
0x99, 0xC7, 0xCA, 0x19, 0xF1, 0x17, 0x27, 0x02, 0x2F, 0x01, 0x76, 0x57,
0xB8, 0xB3, 0x31, 0xA3, 0x21, 0x24, 0xD2, 0xD4, 0x91, 0x9D, 0x48, 0x0A,
0xE0, 0xEC, 0x04, 0x37, 0xB5, 0x64, 0x1E, 0xD3, 0xC5, 0xF2, 0x31, 0x68,
0xCB, 0x78, 0xA1, 0x73, 0xC9, 0x95, 0x48, 0xB5, 0x7B, 0x7B, 0xC7, 0xC0,
0x8C, 0x46, 0x57, 0x0A, 0x39, 0x3C, 0x47, 0x97, 0x71, 0xE4, 0xD5, 0x12,
0xBD, 0x20, 0x66, 0xC4, 0x2B, 0x6F, 0x14, 0xC6, 0xB5, 0x79, 0xFC, 0x17,
0x37, 0x00, 0x0A, 0xCA, 0x72, 0x8C, 0xC9, 0xC3, 0x02, 0x01, 0x64, 0x69,
0x3A, 0x93, 0x32, 0xC6, 0xDA, 0x1B, 0x26, 0x07, 0x15, 0x01, 0xF4, 0x2C,
0xED, 0x79, 0x4F, 0xD7, 0x28, 0xA6, 0x92, 0x0A, 0x8B, 0xEE, 0xD7, 0x66,
0xC3, 0xA8, 0x6E, 0x1D, 0xF9, 0x22, 0xA7, 0x2A, 0x0C, 0xC8, 0xC0, 0x3A,
0xE1, 0xAC, 0xC4, 0x47, 0x82, 0x81, 0xD6, 0xA5, 0x42, 0xB1, 0x4B, 0x88,
0x41, 0x14, 0x7C, 0x6A, 0x32, 0x17, 0xB5, 0xE1, 0x1A, 0x16, 0xA1, 0x98,
0x76, 0x59, 0xA4, 0x03, 0x9B, 0xB9, 0x5E, 0x79, 0x11, 0x3C, 0xA0, 0x40,
0xEA, 0xC0, 0x09, 0x44, 0x77, 0xBA, 0x7F, 0xD3, 0x3C, 0xF5, 0x26, 0x8B,
0x2F, 0xE2, 0x30, 0x01, 0x9A, 0x50, 0xD8, 0x7A, 0xB1, 0x45, 0x58, 0xAF,
0xAB, 0xD6, 0x40, 0x37, 0x52, 0x50, 0x85, 0xA0, 0xCA, 0x05, 0x05, 0xA3,
0xA9, 0xBC, 0x50, 0x79, 0x00, 0xC0, 0x9F, 0x5C, 0x33, 0x7B, 0xA8, 0x2C,
0x60, 0xCB, 0x24, 0x59, 0xCB, 0x9D, 0x27, 0x14, 0x99, 0xCB, 0x39, 0x1A,
0x82, 0x1B, 0x60, 0xAF, 0x84, 0x71, 0x97, 0x6B, 0x2D, 0xA0, 0xF0, 0xCC,
0xA4, 0x8B, 0x5E, 0xB9, 0x12, 0xBE, 0xD5, 0xB5, 0x62, 0x8A, 0x57, 0x87,
0x34, 0x69, 0x3B, 0xA3, 0x22, 0x73, 0xD2, 0x31, 0x47, 0x08, 0x95, 0x0F,
0x12, 0xCA, 0xA1, 0xC7, 0xC1, 0x2B, 0x49, 0x35, 0xBB, 0x58, 0x95, 0x19,
0x68, 0x84, 0x2D, 0x19, 0x52, 0x41, 0x43, 0x04, 0x56, 0xBD, 0xA2, 0x9C,
0xB8, 0x08, 0x1B, 0x8C, 0x74, 0x00, 0x01, 0x02, 0x1F, 0x86, 0x06, 0x38,
0x29, 0x93, 0x8F, 0xAA, 0xF6, 0x00, 0xDE, 0x48, 0x7E, 0x7B, 0x14, 0x3D,
0x7C, 0x47, 0x8E, 0xB5, 0xB3, 0x43, 0x0A, 0xD6, 0x7B, 0x63, 0xC2, 0x7D,
0x3A, 0xA1, 0x05, 0x70, 0xD4, 0x3F, 0xCA, 0x67, 0x9C, 0x5F, 0x1D, 0xE6,
0xF0, 0xD1, 0x4A, 0x5D, 0xFA, 0x60, 0x1A, 0x39, 0x21, 0xBC, 0xEB, 0x67,
0x88, 0xC7, 0x71, 0x99, 0xC6, 0xE1, 0x8D, 0xF5};
int main(int argc, char *argv[]) {
uint8_t packed_sk[PQCLEAN_KYBER51290S_CLEAN_CRYPTO_SECRETKEYBYTES] = {0};
polyvec sk;
memcpy(sk.vec[0].coeffs, sk0, sizeof(sk0));
memcpy(sk.vec[1].coeffs, sk1, sizeof(sk1));
PQCLEAN_KYBER51290S_CLEAN_polyvec_tobytes(packed_sk, &sk);
memcpy(packed_sk + KYBER_INDCPA_SECRETKEYBYTES, pk, sizeof(pk));
sha256(packed_sk + KYBER_SECRETKEYBYTES - 2 * KYBER_SYMBYTES, pk, KYBER_PUBLICKEYBYTES);
// test the key
uint8_t test_ct[PQCLEAN_KYBER51290S_CLEAN_CRYPTO_CIPHERTEXTBYTES];
uint8_t test_ss[PQCLEAN_KYBER51290S_CLEAN_CRYPTO_BYTES];
PQCLEAN_KYBER51290S_CLEAN_crypto_kem_enc(test_ct, test_ss, pk);
uint8_t dec_ss[PQCLEAN_KYBER51290S_CLEAN_CRYPTO_BYTES];
PQCLEAN_KYBER51290S_CLEAN_crypto_kem_dec(dec_ss, test_ct, packed_sk);
if (memcmp(test_ss, dec_ss, sizeof(test_ss)) != 0) {
puts("FAIL");
return 1;
}
uint8_t ss[PQCLEAN_KYBER51290S_CLEAN_CRYPTO_BYTES];
PQCLEAN_KYBER51290S_CLEAN_crypto_kem_dec(ss, ct, packed_sk);
char flag[33] = {0};
for (int i = 0; i < 32; i++)
flag[i] = ss[i] ^ flag_xor_ss[i];
puts(flag);
return 0;
}
Raw
Makefile
BINARY = solve
CC = gcc
CXX = g++
LD = g++
PQCOMMON = firmware/third_party/PQClean/common
KYBER = firmware/third_party/PQClean/crypto_kem/kyber512-90s/clean
OBJS += $(PQCOMMON)/aes.o $(PQCOMMON)/sha2.o $(PQCOMMON)/randombytes.o
OBJS += $(KYBER)/cbd.o $(KYBER)/indcpa.o $(KYBER)/kem.o $(KYBER)/ntt.o
OBJS += $(KYBER)/poly.o $(KYBER)/polyvec.o $(KYBER)/reduce.o $(KYBER)/symmetric-aes.o $(KYBER)/verify.o
CFLAGS += -O2 -ggdb -fopenmp
CFLAGS += -I$(KYBER) -I$(PQCOMMON)
LDFLAGS =
LD_LIBS = -lgsl -fopenmp -lgslcblas
all: solve genkey
%.o : %.c
$(CC) -c $(CFLAGS) $< -o $@
%.o : %.cc
$(CXX) -std=c++17 -c $(CFLAGS) $< -o $@
solve: $(OBJS) solve.o
$(LD) $(LDFLAGS) $(OBJS) solve.o $(LD_LIBS) -o solve
genkey: $(OBJS) genkey.o
$(LD) $(LDFLAGS) $(OBJS) genkey.o $(LD_LIBS) -o genkey
decode_flag: $(OBJS) decode_flag.o
$(LD) $(LDFLAGS) $(OBJS) decode_flag.o $(LD_LIBS) -o decode_flag
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment