Publish on 03rd November 2019
Category: Birds
0

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

Cryptography - csee.umbc.edu