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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
| from pwn import * from Crypto.Util.number import * from sys import stdout from fastecdsa.curve import P256 from fastecdsa.point import Point from Crypto.Cipher import AES from tqdm import trange
VERBOSE = True
G = P256.G
def pad(s): return s + (16 - len(s) % 16) * b"\x00"
class PRNG: def __init__(self, e, seed): self.state = seed self.Q = e * G self.P = G self.mask = 2**240 - 1 def gen(self): new_point = self.state * self.P r = new_point.x self.state = r ret = r * self.Q return ret.x & self.mask
def p256_mod_sqrt(c): p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff t1 = pow(c, 2, p) t1 = (t1 * c) % p t2 = pow(t1, 2**2, p) t2 = (t2 * t1) % p t3 = pow(t2, 2**4, p) t3 = (t3 * t2) % p t4 = pow(t3, 2**8, p) t4 = (t4 * t3) % p r = pow(t4, 2**16, p) r = (r * t4) % p r = pow(r, 2**32, p) r = (r * c) % p r = pow(r, 2**96, p) r = (r * c) % p return pow(r, 2**94, p)
def find_point_on_p256(x): # equation: y^2 = x^3-ax+b y2 = (x * x * x) - (3 * x) + P256.b y2 = y2 % P256.p y = p256_mod_sqrt(y2) return y2 == (y * y) % P256.p, y
class Solve: def __init__(self) -> None: self.conn = remote('192.168.0.64', 58010) self.n = 15 def s_3(self): self.conn.sendlineafter('>', '3') x0 = eval(self.conn.recvline()) x = eval(self.conn.recvline()) y = eval(self.conn.recvline()) x1 = x[:self.n] x2 = x[self.n:] p_list = [] PR = PolynomialRing(Zmod(x0), 'x') x_ = PR.gen() f = x_ + y sol = f.small_roots(X=2**20, beta=1./20) p_list = [ZZ(gcd(t + y, x0)) for t in sol] print(len(p_list)) e = min(p_list) # print(set(p0) == set(p_list)) return e
def gen_prediction(self, observed, Q, d): ret = [] for high_bits in trange(2**15): # 2**16: have sol, 2**15: 1/2 prob guess = (high_bits << (8 * 30)) | observed on_curve, y = find_point_on_p256(guess)
if on_curve: # use the backdoor to guess the next 30 bytes point = Point(guess, y, curve=P256) s = (d * point).x r = (s * Q).x & (2**(8 * 30) - 1) ret.append(r)
return ret
def s_pred(self, e): d = int(inverse(e, P256.q)) Q = e * G self.conn.sendlineafter('>', '1') observed = eval(self.conn.recvline()) # print(guess) # pred = eval(self.conn.recvline()) # print(pred) predicted = self.gen_prediction(observed, Q, d) # print(len(predicted)) # print(pred in predicted) return predicted def s_2(self, pred): self.conn.sendlineafter('>', '2') self.conn.recvuntil('ct: ') ct = self.conn.recvline().strip() ct = base64.b64decode(ct) for nx in pred: key = pad(long_to_bytes(nx)) cipher = AES.new(key, AES.MODE_ECB) pt = cipher.decrypt(ct) if (all(64 < x < 128 for x in pt)): print(pt) self.conn.sendlineafter('pt:', base64.b64encode(pt)) self.conn.interactive() return True else: self.conn.close() return False
def s(self): e = int(self.s_3()) pred = self.s_pred(e) if (pred == 0): self.conn.close() return False is_success = self.s_2(pred) return is_success
if __name__ == '__main__': while True: print('Begin try...') s = Solve() is_success = s.s() if (is_success): break print('Failed')
|