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

51–60 of 92 posts

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

#51

Post by inopinatus »

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 see they learned clang’s dirty little secret over intrinsics viz. that in producing the IR it deviates (sometimes dramatically when AVX-512 is concerned) from the documented opcodes and the results are inevitably detrimental.

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

#52

Post by dhx »

tptacek wrote: post #41
dhx wrote: post #40

Earlier quoted context omitted.

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.

As an example, the Amazon implementation doesn't refer to gcc's[1] and clang's[2] "zero_call_used_regs" to zeroise CPU registers upon return or exception of functions working on crypto secrets. OpenSSL doesn't either.[3] firedancer _does_ use "zero_call_used_regs" to allow gcc/clang to zeroise used CPU registers.[9]

As another example, the Amazon implementation also doesn't refer to gcc's "strub" attribute which zeroises the function's stack upon return or exception of functions working on crypto secrets.[4][5] OpenSSL doesn't either.[3] firedancer _does_ use the "strub" attribute to allow gcc to zeroise the function's stack.[9]

Is there a performance impact? [6] has the overhead at 0% for X25519 for implementing CPU register and stack zeroisation. Compiling the Linux kernel with "CONFIG_ZERO_CALL_USED_REGS=1" for x64_64 (impacting all kernel functions) was found to result in a 1-1.5% performance penalty.[7][8]

[1] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...

[2] https://clang.llvm.org/docs/AttributeReference.html#zero-cal...

[3] https://github.com/openssl/openssl/discussions/24321

[4] https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Type-At...

[5] https://gcc.gnu.org/onlinedocs/gcc/Stack-Scrubbing.html

[6] https://eprint.iacr.org/2023/1713.pdf

[7] https://www.phoronix.com/review/zero-used-regs/5

[8] https://lore.kernel.org/lkml/20210505191804.4015873-1-keesco...

[9] FD_FN_UNSANITIZED: https://github.com/firedancer-io/firedancer/blob/master/src/...

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

#53

Post by SEJeff »

scrlk wrote: post #38
SEJeff wrote: post #30

Earlier quoted context omitted.

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.

Rumors of Jump’s demise are greatly exaggerated. Check the torrent of firedancer talks at Solana Breakpoint literally next week and decide yourself.

Folks have said jump is gonna die for 20+ years. They’ve been around 30ish…

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

#54

Post by ShroudedNight »

webXL wrote: post #49
syzygyhack wrote: post #11

Earlier quoted context omitted.

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?

The trough of disillusionment carved out by grifters burning the peat of enthusiasm unsustainably.

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

#55

Post by dlgeek »

jonmon6691 wrote: post #50

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.

The industry is moving to a hybrid that mixes classic crypto (including ECC) with post-quantum crypto. AWS has even turned this on in some places - https://aws.amazon.com/about-aws/whats-new/2022/03/aws-kms-a... from 2022 and https://docs.aws.amazon.com/kms/latest/developerguide/pqtls.... for some details.

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

#56

Post by SEJeff »

webXL wrote: post #49
syzygyhack wrote: post #11

Earlier quoted context omitted.

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?

I didn’t use it because I didn’t find it relevant. They’re using hashing and EC algorithms and they’re improving them.

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

#57

Post by tptacek »

saghm wrote: post #48
stouset wrote: post #8

Earlier quoted context omitted.

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

Counterpoint: it's not OK to skip the math with cryptography. You may not need to power through all of Silverman's curve book (though: I don't know for sure that's true, which is why I don't call myself a cryptography engineer), but you have to get as deep into the math as you can in order to safely use cryptographic algorithms.

If you're math-avoidant, stick with high-level abstractions like NaCL and TLS. There's nothing wrong with that!

A professor talking about and demonstrating cryptography at the level of individual algorithms is doing their class a disservice if they say "none of the math will be on the test". The algorithms are enough to put something together that seems like it works; the math is what you need to find out if your resulting system actually does work. It's where many of the fun bug classes live.

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

#58

Post by jonmon6691 »

dlgeek wrote: post #55
jonmon6691 wrote: post #50

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.

The industry is moving to a hybrid that mixes classic crypto (including ECC) with post-quantum crypto. AWS has even turned this on in some places - https://aws.amazon.com/about-aws/whats-new/2022/03/aws-kms-a... from 2022 and https://docs.aws.amazon.com/kms/latest/developerguide/pqtls.... for some details.

Thanks I forgot about that. So if understand it right, the idea is to provide some insurance in the case that these relatively young algorithms are broken as they get exposed to more and more cryptanalysis

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

#59

Post by caned »

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…

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

For users that have AVX-512, which isn't widely available (AMD Zen 4 / Zen 5, Sapphire Rapids)...

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

#60

Post by adgjlsfhk1 »

jonmon6691 wrote: post #50

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.

No one other than NIST is recommending phasing out pre-quantum crypto. Everyone else is using a combination of pre-quantum and post-quantum because trust in the security and robustness of the post-quantum ecosystem is fairly low.
Post reply on HN