full-disclosure - [FD] AMD's buddies for Intel's FDIV bug: _llrem and _ullrem yield wrong remainders!

Open Source and information security mailing list archives

Date: Thu, 30 Nov 2017 20:23:59 +0100
From: "Stefan Kanthak" <stefan.kanthak@...go.de>
To: <bugtraq@...urityfocus.com>
Cc: fulldisclosure@...lists.org
Subject: [FD] AMD's buddies for Intel's FDIV bug: _llrem and _ullrem yield
	wrong remainders!

Hi @ll,

at least after Intel's infamous FDIV bug, everybody who uses (or
programs) computers should know that (floating point) division is
hard to implement right.-)

But what about integer division and integer modulus/remainder?

Starting at least in 1999, and at least until 2011, AMD, Intel's
competitor on the market for x86 and x64 processors, published in
their "AMD Athlon Processor x86 Code Optimization Guide" and their
"Software Optimization Guide for AMD64 Processors" under the title
"Efficient 64-Bit Integer Arithmetic in 32-Bit Mode" routines for
I386 compatible processors: _lldiv, _ulldiv, _ullrem and _llrem

The routines _llrem and _ullrem have a bug and yield wrong remainders!

See for example <https://support.amd.com/TechDocs/25112.PDF> and
<http://support.amd.com/techdocs/40546.pdf> on AMD's website.

    _llrem PROC
    ...
       sbb  eax, eax             ; remainder < 0 ? 0xffffffff : 0
       and  edx, eax             ; remainder < 0 ? divisor_hi : 0
       and  eax, [esp+4]         ; remainder < 0 ? divisor_lo : 0
       add  eax, ebx             ; remainder_lo
-      add  edx, ecx             ; remainder_hi
+      adc  edx, ecx             ; remainder_hi
       add  esp, 16              ; Remove local variables.
    sr_makesign:

    _ullrem PROC
    ...
       sbb  edx, edx             ; (remainder < 0) ? 0xFFFFFFFF : 0
       and  eax, edx             ; (remainder < 0) ? divisor_lo : 0
       and  edx, [esp+24]        ; (remainder < 0) ? divisor_hi : 0
       add  eax, ebx             ; remainder += (remainder < 0) ? divisor : 0
+      adc  edx, ecx
       pop  edi                  ; Restore EDI as per calling convention.
       pop  ebx                  ; Restore EBX as per calling convention.
       ret  16                   ; Done, return to caller.
    _ullrem ENDP

Older revisions of AMD's guides, available for example from
<https://cr.yp.to/bib/2004/-amd-25112.pdf> or
<http://www.ii.uib.no/~osvik/amd_opt/25112.pdf>, show these bugs too!

Prior versions of this guide, available for example from
<http://www.ii.uib.no/~osvik/amd_opt/22007k.pdf> or
<https://en.wikichip.org/w/images/5/5f/AMD_Athlon_Processor_x86_Code_Optimization_Guide.pdf>,
show this bug only in the _llrem routine!

stay tuned
Stefan Kanthak

_______________________________________________
Sent through the Full Disclosure mailing list
https://nmap.org/mailman/listinfo/fulldisclosure
Web Archives & RSS: http://seclists.org/fulldisclosure/

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