Delegate wallet

Description:

I have been using this software for generating crypto wallets. I think if I was able to predict the next private key, I could probably steal the funds of other users.

EU instance: 161.97.176.150 4008

US instance: 185.172.165.118 4008

Files:

wallet.py

import os
import socketserver
import string
import threading
from time import *
import time
import binascii
import random

flag = open("flag.txt", "rb").read().strip()

class prng_lcg:

    def __init__(self):
        self.n = pow(2, 607) -1 
        self.c = random.randint(2, self.n)
        self.m = random.randint(2, self.n)
        self.state = random.randint(2, self.n)

    def next(self):
        self.state = (self.state * self.m + self.c) % self.n
        return self.state

class Service(socketserver.BaseRequestHandler):

    def handle(self):
        RNG = prng_lcg()
        while True:
            self.send("1) Generate a new wallet seed")
            self.send("2) Guess the next wallet seed")
            choice = self.receive("> ")
            print(choice)
            if choice == b'1':
                self.send(str(RNG.next()))
            elif choice == b'2':
                guess = int(self.receive("> ").decode())
                if guess == RNG.next():
                    self.send(flag)
                else:
                    self.send("Nope!")

    def send(self, string, newline=True):
        if type(string) is str:
            string = string.encode("utf-8")

        if newline:
            string = string + b"\n"
        self.request.sendall(string)

    def receive(self, prompt="> "):
        self.send(prompt, newline=False)
        return self.request.recv(4096).strip()


class ThreadedService(
    socketserver.ThreadingMixIn,
    socketserver.TCPServer,
    socketserver.DatagramRequestHandler,
):
    pass


def main():

    port = 4008
    host = "0.0.0.0"

    service = Service
    server = ThreadedService((host, port), service)
    server.allow_reuse_address = True

    server_thread = threading.Thread(target=server.serve_forever)

    server_thread.daemon = True
    server_thread.start()

    print("Server started on " + str(server.server_address) + "!")

    # Now let the main thread just wait...
    while True:
        sleep(10)


if __name__ == "__main__":
    main()

Auther:

Soul

Points and solvers:

At the end of the CTF, 71 teams solved this challenge and it was worth 465 points.

Solution:

First of all, let's clean that code - it contains server stuff that is irrelevant to us:

import os
import socketserver
import string
import threading
from time import *
import time
import binascii
import random

flag = open("flag.txt", "rb").read().strip()

class prng_lcg:

    def __init__(self):
        self.n = pow(2, 607) -1 
        self.c = random.randint(2, self.n)
        self.m = random.randint(2, self.n)
        self.state = random.randint(2, self.n)

    def next(self):
        self.state = (self.state * self.m + self.c) % self.n
        return self.state

RNG = prng_lcg()
while True:
    self.send("1) Generate a new wallet seed")
    self.send("2) Guess the next wallet seed")
    choice = self.receive("> ")
    print(choice)
    if choice == b'1':
        self.send(str(RNG.next()))
    elif choice == b'2':
        guess = int(self.receive("> ").decode())
        if guess == RNG.next():
            self.send(flag)
        else:
            self.send("Nope!")

This is nicer. Now we see that we can generate a new seed - option 1 or we can guess the new seed - option 2, if we succeed we get the flag.
The name of the function that generates the seeds called prng_lcg - a lcg is a Linear congruential generator and it is unsafe, it appears that using a pen and paper we can predict the next number.

Let's take 3 seeds from the server and call them s1, s2 and s3. Now write s2 and s3 as a function of s1, s2, c, m, n:

s2 = (s1 * m + c) % n
s3 = (s2 * m + c) % n 

m and c are the only two parameters we do not know in these equations - we have two equations with two parameters, let's simplify that:

s2 - s1 * m = c % n
s3 - s2 * m = c % n

s2 - s1 * m = s3 - s2 * m % n
s2 - s3 = s1 * m - s2 * m % n
s2 - s3 = (s1 - s2) * m % n
(s2 - s3) / (s1 - s2) = m % n

Awesome - we can calculate m! Once we know m just put it in one of the first equations and we will know c as well, and once we also know c we can easly calculate s4.
Note that this is not a real division, since we are uner a finite field (module n) this is acutall multipling by the inverse of (s1 - s2).

Solution Code:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m



s1 = 218938461323895569921115633648418966539571486170478785862264203996978269091395347765886630029952567881444657422342493768766050168087793902109378055588445059510453936507447004586534925
s2 = 433361185786481276360491616006724395919669309745646122570934960031956841654449931009448691601128913477289285712098780268872043119937154923052768918289171555608608361093538139103503876
s3 = 12831025342291268037915091642369375488556080108863259142478771087950396499592076555863031197803965224100400575779286156704477686476699016159544785204495338931642799818807215798813739

n = pow(2, 607) - 1
m = ((s3 - s2) * modinv(s2 - s1, n)) % n
c = (s2 - s1 * m) % n
assert s2 == (s1 * m + c) % n
assert s3 == (s2 * m + c) % n

s4 = (s3 * m + c) % n
print(s4)

Flag:

The server went down after the event closed.

Original writeup (https://github.com/yonlif/0x41414141-CTF-writeups/blob/main/Delegatewallet.md).