| Block encryption method and schemes for data confidentiality and integrity protection -> Monitor Keywords |
|
|
  Block encryption method and schemes for data confidentiality and integrity protectionUSPTO Application #: 20060056623Title: Block encryption method and schemes for data confidentiality and integrity protection Abstract: A block encryption method and schemes (modes of operation) that provide both data confidentiality and integrity with a single cryptographic primitive and a single processing pass over the input plaintext string by using a non-cryptographic Manipulation Detection Code function for secure data communication over insecure channels and for secure data storage on insecure media. The present invention allows, in a further aspect, software and hardware implementations, and use in high-performance and low-power applications, and low-power, low-cost hardware devices. The block encryption method and schemes of this invention allow, in yet a further aspect, encryption and decryption in parallel or pipelined manners in addition to sequential operation. In a yet further aspect, the block encryption method and schemes of this invention are suitable for real-time applications. (end of abstract) Agent: Foley And Lardner LLP Suite 500 - Washington, DC, US Inventors: Virgil Dorin Gligor, Pompiliu Donescu USPTO Applicaton #: 20060056623 - Class: 380028000 (USPTO) Related Patent Categories: Cryptography, Particular Algorithmic Function Encoding The Patent Description & Claims data below is from USPTO Patent Application 20060056623. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS-REFERENCE TO RELATED APPLICATION(S) [0001] This application is a Continuation of U.S. Ser. No. 09/761,771, filed on Jan. 18, 2001, which claims priority from U.S. provisional patent application Ser. No. 60/179,147, filed Jan. 31, 2000. The entire contents of each of the aforementioned applications are incorporated herein by reference. FIELD OF THE INVENTION [0002] The present invention relates to the technical field of secure data communication over insecure channels and secure data storage on insecure media using data encryption techniques. Specifically, the invention relates to encryption methods, program products and systems that achieve both data confidentiality and integrity in a single pass over the data with a single cryptographic primitive and allow encryption and decryption in sequential, parallel or pipelined manners. BACKGROUND OF THE INVENTION [0003] It is generally accepted that whenever two or more parties want to communicate over an insecure channel, encryption with a shared secret key can effectively hide all information about the message contents thereby providing data confidentiality (secrecy). However, an insecure channel allows a third party (i.e., an adversary) to modify the other parties' encrypted messages and insert encrypted messages of their own into the insecure channel, not just to read and analyze the other parties' encrypted messages. Furthermore, message encryption cannot provide the ability of each of the two communicating parties to determine that a message received was, in fact, generated by the other party. That is, message encryption, by itself, does not guarantee the integrity (authenticity) of the message data. For example, an adversary can alter the ciphertext of the encrypted message (sections deleted, rearranged, added to, etc.) after it is generated, transmitted via, or stored in, the insecure channel in a way that may cause undetectable message-plaintext alteration at decryption by the recipient (viz., A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone: "Handbook of Applied Cryptography", CRC Press, Boca Raton, 1997). Therefore, it is desirable that encryption methods provide data integrity in addition to data confidentiality for communication over insecure channels. Such methods are also desirable whenever a party stores a set of data on an insecure storage device that can be accessed by other parties which are not intended to read or alter that data (viz., V. D. Gligor and B. G. Lindsay: "Object Migration and Authentication," IEEE Transactions on Software Engineering, SE-5 Vol. 6, November 1979). [0004] Block ciphers have long been established among the cryptographic primitives of choice for implementing general data encryption. A block cipher uses a key to transform data (plaintext) blocks of fixed length into ciphertext blocks of the same length. To encrypt data consisting of multiple blocks, encryption schemes, also known as encryption modes to those skilled in the art, typically use block ciphers. A well-known block cipher is provided by the U.S. Data Encryption Standard (DES), which uses a 56-bit key and has a block size of 64 bits (viz., NBS FIPS Pub 46, titled "Data Encryption Standard," National Bureau of Standards, U.S. Department of Commerce, January 1977). DES can be used with different modes (or schemes) of operation to process multi-block data (viz., NBS FIPS Pub 81, titled "DES Modes of Operation", National Bureau of Standards, U.S. Department of Commerce, December 1980), of which the most used one is the Cipher Block Chaining (CBC) mode. It is well-known in the art that the CBC mode of encryption can use other block cipher algorithms, not just that of DES. [0005] CBC takes as input data a plaintext string x=x.sub.1 . . . x.sub.n, an initialization vector, IV, and a key K. The size of each block x.sub.i and of the IV is l bits and that of key K is k bits (e.g., l=64 and k=56 in DES). The encryption of plaintext x is denoted by ciphertext z=z.sub.1 . . . z.sub.n, and is defined by equation z.sub.i=F.sub.K(x.sub.i.sym.z.sub.i-1), where i=1, . . . , n, z.sub.0=IV, .sym. is the bit-wise exclusive-or operation, and F.sub.K is the block cipher F using key K. Key K is usually chosen uniformly at random. Decryption of ciphertext z=z.sub.1 . . . z.sub.n is performed by F.sup.-1.sub.K, the inverse of the block cipher F using key K, to obtain plaintext x=x.sub.1 . . . x.sub.n, and is defined by equation x.sub.i=F.sup.-1.sub.K (z.sub.i).sym.z.sub.i-1, where i=1, . . . , n, z.sub.0=IV. [0006] Also well-known in the art are other encryption schemes, such as the Plaintext-Ciphertext Block Chaining (PCBC) (viz., C. H. Meyer and S. M. Matyas: "Cryptography; A New Dimension in Computer Data Security", John Wiley & Sons, New York, 1982 (second printing)), stateful or counter-based (XORC), and stateless (XOR$), XOR schemes (viz., M. Bellare, A. Desai, E. Jokipii, and P. Rogaway: "A Concrete Security Treatment of Symmetric Encryption," Proceedings of the 38th Symposium on Foundations of Computer Science, IEEE, 1997, pp. 394-403), and the "infinite garble extension" (viz., C. M. Campbell: "Design and Specification of Cryptographic Capabilities," in Computer Security and the Data Encryption Standard, (D. K. Brandstad (ed.)) National Bureau of Standards Special Publications 500-27, U.S. Department of Commerce, February 1978, pp. 54-66). The encryption and decryption equations of these schemes illustrate in a brief manner how these schemes use F.sub.K, a block cipher F with key K, and its inverse F.sup.-1.sub.K, to process the plaintext and ciphertext blocks of a message or data. For example, in the PCBC scheme, encryption of plaintext string x=x.sub.1 . . . x.sub.n to obtain ciphertext string z=z.sub.1 . . . z.sub.n is defined by the following equation: z.sub.i=F.sub.K(x.sub.i.sym.z.sub.i-1.sym.x.sub.i-1), x.sub.0=IV.sub.1, z.sub.0=IV.sub.2, i=1, . . . , n, where F.sub.K is the block cipher F using secret key K. In this scheme, decryption of ciphertext string z=z.sub.1 . . . z.sub.n to obtain plaintext string x=x.sub.1 . . . x.sub.n, is defined by the following equation: x.sub.i=F.sup.-1.sub.K(z.sub.i).sym.z.sub.i-1.sym.x.sub.i-1, x.sub.0=IV.sub.1, z.sub.0=IV.sub.2, i=1, . . . , n where and F.sup.-1.sub.K is the inverse of the block cipher F using secret key K. [0007] In the "infinite garble extension" scheme, encryption of plaintext string x=x.sub.1 . . . x.sub.n to obtain ciphertext string z=z.sub.1 . . . z.sub.n, is defined by the following equation: z.sub.i=F.sub.K(x.sub.i.sym.z.sub.i-1).sym.x.sub.i-1, x.sub.0=IV.sub.1, z.sub.0=IV.sub.2, i=1, . . . , n, where F.sub.K is the block cipher F using key K. In this scheme, decryption of ciphertext string z=z.sub.1 . . . z.sub.n to obtain plaintext string x=x.sub.1 . . . x.sub.n, is defined by the following equation: x=F.sup.-1.sub.K(z.sub.i.sym.x.sub.i-1).sym.z.sub.i-1, x.sub.0=IV.sub.1, .sub.0=IV.sub.2, i=1, . . . , n, where F.sup.-1.sub.K is the inverse of block cipher F using secret key K. [0008] The encryption and decryption equations of the stateful XOR (XORC) scheme use a counter, ctr, which is initialized to constant value c. Encryption of plaintext string x=x.sub.1 . . . x.sub.n to obtain ciphertext string z=z.sub.1 . . . . z.sub.n with the XORC scheme is defined by the following equation: z.sub.i=F.sub.K(ctr+i).sym.x.sub.i, i=1, . . . , n, where new counter value ctr+n is obtained after each message x encryption, n is the number of blocks of message x, and F.sub.K is the block cipher F using key K. In this scheme, decryption of ciphertext string z=z.sub.1 . . . z.sub.n to obtain plaintext string x=x.sub.1 . . . x.sub.n, is defined by the following equation: x.sub.i=F.sub.K(ctr+i).sym.z.sub.i, i=1, . . ., n. [0009] In contrast with the CBC, PCBC, and "infinite garble extension" schemes, in both the stateful XOR (XORC) scheme and stateless XOR (XOR$) scheme, blocks x.sub.i of plaintext x and blocks z.sub.i of ciphertext z are not processed by F.sub.K and F.sup.-1.sub.K. Nevertheless in these schemes, just as in all others, the message or data decryption operation is the inverse of the message or data encryption operation. [0010] It is well-known in the art that only certain encryption schemes are secure with respect to confidentiality (secrecy) when chosen-plaintext attacks are launched by an adversary using a well-defined set of resources (viz., M. Bellare, A. Desai, E. Jokipii, and P. Rogaway: "A Concrete Security Treatment of Symmetric Encryption," Proceedings of the 38th Symposium on Foundations of Computer Science, IEEE, 1997, pp. 394-403). In such attacks, an adversary can obtain ciphertexts for a set of plaintexts of his/her own choice. Security with respect to confidentiality (secrecy) means that, after such an attack, the adversary cannot determine the plaintext of a never-seen-before ciphertext message (i.e., a ciphertext message not obtained during the attack) with more than negligible probability. The notion of negligible probability in such attacks is also known to those skilled in the art (e.g., as defined by M. Naor and O. Reingold: "From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs," in Advances in Cryptology--CRYPTO '98 (LNCS 1462), pp. 267-282, 1998). All schemes that are secure in this sense are called "confidentiality-secure against chosen-plaintext attacks," or simply, "confidentiality-secure," henceforth. [0011] Variants of the CBC and XOR schemes are proved to be confidentiality-secure against chosen-plaintext attacks. For example, M. Bellare, A. Desai, E. Jokipii, and P. Rogaway, in "A Concrete Security Treatment of Symmetric Encryption," Proceedings of the 38th Symposium on Foundations of Computer Science, IEEE, 1997, pp. 394-403, demonstrate that the CBC and XOR schemes are secure in the left-or-right (or real-or-random) sense, which in turn implies that they are confidentiality-secure against chosen-plaintext attacks (viz., S. Goldwasser and M. Bellare: "Lecture Notes on Cryptography", 1999, available at http://www-cse.ucsd.edu/users/mihir/papers/gb.pdf). Similarly, those skilled in the art can easily show that other schemes, such as PCBC and "infinite garble extension" schemes, are also confidentiality-secure against chosen-plaintext attacks. However, not all schemes for the encryption of multi-block data or messages are confidentiality-secure against chosen-plaintext attacks. For example, it is well known in the art that the Electronic Codebook (ECB) mode of encryption (viz., NBS FIPS Pub 81, titled "DES Modes of Operation", National Bureau of Standards, U.S. Department of Commerce, December 1980) is not confidentiality-secure against chosen-plaintext attacks (viz., S. Goldwasser and M. Bellare: "Lecture Notes on Cryptography", 1999, available at http://www-cse.ucsd.edu/users/mihir/papers/gb.pdf). [0012] It is also well known to those skilled in the art that encryption schemes which are confidentiality-secure against chosen-plaintext attacks do not, by themselves, preserve message integrity (authenticity). All encryption schemes known in the art to date typically use additional methods to provide for the integrity of encrypted multi-block data and messages. Several such methods have been surveyed by A. J. Menezes, P. van Oorschot, and S. Vanstone, in their book entitled "Handbook of Applied Cryptography," CRC Press, 1997. One of the known methods uses an additional cryptographic primitive besides the block cipher, namely a hash function, to provide integrity for encrypted messages. This method requires that the value obtained by applying the hash function to a plaintext be concatenated with the plaintext before encryption. Upon receipt of an encrypted message, the message is decrypted and accepted only after the integrity check is passed; i.e., the check passes if the value of the hash function when applied to the decrypted plaintext matches the hash value decrypted along with, and separated from, the decrypted plaintext. Encryption schemes that use two cryptographic primitives (e.g., block ciphers and hash functions) to provide both message confidentiality and integrity are embodied in commercial systems such as Kerberos V5 as described in RFC 1510, "The Kerberos network authentication service (V5)," Internet Request for Comments 1510, J. Kohl and B. C. Neuman, September 1993. Other known schemes for obtaining the integrity of encrypted multi-block data and messages can use only a single cryptographic primitive (i.e., a block cipher) but require two passes over the data or message; i.e., one pass for encryption with one secret key, and an additional pass for computing a Message Authentication Code (MAC) for the plaintext data or message with a separate secret key; or an additional pass for computing the MAC for the encrypted data or message with a separate secret key. Both the encrypted data or message and the corresponding MAC represent the output of these encryption schemes. [0013] Encryption schemes that require two sequential passes over the data or message and use only one cryptographic primitive, and those that use two cryptographic primitives sequentially, to provide integrity of encrypted messages or data (1) decrease the performance of message and data encryption considerably, and (2) cannot be applied to real-time applications where commencing verification of message integrity cannot be deferred until the end of message decryption (viz., E. Petrank and C. Rackoff: "CBC MAC for Real-Time Data Sources," manuscript available at http://www.cs.technion.ac.il/.about.erez/publications.html, 1999). Furthermore, schemes using one cryptographic primitive and two processing passes concurrently, and those using the two cryptographic primitives concurrently, can achieve high-performance for confidentiality and integrity but require substantial implementation complexity, cost, and additional power, and are less suitable for implementation in low-power applications, and low-power, low-cost hardware devices. [0014] Past attempts to overcome these shortcomings in message or data integrity protection with traditional encryption schemes (e.g., CBC, PCBC) relied on non-cryptographic Manipulation Detection Codes (MDCs), particularly on checksums, such as 32-bit Cyclic Redundancy Codes (CRC-32) (viz., RFC 1510, "The Kerberos network authentication service (V5)", Internet Request for Comments 1510, J. Kohl and B. C. Neuman, September 1993; R. R. Juneman, S. M. Mathias, and C. H. Meyer: "Message Authentication with Manipulation Detection Codes," Proc. of the IEEE Symp. on Security and Privacy, Oakland, Calif., April 1983, pp. 33-54). However, all past attempts to protect the integrity of encrypted messages with non-cryptographic MDC functions failed. The reason for this is that non-cryptographic MDC functions cannot be used with traditional encryption schemes to detect integrity violations (e.g., forgeries) caused by chosen-plaintext attacks followed by verification of forged ciphertext messages by the adversary. These attacks are called the chosen-message attacks herein. In a successful chosen-message attack, an adversary is able to forge ciphertext messages that would be decrypted correctly with non-negligible probability by an unsuspecting party. The adversary need not know, nor be able to predict, the plaintext produced by correct decryption of the forged ciphertext. An example of such a successful attack against CBC encryption when CBC is used with the CRC-32--one of the strongest non-cryptographic MDC in use--in which the adversary can predict the plaintext of a forgery is provided by S. G. Stubblebine and V. D. Gligor in "On message integrity in cryptographic protocols," Proceedings of the 1992 IEEE Computer Society Symposium on Research in Security and Privacy, pp. 85-104, 1992. Other block encryption schemes that are susceptible to chosen-message attacks when using the typical non-cryptographic MDCs include the PCBC scheme (viz., J. T. Kohl: "The use of encryption in Kerberos for network authentication", Advances in Cryptology-CRYPTO '89 (LNCS 435), pp. 35-43, 1990; and A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone: "Handbook of Applied Cryptography", CRC Press, Boca Raton, 1997), the "infinite garble extension" scheme, and the XOR schemes. [0015] Furthermore, encryption schemes that use non-cryptographic MDC functions have not generally offered the possibility of processing encryption and decryption operations in a parallel or pipelined fashion, which has limited their applicability to sequential processing. SUMMARY OF THE INVENTION [0016] The inventors have recognized, and it is an aspect of this invention, that it is highly advantageous to provide encryption schemes that several or all of the following aspects (1) require only one processing pass over the data or message with only one cryptographic primitive (i.e., the block cipher), (2) withstand chosen-message attacks, (3) can be used for high-performance and low-power applications, and low-power, low-cost hardware devices, (4) are suitable for real-time applications, and (5) can be used in parallel or pipelined fashion in addition to that of the standard sequential processing. [0017] It has been recognized by the present inventors that prior-art block encryption schemes do not achieve both confidentiality and integrity in one single processing pass over the input data using a single cryptographic primitive. In the prior art, block encryption schemes that require two passes over the data (e.g., one for encryption and one for computing a MAC) and a single cryptographic primitive, or two cryptographic primitives (e.g., block cipher and hash function), to provide both confidentiality and integrity, result in decreased performance or demand additional power when compared to schemes using a single cryptographic primitive (i.e., the block cipher) in one pass over the data. Hence, prior-art block-encryption schemes are less suitable for use in high-performance, low-power applications, and low-power, low-cost hardware devices. Furthermore, these prior-art block encryption schemes cannot be used in most real-time applications for embedded systems where commencing integrity verification cannot be deferred until the completion of message decryption. [0018] It has also been recognized by the present inventors that, despite their inadequacy in detecting integrity violations caused by chosen-message attacks when used with traditional encryption schemes (e.g., CBC, PCBC, "infinite garble extension," XOR), it is advantageous to develop new encryption schemes that use non-cryptographic Manipulation Detection Code functions to protect both data confidentiality and integrity because these functions add only a small overhead to the encryption and decryption operations. Among these non-cryptographic MDC functions, those that can be computed in a parallel or pipelined manner have been of particular interest, and henceforth we refer to them as the (non-cryptographic) high-performance Manipulation Detection Code (hpMDC) functions. [0019] There remains a need for secure block encryption methods that provide data confidentiality and integrity with a single cryptographic primitive in a single processing pass over the data by using a non-cryptographic (high performance) Manipulation Detection Code function. There is a need for such block encryption methods that are applicable to real-time applications. There is a further need for such block encryption methods that are suitable for both software or hardware implementation, for high-performance, low-power applications. There is a yet further need for such block encryption methods that are suitable for low-power, low-cost hardware devices. There is a yet further need for such block encryption methods that allow encryption and decryption in sequential, parallel or pipelined manners. [0020] Briefly, the present invention comprises, in a first embodiment, an encryption method for providing both data confidentiality and integrity for a message, comprising the steps of: receiving an input plaintext string comprising a message and padding it as necessary such that its length is a multiple of l bits; partitioning the input plaintext string a length that is a multiple of l bits into a plurality of equal-size blocks of l bits in length; creating an MDC block of l bits in length that includes the result of applying a non-cryptographic Manipulation Detection Code (MDC) function to the plurality of the equal-size blocks; making one and only one processing pass with a single cryptographic primitive over each of the equal-size blocks and the MDC block to create a plurality of hidden ciphertext blocks each of l bits in length; and performing a randomization function over the plurality of hidden ciphertext blocks to create a plurality of output ciphertext blocks each of l bits in length. Continue reading... Full patent description for Block encryption method and schemes for data confidentiality and integrity protection Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Block encryption method and schemes for data confidentiality and integrity protection patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Block encryption method and schemes for data confidentiality and integrity protection or other areas of interest. ### Previous Patent Application: Enabling user control over automated provisioning environment Next Patent Application: Method for universal calculation applied to points of an elliptic curve Industry Class: Cryptography ### FreshPatents.com Support Thank you for viewing the Block encryption method and schemes for data confidentiality and integrity protection patent info. IP-related news and info Results in 0.83194 seconds Other interesting Feshpatents.com categories: Electronics: Semiconductor , Audio , Illumination , Connectors , Crypto , |
||
