shadow-maint/shadow

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

michaelbrunnbauer opened this issue · 15 comments

michaelbrunnbauer commented

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 commented

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 commented

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 commented

Someone will look at this eventually, right?

alejandro-colomar commented

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 commented

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 commented

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 commented

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 commented

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

alejandro-colomar commented

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

alejandro-colomar commented

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 commented

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

alejandro-colomar commented

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 commented

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 commented

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.