Subject: RE: Advantages and disadvantages of using CB64 type of identifiers

From: "Christian Huitema" <[email-masked]>
Date: Fri, 2 Jul 2004 10:21:38 -0700

> My understanding is that SeND chose different IIDs for different
prefixes
> but that might be overkill. If the IID is not a function of the prefix
> it would enable redirection by a resourceful attacker
> by precomputing 2^64 public/private keys that hash to all 2^64 IIDs.
> If the content of the packets are encrypted the redirection would not
> provide access to the content; it could only be used for DoS or for
> gathering the content for cryptoanalysis.

There are two issues: catalog attacks and privacy implications. I have
already expressed my reservations about the privacy effects of having
unique identifiers in addresses. I would certainly not recommend that my
company ships anything like that.

> A while back Jari Arkko computed the amount of space needed to store
> 2^64 precomputed keys, and the storage space was a few buildings the
size
> of the former world trade center buildings I think.

You do not need to compute 2^64 keys to start having an effect. Suppose
that there are N users in the system, and that the bad guys have
computed a catalog of M keys. The average number of hits that a catalog
of size N will achieve is approximately NxM/2^64. There are currently at
least 500M Internet users, it is reasonable to expect some growth, so we
can set N to about 1 billion -- 2^30. This means you need M=2^34 to get
at least one hit. That is probably less than a Terabyte of data, i.e.
pretty soon a single hard disk.

Everybody should be convinced that, when it comes to cryptography, 2^64
is actually a small number. SEND alleviates this risk by
cryptographically link a public key to the entire 128 bits of the
address. This is NOT overkill.

-- Christian Huitema

---

From: marcelo bagnulo braun <[email-masked]>
Date: Sat, 3 Jul 2004 15:01:43 +0200

Hi Christian,

> company ships anything like that.

i don't fully understand why do you think that having an identifier in 
the address is worse than current IPv4 situation (where the id and 
locator are one, and multihomed sites have a single address) or the 
current IPv6 situation (i guess that something similar to privacy 
extensions could be achieved by periodically creating new keys hence 
new identifiers)

> at least one hit.

Yes but how useful would this single hit be?
i mean this hit is likely to correspond with an identifier of an 
unknown host.
i guess that an attacker would be interested in knowing the identifier 
of a specific victim, right?

perhaps we need (at least i need) to understand the potential attacks a 
bit more...

>  That is probably less than a Terabyte of data, i.e.

i still don't have an opinion about this being an overkill or not.

regards, marcelo

---

From: Brian E Carpenter <[email-masked]>
Date: Sun, 04 Jul 2004 09:57:23 +0200

Christian Huitema wrote:
...
> address. This is NOT overkill.

But is 2^80 big enough? Omitting the /48 prefix from the crypto would
avoid the hash changing when rehoming to a different prefix.

    Brian

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 5 Jul 2004 02:41:18 -0700 (PDT)

> company ships anything like that.

We definitely need to take the privacy concerns into account.
But those concerns might imply the need to change the identifier
periodically, for instance every 24 hours, for some type of communication
such as web browsing client. If we need that, the same approach can be
used when the prefixes change without requiring that the IID is
different for every prefix. 

> pretty soon a single hard disk.

But how would an attacker make use of these precompleted keys?
A possibility is that the attacker knows that all hosts connect
to some well-known http server and the attacker launches a pre-meditated
attack against that web server for all 2^34 prefixes; presumably
the attacker would also need to maintain the state at that server
until one of the hosts try to connect. If we assume that the server
discards the multihoming state after 5 minutes this presumably implies
that the attacker would need to send at least one packet per identity
every 5 minutes i.e. about 50 million packets per second.
And if not every host on the planet connects to a single server then
this isn't sufficient to impact even one host on average.

To use the keys to lauch an attack against communication in progress the
attacker would need to predict when one of the hosts for which it has a key
would communicate with another host with a particular IP address.
And solution which use some context ID would make it
even harder for off-path attackers to take advantage of the keys they've
gathered.

> address. This is NOT overkill.

For crypto in general, I agree.
But I'm not convinced it is required to require the inclusion the prefix
in a CB64 scheme. The hash extension in the send-cga spec is probably
a better approach to make it harder to brute force CGAs.

  Erik