Re: Re: Adler-32 Checksum

Hi Thomas,

see my comments in-line.

Best regards
Michael

On Jun 28, 2005, at 3:25 PM, Thomas Dreibholz wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Tuesday 28 June 2005 14:56, Michael Tuexen wrote:
>
>>> For the handlespace audit, it is necessary to have a checksum
>>> function f which
>>> provides the property that when a PE entry b is deleted from the
>>> set of PE
>>> entries a,b,c, then the checksum f(ac) has to be computable by f
>>> (abc) - f(b)
>>> without re-computing f(a) or f(c). "-" denotes an appropriate
>>> subtraction
>>> operation. Furthermore, it must be possible to add an element b to
>>> the set of
>>> PE entries a,c and compute the checksum f(abc) = f(a) + f(b) + f(c)
>>> without
>>> having to re-computing f(a) or f(c) ("+" denotes and appropriate
>>> concatencation function).
>>>
>>
>> That is one question: Do we want such a function? Adler32 and CRC  
>> do not
>> have the property. The Internet checksum has. I would prefer the
>> Internet
>> checksum to XOR.
>> But the question remains: Do we need the function which with 'an  
>> update
>> possibility' or can we just recompute the stuff?
>>
>
> It is necessary to have an update possibility. Otherwise, each time  
> a small
> change is made to the handlespace, a complete re-calculation of the
> handlespace checksum is necessary. Consider a handlespace with  
> thousands of
> PEs this would cause a significant effort. An evil PE could exploit  
> this
> behaviour by registering and deregistering at a high frequency and  
> cause a
> DoS.
I'm more concerned that an evil attacker can register PE which means  
that
he can pollute the namespace. The computation resource is not so  
important
compared to that, I think.
>
>
>
>> The problem I see is that by computing we really compare stuff. But
>> just doing
>> incremental updates we might report something we really do not have
>> anymore
>> in the cache (due to sume bugs, for example).
>>
>
> If PEs are removed, the implementation must update its checksum. If  
> the
> checksum is not updated, the implementation is broken and should be  
> fixed.
> IMHO, it should not be complicated to ensure that after an entry  
> has been
> added or removed the checksum is updated. By using an inefficient  
> checksum
> algorithm, a significant performance impact is imposed on every  
> correct
> implementation. And this would be a very bad thing.
>
>
> I think, the Internet checksum algorithm (may be with keeping the  
> full 32 bits
> instead of truncating to 16 bits) should already be sufficient for  
> the audit
> purpose. Using this checksum algorithm, we also get order- 
> invariancy and do
> not need to force a specific ordering of the handlespace within a  
> management
> component. It is furthermore very simple and fast (only + and ~  
> operations
> are needed, no *, / or %).
So the Internet checksum is the way to go... I have no particular  
preference
in 16 bit or 32 bit.
>
>
> Best regards
> - --
> ====================================================================== 
> =
>  Dipl.-Inform. Thomas Dreibholz
>
>  University of Essen,                            Room ES210
>  Inst. for Experimental Mathematics              Ellernstraße 29
>  Computer Networking Technology Group            D-45326 Essen/Germany
> -  
> ---------------------------------------------------------------------- 
> -
>  E-Mail:     [email protected]
>  Homepage:   http://www.exp-math.uni-essen.de/~dreibh
> ====================================================================== 
> =
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>
> iD8DBQFCwU/Y32BbsHYPLWURAvVkAKCzmbkwGqSWUOhnO1LkTYMqbPE3iQCfZ/Na
> vhWiJ2Z2x1+ntoKqqkMSJjc=
> =N0tj
> -----END PGP SIGNATURE-----
>
>