- Category: Reversing
- Score: 471/500
- Solves: 19
Can you find what this (very inefficient) VM is doing?
The VM implements Markov algorithm, and the flag checker does these steps:
- Convert the flag into a ternary string
- Apply (mod 3) lfsr state transition
Ntimes - Check if the result matches a certain ternary string
So you can find the N and the lfsr taps by analyzing the substitution rules, then it is easy to reverse the state transition and get the flag.
It is possible to inspect the intermediate states and solve a linear equation to find its transition matrix instead.