Hey everyone! I'm Hive account@lemony-cricket. In the inaugural installment of Introduction to Cryptography, we laid down some of the basic building blocks of understanding encryption. We learned about encryption and decryption, plaintext and ciphertext, and what a key is. In this installment, we'll be learning about one-time pads and a little bit about modern stream ciphers.

This is the second post in this series. The next post is here.

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

Retrospective

First, before we begin, I'd like to extend gratitude to Hive account@bachuslib, Hive account@svemirac, Hive account@insaneworks, Hive account@warpedpoetic, Hive account@kex, and Hive account@enjar for their participation in the interactive portion last time. Full marks, all of you! All participants successfully encrypted a message using the Caesar shift algorithm and received an encrypted reply from me using the same key.

But how did I know your key if you didn't tell me? The answer may be obvious to some of you at this point, but if you're still wondering...

The Caesar cipher has an extremely small 𝕜𝕖𝕪𝕤𝕡𝕒𝕔𝕖^{^d1}. This means it is incredibly weak when faced with a simple 𝕓𝕣𝕦𝕥𝕖-𝕗𝕠𝕣𝕔𝕖 𝕒𝕥𝕥𝕒𝕔𝕜^{^d2}. Since there are only 26 letters in the English alphabet, I only had to try to decrypt your message 26 times, one for each possible offset. Once I got something that made sense, I knew I had found the "secret" key.

But that's cheating!

Not really. In matters of cryptography and security, nothing is cheating. Besides, it made for a very nice introduction to extremely basic 𝕔𝕣𝕪𝕡𝕥𝕒𝕟𝕒𝕝𝕪𝕤𝕚𝕤^{^d3}, the "cat" from which cryptography's "mouse" is perpetually running.

For every good person out there who needs cryptographic protection, there is a bad person trying to defeat it. For every bad person using cryptography for evil, there is a good person trying to catch them. In this way, cryptography and cryptanalysis go hand-in-hand to bring balance to a chaotic world. This is just the way that things are.

The one-time pad

^{unbreakable but cumbersome security}

One way to ensure that your data is safe is to use a one-time pad. We'll find out what that means in a moment. First, let's assume Alice and Bob are two friends who are currently together in a safe location, away from prying eyes. Bob is going on a trip soon, and Alice wants to be able to send him a secret message while he is away.

The first thing they will do is generate the key. With a one-time pad, the key has to be very large; at least as large as the message you wish to send! Alice and Bob decide that the message will be small; no longer than 2 or 3 words. They decide that 20 letters will be enough. They use RANDOM.ORG to generate 20 numbers from 0 to 25...

20  21  11  7   14
10  4   4   22  22
17  9   7   25  22
14  0   15  12  1

Each keeps a copy of the numbers and they part ways. A week later, Alice writes her message to Bob:

I MISS YOU

Alice encrypts each letter of this message using the rules of the Caesar shift we learned before, but with a catch: every letter uses a different shift value, taken in order from the one-time pad (from left to right):

I -=20=-> C
M -=21=-> H
I -=11=-> T
S -=07=-> Z
S -=14=-> G
Y -=10=-> I
O -=04=-> S
U -=04=-> Y

C HTZG ISY

When Bob receives the message, he can just perform the decryptions with the same keys in the same order, and he will get the original message back.

One-time pads are an example of 𝕚𝕟𝕗𝕠𝕣𝕞𝕒𝕥𝕚𝕠𝕟-𝕥𝕙𝕖𝕠𝕣𝕖𝕥𝕚𝕔 𝕤𝕖𝕔𝕦𝕣𝕚𝕥𝕪^{^d4}. This means that they are proven to be uncrackable, as without having the key, you actually have no information whatsoever about the plaintext^{^r1}. I am using spaces in these exercises for readability, but in a real-world application, we would be encrypting the spaces too, and they'd get lost in the jumble.

So this is great, right? It's a start. There are a few problems with one-time pads:

The key must be at least as long as the plaintext.
Once a part of the key is used, it should never be re-used again. This would expose the key to a reused key attack^{^r2}.
The key(s) must be generated in full and, once depleted, there is no way to generate more except to meet up again.

Introducing stream ciphers

^{they're like an (almost) infinite one-time-pad}

A stream cipher is an extension of the one-time pad concept. The main logic of a stream cipher is focused upon generating a never-ending stream of 𝕡𝕤𝕖𝕦𝕕𝕠𝕣𝕒𝕟𝕕𝕠𝕞^{^d5} data called the 𝕜𝕖𝕪𝕤𝕥𝕣𝕖𝕒𝕞^{^d6}. This keystream then acts as a one-time pad which is much easier to store and transmit, since it is generated from a much smaller key using a publicly-known algorithm.

In the above example, we used a modified Caesar shift algorithm with each letter consuming a separate key from the keystream. In practice, most modern stream cipher implementations operate on individual bits of data and use the 𝕖𝕩𝕔𝕝𝕦𝕤𝕚𝕧𝕖 𝕆ℝ^{^d7} (XOR) operation for this purpose, as it is fast, universally available, and the decryption operation is actually the same as for encryption! (We will discuss this all in more detail in the next installment.)

Well, it can't be all good news. There has to be a catch.

There is, sort of. Since the keystream must be 𝕕𝕖𝕥𝕖𝕣𝕞𝕚𝕟𝕚𝕤𝕥𝕚𝕔^{^d8}, it cannot possibly be truly random. Therefore, there is a risk some weakness could be discovered in the algorithm which could lead to a practical attack on the cipher. In addition, with the decrease in key size, the keyspace is also decreased, making brute-force and other attacks marginally easier. In general, though, the benefits (which are tangible and tested) outweigh the disadvantages by far (which are theoretical and unlikely).

Next time, we'll be taking a closer look at a specific stream cipher in order to understand how the keystream is generated. We'll also look at some more complicated attacks.

Interactive exercise

^{You should have paper and something to write with for this portion.}

Your name is Evelyn, and you've been trying to get between Alice and Bob for a while now. You've followed Bob to his destination and snuck into his hotel room while he's out running an errand.

You see a note on the desk. You can't believe your eyes; Bob has left his notes out on the table. Alice always was the more careful one.

20  21  11  7   14
10  4   4   22  22
17  9   7   25  22
14  0   15  12  1

C HTZG ISY

What's more, Bob has carelessly written his copy of the key in pencil. This is it! The moment you've been waiting for.

Hurry! Before Bob gets back! Change the key so that the message written reflects a malicious message. Then, leave the new key in the comment section below. You can go for the obvious choice, or get a bit creative. The choice is yours! 🍋

Definitions

^{From my personal knowledge and experience unless otherwise noted.}

keyspace: this is the number of total possible keys that exist. If you have a 256-bit key, and all possible values are valid, then there are 2²⁵⁶ possible keys.
brute-force attack: the attempt to try every single possible key (to search the entire keyspace) to find the valid key. While trivial for small keyspaces such as that of the Caesar shift, it quickly becomes impractical and at some point even almost certainly impossible.
cryptanalysis: the science of attempting to break cryptographic systems, especially encryption.
information-theoretic security:
a cryptosystem whose security derives purely from information theory. In other words, it cannot be broken even if the adversary had unlimited computing power.^{^r3}
pseudorandom: describes a collection of apparently random data which is actually generated by an algorithm in a deterministic manner.
keystream: a continuous, (apparently) randomised stream of data which can be combined in some way (usually XOR) with the plaintext (to encrypt) or ciphertext (to decrypt).
exclusive OR: a bitwise logic operator which returns true (1) if and only if exactly one of the inputs is true (1). For example, the result of XORing 1100 with 1010 is 0110. We'll see more about this in the next installment.
deterministic: describes an algorithm and an outcome which is repeatable in all cases if the same exact input is provided to the system.

References

https://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy
https://en.wikipedia.org/wiki/Stream_cipher_attacks#Reused_key_attack
https://en.wikipedia.org/wiki/Information-theoretic_security

Posted from my blog with SteemPress : https://lemony.cricket/2018/06/12/introduction-to-cryptography-i-encryption-pt-2-one-time-pads-and-stream-cipher-intro/

Introduction to Cryptography I: Encryption (Pt. 2 – One-Time Pads and Stream Cipher Intro)