Introduction

During this week I was able to check the crypto tasks in BCTF. There were 2 of them which I think is not that much but there were a few blockchain tasks which some ctfs count as crypto so number of questions was ok. The first problem was really easy and there were quite a lot of solves on it: around 110. However, this problem was quite hard and fun. There were 9 solves and I was the last team to solve the task. I learned a lot while solving this task but there is an aspect about this task that I am not fond of, which is the task consists of a single problem and there were almost nothing to deduce.

Challenge Description

In the task an IP, port and the source code of the service running in the give server was given Source code:

    import random
    from flag import FLAG
    import gmpy2
    def msb(k, x, p):
        delta = p >> (k + 1)
        ui = random.randint(x - delta, x + delta)
        return ui

    def main():
        p = gmpy2.next_prime(2**160)
        for _ in range(5):
            alpha = random.randint(1, p - 1)
            # print(alpha)
            t = []
            u = []
            k = 10
            for i in range(22):
                t.append(random.randint(1, p - 1))
                u.append(msb(k, alpha * t[i] % p, p))
            print(str(t))
            print(str(u))
            guess = raw_input("Input your guess number: ")
            guess = int(guess)
            if guess != alpha:
                exit(0)
    if __name__ == "__main__":
        main()
        print(FLAG)

The code is quite straight forward and the flag is given when we find the hidden alpha value 5 times consecutively.

Solving the Task

The first thing to notice is how msb function conserves the msb 10 bits of the t * a multiplication. If we were to find the exact value of that multiplication the task would be trivial but we only know the 10 msb of it but we have 22 other values as well for different t’s but for same a’s. Redacted data and few examples sounds a lot like a problem which can be solved by lattices but I did not know how to solve this problem. So I googled “lattice cryptanalysis” and read whatever I could find. I stumbled upon http://www.cits.rub.de/imperia/md/content/may/cryptanalysis_folien.pdf and in page 49 it mentions the problem “The Hidden Number Problem” which sounds a lot like our problem but the explanation there was not clear enough for me to understand. However I had the name of the problem so I could search better now. I found http://www.isg.rhul.ac.uk/\~sdg/igor-slides.pdf which was more focused on this particular problem and gave me better understanding of the limits of the solution. I first check if 10 was close enough to log^½^(2^160^) which is the case so I started the implementation of the solution.

Implementing the Solution

I wish I could say that finding the solution was the hard part but due to the lack of documentations, I struggled a lot trying to implement this. First thing that I am pissed about is sagemath does not support closest vector problem. There was a discussion about this 6 years ago, but I don’t see if it is implemented in sagemath today. The second thing that I am pissed about is I could not find any good fplll library documentation. I tried to go in blind, but I was not able to pass floats numbers in the matrix to the library. I chose to go with the fpylll, a python wrapper for the fplll, which did have a nice documentation but at first, I tried to install it with pip which did not happen but that’s probably an error on my part and I was able to install it using anaconda. But fpylll did not support floats as well(if somebody knows how to do this please contact me). So as a solution I multiplied every value in the basis matrix and the u vector with 2^11^ and crossed my fingers. This actually worked and I was able to solve the task. The following is my implementation of the solution:

    from fpylll import *
    import random
    from gmpy2 import next_prime, invert

    def solve(t, u):
        p = int(next_prime(2**160))
        k = 2**11

        m = [list(map(lambda s: s * k, t)) + [1]]
        m += [[0] * i + [p * k] + [0] * (22 - i) for i in range(22)]
        u = u + [0]
        u = list(map(lambda s: s * k, u))

        M = IntegerMatrix.from_matrix(m)
        U = tuple(u)

        M = LLL.reduction(M)

        v = CVP.closest_vector(M, U)

        x = v[-1]
        x = (p + x) % p
        return x


    for i in range(5):
        t = input().replace('L', '')
        u = input().replace('L', '')
        t = eval(t)
        u = eval(u)
        print(solve(t, u))

The flag was: BCTF{HNP_Pr0b13m_1s_So_3asy_Every0n3_C4n_Guess_1t!}

Conclusion

I learned tremendously while trying to solve this task, hence thanks to the organizers. Getting my hands dirty with fplll was frustrating and a quite informative challenge. You can contact me on @yamantasbagv2 for feedbacks.