Subject: [Rserpool] Re: Adler-32 Checksum

From: Michael Tuexen <[email-masked]>
Date: Tue, 28 Jun 2005 14:56:51 +0200

Dear all,

see my comments in-line.

Best regards
Michael

On Jun 28, 2005, at 2:12 PM, Thomas Dreibholz wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Monday 27 June 2005 23:03, Michael Tuexen wrote:
> Hi all!
>
>
>>     Implementation Note: when the internal handlespace changes  
>> (e.g., a
>>     new PE added or an existing PE removed), an implementation  
>> needs not
>>     to re-calculate the affected PE checksum; it should instead  
>> simply
>>     update the checksum by adding or subtracting the byte block of  
>> the
>>     corresponding PE from the previous checksum value.
>>     is at least miss-leading.
>>
>
> The problem of the Adler-32 checksum is that adding or subtracting  
> a byte
> block from the checksum value is not possible. Example: The  
> handlespace
> contains the pool "PoolTEST" with PEs 0x1234, 0x5000, 0x5001, ...,  
> 0x5100.
> The checksum of the handlespace is therefore
> f(PoolTEST1234PoolTEST5000PoolTEST5001 ... PoolTEST5100). If PE  
> 0x5000 is
> removed, at least the Adler-32 checksum of PE 0x5001 to 0x5100 must be
> recalculated, with the seed set to the checksum of PE 0x1234. The  
> Adler-32
> algorithm depends on the checksum of the previous elements as seed,  
> therefore
> it is not possible to store the checksum of each PE entry and  
> finally combine
> the checksums of PE 0x1234 and the checksum of PE 0x5000 to PE  
> 0x5100 to the
> new checksum.
>
> This is the Adler-32 algorithm:
>
> const uint32_t crcBase = 65521;
> uint32_t adler32(const uint32_t seed, const char* buffer, const  
> size_t size)
> {
>    uint32_t s1  = seed & 0xffff;
>    uint32_t s2  = (seed >> 16) & 0xffff;
>    for(size_t i = 0;i < size;i++) {
>       s1 = (s1 + buffer[i]) % crcBase;
>       s2 = (s2 + s1) % crcBase;
>    }
>    unsigned int adler32 = (s2 << 16) + s1;
>    return(adler32);
> }
>
> Depending on the seed value (i.e. the checksum of the previous  
> elements), a
> counter wrap (due to modulo operation by crcBase) appears at different
> positions in the buffer.
>
>
> 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?
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). So it would be more  
robust to
use something like Adler32/CRC32 as the Internet Checksum, but it  
costs more
performance. But I'm not sure how critical that is.
>
>
> A possible checksum function fulfilling the described requirements  
> is XOR. But
> this function seems to be too simple, the probability that a  
> handlespace
> inconsistency is not recognised may be too high?
>
>
> 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-masked]
>  Homepage:   http://www.exp-math.uni-essen.de/~dreibh
> ====================================================================== 
> =
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>
> iD8DBQFCwT7O32BbsHYPLWURAnYyAJ0ZC9dcA30KFDUwQa+7jkBuzqhhtgCfcMB7
> +B04WYiuaA4E+lF56LgHn9g=
> =k2EC
> -----END PGP SIGNATURE-----
>
>

_______________________________________________
rserpool mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rserpool

---

From: Thomas Dreibholz <[email-masked]>
Date: Tue, 28 Jun 2005 15:02:01 +0200

>     Implementation Note: when the internal handlespace changes (e.g., a
>     new PE added or an existing PE removed), an implementation needs not
>     to re-calculate the affected PE checksum; it should instead simply
>     update the checksum by adding or subtracting the byte block of the

The problem of the Adler-32 checksum is that adding or subtracting a byte
block from the checksum value is not possible. Example: The handlespace
contains the pool "PoolTEST" with PEs 0x1234, 0x5000, 0x5001, ..., 0x5100.
The checksum of the handlespace is therefore
f(PoolTEST1234PoolTEST5000PoolTEST5001 ... PoolTEST5100). If PE 0x5000 is
removed, at least the Adler-32 checksum of PE 0x5001 to 0x5100 must be
recalculated, with the seed set to the checksum of PE 0x1234. The Adler-32
algorithm depends on the checksum of the previous elements as seed, therefore
it is not possible to store the checksum of each PE entry and finally combine
the checksums of PE 0x1234 and the checksum of PE 0x5000 to PE 0x5100 to the
new checksum.

uint32_t adler32(const uint32_t seed, const char* buffer, const size_t size)

Depending on the seed value (i.e. the checksum of the previous elements), a
counter wrap (due to modulo operation by crcBase) appears at different
positions in the buffer.

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

A possible checksum function fulfilling the described requirements is XOR. But
this function seems to be too simple, the probability that a handlespace
inconsistency is not recognised may be too high?

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-masked]
 Homepage:   http://www.exp-math.uni-essen.de/~dreibh
=======================================================================

---

From: Thomas Dreibholz <[email-masked]>
Date: Tue, 28 Jun 2005 15:25:40 +0200

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

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

---

From: Michael Tuexen <[email-masked]>
Date: Tue, 28 Jun 2005 15:53:41 +0200

Hi Thomas,

see my comments in-line.

Best regards
Michael

> behaviour by registering and deregistering at a high frequency and  
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.
> are needed, no *, / or %).
So the Internet checksum is the way to go... I have no particular  
preference
in 16 bit or 32 bit.
> iD8DBQFCwU/Y32BbsHYPLWURAvVkAKCzmbkwGqSWUOhnO1LkTYMqbPE3iQCfZ/Na
> vhWiJ2Z2x1+ntoKqqkMSJjc=
> =N0tj

---

From: Thomas Dreibholz <[email-masked]>
Date: Tue, 28 Jun 2005 15:59:49 +0200

> So the Internet checksum is the way to go... I have no particular

I would prefer 32 bits. The checksum parameter pads the sum to 32 bits of 
space anyway - so why not use the full 32 bits, making the probability that 
two states of the handlespace map to the same checksum value much smaller?

Best regards
- --

---

From: Michael Tuexen <[email-masked]>
Date: Tue, 28 Jun 2005 19:02:06 +0200

32 bits are longer and therefore better, but the 16 bit algorithm is
- already described in RFC 1071
- supported on NICs in hardware.

Since it might be difficult to use a NIC to do the computation,
because RSerPool normally will be implemented in userland,
I would also vote for the 32 bit version and describe the
algorithm explicitly in the ENRP ID.

If others agree I can put some text in the ID.

Best regards
Michael

On Jun 28, 2005, at 15:59 Uhr, Thomas Dreibholz wrote:

> -----------------------------------------------------------------------
> iD8DBQFCwVfb32BbsHYPLWURAs2+AJ4y4dQidaFk8BluPiOCvfbSQG6WiACgpT9t
> F391kp60lLQnAatchlEmwgo=
> =3/5a

---

From: Qiaobing Xie <[email-masked]>
Date: Tue, 28 Jun 2005 15:33:19 -0500

I too agree.

-Q

Randall Stewart wrote:

> Michael Tuexen wrote:
> I agree :-D
> R

---

From: Peter Lei <[email-masked]>
Date: Wed, 29 Jun 2005 14:28:49 -0500

> If others agree I can put some text in the ID.

I agree with using 32-bit checksum.

--peter

> --