{"id":682,"date":"2008-09-15T10:13:04","date_gmt":"2008-09-15T10:13:04","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/09\/15\/modes-of-operation-in-block-cryptography\/"},"modified":"2008-09-15T10:13:04","modified_gmt":"2008-09-15T10:13:04","slug":"modes-of-operation-in-block-cryptography","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/09\/15\/modes-of-operation-in-block-cryptography\/","title":{"rendered":"Modes of Operation in Block Cryptography"},"content":{"rendered":"

Sorry for the slow pace of the blog lately. I’ve been sick with a horrible
\nsinus 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<\/em> knock the infection out.<\/p>\n

With that out of the way: we’re going to look at how to get from simple block ciphers<\/a> to stream ciphers, using the oh-so-imaginatively named modes of operation<\/em>!<\/p>\n

As a quick refresher, block encryption specifies an encryption scheme that operates on fixed-size blocks of bits. In the case of DES<\/a>, that’s 64 bits. In the
\nreal world, that’s not terribly useful on its own. What we want is something called
\na stream cipher<\/em>: 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
\nsome mechanism for taking an arbitrary-sized message, and describing how to break it into blocks, and how to connect those blocks together.<\/p>\n

Modes of operation<\/em> are formal descriptions of the way that you
\nuse 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<\/em> (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.<\/p>\n

<\/p>\n

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,
\nwhere they encrypted the traffic between players and the game server using ECB.
\nSo 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.<\/p>\n

For performance reasons, games like this tend to do a lot of stuff on the
\nplayer’s computer. So, for example, when a player gets into a fight with a monster,
\nthe fight was mostly handled on the players computer, and when it was over, it sent
\na message to the server, either saying “player died”, or “player killed
\nmonster”. Since they were using ECB, a player watching network traffic
\ncould 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
\ntell that the way the game told the server that the player killed a monster was
\nto send those bits.<\/p>\n

This was, naturally, exploited by clever players, who wrote programs sending
\nthousands 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<\/em> how to tell the server that they killed another monster. They
\nhad 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
\nof the combination of ECB with the way in which the cipher was being used, they
\nformed a very effective exploit.<\/p>\n

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

So, moving on, the way to improve the performance of the block cipher is
\nto use a mode of operation that doesn’t just blindly concatenate things.<\/p>\n

The Counter (CTR) MoO<\/h3>\n

(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.)<\/em>
\n<\/p>\n

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

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

\ndef EncryptWithCTR(blocks, ctr, key):\nfor b in blocks:\nencrypted = encrypt(key, b ^ ctr)\nctr = ctr + 1\noutput(encrypted)\n<\/pre>\n
 Of course, just using integers that way isn’t ideal. It’s hard to detect,
\nbut it’s a natural thing to try. What’s better is to use a counter function<\/em>. A counter function is a function F from the natural numbers
\nto a stream of bits the size of one block. So instead of exclusive-ORing
\ncleartext block #I with “I”, you XOR it with F(I). If your counter function
\nis pseudo-random, this can be very effective. Despite the fact that this is
\npotentially a significant benefit, most implementations that I’ve seen using
\nCTR just use a plain counter – the only variation is that it often doesn’t start the counter at 0 or 1.<\/p>\n
<\/strike><\/p>\n
 Consider how the replay attack would play out with CTR (or any of the others
\nbelow). People monitoring the network would be able to detect that a<\/em> 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.<\/p>\n
 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
\nneeding any information from a previous block. So you can encrypt\/decrypt blocks
\n3, 4, 5, and 6 at the same time: you know that the key for block 5 is just the
\nbasic key XOR counter(5).<\/p>\n
 Of course, that parallelization is a curse as well as a blessing. Someone
\ntrying 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
\nbecomes relatively easy, and you’ve got lots of different blocks, some of which may (by chance) be easy to break by brute-force methods.<\/p>\n
Feedback Modes of Operation<\/h3>\n
\"cbc.png\"<\/p>\n
 Most of the common modes of operation are based on some form of feedback. You
\nstart with an initial block of random bits called an initialization vector<\/em>
\n(IV), and you encrypt the block XORing the IV somewhere in the process of
\ngenerating the ciphertext of the first block. Then for each successive block, you
\nreplace the IV with some kind of output from the previous block.<\/p>\n
 Cipher-block chaining is a simple feedback-based MoO. Basically, you start
\nwith your agreed-upon block of bits in the initialization vector (IV). For the
\nfirst block, you exclusive-OR the plaintext with the IV, and then perform the
\nblock encryption. The output ciphertext of the first block is then used as the
\nIV 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.<\/p>\n
\ndef EncryptWithCBC(blocks, iv, key):\nfeedback = iv\nfor b in blocks:\ninblock = b ^ feedback\nencrypted = encrypt(key, inblock)\nfeedback = encrypted\noutput(encrypted)\n<\/pre>\n
 The big problem with CBC is that it’s weak against many kinds of brute-force
\nattacks. You can’t<\/em> parallelize encryption using CBC: you need to finish encrypting each block before you can encrypt the next; but for decrypting, you can
\ntry to decrypt multiple blocks; and once you’ve broken two adjacent blocks,
\nyou’re pretty much wide-open. <\/p>\n
\"cfb.png\"<\/p>\n
  A slight variation is CFB; it’s just a minor reshuffle of the
\norder of things. In CBC, we XORed the plaintext of the message with an IV,
\nand then did block encryption on that to produce the ciphertext. In CFB,
\nto produce the ciphertext, \twe 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
\nwith the previous IV to create the IV for block 5.<\/p>\n
\ndef EncryptWithCFB(blocks, iv, key):\nfeedback = iv\nfor b in blocks:\nencrypted = encrypt(key, feedback)\nout = encrypted ^ b\nfeedback = out\noutput(out)\n<\/pre>\n
 CFB has pretty much the same vulnerabilities as CBC.<\/p>\n
\"ofb.png\"<\/p>\n
 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
\nfrom step N, before<\/em> it’s exclusive-OR’ed with the plaintext for step N.
\nThe 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
\nsome feedback from the previous block – the plaintext gets exclusive-OR’ed afterwards.<\/p>\n
\ndef EncryptWithCFB(blocks, iv, key):\nfeedback = iv\nfor b in blocks:\nencrypted = encrypt(key, feedback)\nfeedback = encrypted\nout = encrypted ^ b\noutput(out)\n<\/pre>\n
 These are all modes that focus on confidentiality rather than integrity. Integrity protection is more recent innovation, and it’s more complicated. In
\nlater 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[84],"tags":[],"class_list":["post-682","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-b0","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/682","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=682"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/682\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=682"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=682"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=682"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}