Subject: [Isis-wg] Checksum

From: Ethan Burns <[email-masked]>
Date: Tue, 22 Jun 2004 13:29:52 -0400

Hello,
	I was wondering if someone could help me.  I am trying to implement the
checksum algorithem in the LSP packets of IS-IS.  I am very confused 
as to what values to use in the initialization of C0 and C1.  Any help on this
would be greatly appreciated.

		--Ethan Burns--

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

---

From: Hannes Gredler <[email-masked]>
Date: Wed, 23 Jun 2004 11:48:44 +0200

On Tue, Jun 22, 2004 at 01:29:52PM -0400, Ethan Burns wrote:
| Hello,
| 	I was wondering if someone could help me.  I am trying to implement the
| checksum algorithem in the LSP packets of IS-IS.  I am very confused 
| as to what values to use in the initialization of C0 and C1.  Any help on this
| would be greatly appreciated.

you may want to have a look at isisd/isis_checksum.c [attached];

/hannes

---

From: Jeff Learman <[email-masked]>
Date: Wed, 23 Jun 2004 10:10:48 -0400

>would be greatly appreciated.

My interpretation of what 10589 says:

At system init, initialize C0 & C1 to zero, run the algorithm on
your System ID, and save these values for subsequent use.
Of course, repeat this whenever your System ID changes.

Your system ID is typically your MAC address.

For received packets, initialize C0 and C1 to zero and checksum the
packet starting at offset 12 (beginning of LSP ID field).

For generated packets, initialize C0 and C1 to the saved values.
Then run the checksum algorithm starting at offset 12 + IdLength
(IdLength is typically 6).

No warranty.  I did not look at Cisco code to verify this, and I
have not worked on ISIS at Cisco.

Jeff

---

From: Satish Dattatri <[email-masked]>
Date: Wed, 23 Jun 2004 15:02:12 -0700 (PDT)

> would be greatly appreciated.

Lookup 8473 Annex C for some detail explanation. The algorithm itself requires
c0 and c1 to be initialized to 'zero'. 

However, 7.3.11 of ISO10589 mentions to keep c0 and c1 to be initialized to 
the values after calculating the algorithm upto the end of system-id.
The reasoning is that if the system id gets corrupted and the IS generates
LSP with bogus system-id the receiving IS will drop the pdu becoz of 
checksum mismatch.

This kind of logic is flawed IMO becoz what if the system-id is not corrupted
but the cached c0 and c1 values are .... 

I would just have the c0 and c1 initialized to zero and do the checksum.

Satish

---

From: Jeff Learman <[email-masked]>
Date: Thu, 24 Jun 2004 17:25:54 -0400

>but the cached c0 and c1 values are .... 

In that case all transmitted LSPs will be rejected.  That's not a
big problem.  The problem is when one system sends LSPs that appear
to be sent by another system, with a valid checksum.  This has to
be avoided at all costs, and the suggested method helps dramatically.

Many of the "strange" features of ISIS are solutions to actual problems
discovered in the Arpanet.  Things are nasty when a flooding mechanism
goes wild.  I don't know whether this is one of those cases.  The ugly
sequence number system definitely is, and you can read about that in
Radia Perlman's book, "Interconnections".

Jeff

---

From: Les Ginsberg <[email-masked]>
Date: Thu, 24 Jun 2004 14:57:10 -0700

>but the cached c0 and c1 values are ....

Satish -

What happens is exactly what should happen when there is memory corruption. 
The checksum sent with the locally generated LSP will not be correct when 
validated at the receiving end - which means that receiver will not accept 
updates received from a corrupted box. Doesn't matter whether the 
corruption was in the stored system ID or on the precalculated checksum - 
either way the originator is not to be trusted.

A prudent implementation would periodically validate that the stored 
precalculated checkum matches the stored system ID so that it would not 
continue operating indefinitely in a corrupted state. There are, of course, 
a number of ways to do this. :-)

    Les

---

From: Satish Dattatri <[email-masked]>
Date: Thu, 24 Jun 2004 23:11:37 -0700 (PDT)

I have combined the last mails.

--- Jeff Learman <[email-masked]> wrote:

[my old mail]
> >LSP with bogus system-id the receiving IS will drop the pdu becoz of 

[Jeff]
> be avoided at all costs, and the suggested method helps dramatically.

[Les]
> either way the originator is not to be trusted.

We all agree that the steps in the spec makes the IS generate 
packets with bad checksum as designed. The receiving IS will
*drop* the pdu.

If an implementation can detect that it's system-id is corrupted 
then it can take corrective actions rather than send these
*bad* pdu's in the network. 

I am  not  comfortable   with flooding bad  packets and what  is
the  guarantee that only system-id is  corrupted ??? This is what
is flawed, the spec assumes that  there are  situations where only
system-id  is  corrupted.  My example of c0 and c1  was  not  good.

> >but the cached c0 and c1 values are .... 

[Jeff]
> Radia Perlman's book, "Interconnections".

Nothing like a lesson from  the actual  network outage ;-)

[Les]
> a number of ways to do this. :-)

That  is  good,  however I would prefer  the implementation  to take
serious corrective  action ;-)

All in all if the  spec  said that  system-id  corruption is  a serious
issue and implementations should handle it. Further it could have
mentioned  the caching of c0 and c1 or  protocol shutdown.
Rather the spec mentions  a  solution  as MUST be done  this way. That is
what I  do  not  agree  with. 

Satish

---

From: Dave Katz <[email-masked]>
Date: Thu, 24 Jun 2004 23:58:20 -0700

> what I  do  not  agree  with.

Regardless of what the spec says, you can implement it any way you want 
so long as what goes out on the wire is correct.  You can precalculate 
the system ID into C0/C1, or leave it zero, or do whatever else you 
want to, so long as the proper checksum ends up in the outgoing 
packets.  There are no implementation police to come audit your code;  
all that counts is interoperability and what shows up on the wire.

---

From: John Harper <[email-masked]>
Date: Fri, 25 Jun 2004 00:35:58 -0700

Well, yes and no. Of course Dave is absolutely right from the point of view 
that
there is no way that "they" can come and get you if you do it some different
way. Otoh there was a reason behind the way it is specified, as previous
posters have identified. Back when the protocol was defined, there was a lot
of thought given to all the possible failure modes and how to limit their
impact. So really the "must" should be interpreted as strong advice for
how to build a sound implementation, given that it is not verifiable by
black-box methods (well, we could expose your implementation to
high density gamma rays and see what happened I suppose).
Or it could be read as "if you really, really, really understand the
thinking behind what is specified here, and you can figure out another
way to achieve the same thing, that's fine. But if not, just do what the
spec says and stop complaining".

         John

At 11:58 PM 6/24/2004 -0700, Dave Katz wrote:

>Regardless of what the spec says, you can implement it any way you want so 
>long as what goes out on the wire is correct.  You can precalculate the 
>system ID into C0/C1, or leave it zero, or do whatever else you want to, 
>so long as the proper checksum ends up in the outgoing packets.  There are 
>no implementation police to come audit your code;

---

From: Satish Dattatri <[email-masked]>
Date: Fri, 25 Jun 2004 00:47:04 -0700 (PDT)

> all that counts is interoperability and what shows up on the wire.

Agree 100%. Still, is it not little odd that the specification says 
we will be extra  careful  about sytem-id corruption, however if it 
occurs  let us flood bad packet.

While writing the email, I did think about specification ("on the wire")
and implementation separation, and your position on the same wrt 
OSPF and ISIS ;-)

---

From: Satish Dattatri <[email-masked]>
Date: Fri, 25 Jun 2004 01:13:22 -0700 (PDT)

> impact. So really the "must" should be interpreted as strong advice for

Exactly, isn't the  impact  much lower if the IS just gives up becoz of
system-id corruption ... (I know I have repeated this, sorry)

> spec says and stop complaining".

I am not complaining ;-) But would  be better if the spec said something 
along the lines of:

- keep a cache of c0 and c1 based on the system-id.
- later when generating checksum, do cksum until the system-id and
  verify the cached values of c0 and c1 with the newly computed ones.
- if they are different then take corrective actions.

(in  summary: Find out if system-id is corrupted and if so take
 action)

My concern being, what is specified in ISO10589 would lead a verbatim
implementation to keep sending bad pdu's in this scenario. 
Limited impact would be if such a system gracefully shutdowns. How
a system knows that it is insane, if  at all  it can come to that
conclusion in various other corruption scenarios is beyond me.

---

From: Tony Li <[email-masked]>
Date: Fri, 25 Jun 2004 01:30:23 -0700

The other exception is when Dave is the one doing your code review.  ;-)

Tony

On Jun 25, 2004, at 12:35 AM, John Harper wrote:

> Well, yes and no. Of course Dave is absolutely right from the point of 
> view that
>> Regardless of what the spec says, you can implement it any way you 
>> want so long as what goes out on the wire is correct.  You can 
>> precalculate the system ID into C0/C1, or leave it zero, or do 
>> whatever else you want to, so long as the proper checksum ends up in 
>> the outgoing packets.  There are no implementation police to come 
>> audit your code;

---

From: Dave Katz <[email-masked]>
Date: Fri, 25 Jun 2004 10:52:17 -0700

> spec says and stop complaining".

It's worth noting that at least one of these clever mechanisms led to 
disaster.  The original (1992) 10589 said that if you received an LSP 
with a bad checksum, you were to purge it.  The theory was that bad LSP 
checksums could only occur due to memory corruption in some machine in 
the network, so by purging the LSP the originator would be motivated to 
regenerate it and thus cause the corrupted copy to be flushed.

Of course, sometime back in about 1996 a line card in UUnet had a 
rather bad problem--it would corrupt data while delivering the packets 
with valid datalink checksums.  The neighbor started purging LSPs.  
Since, by definition, all LSPs must traverse all links, this led to a 
rather poorly behaved network (with all LSPs being continuously purged 
and regenerated.)  Quite spectacular, for train wreck afficionados.  
This led to a widespread "violation" of the spec (though a fully 
interoperable one) to ignore LSPs with bad checksums, and I believe 
that this got changed in a defect report.

Having said all that, this particular clever hack is, well, clever, and 
doesn't hurt anything (though it would hurt a lot more if the above 
change hadn't been made.)  There are no magic bullets to fix all 
possible implementation problems;  at best a protocol can try to 
protect the network in the face of a misbehaving system, but there is 
an assumption that everyone is playing by the rules.  (ISIS makes this 
assumption a bit less than OSPF does, FWIW.)

I'm pretty militant about what is normative and what is an 
implementation choice, and have been heard more than once snarling "it 
doesn't matter if what I send is out of spec, so long as you are 
required to do the right thing when you receive it!" (which is an 
ill-tempered way of saying "this is overspecified.")  I don't recommend 
this attitude for everyone, however.  ;-)

---

From: Dave Katz <[email-masked]>
Date: Fri, 25 Jun 2004 11:00:16 -0700

> occurs  let us flood bad packet.

Think of it as a distributed algorithm.  ;-)

There is nothing to stop you from periodically checksumming any or all 
of your internal state information if you want to be a better network 
citizen, but the sysid hack is a nice way to avoid filling the 
collective memory of the network with a bunch of bogus link state 
information that can't be traced to its originator (it's better to send 
bad LSPs and have them dropped by the immediate neighbors than it is to 
send bad LSPs and have them survive in everyone's databases.)

I've seen situations with other protocols where identity got confused, 
and it's tough to debug (and difficult to find the perpetrator.)  It 
was especially cool when a certain DV protocol with a large metric 
space had a bunch of routes counting to infinity (for weeks on end.)

> and implementation separation, and your position on the same wrt

Old habits die hard.  ;-)

--Dave

---

From: Satish Dattatri <[email-masked]>
Date: Fri, 25 Jun 2004 13:01:57 -0700 (PDT)

> send bad LSPs and have them survive in everyone's databases.)

Much better is for the box to not send bad LSPs, if it can avoid.
And thanks for referring to it as  "sysid hack".

While calculating the checksum, it is straightforward for the box to
compare the cached values of c0 and c1 with current value generated
based on system-id and hence take corrective action. 

My nit here is,  once there is corruption, unless it is temporary ;-)
there is no reason to continue operating ...  Maybe the dominant
implementations already detect and take corrective action.

Thanks Dave for sharing couple of history lessons. It always helps
to learn from them.

---

From: Dave Katz <[email-masked]>
Date: Fri, 25 Jun 2004 13:46:17 -0700

> Much better is for the box to not send bad LSPs, if it can avoid.

Sure, but of course if there's a bad enough bug to cause bad LSPs, 
there's no telling if the code is sane enough to not send them.

> And thanks for referring to it as  "sysid hack".

I meant it in the most affectionate way.  ;-)

> based on system-id and hence take corrective action.

I'm sure there are better ideas.  The one listed in the spec is pretty 
much a zero-overhead way of helping protect the network, which is a 
useful thing.  Implementors are free to be arbitrarily clever in their 
own ways.