More Web Proxy on the site http://driver.im/

article

Message Authentication Based on Cryptographically Secure CRC without Polynomial Irreducibility Test

Authors:

Göran Selander,

Fredrik LindqvistAuthors Info & Claims

Cryptography and Communications, Volume 10, Issue 2

Pages 383 - 399

https://doi.org/10.1007/s12095-017-0227-8

Published: 01 March 2018 Publication History

Abstract

In this paper, we present a message authentication scheme based on cryptographically secure cyclic redundancy check (CRC). Similarly to previously proposed cryptographically secure CRCs, the presented one detects both random and malicious errors without increasing bandwidth. The main difference from previous approaches is that we use random instead of irreducible generator polynomials. This eliminates the need for irreducibility tests. We provide a detailed quantitative analysis of the achieved security as a function of message and CRC sizes. The results show that the presented scheme is particularly suitable for the authentication of short messages.

References

[1]

3GPP TS 36.212: 3GPP technical specifications 36.212, multiplexing and channel coding (release 8). http://www.qtc.jp/3GPP/Specs/36212-830.pdf (2008)

[2]

Agren, M., Hell, M., Johansson, T., Meier, W.: Grain-128a: a new version of Grain-128 with optional authentication. Int. J. Wire. Mob. Comput. 5(1), 48---59 (2011)

Digital Library

[3]

Andrews, G.E.: A Survey of Multipartitions Congruences and Identities, pp. 1---19. Springer, New York (2008)

[4]

Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (ed.) Advances in Cryptology - CRYPTO '96, vol. 1109 of Lecture Notes in Computer Science, pp. 1---15. Springer, Berlin Heidelberg (1996)

[5]

Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '96, pp. 1---15. Springer, London (1996)

Digital Library

[6]

Bellare, M., Guérin, R., Phillip, R.: XOR MACs: New methods for message authentication using finite pseudorandom functions, pp. 15---28. Springer, London (1995)

[7]

Bellare, M., Kilian, J., Rogaway, P.: The security of cipher block chaining. In: Desmedt, Y. (ed.) Advances in Cryptology -- CRYPTO '94, vol. 839 of Lecture Notes in Computer Science, pp. 341---358. Springer, Berlin Heidelberg (1994)

[8]

Berndt, B.C.: Partition-theoretic interpretations of certain modular equations of Schröter, Russell, and Ramanujan. Ann. Comb. 11(2), 115---125 (2007)

[9]

Birch, J., Christensen, L.G., Skov, M.: A programmable 800 Mbit/s CRC check/generator unit for LANs and MANs. Comput. Netw. ISDN Syst. 24(2), 109---118 (1992)

Digital Library

[10]

Black, J., Halevi, S., Krawczyk, H., Krovetz, T., Phillip, R.: UMAC: Fast and secure message authentication. In: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '99, pp. 216---233. Springer, London (1999)

[11]

Brassard, G.: On computationally secure authentication tags requiring short secret shared keys. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology, pp. 79---86. Springer, US (1983)

[12]

Brent, R.P., Zimmermann, P.: Three ways to test irreducibility. http://maths-people.anu.edu.au/~brent/pd/MASCOS02t4.pdf (2008)

[13]

Desmedt, Y.: Unconditionally secure authentication schemes and practical and theoretical consequences. In: Williams, H.C. (ed.) Advances in Cryptology -- CRYPTO'85 Proceedings, vol. 218 of Lecture Notes in Computer Science, pp. 42---55. Springer, Berlin Heidelberg (1986)

[14]

Dubrova, E., Naslund, M., Selander, G.: CRC-based message authentication for 5G mobile technology. In: Proceedings of 1st IEEE International Workshop on 5G Security (2015)

Digital Library

[15]

Dubrova, E, Naslund, M, Selander, Gn, Lindqvist, F: Cryptographically secure CRC for lightweight message authentication. Technical Report 2015/035, Cryptology ePrint Archive (2015)

[16]

Eger, S: Restricted weighted integer compositions and extended binomial coefficients. J. Integer Seq. 18(1), 13.1.3 (2013)

[17]

Ericsson: 5G security. www.ericsson.com/res/docs/whitepapers/5G-security.pdf(2015)

[18]

ETSI SAGE 3GPP: Specification of the 3GPP confidentiality and integrity algorithms UEA2 & UIA2, document 2: SNOW 3G Specification (2006)

[19]

ETSI T.S. 100 909: Digital cellular telecommunications system (Phase 2+); Channel coding. http://www.etsi.org/deliver/etsi_ts/100900_100999/100909/08.09.00_60/ts_100909v080900p.pdf (2005)

[20]

Ferguson, N.: Authentication weaknesses in GCM. csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Ferguson2.pdf (2005)

[21]

Gao, S., Panario, D.: Tests and constructions of irreducible polynomials over finite fields. In: Cucker, F., Shub, M. (eds.) Foundations of computational mathematics, pp. 346---361. Springer, Berlin Heidelberg (1997)

[22]

Gilbert, E.N., MacWilliams, F.J., Sloane, N.J.A.: Codes which detect deception. Bell Syst. Tech. J. 53(3), 405---424 (1974)

[23]

Golomb, S.W.: Shift Register Sequences. Aegean Park Press (1982)

[24]

IEEE Std 802.15.4-2011: IEEE standard for local and metropolitan area networks - part 15.4: Low-rate wireless personal area networks (LR-WPANs). standards.ieee.org/getieee802/download/802.15.4-2011.pdf (2011)

[25]

Johansson, T.: A shift register construction of unconditionally secure authentication codes. Des. Codes Crypt. 4(1), 69---81 (1994)

Digital Library

[26]

Keith, W. J.: Restricted k-color partitions. Ramanujan J. 40(1), 71---92 (2016)

[27]

Krawczyk, H.: LFSR-based hashing and authentication. In: Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '94, pp. 129---139. Springer, London (1994)

Digital Library

[28]

Lai, X., Rueppel, R.A., Woollven, J.: A fast cryptographic checksum algorithm based on stream ciphers. In: Seberry, J., Zheng, Y. (eds.) Advances in Cryptology -- AUSCRYPT '92, Volume 718 of Lecture Notes in Computer Science, pp. 339---348. Springer, Berlin Heidelberg (1993)

[29]

Lam, C.C.Y., Gong, G., Vanstone, S.A.: Message authentication codes with error correcting capabilities. In: Proceedings of the 4th International Conference on Information and Communications Security, ICICS '02, pp. 354---366. Springer, London (2002)

Digital Library

[30]

Lidl, R., Niederreiter, H.: Introduction to Finite Fields and their Applications. Cambridge Univ Press (1994)

[31]

Mattsson, J., Westerlund, M.: Authentication key recovery on Galois/counter mode (GCM). Progress Cryptol. - AFRICACRYPT 2016, 127---143 (2016)

[32]

McCluskey, J.: High speed calculation of cyclic redundancy codes. In: Proceedings of the 1999 ACM/SIGDA Seventh International Symposium on Field Programmable Gate Arrays, FPGA '99, pp. 250---256. ACM, New York (1999)

Digital Library

[33]

Pei, T.-B., Zukowski, C.: High-speed parallel CRC circuits in VLSI. IEEE Trans. Commun. 40(4), 653---657 (1992)

[34]

Peterson, W. W., Brown, D. T.: Cyclic codes for error detection. Proc. IRE 49(1), 228---235 (1961)

[35]

Rabin, M.: Fingerprinting by Random Polynomials. Technical Report TR-15-81, Center for Research in Computing Technology. Harvard University, Cambridge (1981)

[36]

Ramabadran, T.V., Gaitonde, S.S.: A tutorial on CRC computations. Micro IEEE 8(4), 62---75 (1988)

Digital Library

[37]

Rouf, I., Miller, R., Mustafa, H., Taylor, T., Oh, S., Xu, W., Gruteser, M., Trappe, W., Seskar, I.: Security and privacy vulnerabilities of in-car wireless networks: A tire pressure monitoring system case study. In: Proceedings of the 19th USENIX Conference on Security, pp. 21---21. Berkeley (2010)

[38]

Sarwate, D.V.: Computation of cyclic redundancy checks via table look-up. Commun. ACM 31, 1008---1013 (1988)

Digital Library

[39]

Simmons, G.J.: A survey of information authentication. Proc. IEEE 76(5), 603---620 (1988)

[40]

Simmons, G.J: Authentication theory/coding theory. In: Proceedings of CRYPTO 84 on Advances in Cryptology, pp. 411---431. Springer, New York (1985)

[41]

Stinson, D.R.: Universal hashing and authentication codes. Univ. Codes Cryptogr. 4(4), 369---380 (1994)

Digital Library

[42]

Stinson, D.R.: On the connections between universal hashing, combinatorial designs and error-correcting codes. Proc. Congressus Numerantium 114, 7---27 (1996)

[43]

Stinson, D. : Cryptography Theory and Practice, 3rd edn. Chapman & hall/CRC (2006)

[44]

Taylor, R.: An integrity check value algorithm for stream ciphers. In: Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '93, pp. 40---48. Springer, London (1994)

Digital Library

[45]

Trappe, W., Howard, R., Moore, R.S.: Low-energy security: Limits and opportunities in the internet of things. IEEE Secur. Priv. 13(1), 14---21 (2015)

[46]

Wegman, M.N., Lawrence Carter J.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265---279 (1981)

Cited By

Wu LHu YZhang KLi WXu XChang W(2022)FLAM-PUF: A Response–Feedback-Based Lightweight Anti-Machine-Learning-Attack PUFIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.319769641:11(4433-4444)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1109/TCAD.2022.3197696
Zhou LNie Z(2022)An Enhanced Decision-Making Fault Detection Model in Medical IoT Embedded SystemsWireless Personal Communications: An International Journal10.1007/s11277-021-08759-8126:3(2065-2080)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11277-021-08759-8
Dubrova ENäslund MSelander GLindqvist FPapadimitratos PButler KPöpper C(2018)Lightweight Message Authentication for Constrained DevicesProceedings of the 11th ACM Conference on Security & Privacy in Wireless and Mobile Networks10.1145/3212480.3212482(196-201)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3212480.3212482

Message Authentication Based on Cryptographically Secure CRC without Polynomial Irreducibility Test

Recommendations

Anonymous and provably secure certificateless multireceiver encryption without bilinear pairing

Recently, numerous multireceiver identity-based encryption or identity-based broadcast encryption schemes have been introduced with bilinear pairing and probabilistic map-to-point MTP function. As the bilinear pairing and MTP functions are expensive ...
Attribute-based versions of Schnorr and ElGamal

We design in this paper the first attribute-based cryptosystems that work in the classical discrete logarithm, pairing-free, setting. The attribute-based signature scheme can be seen as an extension of Schnorr signatures, with adaptive security relying ...
A Provably Secure ID-Based Mutual Authentication and Key Agreement Scheme for Mobile Multi-Server Environment Without ESL Attack

In mobile multi-server authentication, a client can access different servers over an insecure channel like Internet and wireless networks for numerous online applications. In the literature, several multi-server authentication schemes for mobile clients ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Cryptography and Communications

Cryptography and Communications Volume 10, Issue 2

March 2018

159 pages

ISSN:1936-2447

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 March 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu LHu YZhang KLi WXu XChang W(2022)FLAM-PUF: A Response–Feedback-Based Lightweight Anti-Machine-Learning-Attack PUFIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.319769641:11(4433-4444)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1109/TCAD.2022.3197696
Zhou LNie Z(2022)An Enhanced Decision-Making Fault Detection Model in Medical IoT Embedded SystemsWireless Personal Communications: An International Journal10.1007/s11277-021-08759-8126:3(2065-2080)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11277-021-08759-8
Dubrova ENäslund MSelander GLindqvist FPapadimitratos PButler KPöpper C(2018)Lightweight Message Authentication for Constrained DevicesProceedings of the 11th ACM Conference on Security & Privacy in Wireless and Mobile Networks10.1145/3212480.3212482(196-201)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3212480.3212482

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents