Risk of collisions with using truncated keys/hashes in IPv6 address

[neilalexander]

Right now the IPv6 address is generated by truncating 512 bits down into less than 128 bits to fit in an IPv6 address.

This raises questions of:

1. Address uniqueness/collisions, especially when using the routed /64s which are truncated even further
2. Cryptographic strength/provability
3. Whether using fd00::/8 (which is already designated as ULA territory, unlike fc00::/7) is appropriate

[Arceliar]

Notes about this: Leading 1 bits (and the first 0 bit) are truncated from the 512-bit NodeID and the count of 1 bits is stored in the lower 7 bits of the second byte in the IPv6 address. The rest of the NodeID is appended to the IP, up to the 128-bit IPv6 address size (or up to 64 bits total for a /64 under fd80::/9). So you can brute force an address with a lot of leading 1 bits, and make brute force collision more difficult as a result. You can brute force something with: GOPATH=$PWD go run misc/genkeys.go

This is a partial mitigation for collision-based attacks, if you really care, but I dislike that it could lead to something of an arms race between attackers and users. I would suspect that full addresses are safe for now, but I'm less confident about /64 prefixes.

One option that we've been discussing is to set up a DNS proxy and listen form something like <boxPubKey>.yggdrasil, while forwarding all other domains to the normal system DNS resolver. This would immediately compute the address derived from the key and respond to the lookup. In the background, it would start a session for this key, but leave the session uninitialized. The first time the user tries to send a packet, it would trigger the usual DHT lookup and session setup, requiring that the key exactly match <boxPubKey>. The changes to sessions and dht/searches to support this should be minimal. I'm not sure about the DNS parts... in general I think intercepting DNS is ugly, but I can't think of an alternative that allows for the full key to be used. Addressing nodes inside a /64 subnet would need to do some subdoimaining... something like <lower64>.<boxPubKey>.yggdrasil to match the box pub key but the resolve to the IP of a node in that network, where <lower64> is the lower 64 bits of lower 64 bits (the interface identifier) of the sub netted node's address. I guess hex-encoded and maybe - delimited instead of : (if delimited at all), just for readability reasons. Directly connecting to a node based on IPv6 address would still work, albeit with less security, but we may want to change address ranges if we do this (to stop using fd00::/8, which conflicts with some other networks such as dn42).

[EternityForest]

Do we really need /64 subnets? You could of course keep the /64 behavior internally, behind the router, but what if you only assign addresses with a longer prefix?

If every client had the same first 15 bytes(Or first 14, if you run out of those), collision resistance should still be very strong.

You could brute force the /64 of the router itself, but that would do you no good at all, because the router is just blocking anything that isn't going to something with a much longer prefix, or anything without at least 14 bytes that match the public key.

You could also do the same for packets coming from the router. Just assume that all clients share at least 12-15 bytes with the router, and anything else is a hacking attempt. You can't partition the subnet any smaller anyway, thanks to IPv6 being annoying like that.

If Yggdrasil could actually act as a full consumer router, complete with it's own DHCP integration and UPNP, it could automatically give out reasonable addresses with as long of a prefix as possible, and block any incoming messages to clients that weren't even asking for them.

[EternityForest]

Just another random thought, Assuming you don't want to mess with DHCPv6 to be able to fake longer prefixes, why not give every non-mesh client a full 112 bit address?

Yggdrasil keeps an internal random nonce (Maybe the hash of the private key), and every time it detects a new non-mesh client it needs to route for, it hashes that client's link-local address with that nonce.

Using that result as a seed, we deterministically generate a key and cache it in RAM, using it for all traffic going forward.

The same client behind the same router will always get the same public address, you gain a tiny bit of privacy because it's no longer obvious which nodes are behind the same router, and collisions become almost impossible.

It might get a bit tricky with multiple routers, because the same packet could appear to be from a different client based on what Yggdrasil router it went though.

To avoid this, every router could still advertise it's own prefix, but they would no longer be globally unique, they would just be configurable or generated at startup(I think config free use is important for mesh).

That way, you could even have true roaming while keeping the same 200:, because you could configure multiple redundant routers with the same nonce used for the deterministic keys!

How awesome would that be? You could set up multiple public routers with no backbone or anything, connect to any one of them on your phone, and keep your IP when roaming between them, despite not having any infrastructure linking them.

[treysis]

You also shouldn't be using 200::/? addresses. They are reserved and might cause problems.

[neilalexander]

@treysis

You also shouldn't be using 200::/? addresses. They are reserved and might cause problems.

It was reserved in RFC 1888 in 1996, deprecated in RFC 4048 in 2005 and no other use of it has ever seemingly been suggested since. For now it seems like a safe-enough bet to not conflict with anything else in the world.

[treysis]

Why not use ULA instead of some rogue method?

[neilalexander]

ULA is more likely to conflict with private network addressing and/or projects like cjdns.

[treysis]

You can also get your own official delegation from any of the RIRs.

[neilalexander]

They aren't terribly likely to give us a /7 and bits in Yggdrasil IP addresses matter — the less bits we have, the less bits of the public key we can fit into it which reduces the strength of a given address.

[sdgathman]

@EternityForest

You can't partition the subnet any smaller anyway, thanks to IPv6 being annoying like that.

Partitioning smaller than /64 works just fine. There are a few braindead devices out there that don't even work correctly with DHCP6, but at this point only a few printer brands are that braindead that I've seen.

Yes, SLAAC requires /64, but with DHCP6 you can subdivide to your heart's content.

[treysis]

Technically it might work, but going smaller than /64 is out of spec.