Symmetric Encryption Key Generation Using Wireless Physical Layer Information Without Sharing Any Information Pertinent To The Key

Abstract

Symmetric keys are generated by an algorithm that uses the randomness from the wireless PHY layer to extract the keys. When used with reconfigurable antennas, the algorithm yields longer keys. By using the randomness from the wireless PHY layer, the algorithm solves the issue of secure information leakage to the wireless channel during key establishment phase. The algorithm also omits transmitting anything secure during this phase and prevents any intruder from obtaining information related to the key. This approach can automatically secure the communications over open wireless networks (those without authentication or encryption) or closed wireless networks using other methods of authentication.

Claims

1.-18. (canceled)

19. A method of generating symmetric encryption keys, comprising: for each data subcarrier of a plurality of data subcarriers at a transmitter or at a receiver, sending data wirelessly between the transmitter and the receiver to generate channel trend information (CTI) data, representative of channel state information (CSI) data, wherein CSI data are collected from forward and backward channels between the transmitter and the receiver, and wherein the forward and backward channels are not identical, determining, for each measurement of successive measurements taken from the collected CSI data, whether an increase or decrease in measurement magnitude from the previous measurement is observed, generating the CTI data by assigning a first value for an increase in measurement magnitude and a second value for a decrease in measurement magnitude; and using the CTI data, generated for each of the plurality of data subcarriers, to generate the symmetric encryption keys or as the symmetric encryption keys themselves.

20. The method of claim 19, further comprising: after generating the CTI data, for each data subcarrier of the plurality of data subcarriers, by assigning the first value for an increase in measurement magnitude and the second value for a decrease in measurement magnitude, determining the most agreed upon value of the first and second values; and using the most agreed upon value, determined for each of the subcarrier, to generate the symmetric encryption keys or as a key of the symmetric encryption keys themselves.

21. The method of claim 19, wherein at least one of the transmitter and receiver includes a reconfigurable antenna, wherein the reconfigurable antenna comprises at least one mode, further comprising generating CTI data for each data subcarrier of the plurality of data subcarriers and for each mode of each reconfigurable antenna, and using the generated CTI data to generate symmetric encryption keys or as the symmetric keys themselves.

22. The method of claim 19, wherein the data sent between the transmitter and the receiver to generate channel trend information (CTI) data comprises dummy data that does not contain important information from which symmetric key information may be learned.

23. The method of claim 19, further comprising initiating transmission using the generated symmetric keys, determining whether acknowledgements are not received or whether a non-acknowledgement has been received, and, if so, repeating the symmetric encryption key generation step until a valid symmetric key is established.

24. The method of claim 19, further comprising initiating transmission using the generated symmetric encryption keys, receiving acknowledgements for all packets from the transmitter that the receiver is able to decrypt, receiving non-acknowledgements for all packets from the transmitter that the receiver received and was unable to decrypt, determining whether acknowledgements or non-acknowledgements have been received, and, if so, repeating the symmetric encryption key generation step until a valid symmetric key is established.

25. A wireless access point that generates symmetric encryption keys for enabling wireless communications between a transmitter of the wireless access point and a receiver of a network node, comprising a memory that stores instructions for implementing a symmetric key generation algorithm and a processor that processes the stored instructions to implement the algorithm by performing the steps of: sending data wirelessly between the transmitter and the receiver to generate channel trend information representative of channel state information collected from forward and backward channels between the transmitter and receiver, wherein the forward and backward channels are not identical; repeating the process of sending data between the transmitter and receiver for each data subcarrier to generate channel trend information for each of a plurality of data subcarriers; determining, for each data subcarrier, for successive channel state information data collected from forward and backward channels, whether an increase or decrease in magnitude from the previous measurement is observed for each of a plurality of data points and, if so, assigning a first value for an increase in magnitude and a second value for a decrease in magnitude; and using the channel trend information for each data subcarrier to generate symmetric encryption keys or as the symmetric encryption keys themselves.

26. The wireless access point of claim 25, wherein the processor further executes instructions to perform the steps of collecting 2N measurements of channel state information to form the channel trend information, where N is an integer greater than 0 and repeating the steps of determining, for each data subcarrier, for successive channel state information data collected from forward and backward channels, whether an increase or decrease in magnitude from the previous measurement is observed for each data point and, if so, assigning a first value for an increase in magnitude and a second value for a decrease in magnitude to provide 2N−1 sets of the first values and the second values.

27. The wireless access point of claim 26, further comprising a pseudorandom generator, wherein the processor further executes instructions to perform the steps of determining the most agreed upon bit value and assigning the most agreed upon bit value as a key bit for the pseudorandom generator.

28. The wireless access point of claim 27, wherein the processor further executes instructions to perform the steps of repeating the steps of determining the most agreed upon bit value and assigning the most agreed upon bit value as the key bit for all of the data subcarriers to yield a key with length equal to a number of data subcarriers being used for the wireless transmission between the transmitter and the receiver.

29. The wireless access point of claim 25, wherein at least one of the transmitter and receiver includes a reconfigurable antenna, wherein the reconfigurable antenna comprises at least one mode, and wherein the processor further executes instructions to perform the steps of using the channel trend information for each data subcarrier for each mode of each reconfigurable antenna to generate symmetric encryption keys or as the symmetric encryption keys themselves.

30. The wireless access point of claim 26, wherein the data sent between the transmitter and the receiver comprises dummy data that does not contain important information from which symmetric key information may be learned.

31. The wireless access point of claim 26, wherein the processor further executes instructions to perform the steps of initiating transmission using the generated symmetric keys, determining whether acknowledgements are not received or a non-acknowledgement has been received at least three times back to back, and, if so, repeating the symmetric key generation step until a valid symmetric key is established.

32. The wireless access point of claim 26, wherein the processor further executes instructions to perform the steps of initiating transmission using the generated symmetric keys, receiving acknowledgements for all packets from the transmitter that the receiver is able to decrypt without issues, receiving non-acknowledgements for all packets from the transmitter that the receiver received and was unable to decrypt, determining whether acknowledgements or non-acknowledgements have been received at least three times back to back, and, if so, repeating the symmetric key generation step until a valid symmetric key is established.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0013] Exemplary embodiments of the invention will be described in conjunction with the associated figures, of which:

[0014] FIG. 1 illustrates a transmitter/receiver pair implementing Algorithm 1 for symmetric key generation.

[0015] FIG. 2 illustrates a transmitter/receiver pair using at least one reconfigurable antenna and implementing Algorithm 2 for symmetric key generation.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

[0016] Certain specific details are set forth in the following description with respect to FIGS. 1-2 to provide a thorough understanding of various embodiments of the invention. Certain well-known details are not set forth in the following disclosure, however, to avoid unnecessarily obscuring the various embodiments of the invention. Those of ordinary skill in the relevant art will understand that they can practice other embodiments of the invention without one or more of the details described below. Also, while various methods are described with reference to steps and sequences in the following disclosure, the description is intended to provide a clear implementation of embodiments of the invention, and the steps and sequences of steps should not be taken as required to practice the invention.

[0017] To explain the methodology of the invention, the inventors set up a design using two Software-defined Radio (SDR) nodes using Orthogonal Frequency Division Multiplexing (OFDM) based 802.11 WiFi packets, with 48 data subcarriers. In the prior art (see, for example, S. Mathur, et al., “Radio-telepathy: Extracting a secret key from an unauthenticated wireless channel,” in Proceedings of the 14th ACM International Conference on Mobile Computing and Networking, ser. MobiCom '08. New York, N.Y., USA: ACM, 2008, pp. 128-139. [Online]. Available: http://doi.acm.org/10.1145/1409944.1409960), normalization, averaging, and thresholding are used to generate a key. However, such prior art algorithms fail when there are differences between the forward and the backward channel caused by the environment that is independent from the communication link. In order to cancel out the effects of this difference, the inventors have developed an algorithm that looks at the general trend observed by the CSI measurements. The general trend data is referred to herein as Channel Trend Information (CTI). The inventors look at successive CSI data collected from forward and backward channels and play the game of “higher or lower?” for each data subcarrier. For each data point, where an increase in magnitude from the previous measurement is observed, the inventors assign a 1, and a 0 for the opposite case. Of course, other values besides 0 and 1 may be used for the same purpose. In order to make the algorithm more robust, the inventors collect 2N number of CSI measurements to form the CTI, where N is an integer greater than 0. The inventors then play the same game, which provides 2N−1 sets of ones and zeros (or other value pairs). The algorithm then looks for the most agreed upon bit to finalize its decision on assigning a 1 or a 0 (or two other predesignated values) as the key bit for a pseudorandom generator or other means for generating symmetric encryption keys or the output of the algorithm may be used as the symmetric encryption key itself. This is repeated for all of the data subcarriers, which yields a key with length equal to the number of data subcarriers being used in the wireless standard. FIG. 1 illustrates a transmitter/receiver pair implementing such an algorithm for symmetric key generation. Algorithm 1 below shows in pseudocode the scheme explained in this paragraph.

TABLE-US-00001 Algorithm 1 Extracting Symmetric Keys from Wireless PHY Layer  1: procedure generateSymmetricKey(N)  2: C ← length of data subcarriers  3: key[0 to C−1] ← 0  4: CTI[0 to 2N−1][0 to C−1] ← 0  5: start:  6: for i ← 0, 2N − 1 do /** Obtain CSI and save it to CTI array **/  7: send packet with dummy data to the other node  8: receive packet with dummy data from the other node  9: CTI[i][0 .fwdarw. C − 1] ← abs(CSI measurement) 10: for i ← 0,C − 1 do /** Play the game **/ 11: temp ← 0 12: for j ← 1, 2N − 1 do 13: if CTI┌j┐┌i┐ > CTI┌j − 1┐┌i┐ then temp temp +1 14: if temp >= N then key[i] ← 1 15: elsekey[i] ← 0 16: checkKeyStrength(key) /** Ensure key is strong **/ 17: if key is strong then 18: return key 19: else 20: go to start

[0018] The scheme defined in Algorithm 1 provides more robust symmetric keys. However, Algorithm 1 matches the data subcarrier count to the length of the key. In the case of WiFi OFDM packets, only 48 data subcarriers are present. Algorithm 1 would then only be able to provide a key of 48-bits length, which is too short to provide strong encryption. Such a key could be vulnerable to brute force attacks.

[0019] In order to provide a longer key, the inventors also propose to leverage reconfigurable antennas (RA), where the different radiation patterns obtained by the multiple available modes on the antenna allow the inventors to observe multiple realizations of the wireless channel. The inventors then concatenate these realizations to provide a longer key that is not repeated. In the past, concatenating multiple CSI measurements from an omnidirectional antenna has been tried and, due to the repeated nature of the resulting key, a loss in randomness was observed. Algorithm 2 shows pseudocode explaining an extension to Algorithm 1 using Reconfigurable Antennas. FIG. 2 illustrates a transmitter/receiver pair implementing Algorithm 2 for symmetric key generation.

TABLE-US-00002 Algorithm 2 Extracting Enhanced Symmetric Keys from Wireless PHY Layer using Reconfigurable Antennas  1: procedure generateSymmetricKeyWithRA(N,M)  2: M defined as number of modes available on the RA  3: C ← length of data subcarriers  4: key[0 to M*C−1] ← 0  5: CTI[0 to 2N−1][0 to M*C−1] ← 0  6: start:  7: for i ← 0, 2N − 1 do /** Obtain CSI and save it to CTI array **/  8: for j ← 0,M − 1 do /** for each mode of the reconfigurable antenna **/  9: send packet with dummy data to the other node 10: receive packet with dummy data from the other node 11: CTI[i][0 + j * C .fwdarw. C − 1+ j * C] ← abs(CSI measurement) 12: for i ← 0,M * C − 1 do /** Play the game **/ 13: temp ← 0 14: for j ← 1, 2N − 1 do 15: if CTI[j][i] > CTI[j − 1][i] then temp ← temp +1 16: if temp >= N then key[i] ← 1 17: elsekey[i] ← 0 18: checkKeyStrength(key) /** Ensure key is strong **/ 19: if key is strong then 20: return key 21: else 22: go to start

[0020] Algorithm 2 benefits from the increased number of modes available on a given Reconfigurable Antenna. By way of example, for an antenna with 7 modes, applying Algorithm 2 above with this antenna would increase the key length to 7*48=336 bits. The output of the algorithm could be used as the symmetric keys themselves or applied to a pseudorandom generator or other means for generating symmetric encryption keys.

[0021] In order to use the above algorithms in a practical manner, the inventors further propose an overall network protocol as described in Algorithms 3 and 4 below. The purpose of these algorithms is to demonstrate how a new wireless user joining a wireless network can start their communication in a secure manner. The inventors show the functionality intended for both the receiver and the transmitter for clarity. The inventors propose to start sending dummy data, which could be any wireless packet that does not contain important information. The inventors leave the freedom to select the contents of these packets to Wireless card or access point developers. If the number of packets sent is a vital statistic (e.g. for bandwidth limited customers in cellular data communications), it may be allowed to use these initial packets for actual transmission of data. However, it must be done carefully by not releasing any sensitive information.

[0022] After establishing the key by using Algorithm 1 or Algorithm 2 for the case of reconfigurable antenna supported wireless cards, the secure transmission begins. Similar to Transmission Control Protocol (TCP)'s acknowledgements (ACKs), the protocol using the above algorithms keeps track of the ACKs and determines if the receiving end is able to understand the transmitter. If the ACKs are flowing without any issues, the inventors determine that the symmetric key was established without any problems and is now a valid key. However, if the ACKs are not received or a non-acknowledgement (NACK) was transmitted three times back to back, it is determined that the key generated was bad and the key generation step is repeated. This process is repeated until a valid key is established. The reason for repeating the transmission three times is because there is no need to regenerate the key due to a lost packet, which can happen in congested networks. The inventors try again to ensure the packet is not being acknowledged because of a key that was not generated as a symmetric key. Algorithm 3 summarizes this protocol for the transmitter.

TABLE-US-00003 Algorithm 3 Network Protocol using Symmetric Keys from Wireless PHY Layer (Transmitter)  1: N ∈ Z > 0  2: generate key:  3: if wireless card equipped with RA then  4: M ← number of modes RA supports  5: key = generateSymmetricKeyW ithRA(N, M)  6: else  7: key = generateSymmetricKey(N)  8: communicate:  9: while 1 do 10: retryCount ← 0 11: secureData = encryptData(data, key) 12: send(secureData) 13: waitFor(ACK) 14: retry: 15: if ACK not received or NACK received then 16: if retryCount < 2 then /** try to repeat it 3 times with a random back off time **/ 17: wait(randomTime) 18: send(secureData) 19: waitFor(ACK) 20: retryCount ++ 21: go to retry 22: else 23: go to generate key 24: if key expired then /** generate a new key when an old key is detected **/ 25: go to generate key

[0023] Algorithm 4 demonstrates the functionality of the receiving end of the wireless communication. We train the receiver to send ACKs for all the packets it is able to decrypt without issues (e.g. checksum passes, or the Application layer reports valid data). For all packets, it receives and is not able to decrypt, it sends a NACK to indicate it received the packet but was unable to decrypt the packet. This can happen due to multiple reasons including a packet that was corrupted in-flight because of excessive interference. A repeated transmission with a short back off time might fix this error. Therefore, the transmitter treats the ACKs and NACKs the same. If three NACKs were sent back to back, a new key generation is triggered.

TABLE-US-00004 Algorithm 4 Network Protocol using Symmetric Keys from Wireless PHY Layer (Receiver)  1: N ∈ Z > 0  2: generate key:  3: if wireless card equipped with RA then  4: M ← number of modes RA supports  5: key = generateSymmetricKeyW ithRA(N, M)  6: else  7: key = generateSymmetricKey(N)  8: communicate:  9: while 1 do 10: secureData = receive( ) 11: data = decryptData(secureData, key) 12: if data is meaningful then 13: send(ACK) 14: else 15: send(NACK)

[0024] The algorithms described herein can be used in any of a number of devices that use symmetric encryption keys. For example, the algorithms described herein can be incorporated into wireless access points and the CSI in the local network can be used to automatically generate symmetric encryption keys without the user having to manually enter encryption keys. The symmetric encryption keys would be secure as they are based on the local environment, which is virtually impossible to replicate remotely. This approach can automatically secure the communications over open wireless networks (those without authentication or encryption) or closed wireless networks using other methods of authentication.

[0025] For example, in the case of multiple users connecting to an open network in a coffee shop, the algorithm would automatically generate unique symmetric encryption keys for each user and start securing their wireless communications. This automatically secures the mentioned open wireless network. At regular intervals and/or when a user moves (changing the environment), the algorithm regenerates the symmetric encryption keys to provide continued security without any interruption to the user.

[0026] It will be appreciated that the algorithms and methods described herein may be implemented in software that operates on a processor in a wireless access point such as those implemented in wireless routers, base stations, wireless cards, and the like, where the processor executes instructions stored in a memory component. The processor may include a standardized processor, a specialized processor, a microprocessor, or the like. The processor may execute instructions including, for example, instructions for implementing the method as described herein. On the other hand, the memory component stores the instructions that may be executed by the processor. The memory component may include a tangible computer readable storage medium in the form of volatile and/or nonvolatile memory such as random access memory (RAM), read only memory (ROM), cache, flash memory, a hard disk, or any other suitable storage component. In one embodiment, the memory component may be a separate component in communication with a processor, while in another embodiment, the memory component may be integrated into the processor. Such non-transitory memory components may be used as a computer readable storage device to store the instructions for implementing the methods and software features described herein.

[0027] Those skilled in the art also will readily appreciate that many additional modifications and scenarios are possible in the exemplary embodiment without materially departing from the novel teachings and advantages of the invention. Accordingly, any such modifications are intended to be included within the scope of this invention as defined by the following exemplary claims.