Subject: [IPsec] Secure Crash Discovery for IKEv2

From: Yoav Nir <[email-masked]>
Date: Wed, 6 Aug 2008 17:22:03 +0300

This is a followup to my mini-presentation in Dublin.

The problem we're trying to solve is that of a state de- 
synchronization between two IKE peers. This could take several minutes  
to discover and resolve, and no IPsec traffic can flow in that time.

The following Wiki page describes the problem, and two proposed  
solutions.

http://wiki.tools.ietf.org/wg/ipsecme/trac/wiki/SecureCrashDiscovery

We would like to solicit input from the WG about these two solutions,  
so that we can either combine them or choose between them, and proceed  
with a unified draft.

Thanks in advance

Frederic, Pratima and Yoav

_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec

---

From: <[email-masked]>
Date: Thu, 7 Aug 2008 23:09:12 +0300

Couple of comments (not wearing any hats):

I like the QCD proposal -- it's simple, and doesn't seem to change the
security properties of IKE (unlike the SIR proposal; more below).

On the web page, you asked for comments about "constrained devices"
like cell phones. For a cell phone that can implement IKEv2, keeping
16-32 extra bytes per IKE_SA is trivial (the state needed for IKE_SA
and ESP/AH SAs is anyway much more).

The SIR proposal, on the other hand, relies on totally unauthenticated
exchange. You can treat it as a hint and wait until you're sure you're
not going to get a real authenticated response -- but then it's not
clear why it's better than normal INVALID_IKE_SPI notification. And
if you treat it as something else than hint (and don't wait long time
to hear from the real server), you're exposing yourself to DoS that
wasn't possible earlier.

Best regards,
Pasi

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] 
> On Behalf Of ext Yoav Nir
> Sent: 06 August, 2008 17:22
> To: [email-masked]
> Subject: [IPsec] Secure Crash Discovery for IKEv2
>

---

From: Lakshminath Dondeti <[email-masked]>
Date: Thu, 07 Aug 2008 16:26:01 -0700

Question on the QCD proposal.

Is it possible for an attacker to send HDR(a, b) SK{..} for arbitrary 
values of a and b, receive N(QCD_TOKEN) and build a database of 
QCD_TOKENs?  Throttling mechanisms are not appropriate in this case, as 
far as I can see.

I realize that it is a large database to build :) but whatever secret 
and crypto algorithm is used to generate QCD_TOKENs need to take that 
interaction into consideration.

Another question: Why are a and b equal to 0 in the N(QCD_TOKEN) 
exchange?  Do they need to be?

thanks,
Lakshminath

On 8/6/2008 7:22 AM, Yoav Nir wrote:
> The problem we're trying to solve is that of a state de-synchronization 
> between two IKE peers. This could take several minutes to discover and 
> resolve, and no IPsec traffic can flow in that time.
> 
> The following Wiki page describes the problem, and two proposed solutions.
> 
> We would like to solicit input from the WG about these two solutions, so 
> that we can either combine them or choose between them, and proceed with 
> a unified draft.
> 
> Thanks in advance
> 
> ------------------------------------------------------------------------
>

---

From: Yoav Nir <[email-masked]>
Date: Fri, 8 Aug 2008 11:30:35 +0300

Hi Lakshminath.

See my replies below

On Aug 8, 2008, at 2:26 AM, Lakshminath Dondeti wrote:

> Is it possible for an attacker to send HDR(a, b) SK{..} for  
> arbitrary values of a and b, receive N(QCD_TOKEN) and build a  
> database of QCD_TOKENs?  Throttling mechanisms are not appropriate  
> in this case, as far as I can see.

[yn] Yes, it's possible, but assuming that both Alice and Bob use good  
PRFs to generate the IKE SPIs, it's a 2^128 entry database. If only  
Bob generates good IKE SPIs and Alice generates 0x0000000000001000,  
0x0000000000001001, 0x0000000000001002, etc. it's still bigger than  
2^64.

> I realize that it is a large database to build :) but whatever  
> secret and crypto algorithm is used to generate QCD_TOKENs need to  
> take that interaction into consideration.

[yn] There's also the option of periodic rollover to a new secret

> exchange?  Do they need to be?

[yn] Good catch. I didn't intend them to be.  I'll clear that up.

---

From: Frederic Detienne <[email-masked]>
Date: Mon, 11 Aug 2008 07:20:36 +0200

Hi Pasi,

couple of answers

0- disclaimer
-------------
We participate in QCD as well as in SIR and we do see the pros and cons
of both protocols. QCD does look simpler but there is still some work to
be done to make it a secure protocol specification as opposed to a
specification that may allow a secure implementation. Same goes to
robustness.

Apparent simplicity of QCD will eventually suffer. We invite everyone to
look beyond the surface.

There is also a fitness for purpose issue that we need to sort out in
QCD. SIR is more appropriate in some cases and simply covers more cases
than QCD.

Finally, for large clusters, SIR works without the help of a management
station or a cluster synchronization protocol (e.g. for updating the key
regularly). The deployment scalability of SIR is independent of any
back-channel (e.g. cluster management protocol), which makes SIR fit for
accepting various vendors in the cluster.

We agreed with Yoav to present both protocols for public review before
one is eventually voted out.

Meanwhile, we do defend SIR to the degree that it will suit all the use
cases that we have been given to see or think about.

1- constrained devices
----------------------
The wiki is a cooperative write up and I overlooked the "cell phone"
statement -- this was not precisely our main concern. Constrained was
meant for devices that will not allow spending extra memory/CPU for
various reasons. I will update the wiki.

The real concern is the amount of memory used and operations to be
performed by any device, including the head-end. Over the years, we have
seen the memory requirements growing exponentially. Believe it or not,
there are a lot of other protocols out there than just IKE that ask for
"a few bytes per connection" or some "small amount of memory".

We built our protocol like we would for an internal functional spec or
code review. If you do not need something, do not use it. Hence the call
for an abstraction that I called "Constrained device".

The protocol is simple enough to have been implemented by a novice and
hence we think we did not trade off simplicity.

SIR qualifies as it does not use any resource that IKE would not use
already (under normal circumstances, it even uses less).

2- security of SIR
------------------
The same SIR method can be used with or without tickets.

2.1- Ticket based recovery
--------------------------
Ticket based recovery does not suffer from a DoS attack more than QCD or
Resumption.

SIR just consumes a little less memory, and takes less packets but like
we stated in our draft, this method can be adapted to QCD.

We think this is a useful exchange whenever you want to spend the little
extra memory _and_ distribute a key in the cluster _and_ not play with
too complex designs -- i.e. good whenever Resumption is applicable. And
again, Ticket based SIR does not use more resources than IKE+Resumption
would use.

2.2- Stateless recovery
-----------------------

Yet the protocol is simple, we appreciate that the _rationale_ of
stateless recovery is a little complex for the unwary. Most people stop
when they think they found a "great attack". Notions such as "secure
enough" deserve an explanation.

I will try a deconstructive approach.

Strength:
- The worst case for SIR is an O(n) attack where n is the number of
IKE_SA's already present in the system. This attack only affects
recovery; NEW AND EXISTING CONNECTIONS ARE UNAFFECTED. Dampening and
other techniques reduce the effectiveness of the attack further.

- The worst case for IKEv2 is an O(N) where N is the max number of SA's
the system can hold or accept. This attack can go on continuously,
preventing legitimate keying (including new connections) from taking
place.

Please observe that
- the magnitude of the IKE attack is higher than the SIR attack
- the range of the IKE attack is higher than the SIR attack

Ease of attack:
- IKEv2 can be attacked via MitM or remotely in some cases
- SIR can only be attacked via MitM

So far, SIR is "as strong as" or "stronger" than IKEv2 which makes it
fit for purpose.

Now can you backup your feelings with some facts ?

Could you please elaborate an attack that can not be turned against IKE
alone ?

Can you also please show me how our list of requirements are met with
any other crash detection/recovery protocol ?

thanks,

	fred

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 14 Aug 2008 18:08:33 +0300

> security properties of IKE (unlike the SIR proposal; more below).

I have not yet read the drafts, but checked the description on the
wiki and from there, I think QCD is much better, it is actually quite
close to the birthday certificates, but not using public key crypto.
It could also be possible to combine both QCD and birthday
certificates if needed.

> and ESP/AH SAs is anyway much more).

Yes. IKE SA state is in order of kilobytes or tens of kilobytes (if
large window of 32 is used, IKE SA MUST keep last 32 IKE packets all
the time, thus only that reply window takes 10-20 kB of memory...). I
do not really consider that memory usage an issue here at all (i.e
sounds artifical to even mention it). In the same sense you would need
to mention that SIR requires n bytes of memory to keep the cookie
while doing the unauthenticated check :-)

On the other hand, I am not sure if either one of these are really
that useful, as in normal case the boot up sequence of the bob is
anyways going to be so long, that it has most likely already triggered
the liveness checks if there was active traffic going on between the
hosts.

Also I think that in case of we receive hints that suggest other end
is not reachable, one thing good implementations can do is to reduce
the number of retries. I.e. there is really no point of trying 2
minutes for liveness check if you are getting ICMP host/port
unreachable or INVALID_IKE_SPI notification back for all of your dozen
requests. You could interpret that hint so that you can simply lower
the retransmission times from dozen to 5 or so, over 30 seconds
instead of few minutes. If the other end is still there, it should be
getting one of the liveness checks anyways and reply to it.

If you do not hear anything back from the other end (i.e. no hints),
then there is most likely something wrong inside the path to remote
host, thus there is no point of reducing timers. 
-- 
[email-masked]
_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec

---

From: Frederic Detienne <[email-masked]>
Date: Thu, 14 Aug 2008 21:55:27 +0200

> It could also be possible to combine both QCD and birthday

We are trying to get an apple-to-apple comparison between QCD and SIR.
Is it possible to get some real comparison or do we have to stick to
impressions forever ?

On a side note, Yoav, Pratima and I think that Birth Certificates don't
work well in practice. They may be sort of secure but they are power
hungry. Both QCD and SIR are meant to be implemented on real gateways,
with real memory and real CPU's.

> sounds artifical to even mention it).

I see. "nobody needs more than 640kb or RAM", uh :) funny.

Guess what: there is still a market for embedded OSes that consume very
little memory and those OSes still beat free (as in free beer) operating
systems on that single point.

This being said, the "constraint device" notion is a concept to
summarize a number of notion. The message is "why use resources you do
not need". We could call this "green protocols" too... or "resource
savvy protocols". etc. Anything that you can understand is welcome.
Please help rephrasing.

If you had read the drafts, you would also know that this is not the
main point of SIR vs. QCD. There is a fitness for purpose issue; SIR has
a chapter dedicated to this. QCD is still incomplete on that front.

We would like to know what problem other implementers are willing to
address in the protocol... this is a good thing to start with before
saying that on thing is better than an other.

>  In the same sense you would need

Very good point! Just wrong.

In stateless recovery
---------------------

The cookie is computed with the same key as IKE uses for its
anti-spoofing test. SIR does not require _any_ storage that IKE does not
already require. I am ready to stand the argumentation but we certainly
do not need O(n) storage (n=# of SA's).

In ticket based recovery
------------------------
SIR uses a cookie approach but apparently too secure for FUD. This
method does not use more memory than Resumption.

> the liveness checks if there was active traffic going on between the

er.. darn you caught me... let me guess... oh yeah! Because the
failover/cluster case is really what real users out there are interested
in ? maybe ?

Again: protocols have a purpose.

> getting one of the liveness checks anyways and reply to it.

How is this fundamentally different from what SIR is saying ? SIR does
that kind of dance, only much faster and introduces an payload so that
it can collect hints of an attack as well and _log_ what is going on.

I do appreciate you are calling this a "good implementation", though.  
Thank you.

	fred

---

From: Tero Kivinen <[email-masked]>
Date: Fri, 15 Aug 2008 11:40:22 +0300

> with real memory and real CPU's.

What kind of reasons you have for them not working in real
environments? For the Bob, they are cheaper than both SIR and QCD from
the computational point of view, as you need to generate only one
certificate for each reboot, and regardless how many IKE SAs you had
up, you do not need to do any additional computations.

For the Alice it requires checking one signature when they start
suspecting that the other end is not up and running (i.e. when they
are not receiving anything from the other end and they get INVALID SPI
exchange back). Note, that signature verification in RSA is quite
fast, usually in order of milliseconds, which is faster than what is
the normal round trip time.

On the very slow devices there is quite often hardware to assist doing
RSA and Diffie-Hellman calculations anyways, as those calculations are
needed anyways for IKEv2.

The signature verification for RSA keys is about 10 times faster than
Diffie-Hellman required for recreating the IKE SA. 

> I see. "nobody needs more than 640kb or RAM", uh :) funny.

Nope. More like that there is no point of saving 0.1% of memory by
adding more code that consumes more memory than that... As the memory
is needed only on Alice, and she normally has just ONE IKE SA, the
total memory saving is around 16-32 bytes of memory in total. 

> systems on that single point.

I know, but we also do implementations on those platforms too, and I
know that currently those devices (phones for example) have quite a
lot of memory still (in orders of hundreds of kilobytes), thus adding
32 bytes of memory in total, does not really matter there.
Implementing any of the proposals are going to use much more code
memory (and that is actually quite often more limited than RAM) than
that anyways.

> Very good point! Just wrong.

As n is 1 in Alice anyways, that does not really matter, and when you
generate Cookie and send it to the Bob, you need to keep that in
memory so you can verify it is same when Bob returns it back in the
reply, thus you need to keep it in memory during the exchange. Note,
that it is much faster (and more efficient) to just generate random
cookie, and store it in the memory, than use some cryptographic
algorithm to generate it, especially as Alice still has state (IKE
SA), thus there is no need to be stateless.

> In ticket based recovery

We are not talking about failrover or cluster, we are talking about
secure crash discovery. In any case there are ways to do cluster /
failover methods which do not require any coordination with the
client. 

> it can collect hints of an attack as well and _log_ what is going on.

Yes, but the other method is already there, and can already be used
with ANY standard complient IKEv2 implementation, without requiring
any extra protocol work. It security properties are about the same as
in SIR, and its security is not that much worse than in SIR. So if we
want to do something that is more secure than what there is already
now, then I would like to make that then really secure. 
-- 
[email-masked]
_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec

---

From: Yoav Nir <[email-masked]>
Date: Sun, 17 Aug 2008 01:26:42 +0300

> the liveness checks if there was active traffic going on between the

I'm not sure this is the normal case. I spent most of the IETF meeting  
with the client connected, but the only traffic to the company was,  
that every 5 minutes or so, the mail client would poll the IMAP  
server. If the clients do gratuitous liveness checks all the time,  
they would notice a crash, but if they wait for IMAP to fail, they  
might miss it.

Linux-based servers boot up in less than a minute. "Hardware"  
appliances are even faster, and the VPN software comes up very  
quickly. Besides, most VPN software has some kind of button or command- 
line to erase all the tunnels (setkey -F). That's like an  
instantaneous reboot of "Bob". Users tend to use this whenever they  
feel that "something is wrong".

> getting one of the liveness checks anyways and reply to it.

That's an idea, but you still have 30 seconds of both Bob and Alice  
ready, but traffic does not go through.

---

From: Tero Kivinen <[email-masked]>
Date: Mon, 18 Aug 2008 13:23:37 +0300

> they would notice a crash, but if they wait for IMAP to fail, they  

Even if the machine only notices the crash when it does IMAP poll to
server, the user most likely will not detect that crash at all, as he
is not actively waiting for the email to come in, he will simply see
the email notification to be delayed for some time, and as he is not
doing anything active there, he will not actually notice that at all.

I think your use is quite common, but fast crash discovery is not an
issue in that kind of situations. The fast crash discovery and
recovery is needed when you do active network operations, and in most
of those cases the user will see the problem regardless how fast we
recover (i.e. the VOIP call gets dropped, or too many packets get
dropped in the video stream).

It is bit hard to think about situation where it would be ok to have
10 second network break, where you need to recoved that faster than 30
seconds, but where that 10 second break will not distrupt user too
much already. 

> Linux-based servers boot up in less than a minute.

Quite a lot of PC server hardware require 30-60 seconds to go through
the bios only (at least the server hardware we have in the office,
seems to be much, much slower to boot up than desktop machines).

Recovering from the crash in less than a minute is extremely good
result for any real server. 

> "Hardware"  
> quickly.

Most of the ADSL boxes or WLAN boxes and similar do seem to require
30-60 second boot time before they are ready to server anything.
Usually bigger boxes do require even more time.

> Besides, most VPN software has some kind of button or command- 

That is not an instanteneous reboot of "Bob", it is instanteneous
reboot of "Alice". I.e local end clears all SAs thus when you try to
send next packet, there is no need to do any recovery, you just start
new negotiation to the "Bob", and "Bob" will clear its own SAs when it
receives INITIAL_CONTACT notification.

> ready, but traffic does not go through.

Nope, you have most likely 10-15 seconds of time when they are both
capable of processing traffic. This is because the Alice will start
recover why Bob is still down, i.e. the retransmission timers overlap
with the actual recovery time of the Bob.

I.e. when Bob goes down and starts rebootting (lets say that it is
very fast reboot, taking less than minute, lets say 45 seconds). The
Alice will notice after short while there is no traffic coming back
(incoming ESP packets suddenly stop, thus traffic is changed to be
one-way), it will decide to do liveness check, and starts IKE exchange
to do that.

Lets say it takes 10 seconds since Bob went down to start that (our
default for one-way liveness check timer). It sends packets to black
hole for 35 seconds, as Bob is not yet up (it might already get some
ICMP host unreachable back for some of those depending on the network
infrastructure). Then when Bob gets up it starts sending
INVALID_IKE_SPI and that can then trigger Alice to shorten its default
5 minutes retry timer (for mobike, the retry timer must be longer than
2 minutes, as otherwise you loose connectivity in normal network
switch situations too often).

Alice could make it so that received INVALID_IKE_SPI notification
shortens the retry timer so it is for example 15 seconds after
receiving first of those notifications, or 30 seconds after receiving
ICMP error. That would cause 15 seconds of time when both Alice and
Bob are up and running, but where Alice still tries to recover, before
it recovers from start.
-- 
[email-masked]
_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec

---

From: Yoav Nir <[email-masked]>
Date: Mon, 18 Aug 2008 18:07:22 +0300

Hi Tero

Depending on the IMAP client Alice is using she may or may not notice  
anything is wrong as long as Bob is down. One client I know pops up a  
message that connection to IMAP server has failed. But that doesn't  
matter, because there's nothing to do at that time, and also it  
doesn't involve the IKE/IPsec software.

The IKE software gets the first indication that something is wrong  
when Bob boots up and sends an INVALID_SPI (or ICMP reject for UDP  
4500). By that time Bob is up, so that's when the "several minutes" or  
"30 seconds" begin. That's considerably worse than the nearly  
instantaneous reconnect she can get with either QCD, SIR or birth  
certificates.

I'm not sure why it's a good idea to reduce the time span in the  
presence of INVALID_IKE_SPI notifications. If 30 seconds is long  
enough to be sure we get a response from the real peer (in addition to  
an attacker) in the crash detection case, why is it not enough in the  
liveness check case? 
_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec

---

From: Yoav Nir <[email-masked]>
Date: Mon, 18 Aug 2008 18:45:59 +0300

Hi Tero

---

From: Pratima Sethi <[email-masked]>
Date: Tue, 19 Aug 2008 14:02:21 +0530

> up, you do not need to do any additional computations.
Is there a specification of Birth Certiifcates that you can point us to ?

 From what I understand ,Bob generates a single certificate when he 
reboots, and will add that as  a birth certificate payload, to the 
invalid_spi notification. If  Bob only generates one certificate 
independent of the client Alice, Mallet( the MitM) can snoop and learn 
the birth certificate and replay this to any Alice connected to Bob. How 
does Alice trust that the information is a fresh valid packet generated 
by Bob and not a "constructed" packet from an attacker.

- prati

---

From: Yoav Nir <[email-masked]>
Date: Tue, 19 Aug 2008 12:19:18 +0300

On Aug 19, 2008, at 11:32 AM, Pratima Sethi wrote:

> independent of the client Alice, Mallet( the MitM) can snoop and  
> learn the birth certificate and replay this to any Alice connected  
> to Bob. How does Alice trust that the information is a fresh valid  
> packet generated by Bob and not a "constructed" packet from an  
> attacker.
>
> - prati

There is no real specification of birth certificates, just an idea in  
email from 7 years ago.

Such certificates would not be full X.509 certificates. They should  
include two fields: a public key, and a birth date (or restart  
counter), plus of course a signature using private key matching the  
public key, so it's a self-signed certificate.

When bob reboots, it signs a new certificate with the same public key,  
but  a newer date or counter.

During the AUTH exchange, Bob sends the certificate (with restart  
counter at 17) to Alice.  Alice verifies nothing, just stores it.
When Bob reboots, he creates a certificate with restart counter 18.
When Alice sends traffic, Bob attaches the new certificate to the  
INVALID_SPI or INVALID_IKE_SPI notification.
Now Alice validates that (1) the public key is the same, and (2) the  
restart counter is greater than that stored with the IKE SA, and (3)  
the signature verifies.

That's how Alice knows that Bob really rebooted in between.

Nice idea, but I see trouble with key management, and also with  
signature agility.  We probably don't want to add algorithm  
negotiation, so SHA1+RSA?  SHA1+DSA?  SHA-256+ECDSA?

It also makes everything more complicated.

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 19 Aug 2008 13:17:49 +0300

Yoav Nir writes:
> 4500).

Note, that Bob does not send INVALID_SPI until Alice sends something
to Bob. As I told, in our implementation if the traffic is only one
way (i.e. Alice sends packet, but Bob does not reply) then the
liveness check is started 10 seconds after last packet from Bob is
received (after the liveness check successed, then that is accepted as
valid case of one-way traffic, i.e. no second liveness check is done
before situation changes).

Thus Alice is already doing liveness check while Bob is booting, as I
explained in my last message. 

> By that time Bob is up, so that's when the "several minutes" or  

No, the several minutes starts quite quickly after the traffic is
changed to one way, i.e. after Alice sends one packet and Bob does not
reply to that. 

> an attacker) in the crash detection case, why is it not enough in the  

In MOBIKE 2 minutes was not enough for waiting for the response from
real peer, as you might need to try 3-4 different IP address pairs
before you find correct working address (3 if one end has 2 IP-address
and other 1, and 4 if both ends have IP-addresses). For each you need
to send 3-4 tries, which means you are sure you cannot find working
pair only after dozen or so packets, and with exponential backoff that
is long time (actually you need to limit the max backoff to get any
reasonable recovery, in our cases we only double the timer up to 6
seconds (i.e. packets are sent 0.5, 1, 2, 4, 6, 6 second intervals)).
To send 12 packets takes more than minute already even with that, and
if you have more than 2 IP-addresses (for example both IPv4 and IPv6
addresses in both ends, plus multiple interfaces on the Alice end
(wlan, gprs, fixed ethernet)) you might end up in quite many
retransmissions before you find out working IP-address.

Good thing with MOBIKE is that you sometimes do get notification from
the network (link goes down etc) immediately when the addresses
change. Bad thing is that sometimes you need to run DHCP etc to get
the address you need to use, so that will even more add delay to
recovery.

30 seconds is much faster than the 3-5 minutes you need to wait in
normal case to be sure that the other is not reachable. On the other
hand there are normal operational cases where there is 30 second - 60
second delays even when nothing is wrong, just because you roamed out
of the range of the WLAN network you happened to use. Because of this
there is not really point of trying to get sub-second recover times,
when other delays are still in the order of tens of seconds or
minutes.

Because of that I would much rather have the birth certificates or the
QCD as they do offer cryptogarphic response that the other end is
down, thus they do offer something more than what can be achieved now
with liveness checks. SIR on the other hand does not offer that much
more compared to normal liveness check, so I do not consider that an
good option.

But in all cases we need to think where this will be useful, and does
it really help that much in common usage scenarios. In normal cases I
would consider crashing SGW very uncommon situation, compared to for
example roaming happening in the MOBIKE case. I would consider year a
minimum uptime for real SGW, thus this secure crash recovery protocol
is only needed once per year or so. If your SGW crashes more often
than once per year, it is better to use resources to fix the SGW
software than to make protocol to recover from those crashes.
-- 
[email-masked]
_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec

---

From: Pratima Sethi <[email-masked]>
Date: Tue, 19 Aug 2008 15:48:01 +0530

thanks for the explanation of the exchange. I had forgotten that this 
required a pre-exchange of the certificate.

- prati

Yoav Nir wrote:
>> learn the birth certificate and replay this to any Alice connected to 
>> Bob. How does Alice trust that the information is a fresh valid 
>> packet generated by Bob and not a "constructed" packet from an attacker.
>>
>> - prati
>

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 19 Aug 2008 15:33:32 +0300

> Is there a specification of Birth Certiifcates that you can point us

No, that was never written to draft form of its own. It was presented
on this list by Bill Sommerfeld long time ago. It has been explained
in few drafts quite shortly, for example in the
http://tools.ietf.org/html/draft-ietf-ipsec-soi-features-01 section
3.5:

----------------------------------------------------------------------
3.5 Birth certificates

Assume Alice and Bob have an SA established, and that Bob crashes and
restarts. Alice will send a packet into an SA that Bob doesn't know
about. Birth certificates are a method for letting Alice know that the
SA is no longer alive.

It is desirable that such a mechanism be inexpensive for Bob. If a
mechanism required a lot of computation, for instance, having Bob sign a
customized message saying, "This SA didn't decrypt properly. Perhaps
it's because it's a reused SA number from before I crashed" or "unknown
SPI", then there is an easy DOS attack on Bob's limited computation by
sending him bogus messages. If Bob sends totally unauthenticated
messages, it is difficult for Alice to act on them, since an active
attacker could send her "no such SPI" messages to cause her to close
connections.

The idea of a birth certificate, originated in the IPsec Working
Group by Bill Sommerfeld, is that Bob should have a monotonically
increasing number that increases each time Bob restarts. When Bob
restarts, he signs a message saying, "this is my incarnation number".
When Bob creates an SA, Bob optionally sends his birth certificate.
Alice can optionally keep this certificate with her SA. Then, if Alice
ever receives an error message from Bob with a birth certificate with a
higher incarnation number, she can remove all SAs associated with Bob's
previous incarnation.

This mechanism is somewhat overlapping with the "initial-contact"
mechanism in IKEv2. Discussion in the WG suggested that birth
certificates could replace initial-contact, but some people said that
both were valuable.
----------------------------------------------------------------------

Or from http://tools.ietf.org/html/draft-ietf-ipsec-ikev2-rationale-00
section 3.1:

----------------------------------------------------------------------
   - adding in Bill Sommerfeld's "birth certificate" idea. In this idea
   Bob keeps a number in nonvolatile memory that increments each time
   the node restarts. When Bob restarts, he signs a "birth certificate"
   stating what the value of that counter is. This birth certificate is
   transmitted as a payload in message 4. Alice keeps this value. If Bob
   ever receives an ESP packet that doesn't decrypt properly or with an
   unknown SPI, he responds to that packet with his birth certificate.
   If the recipient has an SA for Bob with an older birth certificate,
   this lets them know Bob has restarted and forgotten state for that
   SA. We decided not to add that to this version of the draft, although
   we think it is a good idea, until it's been written up in a separate
   draft and there has been an opportunity for people to understand it
   and give feedback.
----------------------------------------------------------------------

I think this was the original email message explaining them on the
ipsec-list http://www.vpnc.org/ietf-ipsec/00.ipsec/msg01415.html:

----------------------------------------------------------------------
Message-Id: <[email-masked]>
In-reply-to: Your message of "Mon, 07 Aug 2000 15:55:21 PDT."
             <[email-masked]> 
From: Bill Sommerfeld <[email-masked]>
To: Scott Fanning <[email-masked]>
cc: Derek Atkins <[email-masked]>, [email-masked],
        "Scott G. Kelly" <[email-masked]>, Skip Booth <[email-masked]>,
        Paul Hoffman <[email-masked]>, [email-masked]
Subject: Re: Heartbeats Straw Poll 
Date: Mon, 07 Aug 2000 19:09:50 -0400
Reply-to: [email-masked]

> Maybe we need a "death certificate" CA :-) 

Heh.  Actually, one of the ideas I'm kicking around:

If we have the system sign a "birth certificate" when it reboots
(including a reboot time or boot sequence number), we could include
that with a "bad spi" ICMP error and in the negotiation of the IKE SA.

This pushes the burden of reestablishing state to the end which
already thinks it has shared state and has traffic it wants to send.

The system which is receiving packets to unknown spi's merely has to
respond with a simple message which involves no real-time cryptography
(it should, of course, be rate limited).

The system receiving the error message can discard it if it doesn't
correspond to existing state or if it's "old news" (i.e., you get
replay protection); if it's not old news, you can rate-limit how often
you attempt to verify the signature.

I *think* this is relatively resistant to replay and DoS...

                                        - Bill
----------------------------------------------------------------------

> by Bob and not a "constructed" packet from an attacker.

The Bob also sent that same certificate with the counter (or
timestamp) inside of it when it created the SA. The Alice will receive
the birth certificate, and first check if the counter is same than
before. If it is, then it knows this is old news, and it can simply
ignore the notification. If it has larger incarnation number than the
one used when creating the SA, then it can validate the signature of
the certificate and if that is valid, then it knows that Bob has
rebooted since they created the SA, thus Alice can safely remove all
IKE and IPsec SAs between her and Bob. As only Bob can create valid
signatures, and Bob only does that after reboot Alice can know for
sure that Bob has rebooted.

The incarnation number can be timestamp or simple running counter, the
only property that is required is that it cannot go backwards, and it
has bigger number than it had before every time the machine is booted.
As certificates do require clock or similar already, that same clock
can be used here too.
-- 
[email-masked]
_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 19 Aug 2008 15:46:37 +0300

> negotiation, so SHA1+RSA?  SHA1+DSA?  SHA-256+ECDSA?

If you are using certificates already, then the best pick would be
using the same key (RSA/DSA/ECDSA) as in your authentication key, as
other end must be able to process that. Same thing with the hash
algorithm, i.e. using the same hash algorithm as what was used for the
main certificate in the authentication phase.

If you are not using certificates, but raw RSA keys then again using
same key and hash function you are using for the authentication would
be work.

If you are using shared secret then you most likely would need to
either use the hash that is already used in the negotiation (but as we
do not negotiate hash separate, only as part of integrity alrogithm or
pseudo-random function), or we can simply say we SHOULD use SHA-1 hash
or stronger.

Note, that if the other end cannot verify the birth certificate
because of the unsupported hash function, the responder will simply
ignore the birth certificates and revert back to old method, i.e.
cannot do fast crash recovery.

Note, that there is no reason why Bob needs to have only one birth
certificate, it can sign same data with multiple hash functions and
select which one of them to send (or send them all during the error
message).

In general case I think we will end up so that implementations use one
common algorithm for it (RSA + SHA1 in most cases, I would guess for
now), and in they can be configured to use something else if needed
(i.e. ECDSA + SHA-256 in certain environments). The selected
algorithms are then mandated by the environment...
-- 
[email-masked]
_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec