Good Math, Bad Math

Sorry for the slow pace of the blog lately. I’ve been sick with a horrible
sinus infection for the last month, and I’ve also been particularly busy with work, which have left me with neither the time nor the energy to do the research necessary to put together a decent blog post. After seeing an ENT a couple of days ago, I’m on a batch of new antibiotics plus some steroids, and together, those should knock the infection out.

With that out of the way: we’re going to look at how to get from simple block ciphers to stream ciphers, using the oh-so-imaginatively named modes of operation!

As a quick refresher, block encryption specifies an encryption scheme that operates on fixed-size blocks of bits. In the case of DES, that’s 64 bits. In the
real world, that’s not terribly useful on its own. What we want is something called
a stream cipher: a cipher that’s usable for messages with arbitrary lengths. The way to get from a block cipher to a stream cipher is by defining
some mechanism for taking an arbitrary-sized message, and describing how to break it into blocks, and how to connect those blocks together.

Modes of operation are formal descriptions of the way that you
use block encryption on a message that’s larger than a single block. Modes of operation (MOOs) are critical in making effective use of a block cipher. Of course, there’s always a tradeoff in things like this: you have to choose what properties of your encrypted communication you want to protect. Particularly for DES encryption, the standard MOOs can provide confidentiality (making sure that no one can read your encrypted communication), or integrity (making sure that your communication isn’t altered during transmission), but not both.

To give you a quick and foolishly simple example of that tradeoff, we can consider a real-life example of a simple mode of operation, called the electronic codebook (ECB). In the ECB MoM, you encrypt each block separately, and then just concatenate the results together. Everyone who does crypto knows that ECB is incredibly stupid; no one seriously uses it. The only case I recall hearing of anyone actually using ECB was a multiplayer online role-playing game,
where they encrypted the traffic between players and the game server using ECB.
So every time the player did something, it sent a message to the server, and the server sent back a message telling it how to respond.

For performance reasons, games like this tend to do a lot of stuff on the
player’s computer. So, for example, when a player gets into a fight with a monster,
the fight was mostly handled on the players computer, and when it was over, it sent
a message to the server, either saying “player died”, or “player killed
monster”. Since they were using ECB, a player watching network traffic
could easily notice that whenever he killed a type-A monster, his would sent a particular bag-o-bits to the server. That b-o-b was always exactly the same – so while they didn’t know exactly what was in the message, they were able to
tell that the way the game told the server that the player killed a monster was
to send those bits.

This was, naturally, exploited by clever players, who wrote programs sending
thousands of copies of that b-o-b to the server, racking up credits for killing thousands of monsters. Since it was a message that was set up to be one block long, and it was using ECB, that block always encrypted to the same ciphertext block – so they knew how to tell the server that they killed another monster. They
had no idea of what was actually inside the block – no idea of what data specifically was being transmitted to say “Player A killed an Orc”. But because
of the combination of ECB with the way in which the cipher was being used, they
formed a very effective exploit.

That’s an example of something called a replay attack, where you try
to violate the integrity of the message. Encryption isn’t only about hiding the
message plaintext from prying eyes, but about protecting a communication
channel
from interference by intruders. In the case of this MMORPG, the
attackers compromised the communication channel without decrypting the
message. They had no idea exactly what the batch-o-bits that they were transmitting
said, but they had a good idea of what they meant, and they were able to
intrude on the communication channel, adding messages that the receiver assumed
were legitimate, because they matched the expected encryption. This kind of attack
is called a replay attack. For this application, the ECB did a decent job
of protecting confidentiality (no one figured out what the specific contents of the
message were, but they were able to figure out what it meant, so it didn’t even do
that terribly well), but it did a lousy job with integrity (it was easy to
introduce spurious content to the communication channel without being detectable by
the sender or receiver.)

So, moving on, the way to improve the performance of the block cipher is
to use a mode of operation that doesn’t just blindly concatenate things.

The Counter (CTR) MoO

(I’ve been alerted by a reader that I made a major mistake in my description of the CTR mode of operation. Since I don’t have time to correct it while I’m at work, I’m posting this warning: the information about CTR is incorrect. I’ll fix it this evening.)

The simplest MoO beyond ECB is to just add a counter to the process. So, you
XOR your plaintext block with a counter value, and then send it through the
encryption. For a sequence of blocks, you increment the counter for each block. So
a single block encoded multiple times will encode once exclusive-OR’ed with
“1”, once with “2”, etc. Repeated blocks won’t look repeated in the ciphertext.

Below is a very simple fragment of pseudo-python that demonstrates
the basic idea of this; next to it is a data-flow diagram illustrating
the same thing. For each of the modes of operation I describe below, I’ll provide similar pseudo-code and diagrams.

def EncryptWithCTR(blocks, ctr, key):
  for b in blocks:
    encrypted = encrypt(key, b ^ ctr)
    ctr = ctr + 1
    output(encrypted)

Of course, just using integers that way isn’t ideal. It’s hard to detect,
but it’s a natural thing to try. What’s better is to use a counter function. A counter function is a function F from the natural numbers
to a stream of bits the size of one block. So instead of exclusive-ORing
cleartext block #I with “I”, you XOR it with F(I). If your counter function
is pseudo-random, this can be very effective. Despite the fact that this is
potentially a significant benefit, most implementations that I’ve seen using
CTR just use a plain counter – the only variation is that it often doesn’t start the counter at 0 or 1.

Consider how the replay attack would play out with CTR (or any of the others
below). People monitoring the network would be able to detect that a single encoded block would be sent each time a player killed a monster. But they wouldn’t know what the specific payload of the message was, and they wouldn’t be able to guess how to encode a copy of the block in a way that would work.

One of the nice properties of CTR is that it’s easy to parallelize: if you know the counter function, then you can encrypt/decrypt blocks in isolation without
needing any information from a previous block. So you can encrypt/decrypt blocks
3, 4, 5, and 6 at the same time: you know that the key for block 5 is just the
basic key XOR counter(5).

Of course, that parallelization is a curse as well as a blessing. Someone
trying to crack your system can also parallelize, and try decrypting multiple blocks at the same time. Once you’ve got a few blocks broken, getting the rest
becomes relatively easy, and you’ve got lots of different blocks, some of which may (by chance) be easy to break by brute-force methods.

Feedback Modes of Operation

i-6ae9d659000c03c6ee8da8c3c1e7555d-cbc.png

Most of the common modes of operation are based on some form of feedback. You
start with an initial block of random bits called an initialization vector
(IV), and you encrypt the block XORing the IV somewhere in the process of
generating the ciphertext of the first block. Then for each successive block, you
replace the IV with some kind of output from the previous block.

Cipher-block chaining is a simple feedback-based MoO. Basically, you start
with your agreed-upon block of bits in the initialization vector (IV). For the
first block, you exclusive-OR the plaintext with the IV, and then perform the
block encryption. The output ciphertext of the first block is then used as the
IV for the second block; the IV of the third block is the output ciphertext of the second, and so on. So each block is scrambled by mixing it with the ciphertext of the previous blocks. This also avoids the problem of the game, because the same plain text message encrypts to different ciphertext each time.

def EncryptWithCBC(blocks, iv, key):
  feedback = iv
  for b in blocks:
    inblock = b ^ feedback
    encrypted = encrypt(key, inblock)
    feedback = encrypted
    output(encrypted)

The big problem with CBC is that it’s weak against many kinds of brute-force
attacks. You can’t parallelize encryption using CBC: you need to finish encrypting each block before you can encrypt the next; but for decrypting, you can
try to decrypt multiple blocks; and once you’ve broken two adjacent blocks,
you’re pretty much wide-open.

i-4981c34166621c4b61a8297cd288ed81-cfb.png

A slight variation is CFB; it’s just a minor reshuffle of the
order of things. In CBC, we XORed the plaintext of the message with an IV,
and then did block encryption on that to produce the ciphertext. In CFB,
to produce the ciphertext, we do the block encryption on the IV, and then XOR the result with the plaintext. The ciphertext of block N is then exclusive-or’ed
with the previous IV to create the IV for block 5.

def EncryptWithCFB(blocks, iv, key):
  feedback = iv
  for b in blocks:
    encrypted = encrypt(key, feedback)
    out = encrypted ^ b
    feedback = out
    output(out)

CFB has pretty much the same vulnerabilities as CBC.

i-644daa121f2135d57771006c25e666db-ofb.png

Output feedback (OFB) is yet another variation on the same theme. The only difference is that the input to block N+1 is the output of the block cipher
from step N, before it’s exclusive-OR’ed with the plaintext for step N.
The interesting thing about OFB is that the plaintext doesn’t affect the output of the block cipher itself: the block cipher encrypts the combination of the key and
some feedback from the previous block – the plaintext gets exclusive-OR’ed afterwards.

def EncryptWithCFB(blocks, iv, key):
  feedback = iv
  for b in blocks:
    encrypted = encrypt(key, feedback)
    feedback = encrypted
    out = encrypted ^ b
    output(out)

These are all modes that focus on confidentiality rather than integrity. Integrity protection is more recent innovation, and it’s more complicated. In
later posts, I’m going to talk a bit about the cryptanalysis and attacks that are used against block ciphers, and how they interact with different modes of operation. From there, we’ll be able to see why these modes don’t protect integrity, and show how we can build modes that focus on integrity.

Comments

  1. #1 Nate
    September 15, 2008

    Mark, your description of counter mode is completely wrong. The plaintext input is not mixed with the counter before encryption. Counter mode means encrypting only the counter itself, then XORing the cipher output with the plaintext. In other words, it turns a block cipher into a stream cipher.

    Your latter description (i.e., “counter function”) sounds like you’re thinking of GCM (Galois Counter Mode).

    As I said before:

    I like your blog overall, but this series on crypto is a bit dangerous for amateurs. The devil is in the details, and it’s very easy to make a critical mistake. So while it’s good to give people an intro, I suggest a big warning letting them know that there are some dangerous assumptions lurking below the surface, and that they should always use well-reviewed implementations and protocols (i.e. SSL) rather than rolling their own for pure ego reasons.

    Please consider posting a correction to your blog to avoid misleading people.

  2. #2 Mark C. Chu-Carroll
    September 15, 2008

    Nate:

    Thanks for the correction. I’ve marked it as incorrect, and I’ll fix it after work, when I have some time.

    I disagree with the idea that talking about crypto is “dangerous for amateurs”. It’s dangerous for amateurs to think that they can go off and be cryptographers without bothering to actually study crytography – but for a series of posts that just tries to explain “what is this stuff?”, I don’t see the danger.

    I don’t pretend to be an expert on crypto, nor do I represent my explanations as anything more than very high-level intuitive descriptions to give people a clue of what’s going on.

    I don’t think that anyone is going to mistake this basket of blog posts for a serious primer on how to become a cryptographer, or how to build and analyze cryptosystems, any more than I think that people are going to think that they’re group theorists because they read my group theory posts.

  3. #3 Niall
    September 15, 2008

    The series on cryptography has been very interesting so far, thank you for the time and effort you are putting into it. I am just barely keeping up with whats going on :) The modern crypto techniques are amazing, but I still cant help wondering about security and attacks against mysterious systems. Most of the modern encryption algorithms are very well studied. How difficult is it to take a piece of encrypted message, that has been encrypted by an entirely unknown system, and break it? Might security through obscurity work if I came up with my own methods? Assuming the encryption and decryption processes are completely unknown, Id love to hear your speculation on the strength of systems. Would modern cryptographers just rip my encryption apart like it’s wet toilet paper?

  4. #4 Anonymous
    September 16, 2008

    One of the basic assumptions of information security is that the sufficiently motivated attacker WILL know your algorithm. Bribes, theft, blackmail, court orders and incarceration for contempt of court, whatever it takes.

    On top of that they probably have an idea of what you’re sending. Historically that might have been “From: X; To: Y, etc.”, today it might be a compression header followed by a compressed word document header. Worser case, they’ll have samples of your plaintext. Worserer case, they’ll have samples of plaintext and corresponding ciphertext. Worst case, they can feed arbitrary plaintext into your system and see what pops out.

    So your security has to rest in your keys. Nothing but your keys. Obscurity and misdirection(*) will help protect you from the casual attacker, but can’t be relied upon. That’s why you have to get the algorithm right -and- pick good keys for that algorithm. That’s extremely hard to do on your own.

    (*) A good example of misdirection are the id cards that use a barcode that’s behind a plastic strip that’s transparent to IR, opaque to visible light. Casual attackers will think it’s a magnetic strip.

  5. #5 Chris
    September 16, 2008

    (hmm, why would I be anonymous earlier?)

    My intro to crypto class (at the grad level) had a few “here, crack this” problems, but they were pretty restricted since it was more theory than practice. Lots and lots of number theory. :-) We only did cryptanalysis problems that could be done by hand in a reasonable amount of time.

    Anyway, it was basically a process of looking for structure that gave us insight into the cipher, after making assumptions about the ciphertext (e.g., that it’s simple English text). Count the occurance of each ciphertext symbol — a distinctive pattern of spikes could indicate a simple substitution cipher.

    Didn’t work? Sort the ciphertext symbol into bins. You might see those spikes in each bin when you use, oh, 7 bins. That indicates a substitution cipher with 7 rotors (or whatever they’re called — it’s been years).

    Still didn’t work? Try looking for the structure you see with a Playfair cipher. On and on.

    I don’t know how you distinguish between, e.g., DES vs. AES vs. some new cipher developed by the Russians. Hopefully we’ll see that in later posts.

  6. #6 John Kelsey
    September 18, 2008

    Your discussion of the security issues with CBC mode don’t make much sense to me. In general, all the chaining modes are vulnerable to brute force attacks. That’s just a consequence of the fact that given the ciphertext and the key, you can decrypt to get the plaintext.

    Were you trying to get at the idea that CBC mode doesn’t parallelize well on the encryption side? If you give me 100 processors, I still can’t do CBC encryption of a single long message any faster than with one processor. Or something else?

    Also, your text description of CFB mode is confused. Your code and diagram look right (the ciphertext from encrypting plaintext K should be encrypted to generate the thing that gets XORed into plaintext K+1), but the text is messed up.

    And one nitpick: Your OFB code (it looks right otherwise) is titled EncryptWithCFB.

    CFB also allows variants in which it encrypts only a fraction of a block at a time, but I’m not sure how important that is. (OFB was originally defined with such a variant, if I recall correctly, but there’s a big security problem with using that variant!)

  7. #7 mcow
    September 19, 2008

    So, if I’m reading this right, OFB is essentially a “simulated” one-time pad. Instead of using a truly random pad, you use the block cipher as a pseudorandom number generator and build the pad from that. Then you can rebuild the pad as long as you have the seed (the key and the IV).

  8. #8 WuffenCuckoo
    September 20, 2008

    “Particularly for DES encryption, the standard MOOs can provide confidentiality (making sure that no one can read your encrypted communication), or integrity (making sure that your communication isn’t altered during transmission), but not both.”

    (Naive user) Why not encrypt once to provide confidentiality and then again (different key) to ensure integrity? When decoding, first decryption ensures preserved integrity and the second, preserved confidentiality.

    In the same vein,does successive (serial)encryption offer any advantage in confidentiality? How does successive encryption (different keys)scale? Is it just as easy, twice as difficult . . . to decrypt?

  9. #9 Barry Leiba
    September 26, 2008

    This series has been included in the 40th Carnival of Mathematics. Come check out the others.

  10. #10 Helger Lipmaa
    September 28, 2008

    The CTR mode description is still incorrect. What you do in CTR mode is to encrypt successive integers ctr, ctr+1, ctr+2, … and then XOR the plaintext blocks with those ciphertexts. Decryption is just the opposite: you peel off the encryption by XORing the ciphertext with the encryptions of ctr+i.

    A requirement for security is that the same ctr+i is never used twice with the same key. In practice you can imagine using one of the two next methods:

    – Before encrypting a plaintext, choose a random ctr,
    encrypt with that and transmit the new ctr together with
    the ciphertext. If the space from where you choose
    counters is large enough then the probability that you
    use the same ctr+i twice is negligible.

    – The encrypter is stateful, that is, he remembers ctr.
    ctr is still a part of the ciphertext, but after
    encryption is done, ctr is increased to the next free slot
    and stored.

    As for counter function, one usually just increases ctr by one.

    http://www-08.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ctr/ctr-spec.pdf might be helpful.

  11. #11 Jack
    March 25, 2010

    How would you explane the basic operations in cryptography?

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.