Cybersecurity Senior Capstone Project

Topic

Breaking the Middle Square Weyl Sequence PRNG

Essential Question

How can a pseudorandom number generator (PRNG) be broken and what impacts could this have?

Interview

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.

Paper

One element of my project was a semi-formal paper addressing the vulnerability.
That document is availabe [here] and included below.

Product

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[0],r[1],r[2],r[3])
    for x0, w1 in answers:
        post(x0, w1, r)

Presentation

Presentation Slideshow is available [here].
Presentation was given in front of peers and an industry professional.

Competencies

Overview	Formal Cryptography, Cloud Computing, Scripting, Web Development
Languages	Python, Javascript, C, HTML, LaTeX, Jekyll, Markdown
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

Credits

Bernard Widynski - Creator of Weyl PRNG
Warren Sunada-Wong - Inspiration
Abhiram Kothapalli - Interview
Mike Specter - Interview

References

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