FORSAKES: a forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. (English) Zbl 1366.94551
Summary: This paper suggests a model and a definition for forward-secure authenticated key exchange (AKE) protocols, which can be satisfied without depending on the Diffie-Hellman assumption. The basic idea is to use key-evolving schemes (KES), where the long-term keys of the system get updated regularly and irreversibly. Protocols conforming to our model can be highly efficient, since they do not require the resource-intensive modular exponentiations of the Diffie-Hellman protocol. We also introduce a protocol, called FORSAKES, and prove rigorously that it is a forward-secure AKE protocol in our model. FORSAKES is a very efficient protocol, and can be implemented by merely using hash functions.
MSC:
| 94A62 | Authentication, digital signatures and secret sharing |
| 68M12 | Network protocols |
| 94A60 | Cryptography |
Keywords:
authenticated key exchange protocol; forward security; key evolving schemes; provable security; security modelReferences:
| [1] | A. Banerjee, Pseudorandom functions and lattices,, in Advances in Cryptology-EUROCRYPT 2012, 7237, 719 (2012) · Zbl 1297.68071 · doi:10.1007/978-3-642-29011-4_42 |
| [2] | D. Basin, Provably repairing the ISO/IEC 9798 standard for entity authentication,, in Principles of Security and Trust, 7215, 129 (2012) · Zbl 1354.94055 · doi:10.1007/978-3-642-28641-4_8 |
| [3] | M. Bellare, Keying hash functions for message authentication,, in Advances in Cryptology-CRYPTO ’96, 1109, 1 (1996) · Zbl 1329.94051 · doi:10.1007/3-540-68697-5_1 |
| [4] | M. Bellare, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract),, in Proceedings of the \(30^{th}\) Annual ACM Symposium on Theory of Computing （STOC ’98）, 419 (1998) · Zbl 1028.68015 · doi:10.1145/276698.276854 |
| [5] | M. Bellare, Authenticated key exchange secure against dictionary attacks,, in Advances in Cryptology-EUROCRYPT ’00, 1807, 139 (2000) · Zbl 1082.94533 · doi:10.1007/3-540-45539-6_11 |
| [6] | M. Bellare, Entity authentication and key distribution,, in Advances in Cryptology-CRYPTO ’93, 773, 232 (1993) · Zbl 0870.94019 · doi:10.1007/3-540-48329-2_21 |
| [7] | M. Bellare, Random oracles are practical: A paradigm for designing efficient protocols,, in Proceedings of the \(1^{st}\) Annual ACM Conference on Computer and Communications Security （CCS ’93）, 62 (1993) · doi:10.1145/168588.168596 |
| [8] | M. Bellare, Provably secure session key distribution: The three party case,, in Proceedings of the \(27^{th}\) Annual ACM Symposium on Theory of Computing （STOC ’95）, 57 (1995) · Zbl 0916.94006 · doi:10.1145/225058.225084 |
| [9] | M. Bellare, The exact security of digital signatures-how to sign with RSA and Rabin,, in Advances in Cryptology-EUROCRYPT ’96, 1070, 399 (1996) · Zbl 1304.94094 · doi:10.1007/3-540-68339-9_34 |
| [10] | R. Bird, Systematic design of two-party authentication protocols,, in Advances in Cryptology-CRYPTO ’91, 576, 44 (1992) · doi:10.1007/3-540-46766-1_3 |
| [11] | A. Biryukov, Cryptanalysis of the alleged SecurID hash function,, in Selected Areas in Cryptography (SAC 2003), 3006, 130 (2004) · Zbl 1081.94517 · doi:10.1007/978-3-540-24654-1_10 |
| [12] | A. Biryukov, Recent attacks on alleged SecurID and their practical implications,, Computers & Security, 24, 364 (2005) · doi:10.1016/j.cose.2005.04.006 |
| [13] | S. Blake-Wilson, Key agreement protocols and their security analysis,, in Proceedings of the \(6^{th}\) IMA International Conference on Cryptography and Coding (IMACC ’97), 1355, 30 (1997) · Zbl 0904.94008 · doi:10.1007/BFb0024447 |
| [14] | S. Blake-Wilson, Entity authentication and authenticated key transport protocols: Employing asymmetric techniques,, in Security Protocols, 1361, 137 (2005) · Zbl 0899.94009 · doi:10.1007/BFb0028166 |
| [15] | C. Boyd, Hidden assumptions in cryptographic protocols,, IEE Proceedings of Computers and Digital Techniques, 137, 433 (1990) · doi:10.1049/ip-e.1990.0054 |
| [16] | C. Boyd, <em>Protocols for authentication and key establishment</em>,, Springer (2003) · Zbl 1043.68014 · doi:10.1007/978-3-662-09527-0 |
| [17] | C. Brzuska, Less is more: Relaxed yet composable security notions for key exchange,, International Journal of Information Security, 12, 267 (2013) · doi:10.1007/s10207-013-0192-y |
| [18] | C. Brzuska, Composability of Bellare-Rogaway key exchange protocols,, in Proceedings of the \(18^{th}\) ACM Conference on Computer and Communications Security (CCS 2011), 51 (2011) · doi:10.1145/2046707.2046716 |
| [19] | J. Camenisch, Practical yet universally composable two-server password-authenticated secret sharing,, in Proceedings of the \(19^{th}\) ACM Conference on Computer and Communications Security (CCS 2012), 525 (2012) · doi:10.1145/2382196.2382252 |
| [20] | R. Canetti, Universally composable security: A new paradigm for cryptographic protocols (extended abstract),, in Proceedings of the \(42^{nd}\) Annual IEEE Symposium on Foundations of Computer Science (FOCS ’01), 136 (2001) |
| [21] | R. Canetti, <em>Universally composable security: A new paradigm for cryptographic protocols</em>,, Cryptology ePrint Archive (2000) · doi:10.1109/SFCS.2001.959888 |
| [22] | R. Canetti, A forward-secure public-key encryption scheme,, in Advances in Cryptology-Eurocrypt 2003, 2656, 255 (2003) · Zbl 1037.68532 · doi:10.1007/3-540-39200-9_16 |
| [23] | R. Canetti, A forward-secure public-key encryption scheme,, Journal of Cryptology, 20, 265 (2007) · Zbl 1121.68044 · doi:10.1007/s00145-006-0442-5 |
| [24] | R. Canetti, Universally composable password-based key exchange,, in Advances in Cryptology-EUROCRYPT 2005, 3494, 404 (2005) · Zbl 1137.94367 · doi:10.1007/11426639_24 |
| [25] | R. Canetti, Analysis of key-exchange protocols and their use for building secure channels,, in Advances in Cryptology-EUROCRYPT ’01, 2045, 453 (2001) · Zbl 0981.94032 · doi:10.1007/3-540-44987-6_28 |
| [26] | R. Canetti, Universally composable notions of key exchange and secure channels (extended abstract),, in Advances in Cryptology-EUROCRYPT ’02, 2332, 337 (2002) · Zbl 1056.94511 · doi:10.1007/3-540-46035-7_22 |
| [27] | T. Cao, Security analysis of the SASI protocol,, IEEE Transactions on Dependable and Secure Computing, 6, 73 (2009) · doi:10.1109/TDSC.2008.32 |
| [28] | H.-Y. Chien, SASI: A new ultralightweight RFID authentication protocol providing strong authentication and strong integrity,, IEEE Transactions on Dependable and Secure Computing, 4, 337 (2007) · doi:10.1109/TDSC.2007.70226 |
| [29] | K.-K. R. Choo, <em>Secure key establishment</em>,, Springer (2009) · Zbl 1162.94006 · doi:10.1007/978-0-387-87969-7 |
| [30] | K.-K. R. Choo, Examining indistinguishability-based proof models for key establishment protocols,, in Advances in Cryptology-ASIACRYPT ’05, 3788, 585 (2005) · Zbl 1154.94382 · doi:10.1007/11593447_32 |
| [31] | K.-K. R. Choo, On session identifiers in provably secure protocols: The Bellare-Rogaway three-party key distribution protocol revisited,, in Security in Communication Networks (SCN 2004), 3352, 351 (2005) · Zbl 1116.94317 · doi:10.1007/978-3-540-30598-9_25 |
| [32] | J. Clark, On the security of recent protocols,, Information Processing Letters (IPL), 56, 151 (1995) · Zbl 1004.68503 · doi:10.1016/0020-0190(95)00136-Z |
| [33] | J. Clark, A survey of authentication protocol literature: Version 1.0, 1997,, Available from <a href= |
| [34] | S. Contini, Fast software-based attacks on SecurID,, in Fast Software Encryption (FSE 2004), 3017, 454 (2004) · Zbl 1079.68541 · doi:10.1007/978-3-540-25937-4_29 |
| [35] | C. Cremers, Examining indistinguishability-based security models for key exchange protocols: The case of CK, CK-HMQV, and eCK,, in Proceedings of the \(6^{th}\) ACM Symposium on Information, 80 (2011) · doi:10.1145/1966913.1966925 |
| [36] | C. J. Cremers, Session-state reveal is stronger than ephemeral key reveal: Attacking the NAXOS authenticated key exchange protocol,, in Proceedings of the \(7^{th}\) International Conference on Applied Cryptography and Network Security (ACNS ’09), 5536, 20 (2009) · doi:10.1007/978-3-642-01957-9_2 |
| [37] | D. E. Denning, Timestamps in key distribution protocols,, Communications of the ACM, 24, 533 (1981) · doi:10.1145/358722.358740 |
| [38] | W. Diffie, New directions in cryptography,, IEEE Transactions on Information Theory, IT-22, 644 (1976) · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638 |
| [39] | W. Diffie, Authentication and authenticated key exchanges,, Designs, 2, 107 (1992) · doi:10.1007/BF00124891 |
| [40] | M. S. Dousti, <em>Efficient Statistical Zero-Knowledge Authentication Protocols for Smart Cards Secure Against Active & Concurrent Attacks</em>,, Cryptology ePrint Archive (2013) |
| [41] | M. S. Dousti, An efficient statistical zero-knowledge authentication protocol for smart cards,, International Journal of Computer Mathematics · Zbl 1376.94032 · doi:10.1080/00207160.2015.1011629 |
| [42] | U. Feige, Zero-knowledge proofs of identity (extended abstract),, in Proceedings of the \(19^{th}\) Annual ACM Symposium on Theory of Computing (STOC ’87), 210 (1987) · Zbl 0659.94006 · doi:10.1007/BF02351717 |
| [43] | U. Feige, Zero-knowledge proofs of identity,, Journal of Cryptology, 1, 77 (1988) · Zbl 0659.94006 · doi:10.1007/BF02351717 |
| [44] | O. Goldreich, How to construct random functions,, Journal of the ACM (JACM), 33, 792 (1986) · Zbl 0596.65002 · doi:10.1145/6490.6503 |
| [45] | C. G. Günther, An identity-based key-exchange protocol,, in Advances in Cryptology-EUROCRYPT ’89, 29 (1989) · doi:10.1007/3-540-46885-4_5 |
| [46] | D. Hofheinz, Initiator-resilient universally composable key exchange,, in Proceedings of the \(8^{th}\) European Symposium on Research in Computer Security (ESORICS 2003), 2908, 61 (2003) · Zbl 1482.94052 · doi:10.1007/978-3-540-39650-5_4 |
| [47] | J. Katz, <em>Introduction to Modern Cryptography: Principles and Protocols</em>,, 1st edition (2007) |
| [48] | H. Krawczyk, HMQV: A high-performance secure Diffie-Hellman protocol (extended abstract),, in Advances in Cryptology-CRYPTO’05, 3621, 546 (2005) · Zbl 1145.94445 · doi:10.1007/11535218_33 |
| [49] | B. LaMacchia, Stronger security of authenticated key exchange,, in Proceedings of the \(1^{st}\) International Conference on Provable Security (ProvSec ’07), 4784, 1 (2007) · Zbl 1138.94381 · doi:10.1007/978-3-540-75670-5_1 |
| [50] | L. Law, An efficient protocol for authenticated key agreement,, Designs, 28, 119 (2003) · Zbl 1016.94025 · doi:10.1023/A:1022595222606 |
| [51] | C. Lenzen, Clock synchronization: Open problems in theory and practice,, in International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2010), 5901, 61 (2010) · doi:10.1007/978-3-642-11266-9_5 |
| [52] | A. Menezes, Another look at HMQV,, Journal of Mathematical Cryptology, 1, 47 (2007) · Zbl 1211.94032 · doi:10.1515/JMC.2007.004 |
| [53] | A. Menezes, Some new key agreement protocols providing implicit authentication,, in Presented at the Workshop on Selected Areas in Cryptography (SAC ’95), 22 (1995) |
| [54] | R. M. Needham, Using encryption for authentication in large networks of computers,, Communications of the ACM, 21, 993 (1978) · Zbl 0387.68003 · doi:10.1145/359657.359659 |
| [55] | D. Otway, Efficient and timely mutual authentication,, ACM SIGOPS Operating Systems Review, 21, 8 (1987) · doi:10.1145/24592.24594 |
| [56] | R. C.-W. Phan, Cryptanalysis of a new ultralightweight RFID authentication protocol-SASI,, IEEE Transactions on Dependable and Secure Computing, 6, 316 (2009) · doi:10.1109/TDSC.2008.33 |
| [57] | A. P. Sarr, A new security model for authenticated key agreement,, in Proceedings of the \(7^{th}\) International Conference on Security and Cryptography for Networks (SCN ’10), 6280, 219 (2010) · Zbl 1291.94197 · doi:10.1007/978-3-642-15317-4_15 |
| [58] | V. Shoup, <em>On formal models for secure key exchange</em>,, Technical report (1999) |
| [59] | V. Shoup, Session key distribution using smart cards,, in Advances in Cryptology-EUROCRYPT ’96, 1070, 321 (2001) · Zbl 1304.94108 · doi:10.1007/3-540-68339-9_28 |
| [60] | H.-M. Sun, On the security of Chien’s ultralightweight RFID authentication protocol,, IEEE Transactions on Dependable and Secure Computing, 8, 315 (2011) · doi:10.1109/TDSC.2009.26 |
| [61] | I. Wiener, Sample SecurID token emulator with token secret import, 2000,, Available from <a href=, 2000 |
| [62] | K. Yoneyama, Taxonomical security consideration of authenticated key exchange resilient to intermediate computation leakage,, in Proceedings of the \(5^{th}\) International Conference on Provable Security (ProvSec 2011), 6980, 348 (2011) · Zbl 1298.94113 · doi:10.1007/978-3-642-24316-5_25 |
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.
