Advanced Concepts in Cryptography and Security
Explore the evolution of encryption techniques from historical schemes like Shift and Vigenere to modern methods like private-key encryption and message authentication codes. Learn about perfect secrecy, computational secrecy, and security against chosen-plaintext and chosen-ciphertext attacks in this insightful lecture series.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Cryptography Lecture 11
Historical schemes Shift, Vigenere, etc. They are all easy to attack They are not used anymore The point of this material was to motivate the need for a more formal treatment
Perfect secrecy A more formal approach Definitions Proofs Definition of perfect secrecy The one-time pad achieves this definition Several inherent drawbacks of perfect secrecy The one-time pad is not used
Private-key encryption If we want to overcome drawbacks of perfect secrecy, we must relax the definition Computational secrecy EAV-security (Computational) secrecy for encryption of one message We now need to rely on assumptions in order to prove security
Private-key encryption Pseudorandom generators/stream ciphers Formal definition For now, we simply assume these exist Pseudo-one-time pad (Provable) EAV-security based on any PRG Message length longer than key length Not secure when multiple messages encrypted, or against chosen-plaintext attacks
Private-key encryption CPA-security Security against chosen-plaintext attacks Requires randomized encryption! Pseudorandom functions/block ciphers Formal definition For now, we simply assume these exist (e.g., AES) Basic encryption scheme (Provable) CPA-security based on any PRF 2x ciphertext expansion
Private-key encryption Modes of encryption CBC-mode, CTR-mode are both CPA-secure, and have ciphertext expansion of one block Stream-cipher modes These are used extensively in the real world CCA-security Security against chosen-ciphertext attacks This is a real-world problem (cf. many attacks possible) None of the schemes we have seen so far satisfy this notion of security
Message authentication codes Integrity as an orthogonal security concern Secrecy and integrity are different Encryption and message authentication are different Message authentication codes, and definition of security Basic MAC from any PRF Short, fixed-length messages only
Message authentication codes Constructing a MAC on longer messages? Different attacks to watch out for (Basic) CBC-MAC Secure for fixed-length messages CBC-MAC Secure for arbitrary-length messages Used in the real world
Authenticated encryption Communication with secrecy and integrity An AE scheme is an encryption scheme that achieves both CCA-security Unforgeability Encrypt and authenticate is not a sound generic construction
Secrecy + integrity? We have shown primitives for achieving secrecy and integrity in the private-key setting What if we want to achieve both?
Authenticated encryption An encryption scheme that achieves both secrecy and integrity Secrecy notion: CCA-security Integrity notion: unforgeability Adversary cannot generate ciphertext that decrypts to a previously unencrypted message
Generic constructions Generically combine an encryption scheme and a MAC Useful when these are already available in some library Goal: the combination should be an authenticated encryption scheme when instantiated with any CPA-secure encryption scheme and any secure MAC
Generic constructions? Encrypt and authenticate Authenticate then encrypt Encrypt then authenticate
Encrypt and authenticate c, t k1, k2 k1, k2 m m = Deck1(c) Vrfyk2(m, t) = 1? c Enck1(m) t = Mack2(m)
Problems The tag t might leak information about m! Nothing in the definition of security for a MAC implies that it hides information about m So the combination may not even be EAV-secure If the MAC is deterministic (as is CBC-MAC), then the tag leaks whether the same message is encrypted twice I.e., the combination will not be CPA-secure
Authenticate then encrypt c k1, k2 k1, k2 m m | t = Deck1(c) Vrfyk2(m, t) = 1? t = Mack2(m) c Enck1(m | t)
Problems Counterexamples are possible The combination may not be CCA-secure
Encrypt then authenticate c, t k1, k2 k1, k2 m Vrfyk2(c, t) = 1? m = Deck1(c) c Enck1(m) t = Mack2(c)
Security? If the encryption scheme is CPA-secure and the MAC is secure (with unique tags) then this is an authenticated encryption scheme It achieves something even stronger: Given ciphertexts corresponding to (chosen) plaintexts m1, , mk, it is infeasible for an attacker to generate any new, valid ciphertext!
Authenticated encryption Encrypt-then-authenticate (with independent keys) is the recommended generic approach for constructing authenticated encryption In fact, academia tend to use a stronger integrity notion --- integrity of ciphertext Adversary cannot forge a new ciphertext (Not required in this course)
Direct constructions Other, more-efficient constructions have been proposed and are an active area of research and standardization E.g., OCB, CCM, GCM, SIV Others Active competition: https://competitions.cr.yp.to/caesar.html
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 state Can use authenticated encryption
Enck(m1) Enck(m2) k k Enck(m3)
Replay attack Enck(m1) Enck(m2) Enck(m1) k k
Re-ordering attack Enck(m1) Enck(m2) Enck(m2) Enck(m1) k k
Reflection attack Enck(m1) Enck(m2) k k Enck(m2)
Secure sessions These attacks (and others) can be prevented using counters/sequence numbers and identifiers
Enck(Bob| m1 | 1) Enck( Bob | m2 | 2) k k Enck( Alice | m3 | 1)
Secure sessions These attacks (and others) can be prevented using counters and identifiers Can also use a directionality bit in place of identifiers
