I'm planning to spend my evening checking every other Ed25519 implementation I can find to see if this check is missing any where else in the open source ecosystem.
I found several libraries that simply didn't implement the check, but none that implemented in incorrectly in the same way as the vulnerability discussed above.
Did you also check all of the libraries that implement the check differently to libsodium? That's one problem with the near-universal cargo-culting of ref10, it never did any of the checking so everyone has to reinvent it themselves in different ways. It might be useful to have a single known-good check for both x25519 and ed25519 that people could integrate into their own ref10-derived code.
For people not familiar with the size of the mess we're in here, see https://hdevalence.ca/blog/2020-10-04-its-25519am/. There was another study published before then which found that no two implementations used the same checks, and none of them were compliant with RFC 8032, the alleged standard for Ed25519.
I've been iterating on sodium bindings in Lean4 for about four months, and now that I've gotten to Ristretto255 I can see why the author is excited about its potential. Ristretto is a tightly designed API that allows me to build arbitrary polynomials on Curve25519 and I've been having a blast tinkering and experimenting with it! If the author by chance reads this, just want to say thank you for your work!
The bindings are set and have a monadic interface, but there's some abstractions that still need refining/iterating: mostly I want to be able to formalize keyboard input and eventually build a tactic framework for zero-knowledge proofs.
Libsodium’s goal was to expose APIs to perform operations, not low-level functions. Users shouldn’t even have to know or care about what algorithms are used internally. This is how I’ve always viewed libsodium.
...
Over the years, people started using these low-level functions directly. Libsodium started to be used as a toolkit of algorithms and low-level primitives.
That is interesting to see the common fallacy of what we think users want versus what they really want.
The important point is to be able to recognize that and not coerce users into using your project only how you envisioned it and only like that. Some projects are failure on that count having switched on dictatorial direction on that aspect.
> The important point is to be able to recognize that and not coerce users into using your project only how you envisioned it and only like that. Some projects are failure on that count having switched on dictatorial direction on that aspect.
There is certainly a balance there. If every function inside your code is now considered part of your API contract, almost anything is a breaking change and you can basically forget about ever meaningfully refactoring that codebase.
Many times making things private or marking them as internal-only is the right call.
I'm not really intimate enough with libsodium to judge if they made the right cut there or not in hindsight.
I wrote a C++ implementation of the Framework for Integrated Test (FIT) called CeeFIT, and I was really proud of the way it registered fixtures at compile time.
Anyhow, I was surprised that more than one user was using CeeFIT as a sort of batch runner for C++ code, feeding in rows tabular data and executing it against their code. There were a couple bugs I had to fix to support their use cases.
Some of the most successful products were originally intended for a completely different use case. R7 rockets, Viagra, Hugging Face. The ability to pivot - and to recognize when to pivot - is what makes or breaks.
Subtle but important bug. This is a good example of how “is valid” checks in crypto are rarely as simple as they sound. Accepting points outside the prime-order subgroup can quietly undermine higher-level assumptions, even if no immediate exploit is obvious. Also a reminder that low-level primitives tend to be reused far more widely than intended, so small validation gaps can have surprisingly large blast radii.
Do note thought that X25519 and Ed25519 were designed so they wouldn’t need those checks at all. It’s only when you’re trying to design fancier protocols on top of Curve25519 or Edwards25519 that you can run into subgroup issues.
And for those use cases, I personally try my best to just reproject everything back into the prime order subgroup whenever possible. Monocypher has a number of such fancy functions:
The dirty functions explicitly produce public keys that cover the entire curve, so that random such keys are truly indistinguishable from random when converted with `crypto_elligator_rev()`. But instead of just removing the clamp operation, I instead add random low-order point, so that when we later use the point in an X25519 key exchange, the shared secret is exactly the same as it would have been for a genuine X255119 key.
That’s where I thank DJB for designing a key exchange protocol that project the shared secret to the prime order subgroup, even when the public key it processes is not. The original intent may have been to make checks easier (low order keys all end up yielding zero), but a nice side effect is how it enabled a nice API for Mike Hamburg’s Elligator2.
> Accepting points outside the prime-order subgroup can quietly undermine higher-level assumptions, even if no immediate exploit is obvious.
If on the other hand we can prove that all computed results are low-order-component-independent (as is the case for X25519), then we know for sure we’re safe. In the end, Ristretto is only really needed when we can’t tweak the protocol to safely reproject to the prime order subgroup.
Don’t get me wrong, having a prime order group abstraction does help. But if someone is qualified to design a protocol that may require this, they’re qualified to try and make it work with a non-trivial cofactor as well — that, or prove it cannot be done.
I work for a big company (Apple) but I have no idea who Frank is, nor how to sponsor them; and even if I knew them and how to sponsor them, the money would come directly from my pocket instead of Apple’s banking account.
If libsodium is useful to you, please keep in mind that it is maintained by one person, for free, in time I could spend with my family or on other projects. The best way to help the project would be to consider sponsoring it, which helps me dedicate more time to improving it and making it great for everyone, for many more years to come.
Frank does great work that is critical to many businesses, and should get funded to do it professionally.
However, donating money to an open collective is prohibitively hard for most big companies. Maybe the world should be different (or maybe not, since it would be easy for employees to embezzle money if they could direct donations easily), but that's how it works currently.
AFAICT, there is also no fiscal sponsor, so the donation matching suggested in a sister comment won't apply.
This is why Geomys (https://geomys.org) works the way it does, and why it has revenue (ignoring the FIPS and tlog sides of the business) which is 30-50x of some GitHub Sponsors "success stories": we bill in a way that's compatible with how companies do business, even if effectively we provide a similar service (which is 95% focused on upstream maintenance, not customer support).
I am not saying it's for everyone, or that Frank should necessarily adopt this model, or that it's the only way (e.g. the Zig foundation raises real amounts of money, too), but I find it frustrating to see over and over again the same conversation:
- "Alice does important maintenance work, she should get professionally funded for it!"
- "How does Alice accept/request funding?"
- "Monthly credit card transactions anchored at $100/mo that are labeled donations"
- no business can move professional amounts of money that way
- "Businesses are so short-sighted, it's a tragedy of the commons!"
Anyone who solicits donations should also sell overpriced books of some sort, because it’s often very easy to get even a $500 book approved as an expense where a $5 “donation” causes hell.
With the year prominently displayed, i.e. "20XX Edition", to reflect when it was current. To help people track how long it has been since they dona-bought their last copy. And so purchase documentation explains repeat purchases.
Given the increasing obviousness that there's functionally no oversight of NGOs and government funding, perhaps we just need some NGOs and get government grants for these critical services.
While it might be frustrating to see non-viable options presented as ways to fund critical FOSS, it's even more frustrating to see blame effectively being placed on the maintainer; particularly because, if companies like Apple really wanted to fund this work, I'm pretty sure they could figure something out.
Anyway, looking at the model you propose, it seems like the main difference is that Frank just doesn't explicitly say "you can retain my services"? Is that all that's stopping Apple from contacting him and arranging a contract?
> if companies like Apple really wanted to fund this work, I'm pretty sure they could figure something out.
Having spent the last ~6 years in big tech consistently frustrated by the rigidity of the processes and finding clever ways to navigate (see: wade through the bullshit), this isn’t as easy as you’d hope. The problem is that someone has to spend a non-trivial amount of time advocating internally for something like this (a “non-standard process”) which generally means asking pinging random people across finance, procurement, and legal how to deal with it and 99% of people will just throw up their hands (especially in this case because they don’t understand the importance of it). If things don’t fit a mold in these big companies, they fall into the event horizon and are stretched out to infinity.
Couldn’t you just go up your chain to the VP or whatever and use their backing / negotiating at the VP level to organize? It might not work for random projects but if Apple is using libsodium for security this could presumably be pitched as an investment into their own software supply chain.
Filippo is another maintainer, of extremely similar open source software with entirely the same customer base, offering (important) advice to a peer, so I don't think policing his tone is helpful here.
I know who he is and what he does. I think we probably disagree on whether that makes the comment in better or worse taste.
Otherwise, I agreed with him, and am genuinely curious whether the stopping factor here is maintainers like Frank simply not saying "you can email me to retain my services"
> if companies like Apple really wanted to fund this work, I'm pretty sure they could figure something out
A reminder that companies are not a hive mind.
Many people at Apple surely would love to funnel piles of money to open source. Maybe some of them even work in the Finance or Procurement or Legal departments. But the overwhelming majority of Apple’s procurement flow is not donations, and so it is optimized for the shape of the work it encounters.
I bet there are plenty of people working at Chick-fil-A who wish it was open on Sundays. But it’s not ~“blaming the user” to suggest that as it stands, showing up on Sunday is an ineffective way to get chicken nuggets.
The idea that donations are the only way they could fund this work is what I was talking about. I'm sure Apple has various contractors and other forms of employees.
It's like suggesting that Chic-Fil-A really does want to open on Sunday, but the only thing stopping them is customers not telling them they want it open on Sunday.
If you donate via GitHub Sponsors to https://github.com/jedisct1 from an individual / personal account GitHub won't take a cut (or pays for it from their own purse) for any credit card processing fees.
Maybe you don't know this but Apple has a donation-matching program. If you make donations to non-profits through some special internal mechanism, the company will send a donation of equal value (up to some limit). If I recall correctly the limit is 30K USD per person.
"When you give money to an eligible organization, we’ll match your donations one-for-one, so your $1 has the impact of $2. And if you choose to donate your time, we’ll contribute $25 for every hour you volunteer. Whether you donate time or money, Apple will match your contributions up to $10,000 a year."
Any non-profit, or just charitable non-profits (aka 501(c)(3))? Unfortunately, the US does not consider producing open source software to be charitable activity.
I'm planning to spend my evening checking every other Ed25519 implementation I can find to see if this check is missing any where else in the open source ecosystem.
If you didn't receive an email from me, either your implementation isn't listed on https://ianix.com/pub/ed25519-deployment.html, I somehow missed it, or you're safe.
For people not familiar with the size of the mess we're in here, see https://hdevalence.ca/blog/2020-10-04-its-25519am/. There was another study published before then which found that no two implementations used the same checks, and none of them were compliant with RFC 8032, the alleged standard for Ed25519.
The bindings are set and have a monadic interface, but there's some abstractions that still need refining/iterating: mostly I want to be able to formalize keyboard input and eventually build a tactic framework for zero-knowledge proofs.
The important point is to be able to recognize that and not coerce users into using your project only how you envisioned it and only like that. Some projects are failure on that count having switched on dictatorial direction on that aspect.
There is certainly a balance there. If every function inside your code is now considered part of your API contract, almost anything is a breaking change and you can basically forget about ever meaningfully refactoring that codebase.
Many times making things private or marking them as internal-only is the right call.
I'm not really intimate enough with libsodium to judge if they made the right cut there or not in hindsight.
Anyhow, I was surprised that more than one user was using CeeFIT as a sort of batch runner for C++ code, feeding in rows tabular data and executing it against their code. There were a couple bugs I had to fix to support their use cases.
I was just happy to have users.
And for those use cases, I personally try my best to just reproject everything back into the prime order subgroup whenever possible. Monocypher has a number of such fancy functions:
The dirty functions explicitly produce public keys that cover the entire curve, so that random such keys are truly indistinguishable from random when converted with `crypto_elligator_rev()`. But instead of just removing the clamp operation, I instead add random low-order point, so that when we later use the point in an X25519 key exchange, the shared secret is exactly the same as it would have been for a genuine X255119 key.That’s where I thank DJB for designing a key exchange protocol that project the shared secret to the prime order subgroup, even when the public key it processes is not. The original intent may have been to make checks easier (low order keys all end up yielding zero), but a nice side effect is how it enabled a nice API for Mike Hamburg’s Elligator2.
> Accepting points outside the prime-order subgroup can quietly undermine higher-level assumptions, even if no immediate exploit is obvious.
If on the other hand we can prove that all computed results are low-order-component-independent (as is the case for X25519), then we know for sure we’re safe. In the end, Ristretto is only really needed when we can’t tweak the protocol to safely reproject to the prime order subgroup.
Don’t get me wrong, having a prime order group abstraction does help. But if someone is qualified to design a protocol that may require this, they’re qualified to try and make it work with a non-trivial cofactor as well — that, or prove it cannot be done.
Hope that helps.
However, donating money to an open collective is prohibitively hard for most big companies. Maybe the world should be different (or maybe not, since it would be easy for employees to embezzle money if they could direct donations easily), but that's how it works currently.
AFAICT, there is also no fiscal sponsor, so the donation matching suggested in a sister comment won't apply.
This is why Geomys (https://geomys.org) works the way it does, and why it has revenue (ignoring the FIPS and tlog sides of the business) which is 30-50x of some GitHub Sponsors "success stories": we bill in a way that's compatible with how companies do business, even if effectively we provide a similar service (which is 95% focused on upstream maintenance, not customer support).
I am not saying it's for everyone, or that Frank should necessarily adopt this model, or that it's the only way (e.g. the Zig foundation raises real amounts of money, too), but I find it frustrating to see over and over again the same conversation:
- "Alice does important maintenance work, she should get professionally funded for it!"
- "How does Alice accept/request funding?"
- "Monthly credit card transactions anchored at $100/mo that are labeled donations"
- no business can move professional amounts of money that way
- "Businesses are so short-sighted, it's a tragedy of the commons!"
Anyway, looking at the model you propose, it seems like the main difference is that Frank just doesn't explicitly say "you can retain my services"? Is that all that's stopping Apple from contacting him and arranging a contract?
Having spent the last ~6 years in big tech consistently frustrated by the rigidity of the processes and finding clever ways to navigate (see: wade through the bullshit), this isn’t as easy as you’d hope. The problem is that someone has to spend a non-trivial amount of time advocating internally for something like this (a “non-standard process”) which generally means asking pinging random people across finance, procurement, and legal how to deal with it and 99% of people will just throw up their hands (especially in this case because they don’t understand the importance of it). If things don’t fit a mold in these big companies, they fall into the event horizon and are stretched out to infinity.
Otherwise, I agreed with him, and am genuinely curious whether the stopping factor here is maintainers like Frank simply not saying "you can email me to retain my services"
A reminder that companies are not a hive mind.
Many people at Apple surely would love to funnel piles of money to open source. Maybe some of them even work in the Finance or Procurement or Legal departments. But the overwhelming majority of Apple’s procurement flow is not donations, and so it is optimized for the shape of the work it encounters.
I bet there are plenty of people working at Chick-fil-A who wish it was open on Sundays. But it’s not ~“blaming the user” to suggest that as it stands, showing up on Sunday is an ineffective way to get chicken nuggets.
It's like suggesting that Chic-Fil-A really does want to open on Sunday, but the only thing stopping them is customers not telling them they want it open on Sunday.
https://www.apple.com/careers/us/life-at-apple/benefits.html
But it is on a case by case basis, and it does take work to get the IRS to accept it.