Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 4 down vote favorite

Background

In both, bitstrings are interpreted as a polnomical over GF(2) and they each can be used to implement a hash over a sliding window. The definitions of each are as follows:

Rabin Fingerprint: $M(x) = Q(x) \cdot G(x) + R (x)$

CRC: $M(x) \cdot x^{n} = Q(x) \cdot G(x) + R (x)$

Where $M(x)$ is message polynomial, $G(x)$ is the degree-$n$ irreducible 'generator' polynomial, $x^{n}$ represents $n$ zeroes added at the end of the message, $Q(x)$ is the quotient polynomial (ignored) and $R(x)$ is the remainder polynomial (the hash itself).

The Question

According to page 7 (labelled as page 135) of the paper LFSR-based Hashing and Authentication, CRC offers some improvements for hashing under encryption.

Assuming $G(x)$ is the same for the implementation of each algorithm (i.e. ignoring that polynomials under Rabin should be random) and an identical $M(x)$ is used for testing, does the Rabin Fingerprint offer any advantages over CRC? If not, is there any reason why the Rabin Fingerprint is moderately popular in file chunking (using the sliding window technique mentioned above)? For example, 1, 2 and many others on the web. By contrast, I can find very few implementations of a sliding window version of CRC or mentions of it being used for chunking.

share|improve this question
2  
Your statement about CRC is incorrect as far as communications systems are concerned, though it may be the way CRCs are used in cryptographic applications. In communications systems, CRCs are used exactly the way you describe the Rabin fingerprint, with the transmission being $$x^nM(x)-R(x)=M_kx^{n+k}+M_{k-1}x^{n+k-1}+\cdots+M_0x^n-R_{n-1}x^{n-1}-R_{n-2}x‌​^{n-2}-\cdots-R_0,$$ that is, the data sequence followed by the CRC sequence. – Dilip Sarwate Mar 30 '12 at 19:50
The meaning of "$G(x)$ and $M(x)$ are the same" is obscure to me. – fgrieu Apr 2 '12 at 3:32
As in, we use the same message and same generator polynomial as the input for both. – aidanhs Apr 5 '12 at 16:13

1 Answer

up vote 2 down vote

This is an expanded version of my comment above. At the top of page 135 of the paper cited by the OP, the construction of the cryptographic CRC is defined in the following words:

$\ldots$ for any message $M(x)$ of binary length $m$ bits, $h_p(M)$ is defined as (the coefficients of) $M(x)\cdot x^n \bmod p(x)$.

Thus, the definition of cryptographic CRC in the cited paper is the same as what the OP claims the Rabin fingerprint is. On the other hand, the cited paper says Rabin's construction is essentially the same

$\ldots$ except for the multiplication by $x^n$ in the modular process

In other words, the OP seems to have interchanged the definitions of CRC and Rabin fingerprint in his question.

The cited paper also seems to be implying (the phrasing is somewhat ambiguous) that Rabin's fingerprint is weaker than the cryptographic CRC defined above, which, by the way, is the same as the way CRC error detection is used in communications systems, as I stated in my comment.

share|improve this answer
You are absolutely correct, I managed to carelessly mislabel my equations when crafting my question. I've now corrected it, thanks. – aidanhs Apr 2 '12 at 2:53
The cited paper explains that Rabin's fingerprint would be unsafe, but CRC is safe, as an authentication method, in the setting where $G(x)$ is secret and $M(x)$ $R(x)$ are sent encrypted using a stream cipher. The extra zeroes protect against a trivial attack where e.g. the low-oder bit of the (encrypted) $M(x)$ and $R(x)$ are flipped. This does not answer the question. – fgrieu Apr 2 '12 at 4:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.