[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Replay protection with Manual keying



Ref:  Your note of Thu, 05 Sep 1996 17:08:39 -0400 (attached)


Naganand,

 >
 > We were trying to implement HAMC-SHA with replay protection. We support only
 > manual keying as of now. Are we right in saying that one should not use
 > replay protection with manual keying?
 >
 > We came up with this conclusion because of what happens when either the
 > sender or the receiver crashes. If the sender crashes, when the machine is
 > rebooted the sequence number starts from 1. However, the receiver does not
 > know about this and rejects all packets thinking it is replay attach. In
 > manual keying, the SA'a are static. The only way to avoid this is to keep
 > track of the sequence number and make it persistent.
 >
 > Comments?

Manual keying makes sense in some scenarios for relatively-long lived
master keys. Even in that case support for automatic fast key refreshment
(for security and re-sync as you note) is necessary.
We have been arguing for this need for long time (fortunately, fast
re-key is now part of all the major proposals in this group; also
see our MKMP paper - usenix'95).

 >
 > -Ron Arbo and Naganand Doraswamy
 >

From: Rich Skrenta <skrenta@osmosys.incog.com>
Message-Id: <199609061817.LAA06333@miraj.incog.com>
Subject: SKIP Design & Applicability Statement
To: ipsec@TIS.COM
Date: Fri, 6 Sep 1996 11:17:23 -0700 (PDT)
X-Mailer: ELM [version 2.4 PL24 PGP5]
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: ipsec-approval@neptune.tis.com
Precedence: bulk

Several people, including Paul Lambert, have asked us to provide a list of
differentiators between SKIP and other KMP proposals.  Ashar has recently
expanded his applicability statement for SKIP; I'll include it below.

This is also available on our web site at
	http://skip.incog.com/skip-applic.html

-----------------------------------------------------------------------------

             Design Issues and Applicability Statement for SKIP

Ashar Aziz
Distinguished Engineer
Sun Microsystems, Internet Commerce Group

Introduction
------------

This note describes applications and usage of SKIP in Internet/Intranet
environments, and motivations behind the design of SKIP. (A detailed
description of the SKIP protocol may be found in the online internet-drafts
directories under draft-ietf-ipsec-skip-*.txt).

SKIP enables the establishment of keys with no interactive message exchanges
required between the principals wishing to establish a secure channel. The
base SKIP mode allows the computation of a master key using each principal's
certified DH key. Re-keying is performed inline, by encrypting the traffic
key using the master key, and sending the encrypted traffic key inline with
the packet. The master key computation requires a single DH operation,
during the lifetime of communications between two principals, after which it
can be cached using the same techniques used to store each principal's
long-term private key.

An important point is that the master key is non-interactively and
independently computed by each principal (host, user, etc.). The other
principal neither needs to participate nor even be connected or available on
the network at the time of master key computation. Only the other
principal's certified DH value need be available and this can be distributed
using central servers as through a name service such as secure DNS. This is
important for practical reasons to be discussed shortly.

SKIP supports an ephemeral DH exchange, which provides Perfect Forward
Secrecy (PFS), for situations which require PFS. A protocol has the PFS
property when the compromise of long-term keying material does not
compromise data encrypted in the past (which may have been recorded), and
whose associated transient traffic keys have been deleted from the system.

The inline key-update used in SKIP also works for multicast environments. A
SKIP extension describes how to set-up and refresh traffic keys for
multicast data.

We describe some illustrative application and usage scenarios of SKIP and
its extensions. The example usage scenarios below is not an exhaustive list
of the uses of the SKIP protocol. Rather it is an illustrative list provided
in order to present the considerations that motivated the design of the SKIP
protocol.

Secure Domain Management
------------------------

ipsec protocols will be used in the Internet and Intranet environments not
only to establish secure encrypted channels between two nodes, but also to
establish and manage the security of critical network elements, e.g.
encrypting firewalls, routers etc.

There are two essential components of management that impact key-management;
traps and alerts from managed devices and set operations from management
station to managed devices.

Both of these operations are urgent operations. Namely, they need to be
processed and dispatched in a timely manner for security management to be
effective. The aspect of security that is critical here is authentication of
traps/alerts from managed devices and the authentication of the set
operation from the management station. Secrecy is typically a secondary
concern here, therefore PFS is a moot issue for this application.

An example scenario: Assume a large enterprise containing hundreds (possibly
thousands) of security critical elements, such as firewalls or routers, at
the perimeter of the enterprise.

These firewalls might be programmed to detect security events (such as
penetration attempts) and inform the management station of such events via
network management traps or alerts.

In case such an event occurs, it is unlikely that prior security
associations will always exist, since security associations are intended to
be temporary and will go away on reboot/power up of either management
station or managed device.

(Trying to re-establish these associations on each re-boot of a management
station, where each association could take a second to a few seconds, would
result in a hour's worth of security association for a few thousand managed
devices, a significant limitation. Another factor making this impractical is
that not all managed devices may be powered up or available at the time the
management station is re-booting, making interactive key-establishment on
each re-boot more problematic).

In case intrusion events are detected by the firewall complex (possibly from
all over the site), this could result in a few hundred to a thousand traps
to the management station(s). Assuming a second (or two) per new association
this leads to an overwhelming 1/2 hour to an hour worth of compute time on
the management station simply to process the association requests,
essentially bringing it down, and rendering it useless to take management
action (such as shutting down part of the firewall complex or other such
action).

One could question if all perimeter devices would be simultaneously
attacked. However, if the key-management presents an achilles heel in such
situations, where simultaneous attack would result in disabling all
management stations, then this is precisely the sort of attack one should
expect.

Another argument could be that one could use permanent security associations
for handling such applications, where the session key is negotiated once and
then cached.

There are several limitations of this approach: The first is that permanent
caching of an association essentially results in freezing the traffic key,
an undesirable feature from a cryptographic perspective, where frequent key
changes represent the best defense against cryptanalysis. Dynamic
key-management is the entire goal of ipsec key management, and permanent
security associations are a step back to manual key-management. Another
limitation is that in case association state is ever lost on, say, the
managed device then *both* the management station and the managed device
need to re-compute the key, resulting in the same overhead issues discussed
earlier should this need to happen at urgent message time from many managed
devices.

Cached associations for management are no more elegant or practical than
running SNMP over cached TCP connections.

If SKIP is used for this application scenario, then the limitations
discussed earlier do not exist.

A SKIP master key (Kij) is the only expensive part of the base SKIP
protocol, and this can be cached. Caching the master key doesn't freeze the
traffic key, since the two are independent. Re-keying happens inline, so a
single message representing an urgent trap or alert allows key refreshment,
without incurring a second per message worth of compute time. This is
because only symmetric key operations need to be performed per message. In
case the master key is ever lost on a managed device, then only the managed
device needs to re-compute it, not the management station, which is the
bottleneck in this application scenario.

A thousand or so traps can be processed in a total time of a second or so,
with no extra messages required for key-management purposes. The management
station is able to respond with, say, an authenticated shutdown to the
entire firewall complex in a few seconds, not hours.

A key-management approach that does not adequately meet the needs of
scalable and secure network management is not only incomplete, it represents
a serious security vulnerability for the Internet community. Security
without effective security management will be difficult, if not impossible,
to establish and maintain.

Large Scale Servers
-------------------

A large scale web, mail or file server is expected to receive many
simultaneous connection requests, which can all potentially result in a new
security association requests. Several hundred or thousand requests can
result in computational overload for servers, even if each new association
takes only a second or two.

One could question whether a thousand new requests can occur simultaneously
to a server. The answer here is yes, probably even frequently, when one
considers that they don't all have to occur at the very same instant. Even
if 20 requests occur in the same 1-2 second time frame, processing these new
associations could take 20-40 seconds, and the rest of the requests could
occur in these 20-40 seconds, in order to have the overloading effect of a
hundred/thousand simultaneous requests. Another way of looking at this is as
follows: if the new association requests come in at a rate faster than they
can be processed then this results in a server meltdown situation. For
example, if a new association requires 2 seconds to process, then an
averaged rate of 1 new request per second is sufficient to completely
overload the server. Such a rate is not far-fetched for typical servers in
use today, such as web, mail or file servers, and can certainly occur during
peak usage times.

(Long-term caching of associations is problematic for the reasons noted
above.)

Servers represent a special issue in the trade-off considerations between
performance and security. Servers are typically used to store long-lived
information, such as files, mail messages, or web pages. If PFS is being
employed to encrypt all traffic to/from the server (and the contents of the
secure conversations are stored on the server, e.g. a mail message, or a web
page, etc.) then compromise of the principal's long-term key can still
result in compromise of encrypted traffic. This is because compromise of a
principal's long-term key will always result in authentication failure. The
attacker who has compromised the long-term key is able to impersonate the
legitimate user, and connect to the server to recover the traffic that was
originally encrypted over the channel in PFS mode.

There is one (important) aspect in which PFS offers a better defense than a
non-PFS solution. Namely, if the key-compromise is discovered, the keys may
be revoked, thereby protecting against future impersonation attacks and
still preserving the secrecy of past encrypted data.

However, there are many circumstances in which long-term key-compromise may
not be discovered, and if it is discovered, may be discovered too late.

Therefore, the trade-off in such situations is to take the performance
penalty imposed by a PFS protocol (such as SKIP PFS), in order to guard
against discoverable key-compromise, or to use a lighter-weight protocol
without PFS (such as the base SKIP mode).

There may not be a single right answer here. Some sites may wish to accept
degradation in server performance, and choose the PFS approach because they
believe that key-compromises will be discoverable. Other sites may choose a
lighter weight protocol without PFS, because they believe that guarding
against discoverable key-compromises isn't worth the performance penalty.

We believe this is a choice that should be left to the user community.
Certainly, if all the ipsec protocol is providing by way of security is
authentication, so that the server may perform authenticated access control,
then the entire PFS issue is moot, and the overhead entailed by PFS is
clearly unnecessary.

Low-End devices
---------------

IP layer security is being implemented on low-end devices such as
computationally constrained CPUs (embedded designs, palm-tops, Internet/Web
terminals etc.). The computational overhead of performing even a few public
key operations simultaneously is a challenge for such computational
platforms. The low computational overhead of the base SKIP mode permits it
to be easily implemented on such low-end devices.

High Availability of Encrypting Firewalls/Routers
-------------------------------------------------

Another sample application usage of SKIP is to enable the set up of a
redundant set of intermediate nodes in order to provide failover of
encrypted traffic. IP routing provides for failover for unencrypted traffic,
and this feature is especially important at enterprise connections to the
Internet, where a single point of failure may represent the failure of a
mission critical application, requiring secured access to the enterprise
from across the Internet. An example of this might be mobile sales people,
requiring secured access to corporate information from field locations. If a
single firewall or router was handling several hundred or thousand such
sales people, then it is highly desirable that failure of either the link or
the Intermediate device providing encryption services should not result in a
loss of secure connectivity to this large group of users.

SKIP permits multiple intermediate nodes (routers, firewalls, etc.) to be
configured to share the same long-term DH public/secret value, and the same
master key-id. Failover of encrypted traffic is provided by standard dynamic
IP routing facilities.

As described above, an intermediate device may compute and cache SKIP master
keys (Kij) without ever communicating with the end units that may connect
through it.

At failover time, an encrypted/authenticated packet that was intended for a
failed unit may be re-routed to a redundant standby unit and processed
without requiring several public key operations per new source of encrypted
traffic. Thus failover scales to thousands of encrypted channels, because
there is much lower overhead in processing each new source of encrypted
traffic.

One could argue that failover can still be achieved using an association
based approach, by allowing alternate encrypting nodes to detect failover by
receiving an ipsec packet for which a local SPI does not exist (for that
src, dst IP address pair). In case such a packet is received, the alternate
device can negotiate a new session key for that (src, dst) IP address pair.

There are two problems with this approach. The first is that there is no
requirement that an SPI with a given (src, dst) IP address be unique across
nodes. It need only be unique on a given receiving node, since there is no
coordination between nodes of SPI values. This means there is a possibility
that that same SPI value for the given (src, dst) IP address already exists
on the alternate node (with a different session key). In this case, failover
would not be detected and therefore no failure recovery would occur.

The second problem is that this doesn't scale to failover of thousands of
secure channels, since this would require the alternate intermediate node to
negotiate (simultaneously) thousands of associations. At the rate of a few
seconds per association, this could easily take on the order of hours, which
would be an unacceptable delay for end nodes in the field requiring secured
access.

It is impractical in the association approach for an intermediate node to
cache security associations for all possible end or intermediate nodes that
may require access through it. This is because a) The end nodes may not be
available at the time such caching may need to be performed, b) the location
of the end node (in terms of IP address) may not be known, since many of
these nodes may be coming through dynamically assigned IP addresses and c)
the end node may be connected through a dial-up telephone or ISDN link,
involving a monetary expense simply for association caching purposes.

High availability of the network is an important practical issue, and was a
motivating feature for the design of IP in order to build survivable
networks. It is important to preserve this feature, as the networks become
secure.

High-Speed Links
----------------

An issue for cryptographic security and high speed links is the frequency of
key updates. Key-updates need to be related to the amount of data encrypted
in a given key and not be a function of time alone. For a given key-update
policy (e.g. change the key every 100 Mbytes of encrypted traffic), this
translates to a thousand times more frequent key-update rate, when going
from a 1 Mbit/s link to a 1 Gbit/s link.

This means that a key-update policy that requires a key-update every 15
minutes on a 1 Mbit/s link, translates to a key-update faster than once per
second on a 1 Gbits/s link.

Using an approach that requires an interactive message exchange for each
key-update means that two messages per second will be required for
key-updates on a Gbit/s link. If this node is talking to thousands of other
such high-speed nodes, the messages required for key-updates increase a
thousand fold.

(These are not unrealistic scenarios for an Internet that is simultaneously
getting bigger and faster.)

The node must wait at least a round-trip delay time prior to re-keying. This
is simply a fact due to network latency.

Each lost key-update message means one of two things. a) either wait for a
retransmission of the key-update message and degrade throughput or b)
continue transmitting using the old key and violate the local key-update
policy.

Since SKIP performs inline re-keying, the message exchanges and the latency
inherent in a round-trip message exchange are both avoided. Re-keying can be
performed as frequently as desired, even once a packet, because no message
exchange or round-trip delays are incurred in doing this.

The issue here is purely one of inline keying. Inline re-keying can be used
in conjunction with an ephemeral master key, and still have fast re-key in
conjunction with PFS (e.g. as in the SKIP PFS draft).

It could be argued that one could come up with key-update rates that are far
less frequent for these high-speed links, since all known attacks on the
cryptosystems intended to be used require an impractical amount of known or
chosen text.

However, this precludes key-update policies that may wish to be more
conservative in the amount of data encrypted in a given key. It is entirely
possible that future attacks may be discovered that require less plaintext
encrypted in a given key (either known text or chosen) and such attacks
could compromise past encrypted data which used less conservative key-update
rates. A more conservative key-update policy would prevent future discovery
of these attacks from compromising past encrypted data.

The attacks being defended against here are purely passive attacks, since
discovery of a future cryptanalytic attack permits the adversary to take
recorded encrypted traffic (and any associated known text) and simply apply
the attack techniques to it. This is a far more feasible form of attack than
active forms of attack against past encrypted traffic (e.g. compromising a
long-term secret key).

Multicast IP Issues
-------------------

An important part of multicast key-management is scalable re-keying, where
the re-key operation needs to scale with the size of the multicast group.

A scheme that requires a central Key Distribution Centre (KDC) to supply the
multicast traffic keys doesn't scale very well, because this requires
key-management traffic proportional to the size of the multicast group and
the key-update rate to and from a single entity.

Alternative schemes that have been suggested involve encrypting the traffic
key in an interchange key that the group members already possess and
multicasting the encrypted traffic key to all the group members. This
approach has a significant drawback.

First, IP multicast is an unreliable operation. There can be no assurance
that all the group members in fact have received the new traffic key.
Without knowing if and when the group members have received the encrypted
multicast traffic key, it is difficult to start using the new key.

One could use some reliable multicast transport protocol, but these also
represent scaling problems. In any case, it is a limitation to have to
introduce a reliable multicast protocol when it may not be necessary for the
IP multicast application requiring security.

Other drawbacks include some of the drawbacks mentioned above for high speed
links. How does one perform rapid re-key for multicast over high speed
links, if the re-key operation requires an acknowledgment from all group
members?

SKIP's use of inline re-keying solves these problems. There is no need to
introduce a reliable multicast transport protocol. A multicast group can be
re-keyed as rapidly as desired, independent of the size of the multicast
group and independent of network latency and round-trip time issues.

SKIP multicast inline re-key scales simultaneously to arbitrary size
multicast groups and high-speed links, has no synchronization issues
associated with the re-key operation, and works in the presence of packet
losses.

SKIP PFS
--------

SKIP PFS is a simple, 2-message exchange that provides authenticated PFS. In
addition, it also provides anonymity of the parties involved in the
exchange. The exchange does not use non-repudiable signatures. Therefore it
also has the desirable property of deniability of an exchange, which is
important for privacy considerations. Namely, one doesn't want to provide
each party a non-repudiable proof that a secure conversation tool place,
because one may wish to later deny that the conversation took place.

The overhead of SKIP PFS is comparable to the overhead of other protocols
that provide PFS, but significantly greater than the overhead of the base
SKIP mode.

PFS is highly desirable in many environments which require long-term secrecy
of information, even in the presence of the compromise of long-term keying
material. Ideal use of PFS is to encrypt ephemeral data (i.e. data that is
never stored in the network), because the ephemeral nature of the keys will
permanently (assuming high-strength DH) remove the ability to recover the
encrypted material from any source, including the recorded ciphertext.

Scalability
-----------

Any approach that is being considered for use on the Internet needs to be
scalable. This scalability has many facets to it. Specific aspects of
scalability, and features of SKIP that aid each aspect, are described above.
This includes scalability for management of large secure domains containing
many devices, large-scale web/mail/file/ servers, low-end devices (e.g.
Internet/web terminals), high-speed networks, and large multicast groups.

Simplicity
----------

Although the functionality described above is important (and we believe,
critical) for a scalable approach to key-management, an important element is
the complexity of an approach to achieve its end objectives.

Whereas simplicity and complexity are in the end a subjective judgement, we
believe that the balance in the SKIP protocol lies towards simplicity. When
multiple ways of achieving a cryptographic objective (e.g. PFS or anonymity)
exist, a single and most often the simplest approach is specified.

This simple approach is not limited to solving only simple problems. For
example, inline re-key is a simple mechanism that simultaneously addresses
complex key-management issues related to urgent secure messages, encrypted
multicast traffic, and high-speed networks.

We believe that a simple approach aids in the building of interoperable
implementations, and the security analysis of the final systems, both from a
protocol and implementation point of view.

A simple approach is also quicker to build and deploy. This is an important
practical issue, considering the pressing need for security at the network
layer of the Internet.