Buffer overflow in fast_mp_montgomery_reduce about libtommath HOT 9 CLOSED

You're not meant to call this function directly. It's only called if the
input size is valid.

On Mon, May 23, 2016 at 9:43 AM Dmitry Kovalenko [email protected]
wrote:

fast_mp_montgomery_reduce contains the next code:

/* first we have to get the digits of the input into

• an array of double precision words W[...]
  */
  {
  mp_word *_W;
  mp_digit *tmpx;

  /* alias for the W[] array */
  _W = W;

  /* alias for the digits of x*/
  tmpx = x->dp;

  /* copy the digits of a into W[0..a->used-1] */
  for (ix = 0; ix < x->used; ix++) {
  *_W++ = *tmpx++;
  }

I not found the any check/protection for case " x->used > MP_WARRAY "

Please review this code.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub
#63

from libtommath.

Ok.

I offer to use the 'assert' for declaration of expected states/values/behaviors.

from libtommath.

Although ....

mp_montgomery_reduce - it is public function?

I not see any verification/modification of 'x' before call of fast_mp_montgomery_reduce.

int
mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
{
  int     ix, res, digs;
  mp_digit mu;

  /* can the fast reduction [comba] method be used?
   *
   * Note that unlike in mul you're safely allowed *less*
   * than the available columns [255 per default] since carries
   * are fixed up in the inner loop.
   */
  digs = (n->used * 2) + 1;
  if ((digs < MP_WARRAY) &&
      (n->used <
      (1 << ((CHAR_BIT * sizeof(mp_word)) - (2 * DIGIT_BIT))))) {
    return fast_mp_montgomery_reduce (x, n, rho);
  }

int fast_mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
{
  int     ix, res, olduse;
  mp_word W[MP_WARRAY];

  /* get old used count */
  olduse = x->used;

  /* grow a as required */
  if (x->alloc < (n->used + 1)) {
    if ((res = mp_grow (x, n->used + 1)) != MP_OKAY) {
      return res;
    }
  }

  /* first we have to get the digits of the input into
   * an array of double precision words W[...]
   */
  {
    mp_word *_W;
    mp_digit *tmpx;

    /* alias for the W[] array */
    _W   = W;

    /* alias for the digits of  x*/
    tmpx = x->dp;

    /* copy the digits of a into W[0..a->used-1] */
    for (ix = 0; ix < x->used; ix++) {
      *_W++ = *tmpx++;
    }

from libtommath.

I think we should get rid of the stack-buffer W anyways, this sounds like yet another good reason to replace it with a dynamic-sized one from the heap.

from libtommath.

Heap allocation = SLOW
Heap allocation != buffer overflow protection

just saying...

from libtommath.

Stack-based array - it is not problem.

Problem in lack of checks.

As minimum, developers of this library may add the next verification:

if(MP_WARRAY < x->used)
 return MP_VAL;

from libtommath.

I'm not against a check but it's not really a path that was meant to be
called. It's meant to be called from mp_exptmod() which does an mp_mod()
to ensure it's in range. In other uses (ECC) the caller ensures it's in
range.

Like I said, add a check though for completeness.

Tom

On Wed, May 25, 2016 at 4:54 AM Dmitry Kovalenko [email protected]
wrote:

Stack-based array - it is not problem.

Problem in lack of checks.

As minimum, developers of this library may add the next verification:

if(MP_WARRAY < x->used)
return MP_VAL;

—
You are receiving this because you commented.

Reply to this email directly or view it on GitHub
#63 (comment)

from libtommath.

well I'd just have solved it by mp_word* W = XMALLOC(x->used * sizeof(mp_word))
Why?
I don't think the overhead of this allocation is hurting as much as the fact that on smaller embedded systems this huge stack buffer has always to be taken into account... and it'd solve the overflow issue as well...
@tomstdenis any counter-arguments I didn't think of?

from libtommath.

Back in my days at elliptic as a pro cryptographer one of the things we did
as a decent optimization was hoist allocations out of the montgomery
reduction call. It's called 1000s of times per exptmod and each alloc/free
takes up too much time.

Either leave it on the stack but check for errors or allocate it higher
up. Remember this isn't a function that users should be calling on their
own without knowing what they're doing.

On Sat, May 28, 2016 at 12:27 PM Steffen Jaeckel [email protected]
wrote:

well I'd just have solved it by mp_word* W = XMALLOC(x->used *
sizeof(mp_word))
Why?
I don't think the overhead of this allocation is hurting as much as the
fact that on smaller embedded systems this huge stack buffer has always to
be taken into account... and it'd solve the overflow issue as well...
@tomstdenis https://github.com/tomstdenis any counter-arguments I
didn't think of?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#63 (comment),
or mute the thread
https://github.com/notifications/unsubscribe/ALUzJZqvSr3jUCo4X3NXG6r8CxT1w9Y9ks5qGGzugaJpZM4IkiKv
.

from libtommath.