* This document describes version 3 of the protocol, as of 30 May 1997.   *
* Changes against version 1 and 2 are at the end of the text.             *

This is a description of a protocol for ultra lightweight IP
encryption. I'll refer to it further as "CIPE" (Crypto IP
Encapsulation). An implementation as a Linux kernel module is
published via my WWW pages at
<URL:http://www.inka.de/~bigred/devel/cipe.html/>.

The primary goal of this software is to provide a facility for secure
(against eavesdropping, including traffic analsyis, and faked message
injection) subnetwork interconnection across an insecure packet
network such as the Internet.

1. Overview

This protocol was designed to be simple and efficient, and to work
over existing communication facilities, especially by encapsulation in
UDP packets. Compatibility with existing protocols such as the IPSEC
RFCs were not a concern. The first test implementation was done
entirely on the user level, while the now published one consists of a
kernel module and a user level program.

The CIPE model assumes a fixed link between two peers which exchange
datagrams (packetwise, not necessarily reliable). The most common way
of implementing such a thing is sending UDP messages between them.
(Another would be encapsulation in PPP, etc.)

Nothing that can be parameterized is inside the scope of this protocol
and implementation. This is delegated to either prior arrangement or a
yet-to-be-defined application level protocol. Most notably, this
involves exchanging a shared secret key by now, and it involves choice
of encryption algorithm.

The CIPE protocol consists of two parts: Encryption and checksumming
of the data packets and dynamic key exchange.

2. Packet encryption

Each IP datagram is taken as a whole, including headers. It is padded
at the end with zero to seven random octets so that the total length
in octets is congruent three modulo eight. The padded packet is
appended with one octet of the value P described below and the CRC-32
over the packet built up so far, up to and including P. (This makes
the complete packet length a multiple of eight octets.)

This packet is then encrypted through a 64-bit block cipher in CBC
mode with an IV as described below using either the static or the
sending dynamic key of the outbound interface (for definition of keys
see below). The default cipher algorithm is IDEA. The current
implementation also supports Blowfish with 128 bit key.

The encrypted packet is prepended with the IV block. The highest order
bit of the first octet of the IV is zero if the static key is used,
one if the dynamic key is used. The remaining 63 bits are random, but
the first 15 of them should not be all zeros (i.e. an IV/packet that
starts with hex 0000 0000 or 8000 0000 is not allowed). Such packets
are reserved for later protocol extensions.

The CRC is over the polynomial
X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0
and represented in network byte order.

The value P is given as follows: bits 6,5,4 indicate the length of the
padding between the original packet end and P. Bits 2,1 are a type
code, indicating which kind of packet this is. The remaining bits
7,3,0 are reserved and must be zero.

The type codes are:
00 - data
01 - key exchange
10 - reserved
11 - reserved

For decryption, first check the highest bit of the first octet and use
it to select the key. Decrypt the packet, calculate the CRC over the
packet minus the last four octets, compare that with the last four
octets. If valid, strip off the last octet as value P, strip off the
padding as given by bits 6,5,4 of P and process the packet as
indicated by bits 2,1 of P.

3. Key exchange

Every interface is associated with a static key, a sending dynamic key
and a receiving dynamic key. (An interface is an endpoint of a
connection, which may use protocols like UDP for transport but for the
purpose of CIPE are always point-to-point links.) On startup, only the
static key is valid. Encryption uses the static key if and only if the
sending dynamic key is invalid. The value 0 (all bits zero) for the
static key is reserved for future extensions and should not be used.

The dynamic key is set by a dialogue procedure involving messages with
type code bits 01. These are encrypted just like above. The packets
consist of a type octet followed by protocol data followed by a random
amount of padding random data, so that the packet is at least 64 octets
long. A key consists of 16 octets, a key CRC is the CRC-32 over the
key, transferred in network order.

The following messages exist:

NK_REQ: Type code 1, no data: Requests the peer to immediately start a
key negotiation (send NK_IND). This should be sent when a packet is
received encrypted with a dynamic key but no dynamic receive key is
valid. (Which can happen when the receiving side of a connection is
rebooted while the sending side remains running.)

NK_IND: Type code 2, data is new key followed by key CRC. Specifies a
new sending dynamic key for this sender. Requests the peer to
immediately answer with NK_ACK.

NK_ACK: Type code 3, data is CRC of the previously accepted key.
Confirms receipt of NK_IND.

The key negotiation procedure normally runs as follows: The sender
sends a NK_IND with the new key, then invalidates its own sending key.
Upon receipt of NK_IND, the receiver starts using this key as its
receiving key and sends a NK_ACK. When the sender receives NK_ACK, it
starts using the new key as its sending key. If either of NK_IND or
NK_ACK is lost in transmission, no new key will be used. The sender
should send a new NK_IND (with new key) if no matching NK_ACK is
received within a reasonable amount of time (current specification: 10
seconds).

If any of the checksums contained in the key negotiation data
mismatches the contained or stored key, this packet is ignored and no
further action taken.

A sending dynamic key should be invalidated after being used for a
certain period of time or amount of data and a new NK_IND sent. The
process is symmetric and both sides act independently for their own
sending key. The dynamic key lifetime should not exceed 15 minutes and
the amount of data sent using one dynamic key should not exceed 2^32
packets.

4. Security considerations

The packets that actually get transmitted don't carry any usable
information related to the original IP datagram other than its length,
padded to a multiple of 8. This should effectively guard against most
aspects of traffic analysis. The only information visible prior
(attempt) to decrypting the packet is the bit that tells whether the
static or dynamic key was used. Because the static key has a
potentially long lifetime it is expected to be used as rarely as
possible. It is normally used only in the short period of time during
a key exchange. The dynamic key is changed often. These precautions
are there because the application is prone to known and chosen
plaintext attacks and the intention is to inhibit feeding of large
amounts of data through one key.

Because the type code and padding length are encrypted with the
packet, they can not be deduced from the ciphertext. Especially, it is
not possible to determine whether the packet is a data or key exchange
packet. (Usually, the last packet of a sequence of dynamic key packets
followed by a sequence of static key packets is a NK_IND, but the
NK_ACK and a possible second NK_IND can't be guessed this way, so
there is no provision to tell whether the key exchange succeeded.
However, this is a small but real weakness.)

The CRC serves as a check whether the encryption key was valid - i.e.
some sort of signature for authenticity of the packet. Additionally,
data packets should still have to form valid IP headers (with their
own 16-bit checksum) and key exchange packets carry their own checksum
as defined above.

IP packets carry some known or easily guessable plaintext in certain
positions of their header. Potential exploitation of this fact should
be mitigated by the limited key usage described above. The use of a
random IV for each packet means at least that identical
(retransmitted) packets encrypt to different ciphertexts.

The protocol gives only limited protection against replay attacks. A
packet remains valid as long as the key it is encrypted with remains
valid. However, active exploitation is unlikely as the packet carries
no indication of its meaning. (Except for the note about sequences and
NK_IND above. Replay of NK_IND could be dangerous. Possible remedy:
store the last N accepted key CRCs [for large-ish N] and refuse to
accept NK_INDs with the same CRC as an already stored one.)

Denial of service attacks are possible e.g. by sending large amounts
of bogus packets, which should affect performance only. A vulnerability
against disruption of the key generation process exists if the sender
is overrun with bogus packets so that it fails to process the NK_ACK,
effectively being forced to use its static sending key for a prolonged
period of time. A possible way out of this problem is to stop sending
data completely after a long burst of static key sends, sending only
NK_INDs and resuming only after a valid NK_ACK has been processed.
Then this attack would become a simple denial-of-service.

5. Practical test, Conclusion

The mentioned prototype implementations, one on the user level and one
as a kernel module, have been in use for several months now on a live
network, where they provide a transparent connection between
subnetworks through an insecure transit network based on UDP
encapsulation. This does work flawlessly. However, it is too early to
draw final conclusions about the feasibility of this approach.

It is planned to replace the simple secret key based key exchange
process described above by a signed Diffie-Hellman scheme, which would
eliminate the need for secret keys.

Appendix.

Changes against previous versions:

- version 2, 20 Mar 1997:

The packet CRC was 16-bit, P was 16-bit, CRC and P were not included
in the encrypted packet, CRC XOR P was appended to the ciphertext. The
pad length was in bits 10,9,8 of P, the key selection bit was bit 0 of
CRC XOR P.

The key CRC was 16-bit. The previous implementation incorrectly
transmitted that in host order.

The IV was random in all 64 bits.

Some notes about implementation availability changed.

- version 1, 9 Nov 1996:

The encryption was done using CBC mode with all-0s IV starting with
the last block of the packet, no IV transmitted.

The only cipher specified was IDEA.

The dynamic key lifetime was specified more loosely.
