/ #Harekaze 

Gocha!

A crypto-reversing challenge

Summary: Gocha was a crypto-reversing challenge for 100 points. We were given the following code in python 3. This code is for an online lottery system which asks provides the user with 3 choices of seemingly random numbers, one of which is the winner key and the other two is losing keys. So the probability of winning is 33.3%. However, the user has to win 90% of times for playing at least 30 times. So the probability of winning is a little bit higher than 3.6e-15.



# Python Version: 3.5.2
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from gmpy2 import *
from flag import FLAG
from signal import *

def main():
    signal(SIGALRM, lambda: None)
    alarm(60)
    print('[*] 🎉 WELCOME TO HAREKAZE-CTF LOTTERY CHALLENGE 🎉')
    print('[*] to ensure fairness, we use a public-key 🔑 cryptosystem 🔒')
    win = 0

    for round_ in range(1, 10000):
        print()
        print('[*] ROUND %d' % round_)

        # generate params
        p = [ getPrime(1024) for _ in range(3) ]
        q = [ getPrime(1024) for _ in range(3) ]
        n = [ p[i] * q[i] for i in range(3) ]
        e = 65537
        d = [ invert(e, (p[i] - 1) * (q[i] - 1)) for i in range(3) ]
        m = [ bytes_to_long(['WIN 💎', 'LOSE 💩'][bool(i)].encode()) for i in range(3) ]
        c = [ pow(m[i], e, n[i]) for i in range(3) ]
        f = sorted(range(3), key=lambda x: c[x])

        # receive the choice
        for x, i in enumerate(f):
            print('    🔒 %d. (%#x, %d, %#x)' % (x + 1, n[i], e, c[i]))
        print('[*] select:')
        k = f[int(input('>>> ')) - 1]

        # check the result
        result = long_to_bytes(pow(c[k], d[k], n[k])).decode()
        print('[*] result:', result)
        if 'WIN 💎' in result:
            print('[+] you win 🎉')
            win += 1
        else:
            print('[!] you lose')

        # send the witnesses
        print('[*] here are the keys. please ensure that there is no cheating')
        for i in range(3):
            print('    🔑 %d. %d' % (i + 1, d[i]))

        if round_ >= 30 and win / round_ >= 0.9:
            print('[+] you got the flag 🏁:', FLAG)
            break

if __name__ == '__main__':
    main()

Checking the code we notice that the "winning" string has the gem unicode embedded in it and the win/lose is decoded based on:

result = long_to_bytes(pow(c[k], d[k], n[k])).decode()

Based on the following line we are provided with the c[i] and n[i] but not with the d[i], which seems to be required for decoding the winner key:

print('    🔒 %d. (%#x, %d, %#x)' % (x + 1, n[i], e, c[i]))

However, instead of decoding the keys, we will try to recreate c[i] based on the following key and compare it with the c[i] in the given key:

c = [ pow(m[i], e, n[i]) for i in range(3) ]

we know e=65537, we have n[i] and we know m[gem, aka win]. Note that there is a 60 second timer so this selection cannot be done manually. Therefore, apart from the python scripting to find the winning key, a little bit of bash scripting via python was also required to automate the seletion process.

Author

V.A.

CTF enthusiast