Incremental update of TCP Checksum
Valdis.K...@vt.edu
> 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
Vishwas Raman
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 majo...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Richard B. Johnson
>
> 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.
Leo Mauro
> 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
Vishwas Raman
> 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.
>
>
> 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?
>
>
> 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...