bn_mod_barrt out-of-bounds write and hang

[guidovranken]

OOB write:

#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, tmp, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(tmp); bn_new(tmp);
    bn_null(R); bn_new(R);

    const char* s1 = "200000000000000000000000000000700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000190000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000040000000000000000000000000000000000900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000000000000200000000000000000000000000000000000000000000000000000000000055560000000000000000000000000000000000000000000000000000000000000000000000000000000000000000055550000000000000000000000000000000000000000000000000000000000016777215";
    const char* s2 = "84162174424236059512601364159788552895352108472911307036596759829688884035453236822177423188999761927736478583906391745885484086652739798560985904224480815756330586761129390491742720155379104504686856934612994047";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_pre_barrt(tmp, B);
    bn_mod_barrt(R, A, B, tmp);

    bn_free(A);
    bn_free(B);
    bn_free(tmp);
    bn_free(R);
    return 0;
}

Hang:

#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, tmp, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(tmp); bn_new(tmp);
    bn_null(R); bn_new(R);

    const char* s1 = "4294970310326202049000460015989909879453633060701562293387156796399194598269136941390448872924969452176199497282666242143360729695849607970912549583042220383240905462974333263420526777106027569342398349";
    const char* s2 = "720575940379060000";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_pre_barrt(tmp, B);
    bn_mod_barrt(R, A, B, tmp);

    bn_free(A);
    bn_free(B);
    bn_free(tmp);
    bn_free(R);
    return 0;
}

[dfaranha]

Thanks!

With 87cb595 the code now falls back to long division in case the input to Barrett reduction is too long.

[guidovranken]

Tested at 87cb595:

#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, tmp, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(tmp); bn_new(tmp);
    bn_null(R); bn_new(R);

    const char* s1 = "379220024083016978237080970674718990000000000000000000000000000000000000000000000000000000000000000000000000000000400001000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005555555000001000000000000000000000000000000000000000000000000000000000000000000000000000050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000072057594037927935000000000000000000000000000000000000000";
    const char* s2 = "6777215000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000032317006071311007300714876688678908931972014115229134636887179609218980194941195591504909210950881525864482831206308773673009960917501977503896521517960576383840675682767922186426197561618380943384761704705816458520363050428875758915410658086075523991239303859919143333899668342430855568497478556456949485617607598351150301582835151321971577101803084265674677361251231136292707753237390374856789689487223767233095444444444444444444444444444444445344444444444308944440488444444344534444444444444444444444444444444444444444551444";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_pre_barrt(tmp, B);
    bn_mod_barrt(R, A, B, tmp);

    bn_free(A);
    bn_free(B);
    bn_free(tmp);
    bn_free(R);
    return 0;
}

==27155==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x612000002b50 at pc 0x000000549502 bp 0x7ffee3697dd0 sp 0x7ffee3697dc8
WRITE of size 8 at 0x612000002b50 thread T0
    #0 0x549501 in bn_muld_low /mnt/2tb/cf-relic/relic/src/low/easy/relic_bn_mul_low.c:151:6
    #1 0x4cb2ac in bn_mod_barrt /mnt/2tb/cf-relic/relic/src/bn/relic_bn_mod.c
    #2 0x4c6391 in main /mnt/2tb/cf-relic/cryptofuzz/p.c:22:5
    #3 0x7ff6164ef0b2 in __libc_start_main /build/glibc-sMfBJT/glibc-2.31/csu/../csu/libc-start.c:308:16
    #4 0x41c2ed in _start (/mnt/2tb/cf-relic/cryptofuzz/a.out+0x41c2ed)

0x612000002b50 is located 0 bytes to the right of 272-byte region [0x612000002a40,0x612000002b50)
allocated by thread T0 here:
    #0 0x49635d in malloc (/mnt/2tb/cf-relic/cryptofuzz/a.out+0x49635d)
    #1 0x4c8a89 in bn_make /mnt/2tb/cf-relic/relic/src/bn/relic_bn_mem.c:60:20
    #2 0x4cae3f in bn_mod_barrt /mnt/2tb/cf-relic/relic/src/bn/relic_bn_mod.c:101:3
    #3 0x4c6391 in main /mnt/2tb/cf-relic/cryptofuzz/p.c:22:5
    #4 0x7ff6164ef0b2 in __libc_start_main /build/glibc-sMfBJT/glibc-2.31/csu/../csu/libc-start.c:308:16

[dfaranha]

Oh, the fix triggered a different bug, potentially fixed by 384468a

[guidovranken]

Fixed for my previous reproducer, but:

#include <relic_conf.h>
#include <relic.h>

int main(void)
{
    if ( core_init() != RLC_OK ) abort();

    bn_t A, B, tmp, R;

    bn_null(A); bn_new(A);
    bn_null(B); bn_new(B);
    bn_null(tmp); bn_new(tmp);
    bn_null(R); bn_new(R);

    const char* s1 = "2";
    const char* s2 = "1";

    bn_read_str(A, s1, strlen(s1), 10);
    bn_read_str(B, s2, strlen(s2), 10);

    bn_mod_pre_barrt(tmp, B);
    bn_mod_barrt(R, A, B, tmp);

    bn_free(A);
    bn_free(B);
    bn_free(tmp);
    bn_free(R);
    return 0;
}

=================================================================
==29116==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x612000003038 at pc 0x0000005495c8 bp 0x7ffc12162e90 sp 0x7ffc12162e88
WRITE of size 8 at 0x612000003038 thread T0
    #0 0x5495c7 in bn_muld_low /mnt/2tb/cf-relic/relic/src/low/easy/relic_bn_mul_low.c:139:6
    #1 0x4cb330 in bn_mod_barrt /mnt/2tb/cf-relic/relic/src/bn/relic_bn_mod.c
    #2 0x4c6391 in main /mnt/2tb/cf-relic/cryptofuzz/p.c:22:5
    #3 0x7fac0cbc60b2 in __libc_start_main /build/glibc-sMfBJT/glibc-2.31/csu/../csu/libc-start.c:308:16
    #4 0x41c2ed in _start (/mnt/2tb/cf-relic/cryptofuzz/a.out+0x41c2ed)

0x612000003038 is located 8 bytes to the left of 272-byte region [0x612000003040,0x612000003150)
allocated by thread T0 here:
    #0 0x49635d in malloc (/mnt/2tb/cf-relic/cryptofuzz/a.out+0x49635d)
    #1 0x4c8a89 in bn_make /mnt/2tb/cf-relic/relic/src/bn/relic_bn_mem.c:60:20
    #2 0x4cae3f in bn_mod_barrt /mnt/2tb/cf-relic/relic/src/bn/relic_bn_mod.c:101:3
    #3 0x4c6391 in main /mnt/2tb/cf-relic/cryptofuzz/p.c:22:5
    #4 0x7fac0cbc60b2 in __libc_start_main /build/glibc-sMfBJT/glibc-2.31/csu/../csu/libc-start.c:308:16

[dfaranha]

You found a gradient descent of interlinked bugs!

There is a more principled attempt to fix at 3563cb2

[guidovranken]

Confirmed fixed as far as I can tell now. If there's anything more we will hear it from OSS-Fuzz.