linux-kernel - Re: A divide by zero bug in lib/math/rational.c (with triggering input)

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] [day] [month] [year] [list]

Date:   Sun, 23 May 2021 20:20:00 -0700
From:   Trent Piepho <tpiepho@...il.com>
To:     Oskar Schirmer <oskar@...ra.com>
Cc:     Andy Shevchenko <andy.shevchenko@...il.com>,
        Daniel Latypov <dlatypov@...gle.com>,
        Yiyuan guo <yguoaz@...il.com>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "andy@...nel.org" <andy@...nel.org>,
        "akpm@...ux-foundation.org" <akpm@...ux-foundation.org>
Subject: Re: A divide by zero bug in lib/math/rational.c (with triggering input)

On Sat, May 22, 2021 at 12:08 PM Oskar Schirmer <oskar@...ra.com> wrote:
> On Fri, May 21, 2021 at 12:53:27 +0300, Andy Shevchenko wrote:
> > On Fri, May 21, 2021 at 12:20 PM Trent Piepho <tpiepho@...il.com> wrote:
> > > On Fri, May 21, 2021 at 12:55 AM Yiyuan guo <yguoaz@...il.com> wrote:
>
> Sorry, it does not. E.g. with the given fraction of 31/1000
> and the registers restricted to 8 and 5 bits respectively, the
> proposed fixed function would still divide by zero, because
> n1 == 0. If it was for the division by d1, the test for !d1

Yes, values less than 1 less than the smallest allowed non-zero value
will divide by zero will finish on the 2nd iteration, with n1 == 0,
and divide by zero.

The finished patch I've since sent fixes this.

> Moreover, for a fraction of 33/1000, both the original and
> the latest version would produce 1/30, which is off by some
> 1.01%, but the proposed fixed version would result in 1/31,
> which is worse: 2.24% off.

Finished patch correctly produces 1/30 in this case.

> I think the original function was not so bad. And the code it
> produced was much shorter than the latest version, although
> this might not be an argument in times, where a simple OS
> kernel is beyond the 40MB.

I measured this.  I've compared the original, which did not consider
semi-convergents nor out of range values, the current version, which
does semi-convergents but fails on out of range, and the patched
version, which handles that too.

Size in bytes:
X64 149 205 278
ARM 164 220 300

So 129 bytes on x64 and 136 bytes on ARM.  Not all that much.  I
didn't try writing a special check for large/small inputs in the older
code to see how large that was, for a more like-to-like comparison to
my latest patch.