Subject: Re: New multi6 draft: WIMP

From: Jukka Ylitalo <[email-masked]>
Date: Mon, 02 Feb 2004 13:30:43 +0200

Hi Marcelo,

Thanks for reading through our draft.

marcelo bagnulo wrote:

>Hi Jukka,
>
>I am trying to understand your draft, and i have some questions about some
>points that you perhaps can help me with.
>
>  
>
You have pointed out several important issues that need clarification. I 
already
apologize my long email.

>1. About the Context establishement exchange (section 3.4)
>I fail to see what you mean when you state that the responder remains
>stateless.
>I mean, the responder has to generate the temrporary hash chain. This hash
>chain has to be specific to this particular host pair context, right? (this
>is what it is stated in section 3.3 about generating reverse hash chains)
>So, this means that when the responder receives an INIT message it has to
>generate a new hash chain (or reserve a pre computed hash chain for this
>initiated context establishement), would this be correct?. If so, the
>responder has to at least store a state that is that this hash chain is
>reserved and cannot be used for a future INIT, right?
>
>  
>
The responder has one long term secret that is common for different 
contexts. Basically,
the responder remains stateless, and does not store the temporary hash 
chain values.
It is still able to safely recompute the hash chain after receiving the 
CCR message.

Appendix A describes an example how the hash chain can be generated. The 
responder
generates its hash chain using a long term local secret, IDs and a 
challenge (i.e.
a nonce). The initiator's ID is a hash of a nonce. The secret, in turn, 
is never reavealed
to the peers.  The responder protects the CC message with its newly 
generated
hash chain value. It does not create a state.

It is important to notice that the state machine plays an important 
role. If a responder already has  a state for  a specific ID pair, it 
does not reply with CC message. In other words, an attacker cannot pump 
out the hash chain values of other ID pairs.
The responder cannot generate similar hash chain for a new ID pair 
during the lifetime of the authentic ID pair. The attacker is not able 
to use the same ID as the authentic initiator  is currently using.

In addition, it does not matter if the attacker creates a context with 
the responder,
using the authentic inititor's ID and challenge, after the authentic 
initiator has destroyed its context with the responder. Once the 
authentic initiator creates a new context-pair
with the responder, it generates a new random ID for itself, and 
therefore also the hash chain is changed.

Once the responder receives the CCR message, it is able to recompute the 
hash chain
using the long term secret, IDs and the challenge. The HMACs  bind the 
earlier
exchange messages (INIT and CC) together and quarantee that the hash 
chain is
bound to the requested ID pair.

[Do not hesitate to ask more questions about this, if I my answer was 
not clear enough.]

>If so, wouldn't this imply that an attacker sending INIT messages could
>force the responder to gnerate hash chains, sort of DoS attack? I ask this
>because, if i understand correctly, this is what you are trying to prevent,
>but i just fail to see how you actually prevent it :-(
>
>  
>
A short hash chain generation is a quite fast operation compared to 
signature
calculation. (If I remember correct, e.g., computing SHA1 five times over a
160bit string takes under 0.5 ms with 2Ghz pentium.) The operation is 
efficient
and makes it more diffucult for an attacker to cause a DoS situation.

>The you state that:
>"The initiator replies to the CC message with a context check reply
>   message (CCR) and proves that it was reachable at the specific
>   location by disclosing the anchor value."
>
>I don't really agree with this... I think that the initiator can prove that
>he is reachable by inlcuding the HMAC_CC value in the CCR message, and not
>by disclosing the anchor value.
>
>I mean, the anchor value would prove that the initiator is the same that the
>one who sent the INIT message, but if the RESPONDER is stateless, the
>responder has no information about the INIT message received, .
>I guess that the important is to inlude the HMAC_CC and since the responder
>has the H0_R it can verify that the HMAC__CC was generated by himself (the
>responder)
>
>(i am probably missing something here....)
>
>  
>
Excellent analysis! Thanks! However, as I pointed out above, the responder
is able to recompute its hash chain without creating a state.

A short description:

Once Responder receives  INIT message it  protects  the received values 
, including
HMAC_INIT, with HMAC_CC.  The responder uses the temporary hash chain
value as a key in HMAC_CC.  Finally, the responder  receives CCR message 
and recomputes the hash chain. It uses the long term secret to recompute 
the chain.
The responder verifies HMAC_CC to see that it already has reveived INIT 
message with a specific ID pair. The initiator, in turn, discloses its 
anchor value to prove
that is was reachable in the specific location. In other words, the 
HMAC_INIT
in INIT message, and the anchor_I value in the CCR message bind the messages
together and implement a kind of return-routability test.

>after you mention that:
>
>"The anchor value of the initiator hash chain
>   binds the INIT and CCR messages together, and in this way the
>   responder is able to verify that messages are coming from the same
>   host. "
>
>again if the responder is stateless, he has no knowledge about the INIT
>message by the time he receives the CCR message, so what does it means that
>it can verify that both messages come from the same host?
>  
>
See above.

>2. Re-addressing exchange
>
>First, a simple question: the re-addressing exchange can be initiated by the
>responder? (i think so, but i couldn't find it stated clearly in the draft)
>
>  
>
Yes, the responder of the context establishment exchange is an initiator 
if it starts the re-addressing exchange. The initiator of an context 
establishment or re-addressing exchange is called the initiator. See below:

Section 7:
"The initiator of the context establishment exchange is called the
   initiator. Once the host-pair contexts are established, this initial
   distinction is lost.  The sender of the REA message is called the
   initiator of the re-addressing exchange. In a case of state loss, the
   sender of the RESYNCH message becomes a responder."

>Second, i am really having a hard time to understand how the key masks and
>the key pieces work and how you can verify which of the locators are
>reachable. I guess that part of the reasons is because my own comprehension
>problems, but the fact that part of the explanation is contained in section
>3.5 and that the rest is contained in section 6.12, where the packet format
>is explained, is not helping me much :-(
>Could you provide me a simpel example, with for instance a REA message
>conatining 3 new locators, and detail which would be the AC1, AC2 and AC3
>messages, how they are generated and which would be the ACR message (and its
>generation)?
>Sorry to ask this, but i am really stuck here...
>
>  
>
You are right. That part needs more clarification in the draft. Thanks for
commenting that. I have included a short example:

REA:

IP header: Addr-R, Addr-I1
WIMP:  IDs, Addr-I1, Addr-I2, Addr-I3, H1(I), H0_new(I), challenge, HMAC

Secret splitting:

I refer here the "2nd edition of Applied Cryptography by Bruce 
Schneier", page 70.

Hash chain value H1(R) = 160 bit string
A = 160 bit random string
B = 160 bit random string

Responder computes: H1(R) xor A xor B  = C,
where A, B and C are final key pieces.

Initiator computes: C xor B xor A = H1(R),
where H1(R) is the combined key.

AC1:

IP header: Addr-I1, Addr-R
WIMP: IDs, AC_ID=1, Key_count=3,  Key_mask=001, Key_piece=A

AC2:

IP header: Addr-I2, Addr-R
WIMP: IDs, AC_ID=1, Key_count=3,  Key_mask=010, Key_piece=B

AC1:

IP header: Addr-I3, Addr-R
WIMP: IDs, AC_ID=1, Key_count=3,  Key_mask=100, Key_piece=C

If the initiator receives all of the keys. ACR:

IP header: Addr-R, Addr-I1
WIMP: IDs, AC_ID=1, Key_count=3,  Key_mask=111, combined_key=H1(R), H2(I)

If the initiator receives only AC2 and AC3. ACR:

IP header: Addr-R, Addr-I2
WIMP: IDs, AC_ID=1, Key_count=2,  Key_mask=110,
combined_key=(B xor C), H2(I)

>3. After that a REA message is received, and some of the locators are
>verified, which locator is used for following packets?
>Do you use the address contained in the source address field of last
>received packets?
>
>  
>
The draft does not define an address selection policy. I think
the WG should define a separate draft that defines the address selection 
policy
for all different multi6 protocols. However,  your prososal sounds good for
default address selection.

I hope my comments clarify the draft and give answers to your questions.

Br, Jukka

>Thanks, marcelo

>
>  
>
>>-----Mensaje original-----
>>De: [email-masked] [mailto:[email-masked]]En
>>nombre de Jukka Ylitalo
>>Enviado el: jueves, 29 de enero de 2004 10:09
>>Para: [email-masked]
>>Asunto: New multi6 draft: WIMP
>>
>>
>>(uh oh, the previous email was incorrectly aligned)
>>
>>Hi,
>>
>>We have submitted a new multi6 draft to I-D directory. The draft
>>defines a Weak Identifier Multihoming Protocol (WIMP), and we
>>wrote it in order to see how opportunistic/weak authentication
>>methods could
>>be used to solve the multi6 problem.
>>
>>WIMP is one of those protocols that introduce a new protocol layer
>>between IP and upper layers. Our approach uses some very basic
>>cryptograpahic funtions (reverse hash chains and secret splitting) in
>>order to have light and (hopefully) simple solution. The protocol
>>is not buller broof from security point of view, however, it intends
>>to be secure enough and easy to implement.
>>
>>We hope it will stimulate discussion on various solution to
>>multi6 problem.
>>
>>See more details from the draft itself, available in:
>>
>>http://www.hip4inter.net/multi6/draft-ylitalo-multi6-wimp-00.txt
>>
>>Thanks, Jukka Ylitalo
>>
>>
>>
>>    
>>
>
>
>
>  
>

---

From: "marcelo bagnulo" <[email-masked]>
Date: Mon, 2 Feb 2004 17:30:23 +0100

Hi Jukka,

thanks for this detailed explanation, more below...

[...]

> [Do not hesitate to ask more questions about this, if I my answer was

I think i understand that part, i see now why it is stateless.

> >force the responder to gnerate hash chains, sort of DoS attack?

[...]

> signature calculation.

why do you compare it with the processing required to perform a signature
calculation?

I mean if i were an attacker, i would do the following:

The goal of the DoS attack is to consume the processing power by soliciting
the victim to produce (useless) hash chains.

So, the attacker generates a random number as an ID(I) and also a
challenge(I) and then simply generate a random string which length is the
same than the expected length of the HMAC_INIT. I think the attacker can do
this because the victim (i.e. the responder) cannot verify the HMAC_INIT
since it doesn't know H0(I).

The attacker can generate as much INIT messages as he wants, he just has to
add 1 to the ID(I) values (in order to avoid the duplication of IDs)

So, the attacker can force the responder to generate hash chains based on
the ID(I).

As far as i know (note that i am no security expert nor anything close to
this), the idea to avoid DoS attacks is to impose more workload to the
initiator to the responder.

Now, in this case, in order to generate INIT messages the initiator just has
to perform an addition operation (adding 1 to the ID(I))

However, the responder has to generate a hash chain.

I don't have computation time values but i would say that the responder task
is more time consuming than the attacker task.
Am i missing something?

[...]

> >   location by disclosing the anchor value."

[...]

> is able to recompute its hash chain without creating a state.

i understand the stateless part, buti a have a minor observation. see
below...

> A short description:
>
> Once Responder receives  INIT message it  protects  the received values,
> including HMAC_INIT, with HMAC_CC.  The responder uses the temporary hash
> chain value as a key in HMAC_CC.  Finally, the responder  receives CCR
message
> anchor value to prove that is was reachable in the specific location.

Well, this is not really a big issue, but i think that the proof that the
initiator is reachable at the specific location is provided by the fact that
the initiator has received the HMAC_CC value (and he is proving it because
he is including it in the CCR packet)

Disclosing the anchor value does not prove that he is reachable at the
specific location. Displaying the anchor value proves that the initiator has
generated both the INIT message and the CCR message.

Now, the responder is stateless and thanks to the anchor values it can
verify that the same initiator has sent both the INIT and the CCR message.

But, as i said, this is really minor.

[...]

> combined_key=(B xor C), H2(I)

perfect, thanks

IMHO you should include this example in the draft, it really makes things so
much clearer (at least for me)

> I hope my comments clarify the draft and give answers to your questions.

Yes, thanks.

I think that WIMP may be susceptible to the following hijacking attack. Let
me know if i am wrong.

Attacker A with address IPA
Server S with IP=IPS and FQDN=www.server.com
Victim V with IP=IPV and FQDN=FQDNV

The attacker will try to impersonate S. Now if you consider that S is
server, usually is V who contacts (think for instance a newspaper web server
where V reads the news every morning). So the attacker will try to establish
some malicious state in V so that when V tries to send packets to S, he will
actually send them to A.

The attacker calculates ID(S)=Hash(www.server.com) and ID(V)=Hash(FQDNV)
The attacker sends a INIT value with ID(I)=ID(S) and ID(R)=ID(V) using its
own IP address

Now the attacker has generated this state in V. It can preserve this state
by simply sending periodical pings or just UDP packets to unused ports
(since WIMP is below UDP, this would be enough to preserve the state at the
wimp layer, right?)

Eventually, V will try to contact S to read the news.

At this point, V will calculate Hash(www.server.com)

Considering that V already has a state with ID(R)=Hash(www.server.com) and
according to the rule 2 described in section 4.1, V will simply use the
available state in the wimp layer.

This means that when V tries to communicate with S, V will be actually
sending packets to the IP address associated to this state, that is IPA, so
V will send packets to the attacker. So the attacker will impersonate the
server.

Would this attack work?

Thanks, marcelo

---

From: Jukka Ylitalo <[email-masked]>
Date: Tue, 03 Feb 2004 13:53:57 +0200

Hi,

>is more time consuming than the attacker task.
You are right. DoS is always a difficult problem.  There is a trade-off 
between
DoS resistance and other security features. The  current  hash chain
generation is designed to support state-loss, and it is dependent of 
parameters
coming from the initiator.

Basically, the responder could protect the HMAC_CC with a local secret and
generate the hash chain after receiving CCR message. In that case, the 
responder
could not bind the CC and CONF messages together. The protocol were open for
MitM attack. In other words, an attacker could send CONF message before the
authentic responder.

We have to think more about the DoS situation. However, I would not like to
include any puzzle to the INIT message.

>he is including it in the CCR packet)
Yes!

>generated both the INIT message and the CCR message.
Right.

>much clearer (at least for me)
Ok. I'll put it into the draft

>V will send packets to the attacker. So the attacker will impersonate the
Unfortunately it works :-) thanks! We can fix the problem in a couple of 
ways.

1) the initiator must verify that the existing context has at least one 
verified
IP addresses that corresponds the IP addresses in the DNS.

or

2) The initiating party must not re-use a context if it is initiated by 
other party.
As a consequence, p2p applications will have two contexts. One per 
direction.

Br, Jukka

---

From: "marcelo bagnulo" <[email-masked]>
Date: Tue, 3 Feb 2004 16:07:21 +0100

> verified IP addresses that corresponds the IP addresses in the DNS.

I don't know about this...
some random thoughts:
- if you use the DNS to validate addresses, i think you loose much of the
beauty of your solution. Actually, you could only use the DNS and you end-up
in NOID. The only benefit AFAICS would be to support a more dynamic prefix
change, for instance to support faster renumbering, but i am not really sure
if this is worth it. I mean, probably DNS times and renumbering times are
quite compatible

- besides, i am not sure that this would be really enough becuase you will
have to consider time-shifted attacks. Requiring a valid IP address only
means that this IP address was checked once when the REA message was sent.
This is not good enough to prevent a time shifted variation of the described
attack

- the only way i can figure out is to verify the reachability of the address
contained in the DNS again when the responder wants to initate the new
communication (this is starting to seem a lot to the second solution, i
guess)

> As a consequence, p2p applications will have two contexts. One per

Yes, this may wotk...
I can see how would you this for TCP and even for connected UDP socket, but
is don't know how would you recognize who has initiated the communication in
the case of non-connected UDP though (but i have little knowledge about how
this work)

I would recomend to verify the time shifted attacks in this case either

regards, marcelo

---

From: "marcelo bagnulo" <[email-masked]>
Date: Tue, 3 Feb 2004 16:48:44 +0100

> I can see how would you this for TCP and even for connected UDP
> socket, but is don't know how would you recognize who has initiated the
> communication in the case of non-connected UDP though

Just one more thought...

Perhaps an option for this would be:

suppose that A wants to initiate acommunication with B

A calculates ID(R)=hash(FQDNB)
A then searches for a context with ID(R)
If one context with ID(R) is found, A verifies ID(I),
if ID(I) = hash(FQDNA) then it creates a new context with ID(R) and
ID(I)=random
if ID(I) =! hash(FQDNA) then it just uses this context

This way, you implicetly discover who has created the context.

Do you think this may work?

regards, marcelo

---

From: Jukka Ylitalo <[email-masked]>
Date: Wed, 04 Feb 2004 09:33:22 +0200

>Do you think this may work?
Yes! I think that is a good idea and I will put that into the WIMP draft.
I have to still analyze Pekka Nikander's ideas that he sent to me about the
same issue.

(As a result of this discussion we take the second alternative as a working
assumption, and leave the DNS check out of the scope)

Thanks, Jukka

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 23 Feb 2004 22:07:42 +0100

On 2-feb-04, at 12:30, Jukka Ylitalo wrote:

> signature calculation. (If I remember correct, e.g., computing SHA1 
> five times over a 160bit string takes under 0.5 ms with 2Ghz pentium.) 
> The operation is efficient and makes it more diffucult for an attacker 
> to cause a DoS situation.

Actually this is pretty poor. I seem to remember that a significantly 
slower Pentium can do 2000 DSA signature checks per second. Being able 
to bring down a host with just 2000 packets per second would be a very 
bad thing, as this is easily accomplished over 10 Mbps ethernet (approx 
500 byte packets).

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 23 Feb 2004 14:42:38 -0800 (PST)

> bad thing, as this is easily accomplished over 10 Mbps ethernet (approx 

I would be interesting in seeing some apple-to-apple comparisons
between different security algorithms that might apply to multi6 solutions:

One is an anonymous DH exchange - basically the purpose-built keys approach -
how much CPU to do the modular exponentiation?

Another one is a public key signature (and verification?)

A third is performing 5 SHA1 hashes of 160 bits.

If I had a better feel for the relative CPU cost of those 3 operations it
would be easier for me to understand the performance/DoS aspects of these
schemes.

  Erik

---

From: Jari Arkko <[email-masked]>
Date: Tue, 24 Feb 2004 09:36:47 +0200

> would be easier for me to understand the performance/DoS aspects of these

Yes. Actually, I find Jukka's numbers a bit surprising. SHA1 is used
on a per-packet basis on IPsec, for instance, and many systems can do
this at wire speed. And I always thought that bignum operations (signatures,
diffie-hellman) were significantly slower than symmetric operations (SHA1)
on the same hardware.

Reference http://www.eskimo.com/~weidai/benchmarks.html gives the performance
on a 2.1 Ghz Pentium for SHA1 as 72 Mbytes/s; for RSA signature takes 4.65 ms
and verification 0.19 according to the same source. However, this does not tell
us how many individual SHA1 operations were run, just the data amount.
Digging into the source code of Crypto++ library on which the tests from
the above link were made... hmm.... it seems that it simply calls hash.update
repeatedly. Are we comparing apples to oranges if I assume an individual
SHA1 operation cost is according to 72 Mbytes/s? I seem to recall that
at least HMAC_SHA1 had some fixed cost component. If anyone has better
benchmarks, tell us...

Anyway, the way I read Wimp is that the amount of SHA1 data to be calculated
under the hash in the packet is ~ 90 bytes. For this, using the above numbers
I get 1.19 *microsecond*, not millisecond. The RSA for this would be 4.65
millisecond, or about 4000 times slower. DSA signature would be 2.14 millisecond,
or about 2000 times slower (without precomputation).

--Jari

---

From: Jukka Ylitalo <[email-masked]>
Date: Wed, 25 Feb 2004 11:36:12 +0200 (EET)

> Yes. Actually, I find Jukka's numbers a bit surprising. SHA1 is used

Thanks for correcting me Jari. The question is about microseconds,
not milliseconds.

Br, Jukka

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 25 Feb 2004 10:46:08 +0100

> Thanks for correcting me Jari. The question is about microseconds,

So you can do a SHA-1 hash chain length 5 in 0.5 microseconds??? That 
seems awfully fast, just 1000 clockcycles...

---

From: Jukka Ylitalo <[email-masked]>
Date: Thu, 26 Feb 2004 12:51:50 +0200 (EET)

> seems awfully fast, just 1000 clockcycles...

Jari gave us excellent bench mark results. There is no big difference
if I didn't remember the exact time. Is it 0.5 or 2 microseconds,
it doesn't matter.

Let's focus on the essential issues. The main point was that the
hash chain computation is much more efficient than public key crypto.
Right?

-- Jukka