Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Better-performing “25519” elliptic-curve cryptography

amazon.science

Post reply on HN
Print view View original

41–50 of 92 posts

Re: Better-performing “25519” elliptic-curve cryptography

#41

Post by tptacek »

dhx wrote: post #40
electricshampo1 wrote: post #10

Earlier quoted context omitted.

Completely agree re: firedancer codebase. There is a level of thought and discipline wrt performance that I have never seen anywhere else.

It's much more than just performance they've thought about. Here are some of the secure programming practices that have been implemented: /* 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…

These are table stakes for core cryptographic code, and SOT crypto code --- like the Amazon implementation this story is about --- tend at this point all to be derived from formal methods.

Re: Better-performing “25519” elliptic-curve cryptography

#42

Post by tptacek »

vitus wrote: post #19
miki123211 wrote: post #15

Earlier quoted context omitted.

5. a lot of people (especially older people I suspect) think "RSA" when they hear "public key cryptography". 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.

This is likely in no small part due to CS education only really teaching the mechanics of RSA (modular arithmetic, Fermat's little theorem, etc), or at least, that still seems to be the case at Berkeley. I'd guess because elliptic curve crypto requires more advanced math to reason about (more advanced group theory, at least) and doesn't map as cleanly to existing concepts that non-math-major undergrads have. cryptopa…

We didn't even cover RSA until the original last set. It's a build-up. :)

Re: Better-performing “25519” elliptic-curve cryptography

#43

Post by devman0 »

Spooky23 wrote: post #18
scrapheap wrote: post #9

Earlier quoted context omitted.

> 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'l…

If you interact with government or some large entities that do business with government, they have to comply with FIPS 140-2, and cannot use ed25519.

ed25519 is in FIPS 186-5 which meets criteria (a) for Approved Security Functions in FIPS 140-2.

Re: Better-performing “25519” elliptic-curve cryptography

#44

Post by deathanatos »

vitus wrote: post #26
londons_explore wrote: post #17

Does 25519 suffer from key/data-dependant execution time? Is this implementation resistant to that? If it isn't, it's kinda a footgun which shouldn't be published for general use.

> Does 25519 suffer from key/data-dependant execution 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.…

> but the industry has been aware of timing attacks for decades such that this is table stakes for any crypto implementations.

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.)

Re: Better-performing “25519” elliptic-curve cryptography

#45

Post by saghm »

throw0101b wrote: post #34
loudmax wrote: post #25

Earlier quoted context omitted.

When I run `ssh-keygen`, I can remember the options `-t rsa` or `-t dsa`. I simply cannot remember the flag `-t ed25519`. I have to look it up every time. I just remember the flag as being vaguely similar the name of the monster robot from RoboCop.

> When I run `ssh-keygen` As of OpenSSH 9.5 the default has changed, so you don't have to specify anything: * ssh-keygen(1): generate Ed25519 keys by default. Ed25519 public keys are very convenient due to their small size. Ed25519 keys are specified in RFC 8709 and OpenSSH has supported them since version 6.5 (January 2014). * https://www.openssh.com/txt/release-9.5

Oh wow, I didn't know that one! I still manually type `-t ed25519` from muscle memory, I guess I don't have to now

Re: Better-performing “25519” elliptic-curve cryptography

#46

Post by saghm »

toast0 wrote: post #7
saghm wrote: post #3

My (probably naive) understanding is that 25519 already provided better performance than other algorithms used for similar purposes (e.g. RSA) when tuned for a roughly similar level of security; anecdotally, generating 2048-bit or larger RSA keys for me tends to be a lot slower than ed25519. At times I've run into places that require me to use RSA keys though (ironically, I seem to remember first experiencing this wi…

> My (probably naive) understanding is that 25519 already provided better performance than other algorithms used for similar purposes (e.g. RSA) when tuned for a roughly similar level of security; anecdotally, generating 2048-bit or larger RSA keys for me tends to be a lot slower than ed25519. My also naive (an possibly out of date) understanding is key generation is much faster in with ecc, and that signing is faste…

> 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.

Re: Better-performing “25519” elliptic-curve cryptography

#47

Post by toast0 »

4gotunameagain wrote: post #12
SEJeff wrote: post #5

The firedancer team at one of the better HFT firms wrote an AVX512 optimized implementation of ed25519 and X25519 that’s significantly faster than OpenSSL. 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.

So many manhours spent on finding better ways to shovel around money and pocket what falls from the cracks. 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.

It doesn't seem wasteful and unproductive, given that the result of the HFT industry is smaller bid/ask spreads (lowering costs for all trades) and payment for order flow which is the mechanism that eliminated retail commissions and provides price improvement on many retail trades. And even so, HFT firms are making money.

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.

Re: Better-performing “25519” elliptic-curve cryptography

#48

Post by saghm »

stouset wrote: post #8
saghm wrote: post #6

Earlier quoted context omitted.

I did say my understanding was probably naive; I didn't know the details to be able to assert anything beyond my own observation!

Yep, not faulting you at all! I too was surprised when I found out that it’s a straight 256-bit random value with a few bits masked.

I pretty quickly realized in college when learning about this stuff that the math was well over my head, and I shifted my focus more to understanding how to properly use cryptography rather than implement it (which turned out to be more important as a software engineer anyhow). In retrospect, I really appreciate how the professor I had in a security-focused course explicitly told us it was okay if we didn't understand the math and wouldn't be tested on it when going over how it worked.

Re: Better-performing “25519” elliptic-curve cryptography

#49

Post by webXL »

syzygyhack wrote: post #11
SEJeff wrote: post #5

The firedancer team at one of the better HFT firms wrote an AVX512 optimized implementation of ed25519 and X25519 that’s significantly faster than OpenSSL. 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.

I laughed a little at calling Firedancer contributors "a team at a HFT firm". 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.

What makes the “b-word” dirty?

Re: Better-performing “25519” elliptic-curve cryptography

#50

Post by jonmon6691 »

I'm assuming when they say that this improves user experience, that it implies the use case is primarily TLS. In which case store-now-decrypt-later attacks are already considered an urgent threat with regard to post quantum crypto. With FIPS 203 being released and Chrome is already using an implementation based on the draft standard, this seems like this algo (at least for TLS) should be on its way out.
Post reply on HN