Tags: lua

Rating:

## 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)

-- 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)

-- 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)