Hacker News new | past | comments | ask | show | jobs | submit login
AES-GMAC-CTR (SIV) (zerotier.com)
74 points by LukeLambert on Sept 4, 2019 | hide | past | favorite | 45 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.


> the logic used here is alarming.

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.


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

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.


I do not represent an NVLAP lab, but I'd question whether this would pass strict muster for FIPS given IG A.5: https://csrc.nist.gov/csrc/media/projects/cryptographic-modu...

(Disclaimer: author of AES-GCM-SIV. Not casting shade here, it's a fair idea! But not sure about the specific FIPS claim.)


I'm not 100% sure either and am looking into it. FIPS is a rats nest and it may "depend." At this point I was just looking for basic feedback as to whether anyone could see any obvious problems. One person did suggest using a different AES key for each operation, which costs next to nothing and is probably good practice.

Edit: plan is to re-key often enough than plain GCM with 64-bit tags would be "fine" from a FIPS point of view. The goal here is to do better than the FIPS requirement by closing a potential attack vector.


Fascinating that FIPS not only permitted but basically encouraged them to roll their own crypto instead of using a standard, well-analyzed system. (They're being cautious about their approach but it's still more work to design something that's as safe as a known approach than to just use the known approach.)

I suspect that's the exact opposite of the intention behind FIPS....


FIPS is about the "correctness" of a particular set of functions (behaviors).

You are correct that part of FIPS is encouraging folks to use previous validated crypto modules instead of going from zero.

However you are not forced to do so - if you write your own crypto and pay to have it FIPS validated, more power to you - that's great. It is more competition.


FIPS is a double-edged sword in my experience. On one hand it does set a standard to keep total snake oil crypto out of government. On the other hand it often has the side effect of mandating worse and older crypto and slowing update cycles when there's a bug. When SSL bugs are discovered vulnerable SSL libraries tend to sit around for a lot longer on FIPS-controlled hosts because they have to wait for a FIPS-validated update.


FIPS also ,at least a decade ago, ruled out things like PFS because actually the federal goverent wanted to be able to audit past traffic.


Citation please. There are multiple standards that implement PFS in the FIPS specs.


Fair enough, the ones I was involved with implementing/complying with (FIPS 140-2) ruled out things like DH(E) key exchange.

We had to comply with that standard to sell to the federal government at the time.

Things may well have changed.


ECDHE is standard for FIPS these days.


This comment doesn't really say anything, does it? The point Geoff made stands.


No?

My point was that you are not actively blocked or "discouraged" from making your own crypto implementation and submitting it for FIPS validation.

Of course, that will be more expensive and time consuming than simply reusing a previously validated crypto module. So, you could perhaps call that "encouragement".... but the idea of FIPS is to provide some level of assurance to the consumer of said solutions.

But there are cases where you desire to control your own crypto.


Adam Langley also has a good primer post on AES-GCM-SIV:

https://www.imperialviolet.org/2017/05/14/aesgcmsiv.html


Obviously SIV is reviewed by people much more familiar with cryptanalysis than I am, but I am not sure how an IV based upon a hash of the message contents is any less likely to collide than an IV that is randomly generated?

Isn't the ideal case for a hash that two different inputs will generate outputs exactly as likely to collide as two random numbers?

[edit]

I found the RFC[1] and it explains it. In SIV mode, the inputs are a (Key, Nonce) just like AES-GCM, but the keys used internally are generated deterministically from the key and nonce, so that each nonce provided uses a different key for the AES primitive, and then uses a synthetically generated (from plaintext) IV as input to AES.

1: https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-05


SIV-type schemes use the message content to guard against accidental message IV duplication, which can occur for numerous reasons including bad random sources, loss of storage, or just a smaller IV. They use the message content and message IV to generate a synthetic IV that is message-dependent so a duplicated message IV has no effect (other than revealing message duplication if the messages happen to also be the same).


If the creators of Zerotier are here, could you consider doing a kickstarter or something to pay for getting a professional cryptographer to look at it?


Professional cryptographers will definitely look at it. Doing design research first.


I'm a zerotier user... And I hope that, beyond asking HN and SO, they'll let a professional cryptographer review their design as well!


Have you tried WireGuard? I used ZeroTier in the past (and OpenVPN before that) but found that WireGuard seemed to perform much better (more throughput, less CPU usage)


Wireguard is a (completely) different product. Wireguard is a vpn, where as zero tier is a way to define networks over a network. As they call it: an ethernet switch for planet earth. With centralized configuration. Sdn and more buzzwords. It is quite impressive. That said: you can do sort of vpn things with zerotier if you want to.


WireGuard has also been extensively studied, and more than one academic paper has been written validating it.


Being a layer 3 VPN makes Wireguard inappropriate for many scenarios for which Zerotier is used at least without layering something else on top of it which can significantly increase complexity and lower performance.


There’s also dsvpn which is an extremely simple vpn! The only bad part is that the code has no comments, but it is still auditable in a few hours due to the low amount of lines of code.


Oh, is that how that works? :)


It's a rather different beast, AFAIK. WireGuard works as an openvpn replacement, with a client-server architecture, while zerotier has no real idea of a server (beyond the zerotier controller, which is offered as a SaaS as well), there're just clients connecting between each other, and offers UDP hole punch, so you don't have to open ports and configure things like that.

THAT is ZT advantage.

EDIT: I got back to WireGuard after writing this comment, and I may be wrong. I may have misunderstood a lot about wireguard so far, I'll check it again soon.


Yes that would happen. Blogging and fishing for public comments is round one.


Round one should really be talking to an expert in the field with crypto. I'm concerned that Guy On SO may not be as thorough as your product really deserves.


I'd rather not waste a cryptographer's time with something that contains flaws that Guy On SO can spot. I do know enough about cryptography to generally tell if Guy On SO seems to know what they're talking about or not.


Whoa, using the MAC as the IV to AES? That's really neat, I had not considered that before


Why didn't they contact the authors of AES-SIV and AES-GCM-SIV to review their idea?


Because that would likely cost money, asking on SO costs literally nothing... And surely all appropriate expertise either read SO or their blog, so no problems here!

To be fair, I see nothing obviously wrong with their solution, it's their approach that concerns me.


> Because that would likely cost money

Yeah, maybe a flight and some expensive beers.

Most academic crypto guys are ecstatic at the thought of someone asking them prior to using their stuff wrong.


When I work with Faculty (teaching or research, tenured or not), they are very conscious of their image/reputation. It would look pretty bad for a researcher to "sign off" on something, only for flaws to be discovered.


> It would look pretty bad for a researcher to "sign off" on something, only for flaws to be discovered.

True, but there is a big difference between "Hey, I'm using your stuff, could you look at this and see if I did something stupid?" and "I want you to sign off on this publicly. Here is the contract."


Have you asked a lot of academic crypto people about their bill rates?


I've asked a few, and they've been pretty reasonable.

Of course, I haven't had something where I've had to ask DJB, so I may be biased.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: