Home > cipher, state machine > The Cipher Black Box

The Cipher Black Box

This is how the cipher works: a plaintext is fed in to the “Black Box” and, based on a set of unknown parameters P, is enciphered by an unknown process in the box into the ciphertext, which is written onto the folio.

The internal mechanism of the Black Box is unknown. The only information we have is the output ciphertext (but we have a lot of it).

What strategies can we employ to discover how the internal mechanism of the Black Box works? What are the input parameters to the cipher? Can we avoid having to find out about the mechanism, and directly reverse the cipher, so yielding the plaintext from the ciphertext?

If we could “prod” the Box as enciphering was taking place (e.g. by twiddling one of the input parameters Pi), then by observing the output ciphertext, we could start to build a theory about how the cipher works.

Suppose we devise a candidate cipher that, from a sequence of random plaintext letters, and using a set of parameters we choose, generates a chosen line of VMs text exactly. Mathematically:

ciphertext = C(plaintext,P0…Pi)

where C is the cipher function. We can surely find a function that satisfies these conditions: some sort of State Machine is perhaps most appropriate. When twiddling one of the parameters Pi, and measuring the change in the ciphertext, we are able to calculate the partial derivative of C with respect to Pi:

δC/δPi = Δ(ciphertext)

If the variation on the ciphertext produces new ciphertext that is compatible with the rest of the ciphertext in the VMs, then this would suggest that Pi is a good parameter (i.e. that it is a candidate for retention in the candidate cipher). If, on the other hand, the variation produces invalid new ciphertext, the parameter is poor, and is a candidate for removal from the candidate cipher.

Potential algorithm:

  1. Create a state machine containing a cipher C that takes (many) Parameters P
  2. The state machine parameters are adjusted so that a (random) plaintext input string produces a valid sequence of  VMs ciphertext
  3. Each parameter is varied slightly in value, and the state machine asked to reprocess the plaintext to produce new ciphertext
  4. The similarity of the new ciphertext is compared with the VMs corpus
  5. The parameter in question is demoted or promoted in weight
  6. Once the effects of all parameters have been examined they are graded by weight
  7. Good parameters are kept, poor ones discarded
  8. Develop an overall score for the state machine, based on a suitable metric
  9. Memorize this state machine if it has the best score so far
  10. Go to step 1, but now with the reduced set of parameters

This process is repeated for many different trial state machines, and the best memorized.

Inverting the Cipher

TBA

Advertisements
  1. Philip
    March 4, 2010 at 10:54 am

    Hi,
    it seems that you transform the problem into an optimization problem, where the search-space is the set of all possible algorithms. But algorithms which can be represented by state machines are only a subset (a common example for this: a FSM cannot mirror an input string of arbitrary length). A Turing machine would – from a theoretical standpoint – solve this issue, but I don’t see how this optimization problem can be constructively solved. BTW: what you describe seems to be a genetic algorithm.

    Cheers,
    -Philip

    • JB
      March 4, 2010 at 5:33 pm

      Hi Philip – many thanks for the comment. You are right – the algorithm search space is “large” (i.e. semi infinite). I had in mind the sort of processes that are typically used to encipher plaintext, which are generally quite simple manipulations that involve as input, say, a lookup table and the current latest character(s). Rather than a GA, the idea was more to do with a stochastic “greedy” algorithm that starts with very many degrees of freedom and successively reduces them (a GA tends to have a fixed length or number of parameters).

      Having said that, this is a very long shot and highly unlikely to be successful. It was more of a gedanken experiment.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: