# Moth

In this simple reverse challenge we need to find the password for `moth`

.

## The binary

In Ghidra, we can have a quick look at the main function:

We need to find a `0x51`

characters long password.

In `verify`

, we seem to be performing 3 seperate checks in a 9 by 9 grid:

The first check makes sure that our value is be between 1 and 5 (‘a’ to ‘e’) and that it smaller than our zone size (We are calling a zone a group of characters in the key with the same value).

The second check makes sure that if the key has the same value at 2 coordinates then our password must have different values. In other words, in a given zone, each value needs to be distinct.

The last check makes sure that two adjacent cells (orthogonally or diagonally) have different values.

These checks looks a lot like sudoku checks…

## The puzzle

If you are into sudokus (or an avid Cracking the cryptic fan) you can try and solve this puzzle by hand:

Here are the rules:

- Every zone has every digit from 1 to the size of the zone
- Orthogonal and diagonal cells cannot have the same value

TRADITIONAL SUDOKU RULES DO NOT APPLY

## Wave function collapse

If you are too lazy to solve the above problem by hand you can always write a program to do so.

My preferred method for sudoku like problems is using the wave function collapse algorithm.

Here’s how the algorithm goes:

- Set the initial constraints on each cell
- While there remain undecided cells (a cell with more than one value)
- Find the most constrained undecided cell
- Chose a value in the available values for that cell
- Propagate this change by modifying the constraints of every necessary cell
- If a cell is over constrained -> backtrack

Here’s my python implementation that solves this problem

```
import copy
def reduce(grid: list[list[set[int]]], x: int, y: int, value: int):
grid = copy.deepcopy(grid)
color = g[y][x]
# No same number in a given color
for yy in range(9):
for xx in range(9):
if g[yy][xx] != color:
continue
if xx == x and yy == y:
continue
if value in grid[yy][xx]:
grid[yy][xx].remove(value)
# No same number around around
for dy in [-1, 0, 1]:
for dx in [-1, 0, 1]:
if dy == 0 and dx == 0:
continue
if x + dx < 0 or x + dx >= 9:
continue
if y + dy < 0 or y + dy >= 9:
continue
if value in grid[y + dy][x + dx]:
grid[y + dy][x + dx].remove(value)
return grid
def verify(grid: list[list[set[int]]]):
for y in range(9):
for x in range(9):
if len(grid[y][x]) == 0:
raise ValueError("Empty cell")
def solve(grid: list[list[set[int]]], stack: list[tuple[int, int]], indentation=0):
if len(stack) == 0:
return grid
stack.sort(key=lambda coords: len(grid[coords[1]][coords[0]]))
x, y = stack.pop(0)
values = [v for v in grid[y][x]]
for v in values:
try:
grid[y][x] = set([v])
grid2 = reduce(grid, x, y, v)
verify(grid2)
return solve(grid2, copy.deepcopy(stack), indentation=indentation+1)
except ValueError as e:
continue
raise ValueError()
grid = [[set(range(1, g2[y][x] + 1)) for x in range(9)] for y in range(9)]
all = [(x, y) for x in range(9) for y in range(9)]
SOLUTION = solve(grid, all)
print(SOLUTION)
print(''.join([''.join([['a', 'b', 'c', 'd', 'e'][list(SOLUTION[y][x])[0] - 1] for x in range(9)]) for y in range(9)]))
```

Here is the solved grid:

```
[[{2}, {3}, {1}, {5}, {4}, {2}, {1}, {2}, {1}],
[{1}, {4}, {2}, {3}, {1}, {3}, {4}, {3}, {4}],
[{2}, {3}, {1}, {4}, {2}, {5}, {2}, {1}, {2}],
[{4}, {5}, {2}, {5}, {3}, {1}, {3}, {5}, {3}],
[{3}, {1}, {4}, {1}, {4}, {5}, {4}, {1}, {2}],
[{4}, {2}, {5}, {2}, {3}, {2}, {3}, {5}, {4}],
[{3}, {1}, {3}, {1}, {5}, {4}, {1}, {2}, {1}],
[{2}, {5}, {2}, {4}, {2}, {3}, {5}, {4}, {3}],
[{1}, {3}, {1}, {3}, {5}, {4}, {1}, {2}, {1}]]
```

## Flag

Here is the password for the binary:
`bcaedbabaadbcacdcdbcadbebabdebecaceccadadedabdbebcbcedcacaedababebdbcedcacacedaba`

When we run the binary with this password we get:

```
Well done, flag is ECW{md5(input)}
```

FLAG: `ECW{8b39553c944cdce4ea4f9a692168093b}`