Method and system for enhancing cryptography-based security

As part of a cryptographic protocol, or in addition to it, a computer may participate in a cryptographic key generation protocol. The cryptographic key generation protocol may be such that it generates a set of bits sufficient for a cryptographic key and, also, one or more additional bits. The cryptographic protocol may have one or more parameters, and the parameters of the cryptographic protocol may be varied as a function of the additional bits generated by the cryptographic key generation protocol. The cryptographic protocol may specify a set of one or more cryptographic key sizes. An overkey may be generated that is at least one bit greater than the set of cryptographic key sizes specified by the cryptographic protocol. The parameters of the cryptographic protocol may then be varied as a function of some subset of bits of the overkey. Cryptography-based security may thus be enhanced.

FIELD OF THE INVENTION

This invention pertains generally to computer system security and, more particularly, to computer system security that has its basis in cryptography.

BACKGROUND OF THE INVENTION

Computers connected by networks have become a common means of communication. Modern computer networks may have many millions of nodes and, as a result, much of the virtue and, in particular, vice of any larger community. At times, there is a need for secure communication between computers. This is true even of smaller computer networks. Such secure communication may include private communication as well as authenticated communication. Of the methods for achieving secure communication, methods based on cryptography are among the most reliable and popular.

Cryptographic protocols securing communication typically have one or more parameters, some of which may not be explicit. For example, a specification of a cryptographic protocol may specify some parameters as required and others as optional. In addition, the cryptographic protocol may have parameters that are not explicitly set forth in the specification. Although protocol designers may make efforts to minimize such parameters.

An adversary desiring to compromise a particular cryptographic protocol may attempt to characterize one or more of the parameters of the cryptographic protocol. At least one parameter of the cryptographic protocol is typically designed to be resistant to such characterization. A cryptographic protocol with multiple characterization-resistant parameters may be more secure.

A problem is that, over time, protocol parameters may become less resistant to characterization, for example, because of technical advances. Another problem is that protocol parameters may not be as resistant to characterization as commonly believed. The cryptographic protocol may even have parameters, perhaps not known to the protocol designers, that are relatively easy to characterize. Characterization of one parameter, even if it does not lead to direct security compromise, may lead to characterization of some other, perhaps more significant parameter. Parameter regularities, in particular, may be a problem.

BRIEF SUMMARY OF THE INVENTION

In an embodiment of the invention, a computer facilitates secure communications by participating in a cryptographic protocol. As part of the cryptographic protocol, or in addition to it, the computer may participate in a cryptographic key generation protocol. The cryptographic key generation protocol may be such that it generates a set of bits sufficient for a cryptographic key and, also, in most instances one or more additional bits. The number of additional bits may vary from one generative instance to another. The cryptographic protocol may have one or more parameters, and the parameters of the cryptographic protocol may be varied as a function of the additional bits generated by the cryptographic key generation protocol. Cryptography-based security may thus be enhanced.

The cryptographic protocol may specify a set of one or more cryptographic key sizes. For example, these may be cryptographic key sizes suitable for use by the cryptographic protocol to encrypt data. In an embodiment of the invention, an overkey is generated that is at least one bit greater than the set of cryptographic key sizes specified by the cryptographic protocol. The parameters of the cryptographic protocol may then be varied as a function of some subset of bits of the overkey. In an embodiment of the invention, a secure communications module is configured to participate in the cryptographic protocol. In addition, an overkey module may be configured to generate the overkey and vary the parameters of the cryptographic protocol.

DETAILED DESCRIPTION OF THE INVENTION

Prior to proceeding with a description of the various embodiments of the invention, a description of a computer in which the various embodiments of the invention may be practiced is now provided. Although not required, the invention will be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, programs include routines, objects, components, data structures and the like that perform particular tasks or implement particular abstract data types. The term “program” as used herein may connote a single program module or multiple program modules acting in concert. The terms “computer” and “computing device” as used herein include any device that electronically executes one or more programs, such as personal computers (PCs), hand-held devices, multi-processor systems, microprocessor-based programmable consumer electronics, network PCs, minicomputers, tablet PCs, laptop computers, consumer appliances having a microprocessor or microcontroller, routers, gateways, hubs and the like. The invention may also be employed in distributed computing environments, where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, programs may be located in both local and remote memory storage devices.

Referring toFIG. 1, an example of a basic configuration for the computer102on which aspects of the invention described herein may be implemented is shown. In its most basic configuration, the computer102typically includes at least one processing unit104and memory106. The processing unit104executes instructions to carry out tasks in accordance with various embodiments of the invention. In carrying out such tasks, the processing unit104may transmit electronic signals to other parts of the computer102and to devices outside of the computer102to cause some result. Depending on the exact configuration and type of the computer102, the memory106may be volatile (such as RAM), non-volatile (such as ROM or flash memory) or some combination of the two. This most basic configuration is illustrated inFIG. 1by dashed line108.

The computer102may also have additional features/functionality. For example, computer102may also include additional storage (removable110and/or non-removable112) including, but not limited to, magnetic or optical disks or tape. Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information, including computer-executable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory, CD-ROM, digital versatile disk (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to stored the desired information and which can be accessed by the computer102. Any such computer storage media may be part of computer102.

The computer102preferably also contains communications connections114that allow the device to communicate with other devices such as remote computer(s)116. A communication connection is an example of a communication medium. Communication media typically embody computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. By way of example, and not limitation, the term “communication media” includes wireless media such as acoustic, RF, infrared and other wireless media. The term “computer-readable medium” as used herein includes both computer storage media and communication media.

The computer102may also have input devices118such as a keyboard/keypad, mouse, pen, voice input device, touch input device, etc. Output devices120such as a display, speakers, a printer, etc. may also be included. All these devices are well known in the art and need not be described at length here.

In an embodiment of the invention, the security of a cryptographic protocol is enhanced by varying one or more parameters of the cryptographic protocol. The cryptographic protocol may be carried out between computers (such as the computer102), computer components and/or computer systems.FIG. 2illustrates an example computing environment200suitable for incorporating aspects of the invention.

A first computer202communicates with a second computer204over a network206. The communication between the first computer202and the second computer204may be secure or insecure or a combination of secure and insecure. The secure part(s) of the communication may be established and/or performed with the cryptographic protocol. In this example, a third computer208is a malicious node of the computing environment200attempting to compromise some or all of the secure communication between the first computer202and the second computer204.

For clarity in what follows, embodiments of the invention will be described in the context of the example scenario illustrated byFIG. 2, however, embodiments of the invention are not so limited. In particular, cryptographic protocols may be carried out between components of a single computer such as the computer102(FIG. 1). For further clarity, the following examples will be directed to privacy aspects of security; however, as will be appreciated by those of skill in the art, the associated techniques may be applied to other aspects of security such as authentication and integrity.

Communication security may be facilitated with encryption. For example, a particular cryptographic protocol may specify that a message be encrypted by the computer202before being sent to the computer204. Then, if the message is intercepted and/or copied by the computer208, it will be unreadable unless, for example, the computer208is able to decrypt the message.

FIG. 3depicts an example architecture capable of implementing cryptographic protocols in accordance with an embodiment of the invention. Computers302and304may communicate according to a cryptographic protocol. For example, the computer302may take the part of the computer202(FIG. 2) and the computer304may take the part of the computer204or the computer208.

Each computer302,304may have a communications module306,308that is incorporated into and/or maintains one or more communication connections114(FIG. 1). An application310(e.g., a set of executable instructions in system memory106) at the computer302may communicate with an application312at the computer304by internally passing/sending a message314to the communications module306. The communications module306of the computer302may then send a message316to the communications module308of the computer304. The communications module308may then internally pass/send a message318to the application312. For example, communication between the applications310,312may be in accordance with the International Standards Organization (ISO) Open Systems Interconnection (OSI) series of standards (ISO 7498).

Each communications module306,308may include a secure communications module320,322. Although, in this example, each secure communications module320,322is incorporated into a respective communications module306,308, each embodiment of the invention is not so limited. If the applications310,312request secure communication (e.g., by so indicating as part of the messages314and/or318), the communications modules306,308may invoke the secure communications modules320,322. For example, the secure communications module320at the computer302may encrypt the message314and pass/send it in an encrypted message324to the secure communications module322at the computer304. The secure communications module322may decrypt the encrypted message324to recover the message314to be passed/sent to the application312as the message318.

In this example, each secure communications module320,322is configured with a cryptographic key326,328. The cryptographic keys324,326may operate in corresponding pairs. Messages such as the encrypted message324encrypted with the key326may be easily decrypted (e.g., with relatively low computational effort) with the corresponding key328. Decryption without the corresponding key328may be difficult (e.g., require excessive computational effort) or even impossible for practical purposes within a given period of time. Although in this example, the keys326,328are identical (i.e., symmetric), each embodiment of the invention is not so limited (e.g., the keys326,328may be corresponding ones of asymmetric pairs).

Configuring the secure communications modules320,322with corresponding cryptographic keys326,328(i.e., key distribution) in a way that avoids compromise may be challenging, particularly for cryptographic protocols employing symmetric keys. For example, simply copying the key326at computer302and then sending it in the unencrypted message316to the computer304means that the key may be intercepted by a third party such as the computer208. The third party may then decrypt each encrypted message324in a manner similar to the intended recipient, computer304, thus compromising the security of the transmission.

Any suitable cryptographic key generation and distribution scheme may be incorporated into an embodiment of the invention. However, in an embodiment of the invention, it is overkeys that are generated and distributed, for example, with a cryptographic key generation protocol, and then live keys may be derived from the overkeys. Overkeys and suitable cryptographic key generation protocols are described below in more detail with reference toFIGS. 4,5and6.

Each secure communications module320,322may include an overkey module330,332. Overkey modules330,332may generate and/or distribute overkeys. Overkey modules330,332may derive live keys326,328from overkeys and otherwise configure parameters of cryptographic protocols performed by secure communications modules320,322. Although, in this example, each overkey module330,332is incorporated into a respective secure communications module320,322, each embodiment of the invention is not so limited. As will be appreciated by one of skill in the art, the computers302,304, the communications modules306,308, the secure communications modules320,322and the overkey modules330,332need not be identical pairs of the respective modules, but may instead be, for example, compatible versions of the respective modules.

Standard cryptographic protocols, such as the Transport Layer Security (TLS) protocol described by Dierks et al. “The TLS Protocol,” RFC 2246, January 1999, may incorporate encryption algorithms, such as the Advanced Encryption Standard (AES) described by Federal Information Processing Standards Publication 197 (FIPS PUB 197) “Specification for the Advanced Encryption Standard (AES)”, published by the National Institute of Standards and Technology (NIST) during November 2001, that utilize cryptographic keys with standard sizes. Examples of standard key sizes include 40 bits, 56 bits, 128 bits, 192 bits and 256 bits. Standard key sizes may include any suitable key size specified by a particular cryptographic protocol.

In an embodiment of the invention, an overkey is generated that is larger than one or more standard key sizes employed by the cryptographic protocol, for example, the cryptographic protocol performed by the secure communications modules320and322.FIG. 4depicts an example overkey402in accordance with an embodiment of the invention. The overkey402includes bits404over and above bits406sufficient to provide for the standard key size(s).

In an embodiment of the invention, a key subset of bits is extracted from the overkey402to serve as the live key326,328(FIG. 3) employed by the cryptographic protocol. The size of the key subset may be one of the standard key sizes. The key subset of bits may be the initial bits406of the overkey402. However, each embodiment of the invention is not so limited. The key subset of bits may be any suitable subset of the overkey402. The bits in the key subset need not correspond to contiguous bits of the overkey402. An order of the bits in the key subset need not be the same as an order of the bits in the overkey402.

In an embodiment of the invention, the additional one or more bits404of the overkey402are a result of an overkey402generation process. The overkey402generation process may generate the overkey402in parcels of one or more bits. For example,FIG. 5shows a 64 bit overkey502generated in four parcels504,506,508and510with sizes of 8 bits, 16 bits, 8 bits and 32 bits respectively. For example, the overkey502is suitable for providing standard keys with sizes that include 40 bits and/or 56 bits.

In an embodiment of the invention, the size of each parcel is a power of 2; however, each embodiment of the invention is not so limited. The overkey502need not be assembled from the parcels504,506,508,510in the order that the parcels504,506,508,510are generated. The parcels504,506,508,510may be assembled to form the overkey502in any suitable order. The bits in each parcel504,506,508,510may be generated by a pseudo-random number generator (PRNG) designed to ensure cryptographic quality (e.g., statistical and/or spectral randomness) of the bits, independent of parcel size.

The parcels504,506,508,510may be generated by a cryptographic protocol having one or more rounds, for example, by the cryptographic protocol performed by secure communications modules320,322(FIG. 3).FIG. 6schematically illustrates an example cryptographic protocol602generating four parcels604,606,608,610in four rounds612,614,616,618. The parcels604,606,608,610may be combined to form an overkey620. Sizes of the parcels604,606,608,610may correspond to the sizes of the parcels504,506,508,510(FIG. 5). A size of the overkey620may be a sum of the sizes of the parcels604,606,608,610. The horizontal axis622indicates that the parcels612,614,616,618may be generated in a temporal order. The time required to generate each parcel604,606,608,610need not be proportional to the size of the parcel604,606,608,610.

The size of each parcel604,606,608,610may be randomly selected from a range of values, or randomly selected from a set of possible values. The number of protocol602rounds may be a fixed parameter of the cryptographic protocol602. Alternatively, the number of protocol602rounds may be variable. The protocol602rounds may continue until a number of bits generated by the protocol (e.g., the sum of the sizes of the parcels604,606,608,610) exceeds a threshold. For example, the protocol602rounds may continue until the number of bits generated by the protocol602exceeds a maximum size in a set of standard key sizes.

Detailed examples of cryptographic key generation protocols suitable for incorporation in an embodiment of the invention are described in co-pending U.S. patent application Ser. No. 10/735,992, filed Dec. 15, 2003, entitled “WIRELESS ONLINE CRYPTOGRAPHIC KEY GENERATION METHOD,” and in co-pending U.S. patent application Ser. No. 10/771,929, filed Feb. 4, 2004, entitled “DOMINO SCHEME FOR WIRELESS CRYPTOGRAPHIC COMMUNICATION AND COMMUNICATION METHOD INCORPORATING SAME.”

In an embodiment of the invention, one or more parameters of the cryptographic protocol are varied as a function of a variant subset of the bits of the overkey402(FIG. 4). The variant subset may be the terminating bits404of the overkey402, however, each embodiment of the invention is not so limited. The variant subset of bits may be the bits remaining after the key subset is extracted from the overkey402to serve as the live key326,328(FIG. 3). As with the key subset, the bits in the variant subset need not correspond to contiguous bits of the overkey402, and an order of the bits in the variant subset need not be the same as an order of the bits in the overkey402. The variant subset of bits may be any suitable subset of the overkey402.

FIG. 7depicts examples steps for enhancing cryptography-based security in accordance with an embodiment of the invention. At step702, a cryptographic protocol may be performed. For example, as described above, the cryptographic protocol may be performed by the secure communications modules320and322(FIG. 3). As for each step described below, step702may be incorporated into a series of steps, including steps not explicitly described below. In addition, step702may incorporate sub-steps including and/or in addition to those described below.

Step704and step706may be sub-steps of step702. At step704, an overkey may be generated. For example, the overkey402may be generated as described above with reference toFIGS. 4,5and6. At step706, one or more parameters of the cryptographic protocol may be varied. Examples of suitable cryptographic protocol parameters that may be varied at step706include the live key326,328(FIG. 3), characteristics of the live key326,328such as a cryptographic strength of the live key326,328(key strength), a re-key schedule of the live key326,328, a set of cryptographic keys associated with the re-key schedule of the live key326,328, a re-keying timetable associated with the re-key schedule of the live key326,328, and/or any suitable cryptographic protocol parameter or combinations thereof.

Cryptographic protocol parameters that may be varied at step706need not be limited, for example, to a single layer of the Open Systems Interconnection (OSI) Reference Model. Examples of suitable trans-layer parameters include session layer parameters such as synchronization, transport layer parameters such as data packet sequencing, network layer parameters such as network path routing, data link layer parameters such as channel parameters and data framing, and physical layer parameters such as media selection, signal modulation and encoding. In each case, a particular parameter value may be selected from a set of valid parameter values. For example, a particular signal modulation may be selected from among binary phase shift keying (BPSK), quadrature phase shift keying (QPSK), and a set of available quadrature amplitude modulations (QAM) such as 16-QAM and 64-QAM.

As with step702, step706may incorporate sub-steps. Step708and step710may be sub-steps of step706. At step708, a function of an overkey subset (up to and including the entire overkey, e.g., overkey402ofFIG. 4) may be evaluated. For example, a function of the variant subset of the bits of the overkey402may be evaluated. Examples of suitable functions that may be evaluated at step708include a permutation of the overkey subset, an output of a pseudo-random number generator seeded with the overkey subset, a linear binary transformation of the overkey subset, and a nonlinear binary transformation the overkey subset. At step710, a particular parameter of the cryptographic protocol may be updated. For example, the parameter of the cryptographic protocol may be updated with the result of the function evaluated at step708.

Steps708and710may be performed for each cryptographic protocol parameter varied at step706(optionally in parallel). A same function need not be evaluated for each cryptographic protocol parameter. However, in an embodiment of the invention, a same and deterministic function of the overkey subset is evaluated at each computer202,204(FIG. 2) participating in the cryptographic protocol, for example, so that those parameters of the cryptographic protocol that are varied may be varied in the same way at each participating node and, optionally, at the same time.

In an embodiment of the invention, synchronously varying parameters of the cryptographic protocol at participating nodes enhances a resistance of the varied parameters to characterization by an adversary. The resistance to characterization may be further enhanced by more frequent variation. In an embodiment of the invention, frequent variation of cryptographic protocol parameters is made more efficient by varying the parameters as functions of some or all of the overkey402(FIG. 4). Multiple cryptographic protocol parameter variations may be derived from a single overkey. For example, a set of cryptographic keys may be derived from a single overkey, which may alleviate problems associated with cryptographic key generation and/or distribution. A detailed example with respect to cryptographic keys is described below with reference toFIG. 8.

FIG. 8depicts example steps for varying cryptographic protocol parameters in accordance with an embodiment of the invention. For example each of the steps depicted inFIG. 8may be performed by the computer302(FIG. 3) and/or the computer304. Furthermore, when performed at multiple computers, performance of one or more of the steps may be synchronized at each computer.

At step802, an overkey may be generated, for example, the overkey402(FIG. 4). Step802may be the same as, or similar to, step704(FIG. 7). At step804, a cryptographic key may be extracted from the overkey generated at step802, for example, the extracted key may be the key subset of bits of the overkey402as described above with reference toFIG. 4.

Cryptographic keys may differ in cryptographic strength. For example, some cryptographic key values may introduce regularities into the encrypted message324(FIG. 3) that aid an adversary attempting to characterize parameters of the associated cryptographic protocol. At step806, a cryptographic strength of the extracted key may be determined. For example, the extracted key may be tested for statistical and/or spectral randomness as described by D. Knuth in “The Art of Computer Programming,” Second Edition, Volume 2: Seminumerical Algorithms, Chapter 3: Random Numbers, published 1982 by the Addison Wesley Publishing Company.

At step808, it may be determined if the extracted key is a strong cryptographic key. For example, the extracted key may be determined to be a strong cryptographic key if the cryptographic strength determined at step806is greater than a strong key threshold. If the extracted key is determined to be a strong cryptographic key, then a thread of execution (e.g., of a process of the computer302,304, depicted inFIG. 3) may progress to step810. Otherwise, the thread of execution may progress to step812. At step810, the live key326,328(FIG. 3) may be updated. For example, the live key326,328may be updated with the cryptographic key extracted at step804.

Once the live key326,328(FIG. 3) is updated, the encrypted message324may be encrypted in accordance with the updated live key326,328. In an embodiment of the invention, the live key326,328, is updated periodically, that is, the secure communications module320,322is re-keyed in accordance with a re-key schedule. The re-key schedule may specify a fixed live key326,328update period (e.g., every 10 minutes). However, in an embodiment of the invention, the re-key schedule is varied according to a function of some or all of the overkey402(FIG. 4). For example, a delay between live key326,328updates may be varied as a function of the variant subset of the overkey402.

At step814, a wait period, e.g., a delay between live key326,328(FIG. 3) updates, may be determined. For example, a fixed delay between live key326,328updates may be divided by a size of a set of cryptographic keys that may be derived from the overkey402(FIG. 4). That is, the secure communications module320,322may re-key more frequently depending on the size of the set. Alternatively, or in addition, the delay between live key326,328updates may be varied as a function of the variant subset of the overkey402. For example, the wait period may be varied, within a specified range, in accordance with an output of a pseudo-random number generator seeded with the variant subset. The timetable of the re-key schedule may incorporate any such suitable wait period variation. As will be appreciated by one of skill in the art, the wait period variation may be deterministic so that, for example, a same variation may occur at each computer302,304participating in the cryptographic protocol.

At step816, the thread of execution may wait until the wait period determined at step814elapses. Once the wait period elapses, the thread of execution may progress to step812and thus ultimately to another live key326,328(FIG. 3) update. Step816may be implemented with an alarm or interrupt. In addition, the thread of execution may terminate at step816and then be re-instantiated in response to the alarm or interrupt.

In an embodiment of the invention, the set of cryptographically utilizable keys that may be extracted from the overkey generated at step802is finite. For example, repeated extraction of cryptographic keys from the overkey402(FIG. 4) may result in a sequence of cryptographic keys that, beyond a certain point in the sequence, introduces regularities that aid an adversary attempting to characterize parameters of the associated cryptographic protocol. An extraction metric may indicate a degree to which such regularities are likely to be introduced by further cryptographic key extraction. The extraction metric may be a simple counter, but it need not be. For example, the extraction metric may correspond to a statistical and/or spectral randomness measure of the sequence of cryptographic keys extracted from the current overkey402.

At step812, the extraction metric may be tested, for example, compared to an extraction metric threshold. If the extraction metric passes the test, the thread of execution may progress to step818. Otherwise, the thread of execution may progress to step820.

At step818, the overkey generated at step802(of a copy thereof) may be permuted, for example, in order to simplify extraction of cryptographic keys at step804. The permutation operation may be a simple binary rotation of the overkey402(FIG. 4) but each embodiment of the invention is not so limited. Any suitable permutation of the bits of the overkey402may be performed at step818.

At step822, the extraction metric may be updated. For example, if the extraction metric is a counter, the counter may be incremented. At step820, the extraction metric may be reset. For example, if the extraction metric is a counter, the counter may be reset to an initial value. In an embodiment of the invention, step820is incorporated into step802. That is, the extraction metric is reset at the same time that the overkey402(FIG. 4) is (re-)generated. Similarly, in an embodiment of the invention, steps818and822are incorporated into step804. That is, extraction of the live key326,328(FIG. 3) from the overkey402may simultaneously update the extraction metric and, optionally, involve a permutation of the overkey402or a copy thereof.

In an embodiment of the invention, a set of cryptographic keys are extracted at step804, the cryptographic strength of each extracted key is determined at step806and a strongest cryptographic key in the set is selected at step808for the live key326,328(FIG. 3) update at step810. In such an embodiment, steps812-822may be omitted or incorporated into earlier steps. In contrast, in other embodiments of the invention, steps806and808may be omitted. Any suitable combination of the steps depicted inFIG. 8may be incorporated into an embodiment of the invention.