---
# System prepended metadata

title: HSCTF-10 Writeup

---

# HSCTF-10 Writeup
## rev/1125899906842622 - 492 points

### Description: 
I found this credit card on the floor!
### Challenge files:
* `1125899906842622.py`

---

### Initial Analysis

```python!
a = int(input())
t = a
b = 1
c = 21140326319332556493517...
verified = False
while 1:
	if b == 4:
		verified = True
		break
	d = 2 + (1125899906842622 if a&2 else 0)
	if a&1:
		b //= d
	else:
		b *= d
	b += (b&c)*(1125899906842622)
	a //= 4
if verified:
	t %= (2**300)
	t ^= 1565959740202953...
	print(t)

```

We have a few interesting numbers that we notice first, `c` which is a 2500 bit number, `1125899906842622 = 2**50 - 2`, which happens to be the name of the challenge. And then there's number that `t` is finally XORed with, which I'm assuming will give us the flag. 

Going through the flow of the program, we see that `t` and `a` are in our control. And seemingly, the goal is to set `verified` to `True`, i.e., to set `b` to 4. Trying random inputs makes the program run indefinitely. Trying to print out the values of `b` at each iteration, the value seemingly grows, which is not what we want. 

Let's take a closer look at what's happening: 
In each iteration, the lower 2 bits of `a` play a role in deciding the values of `d` and `b`. Which means, `d` can either be `2**50` or `2` and `b` can either be divided by or multiplied by that value. 


## Functioning
A multiplication or division with a power of 2 is essentially a left shift or right shift respectively. So in each iteration, the lower two bits of a control a left or right shift by 1 or 50. 

| a&2 | a&1 |   d   | Function |
|-----|-----|-------|----------|
|  0  |  0  |   2   |  b<<1    |
|  0  |  1  |   2   |  b>>1    |
|  1  |  0  |2\*\*50|  b>>50   |
|  1  |  1  |2\*\*50|  b<<50   |

And since `a` is our input, we can control the value of `b` using a series of these operations. We start at `b=1` and we need to end at `b=4`. 
However, we have this line that comes after each operation.
`b += (b&c)*(1125899906842622)`
This is the reason that `b` grows almost every time we run it with random inputs. 

Considering the fact that we start with b as just 1 bit, and the desired output is also just 1 bit --> `100` (4)

## How I made a game out of this ( •_•)>⌐■-■ (⌐■_■)

Having no idea of how to find the right number to input, I thought of this approach: 
1. Shift a bit across `c`, starting from bit position 0 and end up at bit position 2
2. Think of the set bits (1) of `c` as mines. Avoid them at all costs! 

I couldn't think of an algorithm to do this yet, so I thought I'd make a simple game out of it to interact with it. 

The first version of it printed the binary of `c` linearly, and placed a red bit that you could move around using 4 inputs: 
`l1`, `r1`, `l5`, `r5`
Using this control system got tiring really quick, so I decided to improve the game. 

I bound the left and right arrow keys to 1 bit shifts, and up and down arrows to 50 bit shifts. The player's current position would be highlighted in red. 
I also made it so that it would record the moves that you made, and remove redundant moves. 

I played this for more time than I'm willing to admit, before I realized that it was just a 50x50 grid. So I changed the game accordingly to print the binary as a 50x50 grid instead one line. The up and down moves would actually be moving me up and down the grid (obviously).

![](https://hackmd.io/_uploads/r1q3jEDP2.gif)

So all I had to do was solve this maze using some algorithm, and I started looking for one. (Part of me still wanted to solve it using the game...)

## Solution

I figured out that I could use a Breadth-First search algorithm on this to find a path from the start to the finish. 

The algorithm works by traversing the maze in a breadth-first manner. It keeps track of the current position, and distance. In each iteration, it checks for available paths in all four directions and queues the unexplored paths. When it finally finds the goal point, it returns the path that was taken to reach it. 

Our starting point would be `(49, 49)`, the initial bit position, and the goal would be at `(49,47)`.

I took some code from my game, modified it and used BFS to find a path. Since I was using code from an earlier version of the game, the path would be a list of `l1`s and `r1`s. I took the lazy approach and decided to parse this instead of changing the code itself. 

I get this big list of moves: 
```python!
['l5', 'l5', 'l5', 'l5', 'l1', 'l1', 'l1', 'l1', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l1', 'l1', 'l5', 'l5', 'r1', 'r1', 'r1', 'r1', 'r5', 'r5', 'r1', 'r1', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l1', 'l1', 'l1', 'l1', 'l5', 'l5', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'l5', 'l5', 'l5', 'l5', 'l1', 'l1', 'l5', 'l5', 'l1', 'l1', 'l5', 'l5', 'l1', 'l1', 'r5', 'r5', 'l1', 'l1', 'l5', 'l5', 'l1', 'l1', 'l5', 'l5', 'r1', 'r1', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'l5', 'l5', 'l1', 'l1', 'l1', 'l1', 'l5', 'l5', 'r1', 'r1', 'l5', 'l5', 'l5', 'l5', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'r5', 'r5', 'r1', 'r1', 'r5', 'r5', 'l1', 'l1', 'l1', 'l1', 'l1', 'l1', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'l1', 'l1', 'l1', 'l1', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l5', 'l1', 'l1', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r5', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1', 'r1']
```
Which I reverse and convert back to binary using the table mentioned earlier. 
Feeding that number as input to the challenge script gives us an output in no time!

![](https://hackmd.io/_uploads/rJCcCBwPn.gif)

`OP: 50937517511040739473747084954399628437899554758014667643591355768086908816264879291316093`
Converting this back to bytes gives us the flag! 

Flag: `flag{l4byr1nth_9abe79d712e6dd52c4597}`

## Solve script:

```python!
from collections import deque

c = 211403263193325564935177732039311880968900585239198162576891024013795244278301418972476576250867590357558453818398439943850378531849394935408437463406454857158521417008852225672729172355559636113821448436305733721716196982836937454125646725644730318942728101471045037112450682284520951847177283496341601551774254483030077823813188507483073118602703254303097147462068515767717772884466792302813549230305888885204253788392922886375194682180491793001343169832953298914716055094436911057598304954503449174775345984866214515917257380264516918145147739699677733412795896932349404893017733701969358911638491238857741665750286105099248045902976635536517481599121390996091651261500380029994399838070532595869706503571976725974716799639715490513609494565268488194
cb = bin(c)[2:]

def find_shortest_path(start, end, grid):
    rows = len(grid)
    cols = len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    distance = {}
    queue = deque([(start, [])])
    distance[start] = 0
    while queue:
        curr, path = queue.popleft()
        row, col = curr
        if curr == end:
            return path
        # Check left
        if col > 0 and not visited[row][col-1] and grid[row][col-1] != '1':
            new_dist = distance[curr] + 1
            if (row, col-1) not in distance or new_dist < distance[(row, col-1)]:
                distance[(row, col-1)] = new_dist
                queue.append(((row, col-1), path + ['l1']))
                visited[row][col-1] = True
        # Check right
        if col < cols-1 and not visited[row][col+1] and grid[row][col+1] != '1':
            new_dist = distance[curr] + 1
            if (row, col+1) not in distance or new_dist < distance[(row, col+1)]:
                distance[(row, col+1)] = new_dist
                queue.append(((row, col+1), path + ['r1']))
                visited[row][col+1] = True
        # Check up
        if row > 0 and not visited[row-1][col] and grid[row-1][col] != '1':
            new_dist = distance[curr] + 1
            if (row-1, col) not in distance or new_dist < distance[(row-1, col)]:
                distance[(row-1, col)] = new_dist
                queue.append(((row-1, col), path + ['l5']))
                visited[row-1][col] = True
        # Check down
        if row < rows-1 and not visited[row+1][col] and grid[row+1][col] != '1':
            new_dist = distance[curr] + 1
            if (row+1, col) not in distance or new_dist < distance[(row+1, col)]:
                distance[(row+1, col)] = new_dist
                queue.append(((row+1, col), path + ['r5']))
                visited[row+1][col] = True
    # No path found
    return None

cgrid = [
    [cb[i*50 + j] for j in range(50)] for i in range(50)
]

def path_to_binary(path):
    binary = ''
    for move in path:
        if move == 'l1':
            binary += '00'
        if move == 'r1':
            binary += '01'
        if move == 'r5':
            binary += '11'
        if move == 'l5':
            binary += '10'
    return binary

start = (49, 49)  # 0th bit position
end = (49, 47)  # 2nd bit position
path = find_shortest_path(start, end, cgrid)
if path:
    print("Path found:", path)
else:
    print("No path found.")

print('Solution:', int(path_to_binary(path[::-1]), 2))
flag = (int(path_to_binary(path[::-1]), 2)%2**300) ^ 1565959740202953194497459354306763253658344353764229118098024096752495734667310309613713367
print(flag.to_bytes(flag.bit_length()//8+1, 'big'))
```

*Output:*
![](https://hackmd.io/_uploads/HyIakIDvn.gif)


## The game ʕノ•ᴥ•ʔノ ︵ ┻━┻

*PS: it's buggy and weird, made for visualization purposes*
*PPS: Apologies for the bad code*

```python!
import curses
import locale
from os import system, name

def clear():
    if name == 'nt':
        _ = system('cls')
    else:
        _ = system('clear')

c = 211403263193325564935177732039311880968900585239198162576891024013795244278301418972476576250867590357558453818398439943850378531849394935408437463406454857158521417008852225672729172355559636113821448436305733721716196982836937454125646725644730318942728101471045037112450682284520951847177283496341601551774254483030077823813188507483073118602703254303097147462068515767717772884466792302813549230305888885204253788392922886375194682180491793001343169832953298914716055094436911057598304954503449174775345984866214515917257380264516918145147739699677733412795896932349404893017733701969358911638491238857741665750286105099248045902976635536517481599121390996091651261500380029994399838070532595869706503571976725974716799639715490513609494565268488194
cb = bin(c)[2:]

def print_red(s, end='\n'):
    print("\033[91m{}\033[00m".format(s), end=end)

def get_arrow_key(stdscr):
    key = stdscr.getch()
    if key == curses.KEY_LEFT:
        return 'l1'
    elif key == curses.KEY_RIGHT:
        return 'r1'
    elif key == curses.KEY_UP:
        return 'l5'
    elif key == curses.KEY_DOWN:
        return 'r5'
    else:
        return ''

def removeredundancy(moves):
    last_four = moves[-4:]
    if last_four in ['0100', '0001', '1011', '1110']:
        return moves[:-4]
    return moves

def printgrid(cb, curr):
    for i in range(50):
        for j in range(50):
            if (i*50 + j) == curr:
                print_red(cb[i*50 + j], end='')
            else:
                print(cb[i*50 + j], end='')
        print(' '*83, end='') # 83 because it fits my screen, adjust as needed

def main(stdscr):
    curr = len(cb) - 1
    moves = ""
    stdscr.nodelay(1)  # Set non-blocking input mode

    # Set UTF-8 encoding
    locale.setlocale(locale.LC_ALL, '')
    stdscr.encoding = 'utf-8'

    while True:
        clear()
        # print(cb[:curr], end='')
        # print_red(cb[curr], end='')
        # print(cb[curr+1:])
        # Commented out above code which was printing linearly, replaced with a function to print as a grid
        printgrid(cb, curr)
        moves = removeredundancy(moves)
        print(f'\n Moves so far: {moves}')

        move = ''
        while not move:
            move = get_arrow_key(stdscr)

        try:
            if move == 'l1':
                if cb[curr-1] == '1':
                    print("Invalid move")
                    continue
                curr -= 1
                moves += '00'
            if move == 'r1':
                if cb[curr+1] == '1':
                    print("Invalid move")
                    continue
                curr += 1
                moves += '01'
            if move == 'r5':
                if cb[curr+50] == '1':
                    print("Invalid move")
                    continue
                curr += 50
                moves += '11'
            if move == 'l5':
                if cb[curr-50] == '1':
                    print("Invalid move")
                    continue
                curr -= 50
                moves += '10'
        except KeyboardInterrupt:
            exit()
        except:
            pass

curses.wrapper(main)
```