Foobar CTF 2023

Crypto writeup

funwithrandom-1

nc chall.foobar.nitdgplug.org 30001

chall.py

import random
import os
from Flag import flag

random.seed(os.urandom(8))
mt = list(random.getstate()[1])
N= 624
M = 397
MATRIX_A = 0x83a2b0c3
UPPER_MASK =  0x80000000  
LOWER_MASK =  0x7fffffff

TemperingMaskB = 0x3f5663d0
TemperingMaskC = 0x56e90000

mag01 = [0, MATRIX_A]
mt_index = 624
def rand_gen():
    global mt_index
    if mt_index>=N:
        for kk in range(N-M):
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK)
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1]

        for kk in range(N-M, N-1):
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK)
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1]

        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK)
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1]
        mt_index = 0

    y = mt[mt_index]
    y ^= (y >> 43)
    y ^= (y << 12) & TemperingMaskB
    y ^= (y << 67) & TemperingMaskC
    y ^= (y >> 69)
    mt_index+=1

    return y

output = []
for _ in range(624):
    output.append(rand_gen())

Banner = "Thou shall guess the next 5 random numbers or burn in the eternal fire of RPNG Generator\n"
print(Banner)
print(output)
print("\n")
for i in range(5):
    response= int(input(f"Number {i+1}: "))
    if response!= rand_gen():
        print("Incorrect!!")
        exit(1)

print(flag)

Đọc qua source code thấy chall dùng 1 trình tạo số giả ngẫu nhiên(Pseudo-Random Number Generator - PRNG) in ra 624 số,yêu cầu đoán đúng 5 số tiếp theo thì thì in ra flag.

Thuật toán challenge sử dụng ở đây là Mersenne Twister
Mersenne Twister hoạt động bằng cách duy trì một mảng state khổng lồ, state ban đầu là seed ngẫu nhiên của chúng ta. Mảng này cung cấp cho mỗi phần tử thông qua một loạt các hoạt động để tạo ra một số giả ngẫu nhiên mới. Sau khi cạn kiệt toàn bộ mảng trạng thái, mảng được tái tạo ("xoắn") - twisted. Để thảo luận thêm về các hoạt động này, chúng ta phải xác định một tập hợp các hằng số được sử dụng trong các hoạt động này. Các hằng số này tương ứng với MT19937, đây là những gì triển khai Python tương ứng với .

Lưu ý đây là giá trị các hằng số mặc định tương ứng với MT19937 tạo số ngẫu nhiên 32 bits ,trong challenge các hằng số có giá trị thay đổi.Ngoài ra với MT19937_64(seed và các số giả tạo ra 64bits) cũng có sự khác biệt .

Quá trình tạo một số ngẫu nhiên từ mảng trạng thái như sau:

    y = x[i]
    y = y ^ (y >> u)
    y = y ^ ((y << s) & b)
    y = y ^ ((y << t) & c)
    y = y ^ (y >> l)
    i++
    return y

Sau khi chạy đoạn code trên n lần tức là sinh n số ngẫu nhiên.State sẽ bị cạn kiệt,chúng ta cần tái tạo lại như sau:

def twist_state_map(state):
    res = []
    for i in range(N):
        y = (state[i]&UPPER_MASK) | (state[(i+1)%N] & LOWER_MASK)
        next_item = state[(i+M)%N] ^ (y>>1) ^(0 if y%2 ==0 else A)
        res.append(next_item)
    return res

Trong quá trình sinh số ngẫu nhiên có 2 bước :y ^ (y >> k) và y ^ ((y << k) & m),chúng ta cần đảo ngược cả hai quá trình này

undo rigth shift

w = 32 
def undo_right(value,shift):
    res = value
    for i in range(0,w,shift):
        por_mask = '0'*i + '1'*shift + '0'*(W-shift-i)
        por_mask = int(por_mask[:w],2)
        por = res & por_mask

        res ^= por>>shift
    return res

undo left shift

w = 32
def undo_left(value,shift,mask):
    res = value
    for i in range(0,w,shift):
        por_mask = '0'*(w-shift-i)+'1'*shift+'0'*i
        por_mask = int(por_mask,2)
        por = res & por_mask

        res ^= ((por<<shift)& mask)

    return int(res)

Để đảo ngược mảng state ta phải thu thập đủ mẫu (challenge cho 624 mẫu). Việc tạo mảng state diễn ra như bước sinh số ngẫu nhiên nhưng với chức năng và thứ tự ngược lại. Thay các hằng số tương ứng giống như trong challenge ( u = 32,s=12,l=69,t=67 ,B,C …)

N= 624
M = 397
UPPER_MASK =  0x80000000  
LOWER_MASK =  0x7fffffff
w = 32
u = 43
s = 12
l = 69
t = 67
A = 0x83a2b0c3
B = 0x3f5663d0
C = 0x56e90000
for sample in samples:
    y = undo_right(sample,l)
    y = undo_left(y,t,C)
    y = undo_left(y,s,B)
    y = undo_right(y,u)
    state.append(y)

Sau khi chạy qua từng phần tử trong tập hợp mẫu 624 phần tử ta sẽ thu được mảng state ban đầu.
Với state ban đầu ta có thể tạo được các số ngẫu nhiên tiếp theo bằng việc tái tạo(xoắn) state sau đó tạo các số ngẫu nhiên tiếp theo

state = twist_state_map(state)
k = 1
for item in state:
    y = item ^ (item >>u)
    y ^= (y << s) & B
    y ^= (y << t) & C
    y ^= y >> l
    print(k,'=' ,y)
    k+= 1 
state = twist_state_map(state)

Full script

import os
from pwn import *


N= 624
M = 397
UPPER_MASK =  0x80000000  
LOWER_MASK =  0x7fffffff
W = 32
w = 32
u = 43
s = 12
l = 69
t = 67
A = 0x83a2b0c3
B = 0x3f5663d0
C = 0x56e90000

def undo_right(value,shift):
    res = value
    for i in range(0,w,shift):
        por_mask = '0'*i + '1'*shift + '0'*(W-shift-i)
        por_mask = int(por_mask[:w],2)
        por = res & por_mask

        res ^= por>>shift
    return res

def undo_left(value,shift,mask):
    res = value
    for i in range(0,w,shift):
        por_mask = '0'*(w-shift-i)+'1'*shift+'0'*i
        por_mask = int(por_mask,2)
        por = res & por_mask

        res ^= ((por<<shift)& mask)

    return int(res)
conn = remote('chall.foobar.nitdgplug.org', 30001)
conn.recvuntil("Generator\n\n".encode())
output = [int(i) for i in (conn.recvline().decode()[1:-2].split(','))]
samples = output
#samples = [1003006329, 1576404318, 3690986363, 1064565925, 3462864879, 3842668979, 3885848073, 1315712282, 554911852, 3523705385, 676581753, 3753175268, 2843442746, 334766186, 467882142, 3824868806, 183752175, 2897029589, 3863386953, 459766103, 588278376, 498296256, 2307508552, 2065254312, 127122405, 4160499537, 2141832795, 1125688166, 1789174104, 3130532987, 3847981364, 3424023620, 1780058813, 3025195680, 3092104363, 852225880, 2680894183, 4257652721, 28677846, 2767114135, 2045158185, 3386961151, 485684738, 2875130238, 3446854811, 2372778432, 560865039, 1728183158, 1986647746, 1673653971, 716248395, 951435062, 2334757098, 848231188, 3578365600, 3571016456, 3049472950, 3047081166, 3795135983, 2121702718, 3685933013, 2181942570, 3791071068, 4045143950, 4141197658, 4078388945, 1313463387, 3403043070, 3336619120, 58930338, 2204079884, 3463411311, 3905185523, 1575629900, 3639844156, 2255046504, 604978240, 3256535964, 3374468589, 3923598766, 2203287698, 174494527, 2617204782, 2495824660, 4002200879, 2450655043, 3903998130, 3474631536, 39509375, 2991991703, 3980035054, 1392120357, 875898396, 3344620260, 3310980174, 1277936382, 4213402943, 4264446690, 3234211804, 973429269, 1301474568, 2976909254, 2306757437, 1535358408, 3461643143, 583271906, 3767407673, 920245678, 1042018791, 1858752389, 1735368919, 3527874075, 4003388430, 1241243709, 356095988, 1773916496, 754971334, 241043439, 900012059, 4084325927, 1166713768, 4285344623, 882752012, 1764152003, 1653882747, 4082356997, 1943066193, 1893921817, 1756609683, 903158175, 3255717120, 217073919, 2589752267, 3433090061, 2263994452, 1005531701, 3125602079, 2009027502, 3816487034, 945546362, 4288673, 2757955698, 3448499924, 2363937741, 297134526, 1328602403, 201162491, 2085601272, 76080461, 936655819, 4098396054, 2566215651, 1953358722, 3638760929, 2835370673, 4238482217, 1116425886, 2347103826, 2713083, 3340059809, 1925301696, 209886385, 1763210657, 845900210, 1197280781, 2691177847, 221206604, 2791249744, 658191806, 2656581701, 849988406, 669757313, 2618077539, 1075685289, 475523722, 4063932295, 4169089252, 2385780215, 3605805994, 4075733836, 2801336526, 2110247527, 1635709243, 3968148305, 2755183254, 2887375021, 2760101653, 2574715198, 2491191960, 3034739481, 3038101441, 392743432, 2035825549, 1026915430, 2856928622, 3641358187, 2221995571, 272279121, 891461167, 1628579426, 32818587, 2748809046, 894716860, 2690132903, 4266418030, 114730355, 2569955404, 1640009526, 1784136946, 3896612480, 3341899965, 4052086605, 3824530265, 3776090169, 1529316455, 934943770, 1001593390, 747936693, 1009943707, 3777105331, 932283584, 1902390245, 3494784177, 1726983854, 1777277510, 1984751018, 3919863568, 3373534889, 1164099196, 2255094775, 3461544371, 17994965, 3352346227, 3457877916, 3225324381, 2951685167, 957957188, 1155732090, 298555032, 3904504307, 2529153191, 1944666460, 1765259255, 1578148640, 75381637, 2621357432, 1983485579, 1867633620, 849365322, 534535469, 161260508, 2871339271, 1622507769, 2325470771, 87650668, 343199423, 2355033977, 3968661473, 3411505770, 3732963737, 157499675, 988506475, 3798424197, 739080166, 256106180, 2655755182, 3168204197, 1449310932, 557829249, 692641835, 2182677090, 3840915, 4647832, 1496461752, 1023232195, 1020285918, 473898103, 2413706281, 3615928727, 608137021, 313340738, 956536501, 4008042078, 3614376389, 2600135875, 2909233447, 3129028003, 4024105094, 3151514850, 421220643, 3067468767, 2595224769, 652933214, 3017842843, 2385856024, 1551452564, 2557228434, 694528201, 3617114367, 3657428936, 4292330212, 3916749765, 1014005344, 1080860707, 1030670932, 1133768423, 317244099, 1891731737, 2895758489, 4007556582, 798755984, 460611118, 2175103392, 2329339249, 802616443, 793908952, 2271164254, 957555078, 1660116099, 2117183256, 4104543542, 2523885183, 1347066146, 142620378, 2845886031, 2775837752, 894938185, 3672438036, 3281052298, 2516510170, 3105833750, 797166386, 670752578, 664147809, 81673934, 1360827839, 226934402, 1861263309, 1305074366, 1698769514, 2425201445, 2172905684, 3007004424, 3791572507, 1401461789, 2628736067, 1177224990, 3087905439, 2821791841, 916556788, 2874293220, 4115415826, 2764290048, 253701125, 3824152819, 1837074152, 1661217708, 877047300, 421208681, 3923192315, 2996691738, 1424746960, 2456413769, 3800290850, 2103094107, 1916816236, 2186316497, 292878747, 3345022151, 589059769, 4016393712, 4230136025, 1310213616, 2678680540, 557958928, 2930998962, 2006131339, 2192606579, 2989920495, 751210322, 871207730, 1494759723, 3813334346, 934506915, 3350828760, 7940785, 1333174752, 2169732131, 95162827, 1256508882, 718768329, 4135983582, 3447857908, 2414205032, 442601346, 837820546, 3053173363, 399129741, 2079410202, 3004973085, 3369531974, 3605713399, 1402247311, 3022916187, 1476985186, 1220375628, 1464221552, 1791785248, 4285996849, 1228671438, 1135934753, 3708325961, 1633071782, 2395405022, 4213765130, 1607840910, 4211596494, 39054827, 1901426305, 2197360043, 2198784263, 3727365098, 2504757606, 2831959171, 1070488628, 2802527907, 1219380977, 2816747349, 1054597357, 363309726, 3095844037, 1659709557, 203602237, 1976292867, 568559469, 223251944, 1567582879, 3011307849, 2305321692, 2276083330, 3928564870, 1812120309, 386179564, 2877680600, 3305744468, 1373269559, 57762000, 3625182775, 667254634, 2671275287, 495914840, 1734822954, 30365458, 3722175533, 642190751, 1753366137, 3360588239, 2892498661, 2862349437, 2593168859, 4015482575, 3711309340, 2930079288, 1284969014, 3906880659, 2035224236, 1966395980, 138419922, 1937759925, 1629646169, 239653419, 2376345978, 3813881522, 643911987, 3798639212, 2265692390, 1490614726, 2268442193, 3724209139, 907584770, 22897326, 4016457003, 240359936, 454369505, 456259032, 2684481382, 1028036994, 292753427, 3067407046, 3568544004, 533431910, 41279675, 2194650386, 1433803920, 741361104, 638940366, 3452137233, 2132897234, 413204008, 481363057, 4184291753, 2933809400, 1798619075, 1829453680, 3248340748, 3100690985, 542707805, 1096182760, 1426314524, 3992202540, 1043280158, 3151768755, 2617283840, 2479818777, 4034331776, 2802417896, 1197342203, 934476471, 1946136380, 1063943275, 2952979979, 3737190945, 1818605196, 1264822037, 579467276, 985675323, 3896612376, 1774744401, 1739141701, 3169434603, 4050510022, 3273674035, 1889487407, 3846228540, 1348719393, 3753538315, 3541427528, 3009730608, 1159153532, 2653092102, 152501631, 2863205100, 3809414098, 1646253408, 340737793, 762702134, 1563756760, 2782364649, 3285639, 1266214195, 2808543967, 576919144, 1730635635, 2321188555, 1529869699, 3432565294, 2929929136, 2597629809, 100499087, 4067226413, 2364942755, 1552148673, 2701920276, 1508022162, 2037733423, 3700663007, 90376605, 2698203449, 777761988, 398159115, 1893520914, 4048763034, 3159309996, 1498542928, 4035779358, 2219810258, 3513728478, 1111176020, 2678959621, 1956283901, 3514459558, 699423319, 2376650300, 1001237708, 1927313502, 3350893555, 2579289080, 4064392463, 2292374676, 3553356117, 260810455, 2604248820, 2510175899, 1385753280, 3243785404, 450281583, 472937192, 748583555, 4042438807, 2385882593, 981534911, 609239826, 1417086349, 313772979, 2590957790, 3716223108, 2051934374, 3095643008, 575996938, 2038564001, 2099455396, 186708462, 887260634, 2211278485, 1185239571, 2114661353, 3142355128, 1092142790, 467018550, 26699198, 1282931654, 2819169911, 1350669178, 552615436]
state = []

for sample in samples:
    y = undo_right(sample,l)
    y = undo_left(y,t,C)
    y = undo_left(y,s,B)
    y = undo_right(y,u)
    state.append(y)

#print(state)
def twist_state_map(state):
    res = []
    for i in range(N):
        y = (state[i]&UPPER_MASK) | (state[(i+1)%N] & LOWER_MASK)
        next_item = state[(i+M)%N] ^ (y>>1) ^(0 if y%2 ==0 else A)
        res.append(next_item)
    return res


state = twist_state_map(state)


k = 0
for i in range(5):
    y = state[k]
    y ^= y >> u
    y ^= (y << s) & B
    y ^= (y << t) & C
    y ^= y >> l
    conn.recvuntil(":".encode())
    print(f'{k+1}= {y}')
    conn.sendline(f'{y}'.encode())
    k+=1

print(conn.recvline().decode())
conn.close()
state = twist_state_map(state)

Gửi 5 số tiếp theo chúng ta sẽ có được flag

Flag :GLUG{R4nd0m_Numb3r_G3n3r470r_15_tru3ly_r4nd0m_0r_15_17}