gcry_mpi_invm succeeds if the inverse does not exist

[Jussi Kivilinna]

Hello,

Cryptofuzz is reporting another heap-buffer-overflow issue in
_gcry_mpi_invm. I've attached reproducer, original from Guido and
as patch applied to tests/basic.c.

Here's AddressSanitizer output from tests/basic with reproducer,
compiled with CFLAGS="-fsanitize=address -O0 -g":

$ tests/basic
=================================================================
==1665037==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000000388 at pc 0x7f36999058d0 bp 0x7ffdef3a5160 sp 0x7ffdef3a5150
READ of size 8 at 0x603000000388 thread T0
    #0 0x7f36999058cf in _gcry_mpi_invm ../../mpi/mpi-inv.c:530
    #1 0x7f369970a270 in gcry_mpi_invm ../../src/visibility.c:472
    #2 0x5608cc442631 in test_cryptofuzz ../../tests/basic.c:13901
    #3 0x5608cc442ffb in main ../../tests/basic.c:14019
    #4 0x7f36994d80b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #5 0x5608cc411f4d in _start (/home/jussi/kernel/libgcrypt/build-amd64-ubsan/tests/basic+0x5bf4d)

0x603000000388 is located 0 bytes to the right of 24-byte region [0x603000000370,0x603000000388)
allocated by thread T0 here:
    #0 0x7f3699ad0bc8 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #1 0x7f36997253ab in _gcry_private_malloc ../../src/stdmem.c:113
    #2 0x7f36997137af in do_malloc ../../src/global.c:920
    #3 0x7f369971395e in _gcry_malloc ../../src/global.c:942
    #4 0x7f3699714007 in _gcry_xmalloc ../../src/global.c:1116
    #5 0x7f36999142f0 in _gcry_mpi_alloc_limb_space ../../mpi/mpiutil.c:138
    #6 0x7f36999057f2 in _gcry_mpi_invm ../../mpi/mpi-inv.c:523
    #7 0x7f369970a270 in gcry_mpi_invm ../../src/visibility.c:472
    #8 0x5608cc442631 in test_cryptofuzz ../../tests/basic.c:13901
    #9 0x5608cc442ffb in main ../../tests/basic.c:14019
    #10 0x7f36994d80b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)

SUMMARY: AddressSanitizer: heap-buffer-overflow ../../mpi/mpi-inv.c:530 in _gcry_mpi_invm
Shadow bytes around the buggy address:
  0x0c067fff8020: 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00 00 fa
  0x0c067fff8030: fa fa 00 00 00 fa fa fa fd fd fd fa fa fa fd fd
  0x0c067fff8040: fd fa fa fa fd fd fd fa fa fa fd fd fd fa fa fa
  0x0c067fff8050: 00 00 00 fa fa fa fd fd fd fa fa fa fd fd fd fa
  0x0c067fff8060: fa fa fd fd fd fa fa fa 00 00 00 fa fa fa 00 00
=>0x0c067fff8070: 00[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff80a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff80b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff80c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==1665037==ABORTING


I applied following change and that appears to avoid the heap-overflow, but
I'm not sure if this is correct fix:

diff --git a/mpi/mpi-inv.c b/mpi/mpi-inv.c
index 3ff5947a..a53a195a 100644
--- a/mpi/mpi-inv.c
+++ b/mpi/mpi-inv.c
@@ -526,7 +526,8 @@ _gcry_mpi_invm (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
       else
        _gcry_mpih_sub_n (diffp, x1p, x2p, x1size);
       _gcry_mpi_free_limb_space (x1p, x1size);
-      for (i = k % BITS_PER_MPI_LIMB; i < BITS_PER_MPI_LIMB; i++)
+      for (i = k % BITS_PER_MPI_LIMB;
+          i < BITS_PER_MPI_LIMB && k / BITS_PER_MPI_LIMB < x1size; i++)
        diffp[k/BITS_PER_MPI_LIMB] &= ~(((mpi_limb_t)1) << i);
 
       hsize = x1size * 2;



-Jussi

On 13.5.2020 9.44, Niibe Yutaka wrote:
> Guido Vranken via Gcrypt-devel wrote:
>> Here is a reproducer for the bugs. OOB reads and writes on i386:
> 
> Thanks.  It was me who embugged.  It was just fixed by the commit:
> 
> 	69b55f87053ce2494cd4b38dc600f867bc4355be
> 
> By the way, the problem in your original report was also fixed.
> Now, it should return correct value (if inverse exists or not).
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: poc_22305.c
Type: text/x-csrc
Size: 663 bytes
Desc: not available
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20200529/0f9c2483/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-cryptofuzz-reproducer-tests-basic.c.patch
Type: text/x-patch
Size: 1640 bytes
Desc: not available
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20200529/0f9c2483/attachment.bin>