Cryptology ePrint Archive: Report 2015/035

Cryptographically Secure CRC for Lightweight Message Authentication

Elena Dubrova and Mats Näslund and Göran Selander and Fredrik Lindqvist

Abstract: A simple and practical hashing scheme based on Cyclic Redundancy Check (CRC) is presented. Similarly to previously proposed cryptographically secure CRCs, the presented one detects both, random and malicious, errors without increasing bandwidth. However, we use a product of irreducible polynomials instead of a single irreducible polynomial for generating the CRC. This is an advantage since smaller irreducible polynomials are easier to compute. The price we pay is that the probability that two different messages map into the same CRC increases. We provide a detailed quantitative analysis of the achieved security as a function of message and CRC sizes. The presented method seems to be particularly attractive for the authentication of short messages.

Category / Keywords: foundations / Hash function, message authentication, CRC, error-detection, LFSR, irreducible polynomial

Date: received 15 Jan 2015

Contact author: dubrova at kth se

Available format(s): PDF | BibTeX Citation

Version: 20150115:182046 (All versions of this report)

Short URL: ia.cr/2015/035

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]