The Million-Key Question: Investigating the Origins of RSA Public Keys | Hacker News Reader

The Million-Key Question: Investigating the Origins of RSA Public Keys

usenix.org

106 pointsdc35233 comments

A short discussion on my blog: https://www.dancvrcek.com/re-investigating-the-origins-of-rs...

It seems pretty unlikely that we're ever going to uncover a practical vulnerability owing to the observations of this paper.

Yes, from what I've read, the researchers discovered that the PGP keys were made by the PGP software and so on.

This kind of inference can be interesting, because occasionally people try to convert a private key from one type to another; for example, there are scripts to convert a private key between PEM, OpenSSH, and GPG formats so that you can re-use it for different applications. (One application for this is to use GPG signatures on public keys to authenticate users and/or servers in SSH.)

So this research might allow someone who didn't already know to recognize more about where a key came from.

Verification that TLS keys are mostly generated by OpenSSL and PGP keys by PGP/GPG are sanity check that method actually works.

If it will turn out, that particular library has vulnerability, one can quickly search for other vulnerable keys from large datasets like IPv4-wide TLS scans.

The impact isn't in discovering a vuln in the software. The impact (as stated in the abstract) is a way to further fingerprint and de-anonymize Tor users and other users who are trying to maintain privacy.

I'm responding to the last paragraph of the post. I acknowledge the privacy implications.

Authors had uncovered vulnerabilities and defects in particular smart card models during their research.

"Although RSA factorization is considered to be an NP- hard problem if keys that fulfil the above conditions are used..."

Isn't this incorrect? The implication would be that quantum computers could solve NP-Complete problems in polynomial time.

Not to mention that being an NP hard problem wouldn't be a strong enough property to ensure the average-case was hard, so I don't think the "considered" saves this from being incorrect...

NP hard is defined with reference to a non-deterministic Turing machine which runs in polynomial time.

A quantum computer is not a Turing machine. Yes, it can solve things in polynomial time that a Turing machine cannot do. But that doesn't mean that given problem is/isn't NP hard.

That's not what I'm saying. I'm saying that if factoring were NP hard, by extension a quantum computer could solve NP complete problems in polynomial time (since every problem in NP is reducible to every NP hard problem, by definition [0]).

That's all I'm saying... they're implying that you could reduce, say, 3SAT to factoring, which would be very very surprising.

[0] https://en.wikipedia.org/wiki/NP-hardness

I do not believe quantum computers can solve NP hard problems in polynomial time. According to https://en.wikipedia.org/wiki/BQP#Relationship_to_other_comp... , "The relation between BQP and NP is not known."

("BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.")

Right, it’s not known. Although technically we don’t know for sure if classical computers can solve NP-hard problems in polynomial time either (that’s the P vs. NP problem).

It's definitely not proven to be correct; we definitely don't know for sure that integer factorization is in NP-hard. If I remember correctly, it's generally suspected that factorization is not NP-complete (and thus outside of NP-hard).

Wikipedia has it first on their "list of problems that might be NP-intermediate", i.e. problems that are in NP but not in P or NP-hard. [0]

[0] https://en.wikipedia.org/wiki/NP-intermediate

Yes, this is an incorrect statement, sorry. It sneaked there after edits by proofreading service, but that is no excuse for us. Should be just NP. (I'm one of the authors of the paper)

Please don't apologize, this is an excellent paper! In retrospect I feel a little bad for nitpicking, honestly -- it's a really fascinating read :)

You may also try online tool that classifies keys based on the results from paper: http://crcs.cz/rsapp/ Just insert encoded certificate or URL to https server and let tool to tell you what library generated that key(s).

If you will provide 5 keys all generated by the same library, the correct library should be within top three most probable sources with high (>95%) probability.

(if not, please submit feedback :))

This is just one of many reasons one should switch from RSA to ECC.

I don't say switching is a bad idea but not sure it would prevent this kind of attack :)

The secret scalar in ECDH doesn't need to be prime; it's just a random number.

Yes, exactly. To generate an RSA key you need a complex mechanism wherein many vulnerabilities can hide. To generate an ECC key all you need is a source of entropy. To be sure vulnerabilities can hide in entropy sources as well, but it's a lot easier to swap out an entropy source than it is to swap out a random prime generator.

... and yet again this shows that complexity is inherently BAD in secure systems.

ECDH doesn't give you authenticity, i.e., you can't get a certificate for that.

When you look at ways to generate ECC keys, there are classes of vulnerable numbers for which you need to test.

Could you be more specific about the "vulnerable numbers" we're talking about? The curve base point is a parameter for ECDSA as well.

I agree that any protocol that required you to generate curves or even base points on the fly would have similar concerns, but we generally don't use those kinds of protocols.

My err - rubbish wording as I was thinking primes and talking curves.

Still, while I'm punching here a wee bit above my weight - I should read the 186-4 again - there are some tests to verify the strength of the prime. Is it enough for a similar classification? - I don't know...

The prime field is part of the definition of the curve. Everyone interoperating on that curve shares it. It may have been generated weirdly --- the Curve25519 prime sure was! --- but all that tells you is what curve they're using.

It's true that the particular curves a system supports could be a kind of fingerprint, but that's a banal observation, equally true of the ciphers they support, or the compression algorithms.

My last comment was towards key generation, not curves. Bug as I said, I am not in a position to say what the impact is.

Sorry, I don't follow. Are you talking about key generation in ECC systems? There's no prime involved there.

> ECDH doesn't give you authenticity, i.e., you can't get a certificate for that.

ECDH doesn't, but ECDSA does. That's why we have Curve25519 & Ed25519, respectively.

As long as you don’t use any of the NIST curves, yes.

Right. I was going to add, "and curve25519 in particular" but decided that sounded too biased.

Oh, to be a fly on the wall at Fort Meade.

Given the thousands of employees the NSA has working on all aspects of cryptography, there must be countless examples of this type of investigation. It's integral to traffic analysis and to fingerprinting of cryptosystems.

At least I hope that the NSA does lots of stuff like this. Because if they don't, what does that leave them doing? If the NSA is simply evil and/or incompetent, that's not enough ROI for the US taxpayers.

Unfortunately, NSA work probably remains highly classified for so long that an ex employee would never be able to write about it in technical detail. But I could be wrong? Are there any Inside Baseball books out there revealing the inner workings of NSA spooks?

Reply on news.ycombinator.com