Defining BCRYPT_MIN_ROUNDS and/or BCRYPT_MAX_ROUNDS seems to cause endless loop in passwd

[michaelbrunnbauer]

hi all,

in login.defs, I have set ENCRYPT_METHOD to BCRYPT and whenever I set BCRYPT_MIN_ROUNDS or BCRYPT_MAX_ROUNDS (e.g. one or both to 12), passwd seems to be stuck in an endless loop using 100% CPU when changing the password of a normal user with "passwd " as root. I am using version 4.14.0 and found no hints that this might be fixed in a newer version. I use Kernel 4.19.314 with gcc 10.4.0, glibc 2.39 and libxcrypt 4.4.36. Let me know if you need further information.

Regards,

Michael Brunnbauer

[michaelbrunnbauer]

So for BCRYPT_MIN_ROUNDS/BCRYPT_MAX_ROUNDS 10, BCRYPT_get_salt_rounds in lib/salt.c is calling csrand_interval(10,10), which is calling csrand_uniform32(1), which returns huge numbers like 1096518022 or 2550315236. Those are then downgraded to B_ROUNDS_MAX, which is 31 rounds and that looks like an endless loop ofc. I will try to find out what goes wrong in csrand_uniform32.

[michaelbrunnbauer]

The problem seems to be that the algorithm in csrand_uniform32 assumes csrand() to be in the range 2^32 while it is actually 2^64. The referenced paper says:

Require: source of uniformly-distributed random integers in [0, 2^L ) Require: target interval [0, s) with s ∈ [0, 2^L )

[michaelbrunnbauer]

Someone will look at this eventually, right?

[alejandro-colomar]

Someone will look at this eventually, right?

Sorry, I (and Serge) are not subscribed (I don't know about @ikerexxe). We have a look every now and then, but might take some time to find the report.

In my case at least, if you use an explicit mention (@alejandro-colomar ), I'll receive a mail, and will reply faster. :)

I'll check it. Thanks for the report!

[alejandro-colomar]

I can confirm a bug. I pasted all of the shadow code that is called by csrand_interval() into a small program:

#define _GNU_SOURCE
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define WIDTHOF(x)  (sizeof(x) * CHAR_BIT)

int leading_zerosul(unsigned long x);
unsigned long bit_ceilul(unsigned long x);
unsigned long bit_ceil_wrapul(unsigned long x);
unsigned long csrand(void);
uint32_t csrand_uniform32(uint32_t n);
unsigned long csrand_uniform_slow(unsigned long n);
unsigned long csrand_uniform(unsigned long n);
unsigned long csrand_interval(unsigned long min, unsigned long max);

int
main(void)
{
    printf("%lu\n", csrand_interval(10, 11));
}

int
leading_zerosul(unsigned long x)
{
    return (x == 0) ? ULONG_WIDTH : __builtin_clzl(x);
}

unsigned long
bit_ceilul(unsigned long x)
{
    return 1 + (ULONG_MAX >> leading_zerosul(x));
}

unsigned long
bit_ceil_wrapul(unsigned long x)
{
    if (x == 0)
        return 0;

    return bit_ceilul(x);
}

unsigned long
csrand(void)
{
    unsigned long  r;

    if (getentropy(&r, sizeof(r)) == 0)
        return r;
    exit(1);
}

uint32_t
csrand_uniform32(uint32_t n)
{
    uint32_t  bound, rem;
    uint64_t  r, mult;

    if (n == 0)
        return csrand();

    bound = -n % n;  // analogous to `2^32 % n`, since `x % y == (x-y) % y`

    do {
        r = csrand();
        mult = r * n;
        rem = mult;  // analogous to `mult % 2^32`
    } while (rem < bound);  // p = (2^32 % n) / 2^32;  W.C.: n=2^31+1, p=0.5

    r = mult >> WIDTHOF(n);  // analogous to `mult / 2^32`

    return r;
}

unsigned long
csrand_uniform_slow(unsigned long n)
{
    unsigned long  r, max, mask;

    max = n - 1;
    mask = bit_ceil_wrapul(n) - 1;

    do {
        r = csrand();
        r &= mask;  // optimization
    } while (r > max);  // p = ((mask+1) % n) / (mask+1);  W.C.: p=0.5

    return r;
}

unsigned long
csrand_uniform(unsigned long n)
{
    if (n == 0 || n > UINT32_MAX)
        return csrand_uniform_slow(n);

    return csrand_uniform32(n);
}

unsigned long
csrand_interval(unsigned long min, unsigned long max)
{
    return csrand_uniform(max - min + 1) + min;
}

and it is printing garbagge, while it should be printing a number in the specified range.

alx@debian:~/tmp/shadow$ ./a.out 
2564369380
alx@debian:~/tmp/shadow$ ./a.out 
1303020100
alx@debian:~/tmp/shadow$ ./a.out 
4036762563
alx@debian:~/tmp/shadow$ ./a.out 
2586641031
alx@debian:~/tmp/shadow$ ./a.out 
4064230723

I'll debug it.

[alejandro-colomar]

Smaller reproducer:

#define _GNU_SOURCE
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define WIDTHOF(x)  (sizeof(x) * CHAR_BIT)

unsigned long csrand(void);
uint32_t csrand_uniform32(uint32_t n);
unsigned long csrand_uniform(unsigned long n);
unsigned long csrand_interval(unsigned long min, unsigned long max);

int
main(void)
{
    printf("%lu\n", csrand_interval(10, 11));
}

unsigned long
csrand(void)
{
    unsigned long  r;

    if (getentropy(&r, sizeof(r)) == 0)
        return r;
    exit(1);
}

uint32_t
csrand_uniform32(uint32_t n)
{
    uint32_t  bound, rem;
    uint64_t  r, mult;

    if (n == 0)
        return csrand();

    bound = -n % n;  // analogous to `2^32 % n`, since `x % y == (x-y) % y`

    do {
        r = csrand();
        mult = r * n;
        rem = mult;  // analogous to `mult % 2^32`
    } while (rem < bound);  // p = (2^32 % n) / 2^32;  W.C.: n=2^31+1, p=0.5

    r = mult >> WIDTHOF(n);  // analogous to `mult / 2^32`

    return r;
}

unsigned long
csrand_uniform(unsigned long n)
{
    if (n == 0 || n > UINT32_MAX)
        exit(2);

    return csrand_uniform32(n);
}

unsigned long
csrand_interval(unsigned long min, unsigned long max)
{
    return csrand_uniform(max - min + 1) + min;
}

alx@debian:~/tmp/shadow$ ./a.out 
3796959791
alx@debian:~/tmp/shadow$ ./a.out 
2008463419
alx@debian:~/tmp/shadow$ ./a.out 
343425320
alx@debian:~/tmp/shadow$ ./a.out 
1961322427

[alejandro-colomar]

Smaller reproducer:

#define _GNU_SOURCE
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define WIDTHOF(x)  (sizeof(x) * CHAR_BIT)

unsigned long csrand(void);
uint32_t csrand_uniform32(uint32_t n);
unsigned long csrand_uniform(unsigned long n);
unsigned long csrand_interval(unsigned long min, unsigned long max);

int
main(void)
{
    printf("%u\n", csrand_uniform32(3));
}

unsigned long
csrand(void)
{
    unsigned long  r;

    if (getentropy(&r, sizeof(r)) == 0)
        return r;
    exit(1);
}

uint32_t
csrand_uniform32(uint32_t n)
{
    uint32_t  bound, rem;
    uint64_t  r, mult;

    if (n == 0)
        return csrand();

    bound = -n % n;  // analogous to `2^32 % n`, since `x % y == (x-y) % y`

    do {
        r = csrand();
        mult = r * n;
        rem = mult;  // analogous to `mult % 2^32`
    } while (rem < bound);  // p = (2^32 % n) / 2^32;  W.C.: n=2^31+1, p=0.5

    r = mult >> WIDTHOF(n);  // analogous to `mult / 2^32`

    return r;
}

alx@debian:~/tmp/shadow$ ./a.out 
3854326299
alx@debian:~/tmp/shadow$ ./a.out 
2077425551
alx@debian:~/tmp/shadow$ ./a.out 
2505308187
alx@debian:~/tmp/shadow$ ./a.out 
3115954596

[alejandro-colomar]

The bug seems to have been introduced in 2a61122b5e8f89484dcc88dfd5f6c11de2d8c95a ("2a61122b5e8f89484dcc88dfd5f6c11de2d8c95a"); my fault.

[alejandro-colomar]

It seems that csrand_uniform_slow() works properly, but csrand_uniform32() is broken.

[alejandro-colomar]

This is quite surprising:

#define _GNU_SOURCE
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define WIDTHOF(x)  (sizeof(x) * CHAR_BIT)

unsigned long csrand(void);
unsigned long csrand_uniform(unsigned long n);
uint32_t csrand_uniform32(uint32_t n);
uint64_t csrand_uniform64(uint64_t n);

int
main(void)
{
    printf("----....----....\n");
    printf("%x\n", csrand_uniform32(10));
    printf("%lx\n", csrand_uniform64(10));
}

unsigned long
csrand(void)
{
    unsigned long  r;

    if (getentropy(&r, sizeof(r)) == 0)
        return r;
    exit(1);
}

uint32_t
csrand_uniform32(uint32_t n)
{
    uint32_t  bound, rem;
    uint64_t  r, mult;

    if (n == 0)
        return csrand();

    bound = -n % n;  // analogous to `2^32 % n`, since `x % y == (x-y) % y`

    do {
        r = csrand();
        mult = r * n;
        rem = mult;  // analogous to `mult % 2^32`
    } while (rem < bound);  // p = (2^32 % n) / 2^32;  W.C.: n=2^31+1, p=0.5

    r = mult >> WIDTHOF(n);  // analogous to `mult / 2^32`

    return r;
}

uint64_t
csrand_uniform64(uint64_t n)
{
    uint64_t           bound, rem;
    unsigned __int128  r, mult;

    if (n == 0)
        return csrand();

    bound = -n % n;  // analogous to `2^64 % n`, since `x % y == (x-y) % y`

    do {
        r = csrand();
        mult = r * n;
        rem = mult;  // analogous to `mult % 2^64`
    } while (rem < bound);  // p = (2^64 % n) / 2^64;  W.C.: n=2^63+1, p=0.5

    r = mult >> WIDTHOF(n);  // analogous to `mult / 2^64`

    return r;
}

The 64-bit function works, but the 32-bit doesn't:

alx@debian:~/tmp/shadow$ ./a.out 
----....----....
c19a9153
3
alx@debian:~/tmp/shadow$ ./a.out 
----....----....
543b622c
3
alx@debian:~/tmp/shadow$ ./a.out 
----....----....
56a8eada
3

Which means that this is the diff that broke it:

  * Fast Random Integer Generation in an Interval
  * ACM Transactions on Modeling and Computer Simulation 29 (1), 2019
  * <https://arxiv.org/abs/1805.10941>
  */
-unsigned long
-csrand_uniform(unsigned long n)
+static uint32_t
+csrand_uniform32(uint32_t n)
 {
-       unsigned long      bound, rem;
-       unsigned __int128  r, mult;
+       uint32_t  bound, rem;
+       uint64_t  r, mult;

        if (n == 0)
                return csrand();

        bound = -n % n;  // analogous to `2^64 % n`, since `x % y == (x-y) % y`

        do {
                r = csrand();
                mult = r * n;
                rem = mult;  // analogous to `mult % 2^64`
        } while (rem < bound);  // p = (2^64 % n) / 2^64;  W.C.: n=2^63+1, p=0.5

        r = mult >> WIDTHOF(n);  // analogous to `mult / 2^64`

        return r;
 }

[alejandro-colomar]

@zx2c4, @xry111, would you mind having a look at this? I suspect something is undergoing integer promotions, but I'm not seeing it.

[zx2c4]

https://git.zx2c4.com/linux-rng/tree/drivers/char/random.c#n535

Maybe just borrow this code?

[alejandro-colomar]

https://git.zx2c4.com/linux-rng/tree/drivers/char/random.c#n535

Maybe just borrow this code?

Hmmmm, seeing that code made me see the problem.

The following line is missing a down-cast

r = csrand();

should be

r = (uint32_t) csrand();

or to avoid a cast:

r = csrand32();

(inspired by get_random_u32()).

Thanks!! :-)

[alejandro-colomar]

I'll backport a fix to 4.14.x, even if it was EOL, just in case anyone needs it, to undo my wrong.

[alejandro-colomar]

BTW, off-topic, but if I may ask, @zx2c4 did you receive a couple of mails from me?

Message-ID: <krwymwzvkzjnuijhea7ygwp6alpgo7ovsuxurhgyo2pkjnrwc4@iwqy3cesw4xm>

If so, please ping me by mail in that thread.