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

in steemstem •  5 months ago

Hey everyone! I'm @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 @bachuslib, @svemirac, @insaneworks, @warpedpoetic, @kex, and @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 plaintextr1. 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 attackr2.
  • 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.

  1. 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 2256 possible keys.
  2. 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.
  3. cryptanalysis: the science of attempting to break cryptographic systems, especially encryption.
  4. 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
  5. pseudorandom: describes a collection of apparently random data which is actually generated by an algorithm in a deterministic manner.
  6. 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).
  7. 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.
  8. deterministic: describes an algorithm and an outcome which is repeatable in all cases if the same exact input is provided to the system.

References

  1. https://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy
  2. https://en.wikipedia.org/wiki/Stream_cipher_attacks#Reused_key_attack
  3. 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/
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:  

2 11 23 24 14
22 14 3 22 22
17 9 7 25 22
14 0 15 12 1

Huh?

·

We got it figured out in the end. :) Thanks for your participation!

·
·

In case anyone else is wondering WTF is wrong with my submission, I started correctly in manipulating the key for the ciphertext C HTZG ISY, and after the second character, I flipped to the actual message instead I MISS YOU and that screwed it up hahahaha....

Great Piece this one, well researched.

🚀 This is a stellar post! 🚀

I will be featuring it in my weekly #technology and #science curation post for the @minnowsupport project and the Tech Bloggers' Guild! The Tech Bloggers' Guild is a new group of Steem bloggers and content creators looking to improve the overall quality of our niche.

Wish not to be featured in the curation post this Friday? Please let me know. In the meantime, keep up the hard work, and I hope to see you at the Creators' Guild!


If you have a free witness vote and like what I am doing for the Steem blockchain it would be an honor to have your vote for my witness server. Either click this SteemConnect link or head over to steemit.com/~witnesses and enter my username it the box at the bottom.

Congratulations! Your post has been selected as a daily Steemit truffle! It is listed on rank 16 of all contributions awarded today. You can find the TOP DAILY TRUFFLE PICKS HERE.

I upvoted your contribution because to my mind your post is at least 24 SBD worth and should receive 86 votes. It's now up to the lovely Steemit community to make this come true.

I am TrufflePig, an Artificial Intelligence Bot that helps minnows and content curators using Machine Learning. If you are curious how I select content, you can find an explanation here!

Have a nice day and sincerely yours,
trufflepig
TrufflePig

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

Great job you've done with the intoduction
Keep em coming @lemony-cricket

For an introductory work -- you did quite great@lemony-cricket

Quality content

20 16 3 8 1
10 4 4 22 22
17 9 7 25 22
14 0 15 12 1

no time for thinking :Y