WO2008059475A1

WO2008059475A1 - Secure communication

Info

Publication number: WO2008059475A1
Application number: PCT/IL2007/000679
Authority: WO
Inventors: Itsik Mantin
Original assignee: Nds Limited
Priority date: 2006-11-12
Filing date: 2007-06-04
Publication date: 2008-05-22
Also published as: IL179202A0

Abstract

A first device to securely communicate with a second device, the first device and the second device sharing a secret, the second device holding a cryptographic key which is at least partially based on the secret, the second device being operative to use a one-way function and the key to determine a first key recovery text, the first device comprising a receiving module to receive the first key recovery text from the second device, a key determination module to determine the key at least based on the secret and the first key recovery text by trial and error, and a communication module to: receive the key from the key determination module, and securely communicate with the second device using the key. Related apparatus and methods are also described.

Description

SECURE COMMUNICATION

FIELD OF THE INVENTION

The present invention relates to secure communication, and in particular, but not exclusively to, secure communication between two devices using a key.

BACKGROUND OF THE INVENTION

Secure communication usually relies on secure keys. The secure keys are either stored in advance in the communicating devices or generated during a session establishment protocol. In a secure communication protocol, when the communicating parties have a shared secret key, the parties may use the key to securely communicate with a very high level of confidence regarding the confidentiality and the integrity of the sent messages. Various methods of establishing a secure communication protocol are known to those ordinarily skilled in the art. By way of example, one known way to establish a secure communication protocol includes deriving two sub keys Kl and K2 from a shared key K, which is known to both parties. Kl is equal to a hash of a concatenation of the first part of K with a first fixed vector Vl and K2 is equal to a hash of a concatenation of the second part of K with a second fixed vector V2, where the hash is performed using a cryptographic hash function, for example, but not limited to, SHA-I. Messages are then encrypted using a block cipher algorithm, such as AES, with Kl as the encryption key. Message authentication codes (MACs), such as CBC-MAC, are calculated for the messages using K2 as the authentication key. Other suitable block ciphers and MAC schemes are known to those ordinarily skilled in the art for use as conventional building blocks of secure protocols. Other ways to mount a secure communication channel based on a shared key are known to those ordinarily skilled in the art.

The above-mentioned scheme may be attacked by an attacker that runs a trial and error search on the key K. A countermeasure against the attack is to make the key K too long for guessing using available technology or the particular application, for example, but not limited to, a 128 bit key.

However, in order to have a secure communication scheme based on symmetric key cryptography, each pair of communicating devices needs to have a shared key in order to communicate securely, meaning that the number of keys in the system is typically proportional to the number of possible pairs, which is

approximately (for N communicating devices). Therefore, each device

generally needs to maintain N-I keys for secure communication with the other N-I devices. So for example, using a secure key of 128 bits, results in a large storage burden for each device.

One solution is to use public key cryptography which is well known to those ordinarily skilled in the art, for example, but not limited to, the Diffie-

Hellman protocol using certificates signed by a known certificate authority. However, public key cryptography may not be suitable for low-resource devices that are not sufficiently powerful for employing public key algorithms.

Therefore, a solution for low-resource devices is to use symmetric key cryptography with manually entered keys. For example, a key generated by a first device is provided to a user of a second device and entered into the second device prior to mounting the secure communication channel.

In most cases, manually entered keys need to be short enough in order to avoid a serious burden on the user. For example, a 4-digit code is easy to invent, remember and enter whereas a 50-digit code is generally too long. However, if the keys are too short, security is generally compromised, as too short keys are easily attacked, as described above. Thus, the establishment of a secure communication channel is a practical problem.

A similar problem exists with respect to devices which do not allow for a sufficiently long shared key, for example, but not limited to, low resource devices such as RFID devices, mobile phones and Bluetooth devices. Such devices may have insufficient storage capabilities or may be required to base security on user passwords. Thus, it may be impossible to provide a sufficiently long key, for example, but not limited to, a 64 or 128 bit key, for many devices.

As described above in some environments and situations the keys on which the secure communication is based are too short and may be broken through a brute force attack. It is well known in the art that keys that are shorter than 48 bits are considered breakable through brute force attack. As technology improves, the definition of too short and sufficiently long will probably change.

The following references are also believed to represent the state of the art: US Patent 5,241,599 to Bellovin, et al.;

US Patent 5,315,658 to Micali;

US Patent 5,416,841 to Merrick;

US Patent 5,764,772 to Kaufman, et al.;

US Patent 6,079,021 to Abadi, et al.; US Patent 6,424,713 to Sprunk;

US Published Patent Application 2005/0157879 of Tanaka, et al.;

European Published Patent Application EP 0202768 of IBM Corp.;

Abstracts of Japanese Published Patent Applications 2004347885, 2005051360, 2003309551 of Nippon Telegraph & Telephone; Abstract of Japanese Published Patent Application 2005130447;

Definition of "Merkle's Puzzles" from www.wikipedia.com;

-Article entitled "ISAKMP Key Recovery Extensions" by David Balenson and Tom Markham in Computers & Security, 19 (2000) pages 91-99; and Article entitled "Specification and analysis of n-way key recovery system by Extended Cryptographic Times Petri Net" by Shin- Young Lim, Jeong- Ho Ko, Eun-Ah Jun and Gang-Soo Lee in the Journal of Systems and Software, 58 (2001) pages 93-106. The disclosures of all references mentioned above and throughout the present specification, as well as the disclosures of all references mentioned in those references, are hereby incorporated herein by reference.

SUMMARY OF THE INVENTION

The present invention seeks to provide an improved secure communication system.

The system of the present invention, in preferred embodiments thereof, includes a secure communication system for providing a sufficiently long cryptographic key for use in encrypted communication between devices while allowing the users of the devices to share a manageable shared secret which is generally, but not always, too short for the specific security needs.

The system of the present invention, in preferred embodiments thereof, is particularly useful for: devices that are weak, and/or only have a small secure storage for keys; and/or devices that rely on volatile secrets and use inputs instead of non-volatile keys; and/or Bluetooth secure specification which relies on

4-digit secret keys; and/or communication between mobile devices; and/or secure communication between a strong reader and an RFID device implemented with some suitable randomness.

There is thus provided in accordance with a preferred embodiment of the present invention, a first device to securely communicate with a second device, the first device and the second device sharing a secret, the second device holding a cryptographic key which is at least partially based on the secret, the second device being operative to use a one-way function and the key to determine a first key recovery text, the first device including a receiving module to receive the first key recovery text from the second device, a key determination module to determine the key at least based on the secret and the first key recovery text by trial and error, and a communication module to receive the key from the key determination module, and securely communicate with the second device using the key.

Further, in accordance with a preferred embodiment of the present invention the communication module is operative to securely communicate using encrypted communication. Still further, in accordance with a preferred embodiment of the present invention the communication module is operative to securely communicate using digital authentication.

Additionally in accordance with a preferred embodiment of the present invention, the one-way function is a cryptographic hash function and the first key recovery text is a hash of the key.

Moreover, in accordance with a preferred embodiment of the present invention the key determination module includes a test key generation module to determine a test key based on the secret, a hash module to hash the test key yielding an output text, and a comparison module to compare the output text to the first key recovery text.

Further in accordance with a preferred embodiment of the present invention if the key determination module determines more than one key based on the secret and the first key recovery text, then the receiving module is operative to receive another key recovery text from the second device, the other key recovery text being a hash of a new key, and the key determination module is operative to determine the new key at least based on the secret and the other key recovery text by trial and error.

Still further in accordance with a preferred embodiment of the present invention the second device is operative to determine the first key recovery text with the one-way function using the key and a second key recovery text as input, the first device and the second device share the second key recovery text, the key determination module is operative to determine the key at least based on the secret, the first key recovery text and the second key recovery text by trial and error.

Additionally in accordance with a preferred embodiment of the present invention the key determination module includes a test key generation module to determine a test key based on the secret, a cipher module to cryptographically transform one of the first key recovery text and the second key recovery text using the test key yielding an output text, and a comparison module to compare the output text to one of the first key recover text and the second key recovery text.

Moreover in accordance with a preferred embodiment of the present invention the second key recovery text is plaintext, the first key recovery text is ciphertext, and the key determination module includes a test key generation module to determine a test key based on the secret, a cipher module to encrypt the second key recovery text using the test key yielding an output text, and a comparison module to compare the output text to the first key recovery text.

Further in accordance with a preferred embodiment of the present invention the second key recovery text is plaintext, the first key recovery text is ciphertext, and the key determination module includes a test key generation module to determine a test key based on the secret, a cipher module to decrypt the first key recovery text using the test key yielding an output text, and a comparison module to compare the output text to the second key recovery text. Still further in accordance with a preferred embodiment of the present invention if the key determination module determines more than one key based on the secret, the first key recovery text and the second key recovery text, then the receiving module is operative to receive a third key recovery text from the second device, the third key recovery text being a fourth key recovery text cryptographically transformed using the key, and the key determination module is operative to determine the key at least based on the secret, the third key recovery text and the fourth key recovery text.

Additionally in accordance with a preferred embodiment of the present invention, the determination of the test key includes concatenating the secret with another string.

Moreover, in accordance with a preferred embodiment of the present invention the determination of the test key includes concatenating a value based on the secret with another string.

■Further, in accordance with a preferred embodiment of "the present invention the determination of the test key includes performing a function on the secret. Still further in accordance with a preferred embodiment of the present invention, the device includes a confirmation module to send a confirmation message to the second device confirming, that the key has been determined. Additionally in accordance with a preferred embodiment of the present invention, the device includes a user input interface to allow input of the secret by a user.

Moreover, in accordance with a preferred embodiment of the present invention, the device includes a secret determination module to determine the secret based on a plurality of random bits.

Further, in accordance with a preferred embodiment of the present invention, the device includes an output interface to output the secret for entry by a user of the second device into the second device.

Still further, in accordance with a preferred embodiment of the present invention, the device includes a storage arrangement having the secret burned therein.

Additionally in accordance with a preferred embodiment of the present invention, the device includes a wireless interface to securely communicate wirelessly between the first device and the second device using the key.

There is also provided in accordance with still another preferred embodiment of the present invention a device to securely communicate with another device, including a secret determination module to determine a secret, an output interface to output the secret for entry by a user of the other device, a key generation module to generate a cryptographic key at least based on the secret, and a communication module to use a one-way function and the key to determine a key recovery text, send the key recovery text to the other device, and securely communicate with the other device using the key.

Moreover, in accordance with a preferred embodiment of the present invention, the device includes a random number generator to generate. a random number, the key generation module being operative to generate the key at least based on the secret and the random number.

Further, in accordance with a preferred embodiment of the present invention the key determination module is operative to determine the key by concatenating the secret with the random number.

Still further, in accordance with a preferred embodiment of the present invention the communication module is operative to securely communicate using encrypted communication.

Additionally in accordance with a preferred embodiment of the present invention, the communication module is operative to securely communicate using digital authentication.

Moreover, in accordance with a preferred embodiment of the present invention, the one-way function is a cryptographic hash function and the key recovery text is a hash of the key. Further, in accordance with a preferred embodiment of the present invention, the device includes a random number generator to generate a plurality of random bits wherein the secret determination module is operative to determine the secret based on the random bits.

There is also provided in accordance with still another preferred embodiment of the present invention a key recovery system associated with a first device to facilitate secure communication between the first device and a second device, the first device and the second device sharing a secret, the second device holding a cryptographic key which is at least partially based on the secret, the second device being operative to use a one-way function and the key to determine a first key recovery text, the system including a receiving module to receive the first key recovery text from the second device, and a key determination module to determine the key at least based on the secret and the first key recovery text by trial and error, and transfer the key to a communication module of the first device in order to facilitate secure communication between the first device and the second device using the key. Still further, in accordance with a preferred embodiment of the present invention the secure communication includes encrypted communication.

Additionally in accordance with a preferred embodiment of the present invention, the secure communication includes digital authentication. Moreover, in accordance with a preferred embodiment of the present invention, the one-way function is a cryptographic hash function and the first key recovery text is a hash of the key.

Further, in accordance with a preferred embodiment of the present invention the key determination module includes a test key generation module to determine a test key based on the secret, a hash module to hash the test key yielding an output text, and a comparison module to compare the output text to the first key recovery text.

Still further in accordance with a preferred embodiment of the present invention if the key determination module determines more than one key based on the secret and the first key recovery text, then the receiving module is operative to receive another key recovery text from the second device, the other key recovery text being a hash of a new key, and the key determination module is operative to determine the new key at least based on the secret and the other key recovery text using trial and error. Additionally in accordance with a preferred embodiment of the present invention the second device is operative to determine the first key recovery text with the one-way function using the key and a second key recovery text as input, the first device and the second device share the second key recovery text, the key determination module is operative to determine the key at least based on the secret, the first key recovery text and the second key recovery text by trial and error.

Moreover in accordance with a preferred embodiment of the present invention the key determination module includes a test key generation module to determine a test key based on the secret, . a cipher module to cryptographically transform one of the first key recovery text and the second key recovery text using the test key yielding an output text, and a comparison module to compare the output text to one of the first key recover text and the second key recovery text.

Further in accordance with a preferred embodiment of the present invention the second key recovery text is plaintext, the first key recovery text is ciphertext, and the key determination module includes a test key generation module to determine a test key based on the secret, a cipher module to encrypt the second key recovery text using the test key yielding an output text, and a comparison module to compare the output text to the first key recovery text.

Still further in accordance with a preferred embodiment of the present invention the second key recovery text is plaintext, the first key recovery text is ciphertext, and the key determination module includes a test key generation module to determine a test key based on the secret, a cipher module to decrypt the first key recovery text using the test key yielding an output text, and a comparison module to compare the output text to the second key recovery text. Additionally in accordance with a preferred embodiment of the present invention if the key determination module determines more than one key based on the secret, the first key recovery text and the second key recovery text, then the receiving module is operative to receive a third key recovery text from the second device, the third key recovery text being a fourth key recovery text cryptographically transformed using the key, and the key determination module is operative to determine the key at least based on the secret, the third key recovery text and the fourth key recovery text.

Moreover, in accordance with a preferred embodiment of the present invention the determination of the test key includes concatenating the secret with another string.

Further, in accordance with a preferred embodiment of the present invention the determination of the test key includes concatenating a value based on the secret with another string.

Still ■ further in accordance with a preferred embodiment of the present invention the determination of the test key includes performing a function on the secret. Additionally in accordance with a preferred embodiment of the present invention, the system includes a confirmation module to send a confirmation message to the second device confirming that the key has been determined.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention will be understood and appreciated more fully from the following detailed description, taken in conjunction with the drawings in which: Fig. 1 is a partly pictorial, partly block diagram view of a secure communication system constructed and operative in accordance with a preferred embodiment of the present invention;

Fig. 2 is a partly pictorial, partly block diagram view of encrypted communication using a key in the system of Fig. 1; Fig. 3 is a block diagram view of a device for generating a key in the system of Fig. 1;

Fig. 4 is a block diagram showing a preferred method of key generation by the device of Fig. 3;

Fig. 5 is a block diagram showing a first alternative preferred method of key generation by the device of Fig. 3 ;

Fig. 6 is a block diagram showing a second alternative preferred method of key generation by the device of Fig. 3;

Fig. 7 is a block diagram view of a device showing a preferred method of determining a key in the system of Fig. 1; Fig. 8 is a block diagram view of a device showing an alternative preferred method for determining a key in the system of Fig. 1;

Fig. 9 is a pictorial view of a secure communication system constructed and operative in accordance with another preferred embodiment of the present invention; Fig. 10 is a pictorial view of a secret being outputted in the system of Fig. 9;

Fig. 11 is a pictorial view of the secret of Fig. 10 being manually transferred; Fig. 12 is a pictorial view of a secret being displayed in the system of Fig. 9;

Fig. 13 is a pictorial view of the secret of Fig. 12 being verbally conveyed to another user in the system of Fig. 9; Fig. 14 is a pictorial view of wireless encrypted communication in the system of Fig. 9;

Fig. 15 is a block diagram view of a device for use in a secure communication system constructed and operative in accordance with yet another preferred embodiment of the present invention; and Fig. 16 is a block diagram view of another device for use in the system of Fig. 15.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

Reference is now made to Fig. I₅ which is a partly pictorial, partly block diagram view of a secure communication system 10 constructed and operative in accordance with a preferred embodiment of the present invention. The secure communication system 10 is operative to facilitate secure communication between a device 12 and a device 14. By way of example only, devices 12, 14 are mobile telephones. However, it will be appreciated by those ordinarily skilled in the art that devices 12, 14 can be any suitable devices that need to communicate using secure communication. Typically, a user 16 of the device 12 and a user 18 of the device 14 agree on sharing a secret 20 which is preferably easy to remember and/or easy to enter into the devices 12, 14. The secret 20 is then entered into the devices 12, 14 by the respective users 16, 18. The device 12 then generates a cryptographic key 22 based on the secret 20 (block 30) and typically on an additional input, such as a plurality of random bits, for example true random bits, and/or pseudo random bits, and/or or bits that are derived from chaotic user input such as mouse movement or random key strokes. The generation of the cryptographic key 22 is described in more detail with reference to Fig. 3.

The secret 20 may be entered by the users 16, 18 using any suitable user input interface such as a keypad 21, or a keyboard or mouse when the communication.device is equipped with a keyboard or mouse.

Alternatively, the device 12 generates the secret 20 based on a plurality of random bits, discussed in more detail with reference to Fig. 3. The secret 20 is then outputted by the device 12, using any suitable output interface, for example, but not limited to, a display screen 23 of the device 12, so that the user 16 of device 12 can share the secret 20 with the user 18 of the device 14. The user 18 of the device 14 then enters the secret 20 into the device 14 using the keypad 21 of the device 14. Alternatively, the secret 20 may be generated by the device 14 for output to an output interface, such as a display screen 25 of the device 14, for sharing with the user 16 of the device 12. Alternatively, the secret 20 may be burned into the device 12 and/or the device 14. If the secret 20 is only burned into one of the devices 12, 14, then the secret 20 needs to outputted for entry into the other device 12, 14.

The user 16 of the device 12 also preferably shares with the user 18 of the device 14 how the secret 20 is associated with the cryptographic key 22.

The user 18 then inputs the information into device 14, for example by entering an index of one of a list of algorithms for associating the secret 20 with the cryptographic key 22.

Generation of the key 22 held by the device 12 is described in more detail with reference to Figs. 3-6. Methods of combining "short-keys" to become "long-keys" are known to those ordinarily skilled in the art.

The device 12 and the device 14 also share a known key recovery- plaintext 24, for example, but not limited to, a string of 64 zeros or a string of 64 ones or any other suitable plaintext of any suitable length. The device 12 is preferably operative to determine a key recovery ciphertext 26, which is the plaintext 24 cryptographically transformed using a oneway function (encrypted) using the cryptographic key 22 (block 30). The ciphertext 26 is then preferably sent by the device 12 to the device 14 (block 34). Preferably, the plaintext 24 is. sent to device 14 by the device 12 with the ciphertext 26.. Alternatively, the plaintext 24 may be sent in advance to the device 14 or handed to the user 18 of the device 14 for entering manually into the device 14, by way of example only. It will be appreciated by those ordinarily skilled in the art that other suitable methods of sharing the plaintext 24 between the devices 12, 14 are possible. The term "one-way function" as used in the specification and claims is a function f such that for each x in the domain f, it is easy to compute f(x) (for example using current technology computation is typically in the order of seconds or less); but for essentially all y in the range off, it is computationally infeasible to find any x such that y=f(x).The term "infeasible" as used in the specification and claims is defined as a problem that while theoretically is possible to solve, in practice is not, due to practical limitations in the amount of time and hardware available. For example only, if a problem can be solved using all the computers in existence working full time the next billion years, that might be considered computationally infeasible. An important property is that advances in technology and theory may well change the definition of what is infeasible. By way of example only, it is currently believed that it is practically impossible to break the AES (Advanced Encryption Standard) via a brute force attack of exploring all 2 to the power 128 possible keys.

Methods of cryptographic transformation are known to those ordinarily skilled in the art, for example, but not limited to, using a block cipher, such as AES, to encrypt/decrypt a block of data.

The device 14 is preferably associated with a key recovery system 28 which receives the ciphertext 26. The key recovery system 28 then generally performs trial and error operations in order to determine the cryptographic key 22 based on the secret 20 (including how the secret 20 is associated with the cryptographic key 22), the plaintext 24 and the ciphertext 26. The determination of the cryptographic key 22 based on the secret 20, the plaintext 24 and the ciphertext 26 is described in more detail with reference to Figs. 7 and 8.

After the cryptographic key 22 has been determined by the device 14, a confirmation message 36 is sent from the device 14 to the device 12.

In general, the secret 20 and the cryptographic key 22 are chosen such that the device 14 can perform trial and error operations in order to determine the cryptographic key 22 based on the secret 20 in a reasonable amount of time, for example, but not limited to, within a number of seconds, whereas an attacker, not knowing the secret 20, will find it extremely difficult, or almost impossible, to determine the cryptographic key 22.

By way of example only, the cryptographic key 22 is a concatenation of the secret 20 and another string. If the secret is a 9 digit password which translates into a 30 bit binary value and the other string is a binary value with a length of 34 bits, the cryptographic key 22 has a length of 64 bits which generally affords a reasonably high level of security in many scenarios. As the device 14 already knows the secret 20 which is 30 bits of the cryptographic key 22 (and how the secret 20 is associated with the cryptographic key 22), the device 14 only needs to run a trial and error search on the remaining 34 bits of the cryptographic key 22 in relation to the unknown other string. The trial and error search on the remaining 34 bits is a relatively straightforward task for most

_O34 devices, requiring in the order of ^ (2 to the power 34) trails. However, any device which does not know the secret 20 needs to determine all 64 bits of the cryptographic key 22 in order to successfully attack the encrypted communication between the device 12 and the device 14 and a brute force attack on 64 bits

^64 generally requires very expensive hardware to perform in the order to ^ (2 to the power 64) trials, which is appreciated by those ordinarily skilled in the art as significant effort.

It will be appreciated by those ordinarily skilled in the art that as technology improves, the security offered by a certain length key and the ease in which a certain length key can be attacked will probably change and therefore, those ordinarily skilled in the art will appreciate that the numbers used in the examples of the present specification may need to be adjusted accordingly.

The cryptographic key 22 determined by the key recovery system 28 is then available for use by the device 14 for encrypted communication with the device 12 as shown in Fig. 2, which is a partly pictorial, partly block diagram view of encrypted communication between the user 16 of the device 12 and the user 18 of the device 14 using the key 22 in the system 10 of Fig. 1.

It will be appreciated by those ordinarily skilled in the art that the system and method of the present invention may implemented with any suitable encrypted communication between two devices, for example, but not limited to, data communication between infrared ports of two mobile devices.

Reference is now made to Fig. 3, which is a block diagram view of the device 12 for generating the cryptographic key 22 in the system 10 of Fig. 1.

The device 12 preferably includes a communication module 38, a random number generator 40 and a key generation module 42. The communication module 38 is preferably operative to facilitate secure communication with other devices, such as the device 14 (Figs. 1 and 2). Secure communication includes encrypted communication and/or digital authentication, for example, but not limited to, digital signatures. The communication module 38 also performs cryptographic transforms (encrypting and/or decrypting) using a suitable cryptographic key, such as the cryptographic key 22.

The random number generator 40 is preferably operative to generate a random number 44 for use by the key generation module 42. The random number 44 is typically a binary string. The random number generator 40 is any suitable random number generator, for example, but not limited to, a pseudorandom number generator with a random seed or a true-random number generator or a module for obtaining pseudo-random input from an external source such as random keystrokes or random mouse movements, by way of example only. The key generation module 42 is preferably operative to generate the cryptographic key 22 based on the secret 20 and the random number 44.

In accordance with an alternative preferred embodiment of the present invention, the key generation module 42 first generates the cryptographic key 22 and then the secret 20 is derived from the cryptographic key 22 by the key generation module 42, typically based on the random number 44.

As described above with reference to Fig. 1, the secret 20 is typically: determined by the users 16, 18; or generated by one of the devices 12, 14 and then outputted for manually entry into the other device 12, 14; or burned into both of the devices 12, 14; or burned into one of the devices 12, 14 and then outputted for manual entry into the other device 12, 14. Therefore, device 12 may include: a user input interface 27 (typically the keypad 21 (Fig. I)) for manual entry of the secret 20; and/or a secret determination module (SDM) 29 for generating the secret based on a plurality of random bits typically generated by the random number generator 40; and/or a storage arrangement 31 for burning the secret 20 therein. The generation of the cryptographic key 22 is described in more detail with reference to Figs. 4-6.

The plaintext 24 (known to both the device 12 and the device 14) is then cryptographically transformed using a one-way function (typically encrypted) by the communication module 38 yielding the ciphertext 26.

Reference is now made to Fig. 4, which is a block diagram showing a preferred method of key generation by the device 12 of Fig. 3. The cryptographic key 22 is formed by concatenating the secret 20 with the random number 44. The above method is particularly useful when both the secret 20 and the random number 44 are in the same format, for example, but not limited to, binary format. It will be appreciated by those ordinarily skilled in the art that the secret 20 does not need to be placed only at the beginning or the end of the cryptographic key 22, the secret 20 may be placed at any suitable location in the cryptographic key 22 or even broken into two or more segments for disposal at different suitable locations within the cryptographic key 22.

Reference is now made to Fig. 5, which is a block diagram showing a first alternative preferred method of key generation by the device 12 of Fig. 3. The secret 20, for example, an alphanumeric password, is first transformed into a binary representation 46 of the secret 20. The binary representation 46 is then concatenated with the random number 44, which is in binary format, to form the cryptographic key 22.

Reference is now made to Fig. 6, which is a block diagram showing a second alternative preferred method of key generation by the device 12 of Fig. 3. The cryptographic key 22 is formed from the output of a function 48 using the secret 20 and the random number 44 as input. By way of example only, the function is a cryptographic Hash function, such as SHA-I. However, it will be appreciated by those ordinarily skilled in the art that any suitable function may be used.

Reference is now made to Fig. 7, which is a block diagram view of the device 14 showing a preferred method of determining the cryptographic key 22 in the system 10 of Fig. 1. The device 14 preferably includes a communication module 50 and the key recovery system 28.

The communication module 50 is preferably operative to receive and/or transmit encrypted data packets, for example, to and from the device 12 (Figs. 1-3). The communication module 50 is also preferably operative to encrypt and/or decrypt data as required.

The ciphertext 26 sent by the communication module 38 of the device 12 (Fig. 3) is preferably received by the communication module 50 (arrow 78). As the communication module 50 does not have a cryptographic key with which to decrypt the ciphertext 26, the ciphertext 26 is forwarded to the key recovery system 28 in order to determine the cryptographic key 22 for use in encrypted communication between the device 12 and the device 14 (arrow 80).

The key recovery system 28 is typically implemented as part of the device 14 using suitable elements of the device 14. Alternatively, the key recovery system 28 may be implemented as a plug-in for connection to the device 14.

Alternatively, the functionality of the key recovery system 28 may be implemented partly using elements of the device 14 and partly using a plug-in.

The key recovery system 28 preferably includes a receiving module 52, a key determination module 54 and a confirmation module 66. The receiving module 52 is typically operative to receive the ciphertext 26 from the device 12, typically via the communication module 50 (arrow 80). The receiving module 52 forwards the ciphertext 26 to the key determination module 54 for processing (arrow 74).

In general, the key determination module 54 determines the cryptographic key 22 based on the secret 20 (and how the secret 20 is associated . with the cryptographic key 22), the plaintext 24 and the ciphertext 26 by trial and error. After the cryptographic key 22 has been determined, the cryptographic key 22 is transferred to the communication module 50 in order to facilitate secure communication between the device 12 and the device 14 using the cryptographic key 22 (arrow 68). The secure communication typically includes encrypted communication and/or digital authentication, for example, but not limited to, digital signatures. The encrypted communication may be two-way or one-way (in either direction) between the device 12 (Figs. 1-3) and the device 14.

The determination of the cryptographic key 22 by the key determination module 54 is now described in more detail. The key determination module 54 preferably includes a test key generation module 56, a cipher module 58 and a comparison module 60.

The test key generation module 56 is preferably operative to determine a test key 62 based on the secret 20 and in the way that the secret 20 is associated with the cryptographic key 22 by the key generation module 42 of the device 12 (arrow 76) (see Figs. 3-6).

The cipher module 58 is preferably operative to ciyptographically transform (encrypt) the plaintext 24 using the test key 62 yielding an output text 64 (ciphertext) (arrow 82). It will be appreciated by those ordinarily skilled in the art that the cipher module may be the same encryption/decryption module used by the communication module 50 or a separate encryption/decryption module.

It will be appreciated by those ordinarily skilled in the art that the cryptographic algorithm used to determine the cryptographic key 22 for use between the device 12 and the device 14 may be the same as, or different from, the cryptographic algorithm used for other encrypted communication between the device 12 and the device 14 using the cryptographic key 22.

The comparison module 60 is preferably operative to compare the output text 64 with the ciphertext 26. The comparison module 60 preferably receives the ciphertext 26 from the receiving module 52 (arrow 74). If the output text 64 is equal to the ciphertext 26, then the test key 62 is generally a possible candidate for being the cryptographic key 22.

The steps performed by the test key generation module 56, cipher module 58 and the comparison module 60 are repeated for all possible values of the test key 62, based on the secret 20 (arrow 72) and the way that the secret 20 is associated with the cryptographic key 22, in order to rule out spurious results, as it may be possible for the key determination module 54 to determine more than one matching key based on the secret 20, the plaintext 24, the ciphertext 26 and the way that the secret 20 is associated with the cryptographic key 22.

If only one of the test keys 62 (a unique test key) is a possible candidate for being the cryptographic key 22, then the unique test key 62 is defined as the cryptographic key 22 and the cryptographic key 22 is transferred to the communication module 50 for use in encrypted communication between the device 12 and the device 14 (arrow 68). The communication module 50 receives the cryptographic key 22 from the comparison module 60 of the key determination module 54. The confirmation module 66 receives a command 84 from the comparison module 60 to send the confirmation message 36 to the device 12, via the communication module 50, confirming that the cryptographic key 22 has been determined (arrows 70).

If more than one candidate for the cryptographic key 22 has been determined based on the secret 20, the plaintext 24, the ciphertext 26, and the way that the secret 20 is associated with the cryptographic key 22 by the key generation module 42 of the device 12, then a message (not shown) is sent to the device 12 typically by the confirmation module 66 via the communication module 50 requesting receipt of a new key recovery ciphertext (not shown) being a cryptographic transform (encryption) of a new key recovery plaintext (not shown), known by the device 14, using the same cryptographic key 22. The receiving module 52 then receives the new ciphertext from the device 12 via the communication module 50. Preferably, the plaintext 24 is sent to device 14 by the device 12 with the ciphertext 26. Alternatively, the plaintext 24 may be sent in advance to the device 14 or handed to the user 18 of the device 14 for entering manually into the device 14, by way of example only. The key determination module 54 is then operative to determine the cryptographic key 22 based on the secret 20, the new ciphertext, the new plaintext and the way that the secret 20 is associated with the cryptographic key 22, as described above with reference to the test key generation module 56, the cipher module 58 and the comparison module 60. If the new ciphertext does not yield a unique result for the cryptographic key 22, then another new key recovery ciphertext and plaintext is generally requested. The process is repeated until a unique result for the cryptographic key 22 is found.

As described above with reference to Fig. 1, the secret 20 is typically: determined by the users 16, 18; or generated by one of the devices 12, 14 and then outputted for manually entry into the other device 12, 14; or burned into both of the devices 12, 14; or burned into one of the devices 12, 14 and then outputted for manual entry into the other device 12, 14. Therefore, the device 14 may include a user input interface (typically the keypad 23 (Fig. I)) for manual entry of the secret 20 or the key recovery system 28 may include: a secret determination module 33 (SDM) for generating the secret based on a plurality of random bits; or a storage arrangement 35 for burning the secret 20 therein.

Reference is now made to Fig. 8, which is a block diagram view of the device 14 showing an alternative preferred method for determining the cryptographic key 22 in the system 10 of Fig. 1. The alternative preferred method is substantially the same as the method described with reference to Fig. 7 except for the following differences. The cipher module 58 is preferably operative to receive the ciphertext 26 from the receiving module 52 (arrow 88) and to decrypt the ciphertext 26 using the test key 62 yielding an output text 86 (arrow 90). The comparison module is preferably operative to compare the output text 86 with the plaintext 24. If the output text 86 is equal to the plaintext 24, then the test key 62 is a possible candidate for being the cryptographic key 22.

If choice allows, the stronger of the two communicating devices 12, 14 is chosen to perform the trial-and-error operations and the weaker of the two communicating devices (for example, but not limited to, the weaker of the devices 12, 14) is selected to determine the cryptographic key 22 (Fig. 1). However, when only one of the devices 12, 14 has the capability to determine the cryptographic key 22 through using a suitable random number generator (pseudo-random or true- random) or has a proper output interface (for example, but not limited to, a display screen or printer), the device with the capability to determine and output the cryptographic key 22 is typically chosen as the device to determine and output the cryptographic key 22. The secure communication system 10 is particularly useful for the following cases: secure communication between devices that are weak and/or have only a small secure storage for keys; and/or secure communication between devices that rely on volatile secrets and use inputs instead of non-volatile keys; and/or Bluetooth secure specification which relies on 4-digit secret keys; and/or secure communication between mobile devices; and/or secure communication between a strong reader with an RFID device implemented with some randomness.

Reference is now made to Fig. 9, which is a pictorial view of a secure communication system 92 constructed and operative in accordance with another preferred embodiment of the present invention. The secure communication system 92 is described to further illustrate different methods of secret sharing. It will be appreciated that the methods of secret sharing described with reference to the secure communication system 92 may be used with the secure communication system 10 of Fig. 1. A user 94 is using a computer system 98 and a user 96 is using a computer system 100. Each computer system 98, 100 preferably includes a wireless interface 102 to enable wireless communication between the computer systems 98, 100. Each computer system 98, 100 typically includes a user input interface 104 (keyboard and preferably a mouse) as well as a display screen 106 and a processor 108. The computer system 98 also preferably includes a printer 110.

Reference is now made to Fig. 10, which is a pictorial view of a secret 112 being outputted in the system 92 of Fig. 9. The processor 108 of the computer system 98 preferably generates the secret 112. The secret 112 is then typically outputted to the printer 110 (output interface) and printed onto a sheet of paper 114.

Reference is now made to Fig. 11, which is a pictorial view of the secret 112 of Fig. 10 being manually transferred. The paper 114 is typically handed by the user 94 to the user 96 so that the user 96 can manually enter the secret 112 (Fig. 10) into the computer system 100 (Fig. 9). Reference is now made to Fig. 12, which is a pictorial view of the secret 112 being displayed. Instead of the secret 112 being printed out, the secret 112 is displayed ori to the display screen 106 (output interface) of the computer system 98. Reference is now made to Fig. 13, which is a pictorial view of the secret 112 of Fig. 12 being verbally conveyed by the user 94 to the user 96 in the system of Fig. 9. The user 96 then preferably manually enters the secret 112 into the computer system 100 (Fig. 9).

Reference is now made to Fig. 14, which is a pictorial view of, wireless encrypted communication in the system 92 of Fig. 9. The computer system 100 determines the encryption key by trial and error. Once the key has been determined, the computer system 98 and the computer system 100 securely communicate wirelessly using the key via the wireless interfaces 102.

Reference is now made to Fig. 15, which is a block diagram view of a device 116 for use in a secure communication system 118 constructed and operative in accordance with yet another preferred embodiment of the present invention. The system 118 is substantially the same as the secure communication system 10 of Figs. 1-8 except for the following differences described with reference to Figs. 15 and 16. The system 118 is preferably operative to enable secure communication between the device 116 and a device 122 described with reference to Fig. 16.

The device 116 is substantially the same as the device 12 of Fig. 3, except for the following differences. The communication module 38 is preferably operative to use a cryptographic hash function, for example, but not limited to, SHA-I, to determine a key recovery text which is a hash value 120 of the key 22. The hash value 120 is then typically sent by the communication module 38 to the device 122.

Reference is now made to Fig. 16, which is a block diagram view of the device 122 for use in the system 118 of Fig. 15. The device 122 is substantially the same as the device 14 of Fig. 7 except for the following differences. The hash value 120 is preferably received by the communication module 50 of the device 122. The receiving module 52 is preferably operative to receive the hash value 120 (key recovery text) from the communication module 50. In general, the key determination module 54 is operative to: determine the key 22 based on the secret 20 and the hash value 120 by trial and error; and transfer the key 22 to the communication module 50 in order to facilitate secure communication between the device 116 and the device 122. The secure communication is typically encrypted communication and/or digital authentication.

The key determination module 54 includes a hash module 124 instead of the cipher module 58 of Fig. 7. The hash module 124 receives the test key 62 from the test key generation module 56 and hashes the test key 62 using the cryptographic hash function of Fig. 15 yielding an output text 126. The comparison module 60 compares the output text 126 to the hash value 120 (key recovery text). The comparison module 60 preferably receives the hash value 120 from the receiving module 52 (arrow 74). If the output text 126 is equal to the hash value 120, then the test key 62 is generally a possible candidate for being the cryptographic key 22.

The steps performed by the test key generation module 56, hash module 124 and the comparison module 60 are repeated for all possible values of the test key 62, based on the secret 20 (arrow 72) and the way that the secret 20 is associated with the cryptographic key 22, in order to rule out spurious results, as it may be possible for the key determination module 54 to determine more than one matching key based on the secret 20, the hash value 120 and the way that the secret 20 is associated with the cryptographic key 22.

If only one of the test keys 62 (a unique test key) is a possible candidate for being the cryptographic key 22, then the unique test key 62 is defined as the cryptographic key 22 and the cryptographic key 22 is transferred to the communication module 50 for use in encrypted communication between the device 116 and the device 122 (arrow 68).

If more than one candidate for the cryptographic key 22 has been determined based on the secret 20, the hash value 120 and the way that the secret

20 is associated with the cryptographic key 22 by the, key generation module 42 of the device 116 (Fig. 15), then a message (not shown) is typically sent to the device 116 by the confirmation module 66 via the communication module 50 requesting receipt of a new key recovery text (not shown) being a hash of a new cryptographic key (not shown) using the cryptographic hash function. The receiving module 52 then receives the new key recovery text from the device 116 via the communication module 50. The key determination module 54 is then operative to determine the new cryptographic key based on the secret 20 and the new key recovery text and the way that the secret 20 is associated with the new cryptographic key using trial and error, as described above with reference to the test key generation module 56, the hash module 124 and the comparison module 60. If the new key recovery text does not yield a unique result for the new cryptographic key, then another new key recovery ciphertext is generally requested. The process is repeated until a unique cryptographic key is found.

In order to reduce the chance of finding more than one candidate for the cryptographic key 22, the cryptographic hash-function is preferably configured to avoid collision by expanding the input using padding for example by repeating the input (typically many times) to form a concatenated value which is then hashed. It is appreciated that software components of the present invention may, if desired, be implemented in ROM (read only memory) form. The software components may, generally, be implemented in hardware, if desired, using conventional techniques.

It will be appreciated that various features of the invention which are, for clarity, described in the contexts of separate embodiments may also be provided in combination in a single embodiment. Conversely, various features of .the invention which are, for brevity, described in the context of a single embodiment may also be provided separately or in any suitable sub-combination. It will also be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove. Rather the scope of the invention is defined only by the claims which follow.

Claims

What is claimed is:CLAIMS

1. A first device to securely communicate with a second device, the first device and the second device sharing a secret, the second device holding a cryptographic key which is at least partially based on the secret, the second device being operative to use a one-way function and the key to determine a first key recovery text, the first device comprising: a receiving module to receive the first key recovery text from the second device; a key determination module to determine the key at least based on the secret and the first key recovery text by trial and error; and a communication module to: receive the key from the key determination module; and securely communicate with the second device using the key.

2. The device according to claim 1, wherein the communication module is operative to securely communicate using encrypted communication.

3. The device according to claim 1 or claim 2, wherein the communication module is operative to securely communicate using digital authentication.

4. The device according to any of claims 1-3, wherein the one-way function is a cryptographic hash function and the first key recovery text is a hash of the key.

5. The device according to claim 4, wherein the key determination module includes: a test key generation module to determine a test key based on the secret; a hash module to hash the test key yielding an output text; and a comparison module to compare the output text to the first key recovery text.

6. The device according to claim 4 or claim 5, wherein if the key determination module determines more than one key based on the secret and the first key recovery text, then: the receiving module is operative to receive another key recovery text from the second device, the other key recovery text being a hash of a new key; and the key determination module is operative to determine the new key at least based on the secret and the other key recovery text by trial and error.

7. The device according to any of claims 1-3, wherein: the second device is operative to determine the first key recovery text with the one-way function using the key and a second key recovery text as input; the first device and the second device share the second key recovery text; the key determination module is operative to determine the key at least based on the secret, the first key recovery text and the second key recovery text by trial and error.

8. The device according to claim 7, wherein the key determination module includes: a test key generation module to determine a test key based on the secret; a cipher module to cryptographically transform one of the first key recovery text and the second key recovery text using the test key yielding an output text; and a comparison module to compare the output text to one of the first key recover text and the second key recovery text.

9. The device according to claim 7, wherein: the second key recovery text is plaintext; the first key recovery text is ciphertext; and the key determination module includes: a test key generation module to determine a test key based on the secret; a cipher module to encrypt the second key recovery text using the test key yielding an output text; and a comparison module to compare the output text to the first key recovery text.

10. The device according to claim 7, wherein: the second key recovery text is plaintext; the first key recovery text is ciphertext; and the key determination module includes: a test key generation module to determine a test key based on the secret; a cipher module to decrypt the first key recovery text using the test key yielding an output text; and a comparison module to compare the output text to the second key recovery text.

11. The device according to any of claims 8-10, wherein if the key determination module determines more than one key based on the secret/ the first key recovery text and the second key recovery text, then: the receiving module is operative to receive a third key recovery text from the second device, the third key recovery text being a fourth key recovery text cryptographically transformed using the key; and the key determination module is operative to determine the key at least based on the secret, the third key recovery text and the fourth key recovery text.

12. The device according to any of claims 5, 8- 10, wherein the determination of the test key includes concatenating the secret with another string.

13. The device according to any of claims 5, 8- 10, wherein the determination of the test key includes concatenating a value based on the secret with another string.

14. The device according to any of claims 5, 8-10, wherein the determination of the test key includes performing a function on the secret.

15. The device according to any of claims 1- 14, further comprising a confirmation module to send a confirmation message to the second device confirming that the key has been determined.

16. The device according to any of claims 1- 15, further comprising a user input interface to allow input of the secret by a user.

17. The device according to any of claims 1- 15, further comprising a secret determination module to determine the secret based on a plurality of random bits.

18. The device according to any of claims 1- 15, 17, further comprising an output interface to output the secret for entry by a user of the second device into the second device.

19. The device according to any of claims 1-15, 17 further comprising a storage arrangement having the secret burned therein.

20. The device according to any of claims 1- 19, further comprising a wireless interface to securely communicate wirelessly between the first device and the second device using the key.

21. A device to securely communicate with another device, comprising: a secret determination module to determine a secret; an output interface to output the secret for entry by a user of the other device; a key generation module to generate a cryptographic key at least based on the secret; and a communication module to: use a one-way function and the key to determine a key recovery text; send the key recovery text to the other device; and securely communicate with the other device using the key.

22. The device according to claim 21, further comprising a random number generator to generate a random number, the key generation module being operative to generate the key at least based on the secret and the random number.

23. The device according to claim 22, wherein the key determination module is operative to determine the key by concatenating the secret with the random number.

24. The device according to any of claims 21-23, wherein the communication module is operative to securely communicate using encrypted communication.

25. The device according to any of claims 21-24, wherein the communication module is operative to securely communicate using digital authentication.

26. The device according to any of claims 21-25, wherein the one-way function is a cryptographic hash function and the key recovery text is a hash of the key.

27. The device according to any of claims 21-26, further comprising a random number generator to generate a plurality of random bits wherein the secret determination module is operative to determine the secret based on the random bits.

28. A key recovery system associated with a first device to facilitate secure communication between the first device and a second device, the first device and the second device sharing a secret, the second device holding a cryptographic key which is at least partially based on the secret, the second device being operative to use a one-way function and the key to determine a first key recovery text, the system comprising: a receiving module to receive the first key recovery text from the second device; and a key determination module to: determine the key at least based on the secret and the first key recovery text by trial and error; and transfer the key to a communication module of the first device in order to facilitate secure communication between the first device and the second device using the key.

29. The system according to claim 28, wherein the secure communication includes encrypted communication.

30. The system according to claim 28 or claim 29, wherein the secure communication includes digital authentication.

31. The system according to any of claims 28-30, wherein the one-way function is a cryptographic hash function and the first key recovery text is a hash of the key.

32. The system according to claim 31, wherein the key determination module includes: a test key generation module to determine a test key based on the secret; a hash module .to hash the. test key yielding an .output text; and . a comparison module to compare the output text to the first key recovery text.

33. The system according to any of claims 31-32, wherein if the key determination module determines more than one key based on the secret and the first key recovery text, then: the receiving module is operative to receive another key recovery text from the second device, the other key recovery text being a hash of a new key; and the key determination module is operative to determine the new key at least based on the secret and the other key recovery text using trial and error.

34. The system according to any of claims 28-30, wherein: the second device is operative to determine the first key recovery text with the one-way function using the key and a second key recovery text as input; the first device and the second device share the second key recovery text; the key determination module is operative to determine the key at least based on the secret, the first key recovery text and the second key recovery text by trial and error.

35. The system according to claim 34, wherein the key determination module includes: a test key generation module to determine a test key based on the secret; a cipher module to cryptographically transform one of the first key recovery text and the second key recovery text using the test key yielding an output text; and a comparison module to compare the output text to one of the first key recover text and the second key recovery text.

36. The system according to claim 34, wherein: the second key recovery text is plaintext; the first key recovery text is ciphertext; and Hie key determination module includes: a test key generation module to determine a test key based on the secret; a cipher module to encrypt the second key recovery text using the test key yielding an output text; and a comparison module to compare the output text to the first key recovery text.

37. The system according to claim 34, wherein: the second key recovery text is plaintext; the first key recovery text is ciphertext; and the key determination module includes: a test key generation module to determine a test key based on the secret; a cipher module to decrypt the first key recovery text using the test key yielding an output text; and a comparison module to compare the output text to the second key recovery text.

38. The system according to any of claims 34-37, wherein if the key determination module determines more than one key based on the secret, the first key recovery text and the second key recovery text, then: the receiving module is operative to receive a third key recovery text from the second device, the third key recovery text being a fourth key recovery text cryptographically transformed using the key; and the key determination module is operative to determine the key at least based on the secret, the third key recovery text and the fourth key recovery text.

39. The system according to any of claims 32, 35-37, wherein the determination of the test key includes concatenating the secret with another string. 000679

40. The system according to any of claims 32, 35-37, wherein the determination of the test key includes concatenating a value based on the secret with another string.

41. The system according to any of claims 32, 35-37, wherein the determination of the test key includes performing a function on the secret.

42. The system according to any of claims 28-41, further comprising a confirmation module to send a confirmation message to the second device confirming that the key has been determined.