Subject: Re: HIP and IKE -- was -- Re: [Hipsec] Moving the base spec forward

From: Petri Jokela <[email-masked]>
Date: Fri, 01 Oct 2004 10:21:16 +0300

Yogesh Prem Swami wrote:

> Okay, the minimal changes required in the present HIP key exchange is
> to just add a HMAC(g^xy, HOST_ID) in message-3 and adds HOST_ID in
> the HMAC of message 4 (shown in the message exchange below). Note
> that the present protocol in the draft looks fairly secure, but as SIGMA
> paper points out encryption is not the right method to prove possession
> of session key (but the attack that the paper describes in the presence
> of stream cipher doesn't apply here). So while the encrypted token
> { PUBLIC_KEY-I, Domain-ID-I }_g^ri and the signature over this token
> guarantees that identity mis-binding attack cannot be carried out,
> it's still better to use HMAC, IMO. (Besides we have a proof that
> HMAC based scheme is secure.)
> 
> I have also added nonce-I and nonce-R in all these message. This is
> important to allow parallel SA creation, and allow cases where both
> initiator and responder choose pre computed g^i and g^r (this can
> happen, unless the draft explicitly prevents it). The nonce should
> be used in deriving the session keys.

Currently we have the ECHO REQ/REPLY in R1/I2. This nonce would replace 
it. Any opinions on this list?

> So the key exchange with minimum change should look something like:
> 
> 1. I->R: NCN-I, 0, HIT-I, [HIT-R]
> 
> 2. R->I: NCN-I, NCN-R, HIT-R, HIT-I, g^r, PUBLIC_KEY-R, Domain-ID-R
>          SIG( HIT-R, g^r, PUBLIC_KEY-R)
> 
> 
> 3. I->R: NCN-I, NCN-R, HIT-I, HIT-R, SPI-I, [R1_COUNTER], g^i,
>          { PUBLIC_KEY-I, Domain-ID-I }_g^ri,
>          SIG( HIT-I, HIT-R, SPI, g^i,
>          { PUBLIC_KEY-R, Domain-ID }_g^ri, )
>          *HMAC(g^xy, HIT-I, PUBLIC_KEY-I, Domain-ID-R)*
> 
> 4. R->I: NCN-I, NCN-R, HIT-R, HIT-I, SPI-R, SIG(HIT-R, HIT-I),
>          HMAC(g^xy, HIT-R, SPI-R, *HOST_ID-R*) /* HMAC content
>                                                   has changed */
> 

According to the new HMAC stuff (including NONCE parameter instead of 
ECHO parameters), packets would look something like:

NONCE parameter contains both nonce-I and nonce-R values, zero if not 
available.
HOST_ID contains both the PUBLIC_KEY and the Domain-ID

I1:
       IP ( HIP ( NONCE ) )

R1:
       IP ( HIP ( NONCE,
                  [ R1_COUNTER, ]
                  PUZZLE,
                  DIFFIE_HELLMAN,
                  HIP_TRANSFORM,
                  ESP_TRANSFORM,
                  HOST_ID,
                  HIP_SIGNATURE_2 ))

R1 signature: HIP packet with the following fields zeroed: HIT-I, header 
checksum and Random #I. NONCE also zeroed to support precreated R1s?

I2:

       IP ( HIP ( NONCE,
                  SPI,
                  [R1_COUNTER,]
                  SOLUTION,
                  DIFFIE_HELLMAN,
                  HIP_TRANSFORM,
                  ESP_TRANSFORM,
                  ENCRYPTED { HOST_ID },
                  HIP_SIGNATURE,
                  HMAC ) )

I2 signature: everything covered
I2 HMAC: (g^xy, HIT-I, HOST_ID(initiator) )

R2:

       IP ( HIP ( NONCE,
                  SPI,
                  HMAC,
                  HIP_SIGNATURE ) )

R2 HMAC: (g^xy, HIT-R, SPI-R, HOST_ID(responder) )

> Couple of observations about this key exchange:
> 
> A) The identity of Responder cannot be concealed even against the
>    passive attack. The HOST_ID in message-2 is required so that the
>    Initiator can get the public-key to verify the SIGNATURE from
>    responder.
> 
> B) The identity of Initiator cannot be concealed against an active
>    attacker unless g^r is covered in SIGNATURE calculation in
>    message-2. (So keep section-7 description and change section-4 text)
> 
> (A) and (B) together means that if we want to get responders ID
> protection then we need to severely reorganize the messages.

I think that at this point we are not willing to make radical changes. 
Any opinions?

> Yogesh

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

---

From: Miika Komu <[email-masked]>
Date: Tue, 5 Oct 2004 10:37:01 +0300 (EEST)

> it. Any opinions on this list?

Seems like this won't affect the stateliness of responder, so I guess the
change is ok.

> I think that at this point we are not willing to make radical changes.

Agree.

-- 
Miika Komu              [email-masked]          http://www.iki.fi/miika/
_______________________________________________
Hipsec mailing list
[email-masked]
http://honor.trusecure.com/mailman/listinfo/hipsec

---

From: Pekka Nikander <[email-masked]>
Date: Fri, 8 Oct 2004 15:20:23 +0300

Yogesh,

Trying to finally cover this message, sorry for the delay.
Anyway, thanks a lot of taking this up and writing this.

> HMAC based scheme is secure.)

Sounds good.

> be used in deriving the session keys.

As was discussed in other messages, parallel SAs between any
given pair of HITs is a non-goal.  I'd like to understand better
your reference to pre-computed D-H keys by both parties.  Would
you care to explain?

>          HMAC(g^xy, HIT-R, SPI-R, *HOST_ID-R*) /* HMAC content

If I understand correctly, and leaving aside the issue of nonces,
the only differences are the addition of HMAC to I2 and the
change of the HMAC contents in R2.  They seem OK to me.

> o  In the draft it's important to say that the responder should keep
>    the random value r for at least 2*MSL  (and possibly longer) from 
> the
>    last time it sent message 2. In case Message 3 arrives after 2*MSL,
>    and no random number r can be found, it should be dropped and an 
> ICMP
>    message should be sent. If the Initiator receives an ICMP after
>    sending message-3, it should not assume that the responder sent
>    the message, and should not close that session. An Initiator
>    MAY however start with a new parallel I1 with a new nonce value.

Sounds OK to me.  I guess most of this is already implied by the
draft, but it would be much better to be explicit.  Petri your Yogesh,
could you provide us with some concrete proposal?

>    Initiator can get the public-key to verify the SIGNATURE from

Yes.  One way to address this has been discussed in the BLIND
paper by Jukka Ylitalo and me, in this year's Cambridge Security
Protocols Workshop.  See Jukka's or my publications web pages.

>    message-2. (So keep section-7 description and change section-4 text)

Sounds OK to me.

> protection then we need to severely reorganize the messages.

Yes.  We are aware of that.  See the above mentioned paper.

> One simple thing one can do is to only send the public-key and
> in message-2 (and leave Domain-ID-R field completely out).

That doesn't help much, since in HIP the public key IS the real
identifier.  The hostname/NAI is only considered as auxliary
information.  You may learn the association between the public
key and the hostname/NAI also from the DNS or some other databse.

>  Later,
> Responder can put Domain-ID as encrypted in message-4 and let Initiator
> verify it against the MAC received in message-2. The advantage is that
> we can now protect the identity of Initiator against passive attacker
> and the Identity of responder against Active attackers. The 
> disadvantage
> is that the Initiator's ID cannot be protected against active 
> attackers.

It was a deliberate choice to err on protecting the initiator's
privacy more than the responder's.

> Note that protecting the Public-Key alone without Domain-ID is not
> that useful. The worst thing that an attacker can do by stealing the
> public key is to register it under her own name (i.e., Eve takes
> Alice's public key and puts it in DNSsec under Eve's name, assuming
> DNSsec doesn't do proof of possession checks).

Binding of public keys and external identifiers, such as hostnames
or NAIs, is currently outside the scope of the WG charter.  The
architectural stance is that the public key is the primary identifier,
and getting the public key from a human understandable name is a
separate problem.

> But the HMAC binding to
> name in  SIGMA prevents from attacks that can result from this kind of
> behavior,  so it's not that useful to protect the public-key. Note 
> that this is the reason I have added HOST_ID in message-4. HMACing 
> only HITs will get us in trouble.

I don't see any adverse effects of adding the HOST_ID to the
HMACs, even though I doubt its value.  The kind of identity
stealing attack that you describe belongs, from an architectural
point of view, beyond the HIP base spec.  On the other hand,
if we can this easily provide some extra security, then why not.

In summary:  I am in favour of making these two changes:
   - adding a HMAC to I2
   - changeing the R2 HMAC contents

I still haven't been convinced about the nonces.  The multiple-SA
argument doesn't hold as it is a non-goal.  I haven't seen
explicit argumentation about using nonces for keymat generation.

--Pekka

---

From: Yogesh Prem Swami <[email-masked]>
Date: Sun, 10 Oct 2004 21:40:01 -0500

Hi Pekka,

Please see in line:

> your reference to pre-computed D-H keys by both parties.  Would

Let's say, both the sides, Alice and Bob, use precomputed values of g^x
and g^y. Let's also say that both Alice and Bob update their g^x and g^y
only once every hour. That means, during that one hour period, no matter
how many HIP exchange Alice and Bob do, they will end up with the same
Keys (the KEYMAT only contains g^xy and HIT-I and HIT-R all of which
will be the same).

This can have quite a few security implications. For example, replay
protection will become weak, because an attacker can now inject packets
from previous sessions and simple sequence numbers and HMAC based
authentication will not be able to detect it (Assuming the session was
not using any form of Initialization Vectors).

>>    the random value r for at least 2*MSL  (and possibly longer) from the
>>    and no random number r can be found, it should be dropped and an ICMP

I agree. But the HIs alone are somewhat hard to work with. When a hosts
grants access to resources, it needs to know who the person on the other
side is, and that's why I consider names bound to HIs to be a
fundamental component to identity. This can also have scalability issues
(for example, with e-mail addresses you can grant access to every one
with address for example as *.acm.org. With HIs one will have to list
all the HIs, which is error prone and takes a lot more space).

>> and the Identity of responder against Active attackers. The disadvantage
>> is that the Initiator's ID cannot be protected against active attackers.
> 
> 

But now, if an attacker, Eve, wants to get the Identity of the
Initiator, Alice, all Eve has to do is to just take Alice's HIT (from an
exchange that she started) and send an I1 to Alice. Alice, on seeing I1
will herself give her identity out in R1.

> and getting the public key from a human understandable name is a

see above.

> explicit argumentation about using nonces for keymat generation.

Okay, the theory for using nonce (or any random data) in keymat goes as
follows (my apologizes, if I am repeating well known stuff): The fact
that an attacker cannot generate g^xy from g^x and g^y in itself is not
sufficient to guarantee that the scheme is secure. Even though an
attacker cannot exactly compute g^xy from g^x and g^y, she can still
guess 60%-80% of bits of g^xy with a high (~ 0.95) probability. (For
example, some people believe that the generator 2 leaks information
about x in 2^x (mod p) because 2^x = (1+1)^x = 1 + x + x(x-1)/2 + ....
by binomial expansion -- an expression with only x on right hand side.
Of course no one has shown, to the best of my knowledge, how to predict
the bits of  g^xy (mod p) based on this or any similar information.)

So to make the scheme more secure, what one needs is that given (g^x,
g^y, and g^xy) an attacker should not be able to distinguish it from the
distribution of (g^x, g^y, and g^Random_number).  There are lots of
papers on this problem (called the Decision Diffie-Hellman (DDH) problem).

To achieve this, g^xy is MACed to get rid of the non-uniform
distribution of bits of g^xy and make it look more like g^random_number
(actually if there is a better Pseudo Random Number Generator (PRG) than
MACs, then that PRG should be used instead).

For a MAC to generate a uniform distribution it should have enough
entropy in the input stream. Adding a nonce (or any random data) helps 
in that sense. Note that the present KEYMAT also MACs the HITs, but the 
amount of entropy of HITs combined (=127*2) is much less that the size 
of g^xy (=1024 bits). So how much MAC will be able to get rid of 
predictability of g^xy is not clear (it might be sufficient; I haven't 
been closely following crypto stuff after 2001, so I don't know what new 
developments have taken place).

Adding the nonce in key generation might help from that POV. If you
don't want to add a nonce, then just adding some random data will also
help (e.g., using the entire R1 and I2 packets in KEYMAT generation).

Yogesh

---

From: Pekka Nikander <[email-masked]>
Date: Mon, 11 Oct 2004 09:09:15 +0300

Yogesh,

This is very good and educating discussion, at least to me.
Thanks again for bringing this up, even if I seem to oppose
quite a lot of what you say :-)

>> I'd like to understand better

Well, my understanding has been that you shouldn't reuse
your DH-key, ever.  (Maybe the docs don't say that.)  That
is, you should have a pool of precomputed R1s, use that pool
pretty uniformingly while they are valid, and once you get
an I2 for a given R1, cease transmitting it.  When some
R1s expire, you can reuse the DH keys in them after a while,
i.e., when it looks like that you won't get any I2 on them.
Since all this is supposed to be (mostly) stateless,
implementing this in practise is pretty hard, though.  Hence,
while I don't buy your argument above, there still seems to
be of some value.

>> ... in HIP the public key IS the real
> fundamental component to identity.

 From a practical point of view, I can't help but agree.
However, from an architectural purity point of view, I bitterly
disagree.  :-)

> This can also have scalability issues

Right.  That's why the HAA HITs were introduced.  The recent
development has pretty much ignored them, but I expect them
to pop up later.  OTOH, you have to remember that you have
to store either the HITs or the HIs somewhere, in order to be
(reasonably) secure.  It may be enough to store a wild card name
locally, but then you still need to have access to a trusted
binding between the names and HIs.  I'd most probably attempt
to solve this problem with SDSI/SPKI name certificates, without
storing anything locally, if space is of concern.

Hence, the name transferred as a part of the HIP base exchange
really is just auxliary information.  You can't trust it, in no way,
as you can't trust your peer.  In fact, if the proposed DHT infra
was there in place, we most probably wouldn't need the HOST_ID
payload at all.

> will herself give her identity out in R1.

That depends on the policy Alice has.  If the associated HI is
non-public, the case may be that Alice doesn't reply to any
I1s asking to connect to it.

Again, if you want to have full privacy with HIP, you most
probably need to go to something like BLIND.  (And there
you have the nonces, too :-).  Hence, I don't see much value
in changing the base spec at this point of time.

But, as I wrote above, this discussion is very useful and
preferably should be preserved in some form.  I think we should
either write another draft, or add an informational appendix
on the base spec.

> the bits of  g^xy (mod p) based on this or any similar information.)

Ok.  This was new to me.  (I haven't been really following crypto
since 1999.)

> papers on this problem (called the Decision Diffie-Hellman (DDH) 

I see.  The first time I hear about this.  Mea culpa.

> in that sense. Note that the present KEYMAT also MACs the HITs, but 
> the amount of entropy of HITs combined (=127*2) is much less that the 
> size of g^xy (=1024 bits). So how much MAC will be able to get rid of 
> been closely following crypto stuff after 2001, so I don't know what 
> new developments have taken place).
>

Good goal.

However, my current suggestion would be not to add nonces to the
base spec.  Adding HMAC to I2 and revising the R2 HMAC looks small
enough that we can do that easily and safely enough.  But adding
nonces seems to have architectural implications that I don't quite
understand.  Hence, I would leave that for later.

What do others think?

However, I would encourage you to work towards a revision of BLIND,
perhaps together with Jukka.  (I am currently too busy to write
papers.)  As the key generation in BLIND is, by necessity, different
from base HIP, including the nonces into key generation seems like
a natural thing.

My personal guess is that we most probably want to adopt some
aspects of BLIND for the next revision of HIP, but given the
pressures to get a stable specification out for experimentation,
I would leave all this nonce stuff for future, and not change the
current spec in that respect.

--Pekka

---

From: Miika Komu <[email-masked]>
Date: Mon, 11 Oct 2004 10:18:51 +0300 (EEST)

> not using any form of Initialization Vectors).

The base spec says:

  "The Diffie-Hellman value is ephemeral, but can be reused over a
   number of connections.  In fact, as a defense against I1 storms, an
   implementation MAY use the same Diffie-Hellman value for a period of
   time, for example, 15 minutes."

The case for long period of DH regeneration may be valid for devices with
limited CPU resources (e.g. PDAs or overloaded servers). At the moment, I
cannot remember how much CPU resources DH generation eats up in practice.

If we decide to tangle the nonce into the KEYMAT derivation, we can still
use the current scheme, i.e., grab the nonce from the echo request/reply
messages. The nonce propably needs to be sufficiently large so that it
really enhances the security. For practical reasons, is may be better that
the length of the nonce is constant.

We should also note that we probably want the nonce to be covered by the
signature because otherwise the nonce can be tampered by an passive
attacker (i.e. rogue host in the path of the message). This is problematic
from the view point of precreated R1s because changing the nonce requires
changing the precreated R1s (or a yet another index, based on nonce, to
the table of R1s).

> > change of the HMAC contents in R2.  They seem OK to me.

For practical reasons, maybe the HMAC should cover the whole packet, not
just few fields. The overhead should not be too significant, and it should
be easier to implement. In addition, I find the "pseudo-HMAC" scheme above
a bit difficult to implement; in the third and fourth packets, the HMAC
covers parameters that are not present in the packet (3. packet g^r, 4.
packet g^ir).

Alternatively, we could have:

I2: IP ( HIP ( SPI,
                 [R1_COUNTER,]
                 SOLUTION,
                 DIFFIE_HELLMAN,     /* g^i */
                 DIFFIE_HELLMAN,     /* g^r (is this really needed?) */
                 HIP_TRANSFORM,
                 ESP_TRANSFORM,
                 ENCRYPTED { HOST_ID },
                 [ ECHO_RESPONSE ],
                 HMAC,
                 HIP_SIGNATURE,
                 [ECHO_RESPONSE] ) )

R2: IP ( HIP ( SPI, HMAC, HIP_SIGNATURE ) )

In this version, the HMAC covers the whole I2. There is no pseudo-HMAC;
the initiator has to include both of the DH parameters to the responder. I
am not completely sure if both of DH parameters need to be sent in I2
(Yogesh, opinion?) but it seems to be so in the SIGMA. Maybe the
pseudo-HMAC scheme is better from the viewpoint of security as you don't
echo the g^ir again on the wire.  Anyway, the g^ir has been exposed
already.

The R2 remains the same as in the current draft because I coupled HIP with
SIGMA-I. I interpreted the R2 as an "SIGMA ACK" that guarantees the peer
awareness property. In a more strict sense, the R2 is not just a plain ack
because it includes the SPI. I don't see this as a problem because the
HMAC already protects against R2 replication attacks (e.g.
man-in-the-middle host tries to record R2s, and tries to DoS the initiator
with incorrect SPIs).

> all the HIs, which is error prone and takes a lot more space).

You need certificates to guarantee that hostname/NAI is not forged. Until
then, it can be considered only as informational.

> will herself give her identity out in R1.

The scenario you described seems to be a valid concern. HIP, as currently
specified, does not take as good care as SIGMA-I of the initiator's
identity. However, the problem can be alleviated with the policies
described by Pekka in the previous email.

I don't understand how the encrypted domain-ID does the trick. IMHO, to
really solve the case, we need to hide the initiator's HIT in the HIP
header. Perhaps we could use blinded HITs in HIPv2 as already suggested in
earlier email from Pekka. A null HIT for the initiator has other problems.

Btw, I did not see a direct correspondence between SIGMA-I/R and HIP. For
example, the responder's identity cannot be encrypted. Also, the first
message in SIGMA-I/R contains already the public DH key of the initiator,
and we need to move it to the third message in HIP. However, I don't think
this was of great importantance in SIGMA. The emphasis was on the
following rules-of-thumb that can reused also in HIP (as Yogesh already
suggested):

* keep the HMAC key different from the other keys derived from KEYMAT
  (as they are in HIP)
* each packet should include either a NONCE or DH
* DH is covered by the SIGNATURE
* The HOST_ID is covered by the HMAC

---

From: Miika Komu <[email-masked]>
Date: Mon, 11 Oct 2004 15:12:43 +0300 (EEST)

> changing the precreated R1s (or a yet another index, based on nonce, to

I'll take this back. The nonce does not have to be covered by the
signature because the the purpose of the nonce is not to provide integrity
protection.

> echo the g^ir again on the wire.  Anyway, the g^ir has been exposed

I think I misunderstood the notation here. g^ir (or g^xy) is the shared
Diffie-Hellman secret, not the concatenation of the Diffie-Hellman
parameters. Just forget my alternative above =)

So, I guess we need to include the shared secret in the calculation of the
HMAC in I2 and R2? Still, I am a bit confused why this should be done.
Yogesh, would you care to explain this point in more depth? I am not a
crypto specialist...

---

From: Pekka Nikander <[email-masked]>
Date: Mon, 11 Oct 2004 15:19:34 +0300

> Yogesh, would you care to explain this point in more depth? I am not a

For practical purposes, we apparently need to use a different
HMAC parameter type for I2 and R2, as they do not cover the packets
but extra-protocol information.   But that also makes it easier to
either place it under the signature or outside, dependent on which
is better.

--Pekka

---

From: Yogesh Prem Swami <[email-masked]>
Date: Tue, 12 Oct 2004 23:36:00 -0500

> Yogesh, would you care to explain this point in more depth? I am not a

Well, I am not a crypto expert either :-)

The signature and HMAC are complementary. Signature prevents from MITM; 
HMAC ensures that the people who are verified to be alice and bob 
actually know the session key. I guess SIGMA paper is the best place for 
in depth analysis of all this.

Yogesh