6 ms·
The Million-Key Question: Investigating the Origins of RSA Public Keys
- lisper 10y agoThis is just one of many reasons one should switch from RSA to ECC.
- dc352 10y agoI don't say switching is a bad idea but not sure it would prevent this kind of attack :)
- tptacek 10y agoThe secret scalar in ECDH doesn't need to be prime; it's just a random number.
- lisper 10y agoYes, 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.
- api 10y ago... and yet again this shows that complexity is inherently BAD in secure systems.
- dc352 10y agoECDH 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.
- tptacek 10y agoCould 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.
- dc352 10y agoMy 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...
- tptacek 10y agoThe 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.
- zeveb 10y ago> 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.
- kuschku 10y agoAs long as you don’t use any of the NIST curves, yes.
- lisper 10y agoRight. I was going to add, "and curve25519 in particular" but decided that sounded too biased.
- dc352 10y agoA short discussion on my blog: https://www.dancvrcek.com/re-investigating-the-origins-of-rsa-public-keys/ https://www.dancvrcek.com/re-investigating-the-origins-of-rs...
- tptacek 10y agoIt seems pretty unlikely that we're ever going to uncover a practical vulnerability owing to the observations of this paper.
- acqq 10y agoYes, from what I've read, the researchers discovered that the PGP keys were made by the PGP software and so on.
- schoen 10y agoThis 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.
- petrs 10y agoVerification 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.
- pm24601 10y agoThe 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.
- PhantomGremlin 10y agoOh, 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?
- misterrobot 10y ago"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.
- misterrobot 10y agoNot 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...
- dalke 10y agoNP 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.
- misterrobot 10y agoThat'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 https://en.wikipedia.org/wiki/NP-hardness
- dalke 10y agoI do not believe quantum computers can solve NP hard problems in polynomial time. According to https://en.wikipedia.org/wiki/BQP#Relationship_to_other_complexity_classes 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.")
- petrs 10y agoYou may also try online tool that classifies keys based on the results from paper: http://crcs.cz/rsapp/ 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 :))