Subject: sticking with 128-bit HITs (was Re: [Hipsec] SHA1 broken? )

From: [email-masked] (Tim Shepard)
Date: Thu Mar 17 11:24:00 2005

I said and have been been quoted as saying:

> > > Implications for HIP
> > > --------------------
> > >
> > > For HIP I think we need to be able to handle longer HITs, and I
> > > think we need a way of encoding in the HIT itself (in an
> > > unambiguous way) what hash function it is that is supposed to
> > > demonstrate the binding of the HIT to a public key.  (Otherwise, a
> > > weakness in one hash function might allow you to create a public
> > > key which can be "demonstrated" to be bound to a HIT that was
> > > created with a different hash function.)

After discussing this with a number of people at IETF62 who are
more of a cryptographer than I am, I am now not certain that we
need to make HITs any longer than they are now.  It may be
reasonable to have only around 120 bits of hash function output
incorporated into the HIT.

If that is secure enough, there may be significant advantages to
keeping HITs at a fixed length of 128 bits.

My understanding now is that 80 bits of good hash function output is
sufficient today, and with a simpleminded extrapolation of needing
another bit every 18 months (for Moore's law), 120-bits of good hash
function output should be good until around the year 2065.  So
perhaps we can save extending the HIT to be greater than 128 bits
for some future rev of the relevant protocols.  (Or are we trying to
design protocols that will last for a 100 years or more?)

I do however still believe that we need an unambiguous tag in the
HIT that tells you how it was generated (which hash function was
used, and perhaps how it was used).  IMHO we need at least four
bits of such a tag, and preferably a few more than that.

And there's also the desire some have to squeeze HITs into the
IPv6 unicast address space somewhere so that they can be passed
across IPv6 related APIs, so that may burn a few top bits of
the HIT.

			-Tim Shepard
			 [email-masked]

---

From: [email-masked] (Greg Perkins)
Date: Thu Mar 17 13:55:00 2005

I mostly agree with this but there may be an issue with long-term HI/HIT
use.  I like the idea of having a long-term HI, one I can hand-out because
it will last years.  In such a use-case it would be a pain if someone
managed to duplicate my HIT and thus I'd be forced to make a new HI/HIT and
hand it out all over again.  I don't consider this critical but it would be
nice if a HI could last for a long period of time IMO.

Also, I have started to consider whether or not it is a good idea to use an
HIT in the HIP exchange/control packets.  The use of a random HIP session
identifier (around 64-96 bits in length) might work out better.  During the
base exchange you'd have to send your HI in the I2 packet.  The R2 packet
would contain a session key to be used to mask your HIP session identifier.
The SPI index is then used to decrypt the encrypted HIP session indentifier,
that is included in every HIP packet header.  The HIP session identifier
(HSI) can then be used as the pointer to the HI and also as an index for
applications.  I am still mulling this over, and am really just being a
devil's advocate atm because I like HITs because of their cryptographic link
to the HI.  But, a HSI has the following benefits:

- an HSI is a temporary value so even if an attacker attains one he can only
do harm to the current HIP session
- fewer bits needed for identifier.  64 bits would be more than enough
because the value is session oriented and thus discarded after use.
Therefore, we could use 64 bits of the IPv6 source address space for an HSI
and use the other 64 bits for other uses like LSIs.
- using an XOR mask is a cheap yet strong method for protecting the HSI.
- for legacy applications you could probably make the HSI an IP address,
though I don't know how HIP could be signaled so that it does this in an
appropriate way (security gets thrown away of course)

In this scenario a HIT is used mainly for lookup at the DNS (or wherever)
and thus can use 128 or 256 bit hash as needed.

I now await a counter-argument in support of HITs.  The crypto-graphic link
to an HI is the strong-point IMO but with hashes under heavy attack, such a
link may not be all that secure.  Thus, we either need more bits, live with
less security or maybe use a different identifier.

Greg

----- Original Message ----- 
From: "Tim Shepard" <[email-masked]>
To: <[email-masked]>
Sent: Thursday, March 17, 2005 11:23 AM
Subject: sticking with 128-bit HITs (was Re: [Hipsec] SHA1 broken? )

> _______________________________________________
> Hipsec mailing list
> [email-masked]
> http://honor.trusecure.com/mailman/listinfo/hipsec
>

---

From: [email-masked] (Teemu Koponen)
Date: Thu Mar 17 16:46:02 2005

On Thu, Mar 17, 2005 at 02:10:35PM -0500, Greg Perkins wrote:

> that is included in every HIP packet header.  The HIP session
> identifier (HSI) can then be used as the pointer to the HI and also
> as an index for applications.  I am still mulling this over, and am
> really just being a devil's advocate atm because I like HITs because
> of their cryptographic link to the HI.  But, a HSI has the following
> benefits:

If I understood correctly, session identifiers, and their connection
to host identities, were known to peers only in your model.  However,
there might be (HIP-aware) middle-boxes in the path that could use an
index to host identities too. For them peer-only HI pointers create
challenges.

Teemu

--
[email-masked] # PGP, X.509v3: http://www.iki.fi/tkoponen/px.html
PGP fingerprint: 98D9 FD4D 7E63 11A4 074A 0D51 FFAA 007D C8D4 BD4C
X.509v3        : D854 0273 366F 53D1 BB35 C2B1 F534 8EC8 91B6 A9AD

---

From: [email-masked] (Pekka Nikander)
Date: Fri Mar 18 05:23:04 2005

On Mar 17, 2005, at 11:23, Tim Shepard wrote:
>>>> demonstrate the binding of the HIT to a public key.
>

I agree.  Tom may have a different opinion, though.

Let me try to put some of my thoughts in more concrete form:

1. It is far easier to handle fixed length entities in hardware
    than variable length ones.  AFAIK, that is one of the main
    reasons why IP has fixed length addresses.  As I can imagine
    one possible future where there is a considerable number of
    SPI-NAT like middle boxes in the network, I consider it highly
    desirable to optimise the HIP header to be suitable for
    hardware-based fast demultiplexing.

2. A software implementation that deals with a fixed length
    length entities is likely to have less bugs and likely to
    be faster than one that is optimised for handling variable
    length entities.

3. It is always possible to embded *shorter* identifiers into
    longer ones, if such need arises.

4. The identifiers must be long enough so that the probability
    of collisions is low enough.  From this point of view 64 bits
    would definitely be too short, and while 128 bits looks likely
    to be long enough, we don't know how many networked devices
    there will be in the future, may be up to 10^15 or 10^16.
    Considering that 2^120 \approx 10^36, there would still be
    about 10^20 identifiers per device.  As long as we impose
    no structure on the identifiers, that should be ok.  However,
    the margin is not that large any more, due to the birthday
    paradox.  Unless my math is completely flawed (which it may
    well be), we might expect to get problems with about
    107..108-bits long identifiers, leaving us with a margin of
    about 12 bits.  In other words, if my upper bound approximation
    of the number of devices (10^16) is off by more than two
    orders of magnitude, we may start having problems.

5. The computational complexity of forging an identifier is
    a different concern, separate from statistical uniqueness.
    Tim described it well:

> for some future rev of the relevant protocols.

So, due to the reasons above, I think that it looks like a good
idea to stick with fixed length identifiers and at least 120-bit
hashes for now.  That we can fairly easily fit into 128-bit
identifiers.  However, I would prefer to keep more bits for the
hash, just to decrease the probability of us getting later in trouble
due to a considerable number devices starting to have the same HIT
by chance.

> (Or are we trying to design protocols that will last for a
> 100 years or more?)

I would say that we should design our protocols so that they are
likely to remain usable for at least 50 years, and preferably
longer.  Hence, we should engineer in a way to extend the length
due to increased computing power in the future.  However, that
can well be a protocol version bump, IMHO.

> bits of such a tag, and preferably a few more than that.

I fully agree with the need for a tag.  It must also be understood
that the tag is a fundamental part of the identifier and cannot
be removed or changed without making the identifier a different one.

What comes to the tag length, we have here two competing forces:

   - Flexibility offered by a longer tag length
   - Smaller probability of collisions due to a longer hash length

> across IPv6 related APIs, so that may burn a few top bits of

With careful co-ordination we can most probably take care of
both the tag and the IPv6 value space considerations, at least
initially.

--Pekka

---

From: [email-masked] (Tim Shepard)
Date: Mon Mar 21 00:12:01 2005

>    - Smaller probability of collisions due to a longer hash length

The difference between 120 bits of hash and 124 bits of hash value
seems barely significant.

The difference between 4 bits of tag and 8 bits of tag seems very
significant.

So it seems to me that the 128-bit format for a HIT should be 8 bits
of tag, followed by 120 bits of hash value.

(Perhaps we could use (or reserve) one bit in the tag byte to indicate
 whether the HIT is 128 bits or 256 bits long.  Or have the
 code-points in the tag byte gain an implied length of the HIT when
 the code points are assigned.)

			-Tim Shepard
			 [email-masked]

---

From: [email-masked] (Pekka Nikander)
Date: Mon Mar 21 05:29:01 2005

> The difference between 4 bits of tag and 8 bits of tag seems very

I still have my doubts whether this is good for the architecture.
I have the strong feeling that 8 bits is too much for encoding
the hash function; in fact, something like 3 bits should do very
well.  On the other hand, I can live with having 3 or 4 bits for the
tag, 5 or 4 bits reserved, and 120 bits for the hash value.

Hence, I would suggest the following:

   0      5    7                                              127
   +------+----+------------------------------------------------+
   | Prfx | HA | Hash                                           |
   +------+----+------------------------------------------------+

    Prfx (5 bits) - Fixed prefix, TBD.  All other values reserved.

         Suggested prefix for testing: 01000

    HA (3 bits) - Hash algorithm.

       000 - SHA-1  (as currently defined)
             All other values reserved.

    Hash (120 bits) - Hash (as specified by HA) of the public key.

Comments?

--Pekka

---

From: [email-masked] (Pekka Nikander)
Date: Mon Mar 21 08:26:03 2005

Greg,

The ideas you have sound interesting and worth investigating,
but I'm afraid they fall beyond the current WG charter.  Hence,
maybe this discussion should be moved to the RG side?

In general, I think it would be a good idea if people worked
out on alternatives to the current HIP protocol.  The questions
about Service and Session identifiers are important, and IMHO
not well enough thought out in the current HIP architecture.

--Pekka

On Mar 17, 2005, at 21:10, Greg Perkins wrote:

> identifier

---

From: [email-masked] (Greg Perkins)
Date: Mon Mar 21 13:21:03 2005

Pekka,

You are correct.  These belong on HIP-RG.  I'll continue any email discusion
on this there.

Greg

---

From: [email-masked] (Tim Shepard)
Date: Thu Mar 24 09:53:00 2005

> Hence, I would suggest the following:

Do you intend to use the same set of assignments for HA if
you are using a different Prfx?  I would guess not.  It seems
to me any software written will want to dispatch on the value
of the top 8 bits taken as a single field.

So I think it would be better (yet equivalent in effect for now) to
explain this as the top byte being reserved to identify the type of
HIT (the hash algorithm used to produce the bottom 120 bits).  Simply:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Htype       |                                               |
   +-+-+-+-+-+-+-+-+                                               +
   |                  Hash (120 bits)                              |
   +                                                               +
   |                                                               |
   +                                                               +
   |                                                               |
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Then, we can allocate one or two code points for Htype (holding all others
in reserve) and you can perform whatever hacks you what to embed this
someplace in IPv6 unicast address space (to allow these to be passed
across IPv6 APIs.

   Htype (8 bits):

       01000000 - SHA-1 (as currently defined)
                  All other values reserved.

So I'm agreeing on the pattern of bits for the one code point you've
assigned (and probably the next one too), just suggesting a better (IMHO)
way to document it.

The IANA considerations would then be (if we want to be able to pass
these across IPv6 interfaces) that each Htype allocated takes a /8
chunk out of IPv6 address space.

That may seem to be a lot to ask for (such a large block out
of IPv6 address space).  However, I'm not sure such /8
allocations would need to be allocated to HIP exclusively.
Rather, it would be a handle that can be passed to refer to
that-which-hashes-to-this-value(-using-the-indicated-hash-algorithm).

(I'm thinking of that SIGCOMM'04 paper here.)

So having IANA set aside a /3 or so out of IPv6 address space
for this sort of thing seems reasonable.  (e.g. 4000::/3 ,
within which it could make up to 32 such /8 allocations.  And
if it ever exhausts this /3, it could use the next one.)

I realize I'm touching areas that are research here, but I
think what I've proposed that we do now would be OK and will
allow us to get this right (via some avenue of bit hackery)
when we are smarter later.

			-Tim Shepard
			 [email-masked]