RSA is a fragile cryptosystem

(What's never trivial is key management, how do you get Alice's public key, but that's hard with any sort of public key cryptography.)

  # Generate Bob's private key, which must be kept secret
  skbob = PrivateKey.generate()

  # Bob's public key, and similarly for Alice...
  pkbob = skbob.public_key

  # Bob wishes to send Alice an encrypted message so Bob must make a Box with
  #   his private key and Alice's public key
  bob_box = Box(skbob, pkalice)

  # This is our message to send (binary blob of data)
  message = b"Kill all humans"

  # Encrypt our message
  encrypted = bob_box.encrypt(message)

Unfortunately Coda Hale's post makes a bunch of assumptions. Reasonable assumptions for a lot of the audience, but they're still assumptions. So an equivalent post has to either make equally broad assumptions OR it has to ask you a bunch of questions.

Not crypto questions, but just questions about what you actually want to achieve by having public key crypto. That's going to dictate what you should do. In particular Public Key crypto almost invariably ends up with questions about Identity because of the Public Keys, how do I know this is Bob's Public Key? Do I care about that? Who is "Bob" anyway?

Example #1: For a Web Browser the answer is Identity means the Internet DNS hierarchy decides what hosts are named, the Web PKI provides us with an Authority that says this public key belongs to news.ycombinator.com. It's up to the end user to decide whether that's Hacker News or the Disney Company.

Example #2: For Signal the answer is that Identity is defined only locally by a user's own "address book" or similar features and they get to decide whether this contact is really "Dad" or "skrebbel" or "Jenny Smith", Signal promises to tell you if "Dad" doesn't have the same public key any more (which is suspicious), but paternity tests or verifying in person that "Dad" isn't just a proxy are your problem.

If in fact you "want to allow my customers to send me encrypted data via an untrusted channel" in 2019 you should just set up a secure Web Server, with a Fully Qualified Domain Name your customers know (e.g. write it on business cards, or the sides of vans, or a huge building) with a form on it, where they can submit things. Done. Choose a web server you like and go look at Mozilla's instructions for securing Web Servers.

https://paragonie.com/blog/2019/03/definitive-2019-guide-cry...

https://latacora.micro.blog/2018/04/03/cryptographic-right-a...

To answer your specific comments: firstly, you don't need public key crypto. If both you and your sender can agree on a secret key, you can use secret key crypto just fine. For that, use libsodium's secretbox.

If you really need public key crypto for some reason, libsodium's box is what you want.

What's the "untrusted channel" here? Is this really about encryption in transit, or encryption at rest?

1. Computing secret keys. Inside your program, to generate a 32-byte Curve25519 secret key, start by generating 32 secret random bytes from a cryptographically safe source: mysecret[0], mysecret[1], ..., mysecret[31]. Then do

     mysecret[0] &= 248;
     mysecret[31] &= 127;
     mysecret[31] |= 64;

2. Computing public keys. To generate the corresponding 32-byte Curve25519 public key mypublic[0], mypublic[1], ..., mypublic[31], call

     curve25519(mypublic,mysecret,basepoint);

     const unsigned char basepoint[32] = {9};

     curve25519(shared,mysecret,hispublic);

But seriously, just use libsodium. It has received extensive audits, its abstraction model is easy to use and understand, while mistakes are hard to make.

There are multiple ways to "send encrypted data via an untrusted channel", none of which is perfect, but by descending order of ease of installation and use I would propose this:

- Use Signal or Wire to send that data through messages

- Use Keybase

- Setup an HTTPS server (the default configuration of caddy (https://caddyserver.com/) is good enough)

- Use the "box" function from NaCl, or libsodium, or Go's reimplementation. Those are all libraries, so it will require actual coding. But those libraries are all made so that misuse is very hard, and you don't need to know or even understand how the crypto works to be able to use it

X25519, Ed25519, XSalsa20-Poly1305--you just minimized your footguns.

Unless you have a different library accessible, use TweetNaCl or one of its wrappers--now you've minimized your library footguns: https://tweetnacl.cr.yp.to/

If the operation you want to do isn't part of that library, you need to ask yourself: "Do I truly understand the security implications of what I am try to do?" And then not do it.

There are still lots of implementation footguns (leaking values in memory, side channel attacks, etc.), but those 2 choices put you so far ahead of the pack that your can probably survive until you have enough money to actually pay a cryptographer to come review your stuff.

> If this is article is "easy" crypto,

This article isn’t “easy” crypto. If you expect to understand it, you should already understand how (mathematically) RSA works.

The consensus of not doing your own crypto is decades old at this point and still good advice but also a bit of a cliche. I don't come across a whole lot of projects actually doing their own algorithms. The opposite actually. People just blindly copy paste dependencies and code they think is good enough.

Despite the tone of the article (and its length), the advice is actually sound. RSA has been around quite long; can be quite complicated to deal with when integrating and definitely has a few pitfalls; mainly because it leaves a lot of things as an exercise to the developer and thus plenty of room to do it wrong.

I recently came across ECC and the curve they recommend in the article in Stellar (which uses it) and had to write a bit of code to figure out how to work with keys; this turned out to be very easy. What I like here is that from a developer point of view there's not a lot to configure here and when you use it as a black box that's a good thing. Basically key generation is generating a single random number. Which of course you should do using a secure random generator. You then calculate the public key from this secret. End of story. You probably want some tests around this to verify that you can work with some known key but this basically either works or doesn't.

The only thing I found slightly worrying was the lack of standard/commonly used implementations for different languages. For example, the Stellar Java SDK for stellar pulls in a library (net.i2p.crypto:eddsa) from the i2p project in version 0.3.0. I actually fixed a minor bug at some point to at least get rid of a fork of this that they were using but this suggests to me that there might be some issues lurking out there with not so great implementations.

The discussion for the relevant ticket to implement this in OpenJDK suggests that there are some not so trivial aspects to a proper implementation: https://openjdk.java.net/jeps/324. This only landed in v11. If you are targeting e.g. Android (like Stellar is), you'd need some third party implementation.

I've looked around and there are a few alternate implementations at this point for java and other languages but nothing that I would consider very mainstream yet. So, ECC curve 25519 looks easy to use but the implementations are all over the place in terms of maturity. That in itself should still be considered a red flag and sort of goes against the advice of not rolling your own crypto; which is effectively what you are doing when pulling in other people's libraries in really early versions.

https://safecurves.cr.yp.to

This seems to be an oblique reference to the attack you were referring to.

No, this is actually much easier than increasing general understanding.

Just get the experts (which is a much smaller pool of individuals than the general populace) to commit to designing things like WireGuard instead of OpenVPN, sodium instead of OpenSSL, PASETO instead of JWT, etc.

Furthermore, they don't just tell you to use some random curve thing: they tell you to use a specific implementation with knobs twiddled for security. You could work hard to maybe get everything right, or you can just do this thing and everything will be set for safety for you.

Which I guess explains why RedHat had corruption issues with their package database for, what, a few years before they figured it out? If RedHat needs a few years to get it right for a core component of their core product, who can be expected to?

This RSA discussion makes me wonder if it is in the same boat.

The biggest issue he describes is that, when implementing RSA, most of the parameter choices are necessarily private to the developer, meaning the dev is expected to supply good parameters on her own, when "good" means in terms of heavy math that no non-cryptographer can be expected to know. It's not just key size--there's a bunch of bad choices a dev can make, many of which are hard to recognize as bad choices.

Secondarily, many of those bad choices are driven by implementing RSA in constrained environments, where they're a tradeoff to achieve performance goals--so known-good techniques or algorithms are actually rejected.

ECC, by contrast, is almost all public parameters, so the security community can provide (and already has) known-good parameters that are provably secure, and a dev can simply choose a known-good configuration for their implementation to go with a well-regarded library like libsodium.

Consider the libsodium example: https://libsodium.gitbook.io/doc/public-key_cryptography/aut.... The crypto implementation parameters are handled under the hood.

On the other hand, those of us who write code that uses crypto are generally beaten about the head with 'NEVER ROLL YOUR OWN CRYPTO' and use library implementations right from the start. These are libraries that I assume are indeed written by people with maths degrees and have done careful analysis of the outputs. I know for a fact that I wouldn't trust any encryption I could write myself in an hour.

The biggest obstacle I find with ECC is that it's relatively easy to judge security by RSA (assuming correct implementation) but it's surprisingly difficult to compare the two; if I want RSA-2048, what key size am I supposed to use. ECC was also heavily promoted as offering 'RSA-equivalent security' while using less CPU, which made it particularly suitable for mobile/embedded systems, without necessarily implying it was an improvement over RSA.

And ECC isn't always implemented (or even standardized) securely (https://cr.yp.to/newelliptic/nistecc-20160106.pdf) either.

FYI, RSA PKCS#1v1.5 signatures can be broken due to trivial implementation errors. [1]

[1]: https://www.cs.purdue.edu/homes/schau/files/pkcs1v1_5-ndss19...

See https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number.

There's actually a counter example on that Wiki page - the highly complex numbers used in the NIST curves, for which no path to derivation was publicly provided.

Do the people who perpetuate this meme with no basis not realise the clear and present danger it presents to humanity?

Yes certainly don't use homerolled crypto in production.

More importantly do not dissuade human beings with talent to roll their own, play with others codebases, and in general have a good fucking time with cryptography.

Straight out of the counter-intel handbook is how it looks when people repeat this bullshit ad nauseum.

Everyone on Earth should roll their own crypto. Don't listen to this nonsense, the real world needs you.

FWIW: while I clearly subscribe to the notion of cryptographic education, I also thing that we should give people high-level recipes. Why are they the right ones? Yep, you gotta trust me. I'm fine with both of those existing ('tptacek and I co-authored our Cryptographic Right Answers doc from last year) because they have different audiences.

The differences, according to the article:

1. RSA looks easy, so developers are tempted to roll their own, not so with ECC

2. almost all RSA parameters are necessarily secret, making it harder to peek on supposedly well-designed systems and know what to select (or even how to select), ECC parameters are public and other users can be used as examples

[0]: https://www.f5.com/content/dam/f5/f5-labs/articles/20180423_...

Not a conspiracy ; ). It has to do with the exponentiation. Most fast math libraries exponentiate quickly by squaring and multiplying: if you want to compute, say, x^23, you can either multiply x by itself 23 times, or you can compute: ((((x^2)^2)x)^2)x^2)x: four squaring operations and four multiplications for a savings of 15 operations. You can do this factoring easily based on the binary representation of the exponent - in this case, 23 is 10111. So I’m going to square x 5 times (since the bit length of the representation is 5 bits long) and additionally multiply x by the result every time I encounter a one bit. Now, if I want to speed this up, it’s in my best interest to choose an exponent with the fewest one bits possible - preferably with a one at the beginning and a one at the end, so now I only have to square _n_ times and multiply twice. As it turns out, numbers whose binary representation have a one at the beginning and a one at the end turn out to be Fermat primes: 2^n+1.

And why do you think they do? The article has an explanation for this: RSA looks easy enough to implement. If you tell people to use RSA, many will roll their own, even if they don't know what they're doing.

And to be honest, after having read this article, I don't trust even the properly peer reviewed implementations of RSA. And if compatibility is an issue, I'll first try to convince whoever I must convince to switch to Curve25519, which is simpler to implement, more secure, and faster in most cases. (Of course, one should still use an existing implementation.)

The problem with RSA is that it's easy to understand and easy to implement well enough to work in the sense of "my test cases verify and reject my good and bad signatures", but extremely hard to implement correctly with respect to a host of subtle number theoretic attacks against prime generation, key selection, and bit banging that have been successful in the wild over the past few decades. Given the number of attacks that have been found and their subtlety, it seems likely that there may be additional holes yet to be found in any given implementation.

There are other options that may be harder to understand and implement, but the trade off is that if you get them to work at all, you have probably done it safely (or more likely used a library written by a cryptographer that did it correctly) - Digital Signature Algorithm (DSA) for signing and Elliptic Curve DSA (ECDSA) and Elliptic Curve Diffie-Helman (ECDH) for key agreement which allows for encryption (via a symmetric method).

Use high-level constructs designed and peer-reviewed by cryptographers who know what they're doing.

Basically: use libsodium.

(It's absolutely true that ECC can be as much of a footgun, e.g. non-random-k ECDSA is worse than RSA PKCSv15. But the real takeaway is to use something that's already set for security, like libsodium.)

From the video, one of his major complaints is that people learn RSA in their first year of university, understand the math, then roll their own. How hard can it be, its modulo and exponents. People don't tend to do this with ECC. They just pick a library.

You are right in saying that the same roll your own problems that occur with RSA would occur with ECC.

Presumably there are some organisations that use smart cards for EFS encryption in windows but not sure if BitLocker supports it

In fact, the ability to encrypt directly with RSA is probably a bug, not a feature. There are too many ways to do it catastrophically wrong, and it almost guarantees cryptosystems without forward secrecy.

(WebCrypto isn't great and I'd avoid it, but this isn't why).

As to curves, just use Curve25519 and Curve448 -- those are "nothing up my sleeve" curves where the authors came up with a set of rules for picking a curve's parameters, then picked the one that most closely matched the stated goals according to their rules. The way they are it's very difficult to imagine that the authors somehow found a curve with a backdoor and then retroactively designed rules to generate the same curve, rules that have to be simple and obvious (at least to cryptographers anyways).

There are many benefits to those curves, not the least of which is that their public keys are smaller than RSA or modular DH keys, and that they are faster, all while being more secure.

Not really, because the pitfalls in AES are more well-known. Moreover, there are widespread AES-modes that work pretty well. Really, once you have picked a mode of AES (besides ECB) the biggest pitfalls are 'only use a nonce once' and 'use HMAC (MAC-then-encrypt) if your mode isn't authenticated'. With AES-GCM, that last one drops off. With AES-SIV the first requirement drops, and AES-GCM-SIV has neither consideration. Granted, AES-GCM and similar are not trivial to implement, but given there are test-vectors it is harder to accidentally publish a faulty version.

Moreover, much fewer people actually know how AES works. Especially compared with the amount of people who could essentially implement primitive (insecure) RSA from memory. This comes with many more attempts at RSA. Essentially because the distance between the insecure primitive and the secure systems using RSA is so incredibly large.

I switched to PyPi RSA. It took a little bit of digging, but it seems to use a sane exponent by default:

https://github.com/sybrenstuvel/python-rsa/blob/11bf33264c62...

In one sentence you admit you have limited knowledge of the field and then immediately make a definitive statement about the field. Bold.

This is because RSA lacks forward secrecy: If the private RSA key is stolen, it can be used to retrospectively decrypt all past communication.

Also X448 provides the equivalent security of ~15000-bit RSA with a fraction of the key size, and key generation takes milliseconds instead of minutes.

tl;dr

For key exchange, use X25519 or X448.

For digital signatures, use Curve25519-based ed25519 signatures.

For authenticating communication, use authenticating encryption like ChaCha20-Poly1305 or Salsa20-Poly1305 or AES256-GCM.

For hash function, use Blake2 or SHA3-256 or SHA256.

The NSA seemed to be suggesting that practical quantum computers were coming so soon that people who had not yet upgraded from RSA to ECC should not bother to do so, and instead should save their money for the future upgrade to post-quantum protocols. Shortly thereafter, the NSA released a revised version in response to numerous queries and requests for clarification. The new wording was even more explicit in its negative tone on the continuing use of ECC: “...elliptic curve cryptography is not the long term solution many once hoped it would be. Thus, we have been obligated to update our strategy.” Although other parts of the statement assured the public that ECC was still recommended during the time before the advent of practical quantum computers, the overall impression was inescapable that the NSA was distancing itself from ECC.

Secondly, if you were really that worried about quantum computing, you'd use a quantum-hard kex, like Google did with CECPQ1.

(I can't speak to why the NSA doesn't tell you to do that. I'm sure it has people in it that think so.)

The NSA and NIST should, in a perfect world, have lost all credibility of any sort given the revelations of poisoned RNGs. It boggles my mind that they are still given any credence let alone still considered authoritative.

But more importantly:

1. No, quantum computers that big don't exist.

2. If they are somewhat practical, you really want perfect forward secrecy so they at least have to break a classically hard problem _every time_, which is unlikely with home-rolled RSA systems.

3. If you do care about post-quantum KEX (because your information needs to be secret for longer than you can count on quantum computers not being practical), we have faster alternatives, like SIDH.

Key sizes are an attractive subject for bikeshedding. You can endlessly argue about whether better performance or stronger theoretical brute force resistance (e.g. billion years vs million years to crack) is more important.

And yet, it is a silly thing to care about. Read the article, it does not even mention this topic really.

It's all about implementation vulnerabilities, and how RSA is fundamentally resistant to correct implementation (requires padding, etc)