6 ms·
Sounds like the author would agree it's fine to use RSA, so long as you use an audited library with a well-designed API that makes it easy to do the right thing
by jchook 5y ago
Sounds like the author would agree it's fine to use RSA, so long as you use an audited library with a well-designed API that makes it easy to do the right thing, and hard to do the wrong thing.
This makes me wonder, if we have an RSA library as good as libsodium, is ECC really a better choice than RSA?
I love libsodium and tend to choose it, but ECC seems far more mysterious to me than RSA. Curve25519 is much newer, has more parameters, and could potentially have a backdoor (like it's precursor, P-256). It also has much smaller, fixed-size keys.
RSA by comparison is elegant and simple to understand, with only one parameter. It's been in wide use since the 1970s. You can choose the key size.
- adgjlsfhk1 5y agoComparing key size isn't really meaningful here because the main reason for moving away from RSA is that it needs way bigger keys to achieve the same security.
- d22 5y agoKeep in mind how much stress you would be putting on only having one implementation. In practice sooner or later someone would write another and using a needlessly complex encryption scheme can lead it to having bugs.
- 112233 5y agoOnly key size. And public exponent. And padding algorithm. And prime generation algorithm. Remember what happened with Infineon’s on-device generated keys?
- duskwuff 5y ago> This makes me wonder, if we have an RSA library as good as libsodium, is ECC really a better choice than RSA? Yes, absolutely. Compare the key generation process, for example: RSA: generate two large prime numbers around half the size of your key, then make sure they aren't too close to each other, or share one of the primes with another RSA key someone else generated, or have certain mathematical relations to each other, or... ECC (specifically Curve25519): take 32 bytes of random data, set and clear a couple bits. Boom, done. Performing operations with ECC keys is also significantly faster, and constant-time implementations are much easier to develop and verify.
- LinAGKar 5y ago>set and clear a couple bits What bits?
- duskwuff 5y agoClear the highest bit, set the next highest bit, and clear the three lowest bits. This process is known as "key clamping", and ensures that the private key is in the right range and is not vulnerable to a couple of specific attacks. https://neilmadden.blog/2020/05/28/whats-the-curve25519-clamping-all-about/ https://neilmadden.blog/2020/05/28/whats-the-curve25519-clam...
- dhzhzjsbevs 5y agoStarting to sound a lot like your description of RSA, just more positive about it.
- bastawhiz 5y agoIt's two bitwise operations
- nullc 5y agokey[31]=(key[31]&63)|64;key[0]&=248; is radically simpler and not remotely comparable to the requirements for RSA key generation. Moreover, RSA key generation is massively slow-- enough to be irritating for users even on fast computers so there is a lot of incentive to 'optimize' key generation and introduce complexity that results in bugs. (do not use, I just implemented what the GP poster said, didn't check if it what he said was correct, but it sounds right)
- duskwuff 5y ago> Moreover, RSA key generation is massively slow-- Not only is it extremely slow, but it's also non-deterministically slow -- there's no constant-time way to randomly generate an RSA key, because searching for suitable primes is a "guess-and-check" process. ECC key generation, on the other hand, is so fast that it's perfectly feasible to use it as part of the session negotiation process (e.g. in ECDHE).
- olliej 5y ago“Seeming” “elegant” is not a good way of choosing cryptographic algorithms (this argument is also unfair to elegance of ECC). RSA has been in use since the 1970s and has been repeatedly shown to be extremely easy to introduce seemingly minor issue that completely break the crypto. Among the many issues are the belief that encryption is just P^^message%N. Which it is not - you must include padding, and doing that padding wrong also breaks the security. In general implementing RSA safely is very hard, then you also get to the the huge keysizes required for acceptable levels of security. An encryption scheme seeming elegant or understandable is not a sign of strength. Neither is age, as basic ciphers like Am+B%N have been used for thousands of years, but are trivially breakable. Furthermore, while RSA dates to the 70s, ECC still dates back to the early 80s IIRC. As for RSA being easy to understand, I’m not sure why you think ECC is hard to understand - you follow the specified addition operation and you get the correct result. I would argue it’s even easier to intuitively understand than RSA, as the whole point is that you’re both adding secret numbers together in such a way that you end up with the same total. This is unless you find the Chinese remainder theorem obvious? Honestly my current preferred encryption scheme is McEliece. Basically you generate an error correction code for a message such that it can correct half the bits in the message. The public key is your error correcting codes basis matrix multiplied by a permutation matrix to shuffle the bits around. Encryption is done by multiply the public key matrix by the message and then flipping half the bits. Decryption is simply inverting the permutation and performing the error correction. As a bonus, in addition to being simple McEliece has also been around since the 70s, encryption and decryption is extremely fast, it has withstood huge amounts of research and isn’t broken by quantum computers. On the downside the keys are impractically large :(
- thaumasiotes 5y ago> An encryption scheme seeming elegant or understandable is not a sign of strength. Neither is age, as basic ciphers like Am+B%N have been used for thousands of years, but are trivially breakable. I don't think the argument is that "we've had RSA since the 70s". I think it's "we've had RSA since the 70s and we still can't break it".
- olliej 5y ago
- stouset 5y ago> and could potentially have a backdoor (like it's precursor, P-256) P-256 is not known to or even suspected to have any backdoors.
- octoberfranklin 5y agoThen I'm sure you can explain where the number c49d3608 86e70493 6a6678e1 139d26b7 819f7e90 came from. http://safecurves.cr.yp.to/rigid.html http://safecurves.cr.yp.to/rigid.html https://credelius.com/credelius/?p=97 https://credelius.com/credelius/?p=97 With Curve25519, by contrast, DJB explains exactly what constraints were imposed (with very solid justifications for each of them) and then proves that Curve25519 is the unique solution to these constraints which minimizes the remaining free coefficient (which maximizes efficiency). NIST should appoint him to be their Czar or something.
- aaronmdjones 5y agoNIST P-256 (and ECDSA in general, to some extent) is widely suspected to have been subverted by NSA, as outlined in the first link in octoberfranklin's response, page 16 of [1], and [2]. [1] https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf [2] https://blog.cr.yp.to/20140323-ecdsa.html https://blog.cr.yp.to/20140323-ecdsa.html "I have a different view. I blame this attack on the ECDSA designers [https://www.nsa.gov/ https://www.nsa.gov/]."
- 3np 5y agoECDSA is a lot computationally cheaper for the same strength. Switching from RSA to ECDSA TLS certs can have a significant impact on the CPU usage for, say a reverse proxy. (By extension, costs less in terms of money and environmental impact). That being said, I do think that global monoculture and putting all eggs in one basket as a society is a bad idea. If you're willing to take the cost and prefer to use something you understand - by all means do so, as long as you're aware of the tradeoffs you're making.
- eek2121 5y agoOf course it is a bad idea. See OpenSSL.