First I searched Mini Purε, and checked the official writeup of De1CTF2019. In that problem, we randomly select the key of last round, and use interpolation to check it.
Let the message be , after 15 rounds, it becomes , where is a polynomial of degree about . If we still enumerate the key and then check, the time complexity is about , which is too high.
Suppose there's some polynomial , and the degree of is less than , and we are given . Now consider the formula of Lagrange interpolation:
It's difficult to compute in most cases, but if for some , it become easier.
(Consider removing the constraint , then all occurs in the left side)
Let , then
Since can be computed in time and the inverse of can be precalculated in time, can be calculated in time.
For the polynomial that I mentioned at the start of this writeup, is a cubic polynomial in . Let , by the equation above, we can find a cubic equation of . It's easy to solve, and then we can find by the same method.
See code in Chinese version writeup