Open in app

Sign in

Write

Sign in

Image source: Jon Moore Unsplash

Introduction to Cryptography: One time pads and stream ciphers

Part 1 of an 8-week explainer series based on Dan Boneh’s Crypto I

I hope this serves as a practical, easy-to-understand guide for crypto enthusiasts who want a stronger understanding of ciphers, encryption, number theory, and public-key encryption methods. No coding/math skills required.

This week we cover:

  • Basic symmetric ciphers: OTPs, stream ciphers
  • Security definitions: perfect secrecy, semantic security

Understanding Basic Ciphers

Cryptographic ciphers are algorithms that scramble your secret messages, e.g. “I love dogs!” into nonsensical, random-looking text, called ciphertext.

To the casual observer, the ciphertext alone doesn’t mean anything. Thus if it is leaked, your secret is still preserved. For example, this ciphertext49f56c6c40654f48eccc61b has no standalone meaning.

A cryptographic cipher can be as simple as an alphabetical substitution:

An example of a (very insecure) Substitution Cipher

Based on the above Substitution Cipher, what does the following encrypted ciphertext say? Can you decrypt: "ifmmp xpsme!"

Modern-day ciphers can be as complicated as the AES encryption standard, which is used across many disk and network encryption protocols:

A schematic of the Advanced Encryption Standard cipher logic

Example 1: The One Time Pad

A particularly important cipher to understand is the One Time Pad (OTP), which was quite popular around WWII.

The OTP mutates a message using another predetermined message of the same length.

For example, Alice and Bob would predetermine a message, also known as a key, ahead of time. An example of a very insecure key would be: “This is very insecure key”

Later, when Alice wants to send the following secret message to Bob: e.g.“Meet me at the park bench”, she can simply perform a bitwise XOR operation on her message using the key.

In the hexadecimal format, this yields the ciphertext 190d0c..., which she then sends to Bob.

Finally, Bob can easily decrypt Alice’s ciphertext by XORing the key and the ciphertext. This allows Bob to reverse derive the original message.

XOR: The bitwise operation in OTPs. For example, 0 xor 0 ,1 xor 1 yields the 0 bit and 0 xor 1 ,1 xor 0 yields the 1 bit.

It’s important to call out that OTPs have an important vulnerability by nature of XOR’s properties: if you generate many ciphertexts with the same key, and assuming an attacker gets at least 2 of your ciphertexts, the attacker can actually reverse engineer the original key! Attack explained.

The main takeaway here is that the One Time Pad is only secure if you only use your key once, and only if your key is the same length as your message.

Relating OTP to Terminology

OTP is a type of “symmetric encryption”

When used correctly, the One Time Pad is a very good example of symmetric encryption. This is also known as private key encryption, secure key encryption, or secret key sharing, etc.

Alice encrypts a file with the same key that Bob uses to decrypt the file

In simpler terms, symmetric encryption is when the same key is shared among participants to both encrypt and decrypt the data.

OTP demonstrates “perfect secrecy”

The One Time Pad also demonstrates an important cryptography principle called perfect secrecy. Where, given a ciphertext, every message in the message space is exactly as likely to be the underlying plaintext.

In simpler terms, perfect secrecy means that to an attacker, the ciphertext looks completely random. There are no patterns, no hints about the underlying message by just looking at the ciphertext.

It also means that, if an attacker somehow gets a part of the key/message, like the first half, he can never derive the remaining parts of the key/message:

Illustration of a Perfect Secrecy cipher, even if some parts of its keys are compromised

Based on the above definition, does a cipher which uses a repeating key demonstrate perfect secrecy? If the key is hellohellohellohello…

Example 2: The Stream Cipher

It turns out, it’s super impractical to use the One Time Pad in most real-life use cases.

For every message you want you to encrypt, you’d have to create and share a new key that’s the same length as your message. Just imagine coming up with keys to encrypt 10 movies that are 5 GB long each. Yikes.

Instead, more modern symmetric encryption ciphers need to help you AVOID generating new & super long keys every time you want to encrypt something. These ciphers still need to be “somewhat secure” against potential attackers.

Stream ciphers offer such a solution.

Stream Ciphers

Like OTP, stream ciphers take a predetermined key k which never changes.

Unlike OTP, you can now use this key multiple times. Each time you need to encrypt some data, you rely on a special algorithm to expand your key into a new and unique encryption key. This encryption key actually matches the length of your data.

And it turns out that there are algorithms out there that can do this type of key expansion for you in a relatively secure way, such that each encryption key still looks relatively random and yields “random” looking keys as a result.

Then, again similar to OTP, you can encrypt the message by XORing it with the newly generated, unique encryption key.

Visually, it works like this:

Stream Ciphers use unique encryption keys randomly derived from the same static key

In stream ciphers, you can now repeatedly encrypt new* content using the same “seed” key without revealing any secrets. Convenient!

Relating Stream Ciphers to Terminology

Stream ciphers are (also) a type of “symmetric encryption”

Again, the same seed k is used for both encryption and decryption.

When it comes to decryption, most stream ciphers use algorithms that deterministically generate encryption keys. This means the receiver already knows which unique decryption keys to use from a preset list.

Stream ciphers demonstrate “semantic security”

Previously, we learned that OTPs offer perfect security but are wholly impractical. So in the real world, we comprise this by ensuring something called semantic security.

Formally, it means that any probabilitic, polynomial-time algorithm that is given the ciphertext of a certain message (taken from any distribution of messages), and the message’s length, cannot determine any partial information on the message with non-negligible probability higher than all other algorithms that only have access to the message length (and not the ciphertext).

In simpler (nonrigorous) terms, semantic security is when an attacker can’t simply send smartly constructed messages into a cipher to detect ANY patterns that would eventually help him mount an attack… at least in a probable timeframe.

To illustrate this in detail, here’s an example of a NON semantically secure cipher, where Bob is the attacker trying to guess Alice’s secret.

Alice has a super insecure cipher which works like a stream cipher —but for some silly reason — turns the last bit of the ciphertext to01 ONLY if the original message ends with a punctuation mark. 😂

Well, Bob can then mount the following attack:

Bob is now one step closer to figuring out Alice’s semantically insecure cipher.

It’s abit of a pedantic example. But the point here is that in polynomial time, a seemingly secure cipher could exhibit some patterns over time that allow attackers with powerful computational resources to eventually crack the cipher.

The main takeaway here is, when choosing symmetric encryption ciphers, choose one that is proven to be semantically secure in the real world, after years of being put to the test in the field. Don’t invent your own ciphers :)

Main takeaways

That’s it! You’ve learned the following key concepts this week:

  • Symmetric encryption: the 2 cipher examples above are cases of symmetric encryption, where both the encryption and decryption share the same key k.
  • OTP ciphers are impractical but have perfect secrecy
  • In practice, stream ciphers are more feasible to use and compromise perfect secrecy for semantic security, which is good enough in real-time.

How can I learn more:

  • Next week: Stay tuned for a simple explainer on block ciphers and what it means to have cryptographic integrity
  • If you want to join my study group — the course material is freely available on Coursera — DM me on Twitter for meeting times (1 hr/week).
  • If you want to do this stuff full time and get paid for it, check out Parity Technologies, the company I work for here and our available roles here. We build cryptography, networking, and core blockchain technologies across both research and implementation.

Also, Read

Get Best Software Deals Directly In Your Inbox

Cryptography
Blockchain
Cybersecurity
Bitcoin
Technology

--

--

Nicole Zhu
Coinmonks

Written by Nicole Zhu

1.3K Followers
Writer for

Engineer. Building jan.ai. Tweets @0xSage

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams