https://github.com/firedancer-io/firedancer/pull/716
Ditto for sha256: https://github.com/firedancer-io/firedancer/pull/778
And sha512: https://github.com/firedancer-io/firedancer/pull/760
If you’re an optimization nerd, this codebase is wild.
Not that you are technically wrong, not at all, that's where Jump came from. It's just that this is all completely blockchain-driven optimization, but the b-word is so dirty now that we've gotta go back to using TradFi for the rep.
If the Amazon improvements are hacker news worthy (they are) this seems reasonable contextually.
Also, I worked for Jump for almost 12 years :)
What a wasteful and unproductive enterprise, considering the vast majority of the devised improvements never see the public eye.
Still, impressive work. Imagine if those brilliant minds behind this were focused somewhere else.
- make people click on ads
- make trading algos faster
- replace human artists
- build more efficient killing machines
- destroy any remaining concept of privacy
It might not seem like real work, but making money by reducing costs of market participants sounds like a good thing. I admit though, block trades might be harder now than before the rise of HFT.
If you could do warehousing/distributing/coordinating fresh foods in a way that reduced the difference in price between the farmer and the consumer and make money doing it, that would clearly be good work.
nb those abstractions do make sense when you can only afford to write a single implementation of the algorithm; then you're just talking about a high level programming language. But they frequently fail to achieve their goal when you're writing a second implementation for the sole purpose of being faster.
/* All the functions in this file are considered "secure", specifically:
- Constant time in the input, i.e. the input can be a secret[2]
- Small and auditable code base, incl. simple types
- Either, no local variables = no need to clear them before exit (most functions)
- Or, only static allocation + clear local variable before exit (fd_ed25519_scalar_mul_base_const_time)
- Clear registers via FD_FN_SENSITIVE[3]
- C safety
*/
[1] https://github.com/firedancer-io/firedancer/blob/main/src/ba...
[2] https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic...
[3] https://eprint.iacr.org/2023/1713
[4] https://libsodium.gitbook.io/doc/internals#security-first
[5] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
They follow a first principles approach (the lead has a few physics degrees) and opted to speed up the cryptography. The beauty of this, despite the bad views on blockchain, is that they freaking sped up the cryptography of commonly used algorithms more than anything open or closed source that I personally am aware of.
It’s a win in cryptography, much like this Amazon post is, except it’s slower than the firedancer implementation.
If this further improvement becomes widely used, it would be interesting to see if it's enough to tip the scales towards ed25519 being more of the de facto "default" ssh key algorithm. My experience is that a decent number of people still use RSA keys most of the time, but I don't feel like I have nearly enough of a sample size to conclude anything significant from that.
I wouldn't be surprised if a lot of people still use RSA for SSH keys for one or more of the following reasons:
1. A lot of tutorials about generating SSH Keys were written before ed25519, so if they follow an old tutorial they'll probably be generating an RSA key.
2. Older versions of OpenSSH, that you'd find on CentOS 7 and below, would default to RSA if you didn't specify a key type when running ssh-keygen.
3. There are some systems out there that don't support ed25519, though they are becoming rarer. If you have to deal with those systems then you're forced to use RSA (at least for that system).
4. Some of us have been using SSH keys from way before OpenSSH add support for ed25519 keys in 2014, so any long lived SSH keys won't be ed25519 keys (wow, ed25519 has now been about in OpenSSH for over 10 years).
I'm in my twenties and still have that reaction. I know elliptic curves exist, I even sort-of-kind-of have an awareness of how they work, but if I was asked to name one cryptosystem that used public and private keys, I'd definitely say RSA first and not elliptic curves.
Azure Devops is a big one.
I just remember the flag as being vaguely similar the name of the monster robot from RoboCop.
That’s not really anecdotal. Generating an ed25519 key is barely more than generating a random 256-bit value. Generating an RSA key is significantly more work.
My also naive (an possibly out of date) understanding is key generation is much faster in with ecc, and that signing is faster too, but verifying is faster for rsa. So switching from a RSA to an ECC server certificate saves bytes on the wire, because keys are smaller, and saves server cpu because signing is faster, but may increase client cpu because verification is slower. The byte savings may make up for the increase in cpu though.
Interesting! I wonder if this new algorithm is intended to help with that. I'm super curious if the smaller payload does indeed make a difference (with the current algorithm) like you mention; I know that with databases and filesystems, compression is commonly used to shift the balance from I/O to CPU due to disk writes being slow (with reduced storage size being a side benefit but not usually the main motivation), but I also know that cryptographic verification being too slow can be an anti-feature if it makes brute forcing feasible, so the amount of CPU work needed might be pretty high still.
* https://www.amazon.science/blog/formal-verification-makes-rs...
RSA signature verification is already very fast and TLS doesn't use RSA for encryption anymore so the problem reduces to optimizing signing operations.
Is this implementation resistant to that?
If it isn't, it's kinda a footgun which shouldn't be published for general use.
That doesn't mean that this implementation doesn't have timing attacks, but the implementors claim they chose mechanisms which should be constant-time.
I mean, when implemented naively, yes, but the industry has been aware of timing attacks for decades such that this is table stakes for any crypto implementations.
From the article:
> We also do our best to execute the algorithms in constant time, to thwart side-channel attacks that infer secret information from the durations of computations.
https://github.com/awslabs/s2n-bignum (where most of the heavy lifting is done, per the article) further explicitly states that "Each function is moreover written in a constant-time style to avoid timing side-channels."
> Our implementations of x/Ed25519 are designed with constant time in mind. They perform exactly the same sequence of basic CPU instructions regardless of the input values, and they avoid any CPU instructions that might have data-dependent timing.
When I see CVE-fests like — https://people.redhat.com/~hkario/marvin/ — … I just do not come away with that impression.
[Widely used] Cryptographic Rust crates offering "constant time" operations in "pure Rust" — but Rust has no primitives for doing constant time operations, so it's only through hopes and prayers that it might actually work, and with no guarantee anywhere that it actually should.
(Other, less timing attack related stuff, but e.g., major companies still not supporting anything beyond RSA.)
Really though? This mostly-untrue statement is the line that warrants adding hashtag #post-quantum-cryptography to the blogpost?
/?q X25519Kyber768Draft00: https://www.google.com/search?q=X25519Kyber768Draft00
That's pretty sweet. I'm currently using BoringSSL in a project as a supplement to OpenSSL (mostly because it is much easier to build for Windows users than requiring them to fiddle with msys2/vcpkg etc; the alternative is to rely on the Windows CNG API, but it lacks features like ed25519 support.) I wonder how much effort it would take to use aws-lc instead... Not that I'm that interested, BSSL is pretty good, but free performance and heavy automated verification is always nice :)
Related: one of the authors of this post, John Harrison, wrote a really good book about automated theorm proving about 15 years ago while working on floating point verification at Intel -- there's still no other book quite like this one, I think https://www.cl.cam.ac.uk/~jrh13/
Turns out someone else has already tried: https://github.com/aws/aws-lc/issues/1827
My immediate fear was that they optimized away the security features like absence of timing side channels, but they say they still have those.
They also claim to have formal proof of correctness, which is even more amazing, because they are not doing it on a symbolic level but on a machine instruction level. Apparently they tought their reasoning system the semantics of all the CPU instructions used in the assembler implementation.
I'll still wait what djb has to say about this, but it looks freaking amazing to me.