Key-Indistinguishability and Robustness.

This presentation on Key-Indistinguishability and Robustness in Anonymous Encryption, given in Rennes on 07/11/2014, by Cristina Onetemaria from CIDRE/INRIA, delves into the intricacies of secure encryption techniques and their implications in preserving anonymity.

• Encryption
• Anonymity
• Security
• Key-Indistinguishability
• Rennes

arriankw Follow

Uploaded on Feb 19, 2025 | 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.

Presentation Transcript

1. Key-Indistinguishability and Robustness. Anonymous Encryption. Rennes, 07/11/2014 Cristina Onete maria-cristina.onete@irisa.fr CIDRE/ INRIA

2. What is anonymity? Anonymous: from anonymos (Greek) , meaning nameless : without any name ackowledged, whose name is withheld. Lacking individuality, unique character, or distinction English Dictionary, Dictionary.com Anonyme/anonymat: du grec anonymos , ce qui veut dire sans nom : se dit de quelqu un dont on ignore le nom, la qualit de ce qui est sans nom ou sans renomm e. Larousse, www.larousse.fr; Wikipedia, fr.wikipedia.org Cristina Onete || 07/11/2014 || 2

3. Encryption B B Am lie Baptiste Security guarantees: Message confidentiality: ciphertext hides plaintext ?? ? = Enc?? (?) ? ?? Random-looking Cristina Onete || 07/11/2014 || 3

4. Encryption ? = "????? ?????!" Encrypted with 2048-bit RSA key -----BEGIN PGP MESSAGE----- wcBMAxDZjxP1noe7AQf+M0T6qNMgf7I2T0ADeUdwmx4J9uxGBFdptH0 RPOGbwLIeGjcKG6PZpemKCtu5iRVCfgE/iMBvE0bxMIWaesxBawBElm3R L8PZ6ZjREWYgDfNJmazpDCraLXnSNJEFVxRkQWApUfw2QMLGf0OVMj5 CRpkd/XjHaMkNEfe+F6M2tUxuxpzdTEMGWxZ+ESrP/gACxTTy3ewm7xl uztdXaracw7RV1UbpM4+9UPBce1kIzPn68w7uIOEZvhEGPeipLAKL8FC3J C9+rAEbDXf+nGZiRPyFQuJn2Pz3Cv+IxZ43hDsSctjLvxUxVMNCEz3QcR mpPXN6h5f7TTFFN2fMdRwOrdJEAdaJt3aE5I5ssJlfxJzBDH1dc8eVfH2d7 9AAUo6chn25kyGQRUvtYfto057ae5Jvl8mpipy37wZKIuKK52D57VNW1x A==2X4l -----END PGP MESSAGE----- Cristina Onete || 07/11/2014 || 4

5. Plaintext Security Plaintext-hiding: The attacker can t get the full plaintext B B What if the message space is small? Cristina Onete || 07/11/2014 || 5

6. Plaintext Security Ciphertext Indistinguishability (IND-CCA) B B 1/2 ??? 1/2 Not even 1 bit of the message is leaked! Cristina Onete || 07/11/2014 || 6

7. Plaintext Security Plaintext Space Ciphertext Space B Cristina Onete || 07/11/2014 || 7

8. Goal: receiver anonymity Make ciphertext hide the receiver Baptiste B ? = Enc?? (?) ? Am lie Charles ??? Cristina Onete || 07/11/2014 || 8

9. Contents Key Indistinguishability IK-CCA IND-CCA vs. IK-CCA IK-CCA of RSA and ElGamal-based systems Robustness of Encryption Weak and Strong Robustness Robustness of RSA and ElGamal WROB- and SROB encryption schemes Receiver-anonymous encryption Construction and limitations

10. Key-(in)distinguishability Baptiste B ? = Enc?? (?) ? Am lie Charles Ciphertext hides the message Does it also hide the recipient (the pk used for encryption)? Not necessarily! Counterexample: take ? (??, Enc??(?)) Cristina Onete || 07/11/2014 || 10

11. Key-(in)distinguishability Goal: ciphertext hides the key under which it was created B B C B ??? B 1/2 1/2 C IK-CCA: Can t tell whether it was one key or the other Cristina Onete || 07/11/2014 || 11

12. IND-CCA, but not IK-CCA Plaintext Space Ciphertext Space B C Cristina Onete || 07/11/2014 || 12

13. IND-CCA and IK-CCA Plaintext Space Ciphertext Space B C Cristina Onete || 07/11/2014 || 13

14. RSA is not IK-CCA Textbook RSA: Key Generation: Primes ?,? of size ?. Define ? = ??, ? ? = (? 1)(? 1) Public key: choose ? s.t. ??? ?,? ? = 1. Now ?? = (?,?) Secret key: find inverse ? of ?: ?? = 1 ??? ? ? . Now ?? = ? Encryption (using pk = (e, N)): ? ?????? = ?? (??? ?) Decryption (using sk = d): ? ?????? = ?? (??? ?) Cristina Onete || 07/11/2014 || 14

15. RSA is not IK-CCA Case I: Moduli of different length ??1= (?1,?1) , with length ?1 = ?1(say 512 bits) ??2= (?2,?2) , with length ?2 = ?2(say 1024 bits) ? ?? ?? ?????????? ????? ??1 ???? ?? 512 ????,? ??? ?? ?? ???????? ????? ??2 ???? ?? 1024 ???? ???? When Adv. gives a message m and the two pk s, she just needs to look at the length of the outcome Cristina Onete || 07/11/2014 || 15

16. RSA is not IK-CCA Case II: Moduli of same length ??1= (?1,?1) ??2= (?2,?2) Let ?1> ?2 ?? ?????????? ????? ??1 ??? ?? ?????? ? ?? ?2 Because the encryption of any message m has to cover the output space well: Prob ?????1? > ?2 is significant ? ?? ?? ?????????? ????? ??2 ???? ?? ??????? ? ?? ?2,? ??? Cristina Onete || 07/11/2014 || 16

17. ElGamal is IK-CCA Textbook ElGamal: Key Generation: Prime ? of size ? s.t. 2q + 1 also prime. Let G?= < ? > Secret key: choose ?? {1, ? 1}. Public key: ?? = ??? (??? ?) Encryption: Choose random ? {1, ,? 1}. Set ?1 ?? (??? ?) Set ?2 ? ??? (??? ?). Send: ? = (?1,?2) Decryption: Compute: ? = ?2 / ?1 ?? (??? ?) Cristina Onete || 07/11/2014 || 17

18. ElGamal is IK-CCA Intuition: All pk s in the same group All ciphertexts are of the same length and format Given ??1, the encryption of ? is: ?1) ? = (??1,? ??1 Given ??2, the encryption of ? is: ?2) ? = (??2,? ??2 Output is identically distributed Cristina Onete || 07/11/2014 || 18

19. Contents Key Indistinguishability IK-CCA IND-CCA vs. IK-CCA IK-CCA of RSA and ElGamal-based systems Robustness of Encryption Weak and Strong Robustness Robustness of RSA and ElGamal WROB- and SROB encryption schemes Receiver-anonymous encryption Construction and limitations

20. Weak and Strong Robustness What happens if we get someone else s ciphertext? Theory: you can t decrypt it Security: you can t recover the message Practice: you ll recover a nonsense message B Baptiste Charles Robustness: can t decrypt other ciphertexts Cristina Onete || 07/11/2014 || 20

21. Why do we care? Our goal: receiver anonymity Baptiste B ? = Enc?? (?) ? Am lie Charles ??? Cristina Onete || 07/11/2014 || 21

22. Why do we care? Setting: Am lie wants to send ? to Baptiste anonymously She encrypts ?under Baptiste s public key, then broadcasts the ciphertext to multiple receivers How do the receivers know whether the ciphertext was for them or not? Robust encryption: If ? was encrypted for someone else, the ciphertext decrypts to an error symbol Cristina Onete || 07/11/2014 || 22

23. Weak Robustness Honestly encrypted ciphertext is robust B B C B Cristina Onete || 07/11/2014 || 23

24. Strong Robustness Adversary-chosen ciphertext is robust B B C B At most 1 decryption Cristina Onete || 07/11/2014 || 24

25. RSA and ElGamal not robust RSA Encryption ElGamal Encryption Encryption Encryption ? = ?1,?2 = (??,? ???) ? ?????? = ?? (??? ?) Decryption (with ?) Decryption (with ??) ? ?????? = ?? (??? ?) ?? (??? ?) ? = ?2 ?1 Decryption (with ? ) Decryption (with ?? ) ?? = ? ??? ? = ??? ?? ??? ? = ? ??? ? /?? ??; ??? ? ?2 / ?1 = ? ??(?? ?? ) = ? Cristina Onete || 07/11/2014 || 25

26. Strongly Robust Encryption Modified Cramer-Shoup (finite fields) Setting: cyclic group G?of prime order ? two generators ?1and ?2of G? choose random ? ? Keys??? Key generation: pick ??,??,??,??,??,?? ? {0 ? 1} set ? = ?1 Encrypt ?: pick ? ?{1 ? 1}, set ?? ?1 set ? ? ?, ? ?(?;?1?2 ?), ? ????? ?1?2 ?2, ? = ?1 ?1?2 ?2, ? = ?1 ?1?2 ?2 ?, ?? ?2 ? ?1?2 ?2 Decrypt (?1,?2,?,?): do ? = ?(?;?1?2 ?), ? = ? ?1 ?1+? ?1?2 ?2+? ?2set ? = if ?1 1 or ? ?1 Cristina Onete || 07/11/2014 || 26

27. Contents Key Indistinguishability IK-CCA IND-CCA vs. IK-CCA IK-CCA of RSA and ElGamal-based systems Robustness of Encryption Weak and Strong Robustness Robustness of RSA and ElGamal WROB- and SROB encryption schemes Receiver-anonymous encryption Construction and limitations

28. Receiver-anonymous encryption Our goal: receiver anonymity Baptiste B ? = Enc?? (?) ? Am lie Charles ??? Cristina Onete || 07/11/2014 || 28

29. Construction & Limitations Use IK-CCA and SROB encryption Adversary won t know whom a ciphertext is for B ? = Enc?? (?) Baptiste ? Am lie Charles ??? Cristina Onete || 07/11/2014 || 29

30. Construction & Limitations Use IK-CCA and SROB encryption What if the adversary waits for an answer? B ? = Enc?? (?) Baptiste ? Am lie Charles Cristina Onete || 07/11/2014 || 30

31. Constructions & Limitations Use onion routing use routers to encrypt and send messages between sender and receiver Source: cdn.arstechnica.net Cristina Onete || 07/11/2014 || 31

32. MRI students: papers Karame, Androulaki, Capkun: Two Bitcoins at the Price of One? Double-spending attacks on fast pay- ments in Bitcoin https://eprint.iacr.org/2012/248.pdf Burmester, Desmedt: A Secure and Efficient Con- ference Key Distribution System http://www.cs.fsu.edu/~langley/Eurocrypt/euro-pre.pdf Sarkar, Fitzgerald: Attacks on SSL. A comprehen- sive study of BEAST, CRIME, TIME, BREACH, LUCKY 13 & RC4 biases https://www.isecpartners.com/media/106031/ssl_attacks_survey.pdf Cristina Onete || 07/11/2014 || 32

33. MRI students: papers BSI: Advanced Security Mechanisms for Machine- Readable Travel Documents Part 2 https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publ ications/TechGuidelines/TR03110/TR- 03110_v2.1_P2pdf.pdf;jsessionid=A06695D3F0DCA020B98B4 CAC8946CD13.2_cid294?__blob=publicationFile Bordes: BitLocker https://www.sstic.org/media/SSTIC2011/SSTIC- actes/bitlocker/SSTIC2011-Article-bitlocker-bordes.pdf Fluhrer, Matin, Shamir: Weaknesses in the Key Sche- duling Algorithm of RC4 http://merlot.usc.edu/cs531-s11/papers/Fluhrer01a.pdf Cristina Onete || 07/11/2014 || 33

34. MRI students: papers Montalvo, Defrance, Lefebvre, Le Scouarnec, P rez: Syst me de stockage-en-ligne avec confidentialit des donn es personnelles https://www.sstic.org/media/SSTIC2011/SSTIC-actes/ systeme_de_stockage-en-ligne_de_photos_avec_confid/ SSTIC2011-Article-systeme_de_stockage-en-ligne_de_photos_ avec_confidentialite_des_donnees_personnelles-montalvo.pdf Marechal: tat de l art sur le cassage de mots de passe https://www.sstic.org/media/SSTIC2007/SSTIC- actes/Etat_de_l_art_cassage_de_mots_de_passe/SSTIC2007- Article-Etat_de_l_art_cassage_de_mots_de_passe-marechal.pdf Cristina Onete || 07/11/2014 || 34

35. MRI students: papers Shi, Chan, Stefanov, Li: Oblivious RAM with O((log N)3) Worse-Case Cost https://eprint.iacr.org/2011/407.pdf Curtmola, Garay, Kamara, Ostrovsky: Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions http://eprint.iacr.org/2006/210.pdf Dodis, Pointcheval, Ruhault, Vergnaud, Wichs: Se- curity Analysis of Pseudo-Random Number Generators with Input: /dev/random is not robust https://eprint.iacr.org/2013/338.pdf Cristina Onete || 07/11/2014 || 35

36. MRI students: papers Bellare, Paterson, Rogaway: Security of Symmetric Encryption against Mass Surveillance https://eprint.iacr.org/2014/438.pdf Cristina Onete || 07/11/2014 || 36

37. Thanks! CIDRE/ INRIA