Bug in internal function is_prime() from cipher/primegen.c

[Heiko Stamer]

Hey libgcrypt developers,

during my regular tests on Distributed Privacy Guard [1] I've spotted a
bug in the internal function is_prime() from cipher/primegen.c: my
program dkg-keycheck [2] calls gcry_prime_check(mpi, 0), which, in some
rare cases, triggers an assertion that kills the application:

Ohhhh jeeee: Assertion `_gcry_mpi_cmp( (x), (nminus1) ) < 0 &&
_gcry_mpi_cmp_ui( (x), (1) ) > 0' failed
([redacted]/libgcrypt-1.7.8/cipher/primegen.c:951:is_prime)

First, let's have a look at the following lines of libgcrypt:

{
    _gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );

    /* Make sure that the number is smaller than the prime and
       keep the randomness of the high bit. */
    if ( mpi_test_bit ( x, nbits-2) )
    {
         mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
    }
    else
    {
         mpi_set_highbit( x, nbits-2 );
         mpi_clear_bit( x, nbits-2 );
    }
    gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0);
}

I guess the second part of the assertion is triggered, because the
internal function _gcry_mpi_randomize() and the following lines does not
prevent that x is 0 or 1. Right?

If the checked mpi is a small number (say 65537), then it is more likely
that this happens. I am not sure whether this bug has any serious
security implications (e.g. DoS attacks), however, it should be fixed
anyway.

Regards,
Heiko.

[1] https://www.nongnu.org/dkgpg/
[2] http://git.savannah.nongnu.org/cgit/dkgpg.git/tree/src/dkg-keycheck.cc