Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5895

Re: Size of a CRC (or similar) code for a given length of message

Show all headers | View raw

On 25/09/15 13:17, Öö Tiib wrote:
> On Friday, 25 September 2015 12:59:47 UTC+3, James Harris  wrote:
>> I see from
>>
>>    https://en.wikipedia.org/wiki/Cyclic_redundancy_check
>>
>> that, typically, an n-bit CRC applied to a data block of arbitrary 
>> length will detect a single error burst up to n bits long.
>>
>> That's fine - or as fine as the complex mathematics of CRCs gets! - but 
>> if looking to select a CRC calculation (or some other data integrity 
>> check) are there any guidelines on how wide the CRC code should be for 
>> given levels of assurance against random corruption for a given size of 
>> message?
> 
> CRC is just a cheap filter that lets you discard most of messages
> that have been corrupted in transit. However what prevents it being 
> maliciously corrupted or corrupted by defect before CRC was added?
> So It can not replace other integrity and sanity checks.  

A CRC check makes it highly unlikely that the message has been corrupted
without detection during that particular part of its journey.  It says
nothing about what happened before it is added, or what happens after
the CRC has been checked - surely that is obvious to the OP, even if he
has not used CRC's before?

> 
>>
>> At the moment I am looking to protect a very short header of about 12 
>> bytes, give or take, and wonder what levels of confidence a certain 
>> number of CRC bits would give against data corruption.
> 
> The likelihood that some other data randomly matches with the CRC
> is 1/(uint_bits_max + 1). So if you have 8 bit CRC then it is
> 1/256  or 0.00390625 or almost 0.4%. Increasing it to 16 bits gives
> 1/65536 (0.0015%) and so on. It can never reach zero but your
> confidence level should increase exponentially with bigger CRC.
> 
>>
>> For example, if I used a 3-bit CRC to protect a 12-byte header how 
>> 'good' would that be compared to a 5-bit CRC? And if the header became 
>> 24 bytes, say, what effect would that have on the effectiveness of 3-bit 
>> and 5-bit CRCs? (Always assuming that other aspects of the CRC 
>> calculation are chosen well.)
> 
> 3-bit CRC gives 1/8 confidence so 12.5% corrupted headers will pass.
> 5-bit results with 3% of corrupted headers passing. Such might be
> useful only for sanity checks inside of your own code. Usually 16 or 
> 32 bits are considered fine. 

8-bit CRCs are also very common, especially for short messages or on
weaker processors.  But I agree that 16-bit and 32-bit are the most
common, and generally most appropriate.  (If you think 32-bit is not
enough, and you are looking at 64-bit CRCs, then you would usually be
better off with some other type of hashing, checking or correcting
mechanism.)

> 
>>
>> If I later wanted to protect a message of a thousand or a 
>> hundred-thousand bytes how wide would the CRC need to be to maintain a 
>> similar level of confidence?
> 
> The chance of match does not change with bigger data. 2 byte CRC 
> has 0.0015% matches with corrupted 12 byte header and same with
> corrupted 1Mb file.
> 

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Size of a CRC (or similar) code for a given length of message James Harris <james.harris.1@gmail.com> - 2015-09-25 10:59 +0100
  Re: Size of a CRC (or similar) code for a given length of message David Brown <david.brown@hesbynett.no> - 2015-09-25 13:05 +0200
    Re: Size of a CRC (or similar) code for a given length of message James Harris <james.harris.1@gmail.com> - 2015-09-25 13:42 +0100
      Re: Size of a CRC (or similar) code for a given length of message David Brown <david.brown@hesbynett.no> - 2015-09-25 15:15 +0200
  Re: Size of a CRC (or similar) code for a given length of message Julio Di Egidio <julio@diegidio.name> - 2015-09-25 04:07 -0700
    Re: Size of a CRC (or similar) code for a given length of message David Brown <david.brown@hesbynett.no> - 2015-09-25 14:32 +0200
      Re: Size of a CRC (or similar) code for a given length of message Julio Di Egidio <julio@diegidio.name> - 2015-09-25 05:40 -0700
    Re: Size of a CRC (or similar) code for a given length of message James Harris <james.harris.1@gmail.com> - 2015-09-25 13:45 +0100
  Re: Size of a CRC (or similar) code for a given length of message Öö Tiib <ootiib@hot.ee> - 2015-09-25 04:17 -0700
    Re: Size of a CRC (or similar) code for a given length of message David Brown <david.brown@hesbynett.no> - 2015-09-25 14:36 +0200
      Re: Size of a CRC (or similar) code for a given length of message James Harris <james.harris.1@gmail.com> - 2015-09-25 13:49 +0100

csiph-web