lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [day] [month] [year] [list]
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/

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux - Powered by OpenVZ