Perfect Forward Security/Secrecy - a.k.a. Ephemeral Keys #204

Open
adamierymenko opened this Issue Jul 8, 2015 · 38 comments

Projects

None yet

8 participants

@adamierymenko
Contributor

Some work has already been done on this in the form of a preliminary message definition in Packet.hpp, but I realized there's no GitHub issue for it so here we go.

This probably will not make it into 1.0.4, which will focus on fixing some Windows issues with 1.0.3 and Android support and similar things. It may well make it into 1.0.5.

The current plan calls for implementing PFS in such a way that the same protocol extension and features can also be used to implement alternative ciphers and FIPS compliance should anyone ever want such a thing. The system can upgrade ciphers and renegotiate keys, and can also use the new cipher suite to re-verify existing credentials and authentication. The latter is a little challenging so will require a bit more research before the real implementation makes it in.

@adamierymenko
Contributor

This is unfortunately getting bumped again... basic design is there but too much to do for this release.

@heri16
heri16 commented Nov 30, 2015

:(

@adamierymenko
Contributor

I'd like to ask an important question: should PFS be implemented in ZeroTier?

The first response of most crypto and security people will be absolutely, but it's important in any project to define scope.

ZeroTier's primary objective is to provide a robust network virtualization layer that works anywhere and makes it easy to connect anything. If we could have done that reliably and robustly without crypto, it's likely that we would have left crypto out. That's because "anything" includes a lot of small devices for which crypto is a real concern in terms of CPU and memory overhead, and because the simpler a system is the more reliable it is and the more free of bugs it is. Complexity equals bugs, overhead, failures, vulnerabilities, etc., and as complexity increases linearly all these other bad things increase exponentially.

But as it turns out, it's probably provably impossible to build a robust distributed peer-to-peer network that works across trust boundaries (i.e. over the open Internet) without crypto. So crypto is required. Once you start doing crypto you have to do it well because bad crypto is worse than no crypto. Bad crypto is false advertising for one -- if you say you have crypto then people will treat your system like a crypto solution, and if you did crypto badly you're offering a crummy one. Secondly if crypto is critical to your design then bad crypto means your design is severely compromised.

So we spent a lot of time implementing what we think and hope is good crypto, or at least good enough crypto to make our crypto at least as strong as SSL and other common crypto that people use on the Internet. So far nobody's found a vulnerability, which either means we did it well or not enough people have looked.

Crypto is hard... old mature professionally audited crypto systems routinely have vulnerabilities found in them. Vulnerabilities are bugs. Linear increases in complexity exponentially increase bugs. One of the things we did to try to make our crypto secure is to take Daniel Bernstein's advice and implement boring crypto. Our crypto is simple and straightforward and doesn't have a lot of features, which means it also has very little bug surface area.

Another major overarching design goal in ZeroTier is to avoid state. In engineering the ZeroTier core we had an extreme aversion to state. Every bit of shared state that must be agreed upon in a networked system equals one transaction that can fail, so the failure rate of any composite transaction made up of multiple bits of state agreement is the product of the failure rate of each individual state negotiation. State also adds latency and code complexity. State is evil.

Therefore there are several cases to be made for declaring PFS beyond scope in ZeroTier:

  • PFS adds negotiated state and negotiated state is the devil.
  • PFS adds CPU, code, and memory overhead, which pushes us further away from smaller IoT-class devices or at least increases the amount of engineering that must be done to support them.
  • PFS adds complexity to the crypto system, which exponentially increases the likelihood of vulnerabilities.
  • If we implement PFS we are saying we have PFS, therefore if bugs are found in PFS those constitute vulnerabilities. If we don't say we have PFS, people won't expect us to have it and will take appropriate countermeasures at other levels.

The case for PFS is very straightforward: PFS is required for a good modern crypto system. Or is it? That's really the question here. If bad crypto is worse than no crypto and PFS is required to not have bad crypto, then PFS is required.

There are numerous crypto systems in use that lack PFS and others that make it optional. So that's obviously a question of opinion, at least as far as current crypto state of the art is concerned.

One possibility we've thought about is making PFS optional. But there's a problem with optional crypto: if a crypto feature is optional, then whether or not you have it must be negotiated and a flag must be added for whether or not you are willing to talk to someone without it. That adds even more complexity, which means bugs and overhead, and it also introduces a strong potential for a very common class of vulnerability. Optional crypto (or crypto with lots of features of varying strengths) is very often vulnerable to attacks that either force downgrade or prevent upgraded features from being negotiated. A man in the middle or even sometimes a remote attacker can sometimes accomplish this by blocking, spoofing, replaying, or otherwise meddling with traffic so as to trigger a state change. Did we mention that state is evil?

So optional PFS is probably out. We should either have PFS and require it or not.

The most common problem report we hear about ZeroTier is "connectivity is flaky," which means that new connections to new devices (or ones that have not been contacted in a while) fail with some probability. This can have many causes that all boil down to some form of network unreliability. Failures are failures to exchange state, so we can assume that adding PFS -- which adds state that must be negotiated -- will increase the rate of these failures over slightly unreliable networks.

Our goal is to converge with the reliability of the underlying network such that running with ZeroTier is no less reliable than running without. Adding any form of state negotiation pushes us provably further from that goal and perhaps makes it impossible, since chains of probability are multiplicative.

Then there's the question of scope. Is PFS in scope?

Our position on security is this: ZeroTier provides a network that can have boundaries, but we do not believe that network boundaries should be the cornerstone of a security posture. A secure system should be designed so that any of its primary components could be exposed to the open Internet. Network boundaries should be an afterthought, a form of defense in depth. That way you don't have a "soft underbelly."

We also believe in defense in depth. With crypto, defense in depth means not relying on a single crypto implementation since any crypto implementation -- new or old, audited or not, etc. -- can have bugs. Therefore if you care deeply about security the recommended course of action is to run established cryptographic protocols like SSH, SSL, etc. over ZeroTIer's networks. That way compromise of ZeroTier constitutes only a compromise of an outer cryptographic envelope. This is how we do things ourselves, at least insofar as a given type of traffic is security-critical in any way. We'll pass stuff unencrypted over virtual networks sometimes, but that's always stuff that would not really matter much if it were stolen and is not used as a security credential anywhere.

Since SSH, SSL, etc. often implement PFS, if you are using these then you probably already have it. The fact that you're layering crypto also accomplishes something like PFS, at least in spirit. The goal of PFS is to make key theft less damaging. If you're running crypto over the ZT layer, then theft of your ZeroTier identity.secret only means they can peel back the first layer and reveal... yet another layer of encryption.

Thoughts?

@adamierymenko
Contributor

Defense in depth is basically: First, make it secure. Then, pretend it's not secure and secure it.

@adamierymenko
Contributor

I realized the stuff about failure rates is still a little tortured and unclear in that brain dump over there:

Let's say you have an 0.0001 packet loss rate. Opening a TCP connection involves a multi-step handshake, so your failure probability is now N*0.0001 where N is the number of steps in the TCP handshake.

Now add ZeroTier. Right now ZeroTier requires a WHOIS to get the identity the very first time you connect (or if you haven't in a long time, or have rm -rf'd your cache) and that adds another step. So now your failure rate is (N+1)*0.0001.

But once you've talked to someone, your failure rate with ZeroTier drops back to N*0.0001 which is the same as the underlying network because ZeroTier is stateless. Statelessness can be achieved because if you have both your private key and someone else's public you can compute a shared secret without further communication. If a device already knows another device it can communicate instantly.

But adding PFS means that ephemeral key exchanges must occur before communication can take place. These occur frequently, so they might as well occur all the time. So ZeroTier's reliability no longer converges with that of the underlying network.

This represents a major sacrifice of a design goal.

@adamierymenko
Contributor

FYI if anyone is like "WTF is PFS" here is some RTFM: https://en.wikipedia.org/wiki/Forward_secrecy

@janjaapbos
Contributor

Just a question, so that I better understand the implication. Does the lack of PFS also affect the control of access to a network as a participant? Or does it only affect the confidentiality?

@adamierymenko
Contributor

Only confidentiality.

@adamierymenko
Contributor

Without PFS theft of your identity.secret will allow someone to decrypt all your past traffic. With PFS that is severely limited -- PFS protects retroactive confidentiality after a breach. It's a good thing but it isn't free, which is what this is about.

@heri16
heri16 commented Dec 4, 2015

No state please. The reason I am using zerotier is to ensure network roaming or mobility. When my WAN IP changes due to path/route failover to another ISP, I can get zerotier to still keep the tunneled tcp connections up. This also mean I could theoratically implement poor man's multipath to aggregate bandwidth from two paths to the Internet (leveraging a technique similar to Connectify Dispatch). PFS is fine if we use a light touch like the new dnscrypt.

http://lifehacker.com/how-to-combine-multiple-internet-connections-into-one-s-1699431630

@chairmanwow

I'm going to recommend something a bit controversial. Zerotier should move to stop encrypting payloads and just use crypto for its own access control.

  1. A secure transport layer is incredibly difficult to do correctly and always ends up being a huge attack surface.
  2. Crypto algorithms and tradeoffs will be different for IoT vs. the datacenter context. This should be handled by someone higher up in the OSI model.
  3. The future of Zerotier is going to be in IoT. Don't lose that market by adding latency in contexts that don't require it.

A "secure" transport layer requires PFS. When bad actors can store all your traffic forever, it is absolutely, 100%, neon-sign flashing, a requirement. The thing is, how many applications have security needs that demand a truly "secure" transport layer? PFS is indeed expensive in terms of cycles and statefulness. Leave all that headache and cryptanalysis to existing implementations, like libtls, which can be added when needed.

Imagine a low-power IoT device and an x86_64 VM on AWS. Xsalsa20, while kinda lightweight, will be a burden on an IoT device and provide ok security on x86_64. Maybe the IoT device should run a lightweight algorithm like SPECK or SIMON instead of Xsalsa20. Maybe the x86_64 VM should run something like Skein, which flies on 64-bit and can have a huge block for the totally paranoid. This should be left to the app designer. Boxing before you box provides little additional security. Boxing when you don't need to could theoretically provide a performance hit that could sink Zerotier against a competitor.

As a rabid evangelist of how awesome this project is, IMHO, the future of Zerotier is indeed going to be networking the world's devices. Low power, real-time, ubiquitous IoT is the growing market. This product should be optimized around rocking that. The devices and contexts where this idea must go will not allow for one-size-fits-all cryptography. What you'll actually end up doing is making Zerotier the target of all kinds of cryptoanalytic attacks, when you really want this to be focused on the apps running over Zerotier.

Here is where I have skin in the game: Our app, Balboa, requires PFS, because we are a security product. We bragged about having an encrypted backplane to customers, but, as security professionals, it feels disingenuous without PFS. If Zerotier were to ditch PFS, this would set us out on rolling PFS for our own backplane. This is doable and with many established solutions. We'd still proudly use Zerotier to keep our microservices humming, and, now, with even less state and latency.

I don't think Zerotier should be obligated to give crypto to us, since, I want my PFS and AEAD to be optimized for my needs without boxing twice. Somebody networking a thermostat shouldn't have to pay for what we need on an AWS m4-xlarge instance.

Just my $0.02!

@janjaapbos
Contributor

Yes, boxing before you box does not sense. I agree with your point that ZeroTier should not be burdened with constraints that may or may not apply at the application level. Also, for me the greatest value is to interconnect and authenticate. The value of confidentiality depends much more on the actual use case. Sometimes it is only important that information is keep confidential as long as this info is relevant, which may be a short time.

Just to be sure, we still do want to digitally sign the payload, if we are not encrypting it? To guarantee authenticity and integrity.

In my use cases for ZeroTier I would like to have the possibility to determine per network whether or not the content should be encrypted. In any case, I do not need PFS.

@bonki
Contributor
bonki commented Dec 7, 2015

[...] I would like to have the possibility to determine per network whether or not the content should be encrypted. In any case, I do not need PFS.

+1 on this.

@chairmanwow

Does making optional the current crypto system violate design concerns @adamierymenko mentioned about statefulness? As a consumer, I'm cool with anything that would allow us to remove a box. I think confidentiality without PFS isn't "truly" (IMHO) possible, but it certainly won't hurt anything if it's optional.

Just spitballin' here, but I imagine you could get away with just signing a poly1305 authenticator result of the header and payload to get authenticity and integrity.

@heri16
heri16 commented Dec 8, 2015

The encryption overhead of Cp25519 used in zerotier-one is very minimal. I am not sure what the fuss here is all about. Have these people even made performance measurements? Cp25519 could probably run on SBCs like the raspberry pi without using more than 3% of CPU time. Having encryption as a default is a smart idea these days unless the world has not awaken to the Swoden incident, or even my neighbour. For state-sponsered hackers like the NSA, they should look elsewhere to break into the system, like weak zt control-nodes or endpoint browser exploits. So let them as long as zerotier has done it's job on the security perimeter (preventing the passive fingerprinting of windows os client nodes over the Internet the moment the zerotier NDIS interface is connected). Haven't heard of Happy Dance? Running SSH over unencrypted channel is bad these days. Allowing no encryption at all in zerotier would be bad, just like the recent cipher downgrade attacks. Go consult dbj instead of these random people here.

@heri16
heri16 commented Dec 8, 2015

Even low-powered IoT products these days by design goals want to use some sort of encryption, just ask Particle, Amazon Web Services, and Intel. I have an espruino embedded board that runs one-year on a coin-cell battery and it uses mbed TLS. We must not let anybody be able to scan the traffic and fingerprint all the IoT devices in the world, which would make designing an exploit for all of them in one go easier.

@maci0
maci0 commented Dec 8, 2015

I'd also say don't remove the current security features. They work great and give reasonable privacy.
About PFS, it would be nice to have on the ZT1 layer, and I would gladly sacrifice a few packages for having better security out of the box. This would be nice for general-purpose use-cases.
But If I would build a really security sensitive application/service I would still add another layer myself.

Also is there any hard data that suggests devices like a raspberry pi couldn't handle PFS just fine ?
Many arm SOCs also do have some kind of hardware acceleration for encryption.

@adamierymenko
Contributor

Fantastic comments here! Thanks!

After reading all of the above here are my current thoughts:

I agree with @chairmanwow that payload encryption should be optional. The good news is that technically it is. The protocol allows unencrypted payload, but in the current code there is no code path for that. The current code only sends HELLO (key exchange and other public info) unencrypted, but all other packet types are sent boxed. It would be possible to make encryption optional either on a per-device level or a per-network level. Both may make sense. Extreme care must be taken here to not introduce downgrade attacks -- basically by never allowing an untrusted entity to influence this decision.

Optional payload encryption would make sense in a few contexts: really itty bitty IoT, SCADA, and other devices that don't have a lot of CPU to spare (there are lots of these), low-power mobile devices that must stretch battery life as far as possible, and the use of ZeroTier as a software defined networking layer inside a data center. In the latter case the CPU power is available but you don't want to be wasting it encrypting traffic that is only going to flow over your internal hardware network fabric between compute nodes. In the intra-data-center SDN case ZeroTier would need to achieve performance parity with solutions like VXLAN/OpenFlow that are offered by the likes of Cisco and Juniper and that would mean shaving off any extraneous costs in that domain.

But I disagree that payload encryption should be removed for two reasons.

One is that while it might be made optional for data traffic (VERB_FRAME and friends), it should remain mandatory for control traffic. Control traffic might contain meta-data about the network or the state of endpoint nodes that could be leveraged to levy other kinds of attacks or to execute denial of service attacks. It's best to keep that stuff secret at the very least as a defense in depth precautionary measure.

Secondly, it's already there and it works. ZeroTier runs over a peer to peer network because a P2P network is mandatory to directly connect the world's devices. We're not doing cloud backhaul here except as a first-and-last-resort path to facilitate things instantly-and-always working. It is impossible to deploy a P2P network without competent cryptographic authentication since any unauthenticated P2P network is going to be trivially vulnerable to a whole host of denial of service and "Sybil" class attacks.

To do authentication you must have crypto, otherwise you've implemented weak security theater authentication. To do distributed crypto across trust boundaries you must have some form of asymmetric crypto and secure key exchange. To do authentication in a scalable way you have to do it with certs which requires signatures which also requires asymmetric crypto. Once you have all those things, doing basic payload encryption is easy and only makes things more secure than they would be without it.

Finally and last but not least: to do authentication well you have to do keyed MAC. Keyed MAC requires a hash function to generate single-use keyed MAC keys (for most keyed MAC), a MAC algorithm to scan and MAC the payload, and of course all of the above to give you a key to do MAC at all. Once you have all that, the case becomes even stronger for just encrypting the !!!@!@!! payload because you are already like 99.9% there. We use Poly1305 for MAC. Poly1305 requires unique single-use keys. To get those you have to either hash the secret key with a nonce or use the secret key with a nonce to generate some cipher output and use that as a Poly1305 key (the DJB NaCl construction). Those two things are about equally costly, and the latter now provides you with an already initialized cipher that you might as well just encrypt the !!!!%!%!!!! payload with because bears.

All that being said, the extra encryption pass is not free. Encrypting the payload means you're crunching it through XSalsa20 and then crunching it through Poly1305. Poly1305 is faster than Salsa20 and one pass is faster than two, so there is performance value to be had from skipping the Salsa20 step for high performance or low power applications.

So here's where I'm leaning and I'd love comments.

My inclination is to keep the status quo right now because it works, but to document our lack of PFS and the rationale behind this decision more prominently so we are not giving people a false sense of security about the confidentiality of their data in the long term. Users who want PFS like PKC Security / Balboa ( @chairmanwow ) should then deploy it over top of the ZeroTier network using SSL in an appropriate mode, IPSec, etc. All of those will run fine over virtual Ethernet.

The cost is very small. XSalsa20 crunches at about 700 megabytes per second per CPU core on my Macbook Pro, and Poly1305 clocks in at over 1200 (1.2gb/sec). Together you're talking something like 350 megabytes per second which is well beyond gigabit Ethernet at ~100mb/sec and well beyond the speed of most storage subsystems. But you can see why only Poly1305 would be desirable for on-site SDN or super-speed-critical applications!

Then in the future we can add an option to optionally disable payload encryption. This could be implemented in two simultaneous ways:

  1. An individual device could elect unencrypted operation by sending this via a MAC'd/authenticated message (e.g. as a payload verb flag in any packet). Once unencrypted operation was elected it would remain in effect for some period of time after this election or until a packet is received with that flag cleared. This would be secure since everything's MAC'd, so only the device itself could elect unencrypted operation. This would also be shown in the peer list -- a device that says "I don't care about confidentiality" would be shown via some flag. Control traffic might still be encrypted but data traffic (which is 99.99+% of all traffic) could skip the XSalsa20 pass except to init Poly1305 (which is trivial and fast). BUT such an election is subject to network-wide rules as per option #2 below.
  2. Networks should have a tri-state option: no encryption, device default encryption, or mandatory encryption. No encryption would cause all peers to skip payload encryption for traffic over that specific virtual network. Other traffic would follow default logic and ZeroTier control traffic would remain encrypted as in #1. The second setting -- device default -- would be the current behavior with most higher powered devices encrypting but with devices allowed to opt out if they are low power or on the local LAN etc. The third setting would prohibit unencrypted traffic, so a low-power device that didn't want payload encryption would not be able to communicate on that network.
@adamierymenko
Contributor

Side question -- and one that I do not immediately know the answer to. This one's for you @chairmanwow and other PKC folks:

Right now we encrypt-then-MAC (which is the right thing) using XSalsa20 to encrypt and Poly1305 to MAC and generating the throwaway Poly1305 key with the first bytes of the XSalsa20 key stream. This is absolutely identical to DJB's NaCl implementation of XSalsa20+Poly1305, which isn't a coincidence because we wanted to do things in a way that an elite professional cryptographer says is solid.

(DJB is Daniel Bernstein who is among the best known and top cited academic cryptographers and mathematicians for those who don't know. You don't get better authorities for academic crypto except maybe top-secret NSA committees staffed by top black-ops crypto mathematicians and those won't admit they exist let alone return e-mails.)

BUT...

If we skip the XSalsa20 pass, that means we'd just be keying Poly1305 and then MAC'ing the plaintext.

Now...

My stupid straightforward reasoning tells me this is no different. Encrypt-then-MAC means you are MAC'ing the cipher text which is then sent in the clear. So right now in the current construction the attacker knows the cipher text that's been MAC'd. In the no-payload-encryption alternative mode nothing has changed vis-a-vis the MAC. The attacker still knows the MAC'd text (which is now plaintext), but they can't work backward and use that to gain any info about the secret key that was used to initialize Salsa20 and generate the Poly1305 key. If they could do that, that would constitute a total break of Salsa20 which would be big front page news in the crypto world and would cause sleepless nights at Apple and Google to name a few.

Is that reasoning sound?

@adamierymenko
Contributor

@heri16 I wanted to respond about IoT -- others might find this interesting too.

You are partly correct. ZeroTier in any form is too heavy to run on a current-generation fridge magnet. There is going to be a class of IoT devices that are too small to run it and that's undesirable but unavoidable. These are things with 16-bit CPUs, only teeny tiny amounts of memory, slow clock speeds, etc. In that case ZeroTier could run on a hub they talk to, and all those types of devices require a hub of some kind because they are also often too tiny to speak SSL or anything else robust enough to be used over the open Internet. The "hub" can in some cases be a PC, a mobile app, a router that supports 'apps', etc., in which case we can do software defined stuff that is off-loaded from the device.

For the rest of devices: if they are big enough to run ZeroTier they are big enough to run PFS. In theory.

The problem is battery life, overall CPU budget, and competitiveness with other solutions in terms of memory and storage footprint. If I'm speccing a board for an IoT device I want to use as little flash and RAM as possible to keep manufacturing costs down. I also want to use a cheaper chip, which might push my CPU budget down. Finally, the more actual crunching it has to do the more power it will use. Batteries are expensive and battery life is among the most prized features for pretty much every kind of mobile or disconnected device.

Therefore to field a competitive solution in that space we will need to be memory, storage, and CPU footprint competitive with things like the Amazon IoT toolkit. That's going to be tough as it is (though not impossible IMHO). That's because back-hauling all traffic to the cloud is simpler and more straightforward. You eat costs further down the line that way -- like constant OpEx for one-time-sale products -- and you lose privacy and security and flexibility and hack-ability and lots of other things many users care about. But it makes the initial development kit an easy sale and it makes our job harder when you start talking about competing with it. I'm not inclined to add features that might make that task even harder still. Curve25519 is fairly cheap but it costs something and doing it every N seconds for M peers is not free.

@adamierymenko
Contributor

Also let me be clear: when I talk about IoT devices I'm talking about things a lot smaller than a phone or a Raspberry Pi. Those are monsters compared to thermostats, appliances, little tiny web cameras, etc.

@chairmanwow

Yep, your reasoning on poly1305 is sound. The security of Poly1305 rests on the uniform randomness of the mac key and not the message, so you'd be groovy.

The only thing you have to watch out for with Poly1305 is not accidentally reusing the same key and nonce for xsalsa20 so you spit out the same, first 32 bytes and authenticate two messages under the same mac key. That's why DJB suggests just using a message count as a nonce (I don't know how nonces are done in ZT), but random nonces are also doable since 24 bytes is a pretty big space to expect a collision.

Also, I'm totally cool with optional crypto, particularly if your user-base wants it!

@adamierymenko
Contributor

Sounds good.

Then in the short term I'm going to leave things as-is and in the long term I'm going to make payload crypto optional in at least one and maybe two ways.

Going to close this for now since for now PFS is shelved.

@heri16
heri16 commented Dec 9, 2015

Awesome. Just a side-note, most people in the IoT world are already doing the hub model. It is just that many fail to secure the last-mile from the Hub to the lightbulb or garage-opener. IoT use-cases commonly send very little packets in small bursts that encryption is even done on WSN (Wireless Sensor Nodes) using 16-bit embedded firmwares. Contiki, NodeMCU, WiPy, Espruino, Particle.io, CSRmesh, and even the Amazon.com Dash buttons use encryption.

I actually use an Espruino Pico microcontroller to pass traffic to the Raspberry Pi Hub with simple encryption. From there the hub runs a dumb proxy that re-encrypts the MQTT traffic to AWS IoT gateways with client x.509 tls certificates. On 8-bit microcontrollers like the digispark, I use other forms of security over 400Mhz that does not even understand IP packets.

Zerotier One lives at the hub, where IP networking exists. It does not have to worry about remote controllers and fridge magnets where IP networking does not exist, where protocols are closely tied to the physical layer.

If Zerotier wants to go further into the physical layer, it could start another project with Bluetooth LE, and work with people from http://opengarden.com.

@heri16
heri16 commented Dec 9, 2015

For those interested on the smallest thing that zerotier-one can run on, I recommend OpenWRT mips microcontrollers like the Arduino Yun and Onion Omega or the $13 Linkit Smart. Check out http://linino.org or http://onion.io for more info.

@adamierymenko
Contributor

Here is the previous suggested PFS ephemeral key implementation -- saving here since it will be removed from the code for now:

    /**
     * Ephemeral (PFS) key push: (UNFINISHED, NOT IMPLEMENTED YET)
     *   <[2] flags (unused and reserved, must be 0)>
     *   <[2] length of padding / extra field section>
     *   <[...] padding / extra field section>
     *   <[8] 64-bit PFS key set ID sender holds for recipient (0==none)>
     *   <[8] 64-bit PFS key set ID of this key set>
     *   [... begin PFS key record ...]
     *   <[1] flags>
     *   <[1] symmetric cipher ID>
     *   <[1] public key type ID>
     *   <[2] public key length in bytes>
     *   <[...] public key>
     *   [... additional records may follow up to max packet length ...]
     *
     * This message is sent to negotiate an ephemeral key. If the recipient's
     * current key pair for the sender does not match the one the sender
     * claims to have on file, it must respond with its own SET_EPHEMERAL_KEY.
     *
     * PFS key IDs are random and must not be zero, since zero indicates that
     * the sender does not have an ephemeral key on file for the recipient.
     *
     * One or more records may be sent. If multiple records are present,
     * the first record with common symmetric cipher, public key type,
     * and relevant flags must be used.
     *
     * The padding section may be filled with an arbitrary amount of random
     * or empty payload. This may be used as a countermeasure to prevent PFS
     * key pushes from being recognized by packet size vs. other packets in
     * the stream. This also provides potential space for additional fields
     * that might be indicated in the future by flags.
     *
     * Flags (all unspecified flags must be zero):
     *   0x01 - FIPS mode, only use record if FIPS compliant crypto in use
     *
     * Symmetric cipher IDs:
     *   0x01 - Salsa20/12 with Poly1305 authentication (ZT default)
     *   0x02 - AES256-GCM combined crypto and authentication
     *
     * Public key types:
     *   0x01 - Curve25519 ECDH with SHA-512 KDF
     *   0x02 - NIST P-256 ECDH with SHA-512 KDF
     *
     * Once both peers have a PFS key, they will attempt to send PFS key
     * encrypted messages with the PFS flag set using the negotiated
     * cipher/auth type.
     *
     * Note: most of these features such as FIPS and other cipher suites are
     * not implemented yet. They're just specified in the protocol for future
     * use to support e.g. FIPS requirements.
     *
     * OK response payload:
     *   <[8] PFS key set ID of received key set>
     *   <[1] index in record list of chosen key record>
     */
    //VERB_SET_EPHEMERAL_KEY = 15,
@adamierymenko
Contributor

New PFS idea, so I'd like to reopen for discussion.

The problem as discussed above is that PFS as originally designed requires a negotiation step, which impacts both usability and the overall 'bloat' of the protocol.

I had an idea today while discussing crypto with some folks in Berlin and I wanted to write it down and see what others think of it.

C25519 keys are tiny. Why not just append the key to every packet?

So here's a proposed design:

  1. Introduce a new crypto "suite" ID for PFS mode. The same algorithms would be used but this would indicate that the last 32 bytes of the packet are in fact a PFS ephemeral public key. This key would have to be authenticated by the MAC so there'd be some details to figure out but that's the idea.
  2. In PFS mode always append the key.
  3. To save compute time, generate new ephemeral keys every e.g. 30-60 minutes. On the receiving end we can cache ephemeral keys and cache the result of ephemeral key agreement so we don't have to do a C25519 ECDH key agreement every single packet.

The important thing here is that every packet contains all the information required to establish PFS, therefore there is no extra state negotiation step before we can talk.

If that's rambling or wrong it's because I'm sitting at a table with a bunch of other people talking right now. Will think on this more later and clarify and maybe post an actual implementation with details.

@adamierymenko adamierymenko reopened this Apr 28, 2016
@adamierymenko
Contributor
adamierymenko commented Apr 28, 2016 edited

^^^ That's too simple. There must be something wrong with it. :) If there is blame it on ridiculous jet lag.

@adamierymenko
Contributor

Still can't think of anything particularly wrong with this except that it's not efficient. 32 extra bytes per packet is a little heavier than ideal.

@dafyre
dafyre commented Apr 28, 2016

Thinking about small IOT devices, why not offload the PFS processing to a
ZT Gateway or Exit node? That would save battery life / processing power
on the devices, while still giving them the features that are granted via
ZT?

On Thu, Apr 28, 2016 at 2:55 PM, Adam Ierymenko notifications@github.com
wrote:

Still can't think of anything particularly wrong with this except that
it's not efficient. 32 extra bytes per packet is a little heavier than
ideal.


You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub
#204 (comment)

@adamierymenko
Contributor

My thought was to make it optional and a network-level config option. Networks could select PFS to be off, optional, or required. IoT-oriented networks could set it to off or optional and IoT devices could disable it, which would just prevent them from communicating on PFS-required networks.

@chairmanwow
chairmanwow commented Apr 28, 2016 edited

I got an implementation question. Is the thought here that ZT nodes would just report a new public key at the end whenever some expiry triggers? Would you do this by swapping out the last 32 bytes with a new 32 byte ed25519 public key from some newly gen'd keypair? If so, would you have some initialization step at the start where the first public-key exchange is authenticated under some long-term, non-ephemeral keypair?

@adamierymenko
Contributor

What I was thinking is that authentication always incorporates the long-term key. When doing PFS the computed shared secret key is the long term key XOR the ephemeral shared secret or something like that. That way you get MAC against the long term key for free and you can't MITM the PFS exchange (without stealing identity.secret that is).

I'm not aware of any way of doing PFS that can't be MITMed without either a long term key for signature or MAC or "ratcheting." Ratcheting, while a very good way of doing PFS, is not possible here because that requires long term state and reliable transport.. or a lot of state negotiation and renegotiation which we are trying to avoid like the plague.

This approach gives us optional PFS (that could be enforced at the network level) without requiring any multi-step state exchange at the expense of 32 bytes per frame. It's also very simple at the code level.

@adamierymenko
Contributor

By long term key XOR the ephemeral shared secret I mean XORing the two secret keys that result from ECDH, not XORing ECDH keys. The latter would break ECDH math.

@adamierymenko
Contributor

The only other drawback I can think of is that the relative lightness of this depends on the lightness of EC. If we ever had to swap it out for RSA for any reason (or any kind of heavy post-quantum crypto) we'd have to totally revisit the design or cope with a lot more overhead. As far as I know EC is the only asymmetric cryptosystem with such small keys.

@chairmanwow
chairmanwow commented Apr 28, 2016 edited

Yeah, it's a good idea to hash in some long-term key that is the shared secret of the long-term keypairs of both sides. Axolotl racheting would be horrible to have to implement with packet loss.... Might be worth taking a look at Noise Pipes though, another piece of crypto from Trevor Perrin.

https://github.com/noiseprotocol/noise_spec/blob/master/noise.md

Probably shouldn't implement this all the way either, but there are some good ideas that could be borrowed.

@nothingmuch

The relevant bits (IMHO) of Noise's protocol are the Noise_K or Noise_X patterns: http://noiseprotocol.org/noise.html#one-way-patterns

These patterns are non interactive, assume a static keypair for the recipient for decryption, and a static key for the sender (authenticated), and use an ephemeral keypair (generated by the sender) for forward security. The only difference is that K assumes the recipient knows the sender's static key.

This provides non interactive key agreement with forward secrecy, and mitm protection, where the authentication is as a result of the static<->static key agreement, which is protected by the ephemeral exchange.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment