Subject: RE: Summary Re: [nemo] comments on "Tree Discovery" draft

From: "Pascal Thubert \(pthubert\)" <[email-masked]>
Date: Mon, 30 Aug 2004 14:57:55 +0200

> In fact, what do you assume "CRC-32c" to be more exactly, if I'm not
too
> ignorant.  I'd suppose it to be "Cyclic Redundancy Check (CRC) codes
> [Peterson] are shortened cyclic codes used for error detection."  But
> what is the "32c" part?  Two's complement or something on 32bit?
Which
> CRC code more exactly?

CRC32C has been proven quite strong and is used for modern protocols
such as SCTP and iSCSI. If you *really* want more, I suggest you read
rfc 3385. Enjoy :)

BTW, here's the patch file that added CRC32C to linux 2.6:

http://www.ussg.iu.edu/hypermail/linux/kernel/0403.3/1648.html

So you see: it's not like if the code was not available.

> 
> Note CRC's are for checking message integrity for error correction not
> for checking a path has changed.
> 
> Note "Digest" in "PathDigest" invites to think of message digest (like
> in "MD5"); digests are also used to check for integrity, but not for
> "path has changed".
> 
> I doubt that combining "Digest" with "CRC" makes a good tool for "path
> has changed".
> 

Imagine a message that would be the concatenation of all the careofs.
And compute a digest of that message. If anything changes in the path
(one or more careofs, the number of careofs, whatever), and if the
digest algorithm is properly distributed, there are little chances (at
best one out of 2^bits_in_digest) that the digest stays the same. We use
a 32 bits digest...

Since we do not want to pass all the list in the RA, we actually
compute:

Crc32c(CoA, Crc32c(CoA, Crc32c(CoA, Crc_32( ... Crc32c(CoA, 0) ...) ) )
)

            <--------------------------------------------------------->
            Received in TIO from Attachment Router over egress
  
<-----------------------------------------------------------------------
->
   Sent in TIO over ingress interfaces to all nodes including visitors

This also lets little chance for any change in the chain to go
undetected. So that is quite a good tool to check whether the path has
changed and I'm surprised you doubt that. Whether it's too expensive is
another issue, but this thing does the job quite well. 

Pascal

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 30 Aug 2004 15:29:11 +0200

Pascal Thubert (pthubert) wrote:
>> In fact, what do you assume "CRC-32c" to be more exactly, if I'm 
>> not too ignorant.  I'd suppose it to be "Cyclic Redundancy Check 
>> (CRC) codes [Peterson] are shortened cyclic codes used for error 
>> detection."  But what is the "32c" part?  Two's complement or 
>> something on 32bit?
> 
> Which CRC code more exactly?
> 
>  such as SCTP and iSCSI. If you *really* want more, I suggest you
> read rfc 3385. Enjoy :)

I was not saying CRC32C was not strong (although I doubt the
qualification of "strong" for an error detection code, "strong" is
better adapted for encryption codes).  I was asking what exactly is it
other than some redundancy check for communicating to SCSI devices (not
even IP over SCSI).

And why not using the classic ICMP Checksum as documented in
rfc2460/1/2/3/4.  Do you have any reason to prefer CRC32c instead of
this IPv6 checksum?  Is one having a better error detection capability
than the other?

> So you see: it's not like if the code was not available.

Ok, I was not saying that CRC32C were not publicly available.  But,
since you talk about this, and since you've mentioned there may be IPR
on TD, would the TD IPR cover the use of CRC32c?

>> Note CRC's are for checking message integrity for error correction 
>> not for checking a path has changed.
>> 
>> Note "Digest" in "PathDigest" invites to think of message digest 
>> (like in "MD5"); digests are also used to check for integrity, but 
>> not for "path has changed".
>> 
>> I doubt that combining "Digest" with "CRC" makes a good tool for 
>> "path has changed".
>> 
>  And compute a digest of that message. If anything changes in the 
> path (one or more careofs, the number of careofs, whatever), and if 
> the digest algorithm is properly distributed, there are little 
> chances (at best one out of 2^bits_in_digest) that the digest stays 
> the same. We use a 32 bits digest...

I understand that... but I don't know whether sending the digest
separated from the actual message makes much sense. Do you know about
another example mechanism where they'd send the digest separated from
the actual message? I know in S/MIME email it's not the case, in ICMP
checksums it's not the case either... if you know of such a case (where
the digest is sent separated from the original), I want to learn.

> Crc32c(CoA, Crc32c(CoA, Crc32c(CoA, Crc_32( ... Crc32c(CoA, 0) ...) )
>  ) )
> 
> <---------------------------------------------------------> Received 
> in TIO from Attachment Router over egress
> 
>  -> Sent in TIO over ingress interfaces to all nodes including 
> visitors

I understand the mechanism.  I understand how it works.  I doubt it's a
good use of CRC32c and I doubt it's an efficient and secure mechanism to
detect something has changed in the upper path.  Call me pessimistic but
I also doubt there's a need to detect something has changed in the upper
path as long as the whole "looping problem" is not actually a problem
with NEMO MR's.

> undetected.

It actually lets a big change for to falsely indicate that something has
changed when actually nothing has.  If an intermediary MR is suddenly
replace by another, the CRC stuff will be different because different
EUID's.

> So that is quite a good tool to check whether the path has changed 
> and I'm surprised you doubt that.

Do you agree that there are situations where the leaf MR will believe
something has changed when nothing has, actually?

> Whether it's too expensive is another issue, but this thing does the 
> job quite well.

Yes, expensive is another issue, but it is a certitude that it does not
do the job quite well, based on my above example with "replacing MR", no?

Alex