Skip to contentSkip to conversation

Netfiltering - NF_IP_LOCAL_OUT - how it works???

DISCUSSION Vishwas Raman 11 participants 20 messages Aug 14, 2003 – Sep 17, 2003

lore
Share & tools
lore
#0 lore raw

Hi,

I am working with the 2.4.20 kernel.

The module I am writing is supposed to intercept all outgoing packets passing between the TCP and IP layer. I was trying to use the netfiltering mechanism for that purpose.

While initializing the module, I register a NF_IP_LOCAL_OUT hook for the outgoing packet and change skb->dst->output to my_ip_output() instead of ip_output() in that hook function. After loading the module, I see control being transferred to my_ip_output() for all outgoing packets which in turn calls ip_output() and everything seems to work well.

The exit function of the module also unregisters the hook that I am using.

The problem is that after I unload the module, which in turn unregisters the hook, I have a kernel panic happening each time I use TCP.

The panic occurs at the following point, ip_build_and_send_pkt() in ip_output.c where it is trying to call

    NF_HOOK(PF_INET, NF_IP_LOCAL_OUT, skb, NULL, rt->u.dst.dev,
                    output_maybe_reroute);

I thought once the unregistering of the hook is done, it no longer looks for that hook function. I have no idea why it is failing. May be I am doing something grossly wrong with netfiltering. Anyone who is familiar with netfiltering and has registered and unregistered hooks before might be able to guide me regarding this.

Any help will be appreciated.

Thanks,

-Vishwas.

#1 lore raw

Hi Vishwas, sorry for the late reply. Most netfilter developers have been to the netfilter developer workshop, I guess.

you should ask this question on the netfilter-devel mailinglist, where it is more on-topic than on lkml.

Quoted 14 lines · Vishwas Raman

While initializing the module, I register a NF_IP_LOCAL_OUT hook for the outgoing packet and change skb->dst->output to my_ip_output() instead of ip_output() in that hook function. After loading the module, I see control being transferred to my_ip_output() for all outgoing packets which in turn calls ip_output() and everything seems to work well.

The exit function of the module also unregisters the hook that I am using.

The problem is that after I unload the module, which in turn unregisters the hook, I have a kernel panic happening each time I use TCP.

The panic occurs at the following point, ip_build_and_send_pkt() in ip_output.c where it is trying to call

Quoted 8 lines
    NF_HOOK(PF_INET, NF_IP_LOCAL_OUT, skb, NULL, rt->u.dst.dev,
                    output_maybe_reroute);

I thought once the unregistering of the hook is done, it no longer looks for that hook function. I have no idea why it is failing. May be I am doing something grossly wrong with netfiltering. Anyone who is familiar with netfiltering and has registered and unregistered hooks before might be able to guide me regarding this.

I think either you are doing something wrong while unregistering from the netfilter hook - or you are running into a race condition. It might happen, that you assign the skb->dst->output function of a packet to your function, and then you remove the module before that packet is actually sent.

Quoted 1 line

-Vishwas.

Signature · 3 lines
- Harald Welte <[email protected]>               http://www.gnumonks.org/
============================================================================
Programming is like sex: One mistake and you have to support it your lifetime
#2 lore raw
Quoted 20 lines · Harald Welte

Hi Vishwas, sorry for the late reply. Most netfilter developers have been to the netfilter developer workshop, I guess.

you should ask this question on the netfilter-devel mailinglist, where it is more on-topic than on lkml.

Quoted 11 lines · Vishwas Raman

While initializing the module, I register a NF_IP_LOCAL_OUT hook for the outgoing packet and change skb->dst->output to my_ip_output() instead of ip_output() in that hook function. After loading the module, I see control being transferred to my_ip_output() for all outgoing packets which in turn calls ip_output() and everything seems to work well.

The exit function of the module also unregisters the hook that I am using.

The problem is that after I unload the module, which in turn unregisters the hook, I have a kernel panic happening each time I use TCP.

The panic occurs at the following point, ip_build_and_send_pkt() in ip_output.c where it is trying to call

   NF_HOOK(PF_INET, NF_IP_LOCAL_OUT, skb, NULL, rt->u.dst.dev,
                   output_maybe_reroute);
Quoted 8 lines
Quoted 1 line

I thought once the unregistering of the hook is done, it no longer looks for that hook function. I have no idea why it is failing. May be I am doing something grossly wrong with netfiltering. Anyone who is familiar with netfiltering and has registered and unregistered hooks before might be able to guide me regarding this.

I think either you are doing something wrong while unregistering from the netfilter hook - or you are running into a race condition. It might happen, that you assign the skb->dst->output function of a packet to your function, and then you remove the module before that packet is actually sent.

Actually I did solve the problem. All I had to do was reset skb->dst->output() to ip_output() in my_ip_output() which is defined in my module. The problem was that even after my module was unloaded the destination cache was still pointing to my_ip_output() which was non-existent...

Thanks,

-Vishwas.

Quoted 5 lines
Quoted 3 lines

-Vishwas.

Signature · 8 lines
--
Vishwas Raman
Software Engineer, Eternal Systems, Inc,
5290 Overpass Rd, Bldg D, Santa Barbara. CA 93111
Email: [email protected]
Tel:   (805) 696-9051 x246
Fax:   (805) 696-9083
URL:   http://www.eternal-systems.com/
#3 lore raw

Incremental update of TCP Checksum

In reply to Harald Welte

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.

#4 lore raw

Re: Incremental update of TCP Checksum

Quoted 2 lines · Vishwas Raman

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

#11 lore raw

Re: Incremental update of TCP Checksum

In reply to Vishwas Raman
Quoted 34 lines · 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
}
Quoted 1 line

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.

#12 lore raw

Re: Incremental update of TCP Checksum

Quoted 56 lines · Richard B. Johnson
Quoted 34 lines · 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
}
Quoted 1 line

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.
Quoted 8 lines

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?

Quoted 9 lines

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

Signature · 8 lines
--
Vishwas Raman
Software Engineer, Eternal Systems, Inc,
5290 Overpass Rd, Bldg D, Santa Barbara. CA 93111
Email: [email protected]
Tel:   (805) 696-9051 x246
Fax:   (805) 696-9083
URL:   http://www.eternal-systems.com/
#13 lore raw

Re: Incremental update of TCP Checksum

Quoted 67 lines · Vishwas Raman
Quoted 56 lines · Richard B. Johnson
Quoted 34 lines · 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
}
Quoted 1 line

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.
Quoted 8 lines

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.

Quoted 5 lines

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.

#19 lore raw

Re: Incremental update of TCP Checksum

In reply to Vishwas Raman
Quoted 1 line · Vishwas Raman

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

#5 lore raw

Re: Incremental update of TCP Checksum

In reply to [email protected]
Quoted 16 lines · [email protected] wrote:
Quoted 1 line · Vishwas Raman

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)

Quoted 7 lines

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.

#14 lore raw

Re: Incremental update of TCP Checksum

In reply to Vishwas Raman
Quoted 39 lines · Vishwas Raman
Quoted 37 lines · Richard B. Johnson
Quoted 5 lines · 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.

Quoted 8 lines

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.

Quoted 9 lines
Quoted 4 lines

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 <[email protected]>

#6 lore raw

Re: Incremental update of TCP Checksum

In reply to Vishwas Raman
Quoted 12 lines · 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
Quoted 8 lines
     // 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 -

Quoted 9 lines
     cksum += tcpHeader->doff;
     while (cksum >> 16)
     {
         cksum = (cksum & 0xffff) + (cksum >> 16);
     }
     tcpHeader->check = ~cksum;

     // Verifying tcp checksum here fails with bad cksum
}
Signature · 4 lines
Leo Mauro
Network Security
Simon Bolivar University
Caracas, Venezuela
#17 lore raw

Re: Incremental update of TCP Checksum

In reply to Vishwas Raman
Quoted 3 lines · Richard B. Johnson

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.

Quoted 3 lines · Vishwas Raman

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?

Quoted 4 lines
    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

#18 lore raw

Re: Incremental update of TCP Checksum

Quoted 22 lines · Jamie Lokier
Quoted 3 lines · Richard B. Johnson

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.

Quoted 8 lines
Quoted 1 line · Vishwas Raman

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.

Quoted 3 lines

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?

Quoted 8 lines
Quoted 6 lines

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

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

#15 lore raw

Re: Incremental update of TCP Checksum

In reply to Jesper Juhl
Quoted 8 lines · Jesper Juhl

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.

#16 lore raw

Re: Incremental update of TCP Checksum

Quoted 10 lines · Lincoln Dale
Quoted 8 lines · Jesper Juhl

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.

Quoted 8 lines

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 <[email protected]>

#7 lore raw

Re: Incremental update of TCP Checksum

In reply to Vishwas Raman

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) ));
}
Quoted 73 lines · Vishwas Raman
Quoted 17 lines · [email protected] wrote:
Quoted 2 lines · Vishwas Raman

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)

Quoted 7 lines

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,

(quoted diff) +0 -2
-Vishwas.
 
 
 
 
 
 
-

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 1 line
Raf D'Halleweyn <[email protected]>
#8 lore raw

Re: Incremental update of TCP Checksum

Quoted 1 line · On Tue, 16 Sep 2003 23:28:26 -0400 "Raf D'Halleweyn" <[email protected]> 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.

#9 lore raw

Re: Incremental update of TCP Checksum

In reply to Raf D'Halleweyn
Quoted 31 lines · 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) ));
}
Quoted 64 lines
Quoted 63 lines · Vishwas Raman
Quoted 18 lines · [email protected] wrote:
Quoted 2 lines · Vishwas Raman

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)

Quoted 7 lines

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.

#10 lore raw

Re: Incremental update of TCP Checksum

Quoted 4 lines · Richard B. Johnson

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