Use Ed25519 instead of RSA for ruleset signatures

[ghost]

	Ed25519	RSASSA-PKCS1-v1_5	RSASSA-PSS	RFC6979	ECDSA
Has no known security vulnerabilities	Yes	No	Yes	Yes	No
Algorithm is well tested	+	++	++	+	++
Has a well tested implementation for JS	TweetNaCl-js (passed audit)	WebCrypto (built-in)	WebCrypto (built-in)	No	WebCrypto (built-in)
Implemented by OpenSSL	No	Yes	Yes	No	Yes
Deprecated	No	Yes	No	No	No

Advantages:

• Higher security with much smaller key size.
• Possibly faster.
• Used in respected open source projects (1, 2).

Disadvantages:

• Currently requires a third-party library (that passed a security audit with no issues found).

[ghost]

ping @Hainish.

[jeremyn]

Where in the code do we use cryptographic signatures? I've tried to answer this question with some searches in GitHub, but couldn't.

[ghost]

@jeremyn https://github.com/EFForg/https-everywhere/tree/sign-rulesets.

[jeremyn]

Thanks @koops76 .

@Hainish By the way, I disagree with the entire approach of out-of-band updates for rulesets. See my comments in https://github.com/EFForg/privacybadger/issues/1466#issuecomment-315792144 and following for Privacy Badger for why.

[ghost]

@jeremyn In turn, I disagree with you, but let's save this for another time. Let's discuss this issue instead.

[Hainish]

@koops76 I'd rather use the WebCrypto API than some library, even if it has been publicly audited. The longevity of crypto APIs implemented directly in the browser seems better assured. We also need something which is supported by openssl, given the signature scripts in util: https://github.com/EFForg/https-everywhere/blob/sign-rulesets/utils/sign-rulesets-standalone.sh https://github.com/EFForg/https-everywhere/blob/sign-rulesets/utils/sign-rulesets-request.sh https://github.com/EFForg/https-everywhere/blob/sign-rulesets/utils/sign-rulesets-airgap.sh

ECDSA might work, and also has a shorter key size.

[jeremyn]

In the gist https://gist.github.com/tqbf/be58d2d39690c3b366ad by the highly respected security expert Thomas Ptacek, under "Asymmetric signatures" he says

Use Nacl, Ed25519, or RFC6979.

which supports @koops76 's point. On the other hand it's hard to argue with wanting to use the API included in the browser.

EDIT: he goes on to say

Avoid: RSA-PKCS1v15, RSA, ECDSA, DSA; really, especially avoid conventional DSA and ECDSA.

[ghost]

@Hainish Signing can be done by a Node script. Do not trade security for using built-in browser features. Do not use ECDSA, it's worse than RSA-PKCS1v15.

[ghost]

@Hainish I believe this should be decided either by public discussion or by EFF's crypto experts and not by your opinion alone.

[Hainish]

@Hainish Signing can be done by a Node script.

We use an airgapped signing machine, node is not installed on it.

For RSA signatures, the risk is prime factorization in a prime product modulus field. For ECDSA, the risk is the Elliptic Curve Discrete Logarithm Problem.

The general consensus is that choosing two large prime factors for RSA (2048-bit for a prime product of a 4092-bit modulus) is more than enough to protect against a brute-force attack. For Quantum attacks like Shor's algorithm, RSA is more versatile. Yes, the key length is an issue, but only when that key is delivered in real-time in a TLS connection, when milliseconds matter. That's when Ec25519 is really preferred. We're bundling our RSA key with the extension - and bundling a 4092-bit key is trivial, it adds a mere 511 bytes to the filesize. This is not a real issue.

Besides, the real weak link in the development chain is that git is signing tags with sha1. So before I refer to the rest of the crypto team at EFF let's tackle the real problems. Using RSA for delivery of signed rulesets doesn't even come close.

[ghost]

@Hainish I don't think this should be closed before public discussion or crypto experts making a decision.

[ghost]

@Hainish Node is not required, just install something that can use NaCl for signing.

[ghost]

@Hainish I still disagree with you closing this issue without actually consulting the public or your colleagues at EFF.

[Hainish]

The problem with crypto experts is there's about 3 of them in the world. This isn't a problem that requires a crypto expert, it's a problem that requires a third-party audit of a security firm.

[ghost]

@Hainish There are more.

[Hainish]

This problem lies in the stack far above the actual crypto, this is an application problem.

[ghost]

Also, read https://github.com/EFForg/https-everywhere/issues/12087#issuecomment-325045120.

Did I say consult Bruce Schneier? Maybe Satoshi Nakomoto? I asked you to consult your colleagues.

[ghost]

That doesn't give us an excuse to use a weaker algorithm.

[Hainish]

And in application, RSA is a fine choice for this problem. Conceivably there is something marginally better, but the real issue is not in the algorithm, it's in the way it's implemented. This is why we're already seeking consultation from 3rd party security firms.

[ghost]

@Hainish Better have some refactoring on this code before showing it to security firms. I am sure there are lots of potentially security-decreasing flaws in the current code. It was written before there were any real code quality standards. We only have added ESLint very recently.

[ghost]

@Hainish I still believe this project should use a better algorithm than the currently used one.

[ghost]

@Hainish Your "air-gap" scheme is no more secure than simply signing on a Internet-connected machine. A compromised machine can output any hash, tricking you into signing any hash. Also it's easier to sneak a dodgy ruleset into the GitHub repository than trying to fool your "air-gap" scheme. Are you going to personally read each ruleset file?

[ghost]

@Hainish Please bring this before your colleagues at EFF. Decisions like this should not be taken by one man.

[cowlicks]

Hi @koops76, I think using RSA from the webcrypto is the right thing to do for our use case.

[ghost]

@cowlicks RSA-PKCS1v15 has known vulnerabilities. SHA-1 and MD5 also has known, practically exploited vulnerabilities but we can't do anything with it until Chrome, Firefox and Git will stop using it for extension signatures and commit hashes. Also read https://github.com/EFForg/https-everywhere/issues/12087#issuecomment-325048106 for a reason why air-gap wouldn't provide any additional security in the way you use it. For it to provide any additional security the rulesets themselves should be written behind the air-gap.

[ghost]

@cowlicks As you can probably guess, I disagree that using RSA is the right thing to do for HTTPS Everywhere's use case. Please provide some arguments, a simple opinion is not as important as the arguments for it.

[jeremyn]

@koops76 To be fair, you asked @Hainish to double-check with someone else at the EFF, he did, and they agree with him, so really the decision should be considered settled.

Anyway as @Hainish said, the question isn't the algorithm, it's the implementation. We probably all agree that Ed22519 is better here, according to the experts, though RSA must still be basically trustworthy or else Google/Mozilla wouldn't include it. The problem though is that Ed22519 requires using some third party library like tweetnacl.js which is just some random library (no offense intended to the creators) with a few authors and low visibility. That's a big risk for security code.

Using tweetnacl.js also generates more work for the EFF staff. If the in-browser RSA is broken, then they can trust that Google/Mozilla will fix it and push updates with minimal API changes. On the other hand for a library like tweetnacl.js, the EFF staff has to go out of their way to subscribe to their newsletter or equivalent to even learn about a problem, and they have to be ready to switch to something else and get a patch out quickly if there is a problem.

So the question isn't just whether RSA is better or worse than Ed22519. It's whether the RSA used -- an algorithm implemented and trusted by big, highly public organizations like Google and Mozilla -- is so much worse than Ed22519 that it's better to trust a low-visibility third-party implementation of another algorithm that will require extra maintenance effort by the EFF.

I think the EFF is making the right decision by using the in-browser API. If you want to convince them otherwise then I recommend updating your arguments to discuss these other factors.

[ghost]

@jeremyn Refuting your first point, Google/Mozilla also include SHA-1. It's in the WebCrypto specification. The fact that it's implemented does not mean that it's secure. It can't be removed without breaking the specification.

[ghost]

@jeremyn Quoting the WebCrypto spec: Developers making use of the SubtleCrypto interface are expected to be aware of the security concerns associated with both the design and implementation of the various algorithms provided. The raw algorithms are provided in order to allow developers maximum flexibility in implementing a variety of protocols and applications, each of which may represent the composition and security parameters in a unique manner that necessitate the use of the raw algorithms.

Source: https://www.w3.org/TR/2016/PR-WebCryptoAPI-20161215/.

[ghost]

I would also like to remind that HTTPS Everywhere is used, both directly and as a part of Tor Browser by activists, whistleblowers and journalists who work under totalitarian regimes. They risk their lives daily. These regimes may have the resources to break RSA-PKCS1v15, not because of weaknesses of RSA algorithm itself, but because of weaknesses of RSA-PKCS1v15's use of it. Both the algorithm and the library I have suggested were audited and have no current known weaknesses, in contrast of RSA-PKCS1v15, which the W3C itself no longer recommends to use.

[jeremyn]

I'm saying that the question isn't RSA vs Ed22519, it's RSA-by-Google vs Ed22519-by-tweetnacl.js. If the mathematical underpinnings of RSA and Ed22519 are each basically trustworthy then -by-Google is the way to go, obviously, as a matter of trust.

Checking the code in chromium/update.js from sign-rulesets, it looks like we are using the RSASSA-PKCS1-v1_5 algorithm. I'm sure you know this already, I'm just noting it here for reference.

Can you try to clarify or quantify the specific risk you're saying comes from RSASSA-PKCS1-v1_5? Elsewhere you've mentioned "possibly faster" and "smaller key size" both of which are irrelevant for, as you later say, people whose lives depend on this stuff being uncrackable. Can you find an academic paper, blog post, StackExchange comment, anything that makes a specific argument like "an adversary with nation-state resources will probably be able to spoof RSASSA-PKCS1-v1_5 signatures within five years"?

[ghost]

@jeremyn Quoting https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/verify: algo is a DOMString defining the signature function to use. Supported values are: HMAC, RSASSA-PKCS1-v1_5, and ECDSA. None of these algorithms are appropriate for HTTPS Everywhere's use case. HMAC is not a digital signature algorithm, so we will ignore it. The strongest of the remaining two is the currently used one, RSASSA-PKCS1-v1_5. But even it has known attacks. That means SubtleCrypto does not meet our use case.

[ghost]

@jeremyn No. SubtleCrypto implements RSASSA-PKCS1-v1_5 which is designed not by Google, but by W3C, and is deprecated. In turn, TweetNaCl.js is derived from a highly respected NaCl cryptographic library.

[ghost]

@jeremyn Here you go: https://cryptosense.com/why-pkcs1v1-5-encryption-should-be-put-out-of-our-misery/.

[ghost]

@jeremyn Also read your own comment: https://github.com/EFForg/https-everywhere/issues/12087#issuecomment-325032697. I agree with it.

[Hainish]

@koops76 I'm aware of the recommendation from WebCrypto. I am in fact a member of that working group.

Adding an extra dependency introduces a greater attack surface, adds maintenance burden as @jeremyn points out, and increases the extension size by far greater than we'd save by including an Ec25519 key instead.

The weaknesses of pkcs1v1.5 revolve around the ability to perform a chosen ciphertext attack, obtaining the decryption for a chosen ciphertext. The implementation in our extension does not perform decryption at all, just verification of a signed blob. Arguments against including RSA-PKCS1v15 in WebCrypto were centered around its use in decryption. In our implementation, we do not use this operation at all - the key is stored on an airgapped machine, an attacker has no ability to perform arbitrary decryptions.

There is no reason we can't migrate to a new signing algorithm once it becomes available. As it stands, RSASSA-PKCS1-v1_5 is a robust choice for our purposes.

[ghost]

@Hainish The only exposed surface is signature validation, and it is very hard to create a signature that would compromise the user's machine if they will attempt to verify it, especially if the algorithm is executed inside a JavaScript sandbox and not directly on the CPU. An attacker should somehow persuade the JavaScript signature validation algorithm to execute a JavaScript string supplied by the attacker, something I cannot imagine how it can be done. The validation function is pure math and the only decision made based on input is whether it is a valid signature.

[ghost]

@Hainish Also see https://github.com/dchest/tweetnacl-js#audits.

[ghost]

@Hainish Even if we use WebCrypto API, we would expose crypto.subtle.verify function to an attacker anyway. I think we should use Ed25519 through TweetNaCl.js now, but the moment WebCrypto starts supporting it natively, we will switch to the native implementation.

[ghost]

@Hainish We could have been using RSASSA-PSS but it's not supported by WebCrypto. It is supported by OpenSSL though.

[jeremyn]

@koops76 Thanks for your link. This looks more appropriate, from the same site, since we are talking about signatures and not encryption: https://cryptosense.com/why-pkcs1v1-5-signature-should-also-be-put-out-of-our-misery/

My worry with tweetnacl.js isn't that it's a trojan, but instead that their code implements the algorithm incorrectly. nacl.js clearly requires a specialist to check properly. So the question is, again, like I said before, do we trust a less-good algorithm implemented by highly well-known authors (Google/Mozilla), or a better algorithm implemented by less well-known authors (tweetnacl.js)?

tweetnacl.js is an attack surface not just because of the API it exposes but because the code itself can be compromised. Someone who wants to attack HTTPS Everywhere could instead attack tweetnacl.js by submitting malicious PRs, hacking GitHub accounts, whatever, and get at HTTPS Everywhere as a result.

The audit you linked just looks at the source at one point in time. If a vulnerability is noticed a year from now, we don't know what the tweetnacl.js team's turnaround time will be to fix it. I'm confident Google would fix a security problem quickly.

[ghost]

@jeremyn We are already not secure against GitHub/contributor account compromise. I am sure the algorithm is implemented correctly. Cure53 is also sure that the algorithm is implemented correctly. I also must reiterate that it is a direct port of a library (NaCl) with very well-known authors (cr.yp.to team). We are going in circles. Let's just have a discussion including as many people as possible instead of me, you, @Hainish and @cowlicks discussing the same thing across >40 comments. Let's post on Tor Project mailing list. Tor Browser users are a very major part of our userbase.

[ghost]

@jeremyn Quoting the audit report:

The overall outcome of this audit signals a particularly positive assessment for TweetNaCl-js, as the testing team was unable to find any security problems in the library. It has to be noted that this is an exceptionally rare result of a source code audit for any project and must be seen as a true testament to a development proceeding with security at its core.

To reiterate, the TweetNaCl-js project, the source code was found to be bug-free at this point.

[...]

In sum, the testing team is happy to recommend the TweetNaCl-js project as likely one of the safer and more secure cryptographic tools among its competition.

[ghost]

@jeremyn TweetNaCl-js releases are GPG signed. We should them instead of using code from the Git repository.

[jeremyn]

@koops76 I agree this discussion isn't really productive anymore. I understand your points and disagree with some of them, and ultimately I agree with the EFF's library/algorithm decision here.

We don't need to invite more people to discuss this. We don't need to vote on this. The EFF staff have listened and disagree. If we can't trust them to make good security decisions then this entire project is in serious trouble, not just this one thing we're talking about.

[ghost]

@jeremyn [...] this entire project is in serious trouble, not just this one thing we're talking about. Maybe. Code quality is extremely low for a project critical for safety of many people. Again, remember that Tor Browser includes this extension by default.

[ghost]

@jeremyn Do you think EFF can't be wrong?

[ghost]

@jeremyn Also, Tor is also transitioning from RSA to Ed25519 for relay keys.

[ghost]

I think if the arguments for using Ed25519 outweigh the arguments for keeping RSASSA-PKCS1-v1_5 EFF must listen to these arguments and revise its choice.

[ghost]

This also rises an important question: Is it a community project or is it a private project of EFF that accepts contribution from the community if EFF wants to accept them, and EFF's decision is always final and can't be challenged?