Onion routing with replies. (English) Zbl 1514.94110
Tibouchi, Mehdi (ed.) et al., Advances in cryptology – ASIACRYPT 2021. 27th international conference on the theory and application of cryptology and information security, Singapore, December 6–10, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13091, 573-604 (2021).
Summary: Onion routing (OR) protocols are a crucial tool for providing anonymous internet communication. An OR protocol enables a user to anonymously send requests to a server. A fundamental problem of OR protocols is how to deal with replies: ideally, we would want the server to be able to send a reply back to the anonymous user without knowing or disclosing the user’s identity.
Existing OR protocols do allow for such replies, but do not provably protect the payload (i.e., message) of replies against manipulation. C. Kuhn et al. [“Breaking and (partially) fixing provably secure onion routing”, in: Proceedings of the 2020 IEEE symposium on security and privacy, SP ’20. Los Alamitos, CA: IEEE Computer Society. 168–185 (2020; doi:10.1109/SP40000.2020.00039)] show that such manipulations can in fact be leveraged to break anonymity of the whole protocol.
In this work, we close this gap and provide the first framework and protocols for OR with protected replies. We define security in the sense of an ideal functionality in the universal composability model, and provide corresponding (less complex) game-based security notions for the individual properties.
We also provide two secure instantiations of our framework: one based on updatable encryption, and one based on succinct non-interactive arguments (SNARGs) to authenticate payloads both in requests and replies. In both cases, our central technical handle is an implicit authentication of the transmitted payload data, as opposed to an explicit, but insufficient authentication (with MACs) in previous solutions. Our results exhibit a new and surprising application of updatable encryption outside of long-term data storage.
For the entire collection see [Zbl 1510.94003].
Existing OR protocols do allow for such replies, but do not provably protect the payload (i.e., message) of replies against manipulation. C. Kuhn et al. [“Breaking and (partially) fixing provably secure onion routing”, in: Proceedings of the 2020 IEEE symposium on security and privacy, SP ’20. Los Alamitos, CA: IEEE Computer Society. 168–185 (2020; doi:10.1109/SP40000.2020.00039)] show that such manipulations can in fact be leveraged to break anonymity of the whole protocol.
In this work, we close this gap and provide the first framework and protocols for OR with protected replies. We define security in the sense of an ideal functionality in the universal composability model, and provide corresponding (less complex) game-based security notions for the individual properties.
We also provide two secure instantiations of our framework: one based on updatable encryption, and one based on succinct non-interactive arguments (SNARGs) to authenticate payloads both in requests and replies. In both cases, our central technical handle is an implicit authentication of the transmitted payload data, as opposed to an explicit, but insufficient authentication (with MACs) in previous solutions. Our results exhibit a new and surprising application of updatable encryption outside of long-term data storage.
For the entire collection see [Zbl 1510.94003].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Ando, M., Lysyanskaya, A.: Cryptographic shallots: a formal treatment of repliable onion encryption. eprint (2020). https://eprint.iacr.org/2020/215.pdf |
| [2] | Backes, M., et al.: Provably secure and practical onion routing. In: Computer Security Foundations Symposium, pp. 369-385 (2012) |
| [3] | Bitansky, N., et al.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: ITCS (2012) · Zbl 1347.68129 |
| [4] | Camenisch, J.; Lysyanskaya, A.; Shoup, V., A formal treatment of onion routing, Advances in Cryptology - CRYPTO 2005, 169-187 (2005), Heidelberg: Springer, Heidelberg · Zbl 1145.94460 · doi:10.1007/11535218_11 |
| [5] | Canetti, R.; Krawczyk, H.; Nielsen, JB; Boneh, D., Relaxing chosen-ciphertext security, Advances in Cryptology - CRYPTO 2003, 565-582 (2003), Heidelberg: Springer, Heidelberg · Zbl 1122.94359 · doi:10.1007/978-3-540-45146-4_33 |
| [6] | Catalano, D., Fully non-interactive onion routing with forward secrecy, Int. J. Inf. Secur., 12, 1, 33-47 (2013) · doi:10.1007/s10207-012-0185-2 |
| [7] | Catalano, D.; Fiore, D.; Gennaro, R., A certificateless approach to onion routing, Int. J. Inf. Secur., 16, 3, 327-343 (2016) · doi:10.1007/s10207-016-0337-x |
| [8] | Chaum, D.L.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM (1981) |
| [9] | Chen, C., Asoni, D.E., Barrera, D., Danezis, G., Perrig, A.: HORNET: high-speed onion routing at the network layer. In: ACM CCS (2015) |
| [10] | Chen, C., et al.: TARANET: traffic-analysis resistant anonymity at the NETwork layer. In: IEEE EuroS&P (2018) |
| [11] | Danezis, G., Goldberg, I.: Sphinx: a compact and provably secure mix format. In: IEEE S&P (2009) |
| [12] | Danezis, G., Laurie, B.: Minx: a simple and efficient anonymous packet format. In: WPES (2004) |
| [13] | Dingledine, R., Mathewson, N., Syverson, P.: Tor: the second-generation onion router. Technical report, Naval Research Lab Washington DC (2004) |
| [14] | Feigenbaum, J., Johnson, A., Syverson, P.: Probabilistic analysis of onion routing in a black-box model. ACM TISSEC (2012) |
| [15] | Fuchsbauer, G.; Abdalla, M.; Dahab, R., Subversion-zero-knowledge SNARKs, Public-Key Cryptography - PKC 2018, 315-347 (2018), Cham: Springer, Cham · Zbl 1385.94036 · doi:10.1007/978-3-319-76578-5_11 |
| [16] | Goldschlag, DM; Reed, MG; Syverson, PF; Anderson, R., Hiding routing information, Information Hiding, 137-150 (1996), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-61996-8_37 |
| [17] | Groth, J.; Maller, M.; Katz, J.; Shacham, H., Snarky signatures: minimal signatures of knowledge from simulation-extractable SNARKs, Advances in Cryptology - CRYPTO 2017, 581-612 (2017), Cham: Springer, Cham · Zbl 1410.94077 · doi:10.1007/978-3-319-63715-0_20 |
| [18] | Hayden, M.: The price of privacy: re-evaluating the NSA. In: Johns Hopkins Foreign Affairs Symposium, April 2014 |
| [19] | Kate, A., Zaverucha, G.M., Goldberg, I.: Pairing-based onion routing with improved forward secrecy. ACM TISSEC 13 (2010) |
| [20] | Klooß, M.; Lehmann, A.; Rupp, A.; Ishai, Y.; Rijmen, V., (R)CCA secure updatable encryption with integrity protection, Advances in Cryptology - EUROCRYPT 2019, 68-99 (2019), Cham: Springer, Cham · Zbl 1470.94092 · doi:10.1007/978-3-030-17653-2_3 |
| [21] | Kuhn, C., Beck, M., Strufe, T.: Breaking and (Partially) fixing provably secure onion routing. In: IEEE S&P (2020) |
| [22] | Kuhn, C., Hofheinz, D., Rupp, A., Strufe, T.: Onion routing with replies. Cryptology ePrint Archive, Report 2021/1178 (2021). https://ia.cr/2021/1178 |
| [23] | Mauw, S.; Verschuren, JHS; de Vink, EP; Samarati, P.; Ryan, P.; Gollmann, D.; Molva, R., A formalization of anonymity and onion routing, Computer Security - ESORICS 2004, 109-124 (2004), Heidelberg: Springer, Heidelberg · Zbl 1487.68072 · doi:10.1007/978-3-540-30108-0_7 |
| [24] | Micali, S.: CS proofs (extended abstracts). In: 35th FOCS, pp. 436-453 (1994) |
| [25] | Piotrowska, A.M., Hayes, J., Elahi, T., Meiser, S., Danezis, G.: The Loopix anonymity system. In: USENIX (2017) |
| [26] | Shimshock, E., Staats, M., Hopper, N.: Breaking and provably fixing minx. In: PETS (2008) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
