1/80
Looks like no tags are added yet.
Modern definition of cryptography
The scientific study of techniques for securing digital information and transactions and distributed computation against internal or external attacks
Traditional (Cambridge dictionary) definition of cryptography
The practice of creating and understanding codes that keep information secret
Topics in the cryptography section
Symmetric and authenticated encryption - hash functions and MACs - asymmetric (public-key) encryption - digital signatures and PKI
Three aims of the cryptography section
What cryptography can achieve - that it can go wrong - what good practice looks like when using it
Goal of symmetric encryption
Confidentiality (secure communications and file protection)
Symmetric cipher definition
Two algorithms: encryption E takes key and message to ciphertext and decryption D takes key and ciphertext to message. Correctness: D(k E(k m)) = m for all keys k and messages m
Who knows the key in a symmetric cipher?
The same key is used to encrypt and decrypt and it is secret - known only to Alice and Bob
Why is 'the attacker cannot recover the plaintext' not a strong enough security goal?
The attacker might still recover some bits or a function of the plaintext - a good scheme must hide partial information too
Intuition for a good encryption scheme
Ciphertext is indistinguishable from a random bit string (an encryption of m looks like an encryption of 0) - i.e. pseudorandom
Kerckhoffs's principle
The design of a security system should be public - security relies entirely on the secrecy of the key - no security through obscurity
Why does Kerckhoffs's principle make sense?
Open design lets many users and academics and white hat hackers scrutinise it - flaws are found and fixed early
Historical example of relying on a secret algorithm
Enigma cipher machine (WWII) - its design was classified but still leaked
Ciphertext-only attack
Attacker knows only some ciphertexts c1 to cn
Known plaintext attack
Attacker has some plaintext/ciphertext pairs (m1 c1) to (mn cn)
Chosen plaintext attack (CPA)
Attacker has an encryption oracle - can trick the victim into encrypting messages of the attacker's choice
Chosen ciphertext attack (CCA)
Attacker has a decryption oracle - can trick the victim into decrypting ciphertexts of the attacker's choice
Lunchtime attack
A CCA where the attacker can decrypt chosen ciphertexts for a while then loses access to the device and the victim carries on using it
Why is a ciphertext-only attack not always the realistic model?
Attackers can often guess plaintext (predictable message headers or weather and time-of-day reports) or even influence what gets encrypted
Computational power assumptions for adversaries
Unlimited or polynomial or realistic (up to about 2^80 operations)
Brute-force attack
Try all possible keys in the key space K - needs some knowledge about the structure of the plaintext
Two defences against brute force
Large key space (long keys) and keys sampled uniformly at random
Real-world example of bad key randomness
Certificate authorities that used weak or test keys not picked uniformly at random
One-time pad (OTP) definition
M = C = K = bit strings of length n. Encryption E(k m) = k XOR m. Decryption D(k c) = k XOR c
Why is OTP correct?
k XOR (k XOR m) = m because the key cancels out
Which attack is the OTP perfectly secure against?
Ciphertext-only attack with a single ciphertext (hence 'one-time')
Two-time pad attack
Reusing a key: c1 XOR c2 = m1 XOR m2 because the key cancels - language redundancy then lets the attacker recover both messages
Limitations of the OTP
Key as long as the plaintext - needs true randomness - subject to two-time pad attacks - malleable (no integrity)
What does malleable mean?
An attacker can change the ciphertext so that the decrypted plaintext changes in a predictable way without knowing the key
OTP malleability example
c' = c XOR 'to bob:000' XOR 'to eve:000' turns a transfer to Bob into a transfer to Eve
Does the OTP provide integrity or authentication?
No - it is malleable
Stream cipher idea
Make the OTP practical by using a pseudorandom key G(k) from a short seed instead of a truly random key. E(k m) = G(k) XOR m
Pseudorandom generator (PRG)
Function that expands a short seed (length s) into a long random-looking string (length n) with s much smaller than n
Weaknesses of stream ciphers
Still subject to two-time pad attacks (so vary the keystream with an IV or nonce) and still malleable
Block cipher definition
A pair of deterministic algorithms (E D) that encrypt and decrypt fixed-size blocks of l bits using a k-bit key
AES parameters
Block size 128 bits and key sizes 128 or 192 or 256 bits
3DES parameters
Block size 64 bits and key size 168 bits
How does a block cipher behave?
Like a pseudorandom permutation - flipping one bit of the ciphertext gives a random-looking plaintext on decryption (non-malleable at block level)
Downside of a block cipher
It only encrypts short fixed-size blocks - identical plaintext blocks give identical ciphertext blocks (the image-encrypted-block-by-block problem)
Block cipher modes
Ways to encrypt longer messages using a block cipher - use an integrated mode with authentication such as GCM
Cryptographic hash function definition
Function H from messages to tags that maps arbitrary-length input to a fixed-length output so that any change to the input changes the hash
Four properties of a cryptographic hash function
|M| much bigger than |T| - easy to compute - one-way (OWF) - collision resistant (CRF)
One-way property (OWF)
Given a hash value it is hard to find any message that maps to it
Collision resistance (CRF)
It is hard to find two different messages with the same hash
Do hash collisions exist?
Yes since M is much bigger than T - but finding one is computationally infeasible
Hash functions that are broken or weak
MD4 and MD5 and SHA-1 (broken over time)
Hash functions to use today
SHA-256 and SHA-512 and SHA-3
Why do hash functions get weaker over time?
Cryptanalysis and growing computing power - so output sizes get longer and new versions are standardised
How are crypto algorithms standardised?
Open competition: designers propose schemes and attack each other's - the one with the strongest analysis is chosen (no guarantee it stays secure forever)
Hash application: commitment
Publish H(v) now and reveal v later to prove you knew v first (e.g. auctions)
Two properties of a commitment
Binding (cannot open to a different value - from collision resistance) and hiding (commitment reveals nothing about the value)
Why is a plain hash commitment not hiding?
If the value is guessable the attacker hashes candidate values and compares with the published hash
How to fix a hash commitment
Add a secret random value r (salt) and publish H(v and r) - open by revealing both v and r
Hash application: file integrity
Publish the hash next to the file so users can verify it was not modified (e.g. SHA-256 for Debian packages)
Hash application: password storage
Store the salted hash of each password instead of the password - hash the entered password and compare
Purpose of a salt in password hashing
Stops precomputed tables (rainbow tables) and forces the attacker to do separate work for each user
Rainbow table
A precomputed table of hashes of many likely passwords
Hash application: key derivation
Derive new keys or passwords from a single secure key or password
Hash functions as building blocks
Used to build MACs and block ciphers and PRGs and Bitcoin proof of work and Merkle trees - the Swiss Army knife of symmetric crypto
Why is encryption alone not enough?
Ciphertexts can be malleable - e.g. with OTP an attacker can change the recipient of an encrypted bank transfer
Message authentication code (MAC) definition
Pair of algorithms (S V): S takes key and message and outputs a tag. V takes key and message and tag and outputs 1 (valid) or 0 (invalid)
MAC correctness
V(k m S(k m)) = 1 - a correctly generated tag always verifies
MAC unforgeability
It is hard to compute a valid message/tag pair without knowing the key k
What does a MAC protect?
Integrity and authenticity of a message (not confidentiality)
Authenticated encryption (AE)
Encryption that protects both confidentiality and integrity
Inputs to authenticated encryption
Key and nonce and message and associated data. E: K x N x M x A to C and D reverses it
Purpose of the nonce
Ensures the same message is not encrypted to the same ciphertext twice - can be random or just unique (e.g. a counter)
Associated data in AE
Optional public data that is authenticated but not encrypted
Example of an authenticated encryption scheme
AES-GCM (Advanced Encryption Standard in Galois Counter Mode)
What does symmetric crypto reduce the problem to?
Key management: where keys are generated and how and where stored and used and how revoked and replaced
Cryptography is NOT
The solution to all security problems - secure if badly implemented or deployed - something you will be able to invent after this course
Why is not everything encrypted?
Legacy design (the Internet had no security in mind) - key distribution (bootstrapping) problem - public-key crypto is 10-100x more expensive - post-quantum concerns
Why is public-key crypto slower than symmetric?
It needs big-number (modular) arithmetic - roughly 10 to 100 times more expensive
TLS / SSL
Transport Layer Security (successor of Secure Sockets Layer) - protocol securing Internet traffic such as HTTPS and e-commerce
SSH
Secure Shell - secure remote terminal login using both public-key and symmetric cryptography
VPN
Tunnels your Internet traffic to a server for privacy - but the VPN server sees all your data so it is a risk
Tor
Onion routing: traffic is encrypted in layers towards multiple hops and each hop peels off one layer
Password managers and crypto
Use a deliberately slow key derivation from the password so guessing the password is hard
Snowden revelations (crypto)
NSA ran programmes to subvert cryptography - often by finding sneaky ways to get keys rather than brute force
Signal protocol
Best-known secure messaging protocol - also used in WhatsApp
Why is crypto important for cloud storage?
You may not know which server stores your data so encrypting it matters even more
How will you be examined on crypto?
Conceptual understanding (what it is used for and how it works) - maths was deliberately left out - more maths in the asymmetric par