Not enough people are using snow

[zrm]

[eternaleye]

One thing I find myself wondering is whether snow's goals might be better attained by implementing the IETF-backed HIPv2 protocol - for one, being an implementation of a Standards-track protocol might help with uptake.

(Note that while HIPv2 only recently got published as an RFC, HIPv1 was published in 2008)

[rektide]

@eternaleye had never heard of HIP before. I love this spec so much! Perfect for helping link-local communications establish & validate identity- thanks x 12 for the mention!

The DHT to map from keys -> ip addresses is novel to Snow afaik (edit: I'm finding HIP-ists have already used DHTs). I'd be interested on some words comparing Snow's tunneling over DTLS versus using other tunneling protocols- HIP seems to work in tandem with Encapsulating Security Payload (ESP).

Adoption has trailed, but Snow also brings to mind SocialVPN/GroupVPN, which uses XMPP to discover and exchange keys with peers, then initiates "TinCan" links- an applicationized libjingle. Substitutes a DHT for XMPP, uses a different encapsulation tech, but both peer exchange + encapsulation systems.

[eternaleye]

While ESP is the only transport format currently specified, it's not the only one possible - there exists an expired draft for using SRTP keyed by HIP, and a similar document could be made for TLS/DTLS.

Also, HIP is meant to work across the full public internet, not just link-local - there are even allocated DNS RRs for it.

[eternaleye]

Figured I'd split this out.

In terms of comparisons, ESP in BEET (Bound End-to-End Tunnel) mode (as is specified for HIP) adds 18 bytes of overhead to its contents, while DTLS adds 32. BEET, being end-to-end, encapsulates the endpoint IP addresses and such in the setup, and thus does not need to send the IP header on the inner packets. Also, while it can be wrapped in UDP (for NAT hole-punching, among other things), it does not require it by any means. So far as I can tell, Snow does send the inner IP header, and it uses DTLS over UDP exclusively (while DTLS can be sent directly over IP, basically nobody does so). Thus, the best-case protocol stacks for each look like this:

Snow: IP > [ UDP > DTLS > IP ] > Application
HIP: IP > [ ESP ] > Application

Square brackets denote overhead, and "Application" is whatever the application is making use of normally - UDP, TCP, SCTP, etc.

The minimum overheads of the various protocols are:

Protocol	Bytes
ESP	18
UDP	8
DTLS	32
IPv4	20
IPv6	40

Thus, while HIP's ESP transport faces a best-case overhead of 18 bytes (or 26 bytes, if wrapped in UDP) regardless of IPv4 or IPv6, Snow carries 8 + 32 + 20 = 60 bytes for IPv4, or 80 bytes for IPv6.

[zrm]

The nature of snow is that you give it a public key hash and it gives you a virtual IP address where you can send packets that go to the machine with that public key. The lookup method can be anything and there can be more than one. The transport method can be anything and there can be more than one. Right now it uses a DHT and DTLS but those are just implementation details that don't affect the interface visible to applications.

In theory we could use HIP for these things. Maybe someday we will. But IPSec is trouble. Transport mode requires dealing with platform-specific OS kernel interfaces and invites interference from stupid middleboxes.

Can you explain where your 18 bytes came from? Any of the usual HMAC algorithms are bigger than that by themselves. Doesn't tunnel mode end up looking pretty much like DTLS by the time it provides the same security properties?

The existing transport method clearly has room for improvement regarding packet size. It's sending 8 bytes of zeros as the source and destination address of every packet and some of the internal IP header is probably unnecessary. But I'm not sure I like the idea of putting anything from the internal IP header on the outside of the packet where it isn't encrypted. Stupid middleboxes can be very, very stupid.

[eternaleye]

The nature of snow is that you give it a public key hash and it gives you a virtual IP address where you can send packets that go to the machine with that public key.

This is exactly the purpose of the HIT - the neat trick there is it uses ORCHIDv2 in order to allow the hash of the public key to be the virtual IP(v6) address itself. It also supports dynamically-allocated machine-local "LSI" addresses, which are IPv4-compatible.

The lookup method can be anything and there can be more than one.

HIP does the same - HIPv1 had specified rendezvous-based (meant to make mobility easier), DNS-based, DHT-based, and others; they'll likely return for HIPv2.

The transport method can be anything and there can be more than one.

While only ESP has been published as an RFC, HIP explicitly allows for other transports; a draft was written for SRTP (though it has lapsed). If you want a TLS or DTLS transport, a good option might be to base it on TLS-PSK, keyed with the material generated by the HIP exchange. Submit it to the HIP working group - I suspect it'd get some interest!

Transport mode requires dealing with platform-specific OS kernel interfaces and invites interference from stupid middleboxes.

Perhaps, but OpenHIP has already demonstrated that neither is insoluble - it runs on the Big Three plus at least one BSD, and IIRC supports both bare ESP and middlebox-hole-punching UDP-encapsulated ESP; there have been multiple tests of such functionality as well.

However, neither OpenHIP nor InfraHIP yet support HIPv2 - though OpenHIP has stated an intent to release a version that supports it this summer.

Can you explain where your 18 bytes came from? Any of the usual HMAC algorithms are bigger than that by themselves. Doesn't tunnel mode end up looking pretty much like DTLS by the time it provides the same security properties?

I tried to find the fixed overheads of each - i.e. excluding the MAC length, etc. Using the same MAC in each would expand both by roughly the same amount. (And note: HMAC is a MAC, but not all MACs are HMAC. Poly1305 is a notable example.)

[...] I'm not sure I like the idea of putting anything from the internal IP header on the outside of the packet where it isn't encrypted.

BEET mode does not have to put anything from the internal IP header on the outside. What I meant was that things which are fixed for the session (src IP, dst IP, etc) are part of the tunnel establishment, and protected by HIP - but as they are fixed for the session, they are elided. Per-packet options that cannot be elided are instead sent with a pseudo-header on the inside of the tunnel. This was found to be rare in practice, and overhead remains low.

[zrm]

the neat trick there is it uses ORCHIDv2 in order to allow the hash of the public key to be the virtual IP(v6) address itself.

ORCHID makes me nervous. The address space is just big enough for people to assume there won't be collisions and just small enough for that assumption to be violated. So you end up having to deal with the possibility of collisions even though they're uncommon, and failure to do so gets worse over time as attackers get faster computers while the address space is permanently fixed. If more than one public key can map to the same ORCHID IPv6 address in practice then maintaining the contrary illusion only encourages security bugs in applications that don't appropriately handle a rare edge case.

If you want a TLS or DTLS transport, a good option might be to base it on TLS-PSK, keyed with the material generated by the HIP exchange. Submit it to the HIP working group - I suspect it'd get some interest!

DTLS is more of a lesser of evils than something I actually want. OpenSSL doesn't make my life any easier. Tunnel mode IPSec may even be the better alternative in theory, but is there a good cross-platform userspace library?

I'm more tempted to replace DTLS with NaCl. Think the working group would be interested in that?

Adding HIP as an alternative back end is likely to happen eventually, especially if both become popular. It's just a lot of integration work when there are higher priorities like porting snow to more platforms.

[eternaleye]

I'd say the math actually bears out ORCHID being safe. It allocates 96 bits to the hash. Let us (generously) assume that there are 2^33 (~8.5 billion) humans on the planet, and that they average out to having 2^7 (128) "services" each (after all, when you can allocate a separate HIP identifier for each thing you're running, why not use it and avoid the complexity of application-layer vhosting).

One can approximate the likelihood of a single collision when choosing n members from an alphabet of size m as 1 - e^( [ -n * (n-1) ] / 2m )

Plugging in m = 2^96 and n = 2^40, we get 0.0000076293654; approximately a one in 130k chance of there being a single collision, ever.

Now, this only holds if the hash function used is collision-resistant, but ORCHID allocates four bits to the "OGA" - ORCHID Generation Algorithm, i.e. the hash function used - so if a hash is broken the ability to migrate is right there. Wouldn't even require replacing keys - just re-hash.

And if that gets used up? Allocate another range - ORCHIDv1 used a different block of IPv6 than ORCHIDv2 does; that could be repeated.

Tunnel mode IPSec may even be the better alternative in theory, but is there a good cross-platform userspace library?

StrongSwan has a pure-userspace libipsec library that's pretty light. Look at ipsec_processor.h for the steady-state packet-passing API.

I'm more tempted to replace DTLS with NaCl. Think the working group would be interested in that?

NaCl, despite being a really nice simple library for message crypto, is still nontrivial to build secure protocols on top of. Especially regarding key exchanges and such. Trevor Perrin's 'Noise' may help some, but it's early yet.

[zrm]

Accidental collisions between honest peers are less the issue than that an attacker can generate keys until one of them collides with one of the honest peers. Adding only a couple of bits to the keyspace wouldn't help much either. Most current recommendations are to use 256-bit hash algorithms for new applications and the entire IPv6 address space is only 128-bit.

StrongSwan has a pure-userspace libipsec library that's pretty light. Look at ipsec_processor.h for the steady-state packet-passing API.

Seems to be GPL, which sadly would interfere with an iOS port if I'm not mistaken: http://www.fsf.org/news/2010-05-app-store-compliance

NaCl, despite being a really nice simple library for message crypto, is still nontrivial to build secure protocols on top of. Especially regarding key exchanges and such.

Reading the documentation I got the impression that all I would have to do is crypto_sign_keypair() to generate a long-term key pair, then for each session generate a session key pair with crypto_box_keypair(), sign the session public key with the long term private key using crypto_sign() and send the session public key and signature to the peer to verify with crypto_sign_open(). Then encrypt packets with crypto_box() and decrypt with crypto_box_open(). Have I missed something important? That seems a lot less complicated than the string of kludges it took to make OpenSSL do public key authentication.

[eternaleye]

Accidental collisions between honest peers are less the issue than that an attacker can generate keys until one of them collides with one of the honest peers.

In order for an attacker to achieve a 50% probability that two ORCHIDs, somewhere, collide, they'd need to generate 2^48 - 2^40 keys (which is... costly). And it'd be almost entirely useless besides: The chance of the collision not being between a pair of their own spam IDs is 2^40/2^48 = 1/2^8 = 1/256. That's not a winning bet; the economics don't work out for it to be valuable. Anyone with the processing power to do that (say, a botnet) would get more mileage out of leasing it for spam, mining bitcoins, or any number of other things that are far more effective.

[zrm]

In order for an attacker to achieve a 50% probability that two ORCHIDs, somewhere, collide, they'd need to generate 2^48 - 2^40 keys (which is... costly). And it'd be almost entirely useless besides: The chance of the collision not being between a pair of their own spam IDs is 2^40/2^48 = 1/2^8 = 1/256.

So they would have to do it ~256 times, requiring ~2^56 total work. Brute forcing 56 bits was proved practical by distributed.net... in 1997. Today there are Bitcoin mining ASICs that do over a trillion hashes per second, which is more than 2^56 per day. Brute forcing key hashes is not exactly the same thing and AFAIK there aren't publicly available ASICs to do it, but can you see why it makes me nervous?

Even if we like the opportunity cost argument that it's more profitable to mine Bitcoin than break a random ORCHID public key hash, there is zero security margin.

[eternaleye]

Brute-forcing 56 bits is a very, very different problem from finding collisions among the hashes of 2^56 public keys, and the math works out very differently.

The biggest difference is in generating the iteration values - for brute-forcing the DES keyspace, that can in fact be made incredibly minimal by way of ordering the key space according to a Gray code thus bringing the cost of getting another value for testing to "flip one bit." Generating keypairs is more costly by a large margin... and however fast you can hash them, not having anything to hash is a problem.

EDIT: Even without the Gray code, it's a single-cycle increment instruction to get another DES key to try. Generating an ECC keypair requires generating a private key (which, since some encodings are optimally compact, is the same because you can just increment the last word)... but also requires generating the public key from that, which is an ECC scalar multiplication, and is at best around 64k cycles. That's another 2^16 right there. (and 64k cycles is really optimistic - it's generally between 200k and 300k for the curves actually standardized for HIP, even on a Xeon. ARM tends to be closer to five million cycles.)

RSA is even worse.

In addition, a single-block DES computation is several times cheaper than hashing a public key.

Finally, ORCHIDs permit specifying new generation algorithms - if this really becomes a crucial issue, key stretching techniques come into play, allowing the work factor for generating the hash to be driven up arbitrarily. Note that in this case, the size of the "enhanced key" is not a concern - as the generation algorithm would specify the iteration count, the attacker cannot iterate fewer times and still validate, because the client will iterate fully.

[zrm]

requires generating the public key from that, which is an ECC scalar multiplication

Don't think like someone who wants to generate one unpredictable private key. Think like someone who wants to generate many public keys really fast.

Multiplication is expensive? Pick a point/prime, hold it fixed and choose the next scalar/other prime in order so that your slow multiplication becomes a not so slow addition from the previous attempt. Or fix the modulus entirely and produce a new hash by changing the exponent. It's not as fast as Gray code but it's not so much slower that I would be ready to declare victory.

Key stretching could work in theory but it's a grisly trade-off. There is a 1:1 proportionality between the amount you delay the attacker and the amount you delay the legitimate user. If you stretch the hash by very much at all you have to concede embedded devices, consume significant battery on mobile devices, significant resources and power on servers, create a resource exhaustion denial of service vector and add a human-perceptible amount of latency to each new connection.