Re: Feasibility of constructing backdoors in non-open-source RSA software

On 2011-11-01, Mok-Kong Shen <mok-kong.shen@xxxxxxxxxxx> wrote:

RSA public key cryptography relies on the general computational
difficulty of factorizing a product of two large primes to fulfill its
purposes. Non-open-source software that are used to generate such keys
are clearly by nature potentially susceptible of being secretly
implanted with backdoors by Mafia & Co. that render the factorization
task easy, thus enabling the security of the communications involved
to be compromised. From diverse internet discussions the following
apparently feasible ways of subverting the RSA scheme are known to me
to date:

1. The software contains a predetermined list of public keys and their
corresponding private keys. These are somehow randomly selected and
output by the software on demand. A recent posting in a usenet group
( claims that the current versions of PGP that
are available in a large part of the world outside US have this
rather simple backdoor as a consequence of the US export regulations
that prohibit exportation of strong crypto. (I have no knowledge to
check that claim.)

Well, you could read the source to see that it is nonsense.

2. A little bit more complex method consists in storing in the software
a predetermined list of the approximate values of the ratios of the
two prime numbers that are to be chosen to form the public keys.
Each time when a key is to be generated by the software, one of the
ratios from the list is somehow randomly selected and used. It is
clear that the factorization of N = P * Q is highly facilitated by
knowing the approximate value of P/Q.

Depends on how approximate. for a 1024 bit N, you would need to know it
to at least 20 sigfig to be of much help. Again, read the source.

3. An idea for a more involved and consequently more difficult to be
detected method stems from the following observation: If one
requires the key to be a number of n digits and specifies in
addition that k of its leading digits (say k is about 1/4 of n) to
be a constant M, then there exist under these constraints in general
lots of pairs of prime numbers P_i and Q_i such that the product
N_i = P_i * Q_i is a reasonable candidate for a RSA key. This means
that, conversely, one could rather flexibly choose a function
f(M) such that, given an arbitrary k digit value M, P = f(M) is a
prime and at the same time one can always find another prime number
Q to result in a reasonable pair of primes for a RSA key that
satisfies the condition that N = f(M) * Q = P * Q is a n digit
number and further has M as its k leading digits. (Note that a small
amount of variation of the trailing digits of Q doesn't have any
influence on the leading digits of the product N, which ensures the
existence of the prime Q in general. Digits in our argument could of
course be replaced by bits, if desired.) Thus f, if appropriately
designed, could serve as a backdoor of the software which, on
generating a n digit RSA key, first somehow randomly chooses a
k digit number M and then determines P and Q as described above to
output a key N, which can be readily factorized with knowledge of f,
which appears however to the uninitiated outsiders as if it were the
product of two entirely randomly chosen primes (under the general
constraints for RSA keys), in which case the factorization would
have been computationally infeasible.

Does anyone happen to know or have ideas of additional and perhaps more
elegant methods?

Which is why you should ensure that a) your encryption is open source,
and b) that the key generation can be farmed out to an outside program
which is open source. Some people keep prattling on that crypto does
not need to be open source, all you need to do is trust the vendor.
Since there is no way to test whether or not crypto works (the weakness
of the key cannot in general be determined just from the key itself --
as you suggest) and since crypto is used precisely because of lack of
trust, trusting the vendor, while a good thing to get, it far from
sufficient. To the argument that you cannot read the source anyway, so
what good does it do, the answer is that that others can read the source
and can report if the source broken. Ie, putting your trust in the
community's ability to find out snakeoil.

M. K. Shen

Relevant Pages