2022 | Hacky Easter | crypto
Casino
题目¶
Wanna try your luck in our new casino?
To prove we're not cheating, we are publishing our source code.
Connect to the server and start gamblin'!
1 |
|
Note: The service is restarted every hour at x:00.
server.sage
from random import randint
from secrets import flag
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad
class RNG:
def __init__(self):
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
self.curve = EllipticCurve(GF(p), [-3,b])
self.P = self.curve.lift_x(15957832354939571418537618117378383777560216674381177964707415375932803624163)
self.Q = self.curve.lift_x(66579344068745538488594410918533596972988648549966873409328261501470196728491)
self.state = randint(1, 2**256)
def next(self):
r = (self.state * self.P)[0].lift()
self.state = (r * self.P)[0].lift()
return (r * self.Q)[0].lift() >> 8
class Casino:
def __init__(self, rng):
self.rng = rng
self.balance = 10
def play(self):
print("Your bet: ", end='')
bet = input()
if (bet in ["0", "1"]):
bet = Integer(bet)
if (self.rng.next() % 2 == bet):
self.balance += 1
else:
self.balance -= 1
if (self.balance == 0):
print("You are broke... play again")
exit()
print(f"Your current balance: {self.balance}")
else:
print("Invalid bet option, use either 0 or 1")
def buy_flag(self):
if (self.balance >= 1337):
key = SHA256.new(str(self.rng.next()).encode('ascii')).digest()
cipher = AES.new(key, AES.MODE_ECB)
print(cipher.encrypt(pad(flag.encode('ascii'), 16)).hex())
else:
print("No flag for the poor. Gamble more")
def main():
rng = RNG()
casino = Casino(rng)
print("Welcome to the Casino")
print(f"Your id is {rng.next()}")
print("What would you like to do?")
print("(p)lay and win some money")
print("(b)uy the flag")
while (True):
print("> ", end='')
option = input()
if (not option in ["b", "p"]):
print("Unknown option, use 'b' or 'p'")
elif (option == "b"):
casino.buy_flag()
elif (option == "p"):
casino.play()
if __name__ == '__main__':
main()
解题思路¶
- 简单扫一眼代码,可以确定
RNG
里定义的椭圆曲线及点是特殊的。在不考虑初始余额的情况下,需要连续猜对 \(1337\) 次才能拿到 Flag,因此next
的输出一定是可预测的 - 首先想到看看「点的阶」,发现 \(P\) 和 \(Q\) 的阶都是 \(ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551_{16}\),对应了特殊的椭圆曲线
NIST P-256
,但知道了是特殊的椭圆曲线有什么用呢 > < - 使用
NIST P-256
进一步搜索发现它可以用在Dual_EC_DRBG
,而Dual_EC_DRBG
存在后门,知道当前状态的完整输出,就可以推出下一状态 \(ΦωΦ)/ - 结合
Dual_EC_DRBG
分析Casino
使用的RNG
- 定义函数 \(X(x,y)=x\),提取椭圆曲线上点的 \(X\) 轴坐标
- 状态 \(s\) 的转移过程:\(r_i=X(s_i P),s_{i+1}=X(r_i P)\)
- 第 \(i\) 个「随机数」为 \(X(r_i Q) \gg 8\)
- 存在整数 \(e\) 使得 \(eQ=P\),设 \(t=X(r_i Q)\),点 \(A\) 在椭圆曲线上且 \(X(A)=t\),由此就能推出下一状态了 🥳 \(X(eA)=X(e\times r_i Q)=X(r_i P)=s_{i+1}\)
-
接下来思路就很清晰啦 XD 首先,尝试求出 \(e\),再根据初始
id
和后续几次bet
确定 \(X(r_i Q)\) 未知的部分,最后攒钱buy_flag
!- 说不定
self.balance >= 1337
其实是在暗示 \(e\),不过做的时候没注意 (ŏωŏ)
from sage.all import * from Crypto.Cipher import AES from Crypto.Hash import SHA256 import pwn e = None p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b curve = EllipticCurve(GF(p), [-3, b]) P = curve.lift_x(Integer(15957832354939571418537618117378383777560216674381177964707415375932803624163)) Q = curve.lift_x(Integer(66579344068745538488594410918533596972988648549966873409328261501470196728491)) def get_state(ts): ''' Get possible next states from current RNG.next() output ''' state = [] for t in ts: try: A = curve.lift_x(Integer(t)) except: # some x-coordinate values don't have the corresponding points on the curve continue state.append((e * A)[0].lift()) return state def get_next(state): ''' Get bet(s) and next state(s) from current state(s) ''' bets, nxt = [], [] for s in state: r = (s * P)[0].lift() nxt.append((r * P)[0].lift()) bets.append((r * Q)[0].lift()) return bets, nxt def remove_state(bets, state, false_bet): correct = [] for b, s in zip(bets, state): if (b >> 8) % 2 != false_bet: correct.append(s) return correct if __name__ == '__main__': for i in range(2000): if i * Q == P: e = i # 1337 break conn = pwn.remote("46.101.107.117", 2212) balance = 10 _id = conn.recvline_contains('Your id is').decode() t = int(_id[11:]) ts = [(t << 8) + i for i in range(2 ** 8)] state = get_state(ts) while balance < 1337: conn.sendafter('> ', 'p\n') bets, state = get_next(state) bet = (bets[0] >> 8) % 2 conn.sendafter('Your bet: ', str(bet) + '\n') curr_balance = conn.recvline_contains('balance').decode() curr_balance = int(curr_balance[curr_balance.find(': ') + 2:]) if len(bets) > 1: if curr_balance < balance: state = remove_state(bets, state, bet) else: state = remove_state(bets, state, 0 if bet else 1) balance = curr_balance conn.sendafter('> ', 'b\n') enc_flag = conn.recvline().decode() bets, _ = get_next(state) key = SHA256.new(str(bets[0] >> 8).encode('ascii')).digest() cipher = AES.new(key, AES.MODE_ECB) print(cipher.decrypt(bytes.fromhex(enc_flag))) # b'he2022{C4S1N0_B4CKD00R_ST0NK5}\x02\x02'
- 说不定
Flag¶
he2022{C4S1N0_B4CKD00R_ST0NK5}
参考资料¶
最后更新:
2022年5月17日 22:58:14
Contributors:
Pageviews:
Pageviews: