Heap overflow during hts_md5_update

[OctavioGalland]

Summary

Heap-buffer overflow in hts_md5_update during parsing of a crafted SAM/FASTA file pair.

Environment

Built using LLVM 14 with ASAN on Ubuntu 22.04

How to reproduce

Build with ASAN on latest commit like so:

git clone --recursive https://github.com/samtools/htslib
cd htslib
autoreconf -i
CC=clang-14 CXX=clang++-14 CFLAGS="-fsanitize=address -g" CXXFLAGS="-fsanitize=address -g" LDFLAGS="-fsanitize=address -g" ./configure
make -j$(nproc)

git clone --recursive https://github.com/samtools/samtools
cd samtools
autoheader
autoconf -Wno-syntax
CC=clang-14 CXX=clang++-14 CFLAGS="-fsanitize=address -g -I$(pwd)/../htslib" CXXFLAGS="-fsanitize=address -g -I$(pwd)/../htslib" LDFLAGS="-fsanitize=address -g -L$(pwd)/../htslib" ./configure
make -j$(nproc)

Within the samtools folder, get poc file and reproduce with:

echo -ne "QFNRCVNOOmMxCUxOOgPoCnMwCTAJYzEJOAkwCTEwTTA2MDcwMDBEMDAwMEQJHgkwCTAJQUNDRyIi
IiIiIgkq" | base64 -d > poc
./samtools view -C -T ../htslib/test/c2.fa poc

Which on my setup outputs:

[W::cram_get_ref] Reference file given, but ref 'c1' not present
[W::cram_get_ref] Failed to populate reference for id 0
[W::cram_write_SAM_hdr] No M5 tags present and could not find reference
[W::cram_write_SAM_hdr] Enabling embed_ref=2 option
[W::cram_write_SAM_hdr] NOTE: the CRAM file will be bigger than using an external reference
CRAM-�\��vvr@SQ	SN:c1	LN:�
@PG	ID:samtools	PN:samtools	VN:1.18-21-g528e1b2	CL:./samtools view -C -T ../htslib/test/c2.fa poc
s�|�??}�Y�[W::sam_parse1] unrecognized mate reference name "\x1E"; treated as unmapped
=================================================================
==11718==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x619000001d77 at pc 0x559c568c2c97 bp 0x7ffed1881c40 sp 0x7ffed1881410
READ of size 56 at 0x619000001d77 thread T0
    #0 0x559c568c2c96 in __asan_memcpy (/home/octavio/samtools/samtools+0x132c96) (BuildId: 7078ea94d4e08689f85e1df47e2d609c021d2440)
    #1 0x559c56bd63e9 in hts_md5_update /home/octavio/htslib/md5.c:268:2
    #2 0x559c56c94cbd in cram_encode_container /home/octavio/htslib/cram/cram_encode.c:2041:17
    #3 0x559c56d0496c in cram_flush_container /home/octavio/htslib/cram/cram_io.c:4128:14
    #4 0x559c56d05795 in cram_flush_container_mt /home/octavio/htslib/cram/cram_io.c:4280:16
    #5 0x559c56d11132 in cram_close /home/octavio/htslib/cram/cram_io.c:5538:19
    #6 0x559c56b9e87f in hts_close /home/octavio/htslib/hts.c:1617:15
    #7 0x559c56b184fd in check_sam_close /home/octavio/samtools/sam_utils.c:78:13
    #8 0x559c5691d6f4 in main_samview /home/octavio/samtools/sam_view.c:1403:23
    #9 0x559c5699beed in main /home/octavio/samtools/bamtk.c:244:55
    #10 0x7f83ce629d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #11 0x7f83ce629e3f in __libc_start_main csu/../csu/libc-start.c:392:3
    #12 0x559c56840b24 in _start (/home/octavio/samtools/samtools+0xb0b24) (BuildId: 7078ea94d4e08689f85e1df47e2d609c021d2440)

0x619000001d77 is located 0 bytes to the right of 1015-byte region [0x619000001980,0x619000001d77)
allocated by thread T0 here:
    #0 0x559c568c3d96 in __interceptor_realloc (/home/octavio/samtools/samtools+0x133d96) (BuildId: 7078ea94d4e08689f85e1df47e2d609c021d2440)
    #1 0x559c56cb4071 in extend_ref /home/octavio/htslib/cram/cram_encode.c:1455:17
    #2 0x559c56c9def5 in cram_generate_reference /home/octavio/htslib/cram/cram_encode.c:1653:9
    #3 0x559c56c91ee5 in cram_encode_container /home/octavio/htslib/cram/cram_encode.c:1876:17
    #4 0x559c56d0496c in cram_flush_container /home/octavio/htslib/cram/cram_io.c:4128:14
    #5 0x559c56d05795 in cram_flush_container_mt /home/octavio/htslib/cram/cram_io.c:4280:16
    #6 0x559c56d11132 in cram_close /home/octavio/htslib/cram/cram_io.c:5538:19
    #7 0x559c56b9e87f in hts_close /home/octavio/htslib/hts.c:1617:15
    #8 0x559c56b184fd in check_sam_close /home/octavio/samtools/sam_utils.c:78:13
    #9 0x559c5691d6f4 in main_samview /home/octavio/samtools/sam_view.c:1403:23
    #10 0x559c5699beed in main /home/octavio/samtools/bamtk.c:244:55
    #11 0x7f83ce629d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16

SUMMARY: AddressSanitizer: heap-buffer-overflow (/home/octavio/samtools/samtools+0x132c96) (BuildId: 7078ea94d4e08689f85e1df47e2d609c021d2440) in __asan_memcpy
Shadow bytes around the buggy address:
  0x0c327fff8350: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c327fff8360: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c327fff8370: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c327fff8380: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c327fff8390: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c327fff83a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00[07]fa
  0x0c327fff83b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c327fff83c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c327fff83d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c327fff83e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c327fff83f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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
==11718==ABORTING

Maybe it's related to #1692 ? The backtrace looks a bit different though (6th function is cram_close instead of cram_flush).

[jkbonfield]

It appeared to be fixed by my fix for #1698. That wasn't actually a reuse-after-free bug, but a read buffer read overflow caused by an unmapped "alignment" starting a long way beyond the end of the specified reference. It happened to land within a block which had previously been freed.