Abstract
We propose a way to establish peer-to-peer authenticated communications over an insecure channel by using an extra channel which can authenticate very short strings, e.g. 15 bits.We call this SAS-based authentication as for authentication based on Short Authenticated Strings. The extra channel uses a weak notion of authentication in which strings cannot be forged nor modified, but whose delivery can be maliciously stalled, canceled, or replayed. Our protocol is optimal and relies on an extractable or equivocable commitment scheme.
This approach offers an alternative (or complement) to public-key infrastructures, since we no longer need any central authority, and to password-based authenticated key exchange, since we no longer need to establish a confidential password. It can be used to establish secure associations in ad-hoc networks. Applications could be the authentication of a public key (e.g. for SSH or PGP) by users over the telephone, the user-aided pairing of wireless (e.g. Bluetooth) devices, or the restore of secure associations in a disaster case, namely when one remote peer had his long-term keys corrupted.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Digital Signature Standard (DSS). Federal Information Processing Standards publication #186-2. U.S. Department of Commerce, National Institute of Standards and Technology (2000)
Specification of the Bluetooth System. Core System Package, vol. 2. Bluetooth Specification version 1.2 (2003)
Abdalla, M., Fouque, P.-A., Pointcheval, D.: Password-Based Authenticated Key Exchange in the Three-Party Setting. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 65–84. Springer, Heidelberg (2005)
Balfanz, D., Smeeters, D.K., Stewart, P., ChiWong, H.: Talking to Strangers: Authentication in Ad-Hoc Wireless Networks. In: Network and Distributed System Security Symposium Conference (NDSS 2002), San Diego, California, USA. The Internet Society (2002)
Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated Key Exchange Secure against Dictionary Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 139–155. Springer, Heidelberg (2000)
Bellare, M., Rogaway, P.: Entity Authentication and Key Distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994)
Bellare, M., Rogaway, P.: Provably Secure Session Key Distribution: the Three Party Case. In: Proceedings of the 27th ACM Symposium on Theory of Computing, Las Vegas, Nevada, USA, pp. 57–66. ACM Press, New York (1995)
Bellovin, S.M., Merritt, M.: Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks. In: IEEE symposium on Research in Security and Privacy, Oakland, California, USA, pp. 72–84. IEEE Computer Society Press, Los Alamitos (1992)
Bellovin, S.M., Merritt, M.: Augmented Encrypted Key Exchange. In: 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, pp. 244–250. ACM Press, New York (1993)
Bennett, C.H., Brassard, G.: Quantum Cryptography: Public Key Distribution and Coin Tossing. In: Proc. IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India, pp. 175–179. IEEE Press, Los Alamitos (1984)
Boneh, D.: The Decision Diffie-Hellman Problem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 48–63. Springer, Heidelberg (1998)
Boyd, C., Mathuria, A.: Protocols for Authentication and Key Establishment. In: Information Security and Cryptography. Springer, Heidelberg (2003)
Čagalj, M., Čapkun, S., Hubaux, J.-P.: Key Agreement in Peer-to-Peer Wireless Networks. To appear in the Proceedings of the IEEE (Fall 2005)
Cramer, R., Shoup, V.: Signature Schemes based on the Strong RSA Assumption. ACM Transactions on Information and System Security 3, 161–185 (2000)
Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-Interactive and Non-Malleable Commitment. In: Proceedings of the 30th ACM Symposium on Theory of Computing, Dallas, Texas, USA, pp. 141–150. ACM Press, New York (1998)
Di Crescenzo, G., Katz, J., Ostrovsky, R., Smith, A.: Efficient and Non-Interactive Non- Malleable Commitments. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 40–59. Springer, Heidelberg (2001)
Damgård, I., Groth, J.: Non-interactive and Reusable Non-malleable Commitment Schemes. In: Proceedings of the 35th ACM Symposium on Theory of Computing, San Diego, California, USA, pp. 426–437. ACM Press, New York (2003)
Diffie, W., Hellman, M.E.: New Directions in Cryptography. IEEE Transactions on Information Theory IT-22, 644–654 (1976)
Dierks, T., Allen, C.: The TLS Protocol Version 1.0. RFC 2246, standard tracks. The Internet Society (1999)
Dolev, D., Dwork, C., Naor, M.: Non-Malleable Cryptography. SIAM Journal of Computing 30, 391–437 (2000)
Gehrmann, C., Mitchell, C., Nyberg, K.: Manual Authentication for Wireless Devices. RSA Cryptobytes 7, 29–37 (2004)
Gehrmann, C., Nyberg, K.: Security in Personal Area Networks. In: Mitchell, C. (ed.) Security for Mobility, pp. 191–230. IEE (2004)
Haller, N.: The S/KEY One-Time Password System. RFC 1760 (1995)
Håstad, J., Impagliazzo, R., Levin, L., Luby, M.: A Pseudorandom Generator from any Oneway Function. SIAM Journal on Computing 4, 1364–1396 (1999)
Hoepman, J.-H.: The Ephemeral Pairing Problem. In: Juels, A. (ed.) FC 2004. LNCS, vol. 3110, pp. 212–226. Springer, Heidelberg (2004)
Hoepman, J.-H.: Ephemeral Pairing on Anonymous Networks. In: Hutter, D., Ullmann, M. (eds.) SPC 2005. LNCS, vol. 3450, pp. 101–116. Springer, Heidelberg (2005)
Housley, R., Ford, W., Polk, W., Solo, D.: Internet X.509 Public Key Infrastructure Certificate and CRL Profile. Internet Standard. RFC 2459, The Internet Society (1999)
Jakobsson, M., Wetzel, S.: Security Weaknesses in Bluetooth. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 176–191. Springer, Heidelberg (2001)
Katz, J., Ostrovsky, R., Yung, M.: Efficient Password-Authenticated Key Exchange using Human-Memorable Passwords. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 475–494. Springer, Heidelberg (2001)
Kohl, J., Neuman, C.: The Kerberos Network Authentication Service (V5). Internet standard. RFC 1510 (1993)
MacKenzie, P., Yang, K.: On Simulation-Sound Trapdoor Commitments. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 382–400. Springer, Heidelberg (2004)
Merkle, R.C.: Secure Communications over Insecure Channels. Communications of the ACM 21, 294–299 (1978)
Mitchell, C., Ward, M., Wilson, P.: On Key Control in Key Agreement Protocols. Electronics Letters 34, 980–981 (1998)
Needham, R.M., Schroeder, M.D.: Using Encryption for Authentication in Large Networks of Computers. Communications of the ACM 21, 993–999 (1978)
Nyberg, K.: IKE in Ad-hoc IP Networking. In: Castelluccia, C., Hartenstein, H., Paar, C., Westhoff, D. (eds.) ESAS 2004. LNCS, vol. 3313, pp. 139–151. Springer, Heidelberg (2005)
Pasini, S., Vaudenay, S.: Optimized Message Authentication Protocols (unpublished)
Pass, R.: On Deniability in the Common Reference String and Random Oracle Model. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 316–337. Springer, Heidelberg (2003)
Peyrin, T., Vaudenay, S.: The Pairing Problem with User Interaction. In: Security and Privacy in the Age of Ubiquitous Computing IFIP TC11 20th International Information Security Conference (SEC 2005), Chiba, Japan, pp. 251–265. Springer, Heidelberg (2005)
Rivest, R.L., Shamir, A., Adleman, L.M.: A Method for Obtaining Digital Signatures and Public-key Cryptosystem. Communications of the ACM 21, 120–126 (1978)
Stajano, F., Anderson, R.: The Resurrecting Duckling: Security Issues for Ad-hoc Wireless Networks. In: Malcolm, J.A., Christianson, B., Crispo, B., Roe, M. (eds.) Security Protocols 1999. LNCS, vol. 1796, pp. 172–194. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vaudenay, S. (2005). Secure Communications over Insecure Channels Based on Short Authenticated Strings. In: Shoup, V. (eds) Advances in Cryptology – CRYPTO 2005. CRYPTO 2005. Lecture Notes in Computer Science, vol 3621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535218_19
Download citation
DOI: https://doi.org/10.1007/11535218_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28114-6
Online ISBN: 978-3-540-31870-5
eBook Packages: Computer ScienceComputer Science (R0)