From: peace@BIX.com
Date: Thu, 17 Mar 94 18:46:27 PST
To: pem-dev@tis.com
Subject: New block mode of operation
Message-ID: <9403172142.memo.9558@BIX.com>
MIME-Version: 1.0
Content-Type: text/plain


Fellow cryptorians:

The following is a draft of a paper that describes a mode of
operation that I personally feel is useful for bulk data
encryption for PEM, RIPEM, EDI, PGP and any other secure email
application.  In particular, submode CC1 is proposed for these
applications.  I would welcome any suggestions that would help in
evaluating this method in those venues.

peace at acm.org

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

              Cipher-Chain-Cipher Mode of Operation
           for Improving the Security of Block Ciphers

                       by Thomas C. Jones


1 ABSTRACT

As a way to extend the usefulness of encryption with the DES and
prevent several of the more common attacks on the DES, a new mode
of operation is defined that can be used with any block cipher,
including DES.  This mode of operation performs a cipher
operation both before and after a chaining operation and so could
be called cipher-chain-cipher (CCC) mode of operation.  It is
characterized by never performing any operation with the
plaintext data except immediately after one cipher operation and
immediately prior to another, so that cipher operations separate
the plaintext and ciphertext in both directions.  Thus the common
known-text attack and chosen-text attack are avoided and, for
some implementations, only two DES operations are required per
plaintext block.


2 BACKGROUND

Existing block encryption algorithms, such as the Data Encryption
Standard (FIPS 46) have reached the end of their useful life.  It
was expected when the DES was first issued in 1976 that it would
be used for 5 to 10 years.  It is a tribute the care with which
this algorithm was constructed, that it is only now yielding to
practical cryptanalysis.  In particular, the 56 bit key used with
the DES can be determined by brute force attack using specially
designed hardware operating in parallel.

In practical applications of the DES, there are a wide range of
ways to combine the input plaintext with the DES algorithm to
produce an output ciphertext.  In order to promote
interoperability and good cryptographic practice the NIST issued
"Modes of Operation of the DES" as FIPS 81.  The most popular of
the modes of operation for bulk plaintext data to be encrypted is
Cipher Block Chaining (CBC).

Several candidate algorithms have been offered as a replacement
for the DES, but the large installed base of DES hardware and
industry expertise in applying the DES have worked against the
adoption of any of these candidates.  Experience has shown that
untested cryptographic algorithms are likely to have
unanticipated security weaknesses.  This also works against the
adoption of new algorithms.

When the bankers were looking for a stronger algorithm than the
DES for protection of cryptographic keying material, they chose
to leave the underlying DES algorithm in place, but apply the
algorithm three separate times to the input plaintext to yield a
"super-encrypted" output ciphertext.  This has been considered to
be a special mode of operation known as EDE (for encrypt-decrypt-
encrypt) with 2 independent 56 bit keys.  The reason that three
were chosen, rather than two, relates to a particular
cryptanalytic attack called "meet in the middle" where the
cryptanalyst starts exhaustive first stage encryption of
plaintext simultaneously with exhaustive second stage decryption
of ciphertext and comparing the resulting values.  While the
computer storage required for this attack is impractical today,
the theoretical existence of the attack discourages double DES
modes of operation.

It is well known that the redundancy of common data streams, such
as the English language, results in ciphertext that can be
decrypted to only one plaintext that is realistically English. 
The amount of ciphertext that is needed to have some assurance
that only a single plaintext interpretation is known as the
"unicity distance".  For DES and English the unicity distance is
slightly longer that one 8 byte block.  This means that if the
language was known to be English, only two blocks of ciphertext
would be required to have a high degree of confidence that any
decryption that yielded English text would be the only decryption
that would do so.  Even more to the point, if a computer could
quickly assess the likelihood that a decryption of a single
ciphertext block looked like English, only a single additional
decryption would be required to verify that.  This would make an
attack, that tested every one of the possible keys, likely to
succeed.  The only thing that has prevented such a "brute force"
attack has been the time and effort to perform such an attack. 
That sort of brute force attack is now within the grasp of well-
financed commercial enterprises, not to mention secret
governmental agencies.

Several cryptanalytic attacks have been mounted on the DES to
find some simpler way than brute force to recover the key given
the output ciphertext and some other information.  Most of these
attacks rely on access to a large amount of plaintext and the
corresponding ciphertext, this is called a "known plaintext
attack".  Existing modes of operation do not significantly reduce
the threat of a known plaintext attack.  Several methods are
already known to reduce the threat of this attack, principle
among them is restricting the use of each DES key to a single
document or interchange.  That is the method recommended here.

If the cryptanalyst has access to the cryptographic engine with
the key loaded, then two other attacks are possible.  The "chosen
plaintext attack" relies on the analysis of the underlying
structure of the block algorithm by feeding it special
combinations of bits that test particular functional
characteristics of that structure.  "Differential cryptanalysis"
is an attack that relies on changing single bits in the plaintext
and checking the effect on the ciphertext.  While it seems
unlikely that a user would allow any active DES key to be used in
this way, resistance to these attacks is considered appropriate
in academic circles.

More traditional cryptanalysis relied strictly on redundancy that
could be exploited with access to only the ciphertext itself.  So
far no method of attack on ciphertext has proven to be quicker
than the brute force method mentioned above.  It is up to the
user to employ proven good algorithms in a cryptographically
sound way with secure physical protection of the keying material. 
It is claimed that the cipher-chain-cipher modes of operation
offer a sound way to extend the life of DES for encrypting bulk
data such as that found in electronic mail systems.


3 SUMMARY

The CCC mode of operation provides a way for input plaintext to
be combined with DES block encryption and chaining from one stage
to another to add an apparently random input component to each
stage.  The essentials of the method is its separation of the
input and the output data at each stage by interposing a cipher
operation between them.  This requires a cipher operation on the
output ciphertext before it is combined with the input plaintext,
as well as a cipher operation on the result of the combining
operation.  Thus the cryptanalyst is not aware of either data
stream that is to be combined with the input plaintext, nor of
the output of the combining of the plaintext with the apparently
random data that is combined with the plaintext.

One reason for combining some apparently random value with the
input plaintext is to provide a means for whitening the input
data; that is, for masking any repeating pattern in the input
plaintext so that the output ciphertext would also fail to
contain any repeating pattern.  It might be possible for some
cryptanalyst to obtain some meaning from the existence of the
repeating pattlue to the receiver.  One good
method is to place all the above values into a single packet that
is encrypted with the receiver's public key component.  The
resulting encrypted packet can then be transmi at least as
good a security level as is available from this mode of operation
with the cryptographic algorithms used for bulk data encryption. 
The interchange is thus broken into two parts: the first
involving the selection and secure transmittal of the keying
material which is then used in the second part to encrypt the
bulk data according to the modes of operation described in detail
below.

Once the keying material has been generated, the bulk data is
broken into blocks as required by the block cryptographic
algorithm and processed as specified.  The first step is to
optionally cipher the input plaintext using the first key.  The
second step is to chain together this result with apparently
random data feed from the prior step.  The final step is to
cipher the result of the chaining operation and then to transmit
the cipher block created.  The word cipher is used here to mean
either encryption or decryption, since the exact mode that the
block cryptographic algorithm is used at each stage is not
material to the modes of operation described.


4 DESCRIPTION

Other modes of operation, which may have been established by the
Federal Government for other reasons, have not been able to deter
certain types of cryptanalytic attack.  The weakness found in
these other modes is shown, together with the advantages of this
new mode of operation.


             Plain1            Plain2
               |                 |
               v                 v         
IV ----------->X    +----------->X    +------>
               |    |            |    |
             +----+ |          +----+ |
Key -------->| En |-+--------->| En |-+------>
             +----+ |          +----+ |
               |----+            |----+
               v                 v
            Cipher1           Cipher2

Where:  X       = bit-by-bit exclusive-or operation
        En      = DES 8 byte block encryption
        De      = DES 8 byte block decryption
        Op      = Selection of an input plus encryption
        Plainx  = One of the 8 byte input blocks of plaintext
        Cipherx = One of the 8 byte output blocks of ciphertext
        Key     = 56 bit DES single length key
        IV      = 64 bit Initial Value for chaining operation

This shows the Cipher Block Chaining mode of operation of the
DES.  It is very effective at hiding any pattern in the input
plaintext, but does little to deter a cryptanalyst, since if the
input plaintext, and output ciphertext are known, then the input
and output to the cipher operation are known as well.

The fxample of CCC will show how to defeat this sort of
attack by separating the chaining operation from the feedback of
the ciphertext.


               Plain1          Plain2
                 |               |
IV --------+     |    +----+     |    +----+
           v     |    |    v     |    |    v
         +----+  |    |  +----+  |    |  
Key2 --->| En |--+----+->| En |--+----+->
         +----+  |    |  +----+  |    |  
           |     v    |    |     v    |
           +---> X    |    +---> X    |
           |    |          |    |
                 v    |          v    |
               +----+ |        +----+ |
Key3 --------->| De |-+------->| De |-+------>
               +----+ |        +----+ |
                 |----+          |----+
                 v               v
              Cipher1         Cipher2

The CCC-Encrypt operation consists of DES block encryption of the
ciphertext output from the last stage, an exclusive-or (bit by
bit addition) with the next plaintext input, and a final DES
block decryption to form the next ciphertext output block.  The
initial value (IV) serves as a apparently random input to the
first stage, while the output of each stage serves as a
apparently random input to each stage after the first.  The above
diagram show the first two full stages of encryption.

                   Cipher1        Cipher2
                      |              |
                +-----+----+    +----+----
                v          |    v
              +----+       |  +----+ 
Key2 -------->| En |-------+->| En |------->
              +----+       |  +----+        
IV --------+    |          |    |    
           |    |          |    |
           v    |          v    |
         +----+ |        +----+ |
Key1 --->| En |-+------->| En |-+--------->
         +----+ |        +----+ |
           |    v          |    v
           +--> X          +--> X
                |               |
                v               v
             Plain1           Plain2

The CCC-Decrypt operation consists of DES block encryption of the
ciphertext output from the last stage, a DES block encryption of
the cipher text input to the current stage, and an exclusive-or
with the output of both DES block encryptions.  One attack on
this mode is differential cryptanalysis, since, although the
exact value of input to the final cipher stage is not known, a
cryptanalyst that had access to the cryptographic engine with the
key loaded could process plaintext that differed by only a single
bit which would result in only a single bit change in the input
to the final cipher stage.  The cryptanalysis would then be
performed on the ciphertext output. 


The CCC-encrypt operation can be generalized as shown in the
following diagrams.

       Plain1        Plain2
         |             |
         v             v
       +----+        +----+
Key1 ->| En |------->| En |----->
       +----+        +----+
         |             |
Key2 ----+------+------+------+--->
         |      v      |      v
         v    +----+   v    +----+
IV ----->X -->| Op |-->X -->| Op |->
         |    +----+   |    +----+
         v      ^      v      ^
       +----+   |    +----+   |
Key3 ->| De |---+--->| De |---+--->
       +----+   |    +----+   |
         |------+      |------+
         v             v
       Cipher1       Cipher2

The generalized CCC-encrypt operation consists of an initial DES
encrypt operation on the plain text using the first key, followed
by a chaining operation and then a DES decrypt operation on the
result of the chaining operation using the third key.  Several
operations are possible with the chaining operation which uses
the second key.  In all cases the input to the exclusive-or
operation is the result of a variable operation shown above as Op
and the output from the first cipher operation.  The variable
operation in the middle can have one of two sources, and may use
the second key shown in the diagram. 

       Cipher1       Cipher2
         |             |
         +------+      +-------+
         v      |      v       |
       +----+   |    +----+    |
Key3 ->| En |---+--->| En |----+---->
       +----+   |    +----+    |
         |--+   |      |--+    |
         |  |   v      |  |    v
         v  |  +----+  |  |  +----+
IV ----->X  +->| Op |->X  +->| Op |->
         |     +----+  |     +----+
         |       ^     |       ^
Key2 ----+-------+-----+-------+----->
         v             v
       +----+        +----+
Key1 ->| De |------->| De |--------->
       +----+        +----+
         |             |
         v             v
       Plain1        Plain2

 The generalized CCC-decrypt operation just reverses these
operations, except for the chaining operation, which stays the
same in the encrypt and decrypt operations.

Several submodes are available from this generalized mode of
operation depending on the nature of the operator used between
chaining operations.  Below are listed four submodes that may
have particular interest.

Mode CC0 - This mode does not use Key1, so the first cipher
operation is the identity.  The chaining operation is defined to
be the DES on the feedback from the final cipher operation.  This
is exactly the first example shown above.  Its advantage is that
it uses only two keys and two DES operations per input block. 
The disadvantages are discussed above.

Mode CC1 - This modeof the exclusive-or operation. 
This means that the exclusive-or product is just the accumulation
of all the first stage ciphers with the initialization vector. 
This mode also only uses two independent key values and two DES
operation per input block.  A further advantage is that the
interior chaining operation only uses data that is not available
to the cryptanalyst in either the known-text or the chosen-text
attack.

Mode CC2 - This mode is identical to mode CC1 except that the
chaining operation is the DES performed on the result of the
prior exclusive-or.  This mode requires three DES operation per
input block, but gains by confusion of the diffusion entry added
in between each data cipher operation.

Mode CC3 - This mode is identical to mode CC2 except that the
source of the data for the DES operation prior to chaining is not
the prior chaining operation, but feedback from the output stage
of the final cipher operation.  This too requires three DES
operations per input block.


5 EXAMPLE

It will be assumed that the block ciphers of interest all result
in the same amount of output ciphertext as input plaintext with
the possible addition of a fixed length initial value and a
variable length padding to create some optimal length.  In the
DES this optimal data length is any stream that is an exact
multiple of 8 bytes.  Variants of this method could be used with
other block lengths or with byte oriented modes of operation.

While this new mode of operation is expected to find its greatest
use with bulk encryption using data blocks equal in length to the
block length inherent in the underlying block encryption
algorithm, any length block of data could be utilized with any
block length encryption algorithm.  This section shows how bulk
data can be segmented into 64 byte blocks and encrypted using the
64 byte block DES algorithm.  For added security, the secret
keying material and the DES operations are shown to be contained
inside the security perimeter of a cryptographic module which is
mounted inside of a personal computer using a common operating
system.  It would be equally useful to move some, or all, of the
cryptographic operations to code operating under the personal
computer's operation system.

It is critical to the security of the overall system that the
secret keying material, consisting of the two DES keys and the
initial value (IV), be known only to the originating and
receiving party to the interchange.  One way to do this, and to
prevent the accumulation of information for a cryptanalytic
attack on the secret keying material, is to create a new packet
of keying material for each interchange using some suitably
random generator within the security perimeter and encrypt the
entire packet of keying material using this, or some other
encryption method such as the RSA public key encryption method. 
Using DES as the underlying secret key encryption algorithm may
necessitate other measures when generating the keying material,
such as weak key elimination and key parity generation.

In any case there are two or three DES keys with parity are 64
bits in length.  The initial value is the size of the block which
is also 64 bits.  At least one byte will be used to determine the
exact mode of operation.  Since the first key is optional, the
block of secret data can be constructed as 200 to 264 bits in the
following form:

   +------+----+------+------+----------------+
   | mode | IV | Key3 | Key2 | Key1(optional) |
   +------+----+------+------+----------------+

This data is just a valuable as the plaintext of the message to
be protected, since an attacker is assumed to have access to the
ciphertext, so this data will recover the plaintext.  It should
be noted that it is not any more valuable than the plaintext
since it will be used only once to protect one message or
interchange.  Therefore, if the plaintext data is contained on a
personal computer, the enciphering operation can also be
performed on the same personal computer.

On the other hand, the private components of the public key will
be used to decode essentially all the secured messages that are
received over its life, and so its value is the sum of all such
message.  Thus the private components must be protected to a
commensurate level with this value.  Additional means for
protection should include a security perimeter containing these
components together with the operations that are possible with
them.  The security perimeter must be able to physically show
when an attack on the components was made.  Several devices now
have such a security perimeter including: NIST 140-1
cryptographic modules, smart cards with cryptographic co-
processors and PCMCIA cards.

Once suitable keying material is obtained, the originator of the
message may take appropriate means to reduce the redundancy of
the plaintext by compressing it.  Compression, if successful,
always makes the task of the cryptanalyst more difficult by
reducing the redundancy in the plaintext, and making any trial
decryption more likely to yield a possibly good text plaintext
example.

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

This paper represents ideas that may be subject to patent
applications by the author or by others.  To the author's
knowledge, the mode of operation described in this paper was
invented by the author.  To the extent that any of these ideas do
belong to the author, he grants anybody the right to use his
ideas in code compiled by the user for personal, non-commercial
use.   No warrenty of any sort is implied by this grant.  This 
paper is copyright (c) 1994 by Thomas C. Jones and may
be reproduced only with this notice intact.