US8774410B1

Movatterモバイル変換

Info

Publication number: US8774410B1
Application number: US13/336,849
Authority: US
Inventors: Ari Juels
Original assignee: EMC Corp
Current assignee: EMC Corp
Priority date: 2011-12-23
Filing date: 2011-12-23
Publication date: 2014-07-08

Abstract

A first cryptographic device generates plaintext information characterizing at least one key or other secret value associated with that device. The first cryptographic device releases portions of the plaintext information to a second cryptographic device over respective time intervals. The portions of the plaintext information are configured by the first cryptographic device such that the second cryptographic device must receive at least a designated minimum number of the portions in order to determine the secret value from those received portions. By way of example, the portions of the plaintext information may be wirelessly transmitted by the first cryptographic device, such that the second cryptographic device must be in wireless contact with the first cryptographic device for at least a designated minimum amount of time in order to receive the designated minimum number of portions required to determine the secret value.

Description

FIELD

The field relates generally to cryptography, and more particularly to pairing protocols, key management protocols or other techniques that involve sharing of secret values between cryptographic devices in a communication system.

BACKGROUND

In many applications, it is desirable for one computer, server, mobile telephone, RFID tag or other type of cryptographic device to pair with, authenticate or otherwise share secrets such as keys with another cryptographic device. Unfortunately, such arrangements can be problematic when carried out using existing techniques.

For example, a conventional pairing protocol that relies on breakable ciphers is disclosed in G. T. Amariucai et al., “An Automatic, Time-Based, Secure Pairing Protocol for Passive RFID,” RFIDSec, 2011, which is incorporated by reference herein. This known pairing protocol is referred to as an “adopted pet” or AP protocol. In the AP protocol, an RFID tag gradually leaks a secret key, such that a reader in proximity to the tag for an extended period of time can learn the secret key. However, a reader that receives tag outputs over only limited-duration intervals of time cannot learn the secret key. Thus, for instance, a tag in a user's home might pair with a reader there overnight, while a maliciously operated reader in a commuter bus would not have sufficient time to harvest the secret key from the tag.

The AP protocol leaks the secret key through a key stream generated by a cryptographically weak pseudorandom number generator (PRNG), such as a linear-feedback shift register (LFSR), seeded by the secret key. By harvesting enough contiguous key stream data, a reader can break the PRNG and recover the secret key. However, this reliance on breakable ciphers has a number of significant drawbacks. For example, breakable ciphers can be difficult to implement in practice, and their security level is difficult to calibrate. Also, requiring the use of breakable ciphers means that the AP protocol will not work with strong, standard ciphers such as the Advanced Encryption Standard (AES). Furthermore, the AP protocol does not permit a flexible range of security policies.

SUMMARY

Illustrative embodiments of the present invention provide improved sharing of keys or other secret values between cryptographic devices without requiring the use of breakable ciphers as in the above-described conventional AP protocol.

In one embodiment, a first cryptographic device generates plaintext information characterizing at least one key or other secret value associated with that device. The first cryptographic device releases portions of the plaintext information to a second cryptographic device over respective time intervals. The portions of the plaintext information are configured by the first cryptographic device such that the second cryptographic device must receive at least a designated minimum number of the portions in order to determine the secret value from those received portions.

By way of example, the portions of the plaintext information may be wirelessly transmitted by the first cryptographic device, such that the second cryptographic device must be in wireless contact with the first cryptographic device for at least a designated minimum amount of time in order to receive the designated minimum number of portions required to determine the secret value.

Accordingly, in one or more of the illustrative embodiments, secret shares may be disclosed using controlled release of over a plaintext channel, in a manner that is compatible with AES and other strong, standard ciphers, while also permitting a flexible range of security policies.

These and other features and advantages of embodiments of the present invention will become more readily apparent from the accompanying drawings and the following detailed description.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a simplified block diagram of an authentication system in an illustrative embodiment of the invention.

FIG. 2 is a more detailed block diagram of an authentication system comprising multiple cryptographic devices in an illustrative embodiment of the invention.

FIG. 3 is a flow diagram of a secret sharing process implemented in the authentication system ofFIG. 1 orFIG. 2.

FIGS. 4 and 5 show exemplary communication systems that may incorporate the authentication system ofFIG. 1 orFIG. 2.

DETAILED DESCRIPTION

Illustrative embodiments of the present invention will be described herein with reference to exemplary cryptographic devices and associated authentication and communication systems. It is to be appreciated, however, that embodiments of the invention are not restricted to use with the particular illustrative device and system configurations shown.

The term “cryptographic device” as used herein is intended to be construed broadly, so as encompass, for example, a computer, server, mobile telephone, RFID tag or reader, authentication token or other type of processing device configured to pair with, authenticate or otherwise share secrets such as keys with another cryptographic device.

FIG. 1 shows a simplified view of anauthentication system100 in an illustrative embodiment of the invention. In thesystem100, first and second cryptographic devices are respectively denoted assender102 andreceiver104. These devices communicate over achannel105. An adversary106 initiates security attacks in thesystem100 at least in part by accessingchannel105.

In thesystem100, a key or other secret value may be shared by thesender102 andreceiver104 by controlled release of plaintext information by thesender102. More particularly, a secret value in the present embodiment may be made apparent by thesender102 to thereceiver104 by the sender generating plaintext information characterizing the secret value, and releasing portions of the plaintext information to the receiver over respective time intervals. The portions of the plaintext information are configured by the sender such that the receiver must receive at least a designated minimum number of the portions in order to determine the secret value from those received portions. Theadversary106 similarly must receive the designated minimum number of the portions in order to determine the secret value, and as will be described in greater detail below, thesystem100 is configured such that it is particularly difficult for the adversary to receive the designated minimum number of the portions. The plaintext information may comprise, for example, any type of information characterizing the secret value and transmitted over a plaintext channel and thus in an unencrypted format.

Thesender102 pairs with or otherwise authenticates thereceiver104 only if the receiver is able to determine the secret value, thereby demonstrating receipt of the designated minimum number of the portions of the plaintext information. A wide variety of conventional pairing protocols or other authentication processes may be implemented in thesystem100 based on keys or other shared secret values exchanged by controlled release of plaintext information in the manner disclosed herein. Examples of such authentication processes are disclosed in A. J. Menezes et al., Handbook of Applied Cryptography, CRC Press, 1997, which is incorporated by reference herein. Such processes, being well known to those skilled in the art, will not be described in further detail herein. It is to be appreciated that embodiments of the present invention do not require the use of any particular type of pairing protocol or other authentication process using shared secrets.

FIG. 2 shows an exemplary authentication system corresponding generally to an implementation ofsystem100 in whichsender102 comprises a first cryptographic device200-1 andreceiver104 comprises a second cryptographic device200-2. In this embodiment, the cryptographic devices200-1 and200-2 communicate with one another over awireless channel203 using respective antennas204-1 and204-2 and respective interface circuitry206-1 and206-2. Each of the cryptographic devices200 further comprises a processor210 coupled to a memory212. The processor210-1 in device200-1 is also coupled to other device elements including, by way of example, akey generator214, acoder215 and atiming control element216. Similarly, the processor210-2 in device200-2 is also coupled to a number of other device elements, illustratively including akey reconstructor224, adecoder225 and atiming control element226.

The first cryptographic device200-1 generates a secret value in the form of a key using thekey generator214. For example, the key may be a particular key from a set of keys generated by thekey generator214. More particularly, the set of keys may comprise a set of k-symbol keys K₁, K₂, . . . K_Mthat are generated sequentially over time by the first cryptographic device, where the symbols are drawn from a set S. Plaintext information may be generated for a given one of the keys K_i, i=1, 2, . . . M, by computing a (k,n,d)-erasure code over K_iincoder215 in order to generate plaintext information for key K_iin the form of a set of n symbols, where n>k. Thetiming control element216 is utilized to define time intervals over which respective portions of the plaintext information are released. For example, a different subset of the set of n symbols may be released in each of the time intervals. The second cryptographic device200-2 must receive at least k+1 symbols out of the n symbols released by the first cryptographic device in order to determine the key K_i.

Thewireless channel203 between the cryptographic devices200-1 and200-2 in the present embodiment may be configured to utilize a short-range wireless communication protocol, such as Bluetooth, ZigBee, IEEE 802.11, near field communication (NFC), RFID, wireless sensors, etc. It is to be appreciated, however, that other types of wireless communication protocols may be used in other embodiments.

The above-noted controlled release of plaintext information is implemented in this embodiment by wirelessly transmitting the portions of the plaintext information from the first cryptographic device200-1 to the second cryptographic device200-2 over thewireless channel203.

Such an arrangement ensures that the second cryptographic device200-2 must be in wireless contact with the first cryptographic device200-1 for at least a designated minimum amount of time in order to receive the designated minimum number of portions required to determine the secret value. For example, the second cryptographic device may be required to remain in continuous radio contact with the first cryptographic device for the designated minimum amount of time, or may be required to have a sufficient number of non-continuous radio contacts that collectively meet the designated minimum amount of time. Numerous other alternatives for satisfying radio contact for the designated minimum amount of time may be used.

This type of required minimum duration of radio contact is particularly difficult for theadversary106 to achieve, and therefore provides security within thesystem100. Thus, as in the conventional AP protocol previously described, a tag in a user's home would be able to pair with a reader there overnight, while a maliciously operated reader in a commuter bus would not have sufficient time to harvest the secret key from the tag. However, this functionality may be achieved in the present embodiment over a plaintext channel, in a manner that is compatible with AES and other strong, standard ciphers, while also permitting a flexible range of security policies. Accordingly, the deficiencies of the conventional AP protocol are avoided in this embodiment.

As a more particular example of an erasure code that may be used in one or more embodiments of the invention, the erasure code may comprise a (k,n,d)=(223,255,32) Reed Solomon (RS) code. Other examples of codes suitable for use in embodiments of the invention include Bose Chaudhuri Hocquenghem (BCH) codes.

Other embodiments of the invention may be configured to operate without the use of an erasure code or other type of code. For example, the first cryptographic device200-1 could transmit symbols from a cryptographic key, and also transmit a value derived from the key, e.g., a digest. The second cryptographic device200-2 would utilize the digest and a minimum number of received symbols to recover missing symbols of the key. Such an arrangement involves key transmission rather than ciphertext transmission as in the above-described AP protocol.

As another example, the first cryptographic device200-1 could transmit arbitrary (e.g., random) symbols. The second cryptographic device200-2, rather than recovering a key as in the previous example, would instead need to prove possession of a designated minimum fraction of the symbols. It could, for example, transmit back to the first device a ciphertext on received symbols, or a digest thereof, along with symbol indices. The ciphertext may be digitally signed with respect to an accompanying public key PK. The first device, on verifying that the symbols are correct and of sufficient number, would then accept the holder of the corresponding private key SK as an authentic receiver.

It should be emphasized that the above are only examples, and numerous other arrangements involving controlled release of plaintext information may be utilized in other embodiments.

Cryptographic device elements such as interface circuitry206, processor210, memory212 and one or more of the other functional modules of the cryptographic devices200 may be implemented in whole or in part in the form of one or more integrated circuits.

By way of example, the interface circuitry206 may comprise conventional transceivers of a type well known in the art, and the processor210 may comprise a microprocessor, a microcontroller, an application-specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other type of processing circuitry, as well as portions or combinations of such circuitry elements.

The memory212 may be viewed as an example of what is more generally referred to herein as a “computer program product” having executable computer program code embodied therein. Such a memory may comprise electronic memory such as random access memory (RAM), read-only memory (ROM) or other types of memory, in any combination. The computer program code embodied in the memory212 when executed by the processor210 causes the corresponding cryptographic device to perform functions associated with controlled release of plaintext information. One skilled in the art would be readily able to implement such software given the teachings provided herein. Other examples of computer program products embodying aspects of the invention may include, for example, optical or magnetic disks, or other storage devices, or suitable portions or combinations of such devices. In addition to storing computer program code, such storage devices will also generally be used to store data within the authentication system.

Other device elements such askey generator214,coder215 andtiming control element216 in first cryptographic device200-1 andkey reconstructor224,decoder225 andtiming control element226 in second cryptographic device200-2 may be implemented at least in part in the form of software stored in the corresponding memory212 and executed by the corresponding processor210. One or more of these elements alternatively may be implemented using a combination of hardware, software and firmware.

FIG. 3 shows one example of a secret sharing process which implements controlled release of plaintext information in an illustrative embodiment of the invention. This process is implemented by the first and second cryptographic devices200-1 and200-2 ofFIG. 2, which correspond to therespective sender102 andreceiver104 ofFIG. 1. The secret sharing process as shown inFIG. 3 illustratively includessteps300 through308, which may be implemented at least in part utilizing cryptographic device processor and memory elements of the type previously described.

Instep300, the first cryptographic device200-1 generates plaintext information characterizing at least one secret value associated that device. For example, the secret value may comprise a key generated by thekey generator214, and the plaintext information may be generated by applying an erasure code to that key using thecoder215.

Instep302, the first cryptographic device200-1 releases portions of the plaintext information to the second cryptographic device200-2 over respective time intervals. These portions are transmitted overwireless channel203 for time intervals defined by thetiming control element216. The process may move fromstep302 back to step300 so as to be repeated for one or more additional secret values.

Instep304, the second cryptographic device200-2 determines if it has received the designated minimum number of portions of the released plaintext information that would be required in order to reconstruct the secret value. Thetiming control element226 may be used to coordinate the time intervals utilized by second cryptographic device with those utilized by the first cryptographic device to control release of the portions of the plaintext information. If the designated minimum number of portions has been received, the process moves to step306, and otherwise the process moves to step308. The determination instep304 may be implicit in other embodiments. For example, it may be based on attempts by the second cryptographic device to reconstruct the secret value from particular numbers of received portions. If a given such attempt is successful, the second cryptographic device may assume that the requisite number of portions has been received.

Instep306, the second cryptographic device200-2 is able to reconstruct the secret value from the designated minimum number of portions. This reconstruction may involve, for example, decoding the above-noted erasure code indecoder225, and reconstructing the key inkey reconstructor224. The second cryptographic device may of course receive more than the designated minimum number of portions, and may utilize all the received portions in reconstructing the secret value.

Instep308, the second cryptographic device200-2 is unable to reconstruct the secret value from the designated minimum number of portions, because it has not received the designated minimum number of portions. The process then returns to step300 as indicated, and as noted above the process may be repeated for additional secret values.

As mentioned previously, in one or more embodiments the secret values may comprise a set of k-symbol keys K₁, K₂, . . . K_Mgenerated sequentially over time by thekey generator214 of the first cryptographic device200-1, where the symbols are drawn from a set S. For each of the keys K_i, i=1, 2, . . . M, the first cryptographic device utilizescoder215 to compute a (k,n,d)-erasure code over K_iwhose output is a set of n>k symbols, although it should be understood that in other embodiments, other types of codes can be used in place of the computation of the (k,n,d)-erasure code over K_i.

The first cryptographic device200-1 may pair with or otherwise authenticate the second cryptographic device200-2 only if the second cryptographic device is able to determine the secret value. The second cryptographic device may demonstrate its knowledge of the secret value to the first cryptographic device using any of a number of known techniques for proving possession of a secret value.

As indicated previously, the process as shown inFIG. 3 may be repeated periodically in order to provide multiple shared secret opportunities over time.

Other embodiments may use alternative process flows. For example, process steps indicated as being performed serially inFIG. 3 may be performed at least in part in parallel with one another. Also, one or more steps may be combined, as in the above-described alternative arrangement in which the determination ofstep304 is made implicit in attempted reconstructions in

steps

306 and308.

In the above embodiments, rather than revealing secret values via breakable ciphers as in the AP protocol, secret values are disclosed over a plaintext channel through controlled release of plaintext information. Such arrangements support a broader range of security policies and are compatible with any cryptographic system, including those based on AES and other strong, standard ciphers.

Accordingly, theauthentication system100 can support a broad range of access control policies through the use of different key update techniques. For example, the keys may be invariant, such that K₁=K₂= . . . =K_M. Alternatively, each key K_imay be a deterministic function of one or more earlier keys. In such arrangements, once the second cryptographic device200-2 has acquired sufficiently many keys of the first cryptographic device200-1, it will be able to derive additional keys of the first cryptographic device.

As another example, the keys may be generated independently at random. In an arrangement of this type, the second cryptographic device200-2 must maintain persistent contact with the first cryptographic device200-1 to ensure its knowledge of the current key set of the first cryptographic device.

As yet another example, the keys may be partially randomized, such that a portion of each key K_iis a fresh random value while another portion is invariant or deterministic. In an arrangement of this type, the rate at which the second cryptographic device200-2 must receive symbols initially to learn the keys of the first cryptographic device200-1 will be lower than the rate at which it must later receive symbols to learn subsequent keys of the first cryptographic device. Alternatively, the second cryptographic device might acquire one of the keys of the first cryptographic device through an alternative channel, e.g., a contact channel, and maintain its knowledge of the first cryptographic device keys through periodic sampling of outputs of that device. Thus, ownership can be established in a straightforward manner, and ownership transfer would occur naturally as a result of extended separation between the two devices.

An authentication system of the type described above in conjunction withFIGS. 1-3 may be implemented in a wide variety of different applications. Two exemplary communication system applications that may incorporate secret sharing via controlled release of plaintext information will now be described with reference toFIGS. 4 and 5.

Referring initially toFIG. 4, acommunication system400 comprises a plurality of mobile telephones402-1 and402-2 and computers404-1,404-2 and404-3, configured to communicate with one another over a network404. The network404 may comprise, for example, a global computer network such as the Internet, a wide area network (WAN), a local area network (LAN), a satellite network, a telephone or cable network, a cellular network, a wireless network such as WiFi or WiMAX, or various portions or combinations of these and other types of networks.

Any two or more of the devices402 and404 may correspond to cryptographic devices200-1 and200-2 and accordingly are configured to implement a secret sharing process via controlled release of plaintext information as previously described. Thus, for example, in the case of consumer goods, a user associated with one of the devices might obtain a registration key for another one of the devices provided that the latter device has been in radio contact with the former device for a minimum amount of time. The time intervals associated with the controlled release of plaintext information may be configured in a straightforward manner to enforce this minimum amount of time.

It should be noted in this regard that a single cryptographic device may be configured both to release portions of plaintext information and to receive such portions released by another cryptographic device. Thus, a given one of the devices402 or404 may incorporate

modules

214,215 and216 as well as

modules

224,225 and226.

FIG. 5 shows anotherexemplary communication system500 in an illustrative embodiment of the invention. In this embodiment, thesystem500 is an RFID system comprising RFID tags502-1,502-2, . . .502-N, areader504, and anauthenticator506. One or more of the RFID tags502 may correspond to the first cryptographic device200-1, and thereader504, possibly in combination with theauthenticator506, may correspond to the second cryptographic device200-2. Theauthenticator506 may represent, for example, a back-end authentication server configured to authenticate secret values supplied to it by one or more of the RFID tags302 via thereader504. Thesystem500 may be configured such that a given one of the RFID tags502 might allow its contents to be read or otherwise accessed only by a reader that has been in radio contact with the tag for a minimum period of time, e.g., five minutes. Such a security policy would eliminate many casual scanning attacks, while making key management relatively simple.

It is to be appreciated that the techniques disclosed herein can be implemented in numerous other applications. For example, in other embodiments, the first and second cryptographic devices may comprise an authentication token and an authentication server, respectively, or may comprise an authentication token and a computer or other host device, respectively. In such arrangements, the authentication token may comprise a time-synchronous authentication token such as the RSA SecurID® user authentication token, commercially available from RSA, The Security Division of EMC Corporation, of Bedford, Mass., U.S.A.

It should again be emphasized that the above-described embodiments of the invention are presented for purposes of illustration only. Many variations and other alternative embodiments may be used. For example, the techniques are applicable to a wide variety of other types of cryptographic devices that can benefit from secret sharing over plaintext channels. Also, the particular configuration of system and device elements shown inFIGS. 1,2,4 and5, and the secret sharing process shown inFIG. 3, can be varied in other embodiments. Moreover, the various simplifying assumptions made above in the course of describing the illustrative embodiments should also be viewed as exemplary rather than as requirements or limitations of the invention. Numerous other alternative embodiments within the scope of the appended claims will be readily apparent to those skilled in the art.

Claims

What is claimed is:

1. A method comprising the steps of:

generating plaintext information characterizing at least one secret value associated with a first cryptographic device; and

releasing portions of the plaintext information from the first cryptographic device to a second cryptographic device over respective time intervals;

wherein the portions of the plaintext information are configured by the first cryptographic device such that the second cryptographic device must receive at least a designated minimum number of the portions in order to determine the secret value from those received portions; and

wherein the step of generating plaintext information comprises:

obtaining a key comprising at least a portion of the secret value;

computing an erasure code over the key to generate a set of symbols; and

utilizing the set of symbols as at least part of the plaintext information.

2. The method ofclaim 1 further comprising the step of permitting the first cryptographic device to authenticate the second cryptographic device only if the second cryptographic device is able to determine the secret value.

3. The method ofclaim 1 wherein the releasing step further comprises wirelessly transmitting the portions of the plaintext information.

4. A method comprising the steps of:

wherein the portions of the plaintext information are configured by the first cryptographic device such that the second cryptographic device must receive at least a designated minimum number of the portions in order to determine the secret value from those received portions;

wherein the releasing step further comprises wirelessly transmitting the portions of the plaintext information; and

wherein the second cryptographic device must be in wireless contact with the first cryptographic device for at least a designated minimum amount of time in order to receive the designated minimum number of portions required to determine the secret value.

5. The method ofclaim 1 wherein the secret value comprises a particular key from a set of keys generated by the first cryptographic device.

6. The method ofclaim 5 wherein the set of keys comprises a set of k-symbol keys K₁, K₂, . . . K_Mthat are generated sequentially over time by the first cryptographic device.

7. The method ofclaim 6 wherein the step of generating plaintext information comprises computing for a given one of the keys K_i, i=1, 2, . . . M, a (k,n,d)-erasure code over K_ito generate a set of n symbols, where n>k, the plaintext information for key K_icomprising the set of n symbols.

8. The method ofclaim 7 wherein the step of releasing portions of the plaintext information over respective time intervals comprises releasing a different subset of the set of n symbols in each of the time intervals.

9. The method ofclaim 8 wherein the second cryptographic device must receive at least k+1 symbols out of the n symbols released by the first cryptographic device in order to determine the key K_i.

10. The method ofclaim 5 wherein the keys of the set are invariant.

11. A method comprising the steps of:

wherein the secret value comprises a particular key from a set of keys generated by the first cryptographic device; and

wherein at least one of the keys of the set is generated as a deterministic function of one or more previously-generated keys of the set, such that after the second cryptographic device has acquired a sufficient number of keys of the set, it can determine one or more additional keys of the set.

12. The method ofclaim 5 wherein the keys of the set are generated independently at random.

13. A method comprising the steps of:

wherein the secret value comprises a particular key from a set of keys generated by the first cryptographic device; and wherein the keys of the set are partially randomized, such that one portion of each key comprises a fresh random value while another portion is invariant or deterministic.

14. The method ofclaim 5 wherein portions of the plaintext information are released to the second cryptographic device over one channel and at least one of the keys of the set is provided to the second cryptographic device through another channel.

15. A computer program product comprising a processor-readable storage medium having embodied therein one or more software programs, wherein the one or more software programs when executed by a processor cause the steps of the method ofclaim 1 to be performed.

16. An apparatus comprising:

a first cryptographic device comprising a processor coupled to a memory;

the memory storing at least one secret value;

the first cryptographic device being configured under control of the processor to generate plaintext information characterizing the secret value, and to release portions of the plaintext information to a second cryptographic device over respective time intervals;

wherein, in generating the plaintext information, the first cryptographic device is configured under control of the processor to:

obtain a key comprising at least a portion of the secret value;

compute an erasure code over the key to generate a set of symbols; and

utilize the set of symbols as at least part of the plaintext information.

17. The apparatus ofclaim 16 wherein the processor permits the first cryptographic device to authenticate the second cryptographic device only if the second cryptographic device is able to determine the secret value.

18. The apparatus ofclaim 16 wherein the first cryptographic device further comprises a wireless transmitter, wherein the portions of the plaintext information are released by transmitting those portions using the wireless transmitter, and wherein the second cryptographic device must be in wireless contact with the first cryptographic device for at least a designated minimum amount of time in order to receive the designated minimum number of portions required to determine the secret value.

19. The apparatus ofclaim 16 wherein a given one of the first and second cryptographic devices comprises one of a computer and a mobile telephone.

20. The apparatus ofclaim 16 wherein the first cryptographic device comprises an RFID tag and the second cryptographic device comprises an RFID tag reader.