Is it possible to exactly reverse engineer an unknown cipher inside a black box?

Question

Consider the following arrangement:-

There is an unknown cipher algorithm operating inside the black box. You can enter infinite key /plain text pairs, and observe all of the outputs. The box might just as well be protecting a short friend/foe challenge as an entire 4K UHD movie. Any counter modes, streams, IVs, nonces or padding is handled inside the box. All you need to do is input any size of plain text. The cipher is a world class modern type with strength equivalent to *fish, Rijndael or ChaCha, but not one of those. It may have come from outer space, or perhaps in a vision. The point is that no one has ever seen it. It might even be a totally unknown NSA Suite A algorithm.

Given unlimited input output tuples, is it possible to reverse engineer the algorithm exactly so that it could be used reliably for future encryptions?

Note: Hypothetical unknown cipher - security in obscurity? came up, but honestly I can't understand the question.

Answer 1

No, it is not in general possible to reverse-engineer an unknown cipher inside a black box. Proof: we can build a black box as asked that is demonstrably impossible to reverse-engineer from the outside, if the box is impenetrable and AES/Rijndael (used as a building block) is secure.

A suitable design implementing a block cipher is (for 128-bit arguments)

$$\text{BOX}(K,P)\mapsto\text{AES-128-ENC}(K,\text{AES-128-ENC}(S,P))$$

where for $\text{BOX}$ and $\text{AES-128-ENC}$ the first of the two arguments is the block cipher's key. $\text{BOX}$ has a partially secret design (the 128-bit secret constant $S$). Distinguishing $\text{BOX}$ from an ideal encryption oracle (implementing a random 128-bit permutation of $P$ for each $K$) without knowing $S$ would be a break of AES-128, which is believed to be computationally infeasible.

We could wrap the above $\text{BOX}$ into a $\text{BOX2}$ performing a cipher, rather than a block cipher; e.g. $\text{BOX2}$ could be $\text{BOX-CTR}$. We can extend to larger arguments (e.g. 256-bit as supported by Rijndael, if not by AES) to become resistant to distantly foreseeable progress.

Actual modern (post-DES) ciphers with secret design are reverse-engineered by analyzing leaks about their design, or/and the inside of a captured black box, or/and (to some degree) physical side-channels like unwanted electromagnetic emission.

---

Per comment: One public example of hardware reverse-engineering is Karsten Nohl and David Evans's Reverse-Engineering a Cryptographic RFID Tag, in proceedings of Usenix 2008. Some of their results could not have be obtained from specs alone (e.g. that the implementation reverse-engineered redundantly computes the same Boolean function). There are other, less well documented examples in the field of pay-TV Smart Cards, which reportedly have used customized ciphers, some allegedly broken by reverse-engineering.

For reverse engineering of (quite partially) unknown ciphers by physical side-channels, see e.g. Christophe Clavier's Side Channel Analysis for Reverse Engineering (SCARE) - An Improved Attack Against a Secret A3/A8 GSM Algorithm, in proceedings of ICISS 2007 (paywalled), which is the final form of earlier work (Postscript; PDF translation here).

Answer 2

Judging by your comments, you are imagining a box that accepts inputs of arbitrary length. Hence it is a function $f:\{0,1\}^*\to\{0,1\}^*$. There are uncountably many such functions but only countably many programs you could propose as the "reverse engineered" result. This makes your problem fundamentally impossible.

Answer 3

The answer is NO, as @fgrieu said. I will look from different perspective.

n to 1 Boolean functions in a black-box

Let $f:\{0,1\}^n \rightarrow \{0,1\} $ be n to 1 boolean function;

Now consider two special cases;

$f_1(a_1,\ldots,a_n) = a_1 \wedge \ldots \wedge a_n$, and

$f_2(a_1,\ldots,a_n) = a_1 \wedge \ldots \wedge (a_i \oplus a_j) \wedge \ldots \wedge a_n$

• Fact: To determine the $f_1$ you have to check all input values.
• Fact: To determine The $f_2$ you have to check all input values.

A sketch of proof can be seen as; If you only try $2^n-1$ what is the probability that the black-box produce 1 or 0?

Question; given by an Oracle that the black-box must be one of the functions $f_1$ and $f_2$, but he says "I don't know where the $\oplus$ occurs"

The $\oplus$ causes $1$ extra $T$ value in the Truth table. There is only one difference in their Truth table. To distinguish them $n^2/2$ queries are required.

Distinguishing this too simple difference of two functions must give an idea about the hardness of the problem.

Conclusion: We must check every input value to determine the 2-1 function.

n to n Boolean functions in a black-box

This is very short since any $n$ to $n$ function can be represented as $n$, $n \text{ to } 1$ boolean functions. Each boolean function can be determined individually, we have $2^n$ for each and $n$ outputs.

(n,k) to n Block Cipher in a black-box

The key $k$ in this function generate an extra $2^k$ space. One can easily see that by the avalanche criteria. If you fix a key $k'$ and determine the $n$ boolean function, and than choose another $k^{''}$ such that $pop\_count(k' \oplus k^{''}) = 1$ you will see your current function doesn't satisfy at least half of the outputs in a fixed input.

This also give an intutuion about why we have to test all input values.