Incremental update of TCP Checksum

Incremental update of TCP Checksum

[Vishwas Raman]

Hi all,

I have a very simple question, which a lot of you would have solved. I 
am intercepting a TCP packet, which I would like to change slightly.

Let's say, I change the doff field of the tcp-header (for eg: increase 
it by 1). I know it is wrong just to change the doff field without 
increasing the packet length, but lets say I do it just as a test. Since 
I changed a portion of the tcp header, I have to update the tcp checksum 
too right!!! If so, what is the best way to do so, without having to 
recalculate the entire tcp checksum (I know how to recalculate the 
checksum from scratch).

Can anyone out there tell me the algorithm to update the checksum 
without having to recalculate it.

I tried the following algorithm but it didnt work. The packet got 
rejected as a packet with bad cksum.

void changePacket(struct sk_buff* skb)
{
     struct tcphdr *tcpHdr = skb->h.th;
     // Verifying the tcp checksum works here...
     tcpHeader->doff += 1;
     long cksum = (~(tcpHdr->check))&0xffff;
     cksum += 1;
     while (cksum >> 16)
     {
         cksum = (cksum & 0xffff) + (cksum >> 16);
     }
     tcpHeader->check = ~cksum;
     // Verifying tcp checksum here fails with bad cksum
}

Any pointers/help in this regard will be highly appreciated...

Thanks,

-Vishwas.

Re: Incremental update of TCP Checksum

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 866 bytes --]

On Tue, 16 Sep 2003 11:50:16 PDT, Vishwas Raman <vishwas@eternal-systems.com>  said:

> Can anyone out there tell me the algorithm to update the checksum 
> without having to recalculate it.

The canonical source is the RFCs:

1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.
     Partridge. Sep-01-1988. (Format: TXT=54941 bytes) (Updated by
     RFC1141) (Status: UNKNOWN)

1141 Incremental updating of the Internet checksum. T. Mallory, A.
     Kullberg. Jan-01-1990. (Format: TXT=3587 bytes) (Updates RFC1071)
     (Updated by RFC1624) (Status: INFORMATIONAL)

1624 Computation of the Internet Checksum via Incremental Update. A.
     Rijsinghani, Ed.. May 1994. (Format: TXT=9836 bytes) (Updates
     RFC1141) (Status: INFORMATIONAL)

http://www.ietf.org/rfc/rfc1071.txt
http://www.ietf.org/rfc/rfc1141.txt
http://www.ietf.org/rfc/rfc1624.txt

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: Incremental update of TCP Checksum

[Richard B. Johnson]

On Tue, 16 Sep 2003, Vishwas Raman wrote:

> Hi all,
>
> I have a very simple question, which a lot of you would have solved. I
> am intercepting a TCP packet, which I would like to change slightly.
>
> Let's say, I change the doff field of the tcp-header (for eg: increase
> it by 1). I know it is wrong just to change the doff field without
> increasing the packet length, but lets say I do it just as a test. Since
> I changed a portion of the tcp header, I have to update the tcp checksum
> too right!!! If so, what is the best way to do so, without having to
> recalculate the entire tcp checksum (I know how to recalculate the
> checksum from scratch).
>
> Can anyone out there tell me the algorithm to update the checksum
> without having to recalculate it.
>
> I tried the following algorithm but it didnt work. The packet got
> rejected as a packet with bad cksum.
>
> void changePacket(struct sk_buff* skb)
> {
>      struct tcphdr *tcpHdr = skb->h.th;
>      // Verifying the tcp checksum works here...
>      tcpHeader->doff += 1;
>      long cksum = (~(tcpHdr->check))&0xffff;
>      cksum += 1;
>      while (cksum >> 16)
>      {
>          cksum = (cksum & 0xffff) + (cksum >> 16);
>      }
>      tcpHeader->check = ~cksum;
>      // Verifying tcp checksum here fails with bad cksum
> }
>
> Any pointers/help in this regard will be highly appreciated...

The TCP/IP checksum is a WORD sum (unsigned short) in which
any overflow out of the word causes the word to be incremented.
The final sum is then inverted to become the checksum. Note that
many algorithms sum into a long then fold-back the bits. It's
the same thing, different method.

Therefore:
	Given an existing checksum of 0xffff, if the
	next word to be summed is 0x0001, the result
	will be 0x0001 because adding 1 to 0xffff makes
	it 0, causing an overflow which propagates to
	become 0x0001.
So:
	Clearly, information is lost because one doesn't
	know how the 0x0001 was obtained.

If I were to modify a low byte somewhere by subtracting 1,
would I know that the new checksum, excluding the inversion,
was 0x0000? No. It could be 0xffff.

This presents a problem when trying to modify existing checksums.
It's certainly easier to set the existing checksum to 0, then
re-checksum the whole packet. It's probably faster than some
looping algorithm that attempts to unwind a previous checksum.


Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (794.73 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: Incremental update of TCP Checksum

[Vishwas Raman]

Richard B. Johnson wrote:
> On Tue, 16 Sep 2003, Vishwas Raman wrote:
> 
> 
>>Hi all,
>>
>>I have a very simple question, which a lot of you would have solved. I
>>am intercepting a TCP packet, which I would like to change slightly.
>>
>>Let's say, I change the doff field of the tcp-header (for eg: increase
>>it by 1). I know it is wrong just to change the doff field without
>>increasing the packet length, but lets say I do it just as a test. Since
>>I changed a portion of the tcp header, I have to update the tcp checksum
>>too right!!! If so, what is the best way to do so, without having to
>>recalculate the entire tcp checksum (I know how to recalculate the
>>checksum from scratch).
>>
>>Can anyone out there tell me the algorithm to update the checksum
>>without having to recalculate it.
>>
>>I tried the following algorithm but it didnt work. The packet got
>>rejected as a packet with bad cksum.
>>
>>void changePacket(struct sk_buff* skb)
>>{
>>     struct tcphdr *tcpHdr = skb->h.th;
>>     // Verifying the tcp checksum works here...
>>     tcpHeader->doff += 1;
>>     long cksum = (~(tcpHdr->check))&0xffff;
>>     cksum += 1;
>>     while (cksum >> 16)
>>     {
>>         cksum = (cksum & 0xffff) + (cksum >> 16);
>>     }
>>     tcpHeader->check = ~cksum;
>>     // Verifying tcp checksum here fails with bad cksum
>>}
>>
>>Any pointers/help in this regard will be highly appreciated...
> 
> 
> The TCP/IP checksum is a WORD sum (unsigned short) in which
> any overflow out of the word causes the word to be incremented.
> The final sum is then inverted to become the checksum. Note that
> many algorithms sum into a long then fold-back the bits. It's
> the same thing, different method.
> 
> Therefore:
> 	Given an existing checksum of 0xffff, if the
> 	next word to be summed is 0x0001, the result
> 	will be 0x0001 because adding 1 to 0xffff makes
> 	it 0, causing an overflow which propagates to
> 	become 0x0001.
> So:
> 	Clearly, information is lost because one doesn't
> 	know how the 0x0001 was obtained.
> 
> If I were to modify a low byte somewhere by subtracting 1,
> would I know that the new checksum, excluding the inversion,
> was 0x0000? No. It could be 0xffff.
> 
> This presents a problem when trying to modify existing checksums.
> It's certainly easier to set the existing checksum to 0, then
> re-checksum the whole packet. It's probably faster than some
> looping algorithm that attempts to unwind a previous checksum.

Are you then suggesting that instead of trying to do an incremental 
update of the tcp checksum, I set it to 0 and recalculate it from 
scratch? But I thought that doing that was a big performance hit. Isn't it?

> 
> 
> Cheers,
> Dick Johnson
> Penguin : Linux version 2.4.22 on an i686 machine (794.73 BogoMips).
>             Note 96.31% of all statistics are fiction.
> 
> 
> 



-- 
--
Vishwas Raman
Software Engineer, Eternal Systems, Inc,
5290 Overpass Rd, Bldg D, Santa Barbara. CA 93111
Email: vishwas@eternal-systems.com
Tel:   (805) 696-9051 x246
Fax:   (805) 696-9083
URL:   http://www.eternal-systems.com/

Re: Incremental update of TCP Checksum

[Vishwas Raman]

Valdis.Kletnieks@vt.edu wrote:
> On Tue, 16 Sep 2003 11:50:16 PDT, Vishwas Raman <vishwas@eternal-systems.com>  said:
> 
> 
>>Can anyone out there tell me the algorithm to update the checksum 
>>without having to recalculate it.
> 
> 
> The canonical source is the RFCs:
> 
> 1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.
>      Partridge. Sep-01-1988. (Format: TXT=54941 bytes) (Updated by
>      RFC1141) (Status: UNKNOWN)
> 
> 1141 Incremental updating of the Internet checksum. T. Mallory, A.
>      Kullberg. Jan-01-1990. (Format: TXT=3587 bytes) (Updates RFC1071)
>      (Updated by RFC1624) (Status: INFORMATIONAL)
> 
> 1624 Computation of the Internet Checksum via Incremental Update. A.
>      Rijsinghani, Ed.. May 1994. (Format: TXT=9836 bytes) (Updates
>      RFC1141) (Status: INFORMATIONAL)
> 
> http://www.ietf.org/rfc/rfc1071.txt
> http://www.ietf.org/rfc/rfc1141.txt
> http://www.ietf.org/rfc/rfc1624.txt

As mentioned in RFC1624, I did the following.
void changePacket(struct sk_buff* skb)
{
     struct tcphdr *tcpHdr = skb->h.th;

     // Verifying the tcp checksum works here...

     __u16 oldDoff = tcpHeader->doff;
     tcpHeader->doff += 1;	

     // Formula from RFC1624 is HC' = ~(C + (-m) + m')
     // where HC  - old checksum in header
     // C   - one's complement sum of old header
     // HC' - new checksum in header
     // C'  - one's complement sum of new header
     // m   - old value of a 16-bit field
     // m'  - new value of a 16-bit field

     long cksum = (~(tcpHdr->check))&0xffff;
     cksum += (__u16)~oldDoff;
     cksum += tcpHeader->doff;
     while (cksum >> 16)
     {
         cksum = (cksum & 0xffff) + (cksum >> 16);
     }
     tcpHeader->check = ~cksum;

     // Verifying tcp checksum here fails with bad cksum
}

Is there any glaring mistake in the above code. If so, can someone
please let me know what it is. It will be of great help.

Thanks,

-Vishwas.

Re: Incremental update of TCP Checksum

[Patrick McHardy]

Vishwas Raman wrote:

> Can anyone out there tell me the algorithm to update the checksum 
> without having to recalculate it. 


Have a look at net/ipv4/netfilter/ipt_TCPMSS.c (cheat_check).

Regards,
Patrick

Re: Incremental update of TCP Checksum

[Richard B. Johnson]

On Tue, 16 Sep 2003, Vishwas Raman wrote:

>
> Richard B. Johnson wrote:
> > On Tue, 16 Sep 2003, Vishwas Raman wrote:
> >
> >
> >>Hi all,
> >>
> >>I have a very simple question, which a lot of you would have solved. I
> >>am intercepting a TCP packet, which I would like to change slightly.
> >>
> >>Let's say, I change the doff field of the tcp-header (for eg: increase
> >>it by 1). I know it is wrong just to change the doff field without
> >>increasing the packet length, but lets say I do it just as a test. Since
> >>I changed a portion of the tcp header, I have to update the tcp checksum
> >>too right!!! If so, what is the best way to do so, without having to
> >>recalculate the entire tcp checksum (I know how to recalculate the
> >>checksum from scratch).
> >>
> >>Can anyone out there tell me the algorithm to update the checksum
> >>without having to recalculate it.
> >>
> >>I tried the following algorithm but it didnt work. The packet got
> >>rejected as a packet with bad cksum.
> >>
> >>void changePacket(struct sk_buff* skb)
> >>{
> >>     struct tcphdr *tcpHdr = skb->h.th;
> >>     // Verifying the tcp checksum works here...
> >>     tcpHeader->doff += 1;
> >>     long cksum = (~(tcpHdr->check))&0xffff;
> >>     cksum += 1;
> >>     while (cksum >> 16)
> >>     {
> >>         cksum = (cksum & 0xffff) + (cksum >> 16);
> >>     }
> >>     tcpHeader->check = ~cksum;
> >>     // Verifying tcp checksum here fails with bad cksum
> >>}
> >>
> >>Any pointers/help in this regard will be highly appreciated...
> >
> >
> > The TCP/IP checksum is a WORD sum (unsigned short) in which
> > any overflow out of the word causes the word to be incremented.
> > The final sum is then inverted to become the checksum. Note that
> > many algorithms sum into a long then fold-back the bits. It's
> > the same thing, different method.
> >
> > Therefore:
> > 	Given an existing checksum of 0xffff, if the
> > 	next word to be summed is 0x0001, the result
> > 	will be 0x0001 because adding 1 to 0xffff makes
> > 	it 0, causing an overflow which propagates to
> > 	become 0x0001.
> > So:
> > 	Clearly, information is lost because one doesn't
> > 	know how the 0x0001 was obtained.
> >
> > If I were to modify a low byte somewhere by subtracting 1,
> > would I know that the new checksum, excluding the inversion,
> > was 0x0000? No. It could be 0xffff.
> >
> > This presents a problem when trying to modify existing checksums.
> > It's certainly easier to set the existing checksum to 0, then
> > re-checksum the whole packet. It's probably faster than some
> > looping algorithm that attempts to unwind a previous checksum.
>
> Are you then suggesting that instead of trying to do an incremental
> update of the tcp checksum, I set it to 0 and recalculate it from
> scratch? But I thought that doing that was a big performance hit.
> Isn't it?
>

I would just do it. No TCP/IP checksum is a "big performance hit".
An ordinary 'C' procedure does it in about 1.3 CPU clocks/byte.
The ASM checksum routine does it in about 0.54 CPU clocks/byte.
This is basically the time necessary to access memory.

Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (794.73 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: Incremental update of TCP Checksum

[Jesper Juhl]

On Tue, 16 Sep 2003, Vishwas Raman wrote:

>
> Richard B. Johnson wrote:
> > On Tue, 16 Sep 2003, Vishwas Raman wrote:
> >
> >
> >>Hi all,
> >>
> >>I have a very simple question, which a lot of you would have solved. I
> >>am intercepting a TCP packet, which I would like to change slightly.
> >>
> >>Let's say, I change the doff field of the tcp-header (for eg: increase
> >>it by 1). I know it is wrong just to change the doff field without
> >>increasing the packet length, but lets say I do it just as a test. Since
> >>I changed a portion of the tcp header, I have to update the tcp checksum
> >>too right!!! If so, what is the best way to do so, without having to
> >>recalculate the entire tcp checksum (I know how to recalculate the
> >>checksum from scratch).
> >>
> >
> > The TCP/IP checksum is a WORD sum (unsigned short) in which
> > any overflow out of the word causes the word to be incremented.
> > The final sum is then inverted to become the checksum. Note that
> > many algorithms sum into a long then fold-back the bits. It's
> > the same thing, different method.
> >
> > Therefore:
> > 	Given an existing checksum of 0xffff, if the
> > 	next word to be summed is 0x0001, the result
> > 	will be 0x0001 because adding 1 to 0xffff makes
> > 	it 0, causing an overflow which propagates to
> > 	become 0x0001.
> > So:
> > 	Clearly, information is lost because one doesn't
> > 	know how the 0x0001 was obtained.
> >
> > If I were to modify a low byte somewhere by subtracting 1,
> > would I know that the new checksum, excluding the inversion,
> > was 0x0000? No. It could be 0xffff.
> >
> > This presents a problem when trying to modify existing checksums.
> > It's certainly easier to set the existing checksum to 0, then
> > re-checksum the whole packet. It's probably faster than some
> > looping algorithm that attempts to unwind a previous checksum.
>
> Are you then suggesting that instead of trying to do an incremental
> update of the tcp checksum, I set it to 0 and recalculate it from
> scratch? But I thought that doing that was a big performance hit. Isn't it?
>
Personally I can't see that you have any other option. The way the
checksum is calculated information is lost, so it's impossible to
determine exactely what input generated the current output (the checksum).
Just as it is impossible to tell if the number 6 was generated from 2+2+2,
from 3*2 or from 3+3 or some other...  So I don't see what else you can do
except just recalculate the checksum from scratch. To try and determine
how your modification would affect the checksum would probably take far
longer than just re-calculating it.


- Jesper Juhl <jju@dif.dk>

Re: Incremental update of TCP Checksum

[Leo Mauro]

On Tuesday 16 September 2003 04:32 pm, Vishwas Raman wrote:

> As mentioned in RFC1624, I did the following.
> void changePacket(struct sk_buff* skb)
> {
>      struct tcphdr *tcpHdr = skb->h.th;
>
>      // Verifying the tcp checksum works here...
>
>      __u16 oldDoff = tcpHeader->doff;
>      tcpHeader->doff += 1;
>
>      // Formula from RFC1624 is HC' = ~(C + (-m) + m')
>      // where HC  - old checksum in header
>      // C   - one's complement sum of old header
>      // HC' - new checksum in header
>      // C'  - one's complement sum of new header
>      // m   - old value of a 16-bit field
>      // m'  - new value of a 16-bit field
>
>      long cksum = (~(tcpHdr->check))&0xffff;
>      cksum += (__u16)~oldDoff;
                       ^  should be a -

>      cksum += tcpHeader->doff;
>      while (cksum >> 16)
>      {
>          cksum = (cksum & 0xffff) + (cksum >> 16);
>      }
>      tcpHeader->check = ~cksum;
>
>      // Verifying tcp checksum here fails with bad cksum
> }

-- 
Leo Mauro
Network Security
Simon Bolivar University
Caracas, Venezuela

Re: Incremental update of TCP Checksum

[Jamie Lokier]

Richard B. Johnson wrote:
>If I were to modify a low byte somewhere by subtracting 1,
>would I know that the new checksum, excluding the inversion,
>was 0x0000? No. It could be 0xffff.

You're right about information being thrown away, but wrong because IP
checksums are more rigidly defined than that.

RFC1624 was written because the earlier RFC actually got this wrong.

As long as at least one of the checksummed words is known to be
non-zero, 0x0000 is not a possible value.  This is true of all IP checksums.

There is only one possible value of the non-complemented sum: 0xffff.

So when you subtract 1 from 0x0001, you get 0xffff.

To do this right, instead of subtracting a word, you add the
complement of the word.  After carry-folding, this works out right.

Vishwas Raman wrote:
> Are you then suggesting that instead of trying to do an incremental 
> update of the tcp checksum, I set it to 0 and recalculate it from 
> scratch? But I thought that doing that was a big performance hit. Isn't it?

You don't need to recalculate the sum.  All routers modify the IP
header checksum when they decrement the TTL of a packet - it's a
widely used algorithm.  Equation 3 from RFC1624 is correct :)

Your code looks fine to me.  Are you sure you're verifying the
checksum correctly?

>     while (cksum >> 16)
>     {
>         cksum = (cksum & 0xffff) + (cksum >> 16);
>     }

In general you need to add back the carry bits at most twice, btw.

	cksum = (cksum & 0xffff) + (cksum >> 16);
	cksum += (cksum >> 16);

-- Jamie

Re: Incremental update of TCP Checksum

[Vishwas Raman]

Jamie Lokier wrote:
> Richard B. Johnson wrote:
> 
>>If I were to modify a low byte somewhere by subtracting 1,
>>would I know that the new checksum, excluding the inversion,
>>was 0x0000? No. It could be 0xffff.
> 
> 
> You're right about information being thrown away, but wrong because IP
> checksums are more rigidly defined than that.
> 
> RFC1624 was written because the earlier RFC actually got this wrong.
> 
> As long as at least one of the checksummed words is known to be
> non-zero, 0x0000 is not a possible value.  This is true of all IP checksums.
> 
> There is only one possible value of the non-complemented sum: 0xffff.
> 
> So when you subtract 1 from 0x0001, you get 0xffff.
> 
> To do this right, instead of subtracting a word, you add the
> complement of the word.  After carry-folding, this works out right.
> 
> Vishwas Raman wrote:
> 
>>Are you then suggesting that instead of trying to do an incremental 
>>update of the tcp checksum, I set it to 0 and recalculate it from 
>>scratch? But I thought that doing that was a big performance hit. Isn't it?
> 
> 
> You don't need to recalculate the sum.  All routers modify the IP
> header checksum when they decrement the TTL of a packet - it's a
> widely used algorithm.  Equation 3 from RFC1624 is correct :)

I was also under the belief that RFC1624 was handling this correctly.

> 
> Your code looks fine to me.  Are you sure you're verifying the
> checksum correctly?


This is how I am verifying the checksum. It seems to work in other 
cases. (by the way, I am working with the 2.4.20 kernel src code)

/* I do this check for only packets that are less than or equal to 76 
bytes in length. And I make sure the packets that I am dealing with are 
less than this length */

int tcpFailoverVerifyChecksum(struct sk_buff* skb)
{
     int len = skb->len - sizeof(struct iphdr);
     retValue = tcp_v4_check(skb->h.th, len,
                             skb->nh.iph->saddr, skb->nh.iph->daddr,
                             csum_partial((char *)skb->h.th, len, 0));
     return retValue;
}

Is the above function right? If not, what is the right way to verify the 
checksum of a tcp packet?


> 
> 
>>    while (cksum >> 16)
>>    {
>>        cksum = (cksum & 0xffff) + (cksum >> 16);
>>    }
> 
> 
> In general you need to add back the carry bits at most twice, btw.
> 
> 	cksum = (cksum & 0xffff) + (cksum >> 16);
> 	cksum += (cksum >> 16);

Ok...I will make the change... Thks...

Re: Incremental update of TCP Checksum

[Lincoln Dale]

At 06:35 AM 17/09/2003, Jesper Juhl wrote:
>Personally I can't see that you have any other option. The way the
>checksum is calculated information is lost, so it's impossible to
>determine exactely what input generated the current output (the checksum).
>Just as it is impossible to tell if the number 6 was generated from 2+2+2,
>from 3*2 or from 3+3 or some other...  So I don't see what else you can do
>except just recalculate the checksum from scratch. To try and determine
>how your modification would affect the checksum would probably take far
>longer than just re-calculating it.

of course you can do an incremental checksum update.
you know that if you're changing a field from (say) 0x22 to 0x11 then you 
can 'back out' the 0x22 and recalculate the checksum with 0x11.

this is the whole rationale behind why its a _checksum_ and not a _CRC_.

router(s) have taken advantage of incremental since day one.



cheers,

lincoln.

Re: Incremental update of TCP Checksum

[Jesper Juhl]

On Wed, 17 Sep 2003, Lincoln Dale wrote:

> At 06:35 AM 17/09/2003, Jesper Juhl wrote:
> >Personally I can't see that you have any other option. The way the
> >checksum is calculated information is lost, so it's impossible to
> >determine exactely what input generated the current output (the checksum).
> >Just as it is impossible to tell if the number 6 was generated from 2+2+2,
> >from 3*2 or from 3+3 or some other...  So I don't see what else you can do
> >except just recalculate the checksum from scratch. To try and determine
> >how your modification would affect the checksum would probably take far
> >longer than just re-calculating it.
>
> of course you can do an incremental checksum update.
> you know that if you're changing a field from (say) 0x22 to 0x11 then you
> can 'back out' the 0x22 and recalculate the checksum with 0x11.
>
> this is the whole rationale behind why its a _checksum_ and not a _CRC_.
>
> router(s) have taken advantage of incremental since day one.
>

I stand corrected.  Thank you for pointing that out.

Jesper Juhl <jju@dif.dk>

Re: Incremental update of TCP Checksum

[Raf D'Halleweyn]

This is what I wrote some time ago. But I haven't used it recently.

/* Incrementaly update a checksum, given old and new 32bit words */
static inline __u16 incr_check_l(__u16 old_check, __u32 old, __u32 new)
{ /* see RFC's 1624, 1141 and 1071 for incremental checksum updates */
    __u32 l;
    old_check = ~ntohs(old_check);
    old = ~old;
    l = (__u32)old_check + (old>>16) + (old&0xffff)
        + (new>>16) + (new&0xffff);
    return htons(~( (__u16)(l>>16) + (l&0xffff) ));
}


I have a similar function that can be used when you only change a 16bit
word:


/* Incrementaly update a checksum, given old and new 16bit words */
static inline __u16 incr_check_s(__u16 old_check, __u16 old, __u16 new)
{    /* see RFC's 1624, 1141 and 1071 for incremental checksum updates
*/
    __u32 l;
    old_check = ~ntohs(old_check);
    old = ~old;
    l = (__u32)old_check + old + new;
    return htons(~( (__u16)(l>>16) + (l&0xffff) ));
}


On Tue, 2003-09-16 at 16:32, Vishwas Raman wrote:
> Valdis.Kletnieks@vt.edu wrote:
> > On Tue, 16 Sep 2003 11:50:16 PDT, Vishwas Raman <vishwas@eternal-systems.com>  said:
> > 
> > 
> >>Can anyone out there tell me the algorithm to update the checksum 
> >>without having to recalculate it.
> > 
> > 
> > The canonical source is the RFCs:
> > 
> > 1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.
> >      Partridge. Sep-01-1988. (Format: TXT=54941 bytes) (Updated by
> >      RFC1141) (Status: UNKNOWN)
> > 
> > 1141 Incremental updating of the Internet checksum. T. Mallory, A.
> >      Kullberg. Jan-01-1990. (Format: TXT=3587 bytes) (Updates RFC1071)
> >      (Updated by RFC1624) (Status: INFORMATIONAL)
> > 
> > 1624 Computation of the Internet Checksum via Incremental Update. A.
> >      Rijsinghani, Ed.. May 1994. (Format: TXT=9836 bytes) (Updates
> >      RFC1141) (Status: INFORMATIONAL)
> > 
> > http://www.ietf.org/rfc/rfc1071.txt
> > http://www.ietf.org/rfc/rfc1141.txt
> > http://www.ietf.org/rfc/rfc1624.txt
> 
> As mentioned in RFC1624, I did the following.
> void changePacket(struct sk_buff* skb)
> {
>      struct tcphdr *tcpHdr = skb->h.th;
> 
>      // Verifying the tcp checksum works here...
> 
>      __u16 oldDoff = tcpHeader->doff;
>      tcpHeader->doff += 1;	
> 
>      // Formula from RFC1624 is HC' = ~(C + (-m) + m')
>      // where HC  - old checksum in header
>      // C   - one's complement sum of old header
>      // HC' - new checksum in header
>      // C'  - one's complement sum of new header
>      // m   - old value of a 16-bit field
>      // m'  - new value of a 16-bit field
> 
>      long cksum = (~(tcpHdr->check))&0xffff;
>      cksum += (__u16)~oldDoff;
>      cksum += tcpHeader->doff;
>      while (cksum >> 16)
>      {
>          cksum = (cksum & 0xffff) + (cksum >> 16);
>      }
>      tcpHeader->check = ~cksum;
> 
>      // Verifying tcp checksum here fails with bad cksum
> }
> 
> Is there any glaring mistake in the above code. If so, can someone
> please let me know what it is. It will be of great help.
> 
> Thanks,
> 
> -Vishwas.
> 
> 
> 
> 
> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
-- 
Raf D'Halleweyn <raf@noduck.net>

Re: Incremental update of TCP Checksum

[David S. Miller]

On Tue, 16 Sep 2003 23:28:26 -0400
"Raf D'Halleweyn" <raf@noduck.net> wrote:

> This is what I wrote some time ago. But I haven't used it recently.

See include/net/ip.h:ip_increase_ttl().  Most people get this
code wrong, in particular the final carry.

Re: Incremental update of TCP Checksum

[Richard B. Johnson]

On Tue, 16 Sep 2003, Raf D'Halleweyn wrote:

>
> This is what I wrote some time ago. But I haven't used it recently.
>
> /* Incrementaly update a checksum, given old and new 32bit words */
> static inline __u16 incr_check_l(__u16 old_check, __u32 old, __u32 new)
> { /* see RFC's 1624, 1141 and 1071 for incremental checksum updates */
>     __u32 l;
>     old_check = ~ntohs(old_check);
>     old = ~old;
>     l = (__u32)old_check + (old>>16) + (old&0xffff)
>         + (new>>16) + (new&0xffff);
>     return htons(~( (__u16)(l>>16) + (l&0xffff) ));
> }
>
>
> I have a similar function that can be used when you only change a 16bit
> word:
>
>
> /* Incrementaly update a checksum, given old and new 16bit words */
> static inline __u16 incr_check_s(__u16 old_check, __u16 old, __u16 new)
> {    /* see RFC's 1624, 1141 and 1071 for incremental checksum updates
> */
>     __u32 l;
>     old_check = ~ntohs(old_check);
>     old = ~old;
>     l = (__u32)old_check + old + new;
>     return htons(~( (__u16)(l>>16) + (l&0xffff) ));
> }
>
>
> On Tue, 2003-09-16 at 16:32, Vishwas Raman wrote:
> > Valdis.Kletnieks@vt.edu wrote:
> > > On Tue, 16 Sep 2003 11:50:16 PDT, Vishwas Raman <vishwas@eternal-
> > > systems.com>  said:
> > >
> > >
> > >>Can anyone out there tell me the algorithm to update the checksum
> > >>without having to recalculate it.
> > >
> > >
> > > The canonical source is the RFCs:
> > >
> > > 1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.
> > >      Partridge. Sep-01-1988. (Format: TXT=54941 bytes) (Updated by
> > >      RFC1141) (Status: UNKNOWN)
> > >
> > > 1141 Incremental updating of the Internet checksum. T. Mallory, A.
> > >      Kullberg. Jan-01-1990. (Format: TXT=3587 bytes) (Updates RFC1071)
> > >      (Updated by RFC1624) (Status: INFORMATIONAL)
> > >
> > > 1624 Computation of the Internet Checksum via Incremental Update. A.
> > >      Rijsinghani, Ed.. May 1994. (Format: TXT=9836 bytes) (Updates
> > >      RFC1141) (Status: INFORMATIONAL)
> > >
> > > http://www.ietf.org/rfc/rfc1071.txt
> > > http://www.ietf.org/rfc/rfc1141.txt
> > > http://www.ietf.org/rfc/rfc1624.txt
> >
> > As mentioned in RFC1624, I did the following.
> > void changePacket(struct sk_buff* skb)
> > {
> >      struct tcphdr *tcpHdr = skb->h.th;
> >
> >      // Verifying the tcp checksum works here...
> >
> >      __u16 oldDoff = tcpHeader->doff;
> >      tcpHeader->doff += 1;
> >
> >      // Formula from RFC1624 is HC' = ~(C + (-m) + m')
> >      // where HC  - old checksum in header
> >      // C   - one's complement sum of old header
> >      // HC' - new checksum in header
> >      // C'  - one's complement sum of new header
> >      // m   - old value of a 16-bit field
> >      // m'  - new value of a 16-bit field
> >
> >      long cksum = (~(tcpHdr->check))&0xffff;
> >      cksum += (__u16)~oldDoff;
> >      cksum += tcpHeader->doff;
> >      while (cksum >> 16)
> >      {
> >          cksum = (cksum & 0xffff) + (cksum >> 16);
> >      }
> >      tcpHeader->check = ~cksum;
> >
> >      // Verifying tcp checksum here fails with bad cksum
> > }
> >
> > Is there any glaring mistake in the above code. If so, can someone
> > please let me know what it is. It will be of great help.
> >
> > Thanks,
> >
> > -Vishwas.


This is all wonderful. This assumes that the stuff being modified
in the packet is on well-defined boundaries, seldom the case when
you are re-writing packet data, but certainly the case if you
are re-writing an IP address.

Also, modern switches do not rewrite checksums using software.
Therefore, they do not use a re-write algorithm as stated by
others. The checksum gets calculated "for free" during the
hardware transfer to an output holding FIFO. It is done using
an ASIC with the appropriate adder and "stumble-carry".

Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (794.73 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: Incremental update of TCP Checksum

[Ihar 'Philips' Filipau]

Richard B. Johnson wrote:
> 
> This is all wonderful. This assumes that the stuff being modified
> in the packet is on well-defined boundaries, seldom the case when
> you are re-writing packet data, but certainly the case if you
> are re-writing an IP address.
> 
> Also, modern switches do not rewrite checksums using software.
                                                        ^^^^^^^^
> Therefore, they do not use a re-write algorithm as stated by
> others. The checksum gets calculated "for free" during the
> hardware transfer to an output holding FIFO. It is done using
> an ASIC with the appropriate adder and "stumble-carry".
> 

   It depends on definition of software. It is so hard to draw parallel 
especially when what looks like controller runs some flavour of Linux 
from some embedded flash ;-)

   Actually some switches do alter header _before_ they have received 
payload. Just to be able to start rx without waiting for payload to 
arrive completely. Sometimes low latencies (even on narrow bandwidth 
links) are _that_ important...

-- 
Ihar 'Philips' Filipau  / with best regards from Saarbruecken.
   -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
   * Please avoid sending me Word/PowerPoint/Excel attachments.
   * See http://www.fsf.org/philosophy/no-word-attachments.html
   -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
    There should be some SCO's source code in Linux -
       my servers sometimes are crashing.      -- People

Re: Incremental update of TCP Checksum

[Jamie Lokier]

Richard B. Johnson wrote:
> This is all wonderful. This assumes that the stuff being modified
> in the packet is on well-defined boundaries, seldom the case when
> you are re-writing packet data, but certainly the case if you
> are re-writing an IP address.

The only important boundary consideration is whether you're modifying
at an odd or even byte offset into the packet.

-- Jamie