# 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).
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!
`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:*
## 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)
```
Google Drive
Gist
Clipboard
Sign in with Wallet
