Review Videos for Lecture 5: IND-CPA, One-Time Pads, Block Ciphers, Symmetric-Key Encryption

• Summer 2020 notes (part 1)
• Summer 2020 notes (part 2)
• Summer 2020 notes (part 3)
• Playlist (length: 2:13:25)

Intro to Cryptography

(True/False) Cryptography only reasons about defending against known attacks

False. Cryptography mathematically models any attacker strategy and can provide guarantees against attacks we don’t even know about

(True/False) One difference between symmetric and asymmetric key cryptography is that in the former one key is held by both parties, while in the latter both parties have different keys

True.

Kerckhoff’s Principle/Security Through Obscurity

What are three reasons cryptographic schemes should be public? Which part of a cryptosystem must be kept private?

1) If your secrets are leaked, it’s a lot easier to change a key than an entire algorithm 2) Public algorithms can be tested and improved by others 3) The algorithm should be usable by different people under different threat models.

The key

Intro to Symmetric Encryption Schemes

Why do we allow the ciphertext to leak the length of the message in our definition of confidentiality?

Because requiring the length to be hidden would hinder use cases by either making it impossible to encrypt large messages or expensive to encrypt small ones.

Defining Security for Symmetric Encryption

What did our original idea of security fail to account for?

Partial information leakage

Security Games and IND-CPA

What is the adversary's goal in the IND-CPA game?

To distinguish the encryption of two messages of their choosing.

IND-CPA Examples

Is Enc(K, M) = 3*K +2*M, IND-CPA secure?

No. Similar to a previous example, encrypting a message of 0 and dividing by 3 completely reveals the key

IND-CPA Intuition

If we modify IND-CPA such that the messages sent in the challenge phase can't be queried during either of the query phases, which type of undesirable encryption scheme will now be considered IND-CPA?

Deterministic schemes

One-Time Pads (OTP)

Consider a variant of IND-CPA, IND-CPA', where an attack can only make one query before submitting their challenge and no queries after. Is the OTP IND-CPA' secure?

No, the adversary can learn the secret key in one step by querying 0.

Intro to Block Ciphers

As we'll see later in the class, everytime you use the internet you're using block ciphers! The most common block cipher used today is called AES which we'll discuss in a bit.

Fun fact: Prof. Wagner was part of the team that came up with a block cipher called TwoFish which was one of the top 5 block cipher designs chosen internationally when NIST was attempting to find a standard.

Random Functions and Permutations

(True/False) A Gaussian distribution is considered random

False. A Gaussian distribution has a bias towards it’s mean. We consider the Uniform distribution to be random.

How many bits would it take to represent a truth table of a random permutation with input length of n bits?

2^n * 2n. There are 2^n entries each of length 2n. Notice, that for something like n=128 this is more space than all the computers in the world combined have! Thus, it’s not feasible to use actual random functions so we’ll need to use something that’s ‘pseudorandom’ or ‘looks like’ a random function.

Block Cipher Security

What does a block cipher need to computationally indistinguishable from in order to be considered secure? (Computationally indistinguishable means an efficient (ie. polynomial time) attacker can't distinguish)

A random permutation. If this is true, we call a block cipher ‘pseudo-random’.

Why Only Efficient Attackers?

Which input could an unbounded attacker brute force to win the block cipher distinguishing game?

The secret key

Information Leakage of a Block Cipher

If an adversary could learn first bit of M when given E(K, M) where E is encryption for a secure block cipher, how would this lead to a contradiction?

Because this would allow the attacker to distinguish the block cipher from a random function which contradicts our security assumption about block ciphers. This type of contradiction argument is called a reduction and is very common when proving security of cryptographic schemes.

Overview of AES

If you could prove a block cipher was unconditionally secure, what else would you likely prove in the process?

That P!=NP (Don’t worry if you don’t know what this means - but it’s very significant in theoretical computer science!)

ECB Mode

Which property of ECB Mode makes it not IND-CPA secure?

It’s deterministic

CBC Mode

Which property must a block cipher have in order for CBC to be decryptable?

It must be bijective ie. invertible

CBC Security and Pseudo-Random Number Generators (PRNGs/PRGs)

What undesirable property would CBC mode have if we always picked the same IV?

It would become deterministic

Where might computer hardware get sources of weak randomness?

Environment (e.g. temperature), network traffic, key presses, etc.

CTR Mode

(True/False) CTR mode also relies on a block cipher being invertible in order to be decryptable

False. CTR mode never needs to use block cipher decryption since the message is never run through the block cipher.

CTR Security

(True/False) Like CBC mode, in CTR mode the nonce must be chosen randomly

False. We only need to guarantee that the same nonce isn’t used for different messages since the block cipher provides the randomness we need.

Padding

Would appending a sequence of alternating bits (ie. 101010) be a valid padding scheme?

No. A message might end in 10 and you would accidently remove it when stripping the padding