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

in steemstem •  10 months ago  (edited)

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

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. 🍋


Posted from my blog with SteemPress : https://lemony.cricket/2018/07/16/introduction-to-cryptography-i-encryption-pt-4-block-ciphers-modes-of-operation/


Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

Well, I'm thinking it's a CBC... with the property that with constant input, the cipher text is 2-periodic, assuming the cipher is applied along the rows of the image.

k(c+v), k(c + k(c+v)), k(c + k(c + k(c + v))...

if k(x) were your block encryption.

k(c+v) = k(c + k(c + k(c + v))

Without any other info, this could happen if your key was x-or'd too... in which case it would flip between k+c+v and v.

Problem with this theory is that it doesn't explain why the stripes would be flat (single colors), unless the same was true of the key and initial vector. And it also doesn't explain why the color would be restored after going through some edges.

I don't know, maybe it's just a plain old ECB? No that's not it, because the same background color in the middle has a different color. I think I'll just wait for you to tell me then.

·

I know I already said @dexterdev was the closest, but I may have lied. I think you're tied, because his answer is too undercomplicated, and yours is too overcomplicated. You're on the right track there at the end; we'll talk about it in the retrospective next post.

·
·

I think @eonwarped did better. Because my answer can even come without reading the article. Just by plain observation, you can answer like mine. @eonwarped has read it properly and knows the stuff I think.

Interactive exercise

Below are two images; the one on the right is an encrypted version of the one on the left.
Woah! That doesn't seem right. Take your best guess at what went wrong here and explain how you came to that conclusion.

It seems like you have done a Substitution cipher. And it is easy to break.

·

You're the closest person here. Very close. Extremely close. Watch out for next post's retrospective.

I am guessing that you didn't pad the first block with arbitrary data for the image :)

·

Not quite! That can be a problem with CBC if you're using the intitialisation vector "hack"... but only the first block would be affected! Hint: it's a big image, and the blocks are really small... watch for next post's retrospective for the full explanation :)

@lemony-cricket, this is a great piece of work. I really commend u cos I know it's not easy researching and putting down something meaningful as this. But, I'd like to start the series from part 1, if you can be so chanced to send me the link I'd be very happy.

Thanks.

Interactive exercise

Below are two images; the one on the right is an encrypted version of the one on the left.
Woah! That doesn't seem right. Take your best guess at what went wrong here and explain how you came to that conclusion.

I don't know what went wrong. Lol.
But I guess the encrypted picture looks blurred and doesn't look sharper at the edges compared to the original picture.

Thanks.

·

Hi there @emperorhassy! Thank you for your kind words. You can start the series here:

https://steemit.com/steemstem/@lemony-cricket/introduction-to-cryptography-i-encryption-pt-1-the-caesar-cipher

I missed a link between the 3rd and 4th posts. For ease of navigation, you may access the entire series at https://lemony.cricket as well!

But I guess the encrypted picture looks blurred and doesn't look sharper at the edges compared to the original picture.

Hmm... not quite. Remember that the reason that we encrypt things is to make them completely invisible to others. Does the picture on the right look completely random? Or can you sorta tell what's in the picture? That should help you along. The full explanation will be in the retrospective on the next post!

I once heard about Quantum Cryptography (can't remember where though), but I want to ask; does it have any direct/indirect relationship with any of the cipher methods you listed in the post? If yes, which of them?

PS: That image on the right (in the exercise you gave) looks like it had some hidden Steganographic codes in it - I mean; like some text codes are being hidden in it. I might be wrong though.

Nice post there

·

Quantum cryptography actually has much stronger ties to information theory than the cryptography we're talking about here. There's also quantum-resistant cryptography, which aims to re-create the existing systems we have in ways that are resistant to quantum computers.

The algorithms most endangered by the ever-looming threat of generalised quantum computing are actually our most popular public key cryptography schemes. Symmetric cryptography (where the key is the same on both sides; the block ciphers and stream ciphers we've been learning about) is actually mostly safe from that stuff.

It's not steganography, but if I can fit it in, I'd love to do a post on steganography! Maybe I'll do it as a separate post. If I do I'll credit you for giving me the idea!

·
·

Thanks a lot. I would be honoured

Hi @lemony-cricket!

Your post was upvoted by utopian.io in cooperation with steemstem - supporting knowledge, innovation and technological advancement on the Steem Blockchain.

Contribute to Open Source with utopian.io

Learn how to contribute on our website and join the new open source economy.

Want to chat? Join the Utopian Community on Discord https://discord.gg/h52nFrV



This post has been voted on by the steemstem curation team and voting trail.

There is more to SteemSTEM than just writing posts, check here for some more tips on being a community member. You can also join our discord here to get to know the rest of the community!

BINEX.TRADE is the next promising upcoming crypto exchange, which will daily payout 70% of their trading commission proportionally among the BEX token holders. Grab 3 free BEX tokens (5 Dollars) just for pre-registering:

BINEX.trade get free Token

·

You've got to be kidding me.

Congratulations @lemony-cricket! You have completed the following achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of upvotes received

Click on the badge to view your Board of Honor.
If you no longer want to receive notifications, reply to this comment with the word STOP

Do not miss the last post from @steemitboard:
SteemitBoard World Cup Contest - The results, the winners and the prizes

Do you like SteemitBoard's project? Then Vote for its witness and get one more award!