netdev - Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 4 Jan 2007 12:49:02 +0000
From:	Gerrit Renker <gerrit@....abdn.ac.uk>
To:	Herbert Xu <herbert@...dor.apana.org.au>
Cc:	herbert@...dor.apana.org.au, davem@...emloft.net,
	netdev@...r.kernel.org
Subject: 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 dccp@...r.

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 majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html