Tags: virtual sqlite
Rating:
**Description**
> the format of flag is flag{.+}
>
> attachment: https://drive.google.com/open?id=1TDWJWb2diPO_TDTHbZvuLWlsTV1LhoAs
**Solution**
We were given a copy of a `sqlite3` terminal session, where the user typed `explain [some query]`, which produced the detailed SQLite VM bytecode. We don't know what the query is, and it seems the VM bytecode is more compressed than usual, since for my `sqlite3` it looked like:
sqlite> explain select 1;
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 1 0 00 Start at 1
1 Integer 1 1 0 00 r[1]=1
2 ResultRow 1 1 0 00 output=r[1]
3 Halt 0 0 0 00
So the challenge doesn't include the comments column, but other than that all the information is present. The above is useful to check which column represents what.
My first idea was to test some queries directly in `sqlite3` and refine them until the trace matches the one provided. But since the trace contains so many calls to `substr(3)` I figured the flag is probably matched character by character in a shuffled order, so this would probably take too long.
So the approach was to write a simple VM to emulate the opcodes that we actually need, and see what conditional checks are being executed to extract what the flag has to be to pass those checks. There is [an online reference of SQLite3 bytecodes](https://sqlite.org/opcode.html) - very useful for this challenge of course. It also explains the VM well enough to write a super simple implementation.
It was enough to implement these opcodes:
- `Column`
- `Function`
- `Eq`
- `Goto`
- `Integer`
- `Ne`
- `OpenRead`
- `Rewind`
- `String8`
- `TableLock`
- `Trace`
- `Transaction`
- `VerifyCookie`
And even some of these were basically no-ops. One additional piece of information was used to solve the problem: all the conditional `Ne` checks in the query jumped to instruction 90, which immediately halted the machine. So as soon as there is a character mismatch, the query failed. Therefore, we know that these checks need to have operands that are equal to one another. As it turns out, they were always a single character string, and a single character substring of the flag.
([full sqlite mini-VM](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-05-19-RCTF/scripts/sql/Main.hx))
And with that:
`flag{lqs_rof_galf_esrever_a}`
