mpi_swap_cond: different sizes error on eddsa key generation

[NIIBE Yutaka]

Hello again,

I have been looking code closely so that I can find the possible cause,
but I couldn't so far (what I see is the code of libgcrypt in master
branch and LIBGCRYPT-1-7-BRANCH).

Kostis Andrikopoulos <el11151 at mail.ntua.gr> wrote:
> On 11/26/2016 01:11 AM, NIIBE Yutaka wrote:
>> Or..., could you give me information on:
>> Is the call sequence following?
>> 
>>     ...
>>     -> ecc_generate
>>     -> _gcry_ecc_eddsa_genkey
>>     -> _gcry_mpi_ec_mul_point
>>     -> point_swap_cond
>>     -> mpi_swap_cond
>>     -> log_bug
>> 
> Hello again,
>
> we run the application in gdb and got the following stack trace:
>
> https://foss.ntua.gr/paste/?09531d0b88a9cd2c#0JMzhgYKcSPzQUtCKmGpUEs1ahW2NtJmye/zb+T7dKo=
>
> The call sequence seems to be the one you suggested.

Thanks a lot.  There, you can exampine the MPI values.

---------------------------------  GDB session
# to go stack frame of _gcry_mpi_swap_cond
(gdb) up 4

# then let's see the MPI a and MPI b.
(gdb) print *a
(gdb) print *b
---------------------------------

Could you please show us the values?

Here, the condition of log_bug to be called is:

    a->nlimbs > b->alloced

or
    b->nlimbs > a->alloced

This should not occur.  There must be something wrong.

To locate the bug, let me share my thoughts.  Explanation of code in
detail to the very bug reporter might sound strange, but it is effective
sometimes.

In this case, the MPI for point on elliptic curve is allocated in normal
memory (not secure one) and resized by point_resize, by
2*ctx->p->nlimbs+1 (which is large enough, IIUC).  Once MPI memory is
allocated, it never shrinks (IIUC).

I think that the possibility of this failure is that
_gcry_mpi_assign_limb_space is called somewhere (and replaces MPI memory
after initial allocation).  I found that it is called in _gcry_mpi_mul
when U or V is secure but W is not.  I don't think this happens for the
case of ECC computation.

So, I can't find the cause, so far.



        		*	*	*

>From here, it's too long, I know.  You can skip reading this
explanation.

The function _gcry_mpi_swap_cond is to swap two MPI values conditionally
by touching memory of both values.  Regardless of swap of values happens
or not, execution cycles is same and memory access pattern is same.
This is important to mitigate some attacks.

MPI structure (struct gcry_mpi, which is defined in src/mpi.h) is like
this figure:

    MPI:
                 <--------------------alloced-------------------->
                 <---------nlimbs----------------->
     d     ----> [ Limb0 ] [ Limb1 ] ... [ LimbNn ] ... [ LimbNa ]

mpi->d points memory of limbs.  mpi->alloced is limbs allocated.
mpi->nlimbs is valid limbs as a value.

To swap MPI values, number of limbs for two MPI values should be
similar.  But it is still OK when those two MPIs have not exactly same
number of limbs.

Let's consider with following figure.

Before swap:

    MPI a:
                 <----------alloced------------------->
                 <---nlimbs------------>
     d     ----> [ Limb0 ] ... [ LimbA ] ... [ LimbA' ]
                     A0           An


    MPI b:
                 <----------alloced---------------------------->
                 <---nlimbs--------------->
     d     ----> [ Limb0 ] ...    [ LimbB ] ...       [ LimbB' ]
                     B0              Bn'

After swap:

    MPI a:
                 <----------alloced-------------------->
                 <---nlimbs---------------->
     d     ----> [ Limb0 ]  ...    [ LimbB ]..[ LimbA' ]
                     B0               Bn'


    MPI b:
                 <----------alloced---------------------------->
                 <---nlimbs---------------->
     d     ----> [ Limb0 ] ... [ LimbA ] ...          [ LimbB' ]
                     A0           An

When swap happens, _gcry_mpi_swap_cond puts the contents of limbs of a
(A0, ... An, ...) into MPI memory of b and puts the contents of limbs
of b (B0, ... Bn', ...) into MPI memory of a.  The number of limbs it
copies are MIN(a->alloced, b->alloced), it even copies unused limbs and
cycles doesn't depend on MPI values.

When the number of limbs which _gcry_mpi_swap_cond copies is:

    nlimbs = MIN(a->alloced, b->alloced)

For correct results of values, the condition should be met is:

    a->nlimbs <= nlimbs && b->nlimbs <= nlimbs

That is, valid limbs of MPI a should be smaller than to be copied and
valid limbs of MPI b should be smaller than to be copied.

Its negation is:

    a->nlimbs > nlimbs || b->nlimbs > nlimbs

Since a->nlimbs < a->alloced and b->nlimbs < b->alloced always,
it means that the flollowing condition is met when log_bug is called:

    a->nlimbs > b->alloced || b->nlimbs > a->alloced

That is, the value of MPI a cannot be represented by MPI b
or, the value of MPI b cannot be represented by MPI a.

Figure of latter condition is like this:

    MPI a:
                 <----------alloced------------------->
                 <---nlimbs------------>
     d     ----> [ Limb0 ] ... [ LimbA ] ... [ LimbA' ]
                     A0           An


    MPI b:
                 <----------alloced-------------------------------------->
                 <---nlimbs------------------------------->
     d     ----> [ Limb0 ] ...                    [ LimbB ] ... [ LimbB' ]
                     B0                                Bn'

It's too large.
--