So, as it turned out, I made a major screwup in my post earlier today on modes of operation. Rather than just edit the post, I'm adding a new post with the corrected description of the counter mode, and a bit of explanation. I figure that if I screw up badly, it's more honest to make a second post explaining the error than it is to just correct it and pretend that all was well.
What I got wrong was the order in which things happen. In the counter mode, you encrypt the counter using the key, and then you exclusive-or the result of that with the plaintext to get the ciphertext. The plaintext never enters the block cipher; the block cipher just produces a complex and random looking block of bits which are then used to obscure a block of plaintext.
What I said in the original post was that you exclusive or the plaintext with the counter, and then run it through the block cipher. In my screwed up version, the plaintext is being put through the block cipher mechanism; in the correct version, it's not. Below is some of my psuedo-python showing my screwed up CTR mode, and the (hopefully) correct CTR mode. I've also included a diagram of the correct CTR mode.
def EncryptWithMarksScrewedUpCTR(blocks, ctr, key):
for b in blocks:
encrypted = encrypt(key, b ^ ctr)
ctr = ctr + 1
output(encrypted)
def EncryptWithRealCTR(blocks, ctr, key):
for b in blocks:
e_ctr = encrypt(key, ctr)
encrypted = e_ctr ^ b
output(encrypted)
ctr = ctr + 1
This can make a big difference in the effectiveness of the cipher against various attacks. I'm not going to get into details now, but over the course of future posts, I hope that I'll be able to make it clear why changes like this can have huge impacts on the security and quality of a cipher.
Technology
Comments
You still need to include an IV in with the counter. If you use the same counter again for a different stream, it is easy to do attacks by just xoring the two streams together.
Counter mode basically turns a block cypher into a stream cypher. With that, it is important to either never reuse the counter, or never reuse the key. That's commonly done by either xoring the counter with an IV the size of the block, or setting say the upper half of the block to the IV, and the lower half to the counter.
Posted by: David Brown | September 15, 2008 11:16 PM
Thanks for updating your post. David Brown is right -- without an IV, you're going to generate the same keystream on multiple messages. This means CipherText1 XOR CipherText2 = PlainText1 XOR PlainText2, revealing a lot of information about your plaintext. Are you going to revise this again?
In my last comments, I suggested that you recommend your readers use standard protocols like SSL or password hashing algorithms like FreeBSD-MD5 or OpenBSD-Blowfish. The danger is that they'll read your posts, assume they understand enough, and then implement their own versions, recapitulating all the security flaws we've learned about in the research world. As evidence of this, consider that if you fix your post to add the IV, that will be the second important flaw you've accidentally included in describing only a single mode of operation (counter mode). Wouldn't a disclaimer help emphasize how fragile this stuff is?
I make my living finding and fixing flaws in embedded and systems software, especially as they pertain to crypto. So while I appreciate increasing the supply of work, it would be good to issue a warning instead. :)
Consider fiascos like this "rainbow tables" set of comments, where web programmers attempt to reinvent password hashing rather than just reusing the FreeBSD or OpenBSD approaches. There are 105 comments to a very informative post that warns of the dangers of trying to reinvent this, and nearly all the commenters are doing exactly that!
Posted by: Nate | September 18, 2008 12:38 PM
For those of us who are learning, what is an IV?
Posted by: Rob Britton | September 22, 2008 12:52 PM
Ah, oops, hadn't read that far in the older post. Sorry!
Posted by: Rob Britton | September 22, 2008 12:54 PM
Rob:
The "IV" is an initialization vector. It's a collection of random bits.
The idea is that you want to "prime the pump"; that is, you don't want an adversary to ever see a simple sequence of stuff that lets them infer much about what you're doing.
If you use a simple counter, then effectively, you've got a message encoded with DES(1)xor(plaintext),DES(2)xor(plaintext), etc. Every message will look roughly like that. If your adversary somehow figures out what you're doing, then he can just do the same DES(1), DES(2), etc., computation, and have an easy crack to your key.
The IV breaks that. An adversary trying to break your encryption can't just try encrypting "1,2,3" with different passwords, and see if he gets anything that makes sense out of your message. He needs to also guess the IV.
As a computer scientist, I tend to have a somewhat odd way of looking at things, which has annoyed a few cryptographers who read this blog. My understanding of counter mode says
that the counter is a function F, where you use F(N) as an input value for block N.
In terms of functional representations of things, which is the way I think of them, the use of an IV is equivalent to a particular counter function F.
In the diagram of the mode above, you can see that I use "counter(1)", "counter(2)" as inputs to the block cipher. counter(n) could be (n xor IV) if you wanted; it works out as equivalent.
Posted by: Mark C. Chu-Carroll | September 22, 2008 1:11 PM
I would just like to say that I write software for a living, I have a computer science degree from a decent school, I read this blog and find it to be engaging and educational (especially these cryptography-related posts), and I would never roll my own security code. I'd like to think that most people interested in cryptography and security enough to read these blog posts have an appreciation for how hard real security is. I've been interested in this stuff for a while now and I've heard that message over and over again--the security community does an excellent job of communicating that point.
This blog provides some of the most lucid descriptions of various concepts that I've encountered. I'm learning and I love that.
I'm sure there are other readers like me. Keep up the good work.
Posted by: frankzappa | September 25, 2008 6:39 PM
You indeed have an IV. However, the counter and the IV need not be mutually exclusive. Since often the first thing done is to XOR the IV against the counter, you can actually just choose an IV and just start your counter from that. It's essentially the same thing, though, so if you expand your definition of a "counter", your notation works.
Posted by: B-Con | October 2, 2008 10:44 PM
Hi Mark. Sorry for the late comment, I just revisited this thread. Even with your revised comment, the reason you give is incorrect.
What you're saying is that the IV in counter mode prevents a known plaintext attack. That is, you're saying that knowing that the ciphertext is "DES-Encrypt(counter, key) XOR plaintext" gives the attacker a crib, since they can brute-force the key in the forward direction and see if the resultant plaintext makes sense.
This is not the reason for using an IV. The average effort required to perform this attack on DES, assuming the key is randomly chosen, is 2^63. For AES-128, it is 2^127. This is the same effort required to brute-force a single block encrypted with the cipher in ECB mode. Any cipher that is vulnerable to a known plaintext attack is already broken and should not be used. Neither DES nor AES is subject to a known plaintext attack.
The actual reason the IV should be different each time the counter is restarted is because without it, you produce the same keystream multiple times. This is fatal for a stream cipher since the keystream itself can be extracted for any portions of known plaintext.
Say you're using this for packet encryption and you don't have an IV. Once I see the encrypted Packet1 and know some header fields, I know the keystream at those points. Now I can decrypt any packet you send by just XORing those same points with the keystream.
Since an IV makes the keystream different (even though the counter is restarted), it would prevent this attack.
Posted by: Nate | November 12, 2008 4:22 PM
I forgot one more thing. Your assumption that the IV helps prevent a known plaintext attack is based on the IV being secret. An IV is never secret, and any protocol that claims it should be immediately raises red flags.
Posted by: Nate | November 12, 2008 4:26 PM