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

31–40 of 92 posts

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

#31

Post by SEJeff »

electricshampo1 wrote: post #10
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.

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

That team is full of world experts in high performance computing.

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

#32

Post by appendix-rock »

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.

What do you work on?

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

#33

Post by throw0101b »

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…

I would think that the (non-EC) Diffie-Hellman would also be easy enough to teach as well: exponentials and discrete log problem aren't any/much complicated than explaining factorization.

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

#34

Post by throw0101b »

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.

> 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

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

#35

Post by almostgotcaught »

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.

I'll never be able to figure out what people get from repeating the same thing over and over. I've seen this same exact comment 1000 times on hn and I'm 100% sure you have too (indeed I believe the reason you repeat is because you've seen it and agree with it).

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

#36

Post by fefe23 »

Holy shit these claims are wild! It's not just a percent more performance here and there, the graphs look more like 50% more throughput on the same hardware (depending on the cpu architecture).

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.

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

#37

Post by justinwsmith »

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

The next paragraph makes a slightly stronger statement about its constant-time'ness:

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

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

#38

Post by scrlk »

SEJeff wrote: post #30
pantalaimon wrote: post #21

Earlier quoted context omitted.

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 f…

Off topic - is Firedancer going to survive Jump winding down its crypto arm?

Kanav left, they liquidated a huge staked ETH position a few months ago (+ a bunch of other coins), and the SEC/CFTC is all over them for the Terra Luna fiasco.

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

#39

Post by nly »

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.

A lot of slowness comes typically comes from wanting to avoid methods that enable side-channel timing attacks

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

#40

Post by dhx »

electricshampo1 wrote: post #10
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.

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 static allocation + clear local variable before exit (fd_ed25519_scalar_mul_base_const_time)
     - Clear registers via FD_FN_SENSITIVE[3]
     - C safety
  */
libsodium[4] implements similar mechanisms, and Linux kernel encryption code does too (example: use of kfree_sensitive)[5]. However, firedancer appears to better avoid moving secrets outside of CPU registers, and [3] explains that libraries such as libsodium have inadequate zeroisation, something which firedancer claims to improve upon.

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

Post reply on HN