The Mutilated AES Challenge

[chants]

Well the mathematical or formulaic "white-box" strategy does seem like a total dead-end here. 10 rounds through the AES substitution-permutation network (well I suppose 8 + the first and last which are slightly different) and even with a linear s-box, its pretty much hard to mathematically deduce anything.


From the "black-box" way you mentioned. Well first we know the high bit of each byte is 0, giving 16 bits of 128. But 2^112 is still way too big and even playing with ascii character ranges does not get us within brute force range. So my guess here is quite obvious: linear cryptanalysis. Obviously differential is useless here as you did not give us two or more input-output pairs. But the linear s-boxes should cause a linear bias: Statistical bias in the output bits based on the key bits. It should theoretically get this within range for a practical attack. Is this the right direction?

[dila]

Yes that sounds right. You can use techniques from linear cryptanalysis. My understanding is that this will lead to linear approximations for the function, but note that in this case the approximation will be exact, which should mean there is less computation involved.

By the way, if you solve the challenge you can give your solution as SHA256(your_name||solution) so that your solution is hidden but can be verified.