Subdomain name length limit for .baseXX.i2p addresses vs. PQ bday. atk. security margins?

Misc topics about I2P
Post Reply
User avatar
Posts: 9
Joined: 18 Mar 2023 12:17

Subdomain name length limit for .baseXX.i2p addresses vs. PQ bday. atk. security margins?

Post by FreefallHeavens »

At some point in the future I2P will need to implement post-quantum security algorithms for, among other things, digital signatures. I am not going to discuss what algorithms would be appropriate here.

I am here to discuss the implications for this when it comes to destination address encoding that is meant to be intelligible for network applications.

Currently domain name specification stipulates that each element name uses up to 63 characters consisting of 0-9, a-z, and dashes if used anywhere between the first and last character.

The current URL format is {some_base32_address}.b32.i2p where the address is a 52 character conversion of the SHA-256 hash of the public key. This mechanism is similar to how a cryptocurrency address is automatically authenticated to its private key.

Consider a birthday attack where an attacker can generate private keys over and over until one key's b32 address matches any other previously generated key. At that point the attacker can use two different private keys to claim the same b32 address.

Because we have no constraint on a given exact b32 address and any goes, the complexity of that is square root of the total space. In our current implementation this space is 2^256 so it takes 2^128 attempts. This is considered a good security margin.

With quantum computers involved in birthday attacks, the complexity is cut down to not 1/2 but 1/3. If the current address scheme is preserved this leaves about 85.3 bits of security which is within the realm of possibility to compute for a major state.

To increase that security back up to 128 bits we need a 384 bit address and there are many hashes and schemes to produce that. The problem is storing this in an URL.

As a base32 address this increases in length from 52 to little over 76 characters which is too big to fully store. Given the range of characters valid in an address we can use base36 instead and shorten this to little over 74.

This is still too big to store. Trimming it down to 63 characters can be done, resulting in a ~325-bit address space yielding about 108.5 bits of security vs quantum birthday attacks.

Attempting to reshuffle the hash out from the subdomain and up into the domain name in the form of {addressPart1}.base36-{addressPart2}.i2p opens the can of worms of how browsers treat cookies and cache on what they perceive to be the same domain, should {addressPart2} ever match another site's.

So if we stick to the subdomain we have a quantum birthday attack difficulty of about 2^108.5 which is not all that bad but it's cutting it close and the next few decades of computing may make it practical for a major state actor.

It should be noted that the applicable scope of such attacks will be very limited as a malicious actor would need to somehow convince an incoming registrant to use one of the compromised keys in their pair to later begin broadcasting with their other in order to hijack their traffic, and getting in to plant a private key is as bad as getting in to steal one, it's basically game over either way. But attackers are inventive and with this new possibility at their disposal someone might come up with something ingenious.

As far as I know there is no easy way around this limitation unless URL standards change and given how slow the internet is to adopt standards and ossification in middleware, I don't really see it happening. Am I missing anything here or is this actually a problem?
Post Reply