## 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:
```cint 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:
```cbool 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 1A 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.)
```luafunction getindex(t, x)    -- return index of x in sequence t    for i = 1,#t do        if t[i] == x then            return i        end    endend
function copy(t)    -- shallow copy sequence t    local copy = {}    for i = 1,#t do        copy[i] = t[i]    end
    return copyend
function fact(x)    -- compute factorial of x    local result = x    for i=x-1,1,-1 do        result = result * i    end    return resultend
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 permutationend
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)    endend```
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 tooif print == nil then    print = function(...) endend
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 handend
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 guessend```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:
```luafunction 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 handend```
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 2A 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:```luafunction 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 flippedend
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 flippedend```
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.
## PostscriptAfter 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:
```luafunction 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 seedsend
function Alice1(hand)    seeds = seeds or getseeds(1,40000)    discarded = table.remove(hand)    math.randomseed(seeds[discarded])    return handend
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.