endless loop in probable_prime

classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

endless loop in probable_prime

Ronny Meeus
Hello

we are in the process of upgrading our openssl to version 1.1.1g.
On one of our architectures (Cavium MIPS, running kernel 4.9) we have
an issue in the ssh-keygen tool. It keeps on consuming 100% CPU of 1
core.
On other architectures we do not see the issue at all.

I instrumented the openssl library with some traces and observed that
it keeps on looping in the "probable prime" function.
At the end of the function the "BN_num_bits" check is done and if the
return value is not equal to "bits" it basically starts all over
again.

    }
    if (!BN_add_word(rnd, delta))
        return 0;
    if (BN_num_bits(rnd) != bits) {
        printf("%s BN_num_bits %d %d\n", __FUNCTION__, BN_num_bits(rnd), bits);
        goto again;
    }
    bn_check_top(rnd);
    return 1;
}

I added the print function and the result of the print is as follows:
probable_prime BN_num_bits 1473 1536
This trace keeps on going forever and the values never change.

Any idea what could be the underlying root-cause?

Many thanks and best regards,
Ronny
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Guido Vranken
I think this could be an issue with the system's /dev/urandom or entropy, as I've observed similar infinite loops in BN_prime when I changed OpenSSL code to always return the same sequence of bytes from its PRNG (for testing purposes). It could also be a genuine bug in OpenSSL, or both. I'll let others comment on that.

On Thu, Jun 18, 2020 at 9:47 AM Ronny Meeus <[hidden email]> wrote:
Hello

we are in the process of upgrading our openssl to version 1.1.1g.
On one of our architectures (Cavium MIPS, running kernel 4.9) we have
an issue in the ssh-keygen tool. It keeps on consuming 100% CPU of 1
core.
On other architectures we do not see the issue at all.

I instrumented the openssl library with some traces and observed that
it keeps on looping in the "probable prime" function.
At the end of the function the "BN_num_bits" check is done and if the
return value is not equal to "bits" it basically starts all over
again.

    }
    if (!BN_add_word(rnd, delta))
        return 0;
    if (BN_num_bits(rnd) != bits) {
        printf("%s BN_num_bits %d %d\n", __FUNCTION__, BN_num_bits(rnd), bits);
        goto again;
    }
    bn_check_top(rnd);
    return 1;
}

I added the print function and the result of the print is as follows:
probable_prime BN_num_bits 1473 1536
This trace keeps on going forever and the values never change.

Any idea what could be the underlying root-cause?

Many thanks and best regards,
Ronny
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Ronny Meeus
Op do 18 jun. 2020 om 11:16 schreef Guido Vranken <[hidden email]>:
>
> I think this could be an issue with the system's /dev/urandom or entropy, as I've observed similar infinite loops in BN_prime when I changed OpenSSL code to always return the same sequence of bytes from its PRNG (for testing purposes). It could also be a genuine bug in OpenSSL, or both. I'll let others comment on that.
>

The HW device that should generate entropy is enabled in the kernel:
~ # zcat /proc/config.gz | grep RANDOM_
CONFIG_HW_RANDOM_TIMERIOMEM=y
CONFIG_HW_RANDOM_OCTEON=y

and the daemon  to populate the data is also running:
~ # ps | grep rngd
 3193 root     /usr/sbin/rngd

Doing the test on the /dev/random also works well:
~ # time dd if=/dev/random of=./out3 bs=1024 count=1 iflag=fullblock
1+0 records in
1+0 records out
real    0m 0.02s
user    0m 0.00s
sys    0m 0.00s

Note that without the daemon operational the dd takes very long so it
looks like the mechanism to generate entropy from the HW is working
well.
When I do an strace on the dd command without the rngd tool running I see:
~ # strace -t dd if=/dev/random of=./out3 bs=1024 count=1 iflag=fullblock
...
12:49:29 openat(AT_FDCWD, "/dev/random", O_RDONLY|O_LARGEFILE) = 3
...
12:49:29 read(0,
"-\335\265BA~Wl\253_\325&$\261\301\6\216\303\326\24q\331\233h\25\205\32(u\343@!"...,
1024) = 72
12:49:29 read(0, "\356\336\32\321\305\304", 952) = 6
12:49:30 read(0, "\233\330\20\240n\312", 946) = 6
12:49:31 read(0, "\25\215A\32\241\246", 940) = 6
12:49:31 read(0, "\350\272\352\350\354V", 934) = 6
12:49:31 read(0, "\274\334u\262\337V", 928) = 6
12:49:31 read(0, "N\243\200\16D>", 922) = 6
12:49:32 read(0, "\34F\333\n%i", 916)   = 6
12:49:32 read(0, "\220\263\344\"\216\374", 910) = 6
12:49:32 read(0, "\27|\305\374V\272", 904) = 6
12:49:32 read(0, "\335\27\374\234\273\356", 898) = 6
12:49:32 read(0, "So\263\242|\207", 892) = 6
12:49:32 read(0, "\207\33\375\236mz", 886) = 6
12:49:34 read(0, "H\375\203v\344J", 880) = 6
12:49:35 read(0, "?o\3\326\334\2", 874) = 6
12:49:36 read(0, ";\22\312\314\237\312", 868) = 6

> On Thu, Jun 18, 2020 at 9:47 AM Ronny Meeus <[hidden email]> wrote:
>>
>> Hello
>>
>> we are in the process of upgrading our openssl to version 1.1.1g.
>> On one of our architectures (Cavium MIPS, running kernel 4.9) we have
>> an issue in the ssh-keygen tool. It keeps on consuming 100% CPU of 1
>> core.
>> On other architectures we do not see the issue at all.
>>
>> I instrumented the openssl library with some traces and observed that
>> it keeps on looping in the "probable prime" function.
>> At the end of the function the "BN_num_bits" check is done and if the
>> return value is not equal to "bits" it basically starts all over
>> again.
>>
>>     }
>>     if (!BN_add_word(rnd, delta))
>>         return 0;
>>     if (BN_num_bits(rnd) != bits) {
>>         printf("%s BN_num_bits %d %d\n", __FUNCTION__, BN_num_bits(rnd), bits);
>>         goto again;
>>     }
>>     bn_check_top(rnd);
>>     return 1;
>> }
>>
>> I added the print function and the result of the print is as follows:
>> probable_prime BN_num_bits 1473 1536
>> This trace keeps on going forever and the values never change.
>>
>> Any idea what could be the underlying root-cause?
>>
>> Many thanks and best regards,
>> Ronny
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Matt Caswell-2
In reply to this post by Ronny Meeus


On 18/06/2020 08:46, Ronny Meeus wrote:

> Hello
>
> we are in the process of upgrading our openssl to version 1.1.1g.
> On one of our architectures (Cavium MIPS, running kernel 4.9) we have
> an issue in the ssh-keygen tool. It keeps on consuming 100% CPU of 1
> core.
> On other architectures we do not see the issue at all.
>
> I instrumented the openssl library with some traces and observed that
> it keeps on looping in the "probable prime" function.
> At the end of the function the "BN_num_bits" check is done and if the
> return value is not equal to "bits" it basically starts all over
> again.
>
>     }
>     if (!BN_add_word(rnd, delta))
>         return 0;
>     if (BN_num_bits(rnd) != bits) {
>         printf("%s BN_num_bits %d %d\n", __FUNCTION__, BN_num_bits(rnd), bits);
>         goto again;
>     }
>     bn_check_top(rnd);
>     return 1;
> }
>
> I added the print function and the result of the print is as follows:
> probable_prime BN_num_bits 1473 1536

Hmm. That is very suspicious. I wonder if the generated number in `rnd`
is actually different each time? Can you check?

Matt



> This trace keeps on going forever and the values never change.
>
> Any idea what could be the underlying root-cause?
>
> Many thanks and best regards,
> Ronny
>
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Viktor Dukhovni
In reply to this post by Ronny Meeus
On Thu, Jun 18, 2020 at 09:46:52AM +0200, Ronny Meeus wrote:

> we are in the process of upgrading our openssl to version 1.1.1g.
> On one of our architectures (Cavium MIPS, running kernel 4.9) we have
> an issue in the ssh-keygen tool. It keeps on consuming 100% CPU of 1
> core.

Have you tried building OpenSSL with no assembly optimizations?

--
    Viktor.
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Viktor Dukhovni
In reply to this post by Ronny Meeus
On Thu, Jun 18, 2020 at 09:46:52AM +0200, Ronny Meeus wrote:

> I added the print function and the result of the print is as follows:
> probable_prime BN_num_bits 1473 1536

The difference is exactly 63 bits!  Suggesting that either the high
64-bit bit word is 0x0000000000000001 or the bit counting is not
working right.

What is the "endianness" of this CPU?  Is it big-endian or
little-endian?  And does OpenSSL expect the correct one?

--
    Viktor.
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Ronny Meeus
In reply to this post by Matt Caswell-2
Op do 18 jun. 2020 om 15:33 schreef Matt Caswell <[hidden email]>:

>
>
>
> On 18/06/2020 08:46, Ronny Meeus wrote:
> > Hello
> >
> > we are in the process of upgrading our openssl to version 1.1.1g.
> > On one of our architectures (Cavium MIPS, running kernel 4.9) we have
> > an issue in the ssh-keygen tool. It keeps on consuming 100% CPU of 1
> > core.
> > On other architectures we do not see the issue at all.
> >
> > I instrumented the openssl library with some traces and observed that
> > it keeps on looping in the "probable prime" function.
> > At the end of the function the "BN_num_bits" check is done and if the
> > return value is not equal to "bits" it basically starts all over
> > again.
> >
> >     }
> >     if (!BN_add_word(rnd, delta))
> >         return 0;
> >     if (BN_num_bits(rnd) != bits) {
> >         printf("%s BN_num_bits %d %d\n", __FUNCTION__, BN_num_bits(rnd), bits);
> >         goto again;
> >     }
> >     bn_check_top(rnd);
> >     return 1;
> > }
> >
> > I added the print function and the result of the print is as follows:
> > probable_prime BN_num_bits 1473 1536
>
> Hmm. That is very suspicious. I wonder if the generated number in `rnd`
> is actually different each time? Can you check?
>

I instrumented both the "probable_prime" and the "bnrand" functions as
you can see below and the values actually change (see below).
But what is strange is that the value of "rnd->size" is only 24 and
the size of the sizeof(rnd->d) is 4 bytes = 32 bits which results only
in 768 bits (24*32) while the number of bits requested is 1536.
So there is a problem with the calculation of the size.
It might have to do with the fact that we run on a 64b kernel with a
32b user land and that we use only 1 toolchain to compile both the
kernel and the user-land.

probable_prime BN_num_bits=1473 bits=1536
BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4):
dd5068b3f6658f33b701d31f0b72aa1e6ccd5e4aed5039b32e8d301eefa0c5a4befaa4877a6ff9c131ef974bd3538496acaed1bd442ad0af60a30f5f8bd364d0a0eb31643135aecfec65bcb1074a4f4667f03cee235765ed5cc59801768380db

probable_prime 0 loop=228 again=114
bnrand bits=1536 top=1 bottom=1 bytes=192
data: ff ec 15 94 95 10 ca 68 0f 54 06 0f b9 14 bc da 5d 33 58 4e 3e
35 ca d5 30 c8 33 a5 c1 61 7f d6 00 26 98 45 df 73 34 3c 32 74 89 e2
da 03 72 20 fe 50 23 85 e7 a0 a6 97 27 38 e8 3e 4d 1d d6 11 66 93 d2
01 40 5a 9e 23 31 1f a8 a8 7c 46 c9 eb 79 02 44 9d 9c a7 fe 5e 80 f4
0b 68 ec a5 2f 59 59 a3 02 56 6b 16 7a 01 a5 bb 3c c9 28 71 3b f5 44
30 a3 00 fb f0 de 65 2a 28 8d 8b 8d 2c 71 84 65 33 a9 73 8d 4e ce d4
86 ce 1e 6d d7 2f a4 2d 6c 1c 27 88 0e 2a 0c 09 d0 ff 10 e7 55 7b 55
a9 34 5c 36 88 c9 03 64 f2 ac ae cc 64 f7 a2 3c 6d 62 72 55 8d 99 69
20 2e 33 8b b6 21 20 dd 57 ef


probable_prime BN_num_bits=1473 bits=1536
BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4):
20dd57f19969202ef7a23c6dc90364f2557b55a90e2a0c09d72fa42d8d4eced48d2c7184fbf0de6528713bf56b167a01eca52f599ca7fe5e7c46c9eb405a9e234d1dd611e7a0a697da037220df73343cc1617fd63e35cad5b914bcda9510ca68

probable_prime 0 loop=230 again=115
bnrand bits=1536 top=1 bottom=1 bytes=192
data: fb 14 f4 1d 93 a7 4e 05 7e 25 2c 7e cd d7 28 c1 04 ad 7d 98 11
7c 11 6e 37 6a fd ed c9 e4 a0 e0 2c 08 76 49 35 1f 5e 12 9c d9 58 be
f6 da 74 71 16 5e 5d 79 f8 8f 2e 3b 8a 97 d4 bb 0b ee fc 2e 9f 30 27
9a da 66 1e b5 5f ba 55 40 7b dd c3 2e 5d b2 2c ed 69 07 06 d6 83 80
82 75 7f 88 3e bf bf ee 4f 91 ca 87 1f 19 4e 62 ac 27 cd e4 60 14 78
98 c4 29 78 14 70 3a 7f 04 25 77 11 f7 7f 1a 18 1b 8b e6 36 47 aa a9
ac 7a 0b c1 2b a7 f6 2c 7d ce 2c e4 6e e4 76 6d 5f cc 13 81 48 55 83
b2 53 15 86 8a b2 3e ce fc 30 66 10 78 70 00 15 0e 91 8e 06 f7 b3 05
57 ca 92 3c fa d8 8b b7 a9 6b


probable_prime BN_num_bits=1473 bits=1536
BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4):
8bb7a96db30557ca7000150eb23ecefc485583b26ee4766d2ba7f62c3647aaa911f77f1a7814703acde46014ca871f197f883ebf690706d67bddc32eda661eb50beefc2ef88f2e3bf6da7471351f5e12c9e4a0e0117c116ecdd728c193a74e05

probable_prime 0 loop=232 again=116
bnrand bits=1536 top=1 bottom=1 bytes=192
data: ec 3f f5 df 8f 59 fe 52 2c db 38 22 1e bf 09 45 76 d4 74 d5 d7
c7 94 fe 4f 61 af d9 56 f3 b6 79 3b a9 91 ce ef 47 91 db b7 8c 66 1d
db f3 d9 91 51 1c 81 42 ff 8d 7a 6c 81 0f 48 52 d8 50 39 b1 68 29 79
a0 83 ac b0 f1 2b 4a 92 10 0f f2 1f 7a dd b7 6f f2 10 fa d7 2d ca cc
98 94 a5 c5 74 a1 67 de 44 85 f3 5a 64 14 d6 bc 3d 7d 1b 5a 69 1b f4
ff b8 28 2f dc c3 b6 e2 d9 e4 bd c4 bc b4 d1 a7 b5 0b 04 8a 87 50 0f
f3 36 06 e8 55 1d 8a ef 66 b5 2d d2 c1 86 87 cb 5b 58 30 12 a9 80 04
bf c2 80 44 af 01 91 1b 97 ca 8c 32 0b f7 47 30 e8 b4 8e d9 fb c5 7b
87 e5 66 61 be 80 56 f5 bd f3



>
>
> > This trace keeps on going forever and the values never change.
> >
> > Any idea what could be the underlying root-cause?
> >
> > Many thanks and best regards,
> > Ronny
> >
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Ronny Meeus
In reply to this post by Viktor Dukhovni
Op do 18 jun. 2020 om 16:20 schreef Viktor Dukhovni
<[hidden email]>:

>
> On Thu, Jun 18, 2020 at 09:46:52AM +0200, Ronny Meeus wrote:
>
> > I added the print function and the result of the print is as follows:
> > probable_prime BN_num_bits 1473 1536
>
> The difference is exactly 63 bits!  Suggesting that either the high
> 64-bit bit word is 0x0000000000000001 or the bit counting is not
> working right.
>
> What is the "endianness" of this CPU?  Is it big-endian or
> little-endian?  And does OpenSSL expect the correct one?
>

This is a big endian CPU.
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Matt Caswell-2
In reply to this post by Ronny Meeus


On 18/06/2020 16:06, Ronny Meeus wrote:

> probable_prime BN_num_bits=1473 bits=1536
> BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4):
> dd5068b3f6658f33b701d31f0b72aa1e6ccd5e4aed5039b32e8d301eefa0c5a4befaa4877a6ff9c131ef974bd3538496acaed1bd442ad0af60a30f5f8bd364d0a0eb31643135aecfec65bcb1074a4f4667f03cee235765ed5cc59801768380db
>
> probable_prime 0 loop=228 again=114
> bnrand bits=1536 top=1 bottom=1 bytes=192
> data: ff ec 15 94 95 10 ca 68 0f 54 06 0f b9 14 bc da 5d 33 58 4e 3e
> 35 ca d5 30 c8 33 a5 c1 61 7f d6 00 26 98 45 df 73 34 3c 32 74 89 e2
> da 03 72 20 fe 50 23 85 e7 a0 a6 97 27 38 e8 3e 4d 1d d6 11 66 93 d2
> 01 40 5a 9e 23 31 1f a8 a8 7c 46 c9 eb 79 02 44 9d 9c a7 fe 5e 80 f4
> 0b 68 ec a5 2f 59 59 a3 02 56 6b 16 7a 01 a5 bb 3c c9 28 71 3b f5 44
> 30 a3 00 fb f0 de 65 2a 28 8d 8b 8d 2c 71 84 65 33 a9 73 8d 4e ce d4
> 86 ce 1e 6d d7 2f a4 2d 6c 1c 27 88 0e 2a 0c 09 d0 ff 10 e7 55 7b 55
> a9 34 5c 36 88 c9 03 64 f2 ac ae cc 64 f7 a2 3c 6d 62 72 55 8d 99 69
> 20 2e 33 8b b6 21 20 dd 57 ef

So, it looks to me like in bnrand things are as we expect them to be. We
do generate 192 bytes (1536) bits of data. My guess is things go wrong
right near the end of bnrand when we convert the data into a BIGNUM via
the BN_bin2bn call.

It looks to me like there is a discrepancy between what OpenSSL thinks
the size of a word is and what the actual size of a word is:

> BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4):

24 * 4 * 8 = 768 bits (exactly half of 1536) in spite of the 1473 that
BN_num_bits is reporting.

BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
should also be 4. If BN_BYTES is being incorrectly set to 8 on your
platform then that would explain the discrepancy. Can you check?


Matt




>
>
> probable_prime BN_num_bits=1473 bits=1536
> BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4):
> 20dd57f19969202ef7a23c6dc90364f2557b55a90e2a0c09d72fa42d8d4eced48d2c7184fbf0de6528713bf56b167a01eca52f599ca7fe5e7c46c9eb405a9e234d1dd611e7a0a697da037220df73343cc1617fd63e35cad5b914bcda9510ca68
>
> probable_prime 0 loop=230 again=115
> bnrand bits=1536 top=1 bottom=1 bytes=192
> data: fb 14 f4 1d 93 a7 4e 05 7e 25 2c 7e cd d7 28 c1 04 ad 7d 98 11
> 7c 11 6e 37 6a fd ed c9 e4 a0 e0 2c 08 76 49 35 1f 5e 12 9c d9 58 be
> f6 da 74 71 16 5e 5d 79 f8 8f 2e 3b 8a 97 d4 bb 0b ee fc 2e 9f 30 27
> 9a da 66 1e b5 5f ba 55 40 7b dd c3 2e 5d b2 2c ed 69 07 06 d6 83 80
> 82 75 7f 88 3e bf bf ee 4f 91 ca 87 1f 19 4e 62 ac 27 cd e4 60 14 78
> 98 c4 29 78 14 70 3a 7f 04 25 77 11 f7 7f 1a 18 1b 8b e6 36 47 aa a9
> ac 7a 0b c1 2b a7 f6 2c 7d ce 2c e4 6e e4 76 6d 5f cc 13 81 48 55 83
> b2 53 15 86 8a b2 3e ce fc 30 66 10 78 70 00 15 0e 91 8e 06 f7 b3 05
> 57 ca 92 3c fa d8 8b b7 a9 6b
>
>
> probable_prime BN_num_bits=1473 bits=1536
> BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4):
> 8bb7a96db30557ca7000150eb23ecefc485583b26ee4766d2ba7f62c3647aaa911f77f1a7814703acde46014ca871f197f883ebf690706d67bddc32eda661eb50beefc2ef88f2e3bf6da7471351f5e12c9e4a0e0117c116ecdd728c193a74e05
>
> probable_prime 0 loop=232 again=116
> bnrand bits=1536 top=1 bottom=1 bytes=192
> data: ec 3f f5 df 8f 59 fe 52 2c db 38 22 1e bf 09 45 76 d4 74 d5 d7
> c7 94 fe 4f 61 af d9 56 f3 b6 79 3b a9 91 ce ef 47 91 db b7 8c 66 1d
> db f3 d9 91 51 1c 81 42 ff 8d 7a 6c 81 0f 48 52 d8 50 39 b1 68 29 79
> a0 83 ac b0 f1 2b 4a 92 10 0f f2 1f 7a dd b7 6f f2 10 fa d7 2d ca cc
> 98 94 a5 c5 74 a1 67 de 44 85 f3 5a 64 14 d6 bc 3d 7d 1b 5a 69 1b f4
> ff b8 28 2f dc c3 b6 e2 d9 e4 bd c4 bc b4 d1 a7 b5 0b 04 8a 87 50 0f
> f3 36 06 e8 55 1d 8a ef 66 b5 2d d2 c1 86 87 cb 5b 58 30 12 a9 80 04
> bf c2 80 44 af 01 91 1b 97 ca 8c 32 0b f7 47 30 e8 b4 8e d9 fb c5 7b
> 87 e5 66 61 be 80 56 f5 bd f3
>
>
>
>>
>>
>>> This trace keeps on going forever and the values never change.
>>>
>>> Any idea what could be the underlying root-cause?
>>>
>>> Many thanks and best regards,
>>> Ronny
>>>
>
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Viktor Dukhovni
In reply to this post by Ronny Meeus
On Thu, Jun 18, 2020 at 05:10:08PM +0200, Ronny Meeus wrote:

> > What is the "endianness" of this CPU?  Is it big-endian or
> > little-endian?  And does OpenSSL expect the correct one?
>
> This is a big endian CPU.

And, is OpenSSL configured for the correct endianness?

On Thu, Jun 18, 2020 at 05:06:50PM +0200, Ronny Meeus wrote:

> I instrumented both the "probable_prime" and the "bnrand" functions as
> you can see below and the values actually change (see below).
> But what is strange is that the value of "rnd->size" is only 24 and
> the size of the sizeof(rnd->d) is 4 bytes = 32 bits which results only

If rnd->d is a pointer, you want sizeof(rnd->d[0]).  Or if you
literrally mean "sizeof(sizeof(rnd->d))" than that's expected with a
32-bit address space.  Either way, you're perhaps reporting a misleading
value.

> So there is a problem with the calculation of the size.

Or not.

> It might have to do with the fact that we run on a 64b kernel with a
> 32b user land and that we use only 1 toolchain to compile both the
> kernel and the user-land.

The size of the address space (size of pointers) should not matter,
what matters are the sizes "int", "long", "long long", ...

> probable_prime 0 loop=228 again=114
> bnrand bits=1536 top=1 bottom=1 bytes=192
> data: ff ec 15 94 95 10 ca 68 0f 54 06 0f b9 14 bc da 5d 33 58 4e 3e
                    ----  5 ---
> 35 ca d5 30 c8 33 a5 c1 61 7f d6 00 26 98 45 df 73 34 3c 32 74 89 e2
> da 03 72 20 fe 50 23 85 e7 a0 a6 97 27 38 e8 3e 4d 1d d6 11 66 93 d2
> 01 40 5a 9e 23 31 1f a8 a8 7c 46 c9 eb 79 02 44 9d 9c a7 fe 5e 80 f4
> 0b 68 ec a5 2f 59 59 a3 02 56 6b 16 7a 01 a5 bb 3c c9 28 71 3b f5 44
> 30 a3 00 fb f0 de 65 2a 28 8d 8b 8d 2c 71 84 65 33 a9 73 8d 4e ce d4
> 86 ce 1e 6d d7 2f a4 2d 6c 1c 27 88 0e 2a 0c 09 d0 ff 10 e7 55 7b 55
> a9 34 5c 36 88 c9 03 64 f2 ac ae cc 64 f7 a2 3c 6d 62 72 55 8d 99 69
                 ----  4 ---             ----  3 ---             ----
> 20 2e 33 8b b6 21 20 dd 57 ef
  2 ---             ---- 1  ---

> probable_prime BN_num_bits=1473 bits=1536
> BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4):
> 20dd57f1 9969202e f7a23c6d c90364f2 [...] 9510ca68
  --  1 -- --  2 -- --  3 -- --  4 -- ...   --  5 --

However, clearly the hex output above captures only every other 32-bits
of the actual byte array.  Perhaps there's something wrong with your
compilation tool-chain.

--
    Viktor.
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

OpenSSL - User mailing list
In reply to this post by Matt Caswell-2
>    BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
    BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
    should also be 4. If BN_BYTES is being incorrectly set to 8 on your
    platform then that would explain the discrepancy. Can you check?

This seems HIGHLY likely since Ronny said earlier that the same config/toolchain is used for 32bit userspace and 64bit kernel, right?

Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Ronny Meeus
Op do 18 jun. 2020 om 18:13 schreef Salz, Rich <[hidden email]>:
>
> >    BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
>     BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
>     should also be 4. If BN_BYTES is being incorrectly set to 8 on your
>     platform then that would explain the discrepancy. Can you check?
>
> This seems HIGHLY likely since Ronny said earlier that the same config/toolchain is used for 32bit userspace and 64bit kernel, right?
>

I used the following print statement so the sizeof is actual of the *d
and not of the pointer :-).
printf("BN_num data (size=%d top=%d neg=%d flags=%d, sizeof(*d)=%d)
BN_BYTES=%d: ", rnd->dmax, rnd->top, rnd->neg, rnd->flags,
sizeof(*rnd->d), BN_BYTES);

The output clearly shows that BN_BYTES is 8:

BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4) BN_BYTES=8:
efe838eb2cf627a7cf1944d5969e17602474f949d4e04f33263e49cdc9917b5f4f71f4f27eb06b2f41930dbac791ded7fae69fa604ec65686b412ef048e91cfd8c976e74ff237112406371b6cb2770588328f8db400718366665b6bca733a19c

I think we are getting close to the root-cause here ...

Ronny
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Matt Caswell-2


On 18/06/2020 17:27, Ronny Meeus wrote:

> Op do 18 jun. 2020 om 18:13 schreef Salz, Rich <[hidden email]>:
>>
>>>    BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
>>     BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
>>     should also be 4. If BN_BYTES is being incorrectly set to 8 on your
>>     platform then that would explain the discrepancy. Can you check?
>>
>> This seems HIGHLY likely since Ronny said earlier that the same config/toolchain is used for 32bit userspace and 64bit kernel, right?
>>
>
> I used the following print statement so the sizeof is actual of the *d
> and not of the pointer :-).
> printf("BN_num data (size=%d top=%d neg=%d flags=%d, sizeof(*d)=%d)
> BN_BYTES=%d: ", rnd->dmax, rnd->top, rnd->neg, rnd->flags,
> sizeof(*rnd->d), BN_BYTES);
>
> The output clearly shows that BN_BYTES is 8:
>
> BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4) BN_BYTES=8:
> efe838eb2cf627a7cf1944d5969e17602474f949d4e04f33263e49cdc9917b5f4f71f4f27eb06b2f41930dbac791ded7fae69fa604ec65686b412ef048e91cfd8c976e74ff237112406371b6cb2770588328f8db400718366665b6bca733a19c
>
> I think we are getting close to the root-cause here ...

Ok, this is clearly why you're getting strange results. The question is
why is sizeof(*d) different to the value of BN_BYTES?

What Configure target did you use to build for this platform?

Also, take a look at the end of the file include/openssl/opensslconf.h

You should see a section at the end that looks like this:

/* Only one for the following should be defined */
# define SIXTY_FOUR_BIT_LONG
# undef SIXTY_FOUR_BIT
# undef THIRTY_TWO_BIT

This file is generated, and depending on what Configure has decided is
appropriate for your platform one of the above 3 should be defined, and
the other 2 undef'd. What does it show for your platform?

Matt

Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Ronny Meeus
In reply to this post by Ronny Meeus
Op do 18 jun. 2020 om 18:27 schreef Ronny Meeus <[hidden email]>:

>
> Op do 18 jun. 2020 om 18:13 schreef Salz, Rich <[hidden email]>:
> >
> > >    BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
> >     BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
> >     should also be 4. If BN_BYTES is being incorrectly set to 8 on your
> >     platform then that would explain the discrepancy. Can you check?
> >
> > This seems HIGHLY likely since Ronny said earlier that the same config/toolchain is used for 32bit userspace and 64bit kernel, right?
> >
>
> I used the following print statement so the sizeof is actual of the *d
> and not of the pointer :-).
> printf("BN_num data (size=%d top=%d neg=%d flags=%d, sizeof(*d)=%d)
> BN_BYTES=%d: ", rnd->dmax, rnd->top, rnd->neg, rnd->flags,
> sizeof(*rnd->d), BN_BYTES);
>
> The output clearly shows that BN_BYTES is 8:
>
> BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4) BN_BYTES=8:
> efe838eb2cf627a7cf1944d5969e17602474f949d4e04f33263e49cdc9917b5f4f71f4f27eb06b2f41930dbac791ded7fae69fa604ec65686b412ef048e91cfd8c976e74ff237112406371b6cb2770588328f8db400718366665b6bca733a19c
>
> I think we are getting close to the root-cause here ...
>

I adapted the code so that the BN_BYTES is 4 in all cases (just a hack).
Now the issue is gone and the loop is not observed anymore but the
tool still fails to generate the keys:

LD_LIBRARY_PATH=/tmp ssh-keygen -A
ssh-keygen: generating new host keys: RSA

probable_prime 0 loop=0 again=0
bnrand bits=1536 top=1 bottom=1 bytes=192
data: db d2 2c 9e d8 99 08 af d0 f9 da 7c 19 2a 0d 05 94 e2 ba fd f5
60 38 74 81 aa 1a 1c cf 02 70 0d a6 97 51 c6 4a e4 13 98 39 99 7b c4
30 21 97 a0 32 89 3e 2c ff a2 fb 3f b3 bd f9 6b 59 00 f5 48 41 b7 57
cc a5 37 f9 d8 be ba f9 3d f0 6e 86 58 27 fb ae ca 9c 7b 2e 3f 4c 33
16 74 23 b0 c7 d7 74 19 8a ad 3e 5d 76 73 a5 f5 4a 95 d5 b0 da 5f a0
34 c8 ee 57 fb 88 22 be 5a f5 92 6e 47 08 68 e5 21 6c 57 b2 1b 1d 50
c9 89 d8 a3 76 24 b3 2d f3 b6 26 bc 35 33 b7 d0 73 09 8c 1b 2d 90 05
5a 75 24 05 1a de 04 31 ef 5b b1 55 62 33 86 8a 72 3d bc 5b c9 a1 55
e4 6a 4f cd 2e 28 5f 1a 09 25

probable_prime BN_num_bits=1536 bits=1536
BN_num data (size=48 top=48 neg=0 flags=13, sizeof(*d)=4) BN_BYTES=4:
5f1a09734fcd2e28a155e46a3dbc5bc933868a725bb15562de0431ef7524051a2d90055a73098c1b3533b7d0f3b626bc7624b32dc989d8a3b21b1d50e5216c576e470868be5af59257fb8822a034c8eed5b0da5fa5f54a953e5d767374198aad23b0c7d74c3316749c7b2e3f27fbaecaf06e8658bebaf93da537f9d841b757cc5900f548b3bdf96bffa2fb3f32893e2c302197a039997bc44ae41398a69751c6cf02700d81aa1a1cf560387494e2bafd192a0d05d0f9da7cd89908afdbd22c9e

sshkey_generate failed: error in libcrypto
ssh-keygen: generating new host keys: DSA sshkey_generate failed:
error in libcrypto
ssh-keygen: generating new host keys: ECDSA sshkey_generate failed:
memory allocation failed
ssh-keygen: generating new host keys: ED25519

I also have the impression that it takes a very long time for the tool
to complete.
On other CPUs (ARM) the tool finishes much quicker (and successful).


> Ronny
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Ronny Meeus
In reply to this post by Matt Caswell-2
Op do 18 jun. 2020 om 20:01 schreef Matt Caswell <[hidden email]>:

>
>
>
> On 18/06/2020 17:27, Ronny Meeus wrote:
> > Op do 18 jun. 2020 om 18:13 schreef Salz, Rich <[hidden email]>:
> >>
> >>>    BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
> >>     BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
> >>     should also be 4. If BN_BYTES is being incorrectly set to 8 on your
> >>     platform then that would explain the discrepancy. Can you check?
> >>
> >> This seems HIGHLY likely since Ronny said earlier that the same config/toolchain is used for 32bit userspace and 64bit kernel, right?
> >>
> >
> > I used the following print statement so the sizeof is actual of the *d
> > and not of the pointer :-).
> > printf("BN_num data (size=%d top=%d neg=%d flags=%d, sizeof(*d)=%d)
> > BN_BYTES=%d: ", rnd->dmax, rnd->top, rnd->neg, rnd->flags,
> > sizeof(*rnd->d), BN_BYTES);
> >
> > The output clearly shows that BN_BYTES is 8:
> >
> > BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4) BN_BYTES=8:
> > efe838eb2cf627a7cf1944d5969e17602474f949d4e04f33263e49cdc9917b5f4f71f4f27eb06b2f41930dbac791ded7fae69fa604ec65686b412ef048e91cfd8c976e74ff237112406371b6cb2770588328f8db400718366665b6bca733a19c
> >
> > I think we are getting close to the root-cause here ...
>
> Ok, this is clearly why you're getting strange results. The question is
> why is sizeof(*d) different to the value of BN_BYTES?
>
> What Configure target did you use to build for this platform?

We have identified the issue.
We use BR to compile our projects and it is a bug in the buildroot scripts.
This was the code before the patch
        default "linux-generic64 no-asm"        if BR2_ARCH_IS_64
        default "linux-generic32 no-asm"
resulting in the usage of the "linux-generic64 no-asm" target.

When change the above line in:
        default "linux-generic64 no-asm"        if BR2_ARCH_IS_64 &&
!BR2_MIPS_NABI32
        default "linux-generic32 no-asm"
the target becomes "linux-generic32 no-asm".

Compiling openssl with this solves the issue. We will deliver this
correction to the buildroot community.
Thanks all for the great support!


> Also, take a look at the end of the file include/openssl/opensslconf.h
>
> You should see a section at the end that looks like this:
>
> /* Only one for the following should be defined */
> # define SIXTY_FOUR_BIT_LONG
> # undef SIXTY_FOUR_BIT
> # undef THIRTY_TWO_BIT

For completeness, this was the section in the file:

/* Only one for the following should be defined */
# define SIXTY_FOUR_BIT_LONG
# undef SIXTY_FOUR_BIT
# undef THIRTY_TWO_BIT

> This file is generated, and depending on what Configure has decided is
> appropriate for your platform one of the above 3 should be defined, and
> the other 2 undef'd. What does it show for your platform?
>
> Matt
>
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Ronny Meeus
Replying again since it looks like the final mail has not been
delivered to the newsgroup archive.
The issue has been found. It was a bug in buildroot passing the wrong target.

Op do 18 jun. 2020 om 20:33 schreef Ronny Meeus <[hidden email]>:

>
> Op do 18 jun. 2020 om 20:01 schreef Matt Caswell <[hidden email]>:
> >
> >
> >
> > On 18/06/2020 17:27, Ronny Meeus wrote:
> > > Op do 18 jun. 2020 om 18:13 schreef Salz, Rich <[hidden email]>:
> > >>
> > >>>    BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
> > >>     BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
> > >>     should also be 4. If BN_BYTES is being incorrectly set to 8 on your
> > >>     platform then that would explain the discrepancy. Can you check?
> > >>
> > >> This seems HIGHLY likely since Ronny said earlier that the same config/toolchain is used for 32bit userspace and 64bit kernel, right?
> > >>
> > >
> > > I used the following print statement so the sizeof is actual of the *d
> > > and not of the pointer :-).
> > > printf("BN_num data (size=%d top=%d neg=%d flags=%d, sizeof(*d)=%d)
> > > BN_BYTES=%d: ", rnd->dmax, rnd->top, rnd->neg, rnd->flags,
> > > sizeof(*rnd->d), BN_BYTES);
> > >
> > > The output clearly shows that BN_BYTES is 8:
> > >
> > > BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4) BN_BYTES=8:
> > > efe838eb2cf627a7cf1944d5969e17602474f949d4e04f33263e49cdc9917b5f4f71f4f27eb06b2f41930dbac791ded7fae69fa604ec65686b412ef048e91cfd8c976e74ff237112406371b6cb2770588328f8db400718366665b6bca733a19c
> > >
> > > I think we are getting close to the root-cause here ...
> >
> > Ok, this is clearly why you're getting strange results. The question is
> > why is sizeof(*d) different to the value of BN_BYTES?
> >
> > What Configure target did you use to build for this platform?
>
> We have identified the issue.
> We use BR to compile our projects and it is a bug in the buildroot scripts.
> This was the code before the patch
>         default "linux-generic64 no-asm"        if BR2_ARCH_IS_64
>         default "linux-generic32 no-asm"
> resulting in the usage of the "linux-generic64 no-asm" target.
>
> When change the above line in:
>         default "linux-generic64 no-asm"        if BR2_ARCH_IS_64 &&
> !BR2_MIPS_NABI32
>         default "linux-generic32 no-asm"
> the target becomes "linux-generic32 no-asm".
>
> Compiling openssl with this solves the issue. We will deliver this
> correction to the buildroot community.
> Thanks all for the great support!
>
>
> > Also, take a look at the end of the file include/openssl/opensslconf.h
> >
> > You should see a section at the end that looks like this:
> >
> > /* Only one for the following should be defined */
> > # define SIXTY_FOUR_BIT_LONG
> > # undef SIXTY_FOUR_BIT
> > # undef THIRTY_TWO_BIT
>
> For completeness, this was the section in the file:
>
> /* Only one for the following should be defined */
> # define SIXTY_FOUR_BIT_LONG
> # undef SIXTY_FOUR_BIT
> # undef THIRTY_TWO_BIT
>
> > This file is generated, and depending on what Configure has decided is
> > appropriate for your platform one of the above 3 should be defined, and
> > the other 2 undef'd. What does it show for your platform?
> >
> > Matt
> >
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

Matt Caswell-2
Great - glad you found it.

Matt

On 19/06/2020 06:44, Ronny Meeus wrote:

> Replying again since it looks like the final mail has not been
> delivered to the newsgroup archive.
> The issue has been found. It was a bug in buildroot passing the wrong target.
>
> Op do 18 jun. 2020 om 20:33 schreef Ronny Meeus <[hidden email]>:
>>
>> Op do 18 jun. 2020 om 20:01 schreef Matt Caswell <[hidden email]>:
>>>
>>>
>>>
>>> On 18/06/2020 17:27, Ronny Meeus wrote:
>>>> Op do 18 jun. 2020 om 18:13 schreef Salz, Rich <[hidden email]>:
>>>>>
>>>>>>    BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
>>>>>     BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
>>>>>     should also be 4. If BN_BYTES is being incorrectly set to 8 on your
>>>>>     platform then that would explain the discrepancy. Can you check?
>>>>>
>>>>> This seems HIGHLY likely since Ronny said earlier that the same config/toolchain is used for 32bit userspace and 64bit kernel, right?
>>>>>
>>>>
>>>> I used the following print statement so the sizeof is actual of the *d
>>>> and not of the pointer :-).
>>>> printf("BN_num data (size=%d top=%d neg=%d flags=%d, sizeof(*d)=%d)
>>>> BN_BYTES=%d: ", rnd->dmax, rnd->top, rnd->neg, rnd->flags,
>>>> sizeof(*rnd->d), BN_BYTES);
>>>>
>>>> The output clearly shows that BN_BYTES is 8:
>>>>
>>>> BN_num data (size=24 top=24 neg=0 flags=13, sizeof(*d)=4) BN_BYTES=8:
>>>> efe838eb2cf627a7cf1944d5969e17602474f949d4e04f33263e49cdc9917b5f4f71f4f27eb06b2f41930dbac791ded7fae69fa604ec65686b412ef048e91cfd8c976e74ff237112406371b6cb2770588328f8db400718366665b6bca733a19c
>>>>
>>>> I think we are getting close to the root-cause here ...
>>>
>>> Ok, this is clearly why you're getting strange results. The question is
>>> why is sizeof(*d) different to the value of BN_BYTES?
>>>
>>> What Configure target did you use to build for this platform?
>>
>> We have identified the issue.
>> We use BR to compile our projects and it is a bug in the buildroot scripts.
>> This was the code before the patch
>>         default "linux-generic64 no-asm"        if BR2_ARCH_IS_64
>>         default "linux-generic32 no-asm"
>> resulting in the usage of the "linux-generic64 no-asm" target.
>>
>> When change the above line in:
>>         default "linux-generic64 no-asm"        if BR2_ARCH_IS_64 &&
>> !BR2_MIPS_NABI32
>>         default "linux-generic32 no-asm"
>> the target becomes "linux-generic32 no-asm".
>>
>> Compiling openssl with this solves the issue. We will deliver this
>> correction to the buildroot community.
>> Thanks all for the great support!
>>
>>
>>> Also, take a look at the end of the file include/openssl/opensslconf.h
>>>
>>> You should see a section at the end that looks like this:
>>>
>>> /* Only one for the following should be defined */
>>> # define SIXTY_FOUR_BIT_LONG
>>> # undef SIXTY_FOUR_BIT
>>> # undef THIRTY_TWO_BIT
>>
>> For completeness, this was the section in the file:
>>
>> /* Only one for the following should be defined */
>> # define SIXTY_FOUR_BIT_LONG
>> # undef SIXTY_FOUR_BIT
>> # undef THIRTY_TWO_BIT
>>
>>> This file is generated, and depending on what Configure has decided is
>>> appropriate for your platform one of the above 3 should be defined, and
>>> the other 2 undef'd. What does it show for your platform?
>>>
>>> Matt
>>>
>
Reply | Threaded
Open this post in threaded view
|

Re: endless loop in probable_prime

OpenSSL - User mailing list
In reply to this post by OpenSSL - User mailing list
On 2020-06-18 18:13, Salz, Rich via openssl-users wrote:
>>     BN_bin2bn assumes that the size of a BN_ULONG (the type of a bn->d) is
>      BN_BYTES. You have already told us that sizeof(*d) is 4. So BN_BYTES
>      should also be 4. If BN_BYTES is being incorrectly set to 8 on your
>      platform then that would explain the discrepancy. Can you check?
>
> This seems HIGHLY likely since Ronny said earlier that the same config/toolchain is used for 32bit userspace and 64bit kernel, right?
Maybe the internal headers should contain lines that abort compilation if
inconsistencies are found in the values provided by the (public or private)
headers.

For example, if BN_BYTES > sizeof(BN_ULONG), compilation should stop via
an abstraction over the presence/absence of the _Static_assert,
static_assert
or macro emulation of same in any given compiler.

/* Something like this, but via a macro abstraction: */
#if (some C++ compilers)
   /* Works if  defined(__cplusplus) && __cplusplus >= 201103l */
   /* Works for clang++ if has_feature(cxx_static_assert) */
   /* Works for g++ >= 4.3.x if defined(__GXX_EXPERIMENTAL_CXX0X__) */
   /* Works for MSC++ >= 16.00 */
   /* Fails for g++ 4.7.x specifically */
   /* Fails for some versions of Apple XCode */
   static_assert(
     (BN_BYTES <= sizeof(BN_ULONG)),
     "Failed static assert: " "BN_BYTES <= sizeof(BN_ULONG)");
#elif (some C compilers)
   /* Works for clang with has_feature(c_static_assert) */
   /* Works for gcc >= 4.6.x */
   /* Fails for some versions of Apple XCode */
   _Static_assert(
     (BN_BYTES <= sizeof(BN_ULONG)),
     "Failed static assert: " "BN_BYTES <= sizeof(BN_ULONG)");
#else
   /* Portable fallback, but some fudging may be needed for compilers
    *    without __COUNTER__ */
   /* If assertion fails, compiler will complain about invalid array size */
   /* If assertion is not a const expression, compiler will complain
about that */
   typedef char OSSL_const_assert_##fudge##__LINE__##_##__COUNTER__[
     (BN_BYTES <= sizeof(BN_ULONG)) ? 1 : -1];
#endif


Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S.  https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded