Introduction to Cryptography I: Encryption (Pt. 4 – Block Ciphers/Modes of Operation)

Hi everyone. @lemony-cricket here. Let’s learn about block ciphers and modes of operation! We’re nearing the end of our introduction to encryption, but don’t be sad! I’m really excited to get into digital signatures and hashes and everything else cryptography has to offer!



Rocket graphic extracted from this CC0 image from OpenClipart-Vectors on Pixabay.


Retrospective

It’s been almost a month since the last installment of Introduction to Cryptography. Unfortunately, nobody actually completed the activity last time, which gives us not a lot to talk about in this retrospective section! An honourable mention goes to @procrastilearner, who contributed a good question to which I thoroughly enjoyed responding.

Last time we learned about stream ciphers. That was our first introduction to the marvelous world of modern encryption. That stuff is actually in our web servers and browsers making ’em tick! Neat, eh?

Stream ciphers are simple and convenient. They tend to have extremely fast hardware implementations. They don’t require padding (we’ll define that later). They have one mode of operation; they generate a keystream, which is then used as if it were a one-time pad. For better or for worse, that’s all they can do.

Block ciphers and their modes of operation

the most versatile form of symmetic-key encryption

Block ciphers, on the other hand, are a bit more powerful, but a bit more complicated as well. For example, in most modes, block ciphers operate directly upon the plaintext rather than generating a keystream. They also require proper paddingd1 at the end of the plaintext unless it exactly matches up with the block size.

It’s also not enough to know which cipher you’re using; you also need to choose a mode of operationd2. These modes of operation are public and widely standardised and work with any block cipher available. Let’s take a look at some of these modes.

Electronic codebook (ECB)



By WhiteTimberwolf on Wikimedia Commons. Public domain.


The diagram above illustrates the electronic codebook, or ECB, mode of operation. It’s called “electronic codebook” because it is actually a really large substitution cipher, like the Caesar shift. The differences are that it’s more of a “scramble” than a “shift,” and it has a much, much larger alphabet, with each possible permutationd3 of the block size representing a different “letter.”

In this most basic mode of operation, the same key is used to encrypt every block of plaintext. That means that if any of the blocks are exactly the same, those blocks in the ciphertext will also be exactly the same. Now, if you’re starting to get a bad vibe about this, good. You’re learning!

It’s true that ECB has some severe flaws, and for this reason, it is almost never used except as an example of how block ciphers work, since it’s really the most bare-bones mode available. You might already have an idea about what the flaws are, but we’ll save that discussion for later.

Cipher block chaining (CBC)



By WhiteTimberwolf on Wikimedia Commons. Public domain.


No, not “blockchaining.” Actually, there is a slight similarity here! Blockchains are so-called because each new block includes a mathematically indisputable link to the previous block. Similarly, while encrypting in CBC mode, we combine the ciphertext from the previous block with the plaintext of the current block before the encryption operation, using a bitwise exclusive-or (XOR) operation.

CBC thereby solves the problem with ECB since each block depends not only on the key, but also on the previous ciphertext. This effectively breaks the ability to observe patterns in the ciphertext and serves to increase a desirable property we call diffusiond4.

But what’s that “initialisation vectord5” all about? Well, since there is no previous ciphertext to combine with the plaintext for the first block, a random value must be used instead. The random part is actually pretty important; the IV doesn’t have to stay secret, but it cannot be predictable or else it opens the door for certain attacks.

An interesting quirk of CBC is that even though the IV doesn’t have to stay secret, it’s actually not even necessary to tell the decrypting party what it is. All you have to do is pad the first block with arbitrary, disposable data before you encrypt it… then just throw it away on the other side. This works because the subsequent blocks rely only upon the ciphertext, not the plaintext. So, decrypting with the wrong IV will result in the first block being mangled, but every block after it will be fine! This trick is actually widely accepted and used in at least one prominent encryption standard, TLS 1.1, where it was deployed to fix a prior vulnerability.

Counter (CTR)



By WhiteTimberwolf on Wikimedia Commons. Public domain.


The counter mode takes a different approach. Instead of taking the plaintext as input like the other modes we’ve seen so far, it splits the input between a nonce and a counter. The counter is incremented with each block number, but the nonce stays the same for the entire session and should never be used again with the same key. Once the output is generated, it’s combined with the plaintext with a XOR operation…

Hey! Haven’t we seen this before?! Yes! One of the coolest things about cryptography is that since most of the algorithms are built around similar principles and have similar properties, they can often be safely used to construct substitutes for one another. An algorithm built for use as a stream cipher is often perfectly suitable for use as a CSPRNGd6. As @procrastilearner found out in my reply to his question, we can even use a hashing algorithm to generate a secure (if rather slow) stream cipher. It’s not unheard of for certain implementations to re-use existing primitivesd7 in these sorts of ways, especially in embedded systemsd8 where there may be extremely restrictive space and/or memory constraints.

Counter mode is a way to turn a block cipher into a stream cipher. There are other modes like this too, like cipher feedback (CFB) and output feedback (OFB), and others which do more advanced things, but I think we’ve reached a sufficiently advanced point and this is an introduction to cryptography series, after all.

Interactive exercise

Below are two images; the one on the right is an encrypted version of the one on the left.



My continuous undying thanks to @saywha, who made this monster for me!


Woah! That doesn’t seem right. Take your best guess at what went wrong here and explain how you came to that conclusion. 100% upvotes await all thoughful answers!

Definitions

From my personal knowledge and experience unless otherwise noted.

  1. padding: extra data which must be used to “fill up” the last block when using a mode of operation which operates directly upon blocks of plaintext.
  2. mode of operation: the combination of inputs, outputs, and intermediate steps used with a block cipher to allow it to operate on data sets larger than the block size.
  3. permutation: a distinct arrangement of a set of items. For example, the following sequence contains all permutations of the first three positive integers: [123, 132, 213, 231, 312, 321]
  4. diffusion: a desirable property of cryptography which states that any single change to the plaintext should affect all bits of the ciphertext with equal probability. ECB has poor diffusion because changes to the plaintext affect only the current block.
  5. initialisation vector: a nonce, specifically one used as (or which modifies) the input to the initial block.
  6. CSPRNG: In cryptography, there is often a need to generate “random-looking” numbers in a deterministic (and therefore reproducible) fashion. An algorithm used for this purpose is called a CSPRNG: cryptographically secure pseudorandom number generator.
  7. primitives: “well-established, low-level cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems. These routines include, but are not limited to, one-way hash functions and encryption functions.” source
  8. embedded systems: computer systems which exist as part of an appliance or other purpose-built hardware. The computer inside your car is an embedded system, for instance, and so is the one inside your microwave.

References

  • https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
  • http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf
  • https://github.com/dancodery/electronic-codebook-image-demonstration
  • https://en.wikipedia.org/wiki/Cryptographic_primitive

Additional thoughts

If you enjoy my work, please leave a comment. Even if you don’t feel like doing the activity (which I may stop doing soon or at least not every time), don’t hesitate to add something else to the discussion. Is there something I could have explained better? Got a question you think is dumb? Ask it! (It isn’t. This stuff is hard.)

You’ll get an upvote from me, my undying appreciation, and y’know… someday when I am rich and famous, I’ll remember you as I shoo away the onslaught of elephants. 🍋