Re: Re: Adler-32 Checksum

-----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.


> 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 %).


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-----