Take the 2-minute tour ×
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.

My current textbook (Information Security: Principles and Practice by Mark Stamp) discusses how to determine the CRC of data via long-division, using XOR instead of subtraction to determine the remainder.

If our divisor has N-bits, we append (N-1) 0 bits to the dividend (the data) and then use long-division with XOR to solve for the CRC.

For example:

Divisor: 10011
Dividend: 10101011

101010110000 / 10011 = 10110110 R 1010, where 1010 = CRC

I'm able to perform this computation fine. However, the book mentions that in the case of the divisor being 10011, it's easy to find collisions.

I'm missing something here -- why is it easier to find a collision when the divisor is 10011?

share|improve this question
    
Perhaps the author had in mind that given the shortness of the Divisor, collisions are likely to occur by chance. Here there are only $2^4=16$ possible remainders. Thus after trying 5 random dividend/messages, odds are >50% to exhibit a collision among them. Also, after trying 11 random dividend/messages, odds are >50% to exhibit a collision with the remainder of another particular dividend/message. –  fgrieu Feb 29 '12 at 9:38
    
But if this is homework, e.g. exercises 5 or 6, you'd get higher marks (and most importantly a deeper understanding of CRCs) by devising a systematic method to solve these problems, rather than trying at random or even incrementally. Try to find a systematic method that works with the divisor/generating polynomial corresponding to $x^{65}+x^{47}+x^{33}+x^{15}+x^0$ (that is a divisor of 65 bits with ones at the positions defined by the exponents). –  fgrieu Feb 29 '12 at 13:36
1  
@fgrieu Interestingly enough, my professor IS Mark Stamp -- the author of the text in question. His intention was simply for us to solve the problem by randomly generating CRCs until we found two which collided.... –  BSchlinker Mar 2 '12 at 12:48
    
@fgrieu Thanks for the feedback -- its good to understand why the divisor was chosen. –  BSchlinker Mar 2 '12 at 12:49
add comment

1 Answer 1

up vote 5 down vote accepted

I don't have that book, but I suspect that you are misreading it.

It's always easy to find collisions with CRC, no matter what the divisor (more conventionally known as a polynomial) is. One easy way is to take the divisor and exclusive-or that bit pattern into an arbitrary place in the message (dividend); as in:

 10011    : Divisor (polynomial)
10101011  : Dividend (message)
11100111  : Modified message

111001110000 / 10011 = 11110110 R 1010

Here, we picked an arbitrary place in the message (starting at the second bit), and bit-wise exclusive-or'ed the divisor there, flipping any bit of the message where the divisor had a 1 bit. The resulting modified message has exactly the same CRC as the original message. Also, note that the quotient that we came up with is exactly as the original quotient with the second bit flipped; this is not a coincidence.

Given how easy this is, there wouldn't appear to be an even easier way that is specific to this polynomial.

share|improve this answer
    
You mean to say that if i have divisor of 33 bits and dividend of 80 bits , i have to just xor the dividend and xor with divisor(starting at second bit). My motivation of this is i have to find a lower degree dividend which should yield same CRC –  user7229 Jun 12 '13 at 10:51
add comment

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.