Reverse Engineering challenge #25 (black box).

Tags: L3 CRYPTO .

It's a secret algorithm hidden inside of a black box (e.g. a smart card). It's not possible to reveal it (well, at least, let's say, using our current hypothetical budget). But we can send a lot of random data to it and observe responses.

There are 8 black boxes and 100,000 questions/answers pairs are gathered for each:

The problem is to find expression which will be correct for each pair. The problem is generally known to be unsolvable, but it can be practically solved if there are few operations in expressions. Here is one method: http://yurichev.com/writings/z3_rockey.pdf.

To make things slightly harder, inputs like 0, 0xFFFFFFFF, 0x55555555, 0xAAAAAAAA, etc, were not sent to black boxes.

Black boxes for this example were constructed in the sense of naive amateur cryptography (security through chaotic mess of operations and random constants), so they all contains no more than 6 primitive mathematical/logical operations and also small constants (smaller than 64 for the most black boxes, but one of them has a bigger constant as exception).

First three black boxes are easiest, last two are probably hardest.

More challenges: challenges.re; about solutions: challenges.re/#Solutions.