lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 PHC  
Open Source and information security mailing list archives
 

Date: Wed, 3 Jan 2007 08:56:19 +0000 From: Gerrit Renker <gerrit@....abdn.ac.uk> To: Herbert Xu <herbert@...dor.apana.org.au> Cc: David Miller <davem@...emloft.net>, netdev@...r.kernel.org Subject: 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)(seq1seq2) < 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^311 ... 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^311  >> By not using the middle between 0 and 2^32, before can be made  >> unambiguous.  >> This is achieved by testing whether seq2seq1 > 0 (using signed  >> 32bit 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 (exclusiveor 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 (exclusiveor 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 majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomoinfo.html
Powered by blists  more mailing lists