Cryptanalysis of the Gemmell and Naor Multiround Authentication Protocol

  • Christian Gehrmann
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


Gemmell and Naor proposed a new protocol for the authentication of long messages which was based on block codes and which used a transmission channel k times. This multiround authentication makes it possible to limit the key size independently of the message length. We propose a new attack and show that the probability analysis made by Gemmell and Naor, which was only based on the minimum distance property of the codes, does not hold for our attack. Considering also the impersonation attack we conclude that the number of rounds have to be odd.


Hash Function Block Code Impersonation Attack Message Length Bell System Technical Journal 
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.


  1. 1.
    E. Gilbert, F.J. MacWilliams, N. Sloane, “Codes Which Detect Deception”. Bell System Technical Journal. Vol. 53, No. 3. March 1974, pp. 405–424.MathSciNetGoogle Scholar
  2. 2.
    J.L. Carter, M.N. Wegman, “New hash functions and their use in authentication and set equality”, J. Computer and System Sci., Vol 22, 1981, pp. 265–279.zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    G.J. Simmons, “A survey of Information Authentication”, in Contemporary Cryptology, The science for information integrity, ed. G.J. Simmons, IEEE Press, New York, 1992.Google Scholar
  4. 4.
    T. Johansson, G. Kabatanskii, B. Smeets, “On the relation between A-codes and codes correcting independent errors”, Proceedings of Eurocrypt’ 93, 1993, pp. 1–11.Google Scholar
  5. 5.
    J. Bierbrauer, T. Johansson, G. Kabatanskii, B. Smeets, “On Families of Hash Functions via Geometric Codes and Concatenation”, Proceedings of CRYPTO’ 93, 1993, pp. 331–342.Google Scholar
  6. 6.
    D.R. Stinson, “Universal hashing and authentication codes”, to appear in IEEE Transaction on Information Theory.Google Scholar
  7. 7.
    C. Gehrmann, “Long Message Authentication by using Pseudo-Random Functions”, Proceedings of IEEE ISIT 94, to appear (preprint).Google Scholar
  8. 8.
    I.S. Reed, G. Solomon, “Polynomial Codes over certain Finite Fields”, J. Soc. Ind. Appl. Math., vol. 8, June 1960, pp. 300–304.zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    P. Gemmell, M. Naor, “Codes for interactive authentication”, Proceedings of CRYPTO’ 93, 1993, pp. 355–367.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Christian Gehrmann
    • 1
  1. 1.Dept. of Information TheoryLund UniversityLundSweden

Personalised recommendations