endless loop in probable_prime

[Matt Caswell]

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
>>>
>