Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.security.misc > #280

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

Show all headers | View raw

On 2011-11-01, Mok-Kong Shen <mok-kong.shen@t-online.de> 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
>     (de.comp.security.misc) 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

Back to comp.security.misc | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Feasibility of constructing backdoors in non-open-source RSA software Mok-Kong Shen <mok-kong.shen@t-online.de> - 2011-11-01 09:42 +0100
  Re: Feasibility of constructing backdoors in non-open-source RSA software unruh <unruh@physics.ubc.ca> - 2011-11-01 15:26 +0000
    Re: Feasibility of constructing backdoors in non-open-source RSA software Barry Margolin <barmar@alum.mit.edu> - 2011-11-02 00:10 -0400
    Re: Feasibility of constructing backdoors in non-open-source RSA software Mok-Kong Shen <mok-kong.shen@t-online.de> - 2011-11-03 21:45 +0100

csiph-web