Skip to content

Instantly share code, notes, and snippets.

@hellman
Last active May 21, 2024 04:59
Show Gist options
  • Save hellman/7dd5e14a49bb857c8e07e5f3aab866fc to your computer and use it in GitHub Desktop.
Save hellman/7dd5e14a49bb857c8e07e5f3aab866fc to your computer and use it in GitHub Desktop.
DiceCTF 2021 - rejected
from sage.all import *
from rejected import LFSR, taps
from binteger import Bin
from sock import Sock
n = 64
N = 2**30 + 2**29
f = Sock("mc.ax 31669")
f.send_line(str(N))
f.send_line("R\n" * 200)
inds = []
off = 0
total = 0
for i in range(200):
f.read_until(r"took ")
num = int(f.read_until(r" "))
total += num
print(i, "num", num, "off", off)
for j in range(num-1):
inds.append(off + 30)
inds.append(off + 31)
off += 32
off += 32
cols = []
for i in range(64):
key = Bin.unit(i, 64).list
lfsr = LFSR(key, taps)
out = [lfsr.bit() for _ in range(total*32)]
cols.append([out[ind] for ind in inds])
mat = matrix(GF(2), cols).transpose()
target = vector(GF(2), [1]*mat.nrows())
sol = mat.solve_right(target)
print("sol", sol)
f.send_line("F")
f.send_line(str(Bin(sol[::-1]).int))
f.interact()
# dice{so-many-numbers-got-rejected-on-valentines-day-1cc16ff5b20d6be1fbd65de0d234608c}
#!/usr/local/bin/python
import secrets
class LFSR:
def __init__(self, key, taps):
self._s = key
self._t = taps
def _sum(self, L):
s = 0
for x in L:
s ^= x
return s
def _clock(self):
b = self._s[0]
self._s = self._s[1:] + [self._sum(self._s[p] for p in self._t)]
return b
def bit(self):
return self._clock()
class RNG:
def __init__(self, lfsr, N, nbits):
self.lfsr = lfsr
self.N = N
self.nbits = nbits
if not (pow(2, 27) < N < pow(2, 31)):
raise ValueError("modulus is too big or small")
K = pow(2, nbits) // N
self.cutoff = K * N
def get_random_nbit_integer(self):
res = 0
for i in range(self.nbits):
res += self.lfsr.bit() << i
return res
def get_random_integer_modulo_N(self):
count = 1
while True:
x = self.get_random_nbit_integer()
# print(f"{x:032b}")
if x < self.cutoff:
return x % self.N, count
count += 1
taps = [60, 58, 54, 52, 48, 47, 45, 43, 38, 36, 32, 28, 22, 21, 13, 9, 8, 5, 2, 0]
n = 64
# with open("flag.txt", "r") as f:
# flag = f.read()
if __name__ == "__main__":
print("Welcome to the unbiased random number factory!")
N = int(input("What modulus would you like to use? Choose between 2^27 and 2^31: "))
key = secrets.randbits(n)
key_bits = [(key >> i)&1 for i in range(n)]
lfsr = LFSR(key_bits, taps)
rng = RNG(lfsr, N, 32)
for _ in range(1024):
c = input("Enter your command (R,F): ")
if c.startswith("R"):
x,t = rng.get_random_integer_modulo_N()
print("creating this random number took {} attempts".format(t))
elif c.startswith("F"):
seed = int(input("what was my seed?"))
if seed == key:
print(flag)
exit(0)
else:
print("unsupported command")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment