Subject: Re: Verifying a kernel.
To: Tonnerre <tonnerre@thundrix.ch>
From: David Laight <david@l8s.co.uk>
List: tech-kern
Date: 07/20/2005 21:36:10
On Wed, Jul 20, 2005 at 09:42:47PM +0200, Tonnerre wrote:
> Salut,
> 
> On Wed, Jul 20, 2005 at 12:15:10PM -0400, Steven M. Bellovin wrote:
> > There's a subtle distinction here between a *safety* algorithm and a 
> > *security* algorithm.  The former deals with naturally-occuring 
> > failures; the latter deals with enemy action.  The two are not the 
> > same.  If I (and Jason) correctly understand Matt's question, we're 
> > talking about a safety algorithm.  MD5 is fine for that.  CRC32 is 
> > probably not, though -- the size of the kernel is such that the 
> > probability of an undetected error is too high.
> 
> I wonder how the likelyhood of a collission using the Cyclic Redundancy
> Check, maybe even on more than 32 bits, outweights the additional load
> the unnecessary "data shuffling" in MD5 and friends, whereas the key space
> of MD5 is even significantly diminished. If it's not about security,
> a cyclic redundancy check is perfectly enough. I could even produce an
> even simpler function that takes care of a sufficient output length.
> 
> Please note as well that you need 4G of data until you have a guaranteed
> collision.

The chance of missing an error with CRC32 is (about) 1 in 2^32.
A single bit error is guaranteed to give an error (indeed I think any
single burst error block of upto 32bits will give an error).

For a 'safety' algorith a modulo 2^32-1 sum is probably enough, and
much, much faster to calculate.

	David

-- 
David Laight: david@l8s.co.uk