endless loop in probable_prime

[Ronny Meeus]

Op do 18 jun. 2020 om 15:33 schreef Matt Caswell <matt at openssl.org>:
>
>
>
> 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
> >