Insecure PRNG in key generation

[dfaranha]

Hi, thanks for the library!

However, I do not think it is advisable in this day and age to use the Mersenne Twister for generating private keys:

pailliercryptolib/ipcl/keygen.cpp

Line 19 in 28bd2c1

std::mt19937 rng(dev());

Note that the MT is not cryptographically secure (https://en.wikipedia.org/wiki/Mersenne_Twister), so using it to expand the short seed from dev() to 160 bits violates best practices and may introduce bias. If you have a device node to seed the MT generator, why don't you use it to directly generate the primes?

Heck, that piece of code appears to suffer from a much more serious vulnerability: the MT is seeded with a single 32-bit value. An attacker can just brute-force all possible 2^32 seeds to compute the corresponding primes, and check if they match a known public key.

PS: This discussion started after Markku Saarinen's tweet at https://twitter.com/mjos_crypto/status/1554187194046337031

[skmono]

@dfaranha Thanks for the interest! We do not take security risks and vulnerabilities lightly and launched an investigation on this MT seed issue. We'll get back to this ASAP.

[dfaranha]

Thank you! Is this library within scope of Intel's Bug Bounty program?

[skmono]

Currently being investigated and tested on https://github.com/intel/pailliercryptolib/tree/2-insecure-prng-in-key-generation

c9ba00d Replaces the MT based seed generator with RDRAND/RDSEED instructions based PRNG/TRNG.
6d5e1be Adds support of PRNG where RDRAND/RDSEED instructions are not supported

[skmono]

2eb799b Remove seed setup for prime number generator and prioritizes using RDSEED/RDRAND instructions for prime number generation

[skmono]

Security improvement to be released for 1.1.4

[dfaranha]

Thanks for the update! Now that the bug is fixed, is it possible to still apply through the Bug Bounty program? What about filling a CVE? :)

[skmono]

This issue has been resolved with #17
By the way, we are currently working on officially posting the advisory in the Intel security center alongside with CVE filing based on your reporting. We will keep you(@dfaranha) posted, as we take care of the logistics.

Thanks again for your interest and report!

[dfaranha]

Hi again! Was this issue ever posted as a public advisory? :)

[skmono]

Hi @dfaranha, thank you for your continued interest in our library. IPCL has been impacted by internal changes and in the process of transferring to a potential new owner. As such, we will resume the due processes once it lands in a new spot.
We will let you know as soon as it is applied. Thanks again.

[dfaranha]

With the help of Tjerand Silde (@tjesi), we just noticed that the vulnerable code above was reintroduced in the development branch back in February, when the PRNG is selected for seeding as a fallback option.

Can you please fix it again?

[dfaranha]

This is the offending commit: 4c5d255

[justalittlenoob]

Hi @dfaranha
Thank you very much for your feedback, we will fix this issue with our internal testing and let you know when it is done.
At the same time, try to use random number generator RDSEED and RDRAND when it is possible.

[dfaranha]

Thank you! You can seed from the operating system as a fallback, but make sure to not involve the MT and have a 128-bit seed. It'd actually simpler than what the current code is doing.