Robust key generation from signal envelopes in wireless networks

ABSTRACT

The broadcast nature of a wireless link provides a natural eavesdropping and intervention capability to an adversary. Thus, securing a wireless link is essential to the security of a wireless network, and key generation algorithms are necessary for securing wireless links. However, traditional key agreement algorithms can be very costly in many settings, e.g. in wireless ad-hoc networks, since they consume scarce resources such as bandwidth and battery power.

Traditional key agreement algorithms are not suitable for wireless ad-hoc networks since they consume scarce resources such as bandwidth and battery power.

This paper presents a novel approach that couples the physical layer characteristics of wireless networks with key generation algorithms. It is based on the wireless communication phenomenon known as the principle of reciprocity which states that in the absence of interference both transmitter and receiver experience the same signal envelope. The key-observation here is that the signal envelope information can provide to the two transceivers two correlated random sources that provide sufficient amounts of entropy which can be used to extract a cryptographic key. In contrast, it is virtually impossible for a third party, which is not located at one of the transceiver's position, to obtain or predict the exact envelope; thus retrieve the key. Since in the presence of interference strict reciprocity property can not be maintained; our methodology is based on detecting deep fades to extract correlated bitstrings. In particular, we show how a pair of transceivers can reconcile such bitstrings and finally flatten their distribution to reach key agreement. In our constructions we use cryptographic tools related to randomness extraction and information reconciliation. We introduce "secure fuzzy information reconciliators" a tool that enables us to describe robust key generation systems in our setting. Finally we provide a computational study that presents a simulation of a wireless channel that demonstrates the feasibility of our approach and justifies the assumptions made in our analysis.

REFERENCES

• 1: Y. Aumann, Y. Z. Ding, M. O. Rabin, Everlasting security in the bounded storage model, IEEE Transactions on Information Theory 48(6): 1668--1680(2002)
• 2: T. Aono, K. Higuchi, T. Ohira, B. Komiyama and H.Sasaoka, "Wireless secret key generation exploiting reactance-domain scalar response of multipath fading channels," IEEE Transactions on Antennas and Propagation, vol(53), no(11), pages: 3776--3784, Nov. 2005.
• 3: R Blom, An optimal class of symmetric key generation systems, Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, p.335-338, December 1985, Paris, France
• 4: Carlo Blundo , Alfredo De Santis , Amir Herzberg , Shay Kutten , Ugo Vaccaro , Moti Yung, Perfectly-Secure Key Distribution for Dynamic Conferences, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.471-486, August 16-20, 1992
• 5: W. F. Bodtmann and H. W. Arnold, "Fade-Duration Statistics of a Rayleigh Distributed Wave," IEEE Transactions on Communications, vol. COM-30, No. 3, p. 549--553, Mar 1982.
• 6: Christian Cachin , Ueli M. Maurer, Unconditional Security Against Memory-Bounded Adversaries, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.292-306, August 17-21, 1997
• 7: S. A. Camtepe, B. Yener, Key Distribution Mechanisms for Wireless Sensor Networks: a Survey, TR-05-07 Rensselaer Polytechnic Institute, Computer Science Department, March 2005.
• 8: Seyit A. Çamtepe , Bülent Yener, Combinatorial design of key distribution mechanisms for wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.346-358, April 2007 [doi>10.1109/TNET.2007.892879]
• 9: Seyit A. Çamtepe , Bülent Yener, Combinatorial design of key distribution mechanisms for wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.346-358, April 2007 [doi>10.1109/TNET.2007.892879]
• 10: S. A. Camtepe, B. Yener and M. Yung, "Expander graph based key distribution mechanisms in wireless sensor networks," IEEE Int. Conf. on Commun., 2006.
• 11: L. Carter and M. Wegman, Universal Hash Functions, J. Comp. and Syst. Sci. 18(2):143--154, 1979.
• 12: Haowen Chan , Adrian Perrig , Dawn Song, Random Key Predistribution Schemes for Sensor Networks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.197, May 11-14, 2003
• 13: I. Csiszár and J. Körner. Broadcast channels with confidential messages. IEEE Transactions on Information Theory, 22(6):644--654, 1978.
• 14: Y. Dodis, L. Reyzin and A. Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. In Advances in Cryptology - EUROCRYPT 2004.
• 15: Y. Dodis and A. Smith. Entropic security and the encryption of highentropy messages. In J. Kilian, editor. First Theory of Cryptography Conference - TCC 2005, volume 3378 of LNCS. Springer-Verlag, 2005.
• 16: Y. Dodis, On Extractors, Error-Correction and Hiding All Partial Information, Information Theory Workshop (ITW), October 2005.
• 17: Y. Dodis, L. Reyzin and A. Smith, Fuzzy Extractors, invited book chapter in "Security with Noisy Data", 2007.
• 18: W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory 22 (1976), pp:644--654.
• 19: B. Dutertre, S. Cheung and J. Levy, "Lightweight Key Management in Wireless Sensor Networks by Leveraging Initial Trust," System Design Laboratory, Technical Report, SRI-SDL-04-02, 2004.
• 20: Laurent Eschenauer , Virgil D. Gligor, A key-management scheme for distributed sensor networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586117]
• 21: J. E. Hershey, A. A. Hassan, and R. Yarlagadda, "Unconventional Cryptographic Keying Variable Management, "IEEE Transaction on Communications, vol 43, No.1, pp3--6, January 1995.
• 22: T. Holenstein and R. Renner, One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption Advances in Cryptology - CRYPTO '05, Lecture Notes in Computer Science, Springer-Verlag, pp. 478--493.
• 23: D. G. Howe, H. Hilden and E. Weldon, Jr., Shift correction code system for correcting additive errors and synchronization slips, United States Patent 5373513, 12/13/1994.
• 24: J. Kittler and M. S. Nixon, Audio-and Video-Based Biometrie Person Authentication, 4th International Conference, AVBPA 2003, Guildford, UK, June 9-11, Lecture Notes in Computer Science, Vol. 2688, 2003.
• 25: J.-P. M. G. Linnartz and P. Tuyls, New Shielding Functions to Enhance Privacy and Prevent Misuse of Biometric Templates, 4th International Conference, AVBPA 2003, Guildford, UK, June 9-11, Lecture Notes in Computer Science, Vol. 2688, pp. 393--402.
• 26: U. Maurer. Secret key agreement by public discussion. IEEE Transactionon Information Theory, 39(3):733--742, 1993.
• 27: Ueli Maurer and Stefan Wolf. Unconditionally secure key agreement and the intrinsic conditional information. IEEE Transaction on Information Theory, 45(2):499-- 514, 1999
• 28: A. Kitaura and H. Sasaoka, "A Scheme of Private Key Agreement Based on the Channel Characteristics in OFDM Land Mobile Radio,"Electronics and Communications in Japan, Part 3 (Fundamental Electronic Science), vol 88, No 9, p 1--10, 2005
• 29: B. Lai, S. Kim and I. Verbauwhede, "Scalable session key construction protocol for wireless sensor networks," IEEE Workshop on Large Scale Real-Time and Embedded Systems, 2002.
• 30: Xiaohua Li, Mo Chen, and E. Paul Ratazzi, "Array-Transmission Based Physical-Layer Security Techniques For Wireless Sensor Networks," Proceedings of the IEEE International Conference on Mechatronics and Automation, pp 1618--1623, Niagara Falls, Canada, July 2005
• 31: T. Ohira, "Secret Key Generation Exploiting Antenna Beam Steering and Wave Propagation Reciprocity," In: 2005 European Microwave Conference, vol(1), pages:9--12, Oct. 2005.
• 32: Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
• 33: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• 34: D. Stinson, Universal hash families and the leftover hash lemma, and applications to cryptography and computing ,J. Combin. Math. Combin. Comput. vol.42, pp.3--31, 2002.
• 35: Aaron D. Wyner. The wire-tap channel. Bell Systems Technical Journal, 54:1355--1387, 1975.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Measurement, Security, Theory

Keywords:
physical layer security, randomness extraction, signal envelopes, wireless ad-hoc networks