Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
| Since the old definition is not used in the way before(x, y) !before(y, x), but rather in the | fashion before(x, y) or after(y, x), the main advantage of the new definition is that it makes | this type of use a safe case. | | This is not true because | | if (before(x, y)) | goto drop; | | means that you're effectively using it as !before(x, y). In other words, | the change is good if our code read | | if (before(x, y)) | process_packet(); | That is correct - whether it is indeed safe(r) to use needs to be evaluated in the individual context. - To unsubscribe from this list: send the line unsubscribe netdev in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
| The key point where the new definition differs from the old is that _the relation_ | before(x,y) is unambiguous: the case before(x,y) before(y,x) will no longer occur. | | This is highly dependent on how the before macro is used in actual code. | There is nothing to suggest that this change won't create new security | holes in DCCP or any other protocol that uses this macro. The only | way to be sure is to audit every single use. I fully agree, merely changing the definition means going only half way. | So I think we need to do one of two things: | | 1) Audit every single before/after check to ensure that it works | correctly with the new definition. For DCCP I will perform such an audit and post the results to [EMAIL PROTECTED] With regard to TCP: I am heavily snowed under with other work at the moment. If there are experienced TCP people on the list who would be happy to look at this, it would be great. I counted the number of times before() is used - it amounted to 68. There are of course obvious cases which are quick to dismiss, but in particular the example you presented yesterday points out that careful analysis is needed. I asked Dave to revert to the old TCP definition (patch has been committed); for the moment this seems the safest thing to do. | 2) Change before/after such that before(x, x+2^31) == !before(x+2^31, x). This is what the new definition does: in the old definition we always have that before(x, x+2^31) == before(x+2^31, x). - To unsubscribe from this list: send the line unsubscribe netdev in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
On Fri, Jan 05, 2007 at 11:51:16AM +, Gerrit Renker wrote:
| 2) Change before/after such that before(x, x+2^31) == !before(x+2^31, x).
This is what the new definition does: in the old definition we always have
that
before(x, x+2^31) == before(x+2^31, x).
Sorry but the new definition has exactly the same problem since
before(x, x+2^31) == before(x+2^31, x) == 0
While the old definition had
before(x, x+2^31) == before(x+2^31, x) == 1
Both are equally bad. It's only unambiguous if
before(x, x+2^31) == !before(x+2^31, x) == 0
or
before(x, x+2^31) == !before(x+2^31, x) == 1
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmVHI~} [EMAIL PROTECTED]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line unsubscribe netdev in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
Quoting Herbert Xu: | On Fri, Jan 05, 2007 at 11:51:16AM +, Gerrit Renker wrote: | | | 2) Change before/after such that before(x, x+2^31) == !before(x+2^31, x). | This is what the new definition does: in the old definition we always have that | before(x, x+2^31) == before(x+2^31, x). | | Sorry but the new definition has exactly the same problem since | | before(x, x+2^31) == before(x+2^31, x) == 0 You are right. Sorry, I misread the text. Please see below. | While the old definition had | | before(x, x+2^31) == before(x+2^31, x) == 1 | | Both are equally bad. It's only unambiguous if | | before(x, x+2^31) == !before(x+2^31, x) == 0 | | or | | before(x, x+2^31) == !before(x+2^31, x) == 1 Implementing such a solution is a challenge - RFC 1982 suggests here (sec. 3.2): Thus the problem case is left undefined, implementations are free to return either result, or to flag an error, and users must take care not to depend on any particular outcome. I think that a definition which satisfies before(x, x+2^31) != !before(x+2^31, x) will be more complex to implement and will need more instructions. To illustrate with an example, if we assume that `before' operates on minutes and uses modulo-60 arithmetic, the above requirement becomes before60(x, x+30) != before(x+30, x) On a clock, one cannot tell this when we merely look at the minute hands: half before xx o'clock is the same as xx o'clock before half. Only if we also take the hour hand into consideration, the statement half before 2:00 o'clock becomes unambiguous (although one would rather say half past 1:00 o'clock :-). With regard to 31-bit sequence numbers, this would mean that we need additional information to enforce before(x, x+2^31) != before(x+2^31, x) Taking the clock example further, it could be disambiguated by using 33 bits, but then the same problem crops up with regard to modulo-2^33 arithmetic: how to disambiguate the case for x and x+2^32. Please let me restate the differences between the old and new definition: 1) Old definition has the following list of exclusive-or cases * x == y- identity * before(x, y) !before(y, x) - x `before' y and y != (x + 2^31) % 2^32 * before(y, x) !before(x, y) - y `before' x and y != (x + 2^31) % 2^32 * before(x, y) before(y, x) - y == (x + 2^31) % 2^32 2) New definition has the following list of exclusive-or cases * x == y- identity * before(x, y) - x `before' y and y != (x + 2^31) % 2^32 * before(y, x) - y `before' x and y != (x + 2^31) % 2^32 * !before(x, y) !before(y, x)- y == (x + 2^31) % 2^32 Since the old definition is not used in the way before(x, y) !before(y, x), but rather in the fashion before(x, y) or after(y, x), the main advantage of the new definition is that it makes this type of use a safe case. My view is that this is as good as one can get; if you have a suggestion of how one could also disambiguate before(x, x+2^31) != before(x+2^31, x), can you please let me know. Gerrit - To unsubscribe from this list: send the line unsubscribe netdev in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
| With the implementation now, the output of before(x,y) is reliable: it returns true | if (and only if) x is indeed `before' y. | | Sorry but I don't think you've answered my question. | | Let y = (x + 2^31) % 2^32, how is making | | before(x, y) == before(y, x) == 0 | | any better than | | before(x, y) == before(y, x) == 1 | | For an unambiguous before, we must have before(x, y) != before(y, x) | if x != y. I now see where you are coming from. This requirement * is fulfilled in both definitions as long as y != (x + 2^31) % 2^32 * does not hold in both definitions when y == (x + 2^31) % 2^32 The reason is in the underlying principle: due to sequence number wrapping, we are dealing with circular arithmetic, and in circular arithmetic the mid of the range is ambiguous (example: clock minute hands - 30 is as much `after' as it is `before'). This problematic case has been discussed before: RFC 1982 provides some background, and we had quite some discussion about similar issues (48 bit sequence numbers) on [EMAIL PROTECTED] So the short answer is - this kind of unambiguous `before' can not be implemented (see in particular also the notes in sec. 3.2 of RFC 1982). The key point where the new definition differs from the old is that _the relation_ before(x,y) is unambiguous: the case before(x,y) before(y,x) will no longer occur. | For a more concrete example, look at the code in tcp_ack: | | /* If the ack is newer than sent or older than previous acks | * then we can probably ignore it. | */ | if (after(ack, tp-snd_nxt)) | goto uninteresting_ack; | | if (before(ack, prior_snd_una)) | goto old_ack; | | Here we have two checks that weed out cases that we do not wish to | process. When all data have been acknowledged, we have | | snd_nxt == snd_una | | At this point, we only want the value of ack == snd_nxt == snd_una | to pass this check. With your change, the value snd_nxt + 2^31 can | also pass this check, which may have security implications. This is true: with the old definition it is at this point certain that ack == snd_nxt. The reason is that the code implicitly relies on the way `before' is defined. That has been the reason why this has been sent as an `RFC' patch: I am sure that the new definition is is in itself better, but was not sure how it would work with the existing code. With DCCP the case is different: it is a new protocol and an unambiguous `before' relation is beneficial, since this can increase the accuracy of detecting loss. Since there is likely more code which implicitly relies on the old definition, I will send a patch shortly. Many thanks, Gerrit - To unsubscribe from this list: send the line unsubscribe netdev in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
On Thu, Jan 04, 2007 at 12:49:02PM +, Gerrit Renker wrote:
The key point where the new definition differs from the old is that _the
relation_
before(x,y) is unambiguous: the case before(x,y) before(y,x) will no
longer occur.
This is highly dependent on how the before macro is used in actual code.
There is nothing to suggest that this change won't create new security
holes in DCCP or any other protocol that uses this macro. The only
way to be sure is to audit every single use.
So I think we need to do one of two things:
1) Audit every single before/after check to ensure that it works
correctly with the new definition.
2) Change before/after such that before(x, x+2^31) == !before(x+2^31, x).
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmVHI~} [EMAIL PROTECTED]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line unsubscribe netdev in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
Hi Herbert,
| While looking at DCCP sequence numbers, I stumbled over a problem with
| the following definition of before in tcp.h:
|
| static inline int before(__u32 seq1, __u32 seq2)
| {
| return (__s32)(seq1-seq2) 0;
| }
|
| Problem: This definition suffers from an an ambiguity, i.e. always
|
| before(a, (a + 2^31) % 2^32)) = 1
| before((a + 2^31) % 2^32), a) = 1
|
|In text: when the difference between a and b amounts to 2^31,
|a is always considered `before' b, the function can not decide.
|The reason is that implicitly 0 is `before' 1 ... 2^31-1 ... 2^31
|
| Solution: There is a simple fix, by defining before in such a way that
| 0 is no longer `before' 2^31, i.e. 0 `before' 1 ... 2^31-1
| By not using the middle between 0 and 2^32, before can be made
| unambiguous.
| This is achieved by testing whether seq2-seq1 0 (using signed
| 32-bit arithmetic).
|
| Sorry, I still don't get the point of this change.
|
| Prior to the patch, we have values x and y such that both
| before(x, y) and before(y, x) are true. Now for those same
| values both before(x, y) and before(y, x) are false.
|
| It's still as ambiguous as ever. Surely to resolve the
| ambiguity we want to make before(x, y) = !before(y, x), no?
Please let me restate:
Ambiguity here means that for those numbers x,y such that (x + 2^31) % 2^32)
= y
before(x, y) = 1 and before(y, x) = 1. With the previous implementation, one
could
not tell the difference here: and there are 2^32 such cases where this occurs.
With the implementation now, the output of before(x,y) is reliable: it returns
true
if (and only if) x is indeed `before' y.
If before(x,y) is false then there are now two possibilities:
(a) before(y, x) is true and y != (x + 2^31) % 2^32
(b) before(y, x) is false and y == (x + 2^31) % 2^32
This means that the cases can be clearly separated out, which was not possible
before.
To summarize the differences:
-
1) Possible cases in the old implementation (exclusive-or list):
* x == y- identity
* before(x, y) !before(y, x) - x is `before' y
* before(y, x) !before(x, y) - y is `before' x
* before(x, y) before(y, x) - y == (x + 2^31) % 2^32
2) Possible cases in the new implementation (exclusive-or list):
* x == y- identity
* before(x, y) - x is `before' x
* before(y, x) - y is `before x
* !before(x, y) !before(y, x)- y == (x + 2^31) % 2^32
As can be seen (2) requires fewer test cases while (1) would need extra checks
to disambiguate
before(x, y) from the case before(x,y) before(y,x).
I do believe that this is useful, since now speeds of 10 Gigabits are in use,
which means that
sequence numbers wrap around faster; and also with regard to the issue of
selecting an initial
sequence number; and protection against sequence number attacks.
A related discussion is in RFC 1982, but with regard to the case y == (x +
2^31) % 2^32 it
recommends to leave this `undefined' -- the new solution is in agreement with
this, and is
even less complicated to implement.
Gerrit
-
To unsubscribe from this list: send the line unsubscribe netdev in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
Gerrit Renker [EMAIL PROTECTED] wrote:
| Prior to the patch, we have values x and y such that both
| before(x, y) and before(y, x) are true. Now for those same
| values both before(x, y) and before(y, x) are false.
|
| It's still as ambiguous as ever. Surely to resolve the
| ambiguity we want to make before(x, y) = !before(y, x), no?
Please let me restate:
Ambiguity here means that for those numbers x,y such that (x + 2^31) % 2^32)
= y
before(x, y) = 1 and before(y, x) = 1. With the previous implementation, one
could
not tell the difference here: and there are 2^32 such cases where this occurs.
With the implementation now, the output of before(x,y) is reliable: it
returns true
if (and only if) x is indeed `before' y.
Sorry but I don't think you've answered my question.
Let y = (x + 2^31) % 2^32, how is making
before(x, y) == before(y, x) == 0
any better than
before(x, y) == before(y, x) == 1
For an unambiguous before, we must have before(x, y) != before(y, x)
if x != y.
For a more concrete example, look at the code in tcp_ack:
/* If the ack is newer than sent or older than previous acks
* then we can probably ignore it.
*/
if (after(ack, tp-snd_nxt))
goto uninteresting_ack;
if (before(ack, prior_snd_una))
goto old_ack;
Here we have two checks that weed out cases that we do not wish to
process. When all data have been acknowledged, we have
snd_nxt == snd_una
At this point, we only want the value of ack == snd_nxt == snd_una
to pass this check. With your change, the value snd_nxt + 2^31 can
also pass this check, which may have security implications.
Granted I have not looked at other checks in the TCP path that may
prevent this code from being invoked in that case. However, this
does illustrate the need to audit every single before/after check
if they were ambiguous.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmVHI~} [EMAIL PROTECTED]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line unsubscribe netdev in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
Hi David, many thanks for taking the matter seriously and investigating it further. | I went over this patch and analysis a dozen times, because I | couldn't believe something like this has been broken for | so long :-) It gave me some grief too, when I looked at DCCP sequence numbers %-) RFC 1982 provides some definitions, but leaves the case a = (b + 2^31) % 2^32 open to the implementation (suggests `undefined'). I think the new definition is more conformant with RFC 1982 than the old one, since the ambiguity is now removed with regard to a = (b + 2^31) % 32, and it is not unnecessarily burdensome to implement (section 3.2 of RFC 1982). | Even BSD suffers of this issue, since the beginning. See | SEQ_LT() in tcp_seq.h, and it seems that BSD's timestamp | sequence checking has the issue too (see TSTMP_LT() macro | in OpenBSD's tcp_input.c) I didn't know about OpenBSD, but in Stevens vol 2 (sec. 24.7) it is already defined in this way. Best regards merry Christmas Gerrit - To unsubscribe from this list: send the line unsubscribe netdev in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
David Miller [EMAIL PROTECTED] wrote:
From: Gerrit Renker [EMAIL PROTECTED]
Date: Thu, 14 Dec 2006 15:07:06 +
While looking at DCCP sequence numbers, I stumbled over a problem with
the following definition of before in tcp.h:
static inline int before(__u32 seq1, __u32 seq2)
{
return (__s32)(seq1-seq2) 0;
}
Problem: This definition suffers from an an ambiguity, i.e. always
before(a, (a + 2^31) % 2^32)) = 1
before((a + 2^31) % 2^32), a) = 1
In text: when the difference between a and b amounts to 2^31,
a is always considered `before' b, the function can not decide.
The reason is that implicitly 0 is `before' 1 ... 2^31-1 ... 2^31
Solution: There is a simple fix, by defining before in such a way that
0 is no longer `before' 2^31, i.e. 0 `before' 1 ... 2^31-1
By not using the middle between 0 and 2^32, before can be made
unambiguous.
This is achieved by testing whether seq2-seq1 0 (using signed
32-bit arithmetic).
I attach a patch to codify this. Also the `after' relation is basically
a redefinition of `before', it is now defined as a macro after before.
Signed-off-by: Gerrit Renker [EMAIL PROTECTED]
Applied, thanks Gerrit.
I went over this patch and analysis a dozen times, because I
couldn't believe something like this has been broken for
so long :-)
Sorry, I still don't get the point of this change.
Prior to the patch, we have values x and y such that both
before(x, y) and before(y, x) are true. Now for those same
values both before(x, y) and before(y, x) are false.
It's still as ambiguous as ever. Surely to resolve the
ambiguity we want to make before(x, y) = !before(y, x), no?
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmVHI~} [EMAIL PROTECTED]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line unsubscribe netdev in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
From: Gerrit Renker [EMAIL PROTECTED]
Date: Thu, 14 Dec 2006 15:07:06 +
While looking at DCCP sequence numbers, I stumbled over a problem with
the following definition of before in tcp.h:
static inline int before(__u32 seq1, __u32 seq2)
{
return (__s32)(seq1-seq2) 0;
}
Problem: This definition suffers from an an ambiguity, i.e. always
before(a, (a + 2^31) % 2^32)) = 1
before((a + 2^31) % 2^32), a) = 1
In text: when the difference between a and b amounts to 2^31,
a is always considered `before' b, the function can not decide.
The reason is that implicitly 0 is `before' 1 ... 2^31-1 ... 2^31
Solution: There is a simple fix, by defining before in such a way that
0 is no longer `before' 2^31, i.e. 0 `before' 1 ... 2^31-1
By not using the middle between 0 and 2^32, before can be made
unambiguous.
This is achieved by testing whether seq2-seq1 0 (using signed
32-bit arithmetic).
I attach a patch to codify this. Also the `after' relation is basically
a redefinition of `before', it is now defined as a macro after before.
Signed-off-by: Gerrit Renker [EMAIL PROTECTED]
Applied, thanks Gerrit.
I went over this patch and analysis a dozen times, because I
couldn't believe something like this has been broken for
so long :-)
Even BSD suffers of this issue, since the beginning. See
SEQ_LT() in tcp_seq.h, and it seems that BSD's timestamp
sequence checking has the issue too (see TSTMP_LT() macro
in OpenBSD's tcp_input.c)
It seems that our PAWS timestamp checks are ok because we do:
(s32)(tp-rx_opt.ts_recent - tp-rx_opt.rcv_tsval) TCP_PAWS_WINDOW
and
(s32)(tp-rx_opt.rcv_tsval - tp-rx_opt.ts_recent) = 0
Thanks again Gerrit.
-
To unsubscribe from this list: send the line unsubscribe netdev in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation
On Thu, Dec 14, 2006 at 03:07:06PM +, Gerrit Renker wrote:
diff --git a/include/net/tcp.h b/include/net/tcp.h
index c99774f..b7d8317 100644
--- a/include/net/tcp.h
+++ b/include/net/tcp.h
@@ -242,14 +242,9 @@ extern int tcp_memory_pressure;
static inline int before(__u32 seq1, __u32 seq2)
{
-return (__s32)(seq1-seq2) 0;
+return (__s32)(seq2-seq1) 0;
}
-
-static inline int after(__u32 seq1, __u32 seq2)
-{
- return (__s32)(seq2-seq1) 0;
-}
-
+#define after(seq2, seq1)before(seq1, seq2)
Btw, these macfox/inlines are named quite a bit too generic for
something that is in tcp.h
-
To unsubscribe from this list: send the line unsubscribe netdev in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
