Cryptography
Lecture 11
Historical schemes
Shift,Vigenere, etc.They are all easy to attackThey are not used anymoreThe point of this material was to motivate the need for a more formal treatment
Perfect secrecy
A more formal approachDefinitionsProofsDefinition of perfect secrecyThe one-time pad achieves this definitionSeveral inherent drawbacks of perfect secrecyThe one-time pad is not used
Private-key encryption
If we want to overcome drawbacks of perfect secrecy, we must relax the definitionComputational secrecyEAV-security(Computational) secrecy for encryption of one messageWe now need to rely onassumptionsin order to prove security
Private-key encryption
Pseudorandom generators/stream ciphersFormal definitionFor now, we simply assume these existPseudo-one-time pad(Provable) EAV-security based on any PRGMessage length longer than key lengthNot secure when multiple messages encrypted, or against chosen-plaintext attacks
Private-key encryption
CPA-securitySecurity against chosen-plaintext attacksRequires randomized encryption!Pseudorandom functions/block ciphersFormal definitionFor now, we simply assume theseexist (e.g., AES)Basic encryption scheme(Provable)CPA-securitybased on anyPRF2xciphertextexpansion
Private-key encryption
Modes of encryptionCBC-mode, CTR-mode are both CPA-secure, and haveciphertextexpansion of one blockStream-cipher modesThese are used extensively in the real worldCCA-securitySecurity against chosen-ciphertextattacksThis is a real-world problem (cf.manyattackspossible)None of the schemes we have seen so far satisfy this notion of security
Message authentication codes
Integrity as an orthogonal security concernSecrecy and integrity are differentEncryption and message authentication are differentMessage authentication codes, and definition of securityBasic MAC from any PRFShort, fixed-length messages only
Message authentication codes
Constructing a MAC on longer messages?Different attacks to watch out for(Basic) CBC-MACSecure for fixed-length messagesCBC-MACSecure for arbitrary-length messagesUsed in the real world
Authenticated encryption
Communication with secrecyandintegrityAn AE scheme is an encryption scheme that achieves bothCCA-securityUnforgeabilityEncrypt and authenticate is not a sound generic construction
Authenticated encryption
Secrecy + integrity?
We have shown primitives for achievingsecrecyandintegrityin the private-key settingWhat if we want to achieve both?
Authenticated encryption
An encryption scheme that achieves both secrecy and integritySecrecy notion: CCA-securityIntegrity notion:unforgeabilityAdversary cannot generateciphertextthat decrypts to a previously unencrypted message
Generic constructions
Generically combine an encryption scheme and a MACUseful when these are already available in some libraryGoal: the combination should be an authenticated encryption scheme when instantiated withanyCPA-secure encryption scheme andanysecure MAC
Generic constructions?
Encrypt and authenticateAuthenticate then encryptEncrypt then authenticate
mc Enck1(m)t= Mack2(m)
k1, k2
m = Deck1(c)Vrfyk2(m, t) = 1?
c, t
k1, k2
Encrypt and authenticate
Problems
The tag t might leak information about m!Nothing in the definition of security for a MAC implies that it hides information about mSo the combination may not even be EAV-secureIf the MAC is deterministic (as is CBC-MAC), then the tag leaks whether the same message is encrypted twiceI.e., the combination will not be CPA-secure
mt = Mack2(m)c Enck1(m | t)
k1, k2
m| t = Deck1(c)Vrfyk2(m, t) = 1?
c
k1, k2
Authenticate then encrypt
Problems
Counterexamples are possibleThe combination may not beCCA-secure
mc Enck1(m)t= Mack2(c)
k1, k2
Vrfyk2(c,t) = 1?m = Deck1(c)
c, t
k1, k2
Encrypt then authenticate
Security?
If the encryption scheme is CPA-secure and the MAC is secure (with unique tags) then this is an authenticated encryption schemeIt achievessomething even stronger:Givenciphertextscorresponding to (chosen) plaintexts m1,…,mk, it is infeasible for an attacker to generateanynew, validciphertext!
Authenticated encryption
Encrypt-then-authenticate (with independent keys) isthe recommended generic approach for constructing authenticated encryptionInfact,academiatendtouseastrongerintegritynotion---integrityofciphertextAdversarycannotforgeanewciphertext(Notrequiredinthiscourse)
Direct constructions
Other,more-efficientconstructions have been proposed and are an active area of research and standardizationE.g., OCB, CCM, GCM,SIVOthers…Active competition: https://competitions.cr.yp.to/caesar.html
Secure sessions
Secure sessions?
Consider parties who wish to communicate securely over the course of a session“Securely” = secrecy and integrity“Session” = period of time over which the parties are willing to maintain stateCan use authenticated encryption…
k
Enck(m1)
k
Enck(m2)
Enck(m3)
k
Enck(m1)
k
Replay attack
Enck(m2)
Enck(m1)
k
Enck(m1)
k
Re-ordering attack
Enck(m2)
Enck(m1)
Enck(m2)
k
Enck(m1)
k
Reflection attack
Enck(m2)
Enck(m2)
Secure sessions
These attacks (and others) can be prevented usingcounters/sequence numbersandidentifiers
k
Enck(“Bob”| m1| 1)
k
Enck(“Bob” | m2| 2)
Enck(“Alice” | m3| 1)
Secure sessions
These attacks (and others) can be prevented usingcountersandidentifiersCan also use adirectionality bitin place of identifiers
0
Embed
Upload