Using a large nonce is possible but would add protocol overhead, and we intend ZeroTier to be a very low-overhead high performance protocol
No?
"Large" in the context of nonces means "larger than the headroom GCM provides". To get to a place where you can safely use random nonces, you're talking about just a couple extra bytes.
This is neither here nor there, since the actual problem this system has is a marketing decision to simultaneously comply with FIPS and use a nonce-based AEAD (which means, in practice, using GCM). But "larger nonce" is, I think, the general "right answer" to this problem, and the logic used here is alarming.
I had the same thought, but doesn't a larger nonce simply decrease the chance for a duplicate nonce? Even if the chance is decreased to practically-impossible-to-duplicate levels, I could see the thought process being "if we're going to have to roll our own implementation to change the nonce size anyway, we might as well make an implementation that is provably impossible to suffer security issues from a duplicate nonce rather than one that is just immensely unlikely".
I'm not sure if that's really the right choice, but I could at least see that being their reasoning, especially if they're going for FIPS certification which maybe (correct me if I'm wrong) would care about something being provably impossible rather than just provably unlikely?
(disclaimer: my crypto knowledge is fairly surface level and I'm making this comment in a genuine attempt to learn)
It decreases the chance for a duplicate nonce in somewhat the same sense as increasing key sizes decreases the chance of a guessed key. In cryptography, past some threshold, you get to rely on probability.
Why? I agree that a larger nonce would be better and that's possible, but even with a larger nonce not having sudden total compromise of authentication on nonce duplication would be a good thing would it not?
Even with larger nonces/IVs nonce reuse can still be an issue. If you store your counter/seed, storage can be corrupted. If you store your counter/seed, your VM can be cloned creating an exact copy of your counter/seed. If you rely on system entropy you can have entropy issues. The latter is fairly common on small and embedded devices including a ton of ARM boards that are on the market. I have actually seen cheapo ARM boards that ship with kernels where /dev/urandom outputs the same bits at boot every time. I imagine it's a combination of disabling every ad-hoc entropy source option in the kernel parameters (because code size!) combined with no non-volatile clock and no hardware entropy source and a very deterministic single in-order core.
Sudden death properties are a footgun and I'm a little surprised that constructions with this property have become the standard. Increasing the size of the nonce/IV just makes the footgun's trigger less squirrely.
This post (I'm the author) is just research notes posted for feedback, not a final design that is shipping. (I edited the post and added a disclaimer just in case people get confused about that.) My goals are four-fold: (1) to avoid sudden death properties entirely, (2) to be fast (on modern hardware with AES acceleration, which pretty much all targets where performance matters), (3) to be potentially FIPS-certifiable if I plug in FIPS libraries/modules for my primitives, and (4) to avoid adding more packet overhead if possible. My thought is that if (1) is achievable then (4) is also achievable.
<rant>
I really find the fear-mongering around crypto to be counterproductive. This post is just an idea, and the problem it is attempting to address is a real one. No, I don't like FIPS either, but I do like making money and numerous large clients do require it. So why not research ways to be FIPS compliant and be better than the average FIPS-compliant (stock AES-GCM with sudden death footgun) implementation? Why is that goal alarming?
Every time I discuss crypto I get people who just chime in with "don't write crypto, just use standard stuff." (I do agree that it's best to use standard stuff if it meets all your goals, that's not the point.)
What does saying that actually accomplish?
The people who really shouldn't write crypto will ignore it because they think they know more than they really know (or their boss is telling them to). The people who should write crypto will ignore it because it doesn't apply to them. The only people who will follow those kinds of admonitions are the people who don't know crypto and know they don't know but want to learn, and they'll be discouraged from doing so.
I learned about crypto because I realized it was hard, ignored this kind of advice, and read and listened to people who did understand it. When I ask questions about crypto or post ideas for feedback I've learned to only pay attention to replies that contain specific information or point out actual specific issues or flaws in a design. I ignore hand-wavey fear mongering that contains no actual content, and I'd encourage others who are interested in learning about crypto or anything else to do the same.
The point of the larger nonce is to allow safe use of random nonces. You don't do a larger nonce and then record nonces. Among randomized AEADs there seem to be three main strategies for security:
1. Nonces large enough that you can safely use random nonces (XSalsa being the best example).
2. Stateful nonces, such as in systems where the nonce is tied to another protocol, or recorded in non-volatile storage.
3. NMR systems where the nonce isn't necessarily large enough to safely use randomly, but the system doesn't fail catastrophically on the rare occasions they collide.
If you're trying to do cryptography on systems with no functioning random number generator, my presumption is you have bigger problems than which AEAD you're using.
I don't have much of a stake in this story. To the extent I do, I guess what I'm here to say is:
* "Performance" and "overhead" aren't good reasons to use a smaller nonce with an AEAD.
* FIPS is bad, and a requirement to be FIPS-compliant will ultimately harm the security of a cryptosystem.
That's it.
You will better answers on Crypto Stack Exchange than on HN, though.
3. NMR systems where the nonce isn't necessarily large enough to safely use randomly, but the system doesn't fail catastrophically on the rare occasions they collide.
That's what I'm interested in, yes, though making the nonce bigger is also on the table. Ideally I'd like to do both.
If you're trying to do cryptography on systems with no functioning random number generator, my presumption is you have bigger problems than which AEAD you're using.
We aren't really trying to do that, but our stuff runs on a ton of devices and we want to maximize its robustness across that device population. If someone puts it on a device with a crappy random source their security will be impacted but we wouldn't mind minimizing that impact if possible.
* FIPS is bad, and a requirement to be FIPS-compliant will ultimately harm the security of a cryptosystem.
I agree that FIPS sucks. Bureaucratic requirements arounds security suck in general since they perpetuate a box-checking CYA mentality while hamstringing real security measures.
Unfortunately money doesn't suck and bureaucratic organizations control most of the money on this planet. Reality is what it is.
You will better answers on Crypto Stack Exchange than on HN, though.
Agreed. I didn't post this here, someone else did. Crypto Stack Exchange is very good in my experience. It seems to have taken over the niche from the old Usenet crypto groups.
BTW I also do like WireGuard and if ZeroTier were redesigned today we'd consider the Noise framework it's based upon. None of that stuff existed when the design was originally made. As it stands we have a large user-base so backward compatibility matters and our goals and constraints are a little different from WG but we would like to evolve toward better crypto that is closer to what Noise accomplishes.
This is all fine. I just wouldn't want to see the meme established that safe nonce sizes are somehow detrimental to performance or create too much overhead, which is what the post I'm responding to said.
If someone takes that as advice they shouldn't be writing crypto, which means they'll probably both ignore your better advice and screw it up in ways far worse than using a small IV. :)
I don't understand. People shouldn't be writing crypto, that is true, if only to avoid being called "harebrained" on Crypto Stack Exchange by Squeamish Ossifrage. :)
It's hard for me to really engage with anything you're saying, because there are so many layers of problematic to this. I'd prefer to focus my concern on the decision to comply with FIPS, rather than trying to contort my take to some weird box in which unreasonable constraints become reasonable because FIPS says they're reasonable.
In a serious system, you'd either use AES-GCM-SIV, for its NMR property, or (much more likely) XChapoly, for its wide random nonce. OR, you'd have a "FIPS" mode that, like, just composed CTR with HMAC, rather than sticking yourself with GCM's weird nonce limitation. But you've apparently decided to simultaneously support FIPS and roll your own mode to squeeze out a better cycle count.
If there's so much money on the line, just get your design reviewed. Honestly, if you build with cryptography and that cryptography isn't simply Nacl, you should be doing that regardless. Like Nate Lawson used to tell me: you should budget 10x on verification what you do for implementation in a cryptosystem. Are you meeting that standard? I wouldn't know. (Nor, in fairness, would I be qualified to do verification work on a new authenticated encryption mode).
Your advice is good in most circumstances, and may end up being what we do.
In any case the mode I cooked up has after a few minor tweaks essentially converged with AES-(CMAC|PMAC)-SIV but with GMAC in the MAC slot and with an extra AES-ECB (AES as a 128-bit keyed hash) step after GMAC to make it into a proper PRF. If that's the case then it seems that the AES-SIV work and papers apply.
I was reading about AES-GCM-SIV and it's unfortunate that they decided to use a new MAC digest function called POLYVAL instead of GHASH/GMAC. If they'd re-used GHASH/GMAC as-is it's possible that AES-GCM-SIV could be described in terms of GMAC and AES-CTR and therefore could pass FIPS. I guess nobody but people trying to sell to certain parties cares about FIPS, which is probably as it should be because FIPS sucks.
Edit: it looks like POLYVAL is GHASH optimized for little-endian machines, so I see the rationale. Still too bad. They missed a bureaucracy-hacking opportunity.
Comments
Using a large nonce is possible but would add protocol overhead, and we intend ZeroTier to be a very low-overhead high performance protocol
No?
"Large" in the context of nonces means "larger than the headroom GCM provides". To get to a place where you can safely use random nonces, you're talking about just a couple extra bytes.
This is neither here nor there, since the actual problem this system has is a marketing decision to simultaneously comply with FIPS and use a nonce-based AEAD (which means, in practice, using GCM). But "larger nonce" is, I think, the general "right answer" to this problem, and the logic used here is alarming.
I had the same thought, but doesn't a larger nonce simply decrease the chance for a duplicate nonce? Even if the chance is decreased to practically-impossible-to-duplicate levels, I could see the thought process being "if we're going to have to roll our own implementation to change the nonce size anyway, we might as well make an implementation that is provably impossible to suffer security issues from a duplicate nonce rather than one that is just immensely unlikely".
I'm not sure if that's really the right choice, but I could at least see that being their reasoning, especially if they're going for FIPS certification which maybe (correct me if I'm wrong) would care about something being provably impossible rather than just provably unlikely?
(disclaimer: my crypto knowledge is fairly surface level and I'm making this comment in a genuine attempt to learn)
It decreases the chance for a duplicate nonce in somewhat the same sense as increasing key sizes decreases the chance of a guessed key. In cryptography, past some threshold, you get to rely on probability.
Why? I agree that a larger nonce would be better and that's possible, but even with a larger nonce not having sudden total compromise of authentication on nonce duplication would be a good thing would it not?
Even with larger nonces/IVs nonce reuse can still be an issue. If you store your counter/seed, storage can be corrupted. If you store your counter/seed, your VM can be cloned creating an exact copy of your counter/seed. If you rely on system entropy you can have entropy issues. The latter is fairly common on small and embedded devices including a ton of ARM boards that are on the market. I have actually seen cheapo ARM boards that ship with kernels where /dev/urandom outputs the same bits at boot every time. I imagine it's a combination of disabling every ad-hoc entropy source option in the kernel parameters (because code size!) combined with no non-volatile clock and no hardware entropy source and a very deterministic single in-order core.
Sudden death properties are a footgun and I'm a little surprised that constructions with this property have become the standard. Increasing the size of the nonce/IV just makes the footgun's trigger less squirrely.
This post (I'm the author) is just research notes posted for feedback, not a final design that is shipping. (I edited the post and added a disclaimer just in case people get confused about that.) My goals are four-fold: (1) to avoid sudden death properties entirely, (2) to be fast (on modern hardware with AES acceleration, which pretty much all targets where performance matters), (3) to be potentially FIPS-certifiable if I plug in FIPS libraries/modules for my primitives, and (4) to avoid adding more packet overhead if possible. My thought is that if (1) is achievable then (4) is also achievable.
<rant>
I really find the fear-mongering around crypto to be counterproductive. This post is just an idea, and the problem it is attempting to address is a real one. No, I don't like FIPS either, but I do like making money and numerous large clients do require it. So why not research ways to be FIPS compliant and be better than the average FIPS-compliant (stock AES-GCM with sudden death footgun) implementation? Why is that goal alarming?
Every time I discuss crypto I get people who just chime in with "don't write crypto, just use standard stuff." (I do agree that it's best to use standard stuff if it meets all your goals, that's not the point.)
What does saying that actually accomplish?
The people who really shouldn't write crypto will ignore it because they think they know more than they really know (or their boss is telling them to). The people who should write crypto will ignore it because it doesn't apply to them. The only people who will follow those kinds of admonitions are the people who don't know crypto and know they don't know but want to learn, and they'll be discouraged from doing so.
I learned about crypto because I realized it was hard, ignored this kind of advice, and read and listened to people who did understand it. When I ask questions about crypto or post ideas for feedback I've learned to only pay attention to replies that contain specific information or point out actual specific issues or flaws in a design. I ignore hand-wavey fear mongering that contains no actual content, and I'd encourage others who are interested in learning about crypto or anything else to do the same.
</rant>
The point of the larger nonce is to allow safe use of random nonces. You don't do a larger nonce and then record nonces. Among randomized AEADs there seem to be three main strategies for security:
1. Nonces large enough that you can safely use random nonces (XSalsa being the best example).
2. Stateful nonces, such as in systems where the nonce is tied to another protocol, or recorded in non-volatile storage.
3. NMR systems where the nonce isn't necessarily large enough to safely use randomly, but the system doesn't fail catastrophically on the rare occasions they collide.
If you're trying to do cryptography on systems with no functioning random number generator, my presumption is you have bigger problems than which AEAD you're using.
I don't have much of a stake in this story. To the extent I do, I guess what I'm here to say is:
* "Performance" and "overhead" aren't good reasons to use a smaller nonce with an AEAD.
* FIPS is bad, and a requirement to be FIPS-compliant will ultimately harm the security of a cryptosystem.
That's it.
You will better answers on Crypto Stack Exchange than on HN, though.
That's what I'm interested in, yes, though making the nonce bigger is also on the table. Ideally I'd like to do both.
We aren't really trying to do that, but our stuff runs on a ton of devices and we want to maximize its robustness across that device population. If someone puts it on a device with a crappy random source their security will be impacted but we wouldn't mind minimizing that impact if possible.
I agree that FIPS sucks. Bureaucratic requirements arounds security suck in general since they perpetuate a box-checking CYA mentality while hamstringing real security measures.
Unfortunately money doesn't suck and bureaucratic organizations control most of the money on this planet. Reality is what it is.
Agreed. I didn't post this here, someone else did. Crypto Stack Exchange is very good in my experience. It seems to have taken over the niche from the old Usenet crypto groups.
BTW I also do like WireGuard and if ZeroTier were redesigned today we'd consider the Noise framework it's based upon. None of that stuff existed when the design was originally made. As it stands we have a large user-base so backward compatibility matters and our goals and constraints are a little different from WG but we would like to evolve toward better crypto that is closer to what Noise accomplishes.
This is all fine. I just wouldn't want to see the meme established that safe nonce sizes are somehow detrimental to performance or create too much overhead, which is what the post I'm responding to said.
If someone takes that as advice they shouldn't be writing crypto, which means they'll probably both ignore your better advice and screw it up in ways far worse than using a small IV. :)
I don't understand. People shouldn't be writing crypto, that is true, if only to avoid being called "harebrained" on Crypto Stack Exchange by Squeamish Ossifrage. :)
It's hard for me to really engage with anything you're saying, because there are so many layers of problematic to this. I'd prefer to focus my concern on the decision to comply with FIPS, rather than trying to contort my take to some weird box in which unreasonable constraints become reasonable because FIPS says they're reasonable.
In a serious system, you'd either use AES-GCM-SIV, for its NMR property, or (much more likely) XChapoly, for its wide random nonce. OR, you'd have a "FIPS" mode that, like, just composed CTR with HMAC, rather than sticking yourself with GCM's weird nonce limitation. But you've apparently decided to simultaneously support FIPS and roll your own mode to squeeze out a better cycle count.
If there's so much money on the line, just get your design reviewed. Honestly, if you build with cryptography and that cryptography isn't simply Nacl, you should be doing that regardless. Like Nate Lawson used to tell me: you should budget 10x on verification what you do for implementation in a cryptosystem. Are you meeting that standard? I wouldn't know. (Nor, in fairness, would I be qualified to do verification work on a new authenticated encryption mode).
Your advice is good in most circumstances, and may end up being what we do.
In any case the mode I cooked up has after a few minor tweaks essentially converged with AES-(CMAC|PMAC)-SIV but with GMAC in the MAC slot and with an extra AES-ECB (AES as a 128-bit keyed hash) step after GMAC to make it into a proper PRF. If that's the case then it seems that the AES-SIV work and papers apply.
I was reading about AES-GCM-SIV and it's unfortunate that they decided to use a new MAC digest function called POLYVAL instead of GHASH/GMAC. If they'd re-used GHASH/GMAC as-is it's possible that AES-GCM-SIV could be described in terms of GMAC and AES-CTR and therefore could pass FIPS. I guess nobody but people trying to sell to certain parties cares about FIPS, which is probably as it should be because FIPS sucks.
https://tools.ietf.org/html/rfc8452#page-17
Edit: it looks like POLYVAL is GHASH optimized for little-endian machines, so I see the rationale. Still too bad. They missed a bureaucracy-hacking opportunity.