Can the NSA Crack GnuPG

[Pete Stephenson]

On 2/23/2016 9:00 AM, Mercury Rising wrote:
> I saw his old disturbing post at:
> <http://www.austinlinks.com/Crypto/break-pgp.html>

That post is a joke. It even says so.

> I am having a hard time believing it, but if Zimmerman did put in a
> backdoor code in PGP and GnuPG is based on that, wouldn't it be compromised?

If that happened, yes. So far, there's no credible, publicly available
evidence that this has occurred.

GnuPG is based on an open standard (RFC 4880) that is available for your
perusal at https://tools.ietf.org/html/rfc4880

Both the RFC and the GnuPG source code is publicly available. It's
unlikely (though not impossible) that an intentional backdoor exists,
particularly a backdoor that has been inserted undetected not only into
the PGP/GnuPG code, but also into the code of every compiler (including
new ones like LLVM) made in the last 24 years.

If one were particularly concerned, it's possible (albeit costly and
time-consuming) to write one's own disassembler and then disassemble the
compiled code and examine the assembly language for backdoors.

> I went to an EFF meeting in San Francisco and this big guy came up to
> me and said he had a program that would would break PGP. Then Elvis
> left the building fast so I could not follow him fast enough although
> I really tried. IMHO an agent of the Illuminati or its branch arm,
> the NSA.

People come in all shapes and sizes, can enter or leave public venues as
they please, move at whatever speeds they wish, and can say whatever
they want. That doesn't make this big guy's statement true, nor does it
imply membership in particular organizations, shadowy or otherwise.

If the NSA (or some other shadowy organization) could, in fact, break
PGP, why would they send someone to an EFF meeting in San Francisco,
have this person reveal this information to strangers, and then run
away? What purpose would that serve? If anything, I'd expect them to
keep such capabilities heavily guarded so they could use such a method
for intelligence-gathering.

> Cast doubts into the strength of 4096 or larger keys. I don't know
> how many prime numbers are possible between 2 bits (II binary =
> decimal 3) and 4096 bits = decimal a google maybe???)  are possible.

The Prime Number Theorem states that the number of prime numbers between
0 and x is:

x / ln(x)

The number of primes less than 2^4096 are thus:

(2^4096) / ln(2^4096)

which is about 1.84*10^1229.

That's a lot of numbers.

> Now multiply the two prime numbers of this size into a larger number
> then reverse factor and find the two originating prime numbers.

You say that one can "reverse factor" (which I interpret as "factor", as
"reverse factoring" is multiplication) as if it's something trivial.
It's not: as far as we know and barring any mathematical breakthrough,
factoring is hard (at least on classical computers).

If you can factor such enormous semiprimes in a reasonably efficient
way, there's a lot of people who would be interested.

> Now here's a question? If you had a chart showing every prime number
> multiplied by every other prime number couldn't there be a database for
> every multiplied larger number showing the possibilities of each of
> these prime number sets?

Short answer: Not in this universe.

Recall above how I mentioned that there's ~1.84*10^1229 prime numbers
less than 2^4096.

Even if we limit our search for numbers between 2^4096 and 2^4095, that
only reduces the search space by a factor of two. It's still enormous.

Considering there's only about 10^80 (~2^265.75) atoms in the visible
universe, you'd need to fit 2^(4096-265.75) = 1.05*10^1153 prime numbers
per atom in order to store a "chart" of all prime numbers less than 2^4096.

If you could do that you'd likely win multiple Nobel Prizes in different
disciplines. They'd probably have to invent new categories of Nobel
Prizes to award you.

> Some of these larger numbers may only have one pair of numbers that
> would work. AN ADVANCED Database program using array capabilities
> might help. How big would this data base be and how fast could it be
> searched?

Such a database would be unimaginably vaster than the universe.

Searching it would be all-surpassingly impractical. Leaving aside the
speed of light limitations of searching a database far (I've run out of
superlatives) larger than our universe, if you could get each atom in
the universe to output one of the 1.05*10^1153 prime numbers its storing
every Planck time (5.39*10^-44 seconds), it would still take 1.3*10^1092
times longer than the known age of our universe.

Current cosmological models suggest that the universe will reach its
heat death in about 10^100 years, so searching this database would take
~10^992 times longer than the heat death of the universe. How this would
take place is left as an exercise to the reader.

This doesn't consider the time needed to actually do any useful
computation using that data.

I suspect by the time that such a search was completed, any information
encrypted by PGP would be of little use.

> The man who disappeared said he authored a database program using
> arrays for non encryption uses but said it could break PGP.

That is unlikely.

> How does key generation work. Does PGP go into some large database of
> primes and just choose two?  If it just pulled two numbers out of a
> hat, PGP would have to determine if the numbers were prime or not.
> Reverse factoring to test some very large numbers might take a very 
> long time? You must have two of these primes to be able to multiply
> them.

Typically primes are chosen by picking random numbers in the desired
range (e.g. around 2^2048, 2^4096, etc.) and performing primality tests
on them. These tests are probabilistic, but if enough tests are
performed the confidence that a number is prime can be made to any
arbitrary level. See <https://en.wikipedia.org/wiki/Primality_test>

As mentioned earlier, factoring is thought (but not proved) to be hard.
Various mathematical improvements in factoring have been made over the
millennia, but short of a major breakthrough in mathematics, it's likely
that factoring-based cryptosystems will be secure until the development
of quantum computers (see
<https://en.wikipedia.org/wiki/Shor%27s_algorithm>).

Quantum-resistant cryptographic algorithms are something that interests
the NSA. See
<https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html>
for details.

> Apple phones on the other hand - its the password that makes all the
> difference. 10 bad tries of 4-6 digit numbers and all the data is wiped.

...assuming that Apple or the Feds can't load modified software onto the
phone that disables the auto-erase, delay, and lockout functionality. It
is, after all, just software.

Even if the functionality is baked into hardware, hardware can be taken
apart, examined, and modified. It's expensive, risks losing the data one
seeks to recover, and is time-consuming, but it's at least somewhat
feasible to do in our universe.

> I have no idea what kind of encryption they use for the data itself.

AES.

Cheers!
-Pete

(Any math errors are my own.