Subject: [Hipsec] HIP Base draft

From: Petri Jokela <[email-masked]>
Date: Tue, 02 May 2006 12:36:40 +0300

Folks,

I have done some modifications to the base draft based on the 
Bellovin-Rescorla analysis. The current version ( 06-pre020506 ) can be 
found from:

http://hip4inter.net/drafts.php

A list of issues generated from the analysis follows including some
comments based on agreed fixes, proposed fixes, and things still to be
done. Issue numbers refer to roundup issue tracker ("Show all" on the
left side shows also closed issues):

http://hip4inter.net/cgi-bin/roundup.cgi/hip-base/index

/Petri

ISSUE 81: D-H group negotiation

I included the simple version of the negotiation in the text to initiate
some discussion (I'm not sure if I have covered all places in the text).
The DIFFIE_HELLMAN could contain one or two different values, and the
Initiator must select the stronger supported Group ID of those present 
in R1. (Is MUST too strong for this purpose?)

Modifications in the text:

4.1.3. Authenticated Diffie-Hellman Protocol
5.2.6. DIFFIE_HELLMAN

What if the hosts initiate the connection setup simultaneously? (Section
6.9, bullet 5) Do we run into new kinds of problem cases with the new
negotiation?

ISSUE 82: Hash algorithm dependency on the ORCHID draft

Still open. Any opinions on this? Shall we keep the dependency to the
ORCHID draft as it is now?

ISSUE 83: Key expansion: SHA1 wired in

This is changed to RHASH (Section 6.5)

ISSUE 84: Fixed 160-bit field for HMAC

5.2.9, 5.2.10: changed the HMAC into variable length field.
(The table in 5.2. contains still fixed length value for the parameter,
will be fixed in next release)

ISSUE 85: No key size negotiation (AES implies use of 128 bit keys)

A text modification in 6.5.

ISSUE 86: Mandatory AWES128CBC or NULL encryption

Text changed in 5.2.7

ISSUE 88: Vague statement: text change required

Text changed in 5.1.3

ISSUE 89: NOTIFY messages are not acknowledged

Text changed in: 5.3.6., 6.13., and Security considerations

ISSUE 90: Opportunistic mode needs clarification

4.1.6 added, Security considerations text changed. (+ some references
to this 4.1.6 added in various places in the document)

ISSUE 87: Pre-generating R1s

These ISSUE 87 texts are _not_ in the published pre-version document, I
just wrote some text to clarify the D-H value usage. More text is
needed.

4.1.4 HIP Replay protection

(changes required ?)

5.3.2 R1 - the HIP Responder Packet

    The Diffie-Hellman value is ephemeral, and one value SHOULD be used
    only for one connection.  Once the Responder has received a valid
    response to an R1 packet, that Diffie-Hellman value SHOULD be
    deprecated.  Because it is possible that the Responder has sent the
    same Diffie-Hellman value to different hosts simultaneously in
    corresponding R1 packets, also those responses should be accepted.
    However, as a defense agains I1 storms, and implementation MAY use
    the same Diffie-Hellman value for a period of time, for example, 15
    minutes. By using a small number of different puzzles for a given
    Diffie-Hellman value, the R1 packets can be pre- computed and
    delivered as quickly as I1 packets arrive.  A scavenger process
    should clean up unused DHs and puzzles.

6.7.1 R1 management

    All compliant implementations MUST produce R1 packets.  An R1 packet
    MAY be precomputed.  An R1 packet MAY be reused for time Delta T,
    which is implementation dependent, and SHOULD be deprecated and not
    used once a valid response I2 packet has been received from an
    Initiator.  Under I1 message storm, an R1 packet may be re-used
    beyond this limit.  R1 information MUST not be discarded until Delta
    S after T. Time S is the delay needed for the last I2 to arrive back
    to the Responder.

Security considerations

    Denial-of-service attacks take advantage of the cost of start of
    state for a protocol on the Responder compared to the 'cheapness' on
    the Initiator.  HIP makes no attempt to increase the cost of the
    start of state on the Initiator, but makes an effort to reduce the
    cost to the Responder.  This is done by having the Responder start
    the 3-way exchange instead of the Initiator, making the HIP protocol
    4 packets long.  In doing this, packet 2 becomes a 'stock' packet
    that the Responder MAY use many times, until some Initiator has
    provided a valid response to such and R1 packet.  During an I1 storm
    the host may re-use the same D-H value also beyond that point.  Using
    the same Diffie-Hellman values and random puzzle #I has some risk.
    This risk needs to be balanced against a potential storm of HIP I1
    packets.

_______________________________________________
Hipsec mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/hipsec

---

From: Pekka Nikander <[email-masked]>
Date: Wed, 3 May 2006 10:26:44 +0300

> There MUST NOT be more than six (6) HIP Suite-IDs in one HIP
> transform parameter.  The limited number of transforms sets
> the maximum size of HIP_TRANSFORM parameter.  As the default
> configuration, the HIP_TRANSFORM parameter MUST contain at
> least one of the mandatory Suite-IDs.  There MAY be a
> configuration option that allows the administrator to
> override this default.

I would suggest starting with the following:

The sender of a HIP transform parameter MUST make sure that there are  
no more than six (6) HIP Suite-IDs in one HIP transform parameter.   
Conversely, a recipient MUST be prepared to handle received transport  
parameters that contain more than six Suite-IDs.  The limited ....

[i.e. be strict in what you send and liberal in what you accept.]

--Pekka

---

From: Miika Komu <[email-masked]>
Date: Wed, 3 May 2006 16:17:38 +0300 (EEST)

On Tue, 2 May 2006, Petri Jokela wrote:

> Initiator must select the stronger supported Group ID of those present in R1. 
> (Is MUST too strong for this purpose?)

I think RECOMMENDED or at least SHOULD would be better for smaller devices 
with lower CPU capacity.

> 6.9, bullet 5) Do we run into new kinds of problem cases with the new

No? System behaviour in state I1-SENT, Table 3.

    | Receive I1          | If the local HIT is smaller than the peer   |
    |                     | HIT, drop I1 and stay at I1-SENT            |
    |                     |                                             |
    |                     | If the local HIT is greater than the peer   |
    |                     | HIT, send R1 and stay at I1_SENT            |

So, in the case of simultaneous base exchange, the host with the smaller 
HIT does not reply with a R1. Petri, could you verify this also?

(If I am wrong about this, we could also let the I2 carry multiple DH 
parameters and select max(intersection(R1_DH, I2_DH)) but I hope this is 
not necessary)

> ORCHID draft as it is now?

So, there are two problems: a) 120 bits and b) SHA-X wired in. What about 
modifying the the orchid draft so that SHA1 is just HASH() and actual hash 
algo is determined by the prefix? Then we need to rename all references to 
120 and 128 to (ID_LEN - PREFIX_LEN) and ID_LEN.

Then we need to have some recommended values for PREFIX_LEN, ID_LEN and 
HASH algo in the base draft. The PREFIX_LEN should 8, ID_LEN 128 and hash 
algos as SHA1-IME and SHA256. The two hash algos would require two 
different prefixes.

How would this sound?

-- 
Miika Komu              [email-masked]          http://www.iki.fi/miika/

---

From: Petri Jokela <[email-masked]>
Date: Thu, 04 May 2006 10:47:16 +0300

Pekka Nikander wrote:
> The sender of a HIP transform parameter MUST make sure that there are no 
> more than six (6) HIP Suite-IDs in one HIP transform parameter.  

Ok, I added this.

/petri

---

From: Julien Laganier <[email-masked]>
Date: Mon, 8 May 2006 13:38:54 +0200

On Wednesday 03 May 2006 15:17, Miika Komu wrote:
> > Still open. Any opinions on this? Shall we keep the dependency to
> > the ORCHID draft as it is now?
>
> So, there are two problems: a) 120 bits and b) SHA-X wired in. What
> about modifying the the orchid draft so that SHA1 is just HASH()
> and actual hash algo is determined by the prefix? Then we need to
> rename all references to 120 and 128 to (ID_LEN - PREFIX_LEN) and
> ID_LEN.
>
> Then we need to have some recommended values for PREFIX_LEN, ID_LEN
> and HASH algo in the base draft. The PREFIX_LEN should 8, ID_LEN
> 128 and hash algos as SHA1-IME and SHA256. The two hash algos would
> require two different prefixes.
>
> How would this sound?

I think that's what the draft currently recommends. The text in the 
security cons. sections is:

   All mechanism using ORCHIDs MUST use exactly the same mechanism for
   generating a ORCHID from the input bitstring.  Allowing different
   mechanisms, without explicitly encoding the mechanism in the ORCHID
   itself, would allow so called bidding down attacks.  That is, if
   multiple different hash functions were allowed in constructing
   ORCHIDs in a given shared name space, and if one of the hash
   functions became insecure, that would allow attacks against even
   those ORCHIDs that had been constructed using the other, still 
   secure hash functions.

   Due to the desire to keep the hash output value as long as  
   possible, the present design allows only one method for
   constructing ORCHIDs from input bitstrings.  If other methods
   (perhaps using more secure hash functions) are later needed, they
   MUST use a different prefix. Consequently, the suggested method to
   react to the hash result becoming too short, due to increased
   computational power or to the used hash function becoming insecure
   due to advances in cryptology, is to allocate a new prefix and
   cease to use the present one.

   As of today, SHA-1 applied in conjunction with a proper expansion
   function of the hash input is considered as satisfying the second-
   preimage resistance requirement [I-D.irtf-cfrg-sha1-ime].  Hash
   output of at least 100 bits, but preferably up to 120 bits, is
   considered to have a low enough probability of collisions.

How would you like that to be changed?

--julien

---

From: Julien Laganier <[email-masked]>
Date: Mon, 8 May 2006 14:30:34 +0200

> rename all references to 120 and 128 to (ID_LEN - PREFIX_LEN) and

One more thought w.r.t. to b) :

IMHO saying that SHA1 is hardcoded in the ORCHID draft is more less 
like saying that SHA1 is hardcoded in the SHA1 RFC. 

The ORCHID draft defines the allocation of _a prefix_ to store ORCHIDs 
based on SHA1. if SHA1 ORCHIDs are deemed unsecured then one can 
choose a new hash function X and define HASH_X ORCHIDs which would be 
stored under a new prefix to be chosen (that is explained in sec-cons 
of the draft). It would be the role of another draft to define that 
prefix and that hash X.

Perhaps this should be stressed more strongly in the draft; any text 
suggestion is welcomed.

--julien

---

From: Miika Komu <[email-masked]>
Date: Mon, 8 May 2006 15:37:05 +0300 (EEST)

> Perhaps this should be stressed more strongly in the draft; any text

First, I'll take back my original suggestion. Second, if there is going to 
be a 02 version (not sure if it is necessary), I'd just clarify section 2
(Cryptographic Hash Identifier Construction). In the algorithm 
description, SHA1 and 128 bits look like they were hardcoded (hence my 
original comments), but they are clarified in the following text.

---

From: marcelo bagnulo braun <[email-masked]>
Date: Thu, 11 May 2006 14:44:27 +0300

> of the draft). It would be the role of another draft to define that

but this would require an additional /8 allocated to the orchids, right?

i mean, in order to specify what hash algorithm is used, you need bits 
in the address, the question is whether you take this bits out of the 
prefix or out of the crypto part. If you take them out of the crypto 
part, the result is that the security is weaker (less hash bits), but 
if you take them out of the prefix part, this means that you need to 
use more global address space for this, which may well be unacceptable

In this global address space conservation/security tradeoff i would 
suggest to preserve global address space and use some bits (e.g. 3 
bots) from the hash part to encode the hash function used...

regards, marcelo

---

From: Julien Laganier <[email-masked]>
Date: Thu, 11 May 2006 14:37:54 +0200

Hi Marcelo,

On Thursday 11 May 2006 13:44, marcelo bagnulo braun wrote:
>
> > IMHO saying that SHA1 is hardcoded in the ORCHID draft is more
> > less like saying that SHA1 is hardcoded in the SHA1 RFC.
> >
> > The ORCHID draft defines the allocation of _a prefix_ to store
> > ORCHIDs based on SHA1. if SHA1 ORCHIDs are deemed unsecured then
> > one can choose a new hash function X and define HASH_X ORCHIDs
> > which would be stored under a new prefix to be chosen (that is
> > explained in sec-cons of the draft). It would be the role of
> > another draft to define that prefix and that hash X.
>

If we decide to allocate an 8 bits for SHA1 ORCHIDs yes. However I 
don't think we reached yet any sort of agreements on the *right* size 
of the prefix. My educated guess is that it seems fine as long as we 
have at least 96 bits to store the hash output (i.e. prefix is 
a /32). Others might disagree.

> i mean, in order to specify what hash algorithm is used, you need
> bits in the address, the question is whether you take this bits out
> of the prefix or out of the crypto part. If you take them out of
> the crypto part, the result is that the security is weaker (less
> hash bits), but if you take them out of the prefix part, this means
> that you need to use more global address space for this, which may
> well be unacceptable

Right. I think we discussed that a while ago. I try to summarize the 
conclusion we once reached below...

> bots) from the hash part to encode the hash function used...

Actually as long as we did not decide on the prefix length, doing one 
way or another (i.e. allocating new prefixes for store new hashes, or 
reserving bits under the prefix to indicate the prefix) is the same 
thing.

You propose to have plen = 8, and then 3 bits for hash, that would let 
us 117 bits for the hash while allowing for 8 different hash 
functions.

But it would be exactly equivalent to use plen = 11, have as much bits 
for the hash (117), and reserve a new prefix per new hash function, 
_as long as we do not need to define more than 8 different hash 
functions for ORCHIDs_

I think the real issue here is to evaluate how many different hash 
functions we will need in the future.

Once you're settled on that doing it one way (single prefix per hash 
function, as in the ORCHID I-D) or the other way (hash function 
encoded by some bits under the prefix, as proposed by some people) is 
IMO exactly equivalent. It's a matter of taste, and on that matter I 
think I'm tasteless :-)

Best,

--julien

> regards, marcelo
>
> > Perhaps this should be stressed more strongly in the draft; any
> > text suggestion is welcomed.
> >
> > --julien
> >

---

From: marcelo bagnulo braun <[email-masked]>
Date: Thu, 11 May 2006 15:50:03 +0300

> a /32). Others might disagree.

ok, i wasn't aware of this. I thought that the idea was to assign a /8 
so i didn't thought it was acceptable to use even more global address 
space for the orchids to support another hash function

but if you think that a /32 per hash function is enough i strongly 
suggest to state it clearly in the draft, since it would be much easier 
to get it accepted than as it is written now where it seems that the 
proposal is to ask for a /8 allocation for this experiment (you may 
even ask for a RIR allocation for experimental purposes, of a /30 or 
similar)

> IMO exactly equivalent. It's a matter of taste, and on that matter I

agree

regards, marcelo

---

From: Julien Laganier <[email-masked]>
Date: Thu, 11 May 2006 15:09:03 +0200

On Thursday 11 May 2006 14:50, marcelo bagnulo braun wrote:
> > If we decide to allocate an 8 bits for SHA1 ORCHIDs yes. However
> > I don't think we reached yet any sort of agreements on the
> > *right* size of the prefix. My educated guess is that it seems
> > fine as long as we have at least 96 bits to store the hash output
> > (i.e. prefix is a /32). Others might disagree.
>
> ok, i wasn't aware of this. I thought that the idea was to assign a
> /8 so i didn't thought it was acceptable to use even more global
> address space for the orchids to support another hash function
>
> suggest to state it clearly in the draft, since it would be much
> easier to get it accepted than as it is written now where it seems
> that the proposal is to ask for a /8 allocation for this experiment
> (you may even ask for a RIR allocation for experimental purposes,
> of a /30 or similar)

Well, I'm not so sure about that. The current draft says:

   As a baseline (TO BE DISCUSSED), we propose an 8-bit prefix to be
   allocated from the 1000::/4 block.

IIRC, none of the people opposing ORCHIDs did so based on the length 
of the prefix allocation, and we did not discuss it much either. 
Rather, they opposed the idea of "stealing" locator space to store 
unroutable identifiers (and flat, furthermore ;-) 

--julien

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 15 May 2006 16:21:25 -0700

> -----Original Message-----
> From: Petri Jokela [mailto:[email-masked]] 
> Sent: Tuesday, May 02, 2006 2:37 AM
> To: HIP
> Subject: [Hipsec] HIP Base draft
> 
> Folks,
> 

Petri and others, I have some comments on the deltas from -05 to
-06pre020506.  I will respond to the other open issues in a separate
message.

1.  HIT format (Section 3.1)

I found this to be ambiguous.  From the current -06pre draft:

       0                                                          2
       0 1 2 3 4 5 6 7 8  ...                                     7
      +-+-+-+-+-+-+-+-+-+-//-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Prefix      |             Hash                           |
      +-+-+-+-+-+-+-+-+-+-//-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Prefix (8 bits) - Fixed prefix, TBD (0x11, TO BE DISCUSSED), as
      defined per [22].

      Encoding (120 bits) - Encoding of the public key and KHI ORCHID
      context identifier as defined per [22].

As I understand it, the ORCHID is the entire 128-bit quantity, but the
above description implies to me that the HIT is a Prefix + ORCHID (btw,
"Encoding" does not match with "Hash" in the figure).

I think we have the situation now that a HIT is a specific type of
ORCHID, differentiated from other ORCHIDs by use of the Prefix and
Context ID in the ORCHID generation.  Maybe the draft should state this
clearly.  Further, if KHI is intended to be normative for this draft,
then HIP draft maybe should just describe HITs here as "a type of
ORCHID, based on a SHA1 hash of the host identity (Section 2 of [22])"
and not try to imprecisely replicate the specification text.

As an aside, from the ORCHID draft:

                As a baseline (TO BE DISCUSSED), we propose taking
                <n> middlemost bits from the SHA1 output.

this seems like a dangerous way to specify it-- what does "middlemost"
mean?-- should clarify exactly which bits you mean.

Finally (also an ORCHID comment), it seems that one can determine the
hash function used for the ORCHID by inspection of the ORCHID (the
Prefix identifies this), but one cannot determine whether it is a HIT or
other usage (e.g. TMI) because the context identifier is buried in the
hash input-- is this intentional or of any practical concern?

2. RHASH algorithm

It is not directly stated in the draft how RHASH is determined.  It
should state clearly something like the following:

"RHASH can be determined by inspecting the Prefix of the ORCHID (HIT).
The Prefix value has a one-to-one mapping to a hash function."  Maybe
this could be added to the definition in Section 2.3. 

* Note, this requires resolution of the issue of "Prefix + hash ID" vs.
"longer prefix" thread where Julien lost his taste.

3.  Text in section 4.1.3

   When the Initiator receives an R1, it gets one or two Responder's
   public Diffie-Hellman values.  If there are two values, it selects
   the stronger value of these, and computes the Diffie-Hellman session
   key.  

   ^^^^^
   I think you mean to say "selects the value corresponding to the
strongest supported Group ID"

Tom

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Tue, 16 May 2006 08:20:47 -0700

Responding now to the issues below.

> in R1. (Is MUST too strong for this purpose?)

I don't know what the criteria are for "MUST"-- I think SHOULD would
suffice since it doesn't affect interoperability, but maybe MUST is
appropriate as a really strong hint to implementors.

> 6.9, bullet 5) Do we run into new kinds of problem cases with the new

I'll respond to Miika's post on this.

> ORCHID draft as it is now?

This handled in another thread-- I do not have a strong opinion.  I do
not know what the way forward is on the ORCHID draft since it doesn't
seem to be generating any current activity.

I don't have any comment on (am OK with) the other issue resolutions.  I
agree with Pekka's proposal on HIP transform parameter.

Tom

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Tue, 16 May 2006 09:51:47 -0700

Responding to the question about whether the current specification is
correct for cases in which two hosts are trying to establish an
association simultaneously to one another:

>     |                     |                                   
>           |

I agree.  The normative text is in section 6.7:

   3.  If the Responder is in I1-SENT state, it must make a comparison
       between the sender's HIT and its own HIT.  If the sender's HIT is
       greater than its own HIT, it should drop the I1 and stay at I1-
       SENT.  If the sender's HIT is smaller than its own HIT, it should
       send R1 and stay at I1-SENT.  The HIT comparison goes similarly
       as in Section 6.5.

Note that there may be some transient failure cases when the host with
the smaller HIT is having trouble reaching the host with the larger HIT
for some reason (such as when the two hosts are using different locators
in the base exchange), but that is a multihoming case outside the scope
of this spec, probably is relatively rare, and probably just incurs some
timeouts before recovering correctly.

It might be worth clarifying:  s/its own HIT/its own (i.e., the
receiver's) HIT/

I decided to check the rest of the existing text on collisions by
examining some sketched out collision cases.  While nothing is
technically wrong as currently stated, I would suggest some
clarifications (below).

***********

In Section 6.8 (R1 processing):

"  The following steps define the conceptual processing rules for
   responding to an R1 packet:

   1.   A system receiving an R1 MUST first check to see if it has sent
        an I1 to the originator of the R1 (i.e., it has a HIP
        association that is in state I1-SENT and that is associated with
        the HITs in the R1.  IP addresses in the received R1 packet
        SHOULD be ignored and the match SHOULD be based on HITs only).
        If so, it should process the R1 as described below.  Note that
        when the connection was initialized in opportunistic mode, HITs
        cannot be used, but the Initiator must rely on the Responder's
        IP address in the received R1 packet.  See also "HIP
        Opportunistic Mode" (Section 4.1.6)."

I would suggest the following, to avoid saying too much constraining
future definition of opportunistic mode:

   1.   A system receiving an R1 MUST first check to see if it has sent
        an I1 to the originator of the R1 (i.e., it has a HIP
        association that is in state I1-SENT and that is associated with
        the HITs in the R1).  Unless the I1 was sent in opportunistic
        mode (see also "HIP Opportunistic Mode" (Section 4.1.6)), IP 
        addresses in the received R1 packet SHOULD be ignored and the
        match SHOULD be based on HITs only.  If a match exists, the
system
        should process the R1 as described below.  

Also, I came across this sentence later in this section:

"  8.   The system SHOULD attempt to validate the HIT against the
        received Host Identity."

I couldn't find anywhere in the draft where "validate the HIT" is
explained, so it might be worth adding a phrase for clarity:  "by using
the received Host Identity to construct a HIT and verify that it matches
the Sender's HIT."

*************

In section 6.9 (I2 processing):

"  4.   If the system is in the I2-SENT state, it makes a comparison
        between its local and sender's HITs (similarly as in
        Section 6.5).  If the local HIT is smaller than the sender's
        HIT, it should drop the I2 packet.  Otherwise, the system should
        process the received I2 packet."

I would add to the end of this last sentence "and drop any previously
derived Diffie-Hellman keying material Kij it might have formed upon
sending the I2 previously.", just to be clear.

"  5.   To avoid the possibility to end up with different session keys
        due to symmetric operation of the peer nodes, the Diffie-Hellman
        key, I, and J selection is also based on the HIT comparison.  If
        the local HIT is smaller than the peer HIT, the system uses peer
        Diffie-Hellman key and nonce I from the R1 packet received
        earlier.  The local Diffie-Hellman key and nonce J are taken
        from the I2 packet sent to the peer earlier.  Otherwise, it uses
        peer Diffie-Hellman key and nonce J from the just arrived I2.
        The local Diffie-Hellman key and nonce I are the ones that it
        sent ealier in the R1 packet."

The text above only makes sense ("R1 packet received earlier") in a
collision scenario.  Normally, when a responder receives I2, it has not
previously received an R1.  I would therefore suggest merging the above
#5 as a continuation of #4 (i.e., it applies only in the case where the
receiver is in I2-SENT state).

If we merge #5 with #4, then we can add a new #5 that clarifies, in the
case of being in I1-SENT and receiving I2 that matches the HITs in its
previous I1, that the I1 retransmission timer is stopped.  Something
like:

   5.   If the system is in the I1-SENT state, and the HITs in the I2
        match those used in the previously sent I1, the system uses this
        received I2 as the basis for the HIP assocation it was trying 
        to form, and stops retransmitting I1 (provided that the I2
passes
        the below additional checks).

Tom

---

From: Petri Jokela <[email-masked]>
Date: Thu, 18 May 2006 15:15:34 +0300

> Responding now to the issues below.

Tom, thanks for the comments.

I have made some changes to the base draft and new pre-version with date 
180506 is available at

/Petri