Netfiltering - NF_IP_LOCAL_OUT - how it works???
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.
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_OUThook for the outgoing packet and changeskb->dst->outputtomy_ip_output()instead ofip_output()in that hook function. After loading the module, I see control being transferred tomy_ip_output()for all outgoing packets which in turn callsip_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()inip_output.cwhere 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
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_OUThook for the outgoing packet and changeskb->dst->outputtomy_ip_output()instead ofip_output()in that hook function. After loading the module, I see control being transferred tomy_ip_output()for all outgoing packets which in turn callsip_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()inip_output.cwhere it is trying to callNF_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->outputfunction 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/
Incremental update of TCP Checksum
In reply to Harald WelteHi 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
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
Re: Incremental update of TCP Checksum
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.
Re: Incremental update of TCP Checksum
Quoted 12 lines · Vishwas Raman
As mentioned in RFC1624, I did the following.
voidchangePacket(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
Re: Incremental update of TCP Checksum
In reply to Vishwas RamanThis 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.txtAs mentioned in RFC1624, I did the following.
voidchangePacket(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]>
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.
Re: Incremental update of TCP Checksum
In reply to Raf D'HalleweynQuoted 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
__u16incr_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
__u16incr_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.txtAs mentioned in RFC1624, I did the following.
voidchangePacket(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
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
Re: Incremental update of TCP Checksum
In reply to Vishwas RamanQuoted 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.
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 be0xffff.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/
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 be0xffff.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.
Re: Incremental update of TCP Checksum
In reply to Vishwas RamanQuoted 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 be0xffff.
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]>
Re: Incremental update of TCP Checksum
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.
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)0x22to0x11then you can 'back out' the0x22and recalculate the checksum with0x11.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]>
Re: Incremental update of TCP Checksum
In reply to Vishwas RamanQuoted 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 be0xffff.
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
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 be0xffff.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,
0x0000is 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 get0xffff.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...
Re: Incremental update of TCP Checksum
In reply to Vishwas RamanQuoted 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