CSE 127: Computer Security Symmetric-key Cryptography
George Obaido
Some slides adopted from , , and
Copyright By PowCoder代写 加微信 powcoder
Cryptography
A tremendous tool
The basis for many security mechanisms
➤ Used: ATM Machines, Bitcoin, Browsers (TLS), Google authenticator, etc.
The solution to all security problems
Reliable unless implemented and used properly Something you should try to invent yourself
Another word for blockchain
How Does It Work?
Goal: learn how to use crypto primitives correctly
We will treat them as a black box that mostly does what it says
To learn what’s inside the black box take CSE 107
Do not roll your own crypto*
* Exceptions: You are . Bernstein, Joan Daemen, , , or
similar, or you have finished your PhD in cryptography under an advisor of that caliber, and you r work has been accepted at Crypto, Eurocrypt, Asiacrypt, FSE, or PKC and/or NIST is running another competition, and then wait several years for full standardization and community vetting.
How Does It Work?
Goal: learn how to use crypto primitives correctly
To learn what’s inside black box take CSE 107
Do not roll your own crypto*
* Exceptions: You are . Bernstein, Joan Daemen, , , or
We will treat them as a black box that mostly does what it says
similar, or you have finished your PhD in cryptography under an advisor of that caliber, and your work has been accepted at Crypto, Eurocrypt, Asiacrypt, FSE, or PKC and/or NIST is running another competition, and then wait several years for full standardization and community vetting.
Real-world crypto: SSL/TLS
1. Browser and web server run “handshake protocol’’:
Establishes shared secret key using public-key cryptography (next lecture)
2. Browser and web server use negotiated key to communicate.
Real-world crypto: File encryption
Password Decrypted data
Files are symmetrically encrypted with a secret key
The symmetric key is stored encrypted or in tamperproof hardware.
The password is used to unlock the key so the data can be decrypted.
This class: secure communication
Authenticity: Parties cannot be impersonated Secrecy/Confidentiality: No one else can read messages Integrity: Messages cannot be modified
Passive attacker: Eve only snoops on channel
Active attacker: Eve can snoop, inject, block, tamper, etc.
Outline Symmetric-key crypto
Next time: asymmetric (public-key) crypto
Encryption
Hash functions
Message authentication codes (MAC)
Key exchange Digital signatures
Symmetric-key encryption
mEc cDm kk
Encryption: (key, plaintext) → ciphertext
Decryption: (key, ciphertext) → plaintext
Functional property: Where Dk(Ek(m)) = m
Symmetric-key encryption
mEc cDm kk
One-time key: used to encrypt one message
E.g., encrypted email, new key generate per email
Multi-use key: used to encrypt multiple messages
E.g., same key used to encrypt many packets
Symmetric-key encryption
mEc cDm kk
One-time key: used to encrypt one message
E.g., encrypted email, new key generate per email
Multi-use key: used to encrypt multiple messages
E.g., same key used to encrypt many packets
Symmetric-key encryption
One-time key: used to encrypt one message
E.g., encrypted email, new key generate per email
Multi-use key: used to encrypt multiple messages
E.g., same key used to encrypt many packets
Symmetric-key encryption
Need unique/random once
One-time key: used to encrypt one message
E.g., encrypted email, new key generate per email
Multi-use key: used to encrypt multiple messages
E.g., same key used to encrypt many packets
Security definition: Passive eavesdropper
Simplest security definition
How do you know an encryption scheme is secure against a passive eavesdropper?
Want: “Ciphertext reveals nothing about plaintext”
Informal formal definition: Given Ek(m1) and Ek(m2), attacker can’t distinguish which ciphertext encrypts which plaintext without key
Example: One Time Pad (OTP) Vernam (1917)
Plaintext: Ciphertext:
Encryption: c = Ek(m) = m ⨁ k
Decryption: Dk(c) = c ⨁ k = (m ⨁ k) ⨁k = m
Example: One Time Pad (OTP) Vernam (1917)
Plaintext: Ciphertext:
Encryption: c = Ek(m) = m ⨁ k
Decryption: Dk(c) = c ⨁ k = (m ⨁ k) ⨁k = m
OTP security Shannon (1949)
Problems with OTP
Information-theoretic security: without key, ciphertext reveals no “information” about plaintext
Can only use key once
Key is as long as the message
Computational cryptography Want to encrypt with shorter keys
Solution: Use a more practical security notion
Problem: information-theoretic security is impossible if key space is smaller than message space.
It should be infeasible for a computationally bounded attacker to violate security
In practice: attacks should take at least e.g., 2128 time
Quiz of the day
Convert the following into Ciphertexts using the Vernam’s OTP. Question 1
Plaintext: Ciphertext:
Question 2
Plaintext: Ciphertext:
Examples: ChaCha, Salsa, etc.
Symmetrical Cryptography
Sharif and Mansoor (2010)
Stream ciphers
Problem: OTP key is as long as message Solution: Pseudo random generator
Stream ciphers uses bit-by-bit to generate
ciphertext.
Computationally hard to distinguish from random
message ciphertext
Ek(m) = PRG(k) ⊕m
Examples: ChaCha, Salsa, etc.
Dangers in using stream ciphers Can we use a key more than once?
E.g., c1 ← m1 ⊕ PRG(k) c2 ← m2 ⊕ PRG(k)
Eavesdropper does: c1 c2 → m1 m2
Enough redundant information in English that: m1 m2 → m1 , m2
Dangers in using stream ciphers Can we use a key more than once?
E.g., c1 ← m1 ⊕ PRG(k) c2 ← m2 ⊕ PRG(k)
Eavesdropper does: c1 c2 → m1 m2
Enough redundant information in English that: m1m2 →m1,m2
Chosen plaintext attacks
Attacker can learn encryptions for arbitrary plaintexts Historical example:
During WWII the US Navy sent messages about Midway Island and watched Japanese ciphertexts to learn codename (“AF”)
WEP WiFi encryption has poor randomization and can result in the same stream cipher used multiple times
More recent (but still a bit old) example:
Block ciphers: crypto work horses
mEc cDm kk
Block cipher: permutation of fixed-size input block
Each input is mapped to one output (depends on key) Common examples:
E.g., 3DES: |m| = |c| = 64 bits, |k| = 168 bits
E.g., AES: |m| = |c| = 128 bits, |k| = 128, 192, 256
Correct block cipher choice: AES
Challenges with block ciphers
Block ciphers operate on single fixed-size block How do we encrypt longer messages?
Several modes of operation for longer messages
How do we deal with messages that are not block-aligned?
Must pad messages in a distinguishable way
Insecure block cipher usage: ECB mode
Source: wikipedia
Why is ECB so bad?
Source: wikipedia
Moderately secure usage: CBC mode with random IV
Subtle attacks that abuse padding possible!
Source: wikipedia
Better block cipher usage: CTR mode with random IV
Essentially use block cipher as stream cipher!
Source: wikipedia
What mode should you choose?
If your cryptolibrary is making you choose a block cipher mode of operation, use a different library.
(Right answer: block cipher mode of operation can be built into an AEAD mode (end of lecture).)
What security do we get?
All encryption breakable by brute force given enough knowledge about plaintext
Try to decrypt ciphertext with every possible key until a valid plaintext is found
Attack complexity proportional to size of key space
128-bit key requires 2128 decryption attempts
Chosen ciphertext attacks
What if Eve can alter the ciphertexts sent between Alice and Bob?
encryption alone is not enough to ensure security.
Need to protect integrity of ciphertexts (and thus underlying encrypted messages)
Outline Symmetric-key crypto
Encryption Hash functions√
Message authentication codes Asymmetric (public-key) crypto
Key exchange Digital signatures
Hash Functions
A (cryptographic) hash function maps arbitrary length input into a fixed-size string
|m| is arbitrarily large
|h| is fixed, usually 128-512 bits
Hash Function Properties Finding a preimage is hard
Given h, find m such that H(m)=h Finding a second preimage is hard
Given m1, find m2 such that H(m1)=H(m2)
Finding a collision is hard
Find m1 and m2 such that H(m1)=H(m2)
Hash function security
• A 128-bit hash function has 64 bits of security
Birthday bound: find collision in time 264
Real-world crypto: Hash functions
• Blockchain
Versioning systems (e.g., git)
Better than _1, _final, _really_final Sub-resource integrity
Integrity of files you include from CDN File download integrity
Make sure the thing you download is the thing you thought you were downloading
Popular broken hash functions MD5: Message Digest
SHA-1: Secure Hash Algorithm 1
Designed by Output: 128 bits
Designed by NSA Output: 160 bits
Hash functions SHA-2: Secure Hash Algorithm 2
SHA-3: Secure Hash Algorithm 3
Designed by NSA
Output: 224, 256, 384, or 512 bits
Result of NIST SHA-3 contest Output: arbitrary size Replacement once SHA-2 broken
Outline Symmetric-key crypto
Next time: asymmetric (public-key) crypto
Encryption
Hash functions
Message authentication code √
Key exchange Digital signatures
Chosen ciphertext attacks
What if Eve can alter the ciphertexts sent between Alice and Bob?
Symmetric encryption alone is not enough to ensure security.
Need to protect integrity of ciphertexts (and thus underlying encrypted messages)
Validate message integrity based on shared secret MAC: Message Authentication Code
Keyed function using shared secret
Hard to compute function without knowing key
HMAC construction • HMAC: MAC based on hash function
MACk(m) = H( k⊕opad ‖ H( k⊕ipad ‖ m ) )
HMAC-SHA256: HMAC construction using SHA-256
Other MAC constructions
In 2009, Flickr required API calls to use authentication token that looked like:
MD5( secret || arg1=val1&arg2=val2&…) Is MACk(m) = H(k || m) a secure MAC?
No! If H is MD5, SHA1 or SHA2 Use HMAC!
Other MAC constructions
In 2009, Flickr required API calls to use authentication token that looked like:
MD5( secret || arg1=val1&arg2=val2&…) Is MACk(m) = H(k || m) a secure MAC?
No! If H is MD5, SHA1 or SHA2 Use HMAC!
Combining MAC with encryption
MAC then Encrypt (SSL)
Integrity for plaintext not ciphertext
Issue: need to decrypt before you can verify integrity
Hard to get right!
Combining MAC with encryption
Encrypt and MAC (SSH)
Integrity for plaintext not ciphertext
➤ Issue: need to decrypt before you can verify integrity
Hard to get right!
Combining MAC with encryption
Encrypt then MAC (IPSec)
➤ Integrity for plaintext and ciphertext
Almost always right!
AEAD construction Authenticated Encryption with Associated Data
AES-GCM, AES-GCM-SIV
Always use an authenticated encryption mode
Combines mode of operation with integrity protection/ MAC in the right way
Good libraries have good defaults
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com