IPSEC always does 3DES with three different keys, as required by RFC 2451. For an explanation of the two-key variant, see two key triple DES. Both use an EDE encrypt-decrypt-encrpyt sequence of operations.
Double DES is ineffective. Using two 56-bit keys, one might expect an attacker to have to do 2112 work to break it. In fact, only 257 work is required with a meet-in-the-middle attack, though a large amount of memory is also required. Triple DES is vulnerable to a similar attack, but that just reduces the work factor from the 2168 one might expect to 2112. That provides adequate protection against brute force attacks, and no better attack is known.
3DES can be somewhat slow compared to other ciphers. It requires
three DES encryptions per block. DES was designed for hardware
implementation and includes some operations which are difficult
in software. However, the speed we get is quite acceptable for many uses.
See benchmarks below for details.
Fifteen proposals meeting NIST's basic criteria were submitted in
1998 and subjected to intense discussion and analysis, "round one"
evaluation. In August 1999, NIST narrowed the field to five "round
two" candidates:
Adding one or more AES ciphers to Linux FreeS/WAN
would be useful undertaking, and considerable freely available code exists
to start from. One complication is that our code is built for a 64-bit
block cipher and AES uses a 128-bit block.
Volunteers via the mailing list
would be welcome.
For more information, see the
NIST AES home page or the
Block Cipher Lounge AES page. For code and benchmarks
see
Brian Gladman's page
.
Bruce Schneier extends
these with many others such as Eve the Eavesdropper and Victor the
Verifier. His extensions seem to be in the process of becoming
standard as well. See page 23 of
Applied Cryptography
Alice and Bob have an amusing
biography on the web.
Outside IPSEC, passwords are perhaps the most common authentication mechanism. Their
function is essentially to authenticate the person's identity to the system.
Passwords are generally only as secure as the network they travel over. If
you send a cleartext password over a tapped phone line or over a network
with a packet sniffer on it, the security provided by that password becomes
zero. Sending an encrypted password is no better; the attacker merely records
it and reuses it at his convenience. This is called a
replay attack.
A common solution to this problem is a challenge-response
system. This defeats simple
eavesdropping and replay attacks. Of course an attacker might still try
to break the cryptographic algorithm used, or the
random number generator.
IPSEC uses the Diffie-Hellman key exchange protocol to
create keys. An authentication mechansim is
required for this. The methods supported by FreeS/WAN are discussed in our
configuration document.
Having an attacker break the authentication is emphatically not a
good idea. An attacker that breaks authentication, and manages to subvert
some other network entities (DNS, routers or gateways), can use a
man-in-the middle attack to break the security
of your IPSEC connections.
However, having an attacker break the authentication in automatic keying
is not quite as bad as losing the key in manual keying.
The University of Wales at Aberystwyth has done quite detailed tests
and put their results on the web.
Even a 486 can handle a T1 line, according to
this mailing list message:
If you want to measure the loads FreeS/WAN puts on a system, note that
tools such as top or measurements such as load average are more-or-less useless
for this. They are not designed to measure something that does most of its work
inside the kernel.
The second person has 1 chance in 365 (ignoring leap years) of
matching the first. If they don't match, the third person's
chances of matching one of them are 2/365. The 4th, 3/365, and
so on. The total of these chances grows more quickly than one
might guess.
DES is among the the best known and widely used
block ciphers, but is now obsolete. Its 56-bit key size makes it
highly insecure today.
Triple DES is the default transform for
Linux FreeS/WAN because it is the only
cipher which is both required in the RFCs
and apparently secure.
The current generation of block ciphers -- such as
Blowfish,
CAST-128 and
IDEA
-- all use 64-bit blocks and 128-bit keys. The next generation,
AES, uses 128-bit blocks and supports key sizes
up to 256 bits.
The
Block Cipher Lounge web site has more information.
This is not required by the IPSEC RFCs and
not currently used in
Linux FreeS/WAN.
Longer keys protect against brute force attacks. Each extra bit in
the key doubles the number of possible keys and therefore doubles the
work a brute force attack must do. A large enough key defeats
any brute force attack.
For example, the EFF's DES Cracker
searches a 56-bit key space in an average of a few days. Let us assume
an attacker that can find a 64-bit key (256 times
harder) by brute force search in a second (a few hundred thousand
times faster). For a 96-bit key, that attacker needs 232
seconds, just over a century. Against a 128-bit key, he needs
232 centuries or about 400,000,000,000 years. Your data
is then obviously secure against brute force attacks. Even if our
estimate of the attacker's speed is off by a factor of a million, it
still takes him 400,000 years to crack a message.
This is why
Also, once you have adequate keylength (somewhere around 90 or
100 bits), adding more key bits make no practical difference,
even against brute force. Consider our 128-bit example above that takes
400 billion years to break by brute force. Do we care if an extra 16 bits
of key put that into the quadrillions? No. What about 16 fewer bits reducing
it to the 112-bit security level of Triple DES, which
our example attacker could break in just over a billion years?
No again, unless we're being really paranoid
about safety margins.
There may be reasons of convenience in the design of the cipher to support
larger keys. For example Blowfish allows up to 448
bits and RC4 up to 2048, but beyond 100-odd bits it
makes no difference to practical security.
See Web of Trust for an alternate model.
This is not required by the IPSEC RFCs and not
currently used in
Linux FreeS/WAN.
An initialisation vector (IV) must be provided.
It is XORed into
the first block before encryption. The IV need not be secret but
should be different for each message and unpredictable.
Four standard modes were defined for DES in
FIPS
81. They can actually be applied with any block cipher.
Various other modes are also possible, but none of them are
used in IPSEC.
Variations
on this technique exist using public key or
symmetric cryptography. Some provide two-way
authentication, assuring each player of the other's identity.
Because the random number is different each time, this defeats simple
eavesdropping and replay attacks. Of course an attacker might still try
to break the cryptographic algorithm used, or the
random number generator.
For current information, see their web site.
DES is seriously insecure against current attacks.
Linux FreeS/WAN does not include DES, even
though the RFCs specify it.
We strongly recommend that single DES not be used.
This is not required by the IPSEC RFCs and not currently
used in Linux FreeS/WAN.
DESX would be the easiest additional transform to add; there would
be very little code to write. It would be much faster than 3DES
and almost certainly more secure than DES. However, since it is not
in the RFCs other IPSEC implementations cannot be expected to have
it.
The protocol is secure against all passive attacks,
but it is not at all resistant to active
man-in-the-middle attacks.
If a third party can impersonate Bob to Alice and vice versa, then
no useful secret can be created. Authentication of the participants is a
prerequisite for safe Diffie-Hellman key exchange.
IPSEC can use any of several authentication
mechanisims. Those supported by FreeS/WAN are discussed in our
configuration document.
The Diffie-Hellman key exchange is based on the discrete logarithm
problem and is secure unless someone finds an efficient solution to that problem.
Given a prime p and generator g (explained under discrete log
below), Alice:
An eavesdropper will know p and g since these are made public,
and can intercept A and B but, short of solving the
discrete log
problem, these do not let him or her discover the secret s.
Such an encrypted message digest can be treated as a signature since it
cannot be created without both the document and
the private key which only you should possess. The
legal issues are complex, but several
countries are moving in the direction of legal recognition for digital
signatures.
The discrete log problem is the basis of several cryptographic systems, including the
Diffie-Hellman key exchange used in the IKE
protocol. The useful property is that exponentiation is relatively easy but the inverse
operation, finding the logarithm, is hard. The cryptosystems are designed so that the
user does only easy operations (exponentiation in the field) but an
attacker must solve the hard problem (discrete log) to crack the system.
There are several variants of
the problem for different types of field. The IKE/Oakley key determination protocol
uses two variants, either over a field modulo a prime or over a field defined by
an elliptic curve. We give an example modulo a prime below. For the
elliptic curve version, consult an advanced text such as
Handbook of Applied Cryptography.
Given a prime p,
a generator g for the field modulo that prime, and a number x
in the field, the problem is to find y such that
For example, let p = 13. The field is then the integers from 0 to 12. Any integer
equals one of these modulo 13. That is, the remainder when any integer is divided
by 13 must be one of these.
2 is a generator for this field. That is, the powers of two modulo 13 run through
all the non-zero numbers in the field. Modulo 13 we have:
The discrete log problem is the reverse. In our example, given
Note, however, that no-one has proven such methods do not exist. If a solution to either variant
were found, the security of any crypto system using that variant would be destroyed. This is the main
reason IKE supports two variants. If one is broken, we switch to the other.
The sequence is:
The "advantage" of this EDE order of operations is that it makes it simple
to interoperate with older devices offering only single DES. Set key1=key2=key3
and you have the worst of both worlds, the overhead of triple DES with
the security of single DES. Since single DES is insecure,
this is a rather dubious "advantage".
The EDE two-key variant can also interoperate with the EDE three-key
variant used in IPSEC; just set k1=k3.
Major variants include symmetric encryption in which
sender and receiver use the same secret key and public key
methods in which the sender uses one of a matched pair of keys and the receiver
uses the other.
Many current systems, including IPSEC, are
hybrids combining the two techniques.
For example, the Internet may route all traffic for a particular company to
that firm's corporate gateway. It then becomes the company's problem to get
packets to various machines on their subnets in various
departments. They may decide to treat a branch office like a subnet, giving
it IP addresses "on" their corporate net. This becomes an extruded subnet.
Packets bound for it are delivered to the corporate gateway, since as far
as the outside world is concerned, that subnet is part of the corporate
network. However, instead of going onto
the corporate LAN (as they would for, say, the accounting department) they
are then encapsulated and sent back onto the Internet for delivery to the
branch office.
For information on doing this with Linux FreeS/WAN, look in our
Configuration file.
"Free software" refers to the users' freedom to run, copy,
distribute, study, change and improve the software.
IDEA is not required by the IPSEC RFCs and not
currently used in Linux FreeS/WAN.
IDEA is patented and, with strictly limited exceptions for personal use,
using it requires a license from Ascom.
The client machines are set up with
reserved non-routable IP addresses defined in RFC 1918. The masquerading
gateway, the machine with the actual link to the Internet, rewrites packet
headers so that all packets going onto the Internet appear to come from one
IP address, that of its Internet interface. It then gets all the replies,
does some table lookups and more header rewriting, and delivers the replies
to the appropriate client machines.
To use masquerade with Linux FreeS/WAN, you must set leftfirewall=yes and/or
rightfirewall=yes in the connection description in /etc/ipsec.conf.
See this
web site
for more details, and our compatibility
document for information on FreeS/WAN and the Linux implementation of IPv6.
This is the standard Linux FreeS/WAN is implementing.
For more details, see our IPSEC Overview.
For the standards, see RFCs listed in our RFCs document.
In the Linux release numbering system, an even second digit as in 2.2.x
indicates a stable or production kernel while an odd number as in 2.3.x
indicates an experimental or development kernel. Most users should run a recent kernel
version from the production series. The development kernels are primarily for people
doing kernel development. Others should consider using development kernels only if they
have an urgent need for some feature not yet available in production kernels.
Today Linux is a complete Unix replacement available for several CPU
architectures -- Intel, DEC/Compaq Alpha, Power PC, both 32-bit SPARC
and the 64-bit UltraSPARC, SrongARM, . . . -- with support for multiple
CPUs on some architectures.
Linux FreeS/WAN is intended to run on all CPUs
supported by Linux and is currently (February 1999) known to work on
Intel, Alpha and StrongARM. See our
compatibility document for details.
See our IPSEC Overview for more detail.
For the code see our
primary distribution site
or one of the mirror sites on
this list.
NOTE: US citizens or residents are asked not to post code to the
list, not even one-line bug fixes. The project cannot accept
code which might entangle it in US export restrictions.
For more detail, see our document on this and other mailing lists.
For example, if Alice and Bob are negotiating a
key via the Diffie-Hellman key agreement, and are not
using authentication to be certain they are talking to each other, then
an attacker able to insert himself in the communication path can deceive
both players.
Call the attacker Mallory. For Bob, he pretends to be Alice. For Alice,
he pretends to be Bob. Two keys are then
negotiated, Alice-to-Mallory and Bob-to-Mallory. Alice and Bob each
think the key they have is Alice-to-Bob.
A message from Alice to Bob then goes to Mallory who decrypts it, reads
it and/or saves a copy, re-encrypts using the Bob-to-Mallory key and
sends it along to Bob. Bob decrypts successfully and sends a reply
which Mallory decrypts, reads, re-encrypts and forwards to Alice.
To make this attack effective, Mallory must
MD5 is one of two message digest algorithms available in IPSEC. The other
is SHA. SHA produces a longer hash and is therefore more
resistant to birthday attacks, but this is not a
concern for IPSEC. The HMAC method used in IPSEC is
secure even if the underlying hash is not particularly strong against
this attack.
Double DES encryption and decryption can be written:
The meet-in-the middle attack re-writes the equations to calculate a
middle value M:
With enough table space, this breaks double DES with 257 work. The
memory requirements of such attacks can be prohibitive, but there
is a whole body of research literature on methods of reducing them.
IP packets, which can be up to 64K bytes each, must be packaged into
lower-level packets of the appropriate size for the underlying network(s)
and re-assembled on the other end. When a packet must pass over multiple
networks, each with its own MTU, and many of the MTUs are unknown to the
sender, this becomes a fairly complex problem. See
path MTU discovery for details.
Often the MTU is a few hundred bytes on serial links and 1500-odd on Ethernet.
There are, however, serial link protocols which use a larger MTU to avoid packet
packet fragmentation at the ethernet/serial boundary, and
newer (especially gigabit) Ethernet networks sometimes support much larger packets
because these are more efficient in some applications.
Almost invariably, the phrase "non-routable address" means one of the
addresses reserved by RFC 1918 for private networks:
If any packets using these addresses do leak out, they do not go far. Most
routers automatically discard all such packets.
Various other addresses -- the 127.0.0.0/8 block reserved for local
use, 0.0.0.0, various broadcast and network addresses -- cannot be routed
over the Internet, but are not normally included in the meaning when the
phrase "non-routable address" is used.
Some
history of NSA
documents were declassified in response to a FOIA (Freedom of Information Act) request.
There are, however, several problems with this "perfect" cipher.
Outrageous marketing claims about the "unbreakable" security of
various products which somewhat resemble one-time pads are common.
They are a sure sign of cryptographic snake oil.
See also the one time pad FAQ.
This is done as follows:
The 2.xx versions of PGP used the RSA public key
algorithm and used IDEA as the symmetric cipher.
These versions are described in RFC 1991 and in
Garfinkel's book.
They are freely available. There is a
US version and an
International version
.
The differences are questions of licensing; the two are fully
compatible.
Since version 5, the products from PGP Inc.
have used Diffie-Hellman
public key methods and IDEA or
CAST-128 symmetric encryption. These
can verify signatures from the 2.xx versions, but cannot exchange
encryted messages with them.
Some 5.x and 6.x products are free for personal use. Information on all
products and downloads of the free ones are available from
PGP Inc.
The free versions are also on the
US and
International
sites listed above.
An IETF working group has issued RFC 2440 for an "Open PGP" standard,
similar to the 5.x versions. PGP Inc. staff were among the authors. A free
Gnu Privacy Guard based on that standard is now available.
Their PGP 6.5 product includes PGPnet, an IPSEC client for Macintosh or for
Windows 95/98/NT.
There are several PKI products on the market. Typically they use a
hierarchy of Certification Authorities (CAs).
Often they use LDAP
access to X.509 directories to implement this.
See Web of Trust for a different sort of infrastructure.
This is required, for example, when users of a corporate PKI need to
communicate with people at client, supplier or government organisations,
any of which may have a different PKI in place. I should be able to talk
to you securely whenever:
One half of each pair, called the public key, is made public. The other
half, called the private key, is kept secret. Messages can then be sent by
anyone who knows the public key to the holder of the private key. Encrypt
with the public key and you know only someone with the matching private
key can decrypt.
Public key techniques can be used to create digital
signatures and to deal with key management issues,
perhaps the hardest part of effective deployment of
symmetric ciphers. The resulting hybrid cryptosystems
use public key methods to manage keys for symmetric ciphers.
Many organisations are currently creating PKIs, public
key infrastructures to make these benefits widely available.
See RFC 1750
for the theory. It will be available locally
if you have downloaded our RFC bundle (which is described here).
Or read it
on the net.
See the manual pages for ipsec_ranbits(8) and random(4) for details of what we use.
There has recently been discussion on several mailing lists of the limitations of
Linux /dev/random and of whether we are using it correctly. Those discussions
are archived on the
/dev/random support page.
Our list of IPSEC and other security-related RFCs is
here, along with information on methods of obtaining
them.
There are also several classes on non-routable
IP addresses.
An SA is defined by three things -- the destination, the protocol
(AH
orESP) and the SPI, security parameters
index.
It is used to index other things such as session keys and intialisation
vectors.
For more detail, see our IPSEC Overview
and/or RFC 2401.
IPSEC can use this plus
Diffie-Hellman key exchange
to bootstrap itself.
This would allow opportunistic encryption. Any pair
of machines which could authenticate each other via DNS could communicate
securely, without either a pre-existing shared secret or a shared
PKI.
Linux FreeS/WAN will support this in a future release.
For automatic keying mode, the
IPSEC RFCs require that the sender generate sequence
numbers for each packet, but leave it optional whether the receiver does
anything with them.
SHA is one of two message digest algorithms available in IPSEC. The other
is MD5. Some people do not trust SHA because it was
developed by the NSA. There is, as far as we know,
no cryptographic evidence that SHA is untrustworthy, but this does not
prevent that view from being strongly held.
For more detail, see our IPSEC
Overview and/or RFC 2401.
We expect IPSEC will eventually use the AES winner,
and we expect to see a winner (or more than one; there is an ongoing
discussion on that point) declared in the summer of 2000.
That said, the secrets used for authentication, stored in
ipsec.secrets(5),
should still be protected as tightly as cryptographic keys.
Subject: Re: linux-ipsec: IPSec Masquerade
Date: Fri, 15 Jan 1999 11:13:22 -0500
From: Michael Richardson
and a piece of mail from project technical lead Henry Spencer:
Oh yes, and a new timing point for Sandy's docs... A P60 -- yes, a 60MHz
Pentium, talk about antiques -- running a host-to-host tunnel to another
machine shows an FTP throughput (that is, end-to-end results with a real
protocol) of slightly over 5Mbit/s either way. (The other machine is much
faster, the network is 100Mbps, and the ether cards are good ones... so
the P60 is pretty definitely the bottleneck.)
From an Internet Draft The ESP Triple DES Transform:
Phil Karn has tuned DES-EDE3-CBC software to achieve 6.22 Mbps with a
133 MHz Pentium. Other DES speed estimates may be found at
[Schneier95, page 279]. Your milage may vary.
Resisting such attacks is part of the motivation for:
Cautions:
Inadequate keylength always indicates a weak cipher but it
is important to note that adequate keylength does not necessarily
indicate a strong cipher. There are many attacks other than brute
force, and adequate keylength only guarantees resistance to
brute force. Any cipher, whatever its key size, will be weak if design or
implementation flaws allow other attacks.
IPSEC uses CBC mode since this is
only marginally slower than ECB and is more secure.
In ECB mode the same plaintext always
encrypts to the same ciphertext, unless the key is changed. In
CBC mode, this does not occur.
ECB Electronic CodeBook
encrypt each block independently
CBC Cipher Block Chaining
XOR previous block ciphertext into new block
plaintext before encrypting new block
CFB Cipher FeedBack
OFB Output FeedBack
We generally use the term in the first sense. Vendors of Windows
IPSEC solutions often use it in the second.
The two example attacks discussed were both quite effective when first
discovered, capable of crashing or disabling many operating systems.
They were also well-publicised, and today far fewer systems are vulnerable
to them.
If the attacker puts bogus source information in the first packet, such
that the second is never delivered, the responder may wait a long time for
the third to come back. If responder has already allocated memory for the
connection data structures, and if many of these bogus packets arrive, the
responder may run out of memory.
Meanwhile Bob:
Now Alice and Bob can both calculate the shared secret
y x
2^0 == 1
2^1 == 2
2^2 == 4
2^3 == 8
2^4 == 3 that is, the remainder from 16/13 is 3
2^5 == 6 from 32/13 is 6
2^6 == 12 and so on
2^7 == 11
2^8 == 9
2^9 == 5
2^10 == 10
2^11 == 7
2^12 == 1
Exponentiation in such a field is not difficult. Given, say,
For the two-key version, key1=key3.
"Free software" is a matter of liberty, not price.
To understand the concept, you should think of "free speech",
not "free beer."
See also GNU, GNU General Public License,
and the FSF site.
The exact techniques used in IPSEC are
defined in RFC 2104. They are referred to as HMAC-MD5-96 and
HMAC-SHA-96 because they output only 96 bits of the hash.
This makes some attacks on the hash functions harder.
If he manages it, however, it is devastating. He not only gets to
read all the messages; he can alter messages, inject his own, forge
anything he likes, . . . In fact, he controls the communication completely.
possible targets: DNS, router, Alice or Bob's machine, mail server, ...
strong authentication defeats the attack entirely; this is why IKE requires authentication
not hard if Alice and Bob are using email; quite difficult in some situations.
C = E(k2,E(k1,P))
P = D(k1,D(k2,C))
Where C is ciphertext, P is plaintext, E is encryption, D is decryption,
k1 is one key, and k2 is the other key.
If we know a P, C pair, we can try and find the keys with a brute force
attack, trying all possible k1, k2 pairs. Since each key is 56 bits,
there are 2112 such pairs and this attack is painfully inefficient.
M = E(k1,P)
M = D(k2,C)
Now we can try some large number of D(k2,C) decryptions with various
values of k2 and store the results in a table. Then start doing E(k1,P)
encryptions, checking each result to see if it is in the table.
These addresses are commonly used on private networks, e.g. behind a Linux
machines doing IP masquerade. Machines within the private
network can address each other with these addresses. All packets going outside
that network, however, have these addresses replaced before they reach the
Internet.
Given those three conditions, it can easily be proved
that the cipher is perfectly secure, in the sense that an attacker
with intercepted message in hand has no better chance of guessing
the message than an attacker who only knows the message length.
No such proof exists for any other cipher.
Since this requires co-operation of many systems, and since the next packet
may travel a different path, this is one of the trickier areas of IP programming.
Bugs that have shown up over the years have included:
Since IPSEC adds a header, it increases packet size and may require
fragmentation even where incoming and outgoing MTU are equal.
then the system has PFS. The attacker needs the short-term keys in order to read
the trafiic and merely having the long-term key does not allow him to infer those.
Of course, it may allow him to conduct another attack (such as
man-in-the-middle) which gives him some short-term keys, but
he does not automatically get them just by acquiring the long-term key.
At time of writing (March 1999), this is not yet widely implemented but
is under quite active development by several groups.