RELIC Toolkit - Integer Overflow Bug Report

[Arjuna Arya]

yo, found a bug in RELIC's big number code that can crash stuff. basically integer overflow leads to heap overflow. here's the deal:

## The Bug

in src/bn/relic_bn_mem.c, function bn_grow(), line 121:

```c
void bn_grow(bn_t a, size_t digits) {
    ...
    if (a->alloc < digits) {
        digits += (RLC_BN_SIZE * 2) - (digits % RLC_BN_SIZE);  // overflow here!
        t = (dig_t *)realloc(a->dp, (RLC_DIG / 8) * digits);
        ...
    }
}
```

what happens is when digits is huge (like near SIZE_MAX), that addition overflows and wraps around to a small number. then realloc allocates tiny buffer but code thinks its still huge. boom - heap overflow when copying data.

## How to Trigger It

easiest way is through bn_read_raw():

```c
void bn_read_raw(bn_t a, const dig_t *raw, size_t len) {
    bn_grow(a, len);        // len directly from user
    dv_copy(a->dp, raw, len);  // writes len bytes to small buffer
}
```

if you pass len = 0xFFFFFFFFFFFFFFFF, the math becomes:
1. digits += 130 - (0xFFFFFFFFFFFFFFFF % 64)
2. digits = 0xFFFFFFFFFFFFFFFF + 129 → overflows to 0x80 (128)
3. realloc(a->dp, 128 * 8 = 1024 bytes) - tiny alloc
4. tries to copy 0xFFFFFFFFFFFFFFFF bytes to 1KB buffer
5. segfault or heap corruption

## Real World Attack Paths

so this isnt just theoretical - there are actual ways to trigger this:

1. BBS signature verification with hash=1 flag - bn_read_bin(m, msg, len) gets called directly with attacker-controlled len

2. ZSS signature verification same thing

3. any app that calls bn_read_raw() on untrusted input

also found similar bug in bn_read_str() at line 350:
```c
bn_grow(a, RLC_CEIL(len * util_bits_dig(radix), RLC_DIG));
```
the multiplication len * util_bits_dig(radix) can overflow before even reaching bn_grow.

## Impact

severity: high
type: heap buffer overflow  
can crash services, potentially code execution
affects signature verification paths which are usually exposed to network input

## Suggested Fix

the fix is simple - just check for overflow before doing the math:

```c
void bn_grow(bn_t a, size_t digits) {
    ...
    if (a->alloc < digits) {
        size_t pad = (RLC_BN_SIZE * 2) - (digits % RLC_BN_SIZE);
        if (digits > SIZE_MAX - pad) {  // check overflow
            RLC_THROW(ERR_NO_MEMORY);
            return;
        }
        digits += pad;
        ...
    }
}
```

also need similar check in bn_read_str() for the multiplication overflow.

## Affected Code

- src/bn/relic_bn_mem.c line 121 (main bug)
- src/bn/relic_bn_util.c line 350 (multiplication overflow in read_str)
- src/bn/relic_bn_util.c line 528 (bn_read_raw calls bn_grow)

## Status

checked upstream at https://github.com/relic-toolkit/relic - bug still present
this is unpatched as of now

found this while auditing the code. tested locally and confirmed the overflow math works as described.

[Diego F. Aranha]

Thank you for the report!

This has been fixed in HEAD. :)

--
Diego F. Aranha

Associate Professor at Computer Science - Aarhus University, Denmark

https://dfaranha.github.io/

Åbogade 34, Building 5335 (Office 291 at Nygaard)

8200 Aarhus N, Denmark

--

---
You received this message because you are subscribed to the Google Groups "relic-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to relic-discus...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/relic-discuss/645a591b-78db-40f7-a881-20cbe8fa3020n%40googlegroups.com.