## Stegasaurus Scratch

We're given a `netcat` invocation and a download containing a C program (plus Makefile and wrapper script).
The `main` function looks like this:

```c
int main(void) {
setvbuf(stdout, NULL, _IONBF, 0);
urand = fopen("/dev/urandom", "r");
if (!urand) return 0;
// server has a 10 second timeout; disabled for testing
//alarm(timeout);
if (getfile()) {
if (run()) {
system("cat flag.txt");
} else {
puts("failed");
}
}
fclose(urand);
return 0;
}
```

`getfile()` just reads a file from `stdin` and puts the contents in a global buffer.
If we can get `run()` to return `true` we get the flag.

`run()` looks like this:

```c
bool run() {
// Create two instances of the code, one for all of Alice's handling
// and the other for all of Bob's
Alice = luaL_newstate(); Bob = luaL_newstate();

// Give them table and math stdlibs
luaL_requiref(Alice, LUA_TABLIBNAME, luaopen_table, 1); lua_pop(Alice, 1);
luaL_requiref(Alice, LUA_MATHLIBNAME, luaopen_math, 1); lua_pop(Alice, 1);
luaL_requiref(Bob, LUA_TABLIBNAME, luaopen_table, 1); lua_pop(Bob, 1);
luaL_requiref(Bob, LUA_MATHLIBNAME, luaopen_math, 1); lua_pop(Bob, 1);

if (luaL_dofile(Alice, fp)) return false;
if (luaL_dofile(Bob, fp)) return false;

bool won = trial();
lua_close(Alice); lua_close(Bob);
return won;
}
```

Two Lua VMs are created and a small subset of the Lua standard libraries are loaded in - only the math and table libraries.
The file we provide to the server gets loaded into each VM (and must successfully load).

An interesting sidenote is that loading bytecode is not disabled!
This is [likely](https://saelo.github.io/posts/pwning-lua-through-load.html) [exploitable](https://blog.roblox.com/2012/08/bye-bye-bytecode/) and might offer another solution to this challenge, but since the category was crypto, I assume that's not the intended solution here.

Then the function `trial()` is called and its return value determins whether we get the flag.
The trial is broken into two parts, each of which must pass 10,000 times in a row.
Each trial first calls the global variable `Alice1`/`Alice2` in the `Alice` VM, then `Bob1`/`Bob2` in the `Bob` VM.
The trials simulate a sort of card game.

### Part 1
A deck of 40,000 cards (numbered 1 through 40,000) is shuffled.
Alice draws 8 cards from this deck.
Alice must discard one card, and then passes the remaining 7 cards to Bob.
Alice may change the order of the 7 cards before passing them.
Bob must then guess the value of the card Alice discarded.
To pass the trial, Bob must correctly guess the exact value of the card 10,000 times in a row!

In terms of how this works in Lua, `Alice1` is called with a single argument, which is a sequence of 8 numbers representing Alice's hand of 8 cards.
`Alice1` returns a table of 7 numbers, representing the hand to be passed to Bob.
(This hand is checked to ensure that Alice returns 7 of the 8 cards originally dealt to her.)

> Tables in Lua are sort of like dictionaries in Python, but they are also used as arrays/lists, with sequential numerical keys starting from 1.
> I refer to a table which is being used in this way as a "sequence".

`Bob1` is then called in a separate VM, with the hand Alice returned passed as an argument.
`Bob1` must return a number, which is Bob's guess as to which card Alice discarded.

Since all cards are unique, the hand Alice passes to Bob can be in one of 7! = 5,040 states (permutations).
Since there are 40,000 cards total, this lets Bob narrow his choices selection down to one of 8 cards (40,000 / 5,040 ≈ 8).
We can use the permutations of the 7 cards to communicate a number from 1 to 5,040 using [Lehmer codes](https://en.wikipedia.org/wiki/Permutation#Numbering_permutations).
(I initially used the iterative permutation algorithm described [here](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order) but it proved too slow to pass 10,000 trials within the 10 second timeout.)

```lua
function getindex(t, x)
-- return index of x in sequence t
for i = 1,#t do
if t[i] == x then
return i
end
end
end

function copy(t)
-- shallow copy sequence t
local copy = {}
for i = 1,#t do
copy[i] = t[i]
end

return copy
end

function fact(x)
-- compute factorial of x
local result = x
for i=x-1,1,-1 do
result = result * i
end
return result
end

function getpermutation(a)
-- get the lexographical index of the permutation of a
-- https://stackoverflow.com/questions/14013373/finding-the-index-of-a-given-permutation
local index = copy(a)
table.sort(index)

local permutation = 0
local n = #a
factor = fact(n-1)
for i=1,n do
x = getindex(index, a[i])
table.remove(index, x)
permutation = permutation + ((x-1) * factor)
if i < n then
factor = factor//(n-i)
end
end

return permutation
end

function permute(a, permutation)
-- permute the elements of a into their lexographically-nth permutation
-- https://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others

table.sort(a)
local n = #a
factor = fact(n-1)
for i=1,n-1 do
x = permutation // factor
permutation = permutation % factor

local tmp = table.remove(a, i+x)
table.insert(a, i, tmp)
factor = factor//(n-i)
end
end
```

Now Alice and Bob can communicate a 1-in-5,040 choice:

```lua
-- we can modify stegasaurus.c to load the base libraries to enable printing for debug
-- if print does not exist just make it a no-op so our code works on the server too
if print == nil then
print = function(...) end
end

function Alice1(hand)
round1 = (round1 or 0) + 1
print("Hi, I'm Alice, this is check 1 round " .. round1)

discarded = table.remove(hand)
print("card",discarded)

-- Select a permutation for the remaining 7 based on the value of the discarded card / 8.
local permutation = discarded//8
print("perm",permutation)

permute(hand, permutation)

return hand
end

function Bob1(hand)
print("Hi, I'm Bob")
-- get the permutation number of the cards Alice gave us
local permutation = getpermutation(hand)
print("perm",permutation)
-- and choose one of the 8 possibilities at random
local randvalue = math.random(0,7)
print("rand",randvalue)
-- determine Alice's card
local guess = (permutation*8)+randvalue
print("guess",guess)
return guess
end
```
Great. But Bob will get it wrong 7 times in 8.
How can we communicate the final 1-in-8 choice reliably?

The secret lies in Lua's `math` library and its `random`/`randomseed` functions.
`math.randomseed` is just a wrapper around the C function `srand`:

> The `srand()` function sets its argument seed as the seed for a new sequence of pseudo-random numbers to be returned by `rand()`.
> These sequences are repeatable by calling `srand()` with the same seed value.

Since `srand()` is a C library function, its state is global within a process - that means it's shared between the two Lua VMs!
We can use this to communicate a few bits of information from Alice to Bob:

```lua
function Alice1(hand)
round1 = (round1 or 0) + 1
print("Hi, I'm Alice, this is check 1 round " .. round1)

discarded = table.remove(hand)
print("card",discarded)

-- Select a permutation for the remaining 7 based on the value of the discarded card / 8.
local permutation = discarded//8
print("perm",permutation)
local randvalue = discarded % 8
print("rand",randvalue)

permute(hand, permutation)

-- Find a seed so the next call to random(0,7) tells Bob which of the 8 possible cards is ours, and then seed it.
local seed = 0
math.randomseed(seed)
while math.random(0,7) ~= randvalue do
seed = seed + 1
math.randomseed(seed)
end
print("seed",seed)
math.randomseed(seed)

return hand
end
```

Alice finds a seed such that the next call to `math.random(0,7)` returns the correct choice, then re-seeds the RNG with that value before passing the hand to Bob.
Now when Bob uses `math.random` to select which of the 8 possible cards to pick, he will always choose correctly!

### Part 2
A deck of 96 cards, 64 of which are marked '1' and 32 of which are marked '2', is shuffled.
Alice may look at the deck, choose any 32 of the cards marked '1', and flip them face-up to reveal them to Bob.
Alice then passes the deck to Bob.

Bob may not look at the deck (apart from the cards Alice flipped).
Bob must then correctly identify which of the remaining 64 cards are marked '2'.

In Lua: `Alice2` is called with a sequence of 96 numbers which are all either 1 or 2.
`Alice2` returns a sequence of 32 indices (1 to 96) indicating which cards she decides to flip.
This is checked to make sure Alice flipped 32 cards and all of those were 1s.

`Bob2` is called with a sequence of 96 numbers which are all 1 or 0, where 0 indicates a card Alice flipped (which was originally a 1) and 1 indicates a card Alice did not flip (originally either a 1 or a 2).
`Bob2` returns a sequence of 32 indices (1 to 96) indicating his guess as to which cards are the 2s.
`Bob2` must correctly identify the index of every 2.

A strategy for this is for Alice to iterate backwards through the deck.
She keeps a counter which is initialized to 0.
- If she finds a 2, she increments the counter.
- If she finds a 1, and the counter is above 0, she flips that card and decrements the counter.
- If she finds a 1 and the counter is 0, she does not flip the card.
If she reaches the beginning of the deck she loops back to the end.
She continues until she has flipped 32 cards.

Bob reverses this by iterating forwards through the deck with a counter of his own.
- If he sees a flipped card, he increments his counter.
- If he sees an unflipped card, and his counter is above 0, he marks it as a 2 and decrements the counter.
- If he sees an unflipped card and his counter is 0, he skips it.
If he reaches the end of the deck he loops to the beginning.
He continues until he has identified all 32 2s.

This will work as long as Bob starts on an unflipped 1.
If he starts on a 2 or a flipped 1, he may misidentify some cards.
Since there are 32 unflipped 1s, there is guaranteed to be one in the first 65 cards of the (96-card) deck.
This choice of 1 in 65 is a small enough value to communicate through the same `math.randomseed` mechanism used in part 1 without wasting too much time finding a good seed:
```lua
function Alice2(hand)
round2 = (round2 or 0) + 1
print("Hi, I'm Alice, this is check 2 round " .. round2)

local flipped = {}
local flipdict = {}
local n = #hand
local i = n
local toflip = 0
while #flipped < 32 do
if hand[i] == 2 then
toflip = toflip + 1
elseif toflip > 0 and not flipdict[i] then
toflip = toflip - 1
table.insert(flipped, i)
flipdict[i] = true
end
i = i - 1
i = ((i - 1) % n) + 1
end

-- bob needs to start on an unflipped 1
local startindex
for i=1,65 do
if hand[i] == 1 and not flipdict[i] then
startindex = i
break
end
end

if startindex == nil then
print("Failed to find an unflipped 1 in first 65 values!")
startindex = 0
end
print("i",startindex)

-- use the random seed to communicate the index of the first unflipped 1
local seed = 0
math.randomseed(seed)
while math.random(65) ~= startindex do
seed = seed + 1
math.randomseed(seed)
end
math.randomseed(seed)

return flipped
end

function Bob2(hand)
print "Hi, I'm Bob"

local flipped = {}
local n = #hand
local toflip = 0
local i = math.random(65)
print("i",i)
while #flipped < 32 do
if hand[i] == 0 then
toflip = toflip + 1
elseif toflip > 0 then
toflip = toflip - 1
table.insert(flipped, i)
end
i = i + 1
i = ((i - 1) % n) + 1
end

return flipped
end
```

And that does it, passing both trials and yielding the flag: `PCTF{c4rd_b4s3d_crypt0_1s_4_r33l_fi31d}`!
Not sure if that was really "crypto", but it was fun, anyway.

## Postscript
After the CTF, I realized that the random seed communication channel is much more useful and powerful than I initially thought. For example, here is a much simpler solution to round 1:

```lua
function getseeds(lowerbound, upperbound)
seeds = {}
found = 0
seed = 0
while found <= upperbound - lowerbound do
math.randomseed(seed)
result = math.random(lowerbound, upperbound)
if seeds[result] == nil then
seeds[result] = seed
found = found + 1
end
seed = seed + 1
end
return seeds
end

function Alice1(hand)
seeds = seeds or getseeds(1,40000)
discarded = table.remove(hand)
math.randomseed(seeds[discarded])
return hand
end

function Bob1(hand)
return math.random(1,40000)
end
```

By memoizing the seed for each output we can easily generate a table of seeds for all values 1 through 40,000. A similar approach could work on part 2.

And then I read some writeups from other teams and realized that there are actually algorithms which allow you to pass both trials _without_ resorting to "cheating" using the random number generator! I think my solution is more interesting, though likely unintended, and perhaps offers an idea which a future challenge could be based around.