Lockpicking Writeup (dCTF 2021)

Masrt

Type: Crypto

Difficulty: Hard

Prompt: We were playing a game of cows and bulls and decided 260 guesses was enough for 200 pins. `nc dctf1-chall-lockpicking.westeurope.azurecontainer.io 7777`

Solution

Now this was an interesting challenge to say the least, the approach was clear to me rather quickly but seeing as things didn’t addup, I thought there was something else at play here; which there was, but not where I expected it to be. Coupled with the fact that my recent distaste towards asking the authors regarding chall related, leads us here. Into this writeup… so shall we ?

The challenge was based on the popular cow and bull game, in which we have to guess a numbers based on our last guess. The optimal strategy to solve this challenge requires about 5-7 turns but we need better than here.

We were asked to guess 200 numbers in 260 trials, with an overhead of 5 minutes to do so. The numbers to guess were generated by a LFSR (Linear Feedback Shift Register), in which the next number was depended on the intialized coefficients and the current state.

class lsfr:
    def __init__(self):
        self.state = [randint(0, 5039) for _ in range(10)]
        
        while True:
	        self.coefs = [randint(0, 5039) for _ in range(10)]
	      	if solvable(self): break  #this basically checks whether the coefs can be calculated uniquely

    def next(self):
        n = sum([self.state[i] * self.coefs[i] for i in range(10)]) % 5039  #next number is the current state multiplied with the coefs
        self.state = self.state[1:] + [n] #the next number is added to the end of the state. 
        return n

In order to guess the numbers with 100% accuracy, the state of the LFSR must be leaked; helping in calculate the coefficient vector. Guessing the first ten numbers correctly, would give us the state for the next number to be guessed. Now remains the coefficient vector that has 10 elements. So, guessing another 10 numbers will basically give us 10 equations to solve under modulus. Easily done using sage.

state=REDACTED #list of the first 20 integers guessed.

state_matrix=[state[i:i+10] for i in range(10)]
M=Matrix(Zmod(5039),state_matrix)
V=vector(Zmod(5039),state[-10:])

coeff=M.solve_right(V).list()

Now we can have 100% accuracy in our guesses.

BUT, we only have 260 trials for 200 numbers. Taking 20 away from 200, leaves 180. Hence, we need to have atleast 180 trials after the coefficient matrix was calculated to solve this challenge, implying in atmost 80 (260-180) the first 20 numbers needs to be guessed.

As said earlier even the best script can guess in number 5-7 tries, that means about 100-140 trials needed to guess 20 numbers. This won’t work. :/

This was where, I quit. I thought there must have been something related to the lfsr or that issolvable() function, that was holding me back. I should have looked at other parts too.

The “vulnerabilty” (ofc) lay in the way the input was being checked for cows and bulls

def check(pin, guess):
    c = 0
    b = 0
    for i in range(len(guess)):
        if guess[i] in pin:
            if pin.index(guess[i]) == i: c += 1
            else: b += 1
    return [c,b]

def play():
    i = 0
    print("Flag is locked under %d pins, you have %d guesses." % (N, r))

    for _ in range(r):
        guess = input("Enter pin %d:\n>" % (i+1))
        c, b = check(pins[i], guess)
        if c == 4 and b == 0:
            i += 1
            if i == N:
                print("Congratulations! Here is the flag: %s" % flag)
                return
            else:
                print("Correct, onto the next one!")
        else: 
            print("Wrong! Hint: C%dB%d" % (c,b))

    print("Out of guesses, exiting...")

Our guess is passed into the check() function, where it calculates the number of cows and bulls. See the error? I didn’t. Instead of checking just four digits of the guess, it check for all of them. There is no freaking limit, we can even send in a 1024 bit prime and it will returns the number of cows and bulls for it.

How can we exploit this?

Here’s a screenshot:

>>> bin(46)[2:].zfill(10)
'0000101110'

Entering the digits in powers of two, helps us narrow down the search space from 5039 all the way to 24. WE KNOW THE 4 DIGITS THAT ARE IN THE NUMBER BIG BRAIN MOVE sigh…

So, how much does it helps us. Ehh, sadly no soo much… even using the copied script from github to have the best guess, it takes at an average of 4.25 tries to be correct. That hangs us around 175. ;-;

With a bit of luck and optimization using the output of the number of cows, I was reaching 180 or above, once in about 10 tries. YAY!!!

So, I coded it up… fixed some bugs and there it was, the mighty flag. dctf{N0_way_y0u_gu3ss3d_that_w1thout_ch34t1ng}

This was a neat challenge with a easily overlooked issue. Hence Peeps, we must always sanitize our hands and input. Coz, viruses and users are not to be trusted.

Below are links to my scripts: solve.py copied_n_modified.py challenge_file

Don’t use them, they are bad. I just wrote this writeup for memory sake.