5

I am encrypting a sequence of messages with AES/CTR. For each sequence, I generate a random initial IV, say IV(0). Define IV(i) = MD5(IV(i - 1)) for i = 1, ..., n. Then for each message m(i), I transmit IV(i) . e(key, IV(i), m(i)) over the channel, where . denotes the append operation and e(.) is the encryption function. In other words, the IV of each message is derived from the previous IV by applying a hash function and I transmit the IVs along the cypher text. Therefore, the IVs are distinct (with high probability), but predictable, if you have the previous one.

Is there any problem with this encryption scheme?

Edit:

I have to use CTR, because of some implementation constraints. I want to store the encrypted data on an insecure storage device and decrypt it back, once I retrieved the information. Confidentiality is my top priority. Integrity or malleability of the message are of less importance. In fact, the content of the messages are compressed version of some highly structured files. That is, modifying a few bytes of the cipher text without knowing the whole plaintext ruins the integrity of the message. So, I assume the structure of the file imposes some sort of integrity.

2

With CTR mode, IVs do not have to be unpredictable or random. However, they must be unique for a given key -- reusing an IV is a fatal flaw for CTR mode. It's perfectly fine for the IV to just be i (padded out to the appropriate length); it's even fine for you to call up your mortal enemy and ask them what IV you should use for your message, provided that you check that you haven't previously used the IV; as long as you check that, there is nothing that they can do to compromise your encryption. And given that, you need more than "high probability" -- you need virtual certainty (for GCM, NIST specifies a 2^-32 probability that you ever reuse key and IV, and allowing even that is because that's acceptably unlikely and lets you get away with some randomness). A decent way would be to have the first 32 bits be unique to the sequence of messages (say, a counter value for the sequence), and the next 32 be an index of the message within the sequence, also being a counter value.

Note: This assumes that your IV is only part of the nonces that you encrypt to create a keystream. For instance, a common way to build a keystream is to concatenate a 64-bit counter to a 64-bit IV; in that case, a simple counter for the IV is sufficient. If your implementation takes a 128-bit IV, then it probably computes the keystream as E(k,IV)||E(k,IV+1)||E(k,IV+2)||..., in which case you cannot just increment the IV by one each sequence: that would make message 2's keystream E(k,IV+1)||E(k,IV+2).... If you ever encrypt the same thing with the same key to build two different keystreams, that's bad. With GCM, a typical IV is 96 bits, and you just need to ensure that you don't repeat the 96-bit IVs for any two messages. The point is that if your messages can be up to b bytes long, the first 128-16b bits of your IV should be unique between all messages. 96 bits is common, as is 64 bits.

That said, there's a separate problem -- you have no authentication on your system. That means an attacker who knows what part of a message says can change it to say whatever they want, as long as whatever they want is the same length as the part of the message they know. CTR, like all stream ciphers, is particularly easy to do this with. An AEAD mode like GCM or CCM or EAX is better in almost all cases -- it protects your messages from active attacks. I believe GCM has the same IV requirements as CTR (i.e. used once, but other than that no requirements), and plenty of good implementations are available. (With GCM, IVs are generally 96 bits).

  • Thanks cpast for your nice answer. See my edit for some clarification. One additional question that came to my mind: you said reusing an IV is a fatal. Does it mean it's fatal even if I reuse an IV once in a billion message? Since I am using MD5, the chance of repeated messages is practically zero. But what if it happened once or twice in a billion messages? Does the attacker need a lot of repeated messages to break the encryption? or just a couple of them is sufficient? – Oxy Feb 24 '15 at 0:08
  • 1
    @Oxy If you ever use the same IV for two messages with the same key, that's a fatal error. If you use it for two out of your billion messages, that's not acceptable (it's now a two-time pad). – cpast Feb 24 '15 at 0:35

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.