foobarCTF 2022 | new intern

#foobarCTF_2022

#!/usr/bin/env python3
from Crypto.Util.number import *
from random import getrandbits


flag = b'***********************REDACTED***********************'
FLAG = bytes_to_long(flag)

p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q
e = 17


menu = """ 
[1].CURR STATE
[2].ENCRYPT FLAG
[3].EXIT
"""

class PRNG(object):
    def __init__(self, seed1,seed2):
            self.seed1 = seed1
            self.seed2 = seed2
    
    @staticmethod
    def rotl(x, k):
            return ((x << k) & 0xffffffffffffffff) | (x >> 64 - k)
    
    def next(self):
            s0 = self.seed1
            s1 = self.seed2
            result = (s0 + s1) & 0xffffffffffffffff
            
            s1 ^= s0
            self.seed1 = self.rotl(s0, 55) ^ s1 ^ ((s1 << 14) & 0xffffffffffffffff)
            self.seed2 = self.rotl(s1, 36)
            
            return result

def main():
    a = getrandbits(64)
    b = getrandbits(64)
    g = PRNG(a,b)
     
    print("N : {}".format(N))
    print("e : {}".format(e))
    while True:
        print(menu)
        choice = input("$ ").rstrip().lstrip()
        
        if not choice in ["1","2","3"]:
            print("HIGH AF")
            exit()
            
        if choice == "1":
            print("state for you: {}".format(g.next()))
        
        elif choice == "2": 
            X = g.next()          
            ct = pow(FLAG + X, e, N) 
            print("ENC(flag+next_num): {}".format(ct))
        elif choice == "3":
            exit()
        
if __name__ ==  "__main__":
    main()

#RSA と #PRNG の複合問題

PRNGの次の値を得るか、を得ることがでいる

が予測できればあとはFranklin-Reiter Related Message Attackするだけなので予測をどうやるか考える

‥‥z3で殴ればいいきがする

殴れた

from sage.all import *
from z3 import BitVec, Solver, sat, RotateLeft
from ptrlib import Process

def prng_next(a, b):
    r = a + b

    b = a ^ b
    return r, RotateLeft(a, 55) ^ b ^ (b << 14), RotateLeft(b, 36)

class PRNG(object):
    def __init__(self, seed1,seed2):
            self.seed1 = seed1
            self.seed2 = seed2
    
    @staticmethod
    def rotl(x, k):
            return ((x << k) & 0xffffffffffffffff) | (x >> 64 - k)
    
    def next(self):
            s0 = self.seed1
            s1 = self.seed2
            result = (s0 + s1) & 0xffffffffffffffff
            
            s1 ^= s0
            self.seed1 = self.rotl(s0, 55) ^ s1 ^ ((s1 << 14) & 0xffffffffffffffff)
            self.seed2 = self.rotl(s1, 36)
            
            return result

sock = Process(["python3", "./server.py"])

N = int(sock.recvlineafter("N : "))
e = int(sock.recvlineafter("e : "))


a, b = BitVec("a", 64), BitVec("b", 64)
init_a, init_b = a, b
solver = Solver()

r_log = []
for _ in range(3):
    sock.sendlineafter("$ ", "1")
    r = int(sock.recvlineafter("you: "))
    r_log.append(r)

    r_next, a, b = prng_next(a, b)
    solver.add(r_next == r)

r = solver.check()
if r != sat:
    print(r)
    quit()

m = solver.model()
prng = PRNG(m[init_a].as_long(), m[init_b].as_long())
for i in range(3):
    assert prng.next() == r_log[i]


sock.sendlineafter("$ ", "1")
assert int(sock.recvlineafter("you: ")) == prng.next()

sock.sendlineafter("$ ", "2")
c1 = int(sock.recvlineafter("next_num): "))

sock.sendlineafter("$ ", "2")
c2 = int(sock.recvlineafter("next_num): "))

_, x = PolynomialRing(Zmod(N), name='x').objgen()
f1 = (x + prng.next())**e - c1
f2 = (x + prng.next())**e - c2

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

m = -gcd(f1, f2).coefficients()[0]

print(int(m).to_bytes(100, "big"))