mcfx's blog


De1CTF 2020 Mini Purε Plus Writeup (English)

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 (C,x)(C,x), after 15 rounds, it becomes (F(x),G(x))(F(x),G(x)), where FF is a polynomial of degree about 3143^{14}. If we still enumerate the key and then check, the time complexity is about O(342)O(3^{42}), which is too high.

Suppose there's some polynomial ff, and the degree of ff is less than kk, and we are given f(0),f(1),,f(k)f(0),f(1),\dots,f(k). Now consider the formula of Lagrange interpolation:

f(x)=j=0kf(j)i=0,ijkxiji f(x)=\sum_{j=0}^k f(j)\prod_{i=0,i\neq j}^k\frac{x\oplus i}{j\oplus i}

It's difficult to compute in most cases, but if k+1=2pk+1=2^p for some pp, it become easier.

We have

i=0,ijkxjxi=i=1ki \prod_{i=0,i\neq j}^k{x_j\oplus x_i}=\prod_{i=1}^{k}i

(Consider removing the constraint iji\neq j, then 0,1,,k0,1,\dots,k all occurs in the left side)

Let A=i=1ki,B=i=0kxiA=\prod_{i=1}^{k}i,B=\prod_{i=0}^{k}x\oplus i, then

f(x)=j=0kf(j)BA(xj) f(x)=\sum_{j=0}^k f(j)\frac{B}{A\cdot(x\oplus j)}

Since A,BA,B can be computed in O(k)O(k) time and the inverse of xjx\oplus j can be precalculated in O(k)O(k) time, f(x)f(x) can be calculated in O(k)O(k) time.

For the polynomial FF that I mentioned at the start of this writeup, F(x)F(x) is a cubic polynomial in key[15]\text{key}[15]. Let k=2231,x=223k=2^{23}-1,x=2^{23}, by the equation above, we can find a cubic equation of key[15]\text{key}[15]. It's easy to solve, and then we can find key[2],,key[14]\text{key}[2],\dots,\text{key}[14] by the same method.

See code in Chinese version writeup

日期: 2020-05-06

标签: CTF Writeup