linux-kernel - Re: [PATCH v2] lib: gcd: prevent possible div by 0

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]

Message-ID: <1347481832.3384.12.camel@offbook>
Date:	Wed, 12 Sep 2012 22:30:32 +0200
From:	Davidlohr Bueso <dave@....org>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	Eric Dumazet <eric.dumazet@...il.com>,
	lkml <linux-kernel@...r.kernel.org>, stable@...r.kernel.org
Subject: Re: [PATCH v2] lib: gcd: prevent possible div by 0

On Wed, 2012-09-12 at 12:36 -0700, Andrew Morton wrote:
> On Wed, 12 Sep 2012 21:20:30 +0200
> Davidlohr Bueso <dave@....org> wrote:
> 
> > On Wed, 2012-09-12 at 12:10 -0700, Andrew Morton wrote:
> > > On Mon, 10 Sep 2012 16:35:19 +0200
> > > Davidlohr Bueso <dave@....org> wrote:
> > > 
> > > > Account for all properties when a and/or b are 0:
> > > > gcd(0, 0) = 0
> > > > gcd(a, 0) = a
> > > > gcd(0, b) = b
> > > > 
> > > > Cc: stable@...r.kernel.org
> > > 
> > > Why cc:stable?  If this patch fixes some known problem in the current
> > > kernel then that really really should have been described in the
> > > changelog.  Always.  Please.
> > 
> > Ok, I will keep it in mind next time. No known problem (at least that I
> > know of), but due to the nature of the potential bug, I thought that it
> > was worth adding it to stable.
> 
> OK.
> 
> I'm not personally averse to fixing such problems in -stable,
> particualrly in lib/ code.  After all, people who take -stable kernels
> will then change them and add drivers and backport changes from later
> kernels, etc.  They might be bitten by such a bug.

Yes, my thoughts exactly.
> 
> 
> I'm scratching my head a bit at the patch though.  What does gcd(0, 13)
> mean?  That 0 can be divided by 13 zero times, which is an integer
> result?  I wonder why any non-buggy code would do that....
> 

While I've been away from this kind of math for a while, based on the
Euclid's algorithm, if r = a mod b, then gcd(a, b) = gcd(b, r), so:

gcd(0, 13) = gcd(13, 0 mod 13) = gcd(13, 0)

Since the GCD  of a and b is "the largest integer that divides both a
and b with no remainder", when r = 0, the algorithm will stop and
therefore gcd(13, 0) = 13.

http://mitpress.mit.edu/sicp/full-text/sicp/book/node19.html

--
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/