初めに
そういえば今年入ってから書いて無かったなぁとか思ったので今更ですが書きます。 といってもそんな書くことないんですがね…
てか、HNPが32 solveってみんな賢すぎでしょ…正直レベル上がりすぎて怖いです…
[crypto] leaky-dsa [32 solve]
chall
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
from Crypto.Util.number import *
from secret import flag
from hashlib import sha256
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
q = G.order()
priv = Integer(bytes_to_long(flag))
def sign(msg, d):
k = int.from_bytes(sha256(int(d).to_bytes(d.nbits()//8 + 1, 'big') + sha256(msg).digest()).digest(), 'big')
z = int.from_bytes(sha256(msg).digest(),'big')
r = int((k * G)[0]) % q
s = (inverse_mod(k, q) * (z + d * r)) % q
leak_k = (k >> 120) << 120
return z, r, s, leak_k
for i in range(2):
msg = input("Enter message: ").encode()
print(sign(msg, priv))
solve
なんか、$k$の上位120bitがリークされているので実質の$k$のビットサイズは136bit程度、HNPのLLLでなんとかなりそう
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
from pwn import *
from Crypto.Util.number import *
from random import randint
from sage.modules.free_module_integer import IntegerLattice
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
E = EllipticCurve(GF(p), [a,b])
# 256bit
q = E.order()
ret = []
N =1
for _ in range(N):
io = remote("crypto.chall.bi0s.in" ,10000)
io.sendlineafter(b": ",str(randint(0,100)).encode())
ret.append(eval(io.recvline(None).decode()))
io.sendlineafter(b": ",str(randint(0,100)).encode())
ret.append(eval(io.recvline(None).decode()))
io.close()
Z = [ret[i][0] for i in range(len(ret))]
R = [ret[i][1] for i in range(len(ret))]
S = [ret[i][2] for i in range(len(ret))]
T = [ret[i][3] for i in range(len(ret))]
N = len(Z)
mat = matrix(QQ,N+2,N+2)
for i in range(N):
mat[i,i] = -q
mat[-2,i] = (pow(S[i],-1,q) * (Z[i] - T[i]*S[i]))%q
mat[-1,i] = (pow(S[i],-1,q) * R[i])%q
mat[-2,-2] = 2^136
mat[-1,-1] = 2^136/q
for row in mat.LLL():
if abs(row[-2]) == 2^136:
d = abs(row[-1]) * q/2^136
print(long_to_bytes(int(d)))
exit()
# 3CC_S1gn1nG_1s_SECCY_6675636b
# bi0sctf{3CC_S1gn1nG_1s_SECCY_6675636b}
[crypto] bad2code [24 solve]
chall
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
from Crypto.Util.number import *
from secrets import FLAG
assert len(FLAG) == 44
FLAG_FORMAT = "bi0s"
NBITS = len(FLAG)<<2
a = 0xBAD2C0DE
c = 0x6969
m = 1<<NBITS
seed = getRandomNBitInteger(NBITS)
state = seed
ciphertext = []
for i,f in enumerate(FLAG):
state = (state*a+c)%m
ciphertext.append((state>>(NBITS>>1))^^i^^ord(f))
public = [1]
for i in range(2, 91):
public.append(public[-1]*i)
q = sum(public)
while True:
r = getRandomInteger(100)
if GCD(r, q) == 1:
break
B = [r*i % q for i in public]
def encrypt(ct):
blen = ct.bit_length()
ct = bin(ct)[2:]
ct = [int(i) for i in ct]
ct = [ct[i]*B[i] for i in range(len(ct))]
return blen, sum(ct)
ct = []
for i in ciphertext:
ct.append(encrypt(i))
with open("ct.txt", "w") as f:
f.write(str(ct))
print(r)
# r = 439336960671443073145803863477
solve
ファイルの変更で$r$の値が分かるようになってたみたい…??(未確認) まぁ、気を取り直して問題は、truncated LCG → xor → bitにして積の計算を行っている感じなので、順に後ろからやっていく
- bitにして積の計算は$B$がわかるのでLLLでsubset sum problemで解決
- truncated LCGからパラメータの復元
HITCON CTF 2022 writeup で書いてある感じで$ciphertext$の復元を行う。
truncated LCGはkurenaifさんが詳しく解説されているようにすればok
あとは平文範囲を1文字づつ探索してGG!!
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
from Crypto.Util.number import *
from tqdm import tqdm
# assert len(FLAG) == 44
FLAG_FORMAT = "bi0s"
# NBITS = len(FLAG)<<2
# 11 bits
NBITS = 44 <<2
A = 0xBAD2C0DE
C = 0x6969
m = 1<<NBITS
cts = [(85, 2009755672435753240933297922620729942110285100089234834611189610638944428122270966606450209287004686147490741726074233399923807772025455384), (87, 4996607263053501712119670315411210635641476911112656716346186101581162098939506206462698692878856867719374177604968008598982986859155008123), (87, 4837953870616520482139098354277306810171956043791834010204071803405678054968703256907153189059041329376000508442178425613919361101370091597), (87, 2933251583165904105425041103443198171501175581919361545836839336222902826332690613281372817019459906816365925875888304559050438360535693754), (87, 3687643521316276110350069295074808763624177150637370283489602776297956670406673088896906135313859622547057266461156951352840606158133939326), (85, 1338269001646504891852362627714857562957599731250242281507737655117481275381522940187354460968741738873145343823622277547003496172474140929), (88, 7933296831307546148859657742504382496951023270916400508699917815337497611045057441275885597739792345698682705664067022591023419704320903682), (88, 5551940689407978486506000896917506389553250109195458521661213619690861850998613004330276887098156130761269810440548744569924180624922795113), (84, 4231118499738387243085586897653540321361890016337481573279774741827125072054069869204040621495890626440611926639348835434382399384680055422), (85, 4704615409370307656606356674605132679559694819773906599372238093928995241862651680281288235856744305731307534075261385839804274777809615349), (88, 8080256207998531514821351856269697662773084407605094205301308544428843939544685672982309353297946702140050231399104513874885470725033197665), (88, 5409126049900711181553897969759692389994841569000620092514718715454021797905578507700126871105210241868943216288008246115824215988452628610), (87, 9252119153621946581189075112355267174890952393437560488066048810424246555795717704306898381332924931192879341998003358581626937969846419514), (88, 4309485343027874993328683769447337855319861832898927390313412221773647599911173732334028315977555272520439642698050646195173212678056296824), (87, 7585821393024154059281324167310518147335428246416250953866063679865301977430635054486170591035445789330984486529581273451159109931487791502), (87, 4266559781861060657731014334455291598689251074723949797856286897802219958857948301662899795696748957745131495362941575798432727634477829169), (85, 2641970821454174926450206596995181582610648509828849026215891906920020076919398240347027542452996819530972432115175678566086129470049375389), (86, 3077438307667140950446795937461054813957511252383671895612002141778156796698300700433893422617209993376314581927862590976739430303756825799), (84, 6606999799754153651147831000154190219518207430742825676139927743071667153908159445512098245423654757585044526053832363134210629951000894424), (88, 5670578370066772514741437284311647297873639929831922637574590430528630079731096253156055423807240883352926044290617794045498770071653673648), (87, 6894132144232319468740512750496837680809983881874187255032194645685827169634783788480774942267705885439820208999500465383743432841886297780), (88, 6348559834296411797469331328911826454137045759724408730535584371919321718963812479226912064993936288733920150791627489465935504738729746712), (87, 7457067309408071136462520290099813600595760616382451252266638576757556195357758384430233685566475045370258747830063483558129016033041534121), (87, 7138834056650788599340304091245357448689914704543367476875970477848587821892811763578094466693024724929034161719556439516286550418480386826), (85, 4214620981374285095640824086913124961419729602098347661701803957979165936606167686524401563099707189265200486482516005732059773306234258420), (87, 7739066385937951930229094506964291860284170243142110190122036300802992602806430896564185899709833543891933679072444463084661529668059219104), (86, 7996763147644153267931052506581385268378745125996592054161290689392831593366496210631236238142447646254463386914159791951904746842709666621), (83, 2363927368088545362888027832425184786062409622322321649991521010872009124933023792724085312213031828468440431258319304817389205319949123017), (86, 8952178949693065428977346330331508030115172989418887909205463101008773555390353195154597245789628940426095401145185560848927781578325104633), (87, 5437733249052136209105079687557091961563919494484950700755430118355692330802405578709308644911805929080699188377572804834481019970451287210), (88, 6015299972513982077146707497576267202666793107003902152334693697774096888512046451228148219477544391600946101222260160929679756603685952858), (88, 4568852671731251436040898868989551602956632306950375030804513367391992286782270552341135397170272362552944089560054885656717064705695931608), (88, 5214418374014497232007521802148945843762329611158152570151078790657020448385624421117820553224634987052518291618670107521494031262847423514), (85, 4868781049816097655711690233312446779184038900364456479177916582789767967134191139603006712483609665048365174590374678749717762853252392898), (87, 7487878378499555558388350908281092245535427011554302229088273963701472371659945154073798520163320208196872977374676841353329741664704431049), (88, 4804650300297155317595282760599161747288241275410480931480258003053935686370721999717184367371623277273540661128542000775004283694728585525), (87, 6324353155591926121419512579497192374524354396151314193997508188259969434627055717937503525281909856550845807173753553651932260148517039625), (87, 5546469224661430242652418747991106002905180051710879985326544434722895447041925331360634907813012794515907098935485171653197695779005009826), (86, 6493922061250196900387871627336695511599800586007321943800903718034500613505566204881495072235610494479661303981584755703237874004730700241), (84, 3304267236247240014753455621608696126482869339445549240138779235284450054938719633292333925332195771054789798560540593262065547955691287860), (86, 7470707627092056238764393981318045721888042683539521453158125764519328859948265999477619788387120366063077899885955739104933799243393828710), (88, 6674831873895816998217860257081780104168741154329195649911902365299495130324698497916172758145782383658122037059537201009889153133307754158), (88, 5323014117483698150842190422231005724805137799598831691161862346623039247622359972881775361362745899238680458901399065283489317592046388919), (85, 3763698408921732607951773848228884704668238062686979349129116312470621538052054791662510364394420612090312977770614743449723324784458538150)]
r = 439336960671443073145803863477
public = [1]
for i in range(2, 91):
public.append(public[-1]*i)
q = sum(public)
B = [r*i % q for i in public]
def encrypt(ct):
blen = int(ct).bit_length()
ct = bin(ct)[2:]
ct = [int(i) for i in ct]
ct = [ct[i]*B[i] for i in range(len(ct))]
return blen, sum(ct)
def recover_ciphertext(c):
N = len(B)
M = matrix(QQ, N+1,N+2 )
for i in range(N):
M[i,i+1] = 1/65537
M[i,0] = -B[i]
M[-1,0] = c
M[-1,-1] = 2*q
for row in M.LLL():
if abs(row[-1]) == 2*q:
return list(row*65537)[:-1]
state = []
for i in range(4):
ciphertext = [str(k) for k in recover_ciphertext(cts[i][1])]
l = cts[i][0]
c = int("".join(ciphertext[:l+1]),2)
state.append(int(c)^^int(i)^^int(ord(FLAG_FORMAT[i])))
from attacks.lcg.truncated_state_recovery import attack
ret = attack(state,int(m).bit_length(), int(m).bit_length() - (NBITS >>1),m,A,C)
pt = "b"
assert (ret[2]*A+C)%m ==ret[3]
assert (ret[0]*A+C)%m ==ret[1]
s = ret[0]
for i in range(1,44):
for f in range(0,0xff):
_s = (s*A+C)%m
c = int(_s>>(NBITS>>1))^^int(i)^^int(f)
ec = encrypt(c)
if ec[1] == cts[i][1]:
pt +=chr(f)
s = _s
break
else:
print("not found")
break
print(pt)
# bi0sctf{lcg_is_good_until_you_break_them_!!}