Cryptography Lecture 9: Padding Oracle Attack in CBC Mode Encryption
Learn about the Padding Oracle Attack in CBC mode encryption, where a bit of decrypted ciphertext can lead to revealing the entire plaintext. Explore the concepts of CCA-security, arbitrary-length messages, decryption techniques, and more in the field of cryptography.
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 9
Padding-oracle attack In the definition of CCA-security, the attacker can obtain the decryption of any ciphertext of its choice (besides the challenge ciphertext) Is this realistic? We show a scenario where: One bit about decrypted ciphertexts is leaked This can be exploited to learn the entire plaintext The scenario occurs in the real world! 2
CBC-mode encryption m2 ml m1 IV Fk Fk Fk c2 cl c0 c1 3
CBC-mode decryption m2 ml m1 F-1k F-1k F-1k c2 cl c0 c1 4
Arbitrary-length messages? Message encoded data ciphertext PKCS #5 encoding: Assume message is an integral # of bytes Let L be the block length (in bytes) of the cipher Let b 1 be # of bytes that need to be appended to the message to get length a multiple of L 1 b L; note b 0 Append b (encoded in 1 byte), b times I.e., if 3 bytes of padding are needed, append 0x030303 5
Decryption? To decrypt: Use CBC-mode decryption to obtain encoded data Say the final byte of encoded data has value b If b=0 or b > L, return error If final b bytes of encoded data are not all equal to b, return error Otherwise, strip off the final b bytes of the encoded data, and output what remains as the message 6
c k k c Enck(m) Deck(c') c Padding oracle! 7
CCA-security: a summary Chosen-ciphertext attacks represent a significant, real-world threat Modern encryption schemes are designed to be CCA-secure None of the schemes we have seen so far are CCA-secure why? Will see an example of a CCA-secure scheme later 8
Secrecy vs. integrity So far we have been concerned with ensuring secrecy of communication What about integrity? I.e., ensuring that a received message originated from the intended party, and was not modified Even if an attacker controls the channel! Standard error-correction techniques not enough! The right tool is a message authentication code
m, t m, t k k m Vrfyk(m , t ) = 1? t = Mack(m)
m, t k k m
k m, t m, t m, t m, t k Vrfyk(m, t)=1?
price=10 k cookie, t cookie cookie, t k cookie
Secrecy vs. integrity Secrecy and integrity are orthogonal concerns Possible to have either one without the other Sometimes you might want one without the other Most often, both are needed Encryption does not (in general) provide any integrity Integrity is even stronger than non-malleability None of the schemes we have seen so far provide any integrity
Message authentication code (MAC) A message authentication code is defined by three PPT algorithms (Gen, Mac, Vrfy): Gen: takes as input 1n; outputs k. (Assume |k| n.) Mac: takes as input key k and message m {0,1}*; outputs tag t t := Mack(m) Vrfy: takes key k, message m, and tag t as input; outputs 1 ( accept ) or 0 ( reject ) For all m and all k output by Gen, Vrfyk(m, Mack(m)) = 1
Security? Only one standard definition Threat model Adaptive chosen-message attack Assume the attacker can induce the sender to authenticate messages of the attacker s choice Security goal Existential unforgeability Attacker should be unable to forge a valid tag on any message not previously authenticated by the sender
m1, t1 k m2, t2 t1 := Mack(m1) t2 := Mack(m2) ti := Mack(mi) mi, ti m , t k Vrfyk(m , t ) ??
Formal definition Fix A, Define randomized experiment ForgeA, (n): 1. k Gen(1n) 2. A interacts with an oracle Mack( ) ; let M be the set of messages submitted to this oracle 3. A outputs (m, t) 4. A succeeds, and the experiment evaluates to 1, if Vrfyk(m, t)=1 and m M
Security for MACs is secure if for all PPT attackers A, there is a negligible function such that Pr[ForgeA, (n) = 1] (n)
Security? Is the definition too strong? We don t want to make any assumptions about what the sender might authenticate We don t want to make any assumptions about what forgeries are meaningful A MAC satisfying this definition can be used anywhere integrity is needed
Replay attacks Note that replay attacks are not prevented No stateless mechanism can prevent them Replay attacks are often a significant real- world concern Need to protect against replay attacks at a higher level Decision about what to do with a replayed message is application-dependent
Intuition? We need a keyed function Mac such that: Given Mack(m1), Mack(m2), , it is infeasible to predict the value Mack(m) for any m {m1, , } Let Mac be a pseudorandom function!
Construction Let F be a length-preserving pseudorandom function (aka block cipher) Construct the following MAC : Gen: choose a uniform key k for F Mack(m): output Fk(m) Vrfyk(m, t): output 1 iff Fk(m)=t Theorem: is a secure MAC
