糖醋小鸡块的blog
0%

2024-TFCCTF&crewCTF-wp-crypto

发表于 更新于 分类于 Valine：

记录一下。

TFCCTF

CCCCC

题目描述：

1
2
3
CCCCC CCCCC CCCCC CCCCC CCCCC CCCCC CCCCC CCCCC CCCCC CCCCC CCCCC CCCCC

CCCCC CCCCC CCCCC

题目：

1
5c4c4c6c4c3c4c3c5c4c4c6c7cbc6c3c7c3c6c8c6cfc7c5c7c4c5cfc6c3c6cfc7c5c7c4c5cfc6c3c7c4c3c0c5cfc6c3c6cdc7c9c5cfc6c3c6c2c3c0c7c9c5cfc6c3c3c4c6cec6c4c5cfc6c3c6cdc7c9c5cfc6c3c6c4c6cfc6c7c5cfc6c3c6c1c6cec6c4c5cfc6c3c6cdc7c9c5cfc6c3c6c3c3c4c3c7c7cdc0ca

可以看出每两个字符之间都插入了个c，拆掉之后十六进制转bytes即可。

exp：

1
2
3
4
5
6
7
c = "5c4c4c6c4c3c4c3c5c4c4c6c7cbc6c3c7c3c6c8c6cfc7c5c7c4c5cfc6c3c6cfc7c5c7c4c5cfc6c3c7c4c3c0c5cfc6c3c6cdc7c9c5cfc6c3c6c2c3c0c7c9c5cfc6c3c3c4c6cec6c4c5cfc6c3c6cdc7c9c5cfc6c3c6c4c6cfc6c7c5cfc6c3c6c1c6cec6c4c5cfc6c3c6cdc7c9c5cfc6c3c6c3c3c4c3c7c7cdc0ca"
cipher = ""
for i in range(len(c)//2):
    cipher += c[2*i]
print(bytes.fromhex(cipher[:-1]))

#TFCCTF{cshout_cout_ct0_cmy_cb0y_c4nd_cmy_cdog_cand_cmy_cc47}



Conway

题目描述：

1
Sequences... Sequences sequences... Sequences sequences sequences...

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from secret import generate_next_key, flag
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

initial = 11131221131211131231121113112221121321132132211331222113112211

initial = generate_next_key(initial)
print(initial)

initial = generate_next_key(initial)
h = hashlib.sha256()
h.update(str(initial).encode())
key = h.digest()

cipher = AES.new(key, AES.MODE_ECB)
print(cipher.encrypt(pad(flag.encode(),16)).hex())

output.txt：

1
2
311311222113111231131112132112311321322112111312211312111322212311322113212221
f143845f3c4d9ad024ac8f76592352127651ff4d8c35e48ca9337422a0d7f20ec0c2baf530695c150efff20bbc17ca4c

说实话一点都不懂，看了下队伍里师傅的解释，说是个一维康威生命游戏，比如对于题目的递推来说就是：

1
2
3
c1 : 11131221131211131231121113112221121321132132211331222113112211
-->
c2 : 311311222113111231131112132112311321322112111312211312111322212311322113212221

对于c1，其开始是三个连续的1，所以c2的开始就是31，接着是一个连续的3，所以c2就有13，以此类推。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import hashlib
from Crypto.Cipher import AES

def game(state):
    L = len(state)
    idx = 0
    temp = state[idx]
    next_state = ""
    count = 1
    while(1):
        if(state[idx+1] == temp):
            count += 1
        else:
            next_state += (str(count) + temp)
            temp = state[idx+1]
            count = 1
        idx += 1
        if(idx == L-1):
            next_state += (str(count) + temp)
            break   
    return next_state

c1 = "11131221131211131231121113112221121321132132211331222113112211"
c2 = "311311222113111231131112132112311321322112111312211312111322212311322113212221"
enc = "f143845f3c4d9ad024ac8f76592352127651ff4d8c35e48ca9337422a0d7f20ec0c2baf530695c150efff20bbc17ca4c"
assert game(c1) == c2
c3 = game(c2)

h = hashlib.sha256()
h.update(str(c3).encode())
key = h.digest()

cipher = AES.new(key, AES.MODE_ECB)
print(cipher.decrypt(bytes.fromhex(enc)))


#TFCCTF{c0nway's_g4me_0f_sequences?}



GENETICS

题目：

1
2
3
I just took a quick look at my DNA. I feel like I was created for this CTF.

CCCA CACG CAAT CAAT CCCA CACG CTGT ATAC CCTT CTCT ATAC CGTA CGTA CCTT CGCT ATAT CTCA CCTT CTCA CGGA ATAC CTAT CCTT ATCA CTAT CCTT ATCA CCTT CTCA ATCA CTCA CTCA ATAA ATAA CCTT CCCG ATAT CTAG CTGC CCTT CTAT ATAA ATAA CGTG CTTC

DNA编码，查了下发现说就是每个字母代表两位二进制而已。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *

c = "CCCACACGCAATCAATCCCACACGCTGTATACCCTTCTCTATACCGTACGTACCTTCGCTATATCTCACCTTCTCACGGAATACCTATCCTTATCACTATCCTTATCACCTTCTCAATCACTCACTCAATAAATAACCTTCCCGATATCTAGCTGCCCTTCTATATAAATAACGTGCTTC"

flag = ""
for i in c:
    if(i == "A"):
        flag += "00"
    elif(i == "C"):
        flag += "01"
    elif(i == "G"):
        flag += "10"
    elif(i == "T"):
        flag += "11"

print(long_to_bytes(int(flag,2)))


#TFCCTF{1_w1ll_g3t_th1s_4s_4_t4tt00_V3ry_s00n}



PADGROUNDS

题目描述：

1
2
3
Welcome to Padgrounds, where every bit counts. Dive into the action and let your skills shine as you unravel the coded enigma.

Note: Make sure your solver works locally before running on remote.

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/env python3

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import os
import base64
import random

#FLAG regex is TFCCTF{[bdefgmnprsu012345_]+}

FLAG = b'REDACTED' 


def custom_unpad(ct):
    ct = base64.b64decode(ct)
    iv, ct = ct[:16], ct[16:]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = cipher.decrypt(ct)
    padding = True
    try:
        unpad(pt, 16)
    except:
        padding = False
    padding = (padding | (random.randint(1,10) > 7) ) & (random.randint(1,10) <= 7)
    return padding

current = 0
limit = 10000
key = os.urandom(16)
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(FLAG)
give = base64.b64encode(iv + ct)
print(f"Lets see you decode this: {give.decode()}")
print("I made my unpad truly random, there is nothing you can do, just give up already")

while True:
    if current > limit:
        exit()
    to_unpad = input()
    out = custom_unpad(to_unpad)
    print(out)
    current+=1

其实就是个padding oracle attack，只是这次是否unpad成功变成了概率性的，对于unpad成功，返回True的概率是70%，而unpad失败返回True的概率是21%，所以需要统计+padding oracle attack才行。

次数问题完全不需要在意，因为flag又不会变

这个想着就有点折磨，无疑耗时会相当长，所以就不写exp了。



BIASED ELECTIONS

题目描述：

1
We heard rumors that someone might rig the upcoming elections. We managed to place a backdoor in one of their messaging systems. See what you can make out of it, the world counts on you.

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes,bytes_to_long

FLAG = b'TFCCTF{REDACTED}'
G = generator_256
order = G.order()
rand = random.randint(1,order-1)
pubkey = Public_key(G, rand*G)
privkey = Private_key(pubkey, rand)



messages = [
    "Ensure the ballots are ready for the biased count.",
    "The first batch of votes is in. Proceed as planned.",
    "Secure the communications. We can't risk exposure.",
    "Start the rigging process at midnight tonight.",
    "All systems are go. Confirm the final preparations.",
    "Intercepted some chatter. Maintain radio silence.",
    "Verification complete. Everything is on track.",
    "Monitor the vote counts closely. Report any issues.",
    "We've gained access. Execute the next step."
]

def the_random():
    def very_random(length):
        return ''.join(chr((l(a, b, m) % 94) + 33) for _ in range(length))
    
    def l(a, b, m):
        nonlocal x
        result = (a * x + b) % m
        x = result
        return result
    
    a = 6364136223846793005
    b = 1
    m = 2 ** 64
    x = random.getrandbits(64)
    
    r = very_random(128)
    s = hashlib.sha256(r.encode()).hexdigest()
    t = hashlib.md5(s.encode()).hexdigest()
    u = hashlib.sha1(t.encode()).hexdigest()
    f = lambda q: int(q, 16)
    c = lambda q: q & ((1 << random.randint(170,200)) - 1)
    
    g = very_random(256)
    h = very_random(256)
    j = ''.join(chr((ord(k) ^ ord(l)) % 256) for k, l in zip(g, h))
    k = hashlib.sha256(r.encode() + j.encode()).hexdigest()
    n = ''.join(chr((ord(o) ^ ord(p)) % 256) for o, p in zip(j, k))
    o = hashlib.md5(n.encode() + k.encode()).hexdigest()
    p = hashlib.sha1(o.encode() + k.encode()).hexdigest()
    q = f(p[:40])
    
    aes_key = very_random(16).encode('utf-8')
    aes_iv = very_random(16).encode('utf-8')
    aes_cipher = AES.new(aes_key, AES.MODE_CBC, aes_iv)
    aes_data = pad((p[:32] + o[:32]).encode('utf-8'), AES.block_size)
    aes_encrypted = aes_cipher.encrypt(aes_data)
    z = f(hashlib.sha256(aes_encrypted).hexdigest()[:40])
    
    obfuscated_final = lambda a, b: a ^ (b >> 5)
    result = obfuscated_final(q, z)
    return c(result)

def sign_message(message):
    hsh = hashlib.sha256(message.encode()).digest()
    nonce = the_random()
    sig = privkey.sign(bytes_to_long(hsh), nonce)
    return {"hash": bytes_to_long(hsh), "r": hex(sig.r), "s": hex(sig.s)}

max_used = 10
used = 0
print('What do you want to do?')
print('1. Listen in on conversation')
print('2. Submit the info you found')
print('3. Get pubkey')
while True:
    data = input()

    if data == '1':
        if used > max_used:
            print('Intruder spotted, deleting secrets.')
            exit()

        message = messages[random.randint(0,len(messages)-1)]
        print(sign_message(message))
        used+=1

    if data == '2':
        key = int(input('Key? '))

        if key == rand:
            print('Thanks bro here is a flag for your effort')
            print(FLAG)

    if data == '3':
        print(f'Public key: {int(pubkey.point.x())} {int(pubkey.point.y())}')

题目又长又乱，不过总而言之就是要求ECDSA的私钥，并且可以多次签名。

多次签名显然是nonce出了什么问题，看一下函数c，其实就是说nonce最多仅有200bit罢了，因此就是一个普通HNP。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import *
from Pwn4Sage.pwn import *
import json

############################################################################## parameters
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)
a = K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
b = K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
E = EllipticCurve(K, (a, b))
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
n = E.order()
a = 733113379677
b = 657
m = 2 ** 150
messages = [
    "Ensure the ballots are ready for the biased count.",
    "The first batch of votes is in. Proceed as planned.",
    "Secure the communications. We can't risk exposure.",
    "Start the rigging process at midnight tonight.",
    "All systems are go. Confirm the final preparations.",
    "Intercepted some chatter. Maintain radio silence.",
    "Verification complete. Everything is on track.",
    "Monitor the vote counts closely. Report any issues.",
    "We've gained access. Execute the next step."
]


############################################################################## part1 get data
sh = remote("challs.tfcctf.com", 31633)
sh.recvuntil(b"3. Get pubkey\n")
res = []
nums = 9
for i in range(nums):
    sh.sendline(b"1")
    res.append(json.loads(sh.recvline().strip().decode().replace("'","\"")))


############################################################################## part2 ECDSA-HNP
h = [i["hash"] for i in res]
r = [int(i["r"],16) for i in res]
s = [int(i["s"],16) for i in res]
L2 = Matrix(ZZ,2*nums,2*nums)
for i in range(nums):
    L2[i,i] = 1
L2[nums,nums] = 2^180
for i in range(1,nums):
    L2[0,nums+i] = s[0]*r[i]
    L2[i,nums+i] = -s[i]*r[0]

    ci = h[i]*r[0]-h[0]*r[i]
    L2[nums,nums+i] = ci
    L2[nums+i,nums+i] = n
L2[:,-nums+1:] *= n

res = L2.LLL()[0][:nums]
k0 = abs(res[0])
d = (s[0]*k0-h[0])*inverse(r[0],n) % n


############################################################################## part3 get flag
sh.sendline(b"2")
sh.sendline(str(d).encode())
sh.recvline()
print(sh.recvline())


#TFCCTF{c0Ngr47s_y0u_s4v3d_th3_3lect1Ons}



HELLFIRE PHANTOM

题目描述：

1
2
3
4
5
In the heart of an ancient, cursed forest lies the Phantom's lair, shrouded in hellfire. Legends speak of a powerful artifact hidden within, guarded by spectral flames and arcane riddles. Will you be the one to break the curse and uncover the secrets of the Hellfire Phantom?

Note: Challenge requires a bit of bruteforcing. Solver takes ~10 mins to run on my laptop.
Note: sha256sum of the variable secret's value is f8f099dd278c23d44387914def5fc20bc0fb8915d916775e5b4b17275e2107bd, website used is https://emn178.github.io/online-tools/sha256.html, input encoding UTF-8
Note: A person had issue with receiving multiple G points. The one that is used in the challenge ends in 727.

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from sage.all import *
import random
from Crypto.Util.number import getPrime, isPrime, long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha256

FLAG = b'REDACTED'
secret = REDACTED
b_curve = REDACTED

p = 1154543773027194978300531105544404721440832315984713424625039
g = 2
shared = pow(g,secret,p)

print(f"p = {p}")
print(f"g = {g}")
print(f"shared = {shared}")


secret2 = bytes_to_long(FLAG)


p_curve = 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000001
a_curve = 35220

Z = GF(p_curve)
E = EllipticCurve(Z, [a_curve,b_curve])
G = E.lift_x(Z(secret))
P = G * secret2

print(f'p_curve = {p_curve}')
print(f'a_curve = {a_curve}')
print(f'P = {P}')

一个dlp，一个ecdlp，主要解决步骤是：

  • 由于p-1并不光滑，所以dlp用cado-nfs来求，求出secret
  • 用给出的P点求出曲线参数b
  • 把secret lift到点G，注意实际上-G才是需要的点
  • pohlig-hellman求出子群中的secret2
  • 去掉末尾的}得到flag

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256

######################################################################## part1 secret
#./cado-nfs.py -dlp -ell 900580166167858797426311314777226771794720995307888786759 target=589382223336825905353017404337901190007770052877203421235378 1154543773027194978300531105544404721440832315984713424625039
#31653772803698764866405663325365133454945445328775270048
#./cado-nfs.py -dlp -ell 900580166167858797426311314777226771794720995307888786759 target=2 1154543773027194978300531105544404721440832315984713424625039
#364745943990966274208559347028377806262751076921350982122

#p-1 = 2*641*900580166167858797426311314777226771794720995307888786759
p = 1154543773027194978300531105544404721440832315984713424625039
g = 2
shared = 589382223336825905353017404337901190007770052877203421235378

r = 900580166167858797426311314777226771794720995307888786759
t1 = 364745943990966274208559347028377806262751076921350982122
t2 = 31653772803698764866405663325365133454945445328775270048
secret = t2*inverse(t1,r) % r
assert sha256(str(secret).encode()).hexdigest() == "f8f099dd278c23d44387914def5fc20bc0fb8915d916775e5b4b17275e2107bd"

######################################################################## part2 secret2
p = 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000001
a = 35220
P = (623096442003276996005526819582785620084071954736463701753970373963912716099078435477704571257942074621357 , 2384627087675194082373873481003992989604314757777638917742582544298077858048626428935086473569758082583040)
x,y = P
b = (y^2 - (x^3 + a*x)) % p
E = EllipticCurve(GF(p), [a,b])
r = 17229968799761915831961648039300568398720910455733592221895507193323
Z = GF(p)
G = -E.lift_x(Z(secret))
P = E(P)

n = G.order()
ordd = n // r
secret2 = (r*P).log(r*G)

secret2_prefix = (secret2 - ord("}")) * inverse(256,ordd) % ordd
print(long_to_bytes(secret2_prefix) + b"}")


#TFCCTF{cUrv3mAn}



ROTATOR CUFFS

题目描述：

1
Are you ready to rotate your way to victory?

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from secrets import SECRET, x1, x2, y1, y2

sumyum = -142226769181911294109604985414279966698269380324397182385943224688881786967396493297107323123238846393606215646973028804858833605857511769169835160302020010947120438688346678912969985151307036771093126928042899151991372646137181873186360733201445140152322209451057973604096364822332301687504248777277418181289153882723092865473163310211285730079965167100462695990655758205214602292622245102893445811728006653275203674798325843446182682402905466862314043187136542260285271179956030761086907321077282094937573562503816663264662117783270594824413962461600402415572179393223815743833171899844403295401923754406401502029098878225426758204788

assert sumyum == 2 * x1 ** 2 - SECRET * y1 ** 2 + 2 * x2 ** 2 - SECRET * y2 ** 2

F = RealField(3456)
x = vector(F, [x1, x2])
y = vector(F, [y1, y2])

for _ in range(10000):
    theta = F.random_element(min=-5 * pi, max=5 * pi)
    R = matrix(F, [[cos(theta), -sin(theta)], [sin(theta), cos(theta)]])
    x = R * x
    y = R * y

print("resulting_x =", x)
print("resulting_y =", y)

output.txt：

1
2
resulting_x = (3.3634809129087361339072596725006530600959848462815297766832600914180365498172745779530909095267862889993244875375870115862675521807203899602656875152466204714275847395081849947663071267678766620524700684572851632968584152642766533856599351512856580709762480161587856072790441655306539706390277559619708164477066112096159734609814163507781608041425939822535707080207842507025990454423454350866271037975269822168384397403714076341093853588894719723841956801405249658560486108807190027518922407932998209533025998785987344569930974892824749931597842343369782141668038797305601028366704322107431479213165353278773002704707347001056980736352878716736155054293350509670339144379602697176068785416128203382284653052813910539052285224499161723972390574800570738938264516350981139157860135237512937090793549860152173756751719627025142858529263243314917653507237003568510016357713402278753999645732592631577726849749929789275649985363293274521704758513276997442425705172979362522303209937874019044195572717894784790824040985970678829869212168596332338e228, 4.3493076236586169242233212405270398931813271488805260703904730395387317512159124699671617536806847379014763743850012966440449858042327139796085868934120939346500622666309663813415016921760622643752056516232426324399548704613192843351795229042500735885925583510203795565452553753954474949980588780332651769544235511465216034600990329267883327087177217125655503845919331440817328958054102807738186874040636118222352351053320953917165679774298608790659071127811941909136888169274293065733698380573486079052876249484455409206182001827225690775874445171478338344209529207109172368590360722150559332665968826925103060717742483611155201852629766859356827518117986215929527812137774656124580645282319815982553388185475874607903050755710964732279490338614504903256117014312989278124177060468718045944298976827788272885547066724342578660563396148909159051946415261351324693896674313199869788279492452177771905587881622085592044441472137286330359635594402564357596784568377870545793505212074411425362120275312322293627143588322908897500139505746513232e228)
resulting_y = (3.0086123485184949854819528432444522887263618452152977201477700454454717599185922285792607291484161348863603668674724666302028473336653202339259214779198337146709052083562504123644969759313504022148939497579033947489964578987257010705347661159352495880621564046451129149321751369899157697461990748527068553919767557375414807745137776378672423131583632676118768803623661016450513713378889178790819115525404124475586398119768281556573742250499881136366816528002891506377591473809774876327335425713426558761290418087432306668623923825516541279687269109753438014462223886767964900168026643719447209474190574704192551865457553267219179816090151816092471203713238427208397671093453024024773606469951052196613699816481289760243547361942029869165939022611782658000517871759272476768999453412473058498224382162775678590320117678687959374599497850317809926761224934950410879753727042047871292717229649696383856159211062622325024918849176324424823611459590717866478574927162324917352318674258311617781845396479605897293293787546058229588461669469113001e228, 4.1955438730064492244518395125687091233417321001179084616477593364143186962035096742717340249485256810878365124925979444527539802357032735868877910266504910589105346718553503670072791148806000734099122372428956062737130602189826489676949800396857262364104813055382317498461363421406914514918460816121876800728600531432610837129788010503804927836206596876591613685011706833895602299866191433190745884295362337967940063679204541643670409168084686978205876941245671248753306754892761206974604980311577415661960800437927228624982030061751022139301406066860249918396002252864930009083759551916555623475795108943840654272107400479044754688171126386094896825019962082090350188892677712358612478027143147182776057102433244569971150928964257290752485837202929975257858813456753394801152212850446322739077604336730800210171231609831225616780923301071587159265696870229784689201181607735865814975046649574472138172333744474559659785291954987787639082881571990180182337133038177924408020273887276582566592470019342076814034084107444178243083855840959209e228)

题目先给出一个等式(记SECRET为S)：

不过其中仅有sumyum是已知量。

之后题目记两个向量：

并随机生成一个角度 $\theta$，并记如下变换：

然后在RealField(3456)上做了如下变换：

给出x’和y’，要求还原SECRET。

R显然是一个旋转矩阵，所以R^k也依然只是个旋转而已，同理逆变换也是个旋转，也就是说最终的结果一定满足：

因此就可以列出四条等式了。除此之外，还有两条隐含的等式，一个就是带SECRET的，另一个为：

所以所有等式一起做个groebner，再取整就是SECRET了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *

sumyum = -142226769181911294109604985414279966698269380324397182385943224688881786967396493297107323123238846393606215646973028804858833605857511769169835160302020010947120438688346678912969985151307036771093126928042899151991372646137181873186360733201445140152322209451057973604096364822332301687504248777277418181289153882723092865473163310211285730079965167100462695990655758205214602292622245102893445811728006653275203674798325843446182682402905466862314043187136542260285271179956030761086907321077282094937573562503816663264662117783270594824413962461600402415572179393223815743833171899844403295401923754406401502029098878225426758204788
x = (3.3634809129087361339072596725006530600959848462815297766832600914180365498172745779530909095267862889993244875375870115862675521807203899602656875152466204714275847395081849947663071267678766620524700684572851632968584152642766533856599351512856580709762480161587856072790441655306539706390277559619708164477066112096159734609814163507781608041425939822535707080207842507025990454423454350866271037975269822168384397403714076341093853588894719723841956801405249658560486108807190027518922407932998209533025998785987344569930974892824749931597842343369782141668038797305601028366704322107431479213165353278773002704707347001056980736352878716736155054293350509670339144379602697176068785416128203382284653052813910539052285224499161723972390574800570738938264516350981139157860135237512937090793549860152173756751719627025142858529263243314917653507237003568510016357713402278753999645732592631577726849749929789275649985363293274521704758513276997442425705172979362522303209937874019044195572717894784790824040985970678829869212168596332338e228, 4.3493076236586169242233212405270398931813271488805260703904730395387317512159124699671617536806847379014763743850012966440449858042327139796085868934120939346500622666309663813415016921760622643752056516232426324399548704613192843351795229042500735885925583510203795565452553753954474949980588780332651769544235511465216034600990329267883327087177217125655503845919331440817328958054102807738186874040636118222352351053320953917165679774298608790659071127811941909136888169274293065733698380573486079052876249484455409206182001827225690775874445171478338344209529207109172368590360722150559332665968826925103060717742483611155201852629766859356827518117986215929527812137774656124580645282319815982553388185475874607903050755710964732279490338614504903256117014312989278124177060468718045944298976827788272885547066724342578660563396148909159051946415261351324693896674313199869788279492452177771905587881622085592044441472137286330359635594402564357596784568377870545793505212074411425362120275312322293627143588322908897500139505746513232e228)
y = (3.0086123485184949854819528432444522887263618452152977201477700454454717599185922285792607291484161348863603668674724666302028473336653202339259214779198337146709052083562504123644969759313504022148939497579033947489964578987257010705347661159352495880621564046451129149321751369899157697461990748527068553919767557375414807745137776378672423131583632676118768803623661016450513713378889178790819115525404124475586398119768281556573742250499881136366816528002891506377591473809774876327335425713426558761290418087432306668623923825516541279687269109753438014462223886767964900168026643719447209474190574704192551865457553267219179816090151816092471203713238427208397671093453024024773606469951052196613699816481289760243547361942029869165939022611782658000517871759272476768999453412473058498224382162775678590320117678687959374599497850317809926761224934950410879753727042047871292717229649696383856159211062622325024918849176324424823611459590717866478574927162324917352318674258311617781845396479605897293293787546058229588461669469113001e228, 4.1955438730064492244518395125687091233417321001179084616477593364143186962035096742717340249485256810878365124925979444527539802357032735868877910266504910589105346718553503670072791148806000734099122372428956062737130602189826489676949800396857262364104813055382317498461363421406914514918460816121876800728600531432610837129788010503804927836206596876591613685011706833895602299866191433190745884295362337967940063679204541643670409168084686978205876941245671248753306754892761206974604980311577415661960800437927228624982030061751022139301406066860249918396002252864930009083759551916555623475795108943840654272107400479044754688171126386094896825019962082090350188892677712358612478027143147182776057102433244569971150928964257290752485837202929975257858813456753394801152212850446322739077604336730800210171231609831225616780923301071587159265696870229784689201181607735865814975046649574472138172333744474559659785291954987787639082881571990180182337133038177924408020273887276582566592470019342076814034084107444178243083855840959209e228)

F = RealField(3456)
x1_, x2_ = F(x[0]),F(x[1])
y1_, y2_ = F(y[0]),F(y[1])
PR.<cosa,sina,SECRET> = PolynomialRing(F)
x1 = cosa*x1_ - sina*x2_
x2 = sina*x1_ + cosa*x2_
y1 = cosa*y1_ - sina*y2_
y2 = sina*y1_ + cosa*y2_

f1 = 2 * x1 ** 2 - SECRET * y1 ** 2 + 2 * x2 ** 2 - SECRET * y2 ** 2 - sumyum
f2 = cosa^2 + sina^2 - 1
res = Ideal([f1,f2]).groebner_basis()
print(long_to_bytes(abs(int(res[1].coefficients()[1]))))


#TFCCTF{r0t4t3_and__g0_furth3r...s4me_th1ng...schr0d1ng3r's_r0tat1on...not}



BIAS FREE DEMOCRACY

题目描述：

1
In the aftermath, a few masterminds behind the operation managed to escape and have now relaunched their scheme. We've intercepted their encrypted communications, but we need your expertise to decrypt and decipher them.

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes,bytes_to_long

FLAG = b'TFCCTF{REDACTED}'

G = generator_256
order = G.order()
rand = random.randint(1,order-1)
pubkey = Public_key(G, rand*G)
privkey = Private_key(pubkey, rand)



messages = [
    "Initiate phase two, we've secured new access points.",
    "Encryption keys updated. Proceed with the new protocol.",
    "Ensure all communications are routed through the secure channel.",
    "Begin the new vote manipulation sequence at dawn.",
    "The second wave of votes is in. Validate and proceed.",
    "Our agents are in place. Execute the next steps discreetly.",
    "Double-check all encrypted transmissions for vulnerabilities.",
    "We've detected interference. Activate the countermeasures.",
    "Final preparations complete. Awaiting your signal.",
    "The rigging algorithm is updated. Deploy immediately."
]


a = 733113379677
b = 657
m = 2 ** 150
state = random.randint(0,2**150-1)
def patched_random():
    global a,state,b,m
    state = (a * state + b) % m


def the_random():
    patched_random()
    global state
    nonce = ((random.getrandbits(106) & (random.getrandbits(106) ^ random.getrandbits(106)) | random.getrandbits(106)) << 150) | state
    return nonce, state >> 110

def sign_message(message):
    hsh = hashlib.sha256(message.encode()).digest()
    nonce, leak = the_random()
    sig = privkey.sign(bytes_to_long(hsh), nonce)
    return {"hash": bytes_to_long(hsh), "r": hex(sig.r), "s": hex(sig.s), "leak": leak}

max_used = 50
used = 0
print('What do you want to do?')
print('1. Listen in on conversation')
print('2. Submit the info you found')
print('3. Get pubkey')
while True:
    data = input()

    if data == '1':
        if used > max_used:
            print('Why do you need to sign more than 50 times?')
            exit()

        message = messages[random.randint(0,len(messages)-1)]
        print(sign_message(message))
        used+=1

    if data == '2':
        key = int(input('Key? '))

        if key == rand:
            print('At last, they are gone, as payment you receive the flag.')
            print(FLAG)
        exit()

    if data == '3':

        print('Too easy if i just give it to you right? Try and solve this, i need P.x and Q.x')

        # Sage just refused to work in docker, so ill give you the values 
        # from sage.all import GF,EllipticCurve

        # curve secp256r1
        # p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
        # a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
        # b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
        # F = GF(p)
        # E = EllipticCurve(F, [a, b])
        # G = E((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
        
        # k1 = REDACTED
        # k2 = REDACTED
        # P = k1 * G
        # Q = k2 * G
        # print(P,Q)
        # for i in range(2):
        #     a,b = random
        #     out.append([a,b,a * P + b * Q])

        # out = [[96782493581107017213287940431906781117775401216029818502421722067004869671128, 18538871412723353247501824844190723767417562653982776603661341114579966744605, (36566315207713245091176405415710241138207929913023468223244125431056706761511 : 10976749572513729423697994197166601856770738841401887139027157647878298794556 : 1)], [90010878197235881814460760613107101266952873141567869967076779247935202848887, 95977587327198575377209621701343555951978156791715802180542478952260780398694, (42891521857367877217539705137361753088078433669344096955944120767916016902990 : 24699094435692184568058588241787734516749698041094295443543822154915466799108 : 1)]]

        received = input().split(' ')

        px_good, qx_good = REDACTED, REDACTED
        px, qx = int(received[0]), int(received[1])
        
        if px_good == px and qx_good == qx:
            print(f'Public key: {int(pubkey.point.x())} {int(pubkey.point.y())}')

        else:
            print('Wrong ma friend')
            exit()

依然是ECDSA的nonce出问题，只是这次并不能直接用小nonce来HNP了。

但观察一下发现他每次签名会额外给一个leak，leak的是每次nonce的低150位state的高40位，所以无论怎么样还是可以HNP的。再看一看发现说state甚至还是用一个LCG递推的，所以最简单的办法是直接先做LCG的HNP，这样所有nonce低150位就都有了，然后再做ECDSA的HNP即可。

由于数据给的很足，其实就五次签名也基本够用。

做完题目不妨看看他的选项3，是一个额外的小题目。并且居然是跑不了sage的docker所以才静态给出题目来XD。题目内容是给出两组：

曲线已知，要求给出P、Q。这个也很简单，曲线既然已知所以随便消去某一点，然后求出另一点都可以。

exp(HNP)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import *
from Pwn4Sage.pwn import *
import json

############################################################################## parameters
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)
a = K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
b = K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
E = EllipticCurve(K, (a, b))
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
n = E.order()
a = 733113379677
b = 657
m = 2 ** 150
messages = [
    "Initiate phase two, we've secured new access points.",
    "Encryption keys updated. Proceed with the new protocol.",
    "Ensure all communications are routed through the secure channel.",
    "Begin the new vote manipulation sequence at dawn.",
    "The second wave of votes is in. Validate and proceed.",
    "Our agents are in place. Execute the next steps discreetly.",
    "Double-check all encrypted transmissions for vulnerabilities.",
    "We've detected interference. Activate the countermeasures.",
    "Final preparations complete. Awaiting your signal.",
    "The rigging algorithm is updated. Deploy immediately."
]


############################################################################## part1 get data
sh = remote("challs.tfcctf.com", 30371)
sh.recvuntil(b"3. Get pubkey\n")
res = []
nums = 10
for i in range(nums):
    sh.sendline(b"1")
    res.append(json.loads(sh.recvline().strip().decode().replace("'","\"")))


############################################################################## part2 LCG-HNP to get state
h = [i["leak"]*2^110 for i in res]
L1 = Matrix(ZZ,2*nums,2*nums)
for i in range(nums):
    L1[i,i] = 1
L1[nums,nums] = 2^109
for i in range(nums-1):
    L1[i,nums+1+i] = a
    L1[i+1,nums+1+i] = -1

    ci = b + a*h[i] - h[i+1]
    L1[nums,nums+1+i] = ci
    L1[nums+1+i,nums+1+i] = m
L1[:,-nums+1:] *= m
res1 = L1.LLL()[0][:nums]
state = [i["leak"]*2^110+abs(j) for i,j in zip(res,res1)]
assert (state[0]*a + b) % m == state[1]


############################################################################## part3 ECDSA-HNP
h = [i["hash"] for i in res]
r = [int(i["r"],16) for i in res]
s = [int(i["s"],16) for i in res]
L2 = Matrix(ZZ,2*nums,2*nums)
for i in range(nums):
    L2[i,i] = 1
L2[nums,nums] = 2^105
for i in range(1,nums):
    L2[0,nums+i] = s[0]*r[i]*2^150
    L2[i,nums+i] = -s[i]*r[0]*2^150

    ci = h[i]*r[0]-h[0]*r[i]-s[i]*r[0]*state[i]+s[0]*r[i]*state[0]
    L2[nums,nums+i] = ci
    L2[nums+i,nums+i] = n
L2[:,-nums+1:] *= n

res = L2.LLL()[0][:nums]
k0 = abs(res[0])*2^150+state[0]
d = (s[0]*k0-h[0])*inverse(r[0],n) % n


############################################################################## part4 get flag
sh.sendline(b"2")
sh.sendline(str(d).encode())
sh.recvline()
print(sh.recvline())


#TFCCTF{y0u_end3D_Th3_c0rruption}

exp(option 3)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [a, b])
G = E((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
out = [[96782493581107017213287940431906781117775401216029818502421722067004869671128, 18538871412723353247501824844190723767417562653982776603661341114579966744605, (36566315207713245091176405415710241138207929913023468223244125431056706761511,10976749572513729423697994197166601856770738841401887139027157647878298794556)], [90010878197235881814460760613107101266952873141567869967076779247935202848887, 95977587327198575377209621701343555951978156791715802180542478952260780398694, (42891521857367877217539705137361753088078433669344096955944120767916016902990,24699094435692184568058588241787734516749698041094295443543822154915466799108)]]

n = E.order()
a1,b1,C1 = out[0]
a2,b2,C2 = out[1]
C1,C2 = E(C1),E(C2)
Q = (a2*C1 - a1*C2)*inverse(b1*a2-b2*a1,n)
P = (C1 - b1*Q)*inverse(a1,n)
assert a1*P + b1*Q == C1 and a2*P + b2*Q == C2



crewCTF

4ES

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#!/usr/bin/env python3

from hashlib import sha256
from random import choices

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

chars = b'crew_AES*4=$!?'
L = 3

w, x, y, z = (
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
)

k1 = sha256(w).digest()
k2 = sha256(x).digest()
k3 = sha256(y).digest()
k4 = sha256(z).digest()

print(w.decode(), x.decode(), y.decode(), z.decode())

pt = b'AES_AES_AES_AES!'
ct = AES.new(k4, AES.MODE_ECB).encrypt(
         AES.new(k3, AES.MODE_ECB).encrypt(
             AES.new(k2, AES.MODE_ECB).encrypt(
                 AES.new(k1, AES.MODE_ECB).encrypt(
                     pt
                 )
             )
         )
     )

key = sha256(w + x + y + z).digest()
enc_flag = AES.new(key, AES.MODE_ECB).encrypt(pad(FLAG, AES.block_size))

with open('output.txt', 'w') as f:
    f.write(f'pt = {pt.hex()}\nct = {ct.hex()}\nenc_flag = {enc_flag.hex()}')

output.txt：

1
2
3
pt = 4145535f4145535f4145535f41455321
ct = edb43249be0d7a4620b9b876315eb430
enc_flag = e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b

题目进行了四层AES加密，每一层的密钥是特定字符表中的三个字符组成串的sha256值，并且给出了一组明密文，需要解出每层密钥来最终解密flag。

很直白的mitm了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from hashlib import sha256
from Crypto.Cipher import AES
from math import comb
from itertools import *
from tqdm import *

chars = 'crew_AES*4=$!?'
L = 3

pt = bytes.fromhex("4145535f4145535f4145535f41455321")
ct = bytes.fromhex("edb43249be0d7a4620b9b876315eb430")
enc_flag = bytes.fromhex("e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b")

if(0):
    dic = {}
    for w in tqdm(product(chars,repeat=3),total=len(chars)**3):
        for x in product(chars,repeat=3):
            w = "".join(list(w))
            x = "".join(list(x))
            k1 = sha256(w.encode()).digest()
            k2 = sha256(x.encode()).digest()
            AES_w = AES.new(k1, AES.MODE_ECB)
            AES_x = AES.new(k2, AES.MODE_ECB)
            dic[AES_x.decrypt(AES_w.decrypt(ct))] = (w,x)

    for y in tqdm(product(chars,repeat=3),total=len(chars)**3):
        for z in product(chars,repeat=3):
            y = "".join(list(y))
            z = "".join(list(z))
            k3 = sha256(y.encode()).digest()
            k4 = sha256(z.encode()).digest()
            AES_y = AES.new(k3, AES.MODE_ECB)
            AES_z = AES.new(k4, AES.MODE_ECB)
            if(AES_y.encrypt(AES_z.encrypt(pt)) in dic.keys()):
                print(dic[AES_y.encrypt(AES_z.encrypt(pt))],y,z)

#('A_*', 'c=e') A?S _c*
wxyz = b"_c*A?Sc=eA_*"
key = sha256(wxyz).digest()
flag = AES.new(key, AES.MODE_ECB).decrypt(enc_flag)
print(flag)


#crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}



Read between the lines

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#!/usr/bin/env python3

from random import shuffle
from Crypto.Util.number import getPrime


with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

assert len(FLAG) < 100

encoded_flag = []

for i, b in enumerate(FLAG):
    encoded_flag.extend([i + 0x1337] * b)

shuffle(encoded_flag)

e = 65537
p, q = getPrime(1024), getPrime(1024)
n = p * q
c = sum(pow(m, e, n) for m in encoded_flag) % n

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n{e = }\n{c = }\n')

output.txt：

1
2
3
n = 11570808501273498927205104472079357777144397783547577003261915477370622451850206651910891120280656785986131452685491947610185604965099812695724757402859475642728712507339243719470339385360489167163917896790337311025010411472770004154699635694228288241644459059047022175803135613130088955955784304814651652968093606122165353931816218399854348992145474578604378450397120697338449008564443654507099674564425806985914764451503302534957447420607432031160777343573246284259196721263134079273058943290282037058625166146116257062155250082518648908934265839606175181213963034023613042840174068936799861096078962793675747202733
e = 65537
c = 7173375037180308812692773050925111800516611450262181376565814072240874778848184114081029784942289615261118103256642605595499455054072839201835361613983341298973366881719999836078559255521052298848572778824157749016705221745378832156499718149327219324078487796923208917482260462508048311400560933782289383624341257636666638574026084246212442527379161504510054689077339758167386002420794571246577662116285770044542212097174474572856621921237686119958817024794843805169504594110217925148205714768001753113572920225449523882995273988088672624172009740852821725803438069557080740459068347366098974487213070886509931010623

对于flag中的每个字符，记其ord值为ci，题目会生成：

1
ci * [i + 0x1337]

并加入列表，其中i是字符在flag中的索引。

生成完整列表后，题目将列表打乱，并计算每个值在模n下的e次方后，给出和c，要求还原flag。

由于flag长度小于100，假如将flag填充尾0，一直至长度为100的话，列表里的值其实范围就是：

那么就有如下线性关系：

所以类似背包去做LLL就行了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *

n = 11570808501273498927205104472079357777144397783547577003261915477370622451850206651910891120280656785986131452685491947610185604965099812695724757402859475642728712507339243719470339385360489167163917896790337311025010411472770004154699635694228288241644459059047022175803135613130088955955784304814651652968093606122165353931816218399854348992145474578604378450397120697338449008564443654507099674564425806985914764451503302534957447420607432031160777343573246284259196721263134079273058943290282037058625166146116257062155250082518648908934265839606175181213963034023613042840174068936799861096078962793675747202733
e = 65537
c = 7173375037180308812692773050925111800516611450262181376565814072240874778848184114081029784942289615261118103256642605595499455054072839201835361613983341298973366881719999836078559255521052298848572778824157749016705221745378832156499718149327219324078487796923208917482260462508048311400560933782289383624341257636666638574026084246212442527379161504510054689077339758167386002420794571246577662116285770044542212097174474572856621921237686119958817024794843805169504594110217925148205714768001753113572920225449523882995273988088672624172009740852821725803438069557080740459068347366098974487213070886509931010623

L = Matrix(ZZ,102,102)
for i in range(100):
    L[i,i] = 1
    L[i,-1] = pow(i+0x1337, e, n)
L[-2,-2] = 1
L[-2,-1] = c
L[-1,-1] = n
L[:,-1:] *= n
res = L.LLL()
flag = res[0][:-2]
for i in flag:
    print(chr(i), end="")


#crew{D1d_y0u_3xp3cT_LLL_t0_b3_h1Dd3n_b3tw3en_th3_l1n3s???}



Boring LCG

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
import os
from sage.all import *
set_random_seed(1337)
Fp = GF(6143872265871328074704442651454311068421530353607832481181)
a, b = Fp.random_element(), Fp.random_element()

flag = (os.getenv('flag') or 'crew{submit_this_if_desperate}').encode()
s = Fp.from_integer(int.from_bytes(flag[len('crew{'):-len('}')], 'big'))

out = []
for _ in range(12): out.extend(s:=a*s+b)
print([x>>57 for x in out])
# [50, 32, 83, 12, 49, 34, 81, 101, 46, 108, 106, 57, 105, 115, 102, 51, 67, 34, 124, 15, 125, 117, 51, 124, 38, 10, 30, 76, 125, 27, 89, 14, 50, 93, 88, 56]

看上去好像很容易，就是LCG的连续高位泄露而已，做HNP就行了。

然而实际上手会发现，Fp中的数值并不是一个素数，而是：

所以这实际上是一个三次扩域上的LCG递推，而泄露的则是每个state中系数di、ei、fi的高位：

由于三次扩域上，所有运算可以看作是模一个不可约多项式的多项式计算，这个不可约多项式可以用modulus函数调出来，是：

由于泄露高位，所以要往格上去靠，类似于NSSCTF Round18中的Ring3的推理过程，我们可以把所有三次扩域中的元素用一个三维向量表示，代表二次项、一次项和常数项的系数：

那么在商环下与元素a的乘运算是可以写成向量与矩阵相乘的形式的，这个矩阵具体如何生成可以参考NSSCTF Round18中的Ring3的wp：

2024-NSSCTF-Round-18-Basic-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

这里就直接跳过这个矩阵的生成过程，记他为L，那么LCG的递推过程就可以写成矩阵方程形式：

写出这个形式就不难推理出最终HNP应该怎样用格规约了，具体细节参考solver。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
from Crypto.Util.number import *

#aim to construct a matrix of c=a*b%v
def construct_poly_mul_mat(n,v,b):
    assert v[-1] == 1 #use this after monic

    #step1 construct a matrix of d=a*b
    mat1 = Matrix(ZZ,n,2*n-1)
    for i in range(n):
        for j in range(n):
            mat1[i,j+i] = b[j] 

    #step2 construct a matrix of c=d%v
    mat2 = Matrix(ZZ,2*n-1,n)
    for i in range(n):
        mat2[i,i] = 1
    for i in range(n,2*n-1):
        for j in range(i-n,n):
            mat2[i,j] = -v[j-(i-n)]
        
        init_row = vector(ZZ,n*[0])
        for j in range(i-n):
            temp = -v[n-1-j]*vector(ZZ,mat2[i-j-1])
            init_row += temp
        for j in range(n):
            mat2[i,j] += init_row[j]   
             
    #step3 multiply them and return
    return(mat1*mat2)

#################################################### part1 construct modpoly
set_random_seed(1337)
p = 18315300953692143461
F = GF(p)
Fp = GF(p^3)
mod = Fp.modulus()
a, b = Fp.random_element(), Fp.random_element()
aa, bb = a, b
s = Fp.random_element()

A = construct_poly_mul_mat(3,mod.list(),a)
#print(a*s)
#print(vector(F,s.list())*A)


#################################################### part2 construct Lattice
shift = 57
out = [50, 32, 83, 12, 49, 34, 81, 101, 46, 108, 106, 57, 105, 115, 102, 51, 67, 34, 124, 15, 125, 117, 51, 124, 38, 10, 30, 76, 125, 27, 89, 14, 50, 93, 88, 56]
nums = len(out)//3
h = [out[3*i:3*i+3] for i in range(nums)]
a, b = vector(F,a.list()), vector(F,b.list())
L = Matrix(ZZ,3*nums+1+3*(nums-1),3*nums+1+3*(nums-1))
for i in range(nums):
    L[3*i,3*i] = 1
    L[3*i+1,3*i+1] = 1
    L[3*i+2,3*i+2] = 1
L[3*nums,3*nums] = 2^shift

for i in range(nums-1):
    for j in range(3):
        L[3*i,3*nums+1+3*i+j] = A[0,j]
        L[3*i+1,3*nums+1+3*i+j] = A[1,j]
        L[3*i+2,3*nums+1+3*i+j] = A[2,j]

    L[3*i+3,3*nums+1+3*i] = -1
    L[3*i+4,3*nums+1+3*i+1] = -1
    L[3*i+5,3*nums+1+3*i+2] = -1
    
    si, si_1 = vector(F, [j*2^shift for j in h[i]]), vector(F, [j*2^shift for j in h[i+1]])
    ci = si*A + b - si_1
    L[3*nums,3*nums+1+3*i] = ZZ(ci[0])
    L[3*nums,3*nums+1+3*i+1] = ZZ(ci[1])
    L[3*nums,3*nums+1+3*i+2] = ZZ(ci[2])

    L[3*nums+1+3*i,3*nums+1+3*i] = p
    L[3*nums+1+3*i+1,3*nums+1+3*i+1] = p
    L[3*nums+1+3*i+2,3*nums+1+3*i+2] = p

L[:,-3*(nums-1):] *= p
res = L.LLL()[0]
s0l = res[:3]
print(res)

s0 = [ZZ(i+j*2^shift) for i,j in zip(s0l,out[:3])]
s = s0[0]*p^0 + s0[1]*p^1 + s0[2]*p^2
s = Fp.from_integer(s)
s = (s-bb)*aa^(-1)
print(long_to_bytes(s.to_integer()))


#crew{n0rm4l_LCG_but_1_d1d_xxx}



Bigger and better

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long
from secrets import randbelow, choice
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from string import ascii_letters, digits
from flag import flag


key = "".join([choice(ascii_letters + digits) for i in range(150)]).encode()

blocklen = len(key)//5
polsize = 25
maxexp = 3

V, W, X, Y, Z = [bytes_to_long(b) for b in [key[blocklen*i:blocklen*i+blocklen] for i in range(5)]]

n = getPrime(4096)*getPrime(4096)*getPrime(4096)*getPrime(4096)
n = n^2

K = Zmod(n)
PP.<v, w, x, y, z> = PolynomialRing(K)

coeffs = [K.random_element() for i in range(polsize)]

pol = 0
for l in range(polsize):
    while True:
        i, j, k, s, t = [randbelow(maxexp) for _ in range(5)]
        if i == j == k == s == t == 0: continue
        pol = pol + coeffs[l] * v^i * w^j * x^k * y^s * z^t
        if len(pol.coefficients()) == l + 1:
            break

c = pol(V, W, X, Y, Z)
pol = pol - c
assert pol(V, W, X, Y, Z) == 0

key = sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
c = cipher.encrypt(pad(flag, 16)).hex()

with open("output.txt", "w") as f:
    f.write(f"{blocklen = }\n")
    f.write(f"{n = }\n")
    f.write(f"{pol = }\n")
    f.write(f"{c = }\n")

output太长了，不放在这里。

整个题目其实就是给出一个模n下以$(V,W,X,Y,Z)$为根的多项式pol，要求解出这个根从而还原flag。显眼的地方就是n特别大，而V、W、X、Y、Z都是30个字符组成串的整数值，所以相比而言就很小。

自然而然就会想到copper，但是可以想见直接copper的话项数多、度也不小，所以直接用格解决发现直接就行。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES

blocklen = 30
K = Zmod(n)
PP.<v, w, x, y, z> = PolynomialRing(K)
n = 
pol = 
c = '92bbb516b6e04ac3c39df6834328028fc4525cd5c97eb220bf7be20d6d6db596'

coeff = pol.coefficients()
print(pol.monomials())

L = block_matrix(ZZ,[
    [1,Matrix(ZZ,coeff).T],
    [0,n]
])
for i,j in enumerate(pol.monomials()):
    L[i,i] *= (256^30)^(9-j.degree())
L[:,-1:] *= n
res = L.LLL()

tt = []
for i,j in zip(pol.monomials(),res[0]):
    tt.append(j // (256^30)^(9-i.degree()))

xx = GCD(tt[-2],tt[-3])
ww = tt[-2] // xx
zz = tt[-4] // xx // ww
vv = int(sqrt(tt[-7] // xx // zz))
yy = tt[-5] // vv // zz // xx

key = long_to_bytes(vv) + long_to_bytes(ww) + long_to_bytes(xx) + long_to_bytes(yy) + long_to_bytes(zz)
#key = long_to_bytes(ww) + long_to_bytes(xx) + long_to_bytes(zz)
print(key)

key = sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(bytes.fromhex(c))
print(flag)


#crew{LLL1ne4r1z4ti0n_15_c0oLLL}



*Admin

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
from os import urandom
from sys import exit
import string

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

blksize = AES.block_size


def getintinput(msg):
    opt = input(msg)
    try:
        opt = int(opt)
    except:
        return -1
    return opt


def gethexinput(msg):
    opt = input(msg)
    opt = opt.strip()
    if all([ele in string.hexdigits for ele in opt]):
        return opt.encode()
    else:
        return b""


def givetoken(key, i):
    iv = bytes.fromhex(gethexinput("iv(hex): ").decode())
    if len(iv) != blksize:
        print("iv is invalid.")
        return None
    cipher = AES.new(key, AES.MODE_GCM, nonce=iv)
    curusername = b'not_admin_username_' + str(i).encode()
    enc, tag = cipher.encrypt_and_digest(pad(curusername, blksize))
    return (curusername.decode(), iv.hex(), enc.hex(), tag.hex())


def checktoken(key):
    token = bytes.fromhex(gethexinput("token(hex): ").decode())
    if len(token) % blksize != 0 or len(token) <= 2*blksize:
        print("token is invalid.")
        return None
    iv = token[:blksize]
    tag = token[-blksize:]
    enc = token[blksize:-blksize]

    cipher = AES.new(key, AES.MODE_GCM, nonce=iv)
    try:
        dec = unpad(cipher.decrypt_and_verify(enc, tag), blksize)
    except ValueError:
        print("tag may be invalid.")
        return None
    if dec == b"admin":
        print("congrats, give you the flag.")
        flag = open('/flag.txt', 'rb').read().strip().decode()
        print(flag)
        return 1
    else:
        print("you are not admin user.")
        return 0


def banner():
    banner = [
        "#"*80,
        "AES challenge",
        "#"*80,
    ]
    print('\n'.join(banner))


def menu():
    menu = [
        "",
        "0: get token",
        "1: check admin token"
    ]
    print('\n'.join(menu))


def main():
    key = urandom(blksize)
    i = 0
    banner()
    try:
        while (True):
            menu()
            opt = getintinput("option(int): ")
            if opt == 0:
                result = givetoken(key, i)
                if result is None:
                    break
                curusername, iv, enc, tag = result
                print(f"token for {curusername} is: \n{iv + enc + tag}")
                i += 1
            elif opt == 1:
                result = checktoken(key)
                if result is None or result == 1:
                    break
            else:
                break
    except:
        print("error occured.")
        exit(1)

    print("bye")
    exit(0)


if __name__ == "__main__":
    main()

题目基于AES的GCM模式，连接上靶机后会随机生成key，并且提供了一个oracle，其中有两个选项：

  • 可以无限次输入0，可以进入givetoken函数，具体步骤为：
    • 可以自己输入一个iv，长度必须为16
    • 用这个iv和key初始化一个AES-GCM加密器cipher
    • 生成一段明文pt，内容是b'not_admin_username_' + str(i).encode()，并填充到16的倍数。其中i是随调用oracle次数递增的数值
    • 用cipher加密这段明文得到enc和tag，并返回pt、iv、enc和tag
  • 可以输入一次1，之后输入iv，如果能给出一段密文和tag，使得AES-GCM解密后unpad得到”admin”这个明文，并且能通过tag认证就可以拿到flag了

由于iv可以自己控制，所以显然这是针对AES-GCM模式的nonce复用攻击。GCM可以看作是：加密部分为CTR模式，然后额外附带了消息认证功能，也就是tag。

由于CTR模式长这样：

image-20240805111544248

可以看出他加密的是nonce+counter，而最终产生密文的步骤仅仅是与明文异或而已，所以在iv可以自行控制的前提下，篡改解密出的结果根本不是问题，因此主要问题落在了如何伪造tag上。

搜索一下可以发现这篇文章，介绍了一种对GCM模式nonce复用的攻击，叫做forbidden attack：

UTCTF 2020 - Crypto Challenges (meowmeowxw.gitlab.io)

文章讲的相当详细了，总结一下主要有以下几个要点：

  • AES对16字节全0的加密结果其实就是GHASH的子密钥，记作H0，因此能获得这个结果的话，就可以对任意消息伪造tag

  • GHASH工作在GF(2^128)上，所有元素之间的运算可以看作是模如下多项式的多项式运算：

    Ci是密文的每个block块，EJ是AES对 nonce|| 1的加密结果，L是 8x0 || 8xlen(C)

    注意这里没考虑Associated data，具体参考上面的文章

  • 记len(C)为小写l，那么这个多项式具体可以写成：

  • 由于在这个域中，对于任意元素a，其两倍均为0；所以对于相同长度、并且nonce复用的两组tag，有：

  • 相加之后，显然末尾的EJ、LH0都会由于乘了2而消去，那么由于T1、T2、C1、C2我们都知道，所以整个相加后的式子就是只关于H0的多项式了，因此进行求根，其中就有一个会是正确的H0，求出H0后自然也就可以求出EJ，然后就可以伪造tag了。

这个攻击比预想中要容易理解很多，然而实际操作会发现一个问题是：EJ似乎并不像文章说的一样，是对nonce|| 1的AES加密结果，对于有不同个分组的密文来说EJ并不一样。所以虽然测试的确可以求出正确的H0，但由于每次返回的pt都是两个分组的，而我们需要解出的明文只能是pad("admin",16)，所以如果没有它对应的EJ，就没有特别好的办法伪造tag，这个题目最后也卡死在这里了。

搜索很多文章，其实都说EJ就是这个含义，这就很奇怪。因为实际上来说并不需要知道EJ的具体含义究竟是啥，他只要对于不同分组长度的密文来说都是个定值就行，但实际上不是。

放点测试脚本在这里吧，之后学会了回来更一更：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
from Pwn4Sage.pwn import *
from Crypto.Util.number import long_to_bytes as lb
from Crypto.Util.number import bytes_to_long as bl
from binascii import unhexlify, hexlify
import struct
from Crypto.Cipher import AES

def bytes_to_polynomial(block, a):
    poly = 0 
    # pad to 128
    bin_block = bin(bl(block))[2 :].zfill(128)
    # reverse it to count correctly, wrong don't reverse it lol
    # bin_block = bin_block[::-1]
    for i in range(len(bin_block)):
        poly += a^i * int(bin_block[i])
    return poly

def polynomial_to_bytes(poly):
    return lb(int(bin(poly.to_integer())[2:].zfill(128)[::-1], 2))

def convert_to_blocks(ciphertext):
    return [ciphertext[i:i + 16] for i in range(0 , len(ciphertext), 16)]

def xor(s1, s2):
    if(len(s1) == 1 and len(s1) == 1):
        return bytes([ord(s1) ^^ ord(s2)])
    else:
        return bytes(x ^^ y for x, y in zip(s1, s2))

F, a = GF(2^128, name="a", modulus=x^128 + x^7 + x^2 + x + 1).objgen()
R, x = PolynomialRing(F, name="x").objgen()

# Set correct values
key = b"1"*16
iv = b"\x00"*12


cipher = AES.new(key, AES.MODE_GCM, nonce=iv)
pt1 = b'3'*32
C1, T1 = cipher.encrypt_and_digest(pt1)
C1 = convert_to_blocks(C1)

cipher = AES.new(key, AES.MODE_GCM, nonce=iv)
pt2 = b"4"*32
C2, T2 = cipher.encrypt_and_digest(pt2)
C2 = convert_to_blocks(C2)

cipher = AES.new(key, AES.MODE_GCM, nonce=iv)
pt3 = b"5"*32
C3, T3 = cipher.encrypt_and_digest(pt3)
C3 = convert_to_blocks(C3)

################################################# test
nonce = b"\x00"*16
ECB = AES.new(key, AES.MODE_ECB)
H0 = ECB.encrypt(nonce)
print(T3)
print(H0)


L = struct.pack(">QQ", 0 * 8, len(C1) * 8)
C1_p = [bytes_to_polynomial(C1[i], a) for i in range(len(C1))]
C2_p = [bytes_to_polynomial(C2[i], a) for i in range(len(C2))]
C3_p = [bytes_to_polynomial(C3[i], a) for i in range(len(C3))]
T1_p = bytes_to_polynomial(T1, a)
T2_p = bytes_to_polynomial(T2, a)
L_p = bytes_to_polynomial(L, a)
# Here G_1 is already modified to include the tag
def make_poly(C_p,L_p):
    G = 0
    for c in C_p + [L_p]:
        G += c
        G *= x
    return G

G_1 = make_poly(C1_p,L_p) - T1_p
G_2 = make_poly(C2_p,L_p) - T2_p


L3 = struct.pack(">QQ", 0 * 8, len(C3) * 8)
L3_p = bytes_to_polynomial(L3, a)
G_3 = make_poly(C3_p,L3_p)


P = G_1 + G_2
for H, _ in P.roots():
    EJ = G_1(H)
    TT3 = G_3(H) + EJ
    print()
    print(polynomial_to_bytes(EJ))
    print(polynomial_to_bytes(H))



*Noisy Encryption

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import secrets
import sympy

FLAG="crew{fake_flag}"
BITS=512
LIM=pow(2,BITS)

while True:
	while (not sympy.isprime(p:=secrets.randbelow(LIM//2)+LIM//2)) or (p-1)%3==0:
		pass

	while (not sympy.isprime(q:=secrets.randbelow(LIM//2)+LIM//2)) or (q-1)%3==0:
		pass

	n=p*q
	if n>pow(2,1023):
		break

phi=(p-1)*(q-1)
e=3
Secret=secrets.randbelow(LIM)
d=pow(e,-1,phi)
sig=pow(Secret,d,n)

print("The signature is: "+str(sig))

def hamming_weight(x):
	return sum([int(y) for y in bin(x)[2:]])


while True:
	print("I can encrypt anything for you! But the bits may get messy")
	msg=input()
	if msg=="guess":
		print("Do you know the secret?")
		msg=int(input())
		if msg==Secret:
			print("You sure do! Here is your prize:")
			print(FLAG)
			exit(0)
		else:
			print("Wrong answer!")
			exit(0)
	msg=int(msg)
	enc=pow(msg,3,n)
	print(hamming_weight(enc)%2)

一个有趣的oracle，题目会先生成RSA公钥n，然后以e=3作为加密指数，求出d过后如下计算sig并给出：

然后可以无限次调用oracle：

  • 输入msg，可以返回msg^3模n后的汉明重量的奇偶性
  • 如果输入的msg是guess，那么可以再次输入msg，如果输入值等于Secret就可以拿到flag

这个题目最主要的地方在于还原n，因为有n的话，直接对sig计算三次方就有Secret了。

一个思路是，可以先找出一个a，使得：

这样可以先将n卡在一个700bit左右的误差范围内。而找的方式为：

  • 本地计算a^3不模n的汉明重量奇偶性
  • 发送a给靶机，看返回的汉明重量奇偶性是否与本地计算结果相等
  • 如果不相等，说明a^3一定大于n，因为一定是因为模n才改变了汉明重量奇偶性
  • 但如果相等，也不能说明a^3小于n，因为模n也不一定会改变汉明重量就行，所以要连续多次测试才能减小错误概率

这一部分本地测试脚本如下，可以将n卡在a^3到(a+15)^3之间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import secrets
import sympy
from gmpy2 import iroot,powmod

FLAG="crew{fake_flag}"
BITS=512
LIM=pow(2,BITS)

while True:
	while (not sympy.isprime(p:=secrets.randbelow(LIM//2)+LIM//2)) or (p-1)%3==0:
		pass

	while (not sympy.isprime(q:=secrets.randbelow(LIM//2)+LIM//2)) or (q-1)%3==0:
		pass

	n=p*q
	if n>pow(2,1023):
		break

phi=(p-1)*(q-1)
e=3
Secret=secrets.randbelow(LIM)
d=pow(e,-1,phi)
sig=pow(Secret,d,n)

def hamming_weight(x):
	return sum([int(y) for y in bin(x)[2:]])


################################################################################# below is my test
def stable_test(a):
	for i in range(15):
		if(hamming_weight(pow(a+i,3)) % 2 != hamming_weight(powmod(a+i,3,n)) % 2):
			return False
	return True

a = int(iroot(sig,3)[0])  #sig < n --> a^3 < n

for i in range(340,-1,-1):
    a += 2**i
    if(stable_test(a)):
        continue
    else:
        a -= 2**i

t1 = (a)**3
t2 = (a+15)**3
assert t1 < n and t2 > n

e1 = n-t1
e2 = n-t2
print(len(bin(e1)), len(bin(e2)))

这样确实把n卡在了一个稍微小一点的范围内，换句话说也就是知道了n的高300位左右，但我们需要的是完全准确的n，那然后呢？

可能的几个点是：

  • Secret本身其实只有512bit，在模n下比较小，那有没有一种技术可以利用格在模有误差的n下把他恢复？但是完全没想到

  • 可以发送负数，比如-2^i，这样返回的结果其实是n-2^3i的汉明重量奇偶性。这样做的好处在于，-2^3i对n来说只影响了其中1bit

    比如最直接的就是发-1过去，然后能获得n-1的汉明重量奇偶性，又因为n一定是奇数，所以实际上也就是知道了n的汉明重量奇偶性

但还是没有特别清晰的主意，看了下discord发现有个大概的思路是：

image-20240805145544461

这个思路是对第二点的改进，从发-2^i改成发-u*2^i，这样可以在特定的比特位置减去u^3，而不仅仅局限于减1bit。

但是还是没太搞懂怎么能唯一确定下来某个bit，学会再更。