error in fast_s_mp_mul_digs about libtommath HOT 7 CLOSED

If I understand it correctly: the pointer tmpc needs to be put above pa otherwise the following loop would overwrite the last digit in c with a zero which is not what the author intended.

from libtommath.

for (ix = 0; ix < (pa + 1); ix++)

following loop would overwrite the last digit in c with a zero

Yes.

Or (as I understand) can corrupt the memory heap.

from libtommath.

I agree with the original comment by dmitry-lipetsk.

The array W contains valid elements from W[0] through W[pa-1]. These pa items need to be copied to c.

As written, the loop accesses c[0] through c[pa]. But c may have only pa elements allocated: the reference to c[pa] is an error.

With the proposed correction, the loop that zeros unused portions of c would NOT overwrite c[pa-1]. The use of tmpc++ in the corrected loop advances tmpc to point to c[pa]. This is the right place at which to start zeroing any of c that remains.

from libtommath.

It is a bit more complicated than that.

The number digs gets the value a->used + b->used + 1 in the file bn_mp_mul.c.
If there is not enough memory allocated in c it gets the amount of digs elements (mp_digit) allocated.
pa on the other side gets the value of MIN(digs, a->used + b->used). That means that pa is always one element smaller than there is memory in c iff called from mp_mul().

The last increment of the pointer tmpc in the loop in question will point outside of c->dp if c->alloc is smaller than a->used + b->used + 2. That is a problem, indeed.

The first test in fast_s_mp_mul_digs () is if (c->alloc < digs) and mp_grow() allocates at least MP_PREC elements more than asked for. That means that the problem only exists if c->alloc equals digs exactly. Simplest solution: just change that test to if (c->alloc <= digs) (or if (c->alloc < (digs +1)) to keep the style) to ensure enough memory. That won't change the programms logic.

from libtommath.

The loop as written references W[pa]. Only W[0] through W[pa-1] are defined by the multiplication operation. W[pa] should not be copied to c.

from libtommath.

MP_WARRAY is large enough but W is of automatic storage duration, so it would need an explicit initialization which it doesn't have, hence the value in W[pa] is indeterminate (ISO 9899-2011 6.7.9) and accessing such a value is undefined behav... no, they changed the definition!? An indeterminate value is now

either an unspecified value or a trap representation (ISO 9899-2011 3.19.2)

We have "unspecified value" here (concluded from the fact that there is no trap defined) and that term is defined in the very next paragraph

valid value of the relevant type where this International Standard imposes no
requirements on which value is chosen in any instance (ISO 9899-2011 3.19.3)

(Don't ask why, it is a decision of a committee)

Doing a mp_digit W[MP_WARRAY] = {0}; would suffice here, I think.
Nuh, just kidding.

I oversaw that problem while trying to untangle the mess with c, thank you for pointing it out..

A question to both of you: where is the pull-request with your corrections, the changed loop? Makes it simpler for the admins hint

from libtommath.

Does someone have an explanation why the 'extract' operation would want to go up to (pa + 1)?

I can't find one.

Therefore I think the original proposal of @dmitry-lipetsk should be sufficient to fix this issue (and most likely also #80)

Does someone disagree?

from libtommath.