Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1007/11502760_3guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

The Poly1305-AES message-authentication code

Published: 21 February 2005 Publication History

Abstract

Poly1305-AES is a state-of-the-art message-authentication code suitable for a wide variety of applications. Poly1305-AES computes a 16-byte authenticator of a variable-length message, using a 16-byte AES key, a 16-byte additional key, and a 16-byte nonce. The security of Poly1305-AES is very close to the security of AES; the security gap is at most 14D⌈L/16⌉/2106 if messages have at most L bytes, the attacker sees at most 264 authenticated messages, and the attacker attempts D forgeries. Poly1305-AES can be computed at extremely high speed: for example, fewer than 3.1l+780 Athlon cycles for an ℓ-byte message. This speed is achieved without precomputation; consequently, 1000 keys can be handled simultaneously without cache misses. Special-purpose hardware can compute Poly1305-AES at even higher speed. Poly1305-AES is parallelizable, incremental, and not subject to any intellectual-property claims.

References

[1]
17th annual symposium on foundations of computer science, IEEE Computer Society, Long Beach, California, 1976. MR 56:1766.
[2]
20th annual symposium on foundations of computer science, IEEE Computer Society, New York, 1979. MR 82a:68004.
[3]
IEEE standard for binary floating-point arithmetic, Standard 754-1985, Institute of Electrical and Electronics Engineers, New York, 1985.
[4]
Valentine Afanassiev, Christian Gehrmann, Ben Smeets, Fast message authentication using efficient polynomial evaluation, in {10} (1997), 190-204. URL: http://cr.yp.to/bib/entries.html#1997/afanassiev.
[5]
Daniel J. Bernstein, Guaranteed message authentication faster than MD5 (abstract) (1999). URL: http://cr.yp.to/papers.html#hash127-abs.
[6]
Daniel J. Bernstein, Cache-timing attacks on AES (2004). URL: http://cr.yp.to/ papers.html#cachetiming. ID cd9faae9bd5308c440df50fc26a517b4.
[7]
Daniel J. Bernstein, Floating-point arithmetic and message authentication (2004). URL: http://cr.yp.to/papers.html#hash127. ID dabadd3095644704c5cbe9690 ea3738e.
[8]
Daniel J. Bernstein, Stronger security bounds for Wegman-Carter-Shoup authenticators, Proceedings of Eurocrypt 2005, to appear (2005). URL: http://cr.yp.to/ papers.html#securitywcs. ID 2d603727f69542f30f7da2832240c1ad.
[9]
Jürgen Bierbrauer, Thomas Johansson, Gregory Kabatianskii, Ben Smeets, On families of hash functions via geometric codes and concatenation, in {30} (1994), 331-342. URL: http://cr.yp.to/bib/entries.html#1994/bierbrauer.
[10]
Eli Biham (editor), Fast Software Encryption '97, Lecture Notes in Computer Science, 1267, Springer-Verlag, Berlin, 1997. ISBN 3-540-63247-6.
[11]
John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz, Phillip Rogaway, UMAC: fast and secure message authentication, in {34} (1999), 216-233. URL: http://www.cs.ucdavis.edu/~rogaway/umac/.
[12]
Gilles Brassard, On computationally secure authentication tags requiring short secret shared keys, in {13} (1983), 79-86. URL: http://cr.yp.to/bib/entries. html#1983/brassard.
[13]
David Chaum, Ronald L. Rivest, Alan T. Sherman (editors), Advances in cryptology: proceedings of Crypto 82, Plenum Press, New York, 1983. ISBN 0-306-41366-. 3. MR 84j:94004.
[14]
Bert den Boer, A simple and key-economical unconditional authentication scheme, Journal of Computer Security 2 (1993), 65-71. ISSN 0926-227X. URL: http://cr.yp.to/bib/entries.html#1993/denboer.
[15]
Edgar N. Gilbert, F. Jessie MacWilliams, Neil J. A. Sloane, Codes which detect deception, Bell System Technical Journal 53 (1974), 405-424. ISSN 0005-8580. MR 55:5306. URL: http://cr.yp.to/bib/entries.html#1974/gilbert.
[16]
Torbjorn Granlund (editor), GMP 4.1.2: GNU multiple precision arithmetic library (2004). URL: http://www.swox.com/gmp/.
[17]
Shai Halevi, Phil Rogaway, A tweakable enciphering mode (2003). URL: http://www.research.ibm.com/people/s/shaih/pubs/hr03.html.
[18]
Michael Kaminski, A linear time algorithm for residue computation and a fast algorithm for division with a sparse divisor, Journal of the ACM 34 (1987), 968- 984. ISSN 0004-5411. MR 89f:68033.
[19]
Richard M. Karp, Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development 31 (1987), 249-260. ISSN 0018-8646. URL: http://cr.yp.to/bib/entries.html#1987/karp.
[20]
Neal Koblitz (editor), Advances in cryptology--CRYPTO '96, Lecture Notes in Computer Science, 1109, Springer-Verlag, Berlin, 1996.
[21]
Ted Krovetz, Phillip Rogaway, Fast universal hashing with small keys and no preprocessing: the PolyR construction (2000). URL: http://www.cs.ucdavis.edu/~rogaway/papers/poly.htm.
[22]
Wim Nevelsteen, Bart Preneel, Software performance of universal hash functions, in {29} (1999), 24-41.
[23]
Nicholas Pippenger, On the evaluation of powers and related problems (preliminary version), in {1} (1976), 258-263; newer version split into {24} and {25}. MR 58:3682. URL: http://cr.yp.to/bib/entries.html#1976/pippenger.
[24]
Nicholas Pippenger, The minimum number of edges in graphs with prescribed paths, Mathematical Systems Theory 12 (1979), 325- 346; see also older version {23}. ISSN 0025-5661. MR 81e:05079. URL: http://cr.yp.to/bib/entries.html#1979/pippenger.
[25]
Nicholas Pippenger, On the evaluation of powers and monomials, SIAM Journal on Computing 9 (1980), 230-250; see also older version {23}. ISSN 0097-5397. MR 82c:10064. URL: http://cr.yp.to/bib/entries.html#1980/pippenger.
[26]
Michael O. Rabin, Fingerprinting by random polynomials, Harvard Aiken Computational Laboratory TR-15-81 (1981). URL: http://cr.yp.to/bib/entries.html #1981/rabin.
[27]
Victor Shoup, On fast and provably secure message authentication based on universal hashing, in {20} (1996), 313-328; see also newer version {28}.
[28]
Victor Shoup, On fast and provably secure message authentication based on universal hashing (1996); see also older version {27}. URL: http://www.shoup.net/ papers.
[29]
Jacques Stern (editor), Advances in cryptology: EUROCRYPT '99, Lecture Notes in Computer Science, 1592, Springer-Verlag, Berlin, 1999. ISBN 3-540-65889-0. MR 2000i:94001.
[30]
Douglas R. Stinson (editor), Advances in cryptology--CRYPTO '93: 13th annual international cryptology conference, Santa Barbara, California, USA, August 22- 26, 1993, proceedings, Lecture Notes in Computer Science, 773, Springer-Verlag, Berlin, 1994. ISBN 3-540-57766-1, 0-387-57766-1. MR 95b:94002.
[31]
Richard Taylor, An integrity check value algorithm for stream ciphers, in {30} (1994), 40-48. URL: http://cr.yp.to/bib/entries.html#1994/taylor.
[32]
Mark N. Wegman, J. Lawrence Carter, New classes and applications of hash functions, in {2} (1979), 175-182; see also newer version {33}. URL: http://cr.yp.to/bib/entries.html#1979/wegman.
[33]
Mark N. Wegman, J. Lawrence Carter, New hash functions and their use in authentication and set equality, Journal of Computer and System Sciences 22 (1981), 265-279; see also older version {32}. ISSN 0022-0000. MR 82i:68017. URL: http://cr.yp.to/bib/entries.html#1981/wegman.
[34]
Michael Wiener (editor), Advances in cryptology--CRYPTO '99, Lecture Notes in Computer Science, 1666, Springer-Verlag, Berlin, 1999. ISBN 3-5540-66347-9. MR 2000h:94003.

Cited By

View all
  • (2024)OnionVPN: Onion Routing-Based VPN-Tunnels with Onion ServicesProceedings of the 23rd Workshop on Privacy in the Electronic Society10.1145/3689943.3695043(17-33)Online publication date: 20-Nov-2024
  • (2024)Multi-User Security of CCM Authenticated Encryption ModeProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670385(4331-4345)Online publication date: 2-Dec-2024
  • (2024)Object-oriented Unified Encrypted Memory Management for Heterogeneous Memory ArchitecturesProceedings of the ACM on Management of Data10.1145/36549582:3(1-29)Online publication date: 30-May-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings
FSE'05: Proceedings of the 12th international conference on Fast Software Encryption
February 2005
442 pages
ISBN:3540265414
  • Editors:
  • Henri Gilbert,
  • Helena Handschuh

Sponsors

  • Gemplus SA: Gemplus SA
  • Nokia
  • France Telecom

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 February 2005

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)OnionVPN: Onion Routing-Based VPN-Tunnels with Onion ServicesProceedings of the 23rd Workshop on Privacy in the Electronic Society10.1145/3689943.3695043(17-33)Online publication date: 20-Nov-2024
  • (2024)Multi-User Security of CCM Authenticated Encryption ModeProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670385(4331-4345)Online publication date: 2-Dec-2024
  • (2024)Object-oriented Unified Encrypted Memory Management for Heterogeneous Memory ArchitecturesProceedings of the ACM on Management of Data10.1145/36549582:3(1-29)Online publication date: 30-May-2024
  • (2024)Formal Verification of Emulated Floating-Point Arithmetic in FalconAdvances in Information and Computer Security10.1007/978-981-97-7737-2_7(125-141)Online publication date: 17-Sep-2024
  • (2024)Tight Multi-user Security of Ascon and Its Large Key ExtensionInformation Security and Privacy10.1007/978-981-97-5025-2_4(57-76)Online publication date: 15-Jul-2024
  • (2024)Toward Full n-bit Security and Nonce Misuse Resistance of Block Cipher-Based MACsAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0947-5_9(251-279)Online publication date: 10-Dec-2024
  • (2024)On Improved Cryptanalytic Results Against ChaCha for Reduced Rounds Progress in Cryptology – INDOCRYPT 202410.1007/978-3-031-80311-6_2(29-52)Online publication date: 18-Dec-2024
  • (2024)BlindexTEE: A Blind Index Approach Towards TEE-Supported End-to-End Encrypted DBMSStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_19(260-276)Online publication date: 20-Oct-2024
  • (2024)Mystrium: Wide Block Encryption Efficient on Entry-Level ProcessorsSecurity and Cryptography for Networks10.1007/978-3-031-71073-5_4(71-96)Online publication date: 11-Sep-2024
  • (2024)Automatic Verification of Cryptographic Block Function Implementations with Logical Equivalence CheckingComputer Security – ESORICS 202410.1007/978-3-031-70903-6_19(377-395)Online publication date: 16-Sep-2024
  • Show More Cited By

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media