Consider the following arrangement:-

box

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.

  • 2
    If there is no stage as in block cipher, with all input-output pairs we can construct a table for it. – kelalaka Oct 10 at 23:38
  • How exactly do you mean "reverse engineer" here? Does it matter that the alien's chips are nothing like ours? – bmm6o Oct 10 at 23:43
  • 2
    @kelalaka Okay, I shouldn't have mentioned aliens :-( Replace aliens with NSA employees. – Paul Uszak Oct 10 at 23:49
  • 2
    If "You can enter infinite key /plain text pairs, and observe all of the outputs. " also implies that computation time is unbounded, Then the full lookup table is just an equivalent representation, which you can definately create in unlimited time. – tylo Oct 11 at 10:12
  • 1
    The point of the lookup table example is that the unlimited input/outputs that you grant to the adversary implies that no amount of computation/space is prohibitive to the adversary. In such a model, the adversary can construct table(s) that map plaintext to ciphertexts (and vice versa) for every possible key, and then simply use that table whenever they want to encrypt/decrypt anything. Prediction isn't necessary if they have the codebook. Unlimited computational power is not a realistic scenario, which is why polynomial time/computationally bounded adversaries are usually considered instead. – Ella Rose Oct 11 at 21:28
up vote 2 down vote accepted

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/Rinjdael (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 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 computationally infeasible nowadays.

We could wraps 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 Rinjdael, 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).

  • I know one example that intel hardware leaked the internal memory. Could you give some links to actual modern part? – kelalaka Oct 11 at 8:17
  • I'm struggling with your proof via assumption of 128/256 bit input arguments. The box contains a functional cipher, not a single block construct as in ECB mode. Yes the key is probably 128 - 256 bits as it's a contemporary algorithm, but the input sequence could be anything. Although recall that NSA's SAVILLE key might be 120 bits + checksum. The box might just as well be protecting a short friend/foe challenge as an entire 4K UHD movie. – Paul Uszak Oct 11 at 15:30
  • @PaulUszak: I tried to wrap the idea in the first paragraph. I also extended the explanation to provide a cipher rather than a block cipher. – fgrieu Oct 11 at 15:50
  • 1
    Does citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.5390 help? It's free. – Paul Uszak Oct 11 at 21:09
  • The question seems to be about whether or not it is possible sometimes, not whether or not it is always possible for any arbitrary cipher. – forest 2 days ago

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.

  • it will be very complimentary if you add the number of functions. – kelalaka Oct 11 at 18:01
  • If the construction is using ideally secure components and is designed for efficiency (e.g. no extra layers just to increase the complexity of guessing the design), then it does narrow down the search space a little (though I'm not sure that is in conflict with "uncountable"). – Ella Rose Oct 11 at 19:36
  • @EllaRose Absolutely. No weird stuff just for the sake of it. Just a good quality cipher that we've not seen before. – Paul Uszak Oct 11 at 20:38

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.

  • If you want I can continue to memory and stream cipher, too. – kelalaka Oct 11 at 7:53
  • The answer's argument requires that the polarity of each $a_i$ is secret. With the polarity as given, we can distinguish $f_1$ from $f_2$ with about $n^2/2$ queries. Also, the question is specifically about a black box implementing a cipher, and these $f_1$ or $f_2$ are not ciphers. – fgrieu Oct 11 at 8:05
  • @fgrieu I know it is about block ciphers. As block ciphers composition of boolean functions, I want to start with $f_1,f_2$ to give the intuition. – kelalaka Oct 11 at 8:08
  • I take it that it's trivial to distinguish a block cipher from a stream cipher by looking at the output lengths. – Paul Uszak Oct 11 at 12:55
  • 2
    @PaulUszak even OFB mode of operation? What if the block box is stream cipher and behaves like block cipher? – kelalaka Oct 11 at 13:08

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.