Abstract
At EuroCrypt ’08, Gilbert, Robshaw and Seurin proposed HB# to improve on HB + in terms of transmission cost and security against man-in-the-middle attacks. Although the security of HB# is formally proven against a certain class of man-in-the-middle adversaries, it is only conjectured for the general case. In this paper, we present a general man-in-the-middle attack against HB# and Random-HB#, which can also be applied to all anterior HB-like protocols, that recovers the shared secret in 225 or 220 authentication rounds for HB# and 234 or 228 for Random-HB#, depending on the parameter set. We further show that the asymptotic complexity of our attack is polynomial under some conditions on the parameter set which are met on one of those proposed in [8].
Chapter PDF
Similar content being viewed by others
Keywords
References
Berlekamp, E.R., McEliece, R., van Tilborg, H.C.A.: On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory 24(3), 384–386 (1978)
Bringer, J., Chabanne, H.: Trusted-HB: a low-cost version of HB + secure against man-in-the-middle attacks. CoRR, abs/0802.0603 (2008)
Bringer, J., Chabanne, H., Dottax, E.: HB + + : a lightweight authentication protocol secure against some attacks. In: Second International Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2006), Lyon, France, June 29, pp. 28–33. IEEE Computer Society, Los Alamitos (2006)
Duc, D.N., Kim, K.: Securing HB + against GRS man-in-the-middle attack. In: Institute of Electronics, Information and Communication Engineers, Symposium on Cryptography and Information Security, Sasebo, Japan, January 23-26, p. 123 (2007)
Erdős, P., Rényi, A.: On two problems of information theory. Publ. Math. Inst. Hung. Acad. Sci. 8(21), 229–243 (1963)
Gilbert, H., Robshaw, M., Sibert, H.: Active attack against HB + : a provably secure lightweight authentication protocol. IEEE Electronics Letters 41(21), 1169–1170 (2005)
Gilbert, H., Robshaw, M.J.B., Seurin, Y.: Good variants of HB + are hard to find. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 156–170. Springer, Heidelberg (2008)
Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB#: Increasing the security and efficiency of HB + . In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361–378. Springer, Heidelberg (2008)
Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB#: Increasing the security and efficiency of HB + , full version. Cryptology ePrint Archive, Report 2008/028 (2008)
Hammouri, G., Sunar, B.: PUF-HB: A tamper-resilient HB based authentication protocol. In: Bellovin, S.M., Gennaro, R., Keromytis, A.D., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 346–365. Springer, Heidelberg (2008)
Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001)
Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 293–308. Springer, Heidelberg (2005)
Katz, J., Shin, J.S.: Parallel and concurrent security of the HB and HB + protocols. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 73–87. Springer, Heidelberg (2006)
Levieil, É., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348–359. Springer, Heidelberg (2006)
Munilla, J., Peinado, A.: HB-MP: A further step in the HB-family of lightweight authentication protocols. Computer Networks 51(9), 2262–2267 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ouafi, K., Overbeck, R., Vaudenay, S. (2008). On the Security of HB# against a Man-in-the-Middle Attack. In: Pieprzyk, J. (eds) Advances in Cryptology - ASIACRYPT 2008. ASIACRYPT 2008. Lecture Notes in Computer Science, vol 5350. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89255-7_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-89255-7_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89254-0
Online ISBN: 978-3-540-89255-7
eBook Packages: Computer ScienceComputer Science (R0)