Key check failed - e is coprime to lambda!

[anonproject]

Tried to build and run on Debian 10 dedicated server.
Ran 'make test' but it failed with:

WARNING: Key check failed - e is coprime to lambda!
ERROR: A bad key was found!

Prior to it I ran it on Ubuntu 18.04 VPS without much trouble.

Initially I thought it was related to openssl version shipped with Debian testing repo (v1.1.1-g) so I manually compiled v1.1.1 which was the version used on Ubuntu, but it did not resolve the issue.

[anonproject]

cc compiler versions differ. On Ubuntu 18.04.1 its 7.4.0. On Debian 10 its 9.3.0.

Yet I took the binary from Ubuntu and ran it on Debian. The results are the same. How can it be?

[anonproject]

Ah. I see.

So I built the executable file on Ubuntu with libcrypto statically linked. Ran it on Debian and it worked.
Then I realized that when I built executable on Debian with the same version of openssl as on Ubuntu, I forgot that I built it with a dynamic link to libcrypto. So the headers were from the v1.1.1 but the link was to the v1.1.1-g. So then I just statically linked the openssl:

Makefile:

#LIBS   += -lpthread -lssl -lcrypto
LIBS    += -Wl,-Bstatic -lssl -lcrypto -Wl,-Bdynamic -lpthread -ldl

LIBS += -L/opt/openssl/lib
CFLAGS += -I/opt/openssl/include

And it worked fine.
There must be something weird with openssl 1.1.1g-1 from the testing repo of Debian 10.

[Rikarin]

Thanks! It's working with manually builded OpenSSL 1.0!

[qqux]

Short version: OpenSSL library changed how prime numbers are generated. Eschalot will not work with OpenSSL version >= 1.1.1f until appropriate changes are made.

Long version: OpenSSL commit openssl/openssl@7eccef2 changed the prime number generation routine used for generating RSA keys. Previously, the numbers (p and q) were generated in a fashion that produced what are called "safe primes". Why are safe primes necessary? Basically, eschalot works by generating a single RSA keypair, with public key consisting of n (modulus, large number derived from p and q) and e (exponent, typically constant, well-known prime, but in our case it's variable). Eschalot repeatedly increments e, appends it to n (ASN.1 DER encoding) and hashes the result until desired prefix is obtained (onion address is an encoded hash of the public key). Now, this technique doesn't work for all instances of p and q. In RSA key generation, it is imperative that (p - 1)(q - 1) be coprime to e. To avoid checking that for every e, we generate p and q such that they are safe primes, which are guaranteed to be coprime to e. This way e can be any odd number, which provides for very fast operation. Eschalot exploited this behavior of OpenSSL for many years until it was changed by the forementioned commit. Luckily, it implements sanity checks that allowed to detect this anomaly. Some keys may still generate correctly due to sheer luck, but generally it's a waste of time, especially with long prefixes (most of the times it'll throw the error). Use older version of OpenSSL. If you've succesfully generated the key using latest OpenSSL, you can use it normally - the bug doesn't affect security of the keys.

More information: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation

[Spl01ter]

For MacOS:
brew uninstall openssl
brew tap-new $USER/old-openssl
brew extract --version=1.0.2t openssl $USER/old-openssl
brew install openssl@1.0.2t

[Spl01ter]

How do I manually link openssl@1.0.2t ?

[Spl01ter]

On mac, installing openssh seems to solve the problem

[Hugo1974]

PREFIX ?= /usr/local/
This work

[keuin]

Thanks! I compiled openssl-1.1.1e and make it statically linked. It works. My system is Ubuntu 20.04.2 LTS.

[mooleshacat]

I get this error every now and then, I just start over... Sometimes I get a key sometimes I don't and I have to manually start over.

It would be nice to have a "continue on error" option.

[qqux]

It would be nice to have a "continue on error" option.

@mooleshacat well, I am afraid that's unlikely. Not only has Tor removed support for v2 onion addresses in September 2021, but this very software hasn't really been touched for nearly a decade now.