Cryptography 1
Cryptography
‹#›
Caesar cipher
Replace each letter in the plaintext with a letter found at a fixed shift down the alphabet
For example, with a shift of 3:
D A
E B
Uryyb Jbeyq!
‹#›
Vignère Cipher
Use a different shift for each character position
A key encodes the shift for each position
Each character in the key is the shift from A for the matching position
Key “BEER” means that the first position is shifted by one, the second and third by 4 and the fourth by 17
The key repeats to cover the whole message
‹#›
BEERB EERBE
Hello World!
Iipcp Asimh!
Vignère Cipher – example
‹#›
Scytale
‹#›
Feissner Grille
‹#›
How not to select a cipher?
Kerckhoffs’s principle
Don’t use a secret scheme – rely only on the secrecy of the key
Schneier’s law
“Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can’t break.”
The Dunning-Kruger effect
‹#›
Proving Cipher Security
A “formal definition”
A cipher defined over (K, M, C) is a pair of efficient functions (E, D)
E: K⨉MC, D: K⨉CM
(We usually write Ek(m) instead of E(k,m))
For some definition of “efficient”.
Theoreticians use polynomial in the security parameter.
We will think of it as fast enough to calculate
‹#›
“Formal” definitions
A cipher defined over (K, M, C) is a pair of efficient functions (E, D)
E: K⨉MC, D: K⨉CM
(We usually write Ek(m) instead of E(k,m))
5pm at the
rose garden?
Ek()
Gobbledy
gobbledygook
Gobbledy
gobbledygook
Dk()
5pm at the
rose garden?
‹#›
“Formal” definitions
A cipher defined over (K, M, C) is a pair of efficient functions (E, D)
E: K⨉MC, D: K⨉CM
(We usually write Ek(m) instead of E(k,m))
Correctness:
∀m,k: Dk(Ek(m))=m
‹#›
Perfect Secrecy (Shannon 1945)
An adversary that sees a ciphertext cannot learn anything about the plaintext.
All plaintexts have the same probability of producing any given ciphertext
Formally:
∀m1,m2,c: Pr[Ek(m1)=c] = Pr[Ek(m2)=c]
Questions:
Can we achieve perfect secrecy?
Does it guarantee security?
‹#›
One Time Pad (Vernam 1919)
Domain: M={0,1}n, C={0,1}n, K={0,1}n
For a plaintext m and a key k, Ek(m)=k⊕m
For a ciphertext c and a key k, Dk(c)=k⊕c
Are these efficient?
Correctness:
Dk(Ek(m)) = Dk(k⊕m) = k⊕(k⊕m) = (k⊕k)⊕m = 0⊕m = m
‹#›
Perfect secrecy of OTP
Recall: ∀m1,m2,c: Pr[Ek (m1)=c] = Pr[Ek (m2)=c]
For every ciphertext c and plaintext m, there is exactly one key k=c⊕m such that Ek (k,m)=c
Hence for all m and c, Pr[Ek (m)=c] = 2-n
Because the probability of Ek (m)=c does not depend on m, the cipher has perfect secrecy
‹#›
Limitations
Long key
Any perfectly secure cipher must have long keys
Malleable
Key cannot be used more than once
Class exercise: How would you break OTP if the key is used more than once?
Perfect secrecy assumes a very weak attacker!!!
‹#›
Ciphertext indistinguishability
A desired property of ciphers
A cipher is considered secure if no adversary can distinguish identify one of two messages based on their ciphertexts
Typically presented as a game between an adversary and a challenger.
‹#›
Distinguishability Games
Challenger chooses a random key
Adversary gets gets some access to a cipher with that key
Adversary sends two messages to the challenger
Challenger chooses one at random, encrypts it and sends back to adversary
Adversary wins on a successful guess of the encrypted message
k
(m1,Ek(m1))
(m2,Ek(m2))
(M0, M1)
(Ek(mb))
‹#›
16
Adversarial models
Known plaintext attack
The adversary learns some pairs of matching plaintexts and ciphertexts
Chosen plaintext attacks
The adversary can encrypt some plaintexts of her choosing
Chosen ciphertext attack
As CPA, but can also decrypt some ciphertexts
Adaptive chosen ciphertext attack
AS CCA, but can base the choices on previous results
‹#›
More attacks
Side channel attacks
The adversary has information on the internal state of the implementation
Fault injection attacks
The adversary can modify the internal state of the implementation
Protocol attacks, RNG attacks, …
The adversary is not bounded!!!
‹#›
How to select a cipher?
Use an established, well-researched encryption
E.g. AES, Salsa20
Do not write a new implementation
Remember the Dunning-Kruger effect?
Use OpenSSL, libgcrypt, NaCl, etc.
‹#›
Story time – CSS
The DVD copy control association wanted to protect DVDs.
These are MGM, 20th Century Fox, Warner Bros etc.
They have a bit more resources than you, and likely more than your (future) employer
1996 – release CSS
Proprietary encryption algorithm
Oct. 1999 – DeCSS appears. Presumably via reverse engineering a DVD drive.
Uses a 40-bit key. Not entirely CCA’s fault, but could be broken in 24 hours using 1999’s tech. (A few seconds today.)
Nov. 1999 – Frank Stevenson releases three exploits
Reduce attack to 225. Can be broken in a few seconds.
‹#›
Types of ciphers
Stream ciphers
Produce a pseudo-random stream of bits
XOR stream of bits with plaintext message to produce ciphertext
Block ciphers
Operate on fixed-size blocks of data
SWEET32 attack – ciphers with 64-bit blocks are not secure. Use AES (128-bit blocks).
Block ciphers are better understood and are used more often
‹#›
Substitution-Permutation Network
An approach for designing block ciphers
Consists of multiple rounds. Each round consists of two layers:
Substitution boxes – a bijective function of a small number of bits
Permutation box – a function that transposes bits from the input to the output
‹#›
SP-Network
Diagram by Wikipedia
user GaborPete
‹#›
Modes of Operation – ECB
The block cipher mode of operation specifies how to handle messages longer than a single block.
Electronic codebook (ECB)
Divide message into blocks
Encrypt each block
‹#›
ECB is bad
Identical plaintexts encrypted to identical ciphertexts
‹#›
Story time – Adobe password leak
Oct 2013 – Adobe reports a breach of customers data.
We recently discovered that attackers illegally entered our network. The attackers may have obtained access to your Adobe ID and encrypted password. […] information such as your name, encrypted payment card number, and card expiration date also may have been accessed. […]
150,000,000 stolen records published
Contain usernames, emails, encrypted passwords, password hints and more.
Use 3DES in ECB mode for encrypting the passwords
‹#›
Sample data
Image source: nakedsecurity.sophos.com
‹#›
Modes of operation – CBC
Cipher Block Chaining
Before encryption XOR each plaintext block with the previous ciphertext block
Use a random Initialisation Vector (IV) for the first block
IV does not need to remain secret
‹#›
CBC Drawbacks
Encryption (decryption) is sequential
Limited ciphertext error propagation
Exploited in the POODLE and Lucky 13 attacks
‹#›
Modes of operation – CTR
Turns a block cipher into a stream cipher
Generate a sequence of “counter” blocks
Typically, a random nonce combined with a sequence number
Encrypt each counter block
XOR with the corresponding plaintext (ciphertext) block
Supports parallel encryption (decryption)
Diagram from
Wikipedia
‹#›
CTR – Drawbacks
Malleable – a change in the ciphertext results causes a similar change in the plaintext
Sensitive to repeated nonces and to an attacker manipulating the nonces
‹#›
Modes of operation – Summary
ECB – not secure. Do not use unless you know what you are doing.
Remember the Dunning-Kruger effect
CBC – most commonly used.
CTR – better performance but more sensitive
No authentication
No message integrity
‹#›