Archive for the ‘state machine’ Category

The Cipher Black Box

March 4, 2010 2 comments

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