Qual

ASCIS 2023 QUAL

CRYPTOGRAPHY WRITEUP

Author:

  • Pham Quoc Trung

Used Language:

  • Python3

Problem Solving

Crypto Gym

Welcome to crypto gym. First thing first, do 10 pushup

Attachment: pushup.sage

from Crypto.Util.number import *

flag = b"ASCIS{W3llDone_hitting_the_crypto_gym}"
p = random_prime(2^64,False,2^63)
k = 100
N = p^k
R.<x> = PolynomialRing(Zmod(N), implementation="NTL")

pol = R([getrandbits(303) for _ in range(8)])
rem = pol(bytes_to_long(flag))
pol2 = pol - rem

print(p)
print(pol2)

output.txt

11297687362481059303
13610397498137460052595710607775600966440673986561720083617038392214152560062011019976773770*x^7 + 3566392303389726626006032793588065859583087165101596345460586029577767956788324980852746288*x^6 + 7227318468293576946551014881082996672111192766111924180025635102400282562890972644421351500*x^5 + 7771302680925353252595662292109560220768956546753457049454904993425020919927767061221486221*x^4 + 139083310005991713122570444648981888435044361344964087355309478527640012858625517580301911*x^3 + 10431965883129539716182417642690446218733007501683833779007525409139657460951379770712373102*x^2 + 2655891997688433325155635727515206873804011670907688662530856511275429726187800190339210214*x + 1990468213382663050992514193186549986027466683418508635770777413817551279002416425502329820086861584095472837291418005624773513401408758670436382582234048163799788806226626593153501000046514398963951902046012093096889627829382025385675885186988109953010009115770485200550815315808412991631351114821645247484757612802395935646091741255310372634948676346139337203740284867648614092382676490768142323752125479973383639263480304615000184481073131150356830470611732683436270896044490259474247417693471208508957222774925150961910011882960781392579006359531632257744162604999333815810546399453824586710812096069645634464088126006346744764154042984373078867489476719514098331516466106097935211336674536065610816999665679040973651579582751231452003697987383534147985850684095100628612367594611200815680857874889854961710361062023098850129552718682182379299432474772126322312705937896898977384049986981576727484443307309856882552658648662622011836915288387316856549038216691517631404710419267570370185868331551998817164408824273037138508139872246840469178118447891408840689533252470570577069433326089871730774552442047182123932923084697422550196675689928558048170639744494377903971022314792618672680983240190918645044793065660686668847439068894202593794701984461427031780284501758478606643641114708694491715239872860200373088774910354567584766353453900023065619777887852835339101628894266209543584386397885981697802413486043807559982651878851431362770011433278158871282099680537195876295632087913919009624832811111375020850262854356800201139600896028683597688967045073054430644328634631654532540097138840888709833107492434165723295378716876382870562787875916326125400715648718443161316211216677436938376005080710347157377831498391277043220453740841631935922506793862323094941018556991395626031998291221412221183144473483101854286315619799724635496211825342536058324502706123278966607771777568594929815999891921492775

Bài này flag nằm luôn trên file source nên mình cũng chả cần phải làm gì :v. Sẽ nghiên cứu sau.

Flag: ASCIS{W3llDone_hitting_the_crypto_gym}

I_dont_know_how_to_name_this_chall

This is a description. Good luck

Attachments: chall_fixed.sage

from Crypto.Random.random import getrandbits
from Crypto.Util.number import bytes_to_long

nbits = 128
while True:
    mul = getrandbits(nbits)
    add = getrandbits(nbits)
    modulus = getrandbits(nbits)
    if mul < modulus and add < modulus:
        break

def gen_num(bits):
    truncate = bits
    seed = getrandbits(511)
    gen_num = 41

    xx = []
    yy = [] 
    
    for _ in range(gen_num):
        seed = (mul * seed + add) % modulus
        xx.append(seed)
        yy.append(seed >> (nbits-truncate))
    return xx, yy

_, ee = gen_num(18)
_, ff = gen_num(20)

a = ee[-1]
b = ff[-1]
c = getrandbits(1024)
p = next_prime(a * c + getrandbits(512))
q = next_prime(b * c + getrandbits(512))

flag = '<REDACTED>'
N = p * q
e = 65537
m = bytes_to_long(flag.encode())
enc = pow(m, e, N)

print(f'enc = {enc}')
print(f'N = {N}')
print(f'ee = {ee[:-1]}')
print(f'ff = {ff[:-1]}')
print(f'a = {mul}')
print(f'c = {add}')
print(f'm = {modulus}')

output.txt

enc = 4782207738169357679017263311695366580149461241803922088835452812820137537830281562950634059939171784035642202164746425519370563906663225547286363495366866588141853586109553019469599011984795232666657032457349167541183811442599555965876853759790930565452169138123206051344200109808603093521161556603615660329142949615063443855551027286822234646698015310643407246009689006200152818931447476595216569044114220319818061396623338764899012025923470408152189436065437542065068815744124506169026323905222443334212867601172364249248963768649488580249031694113977946046461290930755706144535271632419505875554486279354334709794323960679
N = 3964970058588757148381961704143056706462468814335020245520977895524549102412775370911197710398920529632256746343939593559572847418983212937475829291172342816906345995624544182017120655442222795822907477729458438770162855927353619566468727681852742079784144920419652981178832687838498834941068480219482245959017445310420267641793085925693920024598052216950355088176712030006651946591651283046071005648582501424036467542988971212512830176367114664519888193885765301505532337644978456428464159474089450883733342365659030987687637355512103402573155030916404165387863932234088255017821889649456947853403395704387479968208359004918561
ee = [167323, 194700, 130745, 7156, 65616, 200175, 106106, 4410, 94204, 121719, 176084, 168449, 206162, 19151, 165232, 149276, 151372, 64105, 162906, 92391, 69021, 200382, 22272, 14195, 200195, 70505, 46059, 194712, 177080, 209749, 112239, 9882, 23285, 45783, 117745, 31663, 51641, 148822, 169539, 142669]
ff = [300710, 494582, 107979, 208491, 285026, 638043, 525064, 566864, 36622, 212388, 374138, 220683, 193612, 532230, 75887, 548412, 650282, 195040, 74550, 158762, 797511, 322315, 821880, 484339, 76864, 64394, 101586, 815915, 762307, 410750, 115213, 726390, 378350, 800132, 379035, 797320, 413506, 284265, 537835, 226489]
a = 43787291635671214792919526096167649451
c = 156497500579206068939331641182566791023
m = 273364800599018888270443304662600024273

Nhìn vào code của chương trình, ta có thể nhận ra ban đầu nó đã sử dụng LCG (Linear congruential generator) để tạo ra các số giả ngẫu nhiên. Ở đây ngoài các thông số của LCG như $m$, $a$ và $c$ ra, ta còn thấy sự xuất hiện của biến truncate, phục vụ cho phép dịch phải. Đây là biểu hiện của dạng Truncated LCG.

Vì các biến phục vụ cho mã hóa RSA đằng sau phụ thuộc vào phần tử cuối của mảng được sinh ra từ LCG, thứ mà ta không biết. Để lấy được, ta phải gen lại cả mảng bằng cách break được thuật toán Truncated LCG này. Ở đây mình tìm được 2 nguồn giúp mình thực hiện điều này

  • https://github.com/jvdsn/crypto-attacks/tree/master/attacks/lcg

  • https://gist.github.com/maple3142/c7c31d2e5893d524e71eb5e12b0278f0#file-truncated_lcg-py

let's duel

I really want to play MTG with someone.

Attachments: chall_fixed_final.py

from hashlib import *
import os
from Crypto.Util.number import *


q = 2^32 - 5
n = 256
def bytes_to_seedlist(seedbytes):
    seedlist = []
    for i in range(16):
        seedlist.append(bytes_to_long(seedbytes[i*4:i*4+4]))
    return seedlist

def sample_poly(seed , lower , upper):
    prng = PRNG(seed)
    polylist = []
    for i in range(n):
        polylist.append((prng.raw_rand() % (upper - lower)) + lower)
    return polynomial(polylist)
def encode_m(m):
    m = bytes_to_long(m)
    flist = []
    for i in range(n):
        flist = [m&1] + flist
        m >>= 1
    return polynomial(flist)

class PRNG:
    def __init__(self , seed):
        self.state = bytes_to_seedlist(seed)
        
        self.m = 8723550600886591460
        # f = [randint(0 , self.m) for _ in range(16)]
        self.f = [385590684360, 111617452318, 131804337312, 300824916689, 419524791075, 690238874924, 160408772216, 63764520785, 50573686124, 688400902026, 333066488215, 270710580449, 107293144053, 703516825252, 541402940593, 624566048630]
        self.d = 16
        for i in range(self.d):
            self.generate()
    def generate(self):
        res = 0
        for i in range(self.d):
            res += self.f[i] * self.state[i]
            res %= self.m
        self.state = self.state[1:] + [res]
    def raw_rand(self):
        temp = self.state[0]
        self.generate()
        return temp

class polynomial:
    def __init__(self,flist):
        n = 256
        if type(flist) == list:
            assert len(flist) == n
            self.f = [flist[i] % q for i in range(n)]

    def __add__(self , other):
        assert type(other) == polynomial
        return polynomial([(self.f[i] + other.f[i])%q for i in range(n)])
    def __sub__(self , other):
        assert type(other) == polynomial
        return polynomial([(self.f[i] - other.f[i])%q for i in range(n)])
    def __mul__(self , other):
        assert type(other) == polynomial
        res = [0 for _ in range(n)]
        for i in range(n):
            for j in range(n-i):
                res[i+j] += self.f[i] * other.f[j]
                res[i+j] %= q
        for j in range(1, n):
            for i in range(n-j, n):
                res[i+j-n] -= (self.f[i] * other.f[j])
                res[i+j-n] %= q
        return polynomial(res)

flag = b'<REDACTED>'
assert flag[:8] == b'ASCIS{it' and flag[-1:] == b'}' and len(flag) == 32
print(f'hash_list: {list(map(lambda x: sha256(x).digest(), [flag[i:i+5] for i in range(0, len(flag), 5)][:-1]))}')

A = sample_poly(os.urandom(64) , 0 , 2**32 - 5)
e = sample_poly(os.urandom(64) , -4 , 4)
s = encode_m(flag)
b = A*s + e
print(b.f)
print(A.f)

output.txt

hash_list: [b'\xb6\xb1\xdahR\xef\xb5\xc4\x96\xc9\x87\xe3;K\xf2|(\xc2?\x8b\xd3B\xdc\xc7\x13\xd2\x82[=\xa9\xc3\xfb', b'\xb0"\x8fl8\xc0Z1\x97\x88ct\x8a\xf1\xea\xc8.\xe0Q=\x0e\xd9\x86\xbc\x89\xc2\xbb\x9dT\xc6}Z', b'\xc1\x9d\x81\xe4\xed\xaa\x8a\xa0\xb6\xcb\x15\xc6\xd2yv\x1f\x8f\xac\x839\xa4&}\x1c\xa8\xc3\x15"\x87r!\xe2', b'\xf26\x95*\x0c\xd2\xca\xd8xE\xbf\xf3P \xcc\xd7l\xebx\xdcW\xb2\x8e\x06\xfa\xd7r\xc0~\xdf\x18`', b'\x1f\xfa>\xea\xe2{-\x13:\xfe,`\x01j\xec\xa0\x15hl\xa5\\\x88\x9eQ[\x12\x1es7\xe3w\xa5', b"'cE\x04\xae\x04\x88\xdb\xe6\x0b\x9b}\xf7\x1d]\xedH\xf3:|\x12s\x0f\xc2\xa1v\xa2k\xf4\xbazJ"]
[4283545680, 646834737, 741988181, 3020304857, 3100253413, 1065061328, 3013693513, 3106959241, 2155350166, 1545834191, 790968817, 2015602796, 2973360521, 1871688489, 2744199016, 3790735376, 137555270, 1278025029, 3802308861, 3114891940, 3957760227, 2039267510, 2555990791, 564591932, 844115070, 709763793, 1413511597, 3223782810, 3762408596, 3237568557, 1506656324, 640118751, 3457884507, 2042392508, 3621570353, 2618427178, 3143980384, 4179375357, 2455473338, 3743578199, 1107663085, 1166269545, 349593668, 4275247796, 1262422354, 1739848908, 614386809, 3276667439, 1909302811, 2207910705, 3672171769, 1892473412, 2106619998, 3509534363, 4127643740, 3112406324, 717870202, 2851994732, 3003228494, 4016914585, 570223354, 3624435932, 205090202, 2012416867, 192505113, 3114220319, 1331292762, 479841116, 3516641914, 3685321945, 2143251094, 2590283404, 9811749, 2657687045, 4259037014, 1860067004, 2127021357, 3299398789, 3177792605, 3096187832, 617393158, 3105265865, 3200579500, 2180602657, 405538436, 2523765308, 4240756384, 1314900414, 583358099, 3101348135, 136786442, 2140102983, 360275303, 753809702, 2492856611, 2824277079, 2542382957, 304365097, 1407108023, 179330351, 3572907626, 2987119926, 1837821380, 4255503888, 4150911130, 1079223198, 382550547, 440445936, 429398418, 4269223853, 4293378325, 831535779, 1122173200, 916028602, 2063630491, 397805198, 1714268681, 3482358218, 1527006125, 972019432, 1178792742, 321122436, 1198282426, 4248922335, 1636504259, 1182244646, 1110957456, 3147355806, 2131582789, 816066497, 4212311714, 4189493964, 2888766800, 23922410, 988643330, 1734233855, 3610553547, 2881678944, 413335320, 605483264, 1226557747, 3998585106, 2761250861, 1388516116, 348565449, 1310945281, 2665014408, 3904323348, 3116210769, 371569431, 859621792, 3873282560, 3657629936, 2165332329, 3648500937, 1596125288, 4030977678, 3234029944, 3045811717, 495499658, 2773559501, 2326382782, 3221402806, 3005901931, 977057418, 2320593952, 2794811414, 711422896, 4281286089, 3466560539, 190173095, 3948641737, 1556799426, 3931257454, 1354240466, 2986326087, 4256860762, 3241117779, 640856507, 3473767594, 1713562536, 3684876849, 4017806788, 3077145772, 2824616513, 2935055408, 1623945766, 315873716, 102609950, 419009459, 1963388852, 3699184121, 794095422, 1786769052, 1636765552, 1268289826, 3988009796, 3507703205, 277522927, 3281391735, 3061479622, 2054288077, 320590104, 1155984065, 2345911582, 1311189685, 2417274203, 3663636979, 1355104029, 954525006, 1565182940, 2623166114, 2244058414, 4169012576, 3794090017, 3378386621, 3977599826, 2957395261, 2268921055, 1035839318, 39266986, 4127340185, 3213795177, 2648382777, 2574807466, 1859819418, 724070108, 2468329063, 519293835, 3786683045, 2138218831, 1129997749, 3957889649, 1690256184, 1279827160, 906462778, 337831463, 3731171015, 3668852053, 220581961, 288435651, 2016496414, 4130330054, 1731113030, 1951965858, 10770410, 639445397, 3043395505, 1900552693, 389764505, 902374272, 2347510467, 4180730265, 1161045967, 3252278061, 1005098266]
[287970464, 2164888233, 3900314872, 2803578471, 2100597265, 1816431874, 3107577409, 2442807705, 521828921, 3057968421, 4139887361, 4264789592, 2948288356, 804210161, 669029890, 3126041531, 1423738442, 590110291, 1673973318, 295613802, 3783064449, 901463863, 3903514026, 1296050662, 4273758939, 4100859588, 668993132, 64546990, 131928633, 2595095688, 610213244, 3054956557, 2993694188, 2498770917, 1402362082, 3632530868, 649841672, 1843661157, 786836159, 2485753489, 2839031237, 3731848071, 2817378681, 3403169521, 2015560787, 1822700770, 161085328, 286530859, 4130325360, 1390298514, 865328090, 60541228, 655193450, 3851091442, 4281910285, 745346163, 50447794, 3922986170, 2367251329, 988621856, 3722976714, 3538009554, 213747765, 1299739489, 3466643630, 370290663, 2976632085, 3044010057, 3168989507, 2278979483, 922376384, 2082045756, 784991240, 2824840459, 1611316601, 1606912636, 136325361, 1489816993, 3045086708, 3764326204, 1475244981, 629654012, 1988643969, 3286999466, 3195304933, 1606659017, 736848220, 2158974982, 347685569, 332414878, 207979890, 3372005421, 298012257, 2758990980, 3310277688, 349598758, 2378166773, 1464638028, 3273217830, 3763703130, 1389744097, 714695881, 1685453463, 3570078034, 1037471531, 3873616449, 951661170, 2805305208, 2306223616, 3687866993, 3305452882, 4260765485, 1742500231, 2390392028, 2943743112, 1502774651, 2456351616, 3308830006, 4192023258, 932695074, 1267048809, 2563600344, 3204565645, 4149110498, 2804299962, 163720842, 3742370816, 3487079987, 3312120468, 2779130485, 2412143335, 154330399, 3282001667, 494563132, 299113042, 4027004917, 328155934, 2637548213, 1565335384, 3995545006, 1061013616, 3931901355, 2526277849, 63039371, 947719144, 4204710772, 2705806345, 2725325172, 3596618182, 4263518096, 3004287726, 3480546848, 366296462, 2582223187, 873083062, 3035068564, 129826698, 682624376, 1041985948, 2300167185, 1985311187, 2158495582, 2574786951, 3239489764, 2005786117, 2399685911, 2157700060, 2548490153, 4165961385, 1864494416, 4267425571, 4023585511, 4032607081, 1740596122, 971654485, 4271206296, 1727985879, 770751334, 3357701211, 3406246261, 1758771097, 3755060295, 2398178683, 3380424195, 2048522566, 715325180, 3534765975, 3742183516, 4151425923, 1443702979, 3872154918, 3447970632, 2972193585, 1095301588, 1136514912, 3016628000, 3411626743, 1491689975, 3149230417, 1602027685, 1683352963, 3846848863, 3139684322, 62856240, 2244885460, 2895665432, 297531570, 1074403985, 1653386664, 95133646, 3476903462, 3606247651, 2399138344, 3186466372, 1956121684, 870920533, 3595320696, 3247874941, 3529506430, 2118652780, 2130399537, 2721787296, 1790856026, 4003100801, 1459989599, 437063189, 3567935321, 3982325641, 4200813095, 2636797818, 2761217793, 1932041321, 4210924853, 820967441, 2149054035, 3282837586, 1788349923, 3048451834, 1806983435, 4088507730, 3240976625, 564703315, 237694859, 2591207021, 4175049748, 2906348858, 106898972, 2915350214, 1266855510, 1321452064, 178409141, 3979906468, 1672294316, 1497714995, 1682915718, 968837565]

Vì hiện tại mình vẫn khá ngu về Lattice nên mình đã thử copy 1 số đoạn code để paste lên Github, và mình tìm được một challenge tương tự của giải D^3CTF 2023

https://github.com/shal10w/d3ctf2023-d3bdd/tree/main

Ngoài ra thì còn một cách khác. Ở đây, ta được cho 6 mảnh của flag, mỗi mảng là mã hóa SHA256 của 5 kí tự flag. Mình có thể brute-force SHA256 từng mảnh.

Ở đây mình sử dụng code C:

#include <iostream>
#include <string>
#include <vector>
#include <thread>
#include <atomic>
#include <cstring>
#include <cmath>
#include <openssl/sha.h>

const char charset[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~"; 

std::string target_hash;

std::atomic<bool> found(false);
std::string yepassword;

void crack(int start, int end){
    // just to c5 only
    if (end > strlen(charset)) {
        end = strlen(charset);
    }
    for (int c1 = 0; c1 < (strlen(charset)); ++c1) {
        for (int c2 = 0; c2 < strlen(charset); ++c2) {
            for (int c3 = 0; c3 < strlen(charset); ++c3) {
                for (int c4 = 0; c4 < strlen(charset); ++c4) {
                    for (int c5 = start; c5 < end; ++c5) {
                        if (found) {
                            return;
                        }
                        std::string password = "";
                        password += charset[c1];
                        password += charset[c2];
                        password += charset[c3];
                        password += charset[c4];
                        password += charset[c5];
                        // std::cout << password << std::endl;
                        // generate hex of sha256
                        unsigned char hash[SHA256_DIGEST_LENGTH];
                        SHA256_CTX sha256;
                        SHA256_Init(&sha256);
                        SHA256_Update(&sha256, password.c_str(), password.size());
                        SHA256_Final(hash, &sha256);
                        std::stringstream ss;
                        for(int i = 0; i < SHA256_DIGEST_LENGTH; i++)
                        {
                            ss << std::hex << (int)hash[i];
                        }
                        std::string sha256_hash = ss.str();
                        // std::cout << sha256_hash << std::endl;
                        if (sha256_hash == target_hash) {
                            found = true;
                            yepassword = password;
                            return;
                        }
                    }
                }
            }
        }
    }
}

int main(int argc, char *argv[]) {
    target_hash = argv[1];

  int num_threads = 8;
  std::vector<std::thread> threads;

  uint64_t workload = strlen(charset);
  uint64_t work_per_thread = workload / num_threads + 1;

  for(int i = 0; i < num_threads; i++) {
  
    int start = i * work_per_thread;
    int end = start + work_per_thread;
    // std::cout << start << " " << end << std::endl;
    
    threads.push_back(std::thread(crack, start, end));
  
  }

  for(auto& t : threads) {
    t.join();
  }

  if(found) {
    std::cout << "Password found: " << yepassword << std::endl;
  }
  else {
    std::cout << "Password not found" << std::endl;
  }

  return 0;

}
PreviousSVATTT 2023NextWarm-up

Last updated