introduction
n1 junior crypto方向总的来说题是不难，有新意。本人也有幸拿下两个一血。
这篇文章是我的第一篇wp，也是发在博客上的第一篇文章，就当练练手吧
cc@
首先经过观察可以知道这个GCM是很安全的，因为他每一次都会换nonce，所以即使你知道了GCM的key也是没又说明用的。但是他的每次GCM加密前没有进行pad,那我们就可以根据GCM返回的位数来推断原数的大小
然后我们稍微了解一下ElGamal,知道他最后会产生一个私钥$x$,每次加密的时候会产生两个数$c_1,c_2$,满足对于传入的消息$m$，有$m = c_1^{-x}c_2$
我们$query(c_1, c_2)$ (或者说是oracle) 会返回$m$经过GCM解密的值,我们发现他是21bytes大小的，而理论上随机传进去两个数字的大小应该和模数p是一个量级的（64bytes）。这就给了我们可以攻击的角度。
我们可以$query(c_1,i * c_2)$,此时ElGamal返回的是i * m的值，注意因为m较小，返回的值我们可以当作是没有进行取模的原本的值。
假如我们能找到一个 $i$ 使得，query(c1,i * c2)返回是byte数是$k$ , 而query(c1, (i + 1) * c2)返回的byte数是$k+1$,那就说明$m * i < 256^{k+1} < m * (i+1) $, 然后这样我们就可以得到m的准确值了。
求解这个 $i$ 的话，我们可以先随便泡泡找到他的一个上界和一个下界，然后用二分的方法得到（然后其实虽然我们query只有100次机会，但其实每一次flag都不会变，100次用完了我们重新连接进行交互就行）
from pwn import *
IP, PORT = "101.34.72.206 1338".split()
# return c1, c2, p
def gift() -> (int, int, int):
conn.recvuntil(b"> ")
conn.sendline(b"g")
conn.recvuntil(b"c = [")
c1, c2 = map(int, conn.recvline().decode().strip()[:-1].split(","))
conn.recvuntil(b"p = ")
p = int(conn.recvline().decode().strip())
return c1, c2, p
def query(x: int, y: int) -> bytes:
conn.recvuntil(b"> ")
conn.sendline(b"o")
conn.recvuntil(b"data: ")
conn.sendline(f"{x},{y}".encode())
conn.recvuntil(b"[+] ")
recv_text = conn.recvline().decode().strip()
# print(recv_text)
return bytes.fromhex(recv_text)
conn = remote(IP, PORT)
L = 3000000000000000000000000000000000000000000000000000000000000
R = 5000000000000000000000000000000000000000000000000000000000000
c1, c2, p = gift()
while L != R:
mid = (L + R) // 2
if len(query(c1, mid * c2)) == 46:
L = mid + 1
else:
R = mid
print(L, R)
# L = 3939199615952307623545814154896359932381494589341879343811020
m = int("1" + "0" * 92, 16) // L + 1
iev@l
因为不会python jail而没做出来
谈谈思路，因为提示是meet in the middle，然后就想着类似于bsgs那样的枚举。接着我们要想想怎么反着走，根据
if last: j.remove(last)
然后再观察一下code的ihash过程中j_invariant和j数组的变化，我们可以猜测反着走和正着走其实类似。
然后我们就可以开始写meet in the middle 搜索函数了，参考下面的search函数。
搜索过程类似于下图
m到b的搜索路径理论上可以在search函数里面直接求出来，但这样子search函数就过于麻烦了，我没有这么干。
我选择的是求出了a到m到路径和b到m的路径之后再写一个函数（get_ans）反求m到b的路径。为什么我认为这个反向路径存在呢？对ihash过程的逐步观察和自信猜测。
几个注意的点，因为我们最后需要encode，而一个byte只需要第一位为0就一定能成功。正向路径的这个我们是可以控制的，反向路径就听天由命希望到时候check能过。
然后关于我们的cmd要怎么设计，我们要搜索什么，我讲一下我的心路历程吧。
刚开始我是打算把cmd设计成system(“……”)\n***************print(‘Welcome….’)在print前面的时候j变为0， 然后ihash本地过了，交上去没过。然后才知道pwn交互的时候会把\n直接截断，
然后打算是system(“…..”)……print(‘Welcome….’)然后发现这样根本运行不了直接报错
然后突然想到一些杂七杂八的符号可以加进指令里面，也就是system(‘cat \FLAG ***********’) 借用print(‘……’) 后两个符号。
对应到上图也就是
a = ihash(b"system('cat \FLAG ")
b = ihash(b"print('Welcome 2 n1junior")
，其实到这儿已经和答案很近了，只要百度搜一下python jail就能得到正确的注入方式。改成
a = ihash(b"__import__('os').system('cat /FLAG ")
b = ihash(b"print('Welcome 2 n1junior")
然后就能过了。
下面是完整的代码
from queue import Queue
from Crypto.Util.number import *
p = 2 ^ 12 * 3 ^ 13 - 1
F = GF(p ^ 2, modulus=x ^ 2 + 1, name="i")
def ihash(m: bytes):
p = 2 ^ 12 * 3 ^ 13 - 1
F = GF(p ^ 2, modulus=x ^ 2 + 1, name="i")
E_now = EllipticCurve(j=F(0))
bits = bin(int(m.hex(), 16))[2:].zfill(8 * len(m))
last = None
for _ in bits:
ker = E_now(0).division_points(2)[1:]
j = [E_now.isogeny(k).codomain().j_invariant() for k in ker]
if last:
j.remove(last)
# print(E_now.j_invariant(), j)
E_next = EllipticCurve(j=j[int(_)])
if E_next.j_invariant() == E_now.j_invariant():
print("Error Ring, Bad message!")
return None
last = E_now.j_invariant()
E_now = E_next
return E_now.j_invariant(), last
def bytes_to_bits(m):
return bin(int(m.hex(), 16))[2:].zfill(8 * len(m))
def hash_step(j: F, s: str, last=None):
E_now = EllipticCurve(j=F(j))
ker = E_now(0).division_points(2)[1:]
j = [E_now.isogeny(k).codomain().j_invariant() for k in ker]
if last:
j.remove(last)
return j[int(s)]
def ihash_bits(bits: str, track=False):
E_now = EllipticCurve(j=F(0))
last = None
for _ in bits:
ker = E_now(0).division_points(2)[1:]
j = [E_now.isogeny(k).codomain().j_invariant() for k in ker]
if last:
j.remove(last)
if track:
print(E_now.j_invariant(), j)
E_next = EllipticCurve(j=j[int(_)])
if E_next.j_invariant() == E_now.j_invariant():
print("Error Ring, Bad message!")
return None
last = E_now.j_invariant()
E_now = E_next
return E_now.j_invariant(), last
def search(hash_i: F, hash_j: F, l1=None, l2=None):
dic1 = {}
dic2 = {}
last1 = {}
last2 = {}
E1 = EllipticCurve(j=F(hash_i))
E2 = EllipticCurve(j=F(hash_j))
dic1[hash_i] = ""
dic2[hash_j] = ""
last1[hash_i] = l1
last2[hash_j] = l2
now1, now2 = F(hash_i), F(hash_j)
dic1[l1] = "-1"
dic2[l2] = "-1"
q1 = Queue()
q2 = Queue()
while 1:
ker = E1(0).division_points(2)[1:]
j = [E1.isogeny(k).codomain().j_invariant() for k in ker]
# print(j)
if last1[now1]:
j.remove(last1[now1])
for i in range(len(j)):
if len(dic1[now1]) % 8 == 0 and i == 1:
continue
if j[i] not in dic1:
dic1[j[i]] = dic1[now1] + str(i)
last1[j[i]] = now1
q1.put(j[i])
if j[i] in dic2 and len(dic1[j[i]] + dic2[j[i]]) % 8 == 0:
print(dic1[j[i]], dic2[j[i]])
ker = E2(0).division_points(2)[1:]
j = [E2.isogeny(k).codomain().j_invariant() for k in ker]
# print(j)
# print(last[now2])
if last2[now2]:
j.remove(last2[now2])
for i in range(len(j)):
if j[i] not in dic2:
dic2[j[i]] = dic2[now2] + str(i)
last2[j[i]] = now2
q2.put(j[i])
if j[i] in dic1 and len(dic1[j[i]] + dic2[j[i]]) % 8 == 0:
print(dic1[j[i]], dic2[j[i]])
now1, now2 = q1.get(), q2.get()
E1 = EllipticCurve(j=now1)
E2 = EllipticCurve(j=now2)
def get_ans(command: bytes, a1: str, code: bytes, a2: str) -> bytes:
command_bits = bytes_to_bits(command)
code_bits = bytes_to_bits(code)
n = len(a2)
j1, l1 = ihash_bits(command_bits + a1)
j2, l2 = ihash_bits(code_bits)
j2s = []
for i in range(n):
j2s.append(j2)
tmp = j2
j2 = hash_step(j2, a2[i], l2)
l2 = tmp
assert j1 == j2
if l1 == l2:
return b"\xff"
ans = command_bits + a1
for i in range(n - 1, -1, -1):
tmp = hash_step(j1, "0", l1)
if tmp == j2s.pop():
l1 = j1
j1 = tmp
ans += "0"
else:
tmp = hash_step(j1, "1", l1)
l1 = j1
j1 = tmp
ans += "1"
# print(ans)
assert ihash_bits(ans)[0] == ihash_bits(code_bits)[0]
# print(ihash_bits(ans)[0])
return long_to_bytes(int(ans, 2))
hash_1, l1 = ihash(b"print('Welcome 2 n1junior")
hash_2, l2 = ihash(b"__import__('os').system('cat /FLAG ")
search(hash_2,hash_1,l2,l1)
command = b"__import__('os').system('cat /FLAG "
code = b"print('Welcome 2 n1junior"
command_bits = bytes_to_bits(command)
code_bits = bytes_to_bits(code)
# 上一段代码的输出
lis = """......""".split("\n")
for line in lis:
# print(a1, a2)
a1, a2 = line.split()
m = get_ans(command, a1, code, a2)
f1 = 1
for i in m:
if i >= 128:
f1 = 0
break
if not f1:
continue
print(m, ihash(m)[1])
from pwn import *
IP, PORT = "101.34.72.206 1339".split()
conn = remote(IP, PORT)
print(conn.recvuntil(b">>> "))
conn.sendline(b"__import__('os').system('cat /FLAG \x16;B!C')")
print(conn.recv())
conn.close()
Junior_RSA
我们可以把p，q看成$BASE = 2^{256}$进制数，那么$p = \overline{\text{abc}},q = \overline{\text{cab}}$
条件就转化为了 $n = \overline{\text{abc}}\cdot \overline{\text{cab}}，e=65537abc$
我们可以先把$abc$求解出来
根据十进制乘法的经验，我们可以得出$pq %BASE = bc%BASE $ ，也可以写成$(aBASE^2+bBASE+c)(cBASE^2+aBASE+b)$然后展开，也能观察到这点
接着就能发现我们手头有$abc,bc%BASE$，然后a又是比BASE小的,考虑在Zmod(BASE)环中的除法就可以求出a
考虑为$pq$的低位，再来考虑高位，也能看出$pq$的高位主要由ac决定
$pq//BASE ^ 5 = ac // BASE \ \ \ (+1)$ 注意可能有进位，a有了,c的大小也能估计出来，这以后就水到渠成了
# sage
from Crypto.Util.number import *
n = 1224562468550864572988516321107388462006452125881847529675226398144888628055678744854491489016309262856785169494723943649344959507818155642772331582922466943539371681776924160647697558836379614689120727659593775446187326222964118917872973684996317614900715927751822277949264379149585370840318817143291878609357893969588131470982041272505875501444442064552286330626234504767040724907034678080283717062342383737341651784574675215207283219694413200065153603535550259
e = 47356701171507751941853094934330097161634963503549196148254287987823089762869775349307331223083118848869825102126184149696632299476124764277876323238594318983922914255635452587035212905468593961720866809724369270149104325019013500377581
enc = 307839781648837102719329833689146078918113606357673952357833605392673923316706392387378621203382529480917019155723632239435123748698548640308486267420983085309284306889248702165586731118889200017606360233948688879034822132551452439147516062116990766999765714755923073387252339782026780490661436777023426366620269445376047876173655782230659201893151372247389482285331969025687842851498151565880029377050013378302485301558801016888957357366922840214729734193614497
abc = e / 65537
BASE = 2 ^ 256
bc_low = n % BASE
abc_low = abc % BASE
a = Zmod(BASE)(abc_low / bc_low).lift()
bc = abc / a
print(bc)
ac_high = n // BASE ^ 5 - 1
print(a)
ac_appro = ac_high * BASE
c_appro = ac_appro // a
print(ac_appro)
for i in range(20):
c = c_appro + i
if bc % c == 0:
print(c)
break
b = bc / c
bits = 256
p = (a << (2 * bits)) + (b << bits) + c
q = (c << (2 * bits)) + (a << bits) + b
phi = (p - 1) * (q - 1)
d = Zmod(phi)(1 / e).lift()
m = pow(enc, d, n)
print(long_to_bytes(m))
masquerade
核心是一个DSA的_verify，理论上一个正常的DSA的加密解密是需要对传入的消息进行hash的。但这题并没有，我们就可以进行操作。
下面是DSA的_verify函数
def _verify(self, m, sig):
r, s = sig
y, q, p, g = [self._key[comp] for comp in ['y', 'q', 'p', 'g']]
if not (0 < r < q) or not (0 < s < q):
return False
w = Integer(s).inverse(q)
u1 = (w * m) % q
u2 = (w * r) % q
v = (pow(g, u1, p) * pow(y, u2, p) % p) % q
return v == r
题目只要求了$m % p \neq 0$ 但是我们注意到m在这个函数里面实际上是要%q的，那我们很自然的想着去构造一个m’包含m且$m’%q = 0$，我们可以令$m’ = x*2^t + m$ ,t为足够大的数，我们在Zmod(q)环中进行运算可以很简单求出$x$。
此时我们要验证的式子就转化为了$y^{\frac{w}{r}}(mod\ p)(mod\ q)==r(mod\ p)(mod\ q)$
很容易看出来只要取$w = r = y (mod\ p)$就行了
下面是代码（交互逻辑简单，我是手工交互的）
q = 942524496426357218162327487851802980085768486497
y = 66387746127247930006238071513602067820016919918456147093444250185366572831617643690749527279749659201870282909517421483664282500173244835006656966948266787290969611290478400099615021618573821177508224759028195617700527955339975301182477823908151327954312496723864732200900130492625137758191612756872294978335
m = b" ID: @hash_hash & NOTE: L@zy M@n :)"
m = bytes_to_long(m)
x = (-m * inverse(2 ** 280, q)) % q
ans = x * 2**280 + m
input_str = f"{y%q},{y%q},{ans}"
assert Auth_Code in long_to_bytes(ans) and ans % int(Ticket_Office._key["p"])
print(input_str)