Cybersecurity Senior Capstone Project
Breaking the Middle Square Weyl Sequence PRNG
How can a pseudorandom number generator (PRNG) be broken and what impacts could this have?
Interviews were conducted with PhD students Abhiram Kothapalli (Carnegie Mellon) and Mike Specter (MIT).
An interview summary is available [here], with topics including PRNGs, Zero-Knowledge Proofs, and Verifiable Computation.
One element of my project was a semi-formal paper addressing the vulnerability.
That document is availabe [here] and included below.
Click Here to access the target webpage, which is the simulated lottery to be attacked.
The solve script (attacker) is available below:
#!/usr/bin/env python3 import gmpy2 import sys shi = 0xb5ad4ece slo = 0xda1ce2a9 t64 = 2**64 t32 = 2**32 def solve(r0,r1,r2,r3): answers =  for e0 in [0,1]: for e1 in [0,1]: for e2 in [0,1]: for e3 in [0,1]: for e4 in [0,1]: h0=( 2*r0 )%t32 h1=( (r0*r0)%(t32) )%t32 h2=( (r0*r0) >> 32 )%t32 h3=( 2*r1 )%t32 h4=( (r1*r1)%(t32) )%t32 h5=( (r1*r1) >> 32 )%t32 h7=( 2*r2 )%t32 h8=( (r2*r2)%(t32) )%t32 h9=( (r2*r2) >> 32 )%t32 h6 =( h4+slo )%t32 h10=( 2*shi + e1 + e3 )%t32 h11=( h7*h6 + h9 + h10 + e4 )%t32 h12=( h3*h1 + h5 + shi + e1 + e2)%t32 coeff = h7 - h3 product = r3 + h12 - r2 - h11 product = (product + t32) % t32 coeff = (coeff + t32) % t32 modulus = t32 try: d = gmpy2.divm(product, coeff, modulus) except ZeroDivisionError as e: break d = (d%t32+t32)%t32 c = ((r2 - h3*d - h12)%t32 + t32)%t32 if c != ((r3 - h7*d - h11)%t32 + t32)%t32: break c = (c%t32+t32)%t32 product = r1 - h2 - c - e0 coeff = h0 try: a = gmpy2.divm(product, coeff, modulus) except ZeroDivisionError as e: break a = (a%t32+t32)%t32 b = r0 x0 = a*t32+b w1 = c*t32+d answers.append((x0,w1)) return answers class weyl(): def __init__(self, x=0x5a8dd3ad0756a93d, w=0xed72b823b19dd877, off=0, s=0xb5ad4eceda1ce2a9): self.s = s self.off = off self.x = x self.w = ((w - (self.s * self.off))%t64 + t64)%t64 def nextRand(self): self.w = (self.w + self.s)%t64 self.x = (self.x**2 + self.w)%t64 self.x = ((self.x << 32) + (self.x >> 32))%t64 return (self.x)%t32 def post(x0, w1, r): #print("x0:",hex(x0)) #print("w1:",hex(w1)) gen = weyl(x = x0, w = w1, off=1) for i in range(4): gen.nextRand() for i in range(len(r)-5): if r[i+5] != gen.nextRand(): return print("Future Winners:") for i in range(4): print(gen.nextRand()) print() def get_r(): print("Past Winners:") #Copy-paste from website, ^D when finished r = [*map(int,sys.stdin.read().split())][::-1] print("Most recent winner:") #The value in the red box. ^D to submit r.append(int(sys.stdin.read().strip())) print() if len(r) < 6: print("Please provide more data") print("for a more reliable result.") print() return get_r() return r if __name__ == "__main__": r = get_r() answers = solve(r,r,r,r) for x0, w1 in answers: post(x0, w1, r)
Presentation Slideshow is available [here].
Presentation was given in front of peers and an industry professional.
|Overview||Formal Cryptography, Cloud Computing, Scripting, Web Development|
|Theory||Modular Arithmetic, Linear Congruences, Modular Multiplicative Inverses|
|Tools||GCP (Google Cloud Platform), Z3 Theorem Prover, Linux, SSH|
|Skills||Research, Conducting Interviews, Composing Reports, Presenting Product|
Bernard Widynski - Creator of Weyl PRNG
Warren Sunada-Wong - Inspiration
Abhiram Kothapalli - Interview
Mike Specter - Interview
Middle Square Weyl Sequence RNG - Bernard Widynski
Middle-Square Method - Wikipedia
Attack of the Middle Square Weyl Sequence PRNG - Cryptography StackExchange
Weyl PRNG CTF Challenge - Warren Sunada-Wong