Suppose that I have a block cipher whose key size is 128 bits. but the block length is eight bits. Let E(m’) be an encryption oracle that encrypts by running our “short” block cipher in CBC mode.

How would I write pseudocode for an adversary, A(m), that, given E(m’), can probably decrypt any input in a reasonable amount of time using modern hardware.

My thoughts: The m’ that A passes to E will not be based on the m given to A. But how would I produce a pseudocode for this...?

  • 1
    This sounds a lot like homework. – tylerl Jan 26 '14 at 6:50

The relevant term is codebook. A block cipher is a deterministic permutation: for a given key, it maps input block values to output block values, such that any two distinct input block values map to distinct output block values. The "codebook" is the complete description of that permutation: for each possible input block value, it gives the corresponding output.

One can say that the key-and-algorithm is a compact representation of the codebook, which allows for evaluation of the algorithm over any given input without having to store the complete codebook somewhere. However, if you can, as an attacker, rebuild the codebook, then you can decrypt everything which is encrypted with the same algorithm and the same key: you just have a big look-up table.

With 8-bit blocks, there are only 28 = 256 possible block values, so the codebook is remarkably small: it is just a map of 256 possible values. With the encryption oracle at hand, it is easy to obtain a copy of the complete codebook, e.g. by sending 256 one-byte messages to encrypt to the oracle. There can be details, depending on the following:

  • Does the oracle chooses a random IV, or will it use the IV value that the attacker provides ?
  • Is it a goal to minimize the number of requests to the oracle ? And/or the total number of bytes sent to the oracle ?

There can be interesting analysis here. For instance, if you send an encryption request for a sequence of 256 bytes of value 0, then the encryption result will describe a complete permutation cycle; the IV selects which cycle you get. Laying out a strategy for codebook recovery which minimizes the number of distinct requests, while enforcing a low maximum size on each request, can be challenging -- thus making for good homework subjects.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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