Cryptography: Slide Deck 3


In which the following are discussed...

  1. The Players: Alice, Bob, etc.
  2. Active vs Passive attacks
  3. Attack Models
  4. The One Time Pad
  5. Intro to Stream Ciphers

Alice, Bob and Friends

Communication is about the transfer of information between two parties, Alice (A) and Bob (B).

These may be the same person: We often send messages to our future selves.

Alice and Bob may be separated by space, time, or both.

In cryptography we also consider other parties who may seek to alter, disrupt, or observe communication between Alice and Bob.

These people are variously called Eve (eavesdropper), Mallory (malicious actor), or Oscar (observer?).

The Gang's All Here...

AB

Are they people?

It's important to realize that more often than not Alice and Bob are computer programs.

Therefore they can be very dense and do dumb things, like encrypt/decrypt documents for the adversary.

It depends on what protocol is being run.

Here are two random examples of protocols, just to give an example of what "protocol" means:

protocol 1 protocol 2

Attack Models

When designing a cryptosystem you need a model of what a bad actor might do to break your system.

Usually the threats are divided into passive attacks and active attacks.

In a passive attack Eve only eavesdrops.

Her actions are undetectable because she does not engage with Alice or Bob.

Examples: eavesdropping, traffic analysis, dumpster diving and war driving.

Almost any kind of crytposystem needs to be secure against passive attacks.

Attack Models

When designing a cryptosystem you need a model of what a bad actor might do to break your system.

Usually the threats are divided into passive attacks and active attacks.

In an active attack Mallory will interact with Alice and Bob in some way.

She might...

  • Masquerade
  • Replay old messages (replay attack)
  • Modify messages in transit
  • Try to deny service (DoS or DDoS)

Bob gone wild

In some cases Alice or Bob may themselves be the bad actor.

This might happen if Bob tries to cheat Alice during an electronic payment.

The security goal of non-repudiability addresses Bob or Alice themselves misbehaving.

Attack Models

Just as we might model a passive or active adversary, we can model Eve as having different levels of access to our communications.

Can Eve know or guess some of the plaintext for a piece of ciphertext she might intercept?

Often this is possible with a "crib".

Can Eve trick Alice into encrypting some information that Eve chooses for her?

This might seem odd, but remember that Alice is probably a program implementing a protocol.

There are also historical examples from WW II.

Attack Models

There are the following standard attack models.

  1. Ciphertext only attack (COA):

    Eve sees only ciphertext. Knows the system but not the key.

  1. Known plaintext (KPA):

    Eve has the ciphertext for a message that she knows.

  1. Chosen plaintext (CPA):

    Eve has the ciphertext for a message that she chooses.

  1. Chosen ciphertext (CCA)

    Eve can see the decryption of ciphertexts that she chooses.

Wait...Chosen ciphertext? Why doesn't she just...

It might seem that a chosen ciphertext scenario is silly, because in this case the adversary could just decrypt the message.

This will make more sense when we study asymmetric key cryptography.

But you can imagine a situation (like a smart card) where an attacker has total control over a cryptosystem as a black box and wants to recover the key.

It should be impossible to recover the key just from seeing examples of decryptions.

Examples...

Unfortunately all of the examples we have seen so far are not secure in any of the models: COA,KPA,CPA, or CCA.

For Project 1 for example, simply seeing the encryption of the letter 'A' (aka 0) reveals the key!

k = (A + k)

And as the histogram function shows, even a ciphertext only attack is possible.

We will now study our first cipher with some real security properties: The One Time Pad.

One time pad

The idea of the one time pad is simple...

To transmit an $n$ bit message $M$, Alice generates an $n$ bit key $k$ at random.

She then somehow distributes $k$ to Bob (possibly the key was already distributed).

The ciphertext is $C = M \oplus k$.

After receiving $C$, Bob decrypts $C$ using $k$ to recover $M$:

decryption = $C \oplus k = M \oplus k \oplus k = M$

OTP

The OTP is interesting because it achieves information theoretic security.

This means that the ciphertext $C$ contains no information about $M$ in the absence of $k$.

This is in the sense of "information theory" as developed by Claude Shannon.

His original paper on the OTP is still very accessible: famous paper

The first cryptographer to realize the significance of OTP was Joseph Mauborgne.

Information theoretic security

The chances that an enemy with infinite computational resources can decrypt $C$ without $k$ are zero.

The reason is that for any possible decrypt $M'$, there is exactly one $k'$ such that

$$ M' = C \oplus k' $$

This means that any decrypt is equally likely from Eve's point of view.

With no knowledge of $k$, why would Eve prefer $M$ to $M'$ as a possible decrypt?

She wouldn't... and therefore she can't decrypt $C$ without $k$, even with an infinitely fast computer.

A fact about probability...

Suppose that $r$ is selected uniformly at random from ${0,1}$.

Then $P(r = 1) = P(r = 0) = \frac{1}{2}$.

Now consider $P(r \oplus 1 = 1)$. Again this probability is $\frac{1}{2}$.

Therefore $P(r \oplus 1 = 0) = \frac{1}{2}$ also.

The same is true for $r \oplus 0$:

$$P(r \oplus 0 = 0 ) = P(r \oplus 0 = 1) = \frac{1}{2}$$

.

This says that, in the OTP, if the key is random, then the ciphertext is random.

Downsides of OTP

You might notice that OTP is not very widely used. It is used sometimes, but rarely.

What are the disadvantages?

  1. The key may be very large. It must be as large as the plaintext.
  1. The key (aka pad) can only be used one time, as the name suggests. If the key is reused, then OTP can be cracked.
  1. The key must really be truly random.

The Many Time Pad

Issues similar to the ones found in reusing the key in OTP come up a lot in cryptography.

What goes wrong?

Suppose $C_1 = k \oplus M_1$ and $C_2 = k \oplus M_2$.

Then if Eve has $C_1$ and $C_2$, she can compute

$$C_1 \oplus C_2 = k \oplus M_1 \oplus k \oplus M_2 = M_1 \oplus M_2.$$

If $M_1$ and $M_2$ are long enough and non-random enough, both $M_1$ and $M_2$ can be recovered from $M_1 \oplus M_2$.

The situation is even worse if $k$ is reused more than twice.

Also if $M_1$ is known then finding $M_2$ from $M_1 \oplus M_2$ is easy.

Stream Ciphers

Modern ciphers try to imitate the strengths of OTP without the downsides.

The idea is to shorten the key to something reasonable: 128 or 256 bits.

This means we lose information theoretic security.

But hopefully we can still have co