linux-kernel - Re: [PATCH] kcmp: Fix standard comparison bug

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20140904132912.GL16395@moon>
Date:	Thu, 4 Sep 2014 17:29:12 +0400
From:	Cyrill Gorcunov <gorcunov@...il.com>
To:	Rasmus Villemoes <linux@...musvillemoes.dk>
Cc:	Andrew Morton <akpm@...ux-foundation.org.openvz.org>,
	"Eric W. Biederman" <ebiederm@...ssion.com>,
	linux-kernel@...r.kernel.org, stable@...r.kernel.org,
	"H. Peter Anvin" <hpa@...or.com>,
	Pavel Emelyanov <xemul@...allels.com>
Subject: Re: [PATCH] kcmp: Fix standard comparison bug

On Thu, Sep 04, 2014 at 12:40:06PM +0200, Rasmus Villemoes wrote:
> The C operator <= defines a perfectly fine total ordering on the set
> of values representable in a long. However, unlike its namesake in the
> integers, it is not translation invariant, meaning that we do not have
> "b <= c" iff "a+b <= a+c" for all a,b,c.
> 
> This means that it is always wrong to try to boil down the
> relationship between two longs to a question about the sign of their
> difference, because the resulting relation [a LEQ b iff a-b <= 0] is
> neither anti-symmetric or transitive. The former is due to
> -LONG_MIN==LONG_MIN (take any two a,b with a-b = LONG_MIN; then a LEQ
> b and b LEQ a, but a != b). The latter can either be seen observing
> that x LEQ x+1 for all x, implying x LEQ x+1 LEQ x+2 ... LEQ x-1 LEQ
> x; or more directly with the simple example a=LONG_MIN, b=0, c=1, for
> which a-b < 0, b-c < 0, but a-c > 0.
> 
> Note that it makes absolutely no difference that a transmogrying
> bijection has been applied before the comparison is done. In fact, had
> the obfuscation not been done, one could probably not observe the bug
> (assuming all values being compared always lie in one half of the
> address space, the mathematical value of a-b is always representable
> in a long). As it stands, one can easily obtain three file descriptors
> exhibiting the non-transitivity of kcmp().
> 
> Cc: <stable@...r.kernel.org>
> Signed-off-by: Rasmus Villemoes <linux@...musvillemoes.dk>

It's more than that, I looked into disassembly code and
found that compiler overoptimize obfuscation, instead of doing
^ and * sequently it substracts xor production of both operands
first and only then multiplies the result.

Lets stick with the fix.

Reviewed-by: Cyrill Gorcunov <gorcunov@...nvz.org>

I'll take more precise look at evening, thanks!
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/