Proved that 300::/64 Yggdrasil subnet is vurnerable against private key brute force attack

[vikulin]

This made by @Filarius . He managed to collect huge number of private/public keys and select only pairs with matching 300::/64 subnet. His hardware/software were following:

• i5 3570k, 4 х 4.0 GHz ~6 hours collecting key pairs with ~ 1.5 MH/s on aceton's miner
• found 63.7 М keys, (~2.4 GB data file)
• found 1800 pairs with matching subnetworks

Matching keys example:

EncryptionPublicKey:
8f784c61fe25a181e019e4e4b16dbcd83abd005fdc99eb90ceba69993cf1b162
EncryptionPrivateKey:
183e2af019490521ac627d2dde53812bd9016288f6d8e6a24e78bc211825627b

EncryptionPublicKey:
bec5179de61b9f9b972782e8a3d791e45975d4a0b3028f277a46c42019786056
EncryptionPrivateKey:
a8d73ca615cef484b425dcbfb6d795f1b461a79b1e8cccb8fbdea52ad09b487d

Subnet: 300:2300:7c67:6c3::/64

@neilalexander , can we extend prefixlen from 64 to 32 to make the subnet stronger?

[jorektheglitch]

AFAIK this calls "Birthday attack". Wikipedia says that difficulty of search a collision in hash function typically is 2^(n/2) where n is hash lenght.

In Yggdrasil lenght of hash is 56, and it's very easy to found a similar subnets.

[neilalexander]

Ultimately we knew this was going to happen and it is because we are truncating a longer 512-bit hash of the public key into an even smaller fraction of a smaller 128-bit address space.

We are truncating the keys not because we really want to, but because it's the best way to test the Yggdrasil design with existing IPv6 stacks. Ideally we would address nodes using their full public key without any truncation but this would require a new address family with a kernel-space implementation and significantly more engineering effort than makes sense at this stage.

The reason that the 300::/8 subnets are /64 in size is because this is the minimum subnet size for IPv6, as defined by the IETF, for address auto-configuration. If we make the subnets smaller then we can potentially slow down attackers but at the cost of greatly increasing complexity for users.

I am somewhat inclined to say that we should just accept this risk as it is for now, knowing that this isn't likely to be the thing that will kill Yggdrasil — we're much more interested in whether the routing scheme performs as advertised at scale. If Yggdrasil does succeed at fitting our goals then it may be a good candidate for a future version of IP which is not constrained by 128-bit addressing anyway.

@Arceliar Do you have any other thoughts on this?

[vikulin]

Me, @r4sas, @zhoreeq and @Revertron tested the accesibility of two nodes: mine was peering with German peers and R4SAS's used French one. Both nodes were running web servers with on the same ports. As result I noticed timeout issues while attempt to open web pages for the address http://[300:2300:7c67:6c3::1]:8080/ from USA node which is far away from the first and second one. Secondly, R4SAS took more priority from other locations which were trying to open mentioned URL. Sometimes Yggdrasil restart helps to resolve issue with timeout.
Summarising, I can say that an attacker is capable to take control for traffic going to certain service.

[Arceliar]

This is working as intended. The purpose of the /64 subnets inside of 300::/8 is for ygg devices to advertise routes so non-ygg devices can access resources on the network. Many devices (e.g. android phones) only support IPv6 address assignment through stateless address auto-configuration (SLAAC), which allows for a maximum prefix length of /64 bits.

The second byte of a ygg address is a counter of the number of leading 1 bits in the public key. The leading 1 bits and the first 0 bit are stripped from the start of the key, and then the rest of the key is used as the remaining bits of the IPv6 address or subnet prefix. So if you want to make these attacks more difficult, then you can brute force a stronger key (more leading 1 bits) to make attacks proportionally more difficult.

Hosting services on a 300::/8 address was never a good idea, since there are fewer bits of the key available. Those addresses are meant as a hack to let non-ygg devices connect to the network (which was every device not running linux at the time of release). We can't stop people from hosting services in that range anyway, but at the very least, people should brute force a stronger key if they care about security at all. The documentation section on configuration already mentions that /64 prefixes aren't secure without brute forcing a stronger key, and explains how to generate one, so I'm not sure what else we could really do...

[zhoreeq]

I guess, one of the concerns is if those collisions could break the application logic, i.e. sessions stop working. I didn't notice anything terrible though, the collision even worked as a load balancer.

[vikulin]

I guess, one of the concerns is if those collisions could break the application logic, i.e. sessions stop working. I didn't notice anything terrible though, the collision even worked as a load balancer.

@zhoreeq other peoples might be confused. This issue is not about load balancing but taking control Yggdrasil node traffic. I noticed deny of service issues which leads timeouts and target host unavailability. BTW this is a good starting point to think about some additional features as load balancing.

[neilalexander]

Just adding that this issue is also tracked in #33, although the best question from that was "do we really need /64 subnets at all?".

[Vort]

taking control Yggdrasil node traffic

@vikulin there are two different tasks:

1. Finding two keys with the same 3xx IP (proved as done).
2. Finding one key, which matches other's key 3xx IP (not done yet).

First one is important because of what @zhoreeq said.
And only second scenario is related to taking the control.
It is theoretically possible, but not yet proven.

@neilalexander as a hack, you may use above mentioned miner (one very important optimization is implemented there!) to get >308 addresses for everyone (new users I mean). It will take less than a second, but it will be a huge problem for bruteforcers.

[mxh69420]

could we add a separate api that can find the full public key from an ipv6 address? that way we can check the public key against one that you know is real, and give out the real public key with the ipv6 address.

[vikulin]

could we add a separate api that can find the full public key from an ipv6 address? that way we can check the public key against one that you know is real, and give out the real public key with the ipv6 address.

no, ipv6 is an hash of public key. so way to find ipv6->pub key directly.

[HKalbasi]

A mining step can solve this issue? A public key is valid for an ip if the hash matches the ip AND contains some leading zeros.

[jorektheglitch]

@Arceliar @neilalexander addresses with subnets collision was naturally generated in network recently (well, almost naturally, meant "not on purpose").
Theese addresses is 201:128::7e7d:7829:fbd0:972b and 201:128::84f1:6025:c7a6:2242 if it important.

Discovered in RU community chat, some guy complained about "my 300::/64 subnet does not work because of collision".

[Arceliar]

@Arceliar @neilalexander addresses with subnets collision was naturally generated in network recently (well, almost naturally, meatn "not on purpose").
Theese addresses is 201:128::7e7d:7829:fbd0:972b and 201:128::84f1:6025:c7a6:2242 if it important.

Discovered in RU community chat, some guy complained about "my 300::/64 subnet does not work because of collision".

This is why it's a bad idea to brute force vanity keys for a /64. I assume they were both trying to get a short prefix in this case, or maybe just a short address.

If you must use a /64 then, then you should be brute forcing a stronger key if possible (higher byte 2 in the address compressing 0 bits of the key), since otherwise a /64 is pretty much begging for a collision. That's why we compress bits in the first place, to give people a way to mitigate this if they really must use a /64 to make ygg reachable for an unsupported device (network printers etc).