Jorge Wants a Token

$ nc 0.cloud.chals.io 15980

    __  __           __   ____
   / / / /___ ______/ /__/ __ \____
  / /_/ / __ `/ ___/ //_/ / / / __ \
 / __  / /_/ / /__/ ,< / /_/ / / / /
/_/ /_/\__,_/\___/_/|_|\____/_/ /_/
Welcome to the HackOn administration.

1. Log In - With token.
2. Register.
3. Make a complain.
4. Exit

[*]Option:

def menu():
    banner()
    show_options()
    for i in range(32):
        try:
            option = int(input("[*]Option: ").strip())
        except:
            print("Wait, what?")
            exit()
            
        if option == 1:
            token = input("Token, please: ").strip()
            login(token)
            
        elif option == 2:
            new_user = input("Username: ").strip()
            algorithm = input("Alg: ").strip()
            register(new_user, algorithm)

        elif option == 3:
            print("Fuck no, send bizum to this number +34 631223245 to get the flag")

        else:
            print("Goodbye!!")
            exit()

def register(username: str, algorithm: str):
    payload = dict()
    payload['username'] = username
    payload['iat'] = os.urandom(32).hex()
    payload['status'] = "Student"
    payload['dfh'] = "3+3=2, right?"
    token = jws.encode(json.dumps(payload), algorithm)
    print(token)

    def encode(self, payload, algorithm="HSMAC256"):
        if algorithm not in self.ALGORITHMS:
            raise ValueError(f"ALgorithm {algorithm} not supported.")
        
        try:
            self.payload = json.loads(payload)      
        except:
            raise Exception("Invalid payload format.")

        if algorithm == "HSMAC256":
            self.header = '{"alg":"HSMAC256","typ":"JWT"}'
        
        elif algorithm == "ES512":
            self.header = '{"alg":"ES512","typ":"JWS"}'

        elif algorithm == "ESBLK":
            self.header = '{"alg":"ESBLK","typ":"JWS"}'

        signature = self.sign(payload,self.header, self.key, algorithm)
        token = ".".join([JWS.base64url_encode(data).decode() for data in [self.header.encode(),payload.encode(),signature]])
        return token

    def sign(self, payload, header, key:bytes, algorithm="HSMAC256"):
        sign_input = ".".join([header, payload])
        if algorithm not in self.ALGORITHMS:
            raise ValueError(f"ALgorithm not supported.")

        if algorithm == "HSMAC256":
            signature = hmac.new(key, sign_input.encode(), digestmod=sha256).digest()
        else:
            signature = self.ecdsa_sign(sign_input, key, algorithm)

        return signature

    def ecdsa_sign(self, input:str, key:bytes, algorithm:str):
        if algorithm == "ES512":
            hash = sha512()
        else:
            hash = blake2b(digest_size=46)
            
        hash.update(key + urandom(16))
        nonce = bytes_to_long(hash.digest())
        sign = self.privKey.sign(bytes_to_long(sha256(input.encode()).digest()), nonce)
        
        return long_to_bytes(sign.r)+ b'&&' +long_to_bytes(sign.s)

def login(token: str):
    if jws.verify(token):
        try:
            _,payload,_ = JWS.load_token(token)
            payload = json.loads(payload)
            status = payload['status']
            username = payload['username']
            iat = payload['iat']
            dfh = payload['dfh']
        except:
            print("Problem in your payload detected.")
            exit()

        if status == "Rector" and type(dfh) == int == type(iat):
            flag = bytes_to_long(FLAG.encode())
            assert flag.bit_length() > 600
            if iat > dfh and dfh.bit_length() == 200 and isPrime(dfh):
                print(f"Rector, this belongs to you: {pow(iat,flag,dfh**2)}")
            else:
                print("Bad Parameters.")
        else:
            print(f"Welcome {username},your iat is {iat} and your status is {status}")   
            print(f"This is your public key: ")
            print(jws.pubKey.point.x(),jws.pubKey.point.y()) 
    else:
        print("Fail in Log In. Invalid Token.")

def get_private_key():
    h, r, s = [], [], []

    for _ in range(31):
        token = register('a', 'ESBLK')
        header, payload, signature = token.encode().split(b'.')
        r_i, s_i = map(bytes_to_long, base64_url_decode(signature).split(b'&&'))
        h.append(bytes_to_long(sha256(base64_url_decode(header) + b'.' + base64_url_decode(payload)).digest()))
        r.append(r_i)
        s.append(s_i)

    p = int(generator_384.order())
    a = list(map(lambda s_i, h_i: pow(s_i, -1, p) * h_i % p, s, h))
    t = list(map(lambda r_i, s_i: pow(s_i, -1, p) * r_i % p, r, s))

    X = 256 ** 46

    raw_matrix = []

    for i in range(len(a)):
        raw_matrix.append([0] * i + [p] + [0] * (len(a) - i + 1))

    raw_matrix.append(t + [X / p, 0])
    raw_matrix.append(a + [0, X])

    M = Matrix(QQ, raw_matrix)
    L = M.LLL()

    for row in L.rows():
        if row[-1] == X:
            k = list(map(int, row[:-2]))
            x = (s[0] * k[0] - h[0]) * pow(r[0], -1, p) % p
            io.info(f'Private key: {x}')
            return x

def dlog_mod_power_prime(g, g_x, p, e):
    """
    Discrete Logarithm modulo prime power
    - Calculate x, such that g_x = g^x mod p^e
    Implementation source: Discrete Logarithms and Factoring, Eric Bach
    https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf
    """

    def theta(x, p, e):
        p_2e_1 = pow(p, 2 * e - 1)
        ret = pow(x, (p - 1) * pow(p, e - 1), p_2e_1) - 1 # we can use ^ 2*(p-1)p^(e-1)

        assert ret % (p ** e) == 0
        return ret // (p ** e)

    p_e_1 = p ** (e-1)
    theta_a = theta(g, p, 2)
    theta_b = theta(g_x, p, 2)
    x = (theta_b * inverse(theta_a, p_e_1)) % p_e_1
    return x

crt_r, crt_m = [], []

for _ in range(4):
    io = get_process()
    x = get_private_key()

    key = long_to_bytes(x)
    jws = JWS(key)
    dfh = getPrime(200)
    token = jws.encode(json.dumps({
        'iat': dfh + 1,
        'status': 'Rector',
        'dfh': dfh,
        'username': '7Rocky',
    }))

    io.sendlineafter(b'[*]Option: ', b'1')
    io.sendlineafter(b'Token, please: ', token.encode())
    io.recvuntil(b'Rector, this belongs to you: ')
    enc = int(io.recvline().decode())
    io.close()

    f = dlog_mod_power_prime(dfh + 1, enc, dfh, 2)
    assert pow(dfh + 1, f, dfh ** 2) == enc
    crt_r.append(f)
    crt_m.append(dfh)

io.success(long_to_bytes(crt(crt_r, crt_m)).decode())

$ python3 solve.py 0.cloud.chals.io 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 21527056898547024587609061810343314636054103071083534282832602787779906208125346961093976190169270897359572999836562
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 18814722945154313480948727673868769998572454698779537940745768538072367594925761035156672852090498617182007108488964
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 33961003751330092278804628895767649698903687994164285766669837669581590400494603649396321858221791508300235658238462
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 2260618360756416815541341091789168739127662042173042144222183197102177554812745377485235625697522113617557847117469
[*] Closed connection to 0.cloud.chals.io port 15980
[+] HackOn{I_c4n_s33_b14s3d_N0nc3s_3verywh3r3_I_g0.0nc3_m0r3_s4g3_1s_4lways_4_g00d_fr13nd}