United States Patent 5,623,549

Cipher Mechanisms with Fencing
and Balanced Block Mixing

Terry Ritter

For informational purposes only. Taken from the original Application and Amendment files which were sent to the PTO in printed form. At the PTO, the documents were manually transcribed into the printed patent. Here, the files were converted to HTML, partly by hand. For these reasons this version may differ, somewhat, from the printed patent. If there is any question, see an actual printed patent copy from the PTO, and any Certificate of Correction.

The extensive use of inline images, which make the text easier to follow, caused extensive disk swapping in 16MB machines. Consequently, the document is broken into parts A, B, C and D.

Contents

• Title
• References
• Abstract
• Drawings
• Body
  • Background of Invention
    • Field of Invention
    • Description of Related Art
  • Summary of Invention
  • Brief Description of the Drawings
  • Description of the Presently Preferred Exemplary Embodiments
    • Increasing the Block Size of a Block Cipher using Balanced Block Mixing
    • Balanced Block Mixers
    • Creating and Generating Balanced Block Mixers
    • Construction of Orthogonal Latin Squares
    • Notes on Polynomial Arithmetic
    • Notes on Fields
    • Examples of Balanced Block Mixers
    • Fenced Cryptographic Mechanisms
    • 1x Fenced Cipher Mechanisms
    • Substitution Mechanisms
    • 1x Fenced DES
    • Generating Keys for the Substitution Mechanisms
    • 2x Fenced Cipher Mechanisms
    • 2x Fenced DES
    • 4x Fenced Cipher Mechanisms
    • 4x Fenced DES
    • Some Other Fenced Block Cipher Mechanisms
    • Balanced Block Mixers in Combination with Substitution Mechanisms
    • A Multiple Size Cryptographic Mechanism.
• Claims

"Keyed Balanced Size-Preserving Block Mixing Transforms," Ritter (Mar. 12, 1994) at Internet Newsgroup sci.crypt.publication.

Schweier, (1996) "Applied Cryptography" 2nd Ed John Wiley & Sons p. 50.

"Network Security", Section 2.6 Hash Algorithms, Kaufman et al (1995) pp. 53 & 486.

"Parallel FFT Hashing", Schnorr et al. pp. 1-2 delivered at Fast Software Encryption (Dec. 1993) Cambridge, England.

"Black Box Cryptanalysis of Hash Networks Based on Multiplications," Schnorr et al (May 9-12, 1994) presented at Eurocrypt 1994, Perugia, Italy.

The Efficient Generation of Cryptographic Confusion Sequences, Terry Ritter, Cryptologia, 15(2): 81-139, 1991.

Ritter/Biham Electronic Mail Conversations, dated Feb., 1994.

Keyed Balanced Size-Preserving Block Mixing Transforms, by Terry Ritter, dated Mar. 12, 1994.

Fenced DES, by Terry Ritter, dated Apr. 17, 1994.

The context of the Fenced DES Design, by Terry Ritter, dated Jun. 30, 1994.

Ritter, "Strong Block Ciphers from Weak Ones: NxM DES A New Class of DES Operating Modes", Ritter Software Engineering, Posted on Internet Jan. 31, 1994.

Ritter, "Substitution Cipher With Pseudo-Random Shuffling: The Dynamic Substitution Combiner", Cryptologia, Oct. 1990, vol. XIV, No. 4, pp. 289-304.

H. Kull and E. Specker, "Direct Construction of Mutually Orthogonal Latin Squares", Computational Theory and Logic, 1987, pp. 224-236.

Portz, "On the Use of Interconnection Networks in Cryptography", Advances in Cryptology--Eurocrypt 1991, pp. 302-315.

Kam et al., "Structured Design of Substitution-Permutation Encryption Networks", IEEE Transactions On Computers, Oct. 1979, vol. C-28, No. 10, pp. 747-753.

Feistel, "Cryptography and Computer Privacy", Scientific American, May 1973, vol. 228, No. 5, pp. 15-23.

Massey, "Safer K-64: A Byte-Oriented Block-Ciphering Algorithm", Fast Software Encryption, 1994, Ross Anderson ed. Springer-Verlay, pp. 1-17.

Lai et al., "A Proposal for New Block Encryption Standard", Advances in Cryptology--Eyrocrypt '90, 1990 pp. 389-404.

Massey et al., "Non-Expanding, Key-Minimal, Robustly-Perfect, Linear and Bilinear Ciphers", Advances In Cryptology--Eurocrypt '87, pp. 237-247.

Stevens, "The Completely Orthogonalized Latin Square", Annals of Eugenics, 1939, 9:82-93.

"Parallel FFT-Hashing" C.P. Schnorr & S. Vaudenay Fast Software Encryption, Cambridge Security Workshop Cambridge, U.K., Dec. 9-11, 1993, Proceedings Springer-Verlag.

"Black Box Cryptanalysis of Hash Networks Based on Multipermutations" Schnorr & Vaudenay Advances in Cryptology--Eurocrypt '94 Springer-Verlag.

ABSTRACT

An enhanced cryptographic mechanism employs Latin square derived balanced size-preserving block mixers and strong, practical fencing arrays of substitution mechanisms in combination with each other and with block ciphers. Ciphers are expanded into efficient, larger, stronger versions. Block ciphers, in combination with balanced block mixers and/or with substitution mechanisms, produce cryptographic mechanisms with block sizes that are combinations of the sizes of the block ciphers. Ciphers using large data blocks can reduce data expansion to levels normally consistent with small blocks. Different sized enhanced cryptographic mechanisms are used in a multiple-size cryptographic mechanism to minimize wasted block space in a ciphered message. The cryptographic mechanism provides at least three layers of processing. In one embodiment a message passes through a fencing array of substitution mechanisms, balanced block mixers, multiple block ciphers, balanced block mixers, and another fencing array of substitution mechanisms, for encryption and decryption, yet still ciphers at a rate near that of the block ciphers alone.

DRAWINGS

FIGURE 1: A Cryptographic Mechanism.

FIGURE 2: An Implementation of a Cryptographic Mechanism.

FIGURES 3(a) and 3(b): A Communication System Employing a Cryptographic Mechanism; and A Schematic Diagram of that Communication System.

FIGURE 3(c): A Computer System Employing a Cryptographic Mechanism.

FIGURE 4(a): Mixing - Enciphering - Mixing with a Double-Width Block.

FIGURE 4(b): Mixing - Deciphering - Mixing with a Double-Width Block.

FIGURE 5(a): Enciphering - Mixing - Enciphering with a Double-Width Block.

FIGURE 5(b): Deciphering - Mixing - Deciphering with a Double-Width Block.

FIGURE 6: Feistel Ciphering - Mixing - Feistel Ciphering with a Double-Width Block.

FIGURE 7: Mixing - Ciphering - Mixing with a Quad-Width Block.

FIGURE 8: Ciphering - Mixing - Ciphering, with a Quad-Width Block.

FIGURES 9(a) and 9(b): Balanced Block Mixers.

FIGURE 10: 1x Fenced DES; Substitute - Cipher - Substitute Cryptographic Mechanism.

FIGURE 11: A Substitution Mechanism.

FIGURE 12: Substitute - Cipher - Substitute with a 128-bit Block.

FIGURE 13: 2x Fenced DES; Substitute - Mix - Cipher - Mix - Substitute with a Double-Width Block.

FIGURE 14: 4x Fenced DES; Substitute - Mix - Cipher - Mix - Substitute with a Quad-Width Block; Power-of-2 Mixing.

FIGURE 15(a): Substitute - Cipher - Substitute.

FIGURE 15(b): 4x Fenced DES; Substitute - Mix - Cipher - Mix - Substitute with a Quad-Width Block; Power-of-2 Mixing, Reversed Order.

FIGURE 16: Cipher Formed from Small Substitutions: Substitute - Mix - Substitute - Mix - Substitute; Power-of-2 Mixing.

FIGURE 17: Cipher Formed from Small Substitutions; Substitute - Mix - Substitute - Mix - Substitute; FFT-style Mixing.

FIGURE 18: A Multiple Block-Size Cryptographic Mechanism.

BODY

CIPHER MECHANISMS WITH FENCING
AND BALANCED BLOCK MIXING

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to cryptography, and more particularly, to constructing and enhancing cryptographic mechanisms.

2. Description of Related Art

Cryptographic mechanisms are used in many fields to improve the security of stored and transmitted data and signals, to authenticate data and signals and to provide protection and privacy of data and signals. Cryptographic mechanisms are used, for example, in communication systems such as digital telephone systems (for both audio and video communications) and in data processing systems to maintain privacy and secrecy of stored and transmitted data, and to authenticate signals and data.

The transformation of signals or data so that their contents cannot be determined is called encryption. The re- transformation of an encrypted signal or data to get back the original signal or data is called decryption. The combination of encryption and decryption is called cryptography and is carried out by cryptographic mechanisms. For example, FIGURE 1 shows a typical cryptographic mechanism 100. Cryptographic mechanism 100 includes an encryption mechanism component 102 and a decryption mechanism component 104. Data encryption operates via the encryption mechanism 102 on an input signal or data (plaintext) P (via a channel 106) to produce an encrypted output signal or data (ciphertext) C (via a channel 108). Similarly, the ciphertext C is decrypted using the decryption mechanism 104 to produce the plaintext P. Most cryptographic mechanisms 100 use cryptographic keys 110, 112 to select the transformation used in encryption and decryption. A cryptographic mechanism 100 can viewed as a filter, taking a first signal and producing another signal corresponding to the encryption or decryption (as appropriate) of the first signal.

Cryptographic mechanisms can be broadly categorized into two classes, namely stream and block devices. In stream cryptographic mechanisms, the input plaintext is encrypted one unit (e.g., one bit or character) at time. Decryption in these stream devices also takes place one unit at a time. In block cryptographic mechanisms, the plaintext is encrypted (and decrypted) in blocks of units, e.g., 64-bit blocks.

Cryptographic mechanism 100 may be implemented entirely in electronic hardware, entirely in software operating on a computer, or in a hybrid combination of both hardware and software. FIGURE 2 is a schematic diagram of a hybrid implementation of cryptographic mechanism 100 which employs one or more cipher mechanisms 114, one or more CPUs 116, and memory 118. Each of the encryption mechanism 102 and the decryption mechanism 104 may have its own cipher mechanism 114, CPU 116, and memory 118, or some or all of these components may be shared. Cipher mechanism 114 implements a particular cipher and may be on its own chip and include its own computer. Other aspects of the cryptographic mechanism 100 are implemented using the CPU 116 and the memory 118, in combination with the cipher mechanism 114.

Cryptographic mechanisms are used in many systems to perform a number of functions, including, but not limited to, authenticating and verifying data (transmitted or stored), hashing data, and encrypting and decrypting messages, data and signals. As examples, a communications system and a computer system, both employing cryptographic mechanisms for various purposes, are described herein. These systems are described only as examples of systems which employ cryptographic mechanisms and of the uses of cryptographic mechanisms in those systems. These examples are not intended to be a complete enumeration of all possible systems in which a cryptographic mechanism of the type described herein could be used, nor are they intended to be a complete enumeration of the various uses of cryptographic mechanisms in those systems.

Cryptographic mechanisms are used in a typical communication system 120, such as shown in FIGURE 3(a) to ensure, inter alia, the secrecy and privacy of communications within the system. In communication system 120, communication devices 122 communicate messages over channels 124. Communication devices 122 may, for example, be computer systems, telephones, facsimile devices, or the like, alone or in combination. The channels 124 may, for example, be regular telephone wires, fiber optic cables, radio waves, microwaves, or the like, alone or in combination. The messages transmitted over the channels 124 may be voice or data, they may be video signals, pictures, or any other form of transmittable data.

Many data communication systems are open, having some or all of the channels 124 insecure. This is especially the case when one or more of the channels employs radio waves which are detectable and easily monitored without affecting the communication system itself. For example, in the case where the communication system 120 is a telephone network, with some of the devices 122 being cellular telephones, some of the channels 124 being radio channels, and the messages being telephone conversations, i.e., voice messages, between users of telephones, the contents of the messages which are sent over radio channels 124 can be monitored by listening in on the appropriate broadcast frequency.

To overcome problems presented by open, insecure channels in communication systems, it is desirable to make it difficult, if not impossible, for someone to ascertain the content of a monitored message. To this end, it is desirable to transform or encode messages, prior to their transmittal over open channels, into messages whose contents cannot be determined. Clearly it is necessary to be able to transform an encoded, transmitted message back to its original message so that the intended recipient can determine its contents.

Thus, in order to overcome the insecurity of communication messages between communication devices 122 over open channels 124 in communication system 120, it is desirable to encrypt messages prior to their transmittal by a communication device 122 and to decrypt them upon receipt by another communication device 122. In this way, by the time a message can be intercepted, i.e., by the time a message is available on an open channel, its contents cannot be determined without being decrypted. To this end, with reference to FIGURES 3(a) and 3(b), each communication device 122 has a message generator/receiver 126 connected via internal (secure) channel 128 to cryptographic mechanism 100. (Cryptographic mechanism 100 corresponds to the cryptographic mechanism 100 of FIGURE 1.) As noted above, a typical cryptographic mechanism 100 is keyed, that is, it uses a cryptographic key 110 or 112 to control its encryption/decryption functions. Communication between communication devices 122 over open channels 124 takes place via cryptographic mechanisms 100. For example, in a transmit mode, the message generator/receiver 126 of one communication device 122 produces a plaintext message which is sent over internal channel 128 to cryptographic mechanism 120 of that communication device 122. Cryptographic mechanism 100 uses a cryptographic key 110 to control the encryption of the plaintext message, producing a ciphertext message which is transmitted over open channel 124. Anyone intercepting the transmitted ciphertext message would be unable to determine its contents (i.e., the plaintext message) without first decrypting the message. The ciphertext message is sent, via channel 124 to another communication device 122. At the other communication device 122, cryptographic mechanism 100 receives the ciphertext message and decrypts it using the same cryptographic key 112, producing the plaintext message. The plaintext message is then sent over the internal channel 128 of communication mechanism 122 to the message generator/receiver 126.

The internal channel 128 may be a real channel in a device or it may be a logical (i.e., virtual channel). In other words, the cryptographic mechanism 100 may be integrated with the message generator/receiver 126 in such a way that the actual channel 128 is not physically discernable or it may be a separate device connected via an internal data bus of some sort.

Cryptographic mechanisms are used in computer systems such as computer system 130 shown in FIGURE 3(c), having one or more computers 132 connected to each other and to at least one storage device 134 via a bus 136. Storage device 134 may be fixed, e.g., a hard disk, or it may be portable, e.g., a floppy disk, an optical disk, a tape, or the like. Each computer 132 may also have its own local storage device (not shown). In computer system 130, a cryptographic mechanism 100 (FIGURE 1) is used, inter alia, to verify data (stored on a computer 132 or a storage device 134, or transmitted between computers 132), to keep data secret and private, and to prevent unauthorized access to data (stored on a storage device 134 or a computer 132, or transmitted between computers 132).

For example, with reference to FIGURE 3(c), a computer 132 in computer system 130 stores (via bus 136) data in a file 138 on a storage device 134. In order to prevent unauthorized access to the data in the file 138, whether by other users of the computer system 130, or by someone gaining access to the file 138 in some other way, it is desirable to store the data in an encrypted form. Note that access to the data can be gained by obtaining the storage device 134 or by gaining access to the bus 136 while the data is being transferred from the computer 132 to the storage device 134. To this end, the computer 132 includes a cryptographic mechanism 100 (FIGURE 1) for encrypting and decrypting stored data.

As a further example of the use of a cryptographic mechanism, in the communication system 120 of FIGURE 3(a), or computer system 130 of FIGURE 3(c), or the like, it is sometimes desirable to use only one aspect of the cryptographic mechanism 100. In particular, it is sometimes desirable to use only the encryption mechanism (reference numeral 102 of FIGURE 1) to encrypt data in order to authenticate the data. To this end, the cryptographic mechanism 100 can be used to provide an authentification function. Data or signals to be authenticated are encrypted or hashed (controlled by a cryptographic key) by the cryptographic mechanism 100 to produce a value representative of the data. If the data changes then its corresponding encryption value will change, thereby allowing authentification.

In the cryptographic mechanisms described herein, the manner in which keys are provided to the mechanisms is well known and therefore is not described in detail. For example, each communication device 122 or computer 132 may have some means for creating, storing and inputting keys when need, and for providing these keys to their cryptographic mechanisms in a conventional manner.

The above examples (the communications system and the computer system) are only some examples of fields, mechanisms, devices and systems which employ cryptographic mechanisms, and they are not intended to be a complete enumeration of all possible systems in which a cryptographic mechanism of the type described herein could be used.

Cryptographic mechanisms 100 employed in the same system, whether it be a communication system 120, a computer system 130, or the like, must be of the same type in order to be able to function together. This is not to say that the mechanisms must use the same implementations, only that the mechanisms must perform the same encryption and decryption functions. For example, cryptographic mechanism 100 may be implemented entirely in electronic hardware, entirely in software operating on a computer, or in a hybrid combination of hardware and software (as shown above with respect to FIGURE 2). Such differently implemented mechanisms can readily be employed in the same system as long as the mechanisms perform the same or compatible encryption and decryption functions.

Throughout this application, including the claims, the term "mechanism" is intended to include all possible implementations (such as electronic hardware, computer implemented software, hybrids, or the like) or the process performed. Thus a cryptographic or cipher mechanism refers to either a process of enciphering and/or deciphering or any implementation (for example, hardware, computer implemented software, hybrid, or the like) for performing the process. Furthermore, the terms "cipher" and "ciphering" are employed to refer generally to both enciphering and deciphering.

To ensure that various cryptographic mechanisms perform the same encryption and decryption functions, various national and international standards have been set for cryptographic mechanisms and techniques. One example is the Data Encryption Standard (DES). DES is a block cipher that encrypts data in 64-bit blocks. DES takes a 64-bit plaintext and a key, effectively 56 bits long, to produce a 64-bit ciphertext. Decryption in DES takes 64-bit blocks of ciphertext and the same key to reproduce 64-bit blocks of plaintext. The effective DES key length is 56 bits (usually the key is expressed as a 64-bit number, with every eighth bit used for parity checking).

DES has been adopted as an American National Standards Institute (ANSI) standard (ANSI X3.92) and, as part of the standard, the National Institute of Standards and Technology (NIST) validates hardware and firmware implementations of DES. This validation confirms that the implementation follows the standard. The standard does not allow software versions of DES, unless they are unchangeably fixed within a hardware device (for example, by using a read- only memory to hold the hardware control instructions which implement the DES cryptographic mechanism). However, uncertified software versions of DES are common.

The security of DES has been questioned and attempts have been made to increase and improve it. Two aspects of DES relating to its security are the key length and the block size.

Doubling the block size of cipher mechanisms using multiple encryptions has been proposed in order to strengthen them. However, proposed techniques are subject to cryptanalysis.

Attempts have been made to improve DES by using multiple DES operations in sequence (using the same or different keys for each round of DES). Unfortunately, double DES (using DES to again encipher a message already encrypted by DES) has been shown to be barely stronger than DES itself. When a known plaintext-ciphertext pair is available, a search of all possible keys for the input operation, and all keys for the output operation will break the system. It has been shown that if DES has certain mathematical properties (namely if DES is a group) then cryptanalysis of DES (that is, breaking DES) would be easier than if it does not have those properties. Further, if DES has those mathematical properties, then multiple encryption would be useless and would actually weaken DES. To date it has not been shown whether DES has those mathematical properties (i.e., whether DES is a group) but most research points away from it having them. Assuming DES is not a group, the result of triple-DES (passing a message through DES three times, with the same or different keys) may be much harder to break than that of DES or double-DES. However, triple-DES is expensive and complex, and may require three hardware DES implementations and interconnecting hardware, or three software DES executions. In general multiple encryption using the same encryption technique and key does not affect the complexity of a brute-force cryptanalysis. Multiple keys are needed to enhance security.

Many other block ciphers have been developed and some of these may eventually overtake or replace DES in usage. The most likely successor to DES at present is a block cipher called IDEA. IDEA operates on 64-bit plaintext blocks using a 128-bit key (more than twice the effective key length of DES). Current software implementations of IDEA are about as fast as DES. A hardware implementation of IDEA encrypts data at a rate of 177 Mbits/second when clocked at 25MHz. The security of the IDEA cipher is not yet known, and even if it is adopted in some areas, it will be some time before it overtakes DES in use.

In general, the displacement of a commonly-used cipher by a new cipher will not take place until the community of users is satisfied that the new cipher is more secure than the old one. Since ciphers are often implemented by hardware cipher mechanisms, a change in ciphers can be expensive and may require extensive changes to a system employing them. In a large system, with some cryptographic mechanisms implemented in hardware, some in software, and others in hybrid form, changing or updating a cipher is not only costly, but potentially error prone. For example, in the communication system 120 of FIGURES 3(a)-3(b), each of the cryptographic mechanisms 100 in every communication device 122 would have to be replaced. Or in a computer network employing computers 132 as in the computer system 130 of FIGURE 3(c), the cryptographic mechanisms 100 on each computer 132 in the system would have to be replaced. On the other hand, when there are widespread suspicions of weakness of an existing highly used cipher, it would be useful to enhance existing systems which use that cipher.

SUMMARY OF THE INVENTION

This invention provides enhanced cryptographic mechanisms employing combinations of balanced, size-preserving block mixers, arrays of substitution mechanisms, and cipher mechanisms. When cipher mechanisms are used, the enhanced cryptographic mechanisms enhance the cipher mechanisms. The cipher mechanisms can be DES or IDEA mechanisms, or any other block cipher mechanisms, including embodiments of the present invention, and the enhanced cryptographic mechanisms increase the strength of those ciphers.

Cipher mechanisms are enhanced by having their block size increased. This increase is achieved using balanced block mixers or arrays of substitution mechanisms to spread an input to the cryptographic mechanism into multiple cipher mechanisms. Cipher mechanisms are also enhanced by transforming their inputs and outputs using balanced block mixers and arrays of substitution mechanisms.

In another aspect, this invention is a key-balanced, size-preserving block mixer for mixing two input blocks to produce two balanced output blocks, and a method of making a balanced block mixer. A balanced block mixer has two combiners, each of which combines both of the input blocks to the balanced block mixer into one output block of the mixer, such that: (i) every possible input block produces a different output block, and every possible output block is produced by a different input block; (ii) each output block is a function of both input blocks; (iii) any change to any one of the input block values changes both of the output block values; and (iv) stepping either of the input blocks through all possible values while keeping the other of the input blocks fixed steps each of the output blocks through all possible values. The method of making balanced block mixers with these properties uses techniques of constructing orthogonal Latin squares.

In another aspect, this invention is a multiple-size cryptographic mechanism which has a number of cryptographic mechanisms of different sizes and means for selecting among these cryptographic mechanisms in order to process a message. The selecting means decides which cryptographic mechanisms to use so as to minimize wasted block space in the output message.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other objects and advantages of this invention will become more apparent and more readily appreciated from the following detailed description of the presently preferred exemplary embodiments, taken in conjunction with the accompanying drawings, of which:

FIGURE 1 depicts a cryptographic mechanism according to the present invention;

FIGURE 2 is a schematic diagram of an implementation of the cryptographic mechanism of FIGURE 1;

FIGURE 3(a) depicts a communication system employing a cryptographic mechanism according to the present invention;

FIGURE 3(b) is a schematic diagram of a communication device of the communication system of FIGURE 3(a);

FIGURE 3(c) is a computer system employing a cryptographic mechanism according to the present invention;

FIGURE 4(a), FIGURE 4(b), FIGURE 5(a), FIGURE 5(b), FIGURE 6, FIGURE 7, and FIGURE 8 are schematic diagrams of cryptographic mechanisms which employ block mixers according to the present invention, in conjunction with block ciphers;

FIGURES 9(a) and 9(b) are schematic diagrams of balanced block mixers according to the present invention;

FIGURE 10 is a schematic diagram of a cryptographic mechanism employing substitution mechanisms according to the present invention;

FIGURE 11 is a schematic diagram of a substitution mechanism according to the present invention;

FIGURE 12, FIGURE 13, FIGURE 14, FIGURE 15(a), FIGURE 15(b), FIGURE 16, and FIGURE 17 are schematic diagrams of cryptographic mechanisms employing substitution mechanisms according to the present invention; and

FIGURE 18 is a schematic diagram of a multiple block-size cryptographic mechanism according to the present invention.

To Part B: