The Phuctoring | Hacker News Reader

The Phuctoring

trilema.com

96 pointsgrhmc29 comments

This story already came up about a year ago, I have written something about it back then: https://blog.hboeck.de/archives/872-About-the-supposed-facto...

To sum it up:

* If you do a batch gcd / mining ps and qs attack on the pgp keyserver data you will find a bunch of broken keys. However most of them are not valid keys, they are just broken copies of valid keys with errors in them. I don't know why they exist, but most likely either due to data transmission errors, disk failures or software bugs. But they don't pose any risk. Their self-signature is invalid, therefore gpg won't use them.

* There are two very old keys that can really be broken with this attack. According to what I know and heard from other people researching this stuff they were created with a no longer developed email encryption tool called CryptoEx by a no longer existing company called Gluck&Kanja. (afaik this hasn't been public knowledge, so I'm dropping it here)

This has been researched before by Arjen Lenstra, Nadia Heninger and myself: https://eprint.iacr.org/2012/064 https://factorable.net/ https://eprint.iacr.org/2015/262.pdf (On the factorable webpage there is an efficient free implementation of this attack by Nadia Heninger - in case you want to play with it)

Yes, all this nonsense was brought up in the previous cover-up of this story also. See http://trilema.com/2015/on-how-the-factored-4096-rsa-keys-st... for a discussion of that.

The announcement is here: http://trilema.com/2016/the-phuctoring/

Other related articles are in their "breaking news" category: http://trilema.com/category/breaking-news/

By the way, I just noticed I'm on their very first list, but I never got the promised email.

Ok, we changed to that first URL from http://phuctor.nosuchlabs.com/phuctored, since it gives a little more context and also points to the other one.

People have made scare posts like this before. In reality this is not an issue, since the public keys in the key server are not the actual public key the user pushed. Due to random factors (cosmic rays, bad memory controllers) at some point in the many copy operations required to send packets to the Internet, the data was silently corrupted and the result was a weak PGP key. If you actually email the users, I guarantee they'll tell you that isn't their real public key.

> If you actually email the users, I guarantee they'll tell you that isn't their real public key.

Have you tried emailing them to test your theory?

I did a little easier than that. I picked two people at random with vanity domains (assuming they'd advertise their key on their site) and did a keyserver lookup for them, and noticed that two keys were submitted to the keyserver on the same exact day for both of them: the broken one from this Web site, and the other one that they advertise as their PGP key. Same key type, same size, same date, same UIDs, different fingerprints.

Not really data, but interesting nonetheless to OP's point (and, if true, a little more ammo in my disliking-keyservers gun).

The real data is how often the exponent 281479271743489 appears on that page. That really points toward bugs in key generation, IMO. Bad gpg at some point?

Yeah, the exponent not being prime does point toward a broken key generation algorithm.

Some of them have legit self-sigs. Also cosmic rays?

IBM estimated in the '90s that an average desktop computer experienced soft-errors from cosmic rays (energetic neutrons striking a memory cell or data bus, perturbing it enough to flip a bit) at a rate of 1 incident/per 256 Megs of RAM/per month

I want to know more that sounds awesome:

Was this it? http://domino.research.ibm.com/tchjr/journalindex.nsf/0b9bc4...

http://www.ida.liu.se/labs/eslab/SNDFT/docs/IBMdram.pdf "This clearly indicates that because of cosmic rays, for every 256 Mbytes of memory, you'll get one soft error a month," said Tim Dell, senior design engineer for IBM Microelectronics. "The same phenomenon for hard errors with multiple bits will also come into effect with soft errors."

Cosmic rays are a big problem for supercomputers. There was a very interesting piece [1] on it in Spectrum recently. One of the funniest anecdotes was about a DEC AlphaServers machine installed at Los Alamos, where they had to put a running server blade inside a neutron beam and confirm the error rates spiked in order to convince the manufacturer that the machines were improperly shielded.

[1] http://spectrum.ieee.org/computing/hardware/how-to-kill-a-su...

Cosmic rays can cause bit-flips (as sibling commenter mentioned). But there's also other interesting ways that bits can flip in memory. For example, Sun had an interesting issue with their SRAM where their manufacturer had accidentally doped the SRAM with radioactive boron. This resulted in alpha particles being emitted that caused corruption in the SRAM (which then caused Solaris to crash because they had parity bit checking).

Other than the TI calculator firmware signing keys and alice@example.com, do any of them have valid self-signatures?

That's still a problem. Having an incorrect breakable public key posted on the server.

Why doesn't the key server scan for this and reject them?

Ask the SKS folks why not?

Key severs don't implement any non-trivial verification. Presumably they have some reason for doing so (apart from laziness). I'd ask them why they don't implement it.

Some of them, but not all. Many have a common issue of high-bits == low-bits. That's would require a very consistent and precise cosmic ray hitting many computers.

Especially seeing how the signature part is copied from other subkeys and pasted into place. Quite the magic rays.

I didn't notice the dodgy exponents. In that case, it's possible it was a broken keygen algorithm. But many of the others (small factors) are probably other errors in the chain (and a cousin comment has done some testing that appears to back this up).

People, such as the same nutjob who is doing it now: http://trilema.com/2015/full-disclosure-4096-rsa-key-in-the-...

Explanation: https://news.ycombinator.com/item?id=9561179

Newbie here. Can somebody summing up the implications of this? At first sight it seems terrible.

Very small, unless you used some really weird/experimental software/hardware to generate your PGP key.

What they keep finding is: keys that do not pass the first sanity test (very non-standard values and values which most likely come from memory corruption) and keys that share primes with other keys (most likely generated by broken or badly initialised PRNGs).

The same class of issues has been found before on SSL certificates and SSH keys. (https://factorable.net/index.html)

It will get interesting people with affected keys can report back how they generated them and find something in common - maybe specific version of PGP / GPG was broken. You can submit your key via http://phuctor.nosuchlabs.com/ if you want to check your own key quickly.

Most of the factors are much too short to be the result of broken/badly initialised PRNGs. The exceptions claim to belong to alice@example.com and txn@ti.com, and the TI ones aren't actually PGP keys at all - one is the 512-bit firmware signing key for the TI-83+ calculator which was factored the hard way a while back and another is a key someone's created sharing the same prime, most likely as a way of mocking TI. Other than those two pairs of obviously-fake keys, the rest are most likely just the result of keys being corrupted somewhere in the process of being uploaded to the keyserver.

> Most of the factors are much too short to be the result of broken/badly initialised PRNGs.

How do you reason?

It would seem that Windows and Apple implementations of RSA/PGP do not live up to standards. If you use either products you should probably check your keys.

I wonder if they will revoke the keys that they have compromised.

Asked, said no: http://btcbase.org/log/2016-05-02#1460859

Reply on news.ycombinator.com