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

21–30 of 92 posts

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

#21

Post by pantalaimon »

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.

That looks really neat, but I still don't understand what firedancer actually is - what is a validator client for Solana and why does it need it's own crypto library?

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

#22

Post by pantalaimon »

scrapheap wrote: post #9
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 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…

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

Azure Devops is a big one.

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

#23

Post by vladms »

posnet wrote: post #13
4gotunameagain wrote: post #12

Earlier quoted context omitted.

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.

The greatest minds of our generation spend their time thinking about how to: - make people click on ads - make trading algos faster - replace human artists - build more efficient killing machines - destroy any remaining concept of privacy

This directly implies that all the people that did useful stuff (improving cancer survivability, new vaccines, renewable energy, and others) are all "below" the "greatest minds of our generation".

Not to mention it also suggests there is a way to "compare" minds. I would not choose myself to do somethings, but that does not mean I despise automatically people choosing to.

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

#24

Post by upofadown »

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…

Another article from the same blog about optimizing RSA:

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

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

#25

Post by loudmax »

scrapheap wrote: post #9
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 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…

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.

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

#26

Post by vitus »

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

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

#27

Post by homebrewer »

loudmax wrote: post #25
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…

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.

Use shell autocomplete. Even `bash-completion` suggests arguments for the key type these days:

  $ ssh-keygen -t 
  dsa   ecdsa   ecdsa-sk   ed25519   ed25519-sk  rsa
`-sk` is short for "security key" if memory serves me right, and is used with FIDO2 hardware tokens.

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

#28

Post by SEJeff »

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.

It’s an optimization in hashing algorithms that is around twice as fast as the ones Amazon is posting in thus article for the same eliptic curves.

If the Amazon improvements are hacker news worthy (they are) this seems reasonable contextually.

Also, I worked for Jump for almost 12 years :)

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

#30

Post by SEJeff »

pantalaimon wrote: post #21
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.

That looks really neat, but I still don't understand what firedancer actually is - what is a validator client for Solana and why does it need it's own crypto library?

It’s a new from scratch implementation of a validator for Solana the fastest blockchain by several orders of magnitude. The slowest part is signature verification so they sped up hashing to improve performance of the entire system.

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.

Post reply on HN