Theorem 4. Localization privacy cannot be achieved when the tags are static if neither temporal nor location information is available.
Proof. The proof is by contradiction. Suppose that neither temporal nor location infor- mation is available. First consider a ubiquitous adversary. If the tag is not in range of the RFID reader that challenges it, then the adversary can use an online man-in-the-middle relay attack to forward the reader’s challenge to another area of the deployment zone were the tag may be. The tag has no way of checking that the challenge was sent from far away and/or much earlier. So it will respond. This violates localization privacy.
Next consider a local adversary. In this case suppose that the tag is not present during the interrogation. Then the adversary may record the challenge of the RFID reader and replay the challenge later (an offline man-in-the-middle attack). Again the tag has no way of detecting that the challenge was sent from another location earlier, and will
respond.
7 Conclusion
We have shown that for static RFID deployments, localization privacy can be achieved in the presence of a ubiquitous adversary, if the tags know either:(i)their approximate location (Theorem 1, Part 1; Theorem 2, Part 1), or(ii)the exact time (highly synchro- nized clocks, Theorem 3). In this threat model, localization privacy is restricted to one (complete) interrogation per tag.
For applications that require multiple interrogations per tag we only get localization privacy for local adversaries (Theorem 1, Part 2; Theorem 2, Part 2; Theorem 3, Part 2), and this only if the tags know either their approximate location or the time (loosely synchronized clocks).
If the RFID tags do not have temporal or location information then we cannot get localization privacy (Theorem 4), not even for local adversaries.
Acknowledgement. The author would like to thank Xiuwen Liux and Zhenghao Zhang for helpful discussions on accurate localization technologies and Jorge Munilla for help- ful comments on security issues.
References
1. Alippi, C., Cogliati, D., Vanini, G.: A statistical approach to localize passive RFIDs. In: Proc.
of the IEEE Int. Symp. on Circuits and Systems (ISCAS), pp. 843–846. Island of Kos, Greece (2006)
2. Ateniese, G., Camenisch, J., de Medeiros, B.: Untraceable RFID tags via insubvertible en- cryption. In: Proc. ACM Conf. on Computer and Communication Security (ACM CCS 2005), pp. 92–101. ACM Press, New York (2005)
3. Avoine, G.: RFID Security and Privacy Lounge (2010), http://www.avoine.net/rfid/
4. Avoine, G., Oechslin, P.: A scalable and provably secure hash-based rfid protocol. In: PER- COMW 2005: Proceedings of the Third IEEE International Conference on Pervasive Com- puting and Communications Workshops, pp. 110–114. IEEE Computer Society, Washington, DC,USA (2005)
5. Bahl, P., Padmanabhan, V.N.: Radar: An in-building rf-based user location and tracking sys- tem. In: INFOCOM, pp. 775–784 (2000)
6. Barsumian, B.R., Jones, T.H.: U.S. Patent # 6, pp. 163–259 (December 19, 2010)
7. Brunato, M., Battiti, R.: Statistical learning theory for location fingerprinting in wireless LANs. Computer Networks 47, 825–845 (2005)
8. Burmester, M., van Le, T., de Medeiros, B.: Provably secure ubiquitous systems: Univer- sally composable RFID authentication protocols. In: Proceedings of the 2nd IEEE/CreateNet International Conference on Security and Privacy in Communication Networks (SE- CURECOMM 2006), IEEE Press, Los Alamitos (2006)
9. Burmester, M.: His late master’s voice, barking for location privacy
10. Burmester, M., de Medeiros, B.: The Security of EPC Gen2 Compliant RFID Protocols.
In: Bellovin, S.M., Gennaro, R., Keromytis, A.D., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 490–506. Springer, Heidelberg (2008)
11. Burmester, M., Munilla, J.: Flyweight authentication with forward and backward security.
ACM Trans. Inf. Syst. Secur. 12 (August 27, 2010) (accepted), http://www.cs.fsu.edu/burmeste/103.pdf,2011
12. Chang, H.-L., Tian, J.-B., Lai, T.-T., Chu, H.-H., Huang, P.: Spinning beacons for precise in- door localization. In: ACM Third International Conference on Embedded Networked Sensor Systems, SenSys 2008 (November 2008)
13. Cilek, F., Seemann, K., Brenk, D., Essel, J., Weigel, R., Holweg, G., Heidrich, J.: Ultra low power oscillator for UHF RFID transponder. In: IEEE Frequency Control Symposium, 2008, 19-21 May, pp. 418–421. IEEE, Los Alamitos (2008)
14. Coco, S., Laudani, A., Mazzurco, L.: A novel 2-D ray tracing procedure for the localization of EM field sources in urban environment. IEEE Transactions on Magnetics 40(2), 1132–
1135 (2004)
15. Danezis, G., Lewis, S., Anderson, R.: How Much is Location Privacy Worth? In: Fourth Workshop on the Economics of Information Security (WEIS 2005), June 23, vol. 3. Harvard University, Cambridge (2005)
16. Dimitriou, T.: A secure and efficient RFID protocol that can make big brother obsolete. In:
Proc. Intern. Conf. on Pervasive Computing and Communications (PerCom 2006). IEEE Press, Los Alamitos (2006)
17. Elnahrawy, E., Martin, R.P., Ju, W.h., Krishnan, P., Madigan, D.: Bayesian indoor positioning systems. In: Infocom, pp. 1217–1227 (2005)
18. EPC Global. EPC tag data standards, vs. 1.3, http://www.epcglobalinc.org/
standards/EPCglobal Tag Data Standard TDS Version 1.3.pdf
19. Fortune, S.J., Gay, D.M., Kernighan, B.W., Landron, O., Valenzuela, R.A., Wright, M.H.:
Wise design of indoor wireless systems: practical computation and optimization. IEEE Com- putational Science & Engineering 2(1), 58–68 (1995)
20. Hahnel, D., Burgard, W., Fox, D., Fishkin, K., Philipose, M.: Mapping and Localization with RFID Technology. In: Proceedings of IEEE International Conference on Robotics and Automation, pp. 1015–1020 (2004)
21. Cory, H.-W., Grant, B., Liu, X., Zhang, Z., Kumar, P.: Accurate localization of RFID tags us- ing phase difference. In: IEEE International Conference on RFID 2010. IEEE, Los Alamitos (2010)
22. Henrici, D., M¨uller, P.M.: Hash-based enhancement of location privacy for radio-frequency identification devices using varying identifiers. In: Proc. IEEE Intern. Conf. on Pervasive Computing and Communications, pp. 149–153 (2004)
23. His Master’s Voice,http://en.wikipedia.org/wiki/
24. ISO/IEC. Standard # (1800), 0 – RFID Air Interface Standard, http://www.hightechaid.com/standards/18000.htm
25. Iwata, T., Kurosawa, K.: OMAC: One-Key CBC MAC. In: Johansson, T. (ed.) FSE 2003.
LNCS, vol. 2887, pp. 129–153. Springer, Heidelberg (2003)
26. Joho, D., Plagemann, C., Burgard, W.: Modeling RFID Signal Strength and Tag Detection for Localization and Mapping. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Kobe, Japan, pp. 3160–3165 (May 2009)
27. Jones, T.H., Barsumian, B.R.: U.S. Patent #6,057,765, (May 2, 2010)
28. Kleiner, A., Dornhege, C., Dali, S.: Mapping disaster areas jointly: RFID-coordinated SLAM by humans and robots. In: Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics, SSRR (2007)
29. Kusy, B., Ledeczi, A., Koutsoukos, X.: Tracking mobile nodes using rf doppler shifts. In:
SenSys 2007: Proceedings of the 5th International Conference on Embedded Networked Sensor Systems, pp. 29–42. ACM, USA (2007)
30. Kusy, B., Sallai, J., Balogh, G., Ledeczi, A., Protopopescu, V., Tolliver, J., DeNap, F., Parang, M.: Radio interferometric tracking of mobile wireless nodes. In: Proc. of MobiSys 2007(2007)
31. Ledeczi, A., Volgyesi, P., Sallai, J., Kusy, B., Koutsoukos, X., Maroti, M.: Towards Precise Indoor RF Localization. In: HOTEMNETS 2008, Charlottesville, VA (June 2008)
32. Lee, Y.K., Batina, L., Singelee, D., Preneel, B., Verbauwhede, I.: Anti-counterfeiting, Un- traceability and Other Security Challenges for RFID Systems: Public-Key-Based Protocols and Hardware. In: Towards Hardware-Intrinsic Security, Information Security and Cryptog- raphy – THIS 2010, pp. 237–257. Springer, Heidelberg (November 2010)
33. Li, B., Kam, J., Lui, J., Dempster, A.G.: Use of directional information in wireless LAN based indoor positioning. In: IGNSS Symposium (2007)
34. Liu, L.: From data privacy to location privacy: models and algorithms. In: Proceedings of the 33rd International Conference on Very large Data Bases, VLDB 2007, pp. 1429–1430.
VLDB Endowment (2007)
35. Maroti, M., Kusy, B., Balogh, G., Volgyesi, P., Molnar, K., Nadas, A., Dora, S., Ledeczi, A.:
Radio Interferometric Geolocation. In: ACM Third International Conference on Embedded Networked Sensor Systems (SenSys 2005), San Diego, CA, pp. 1–12 (November 2005) 36. Molnar, D., Soppera, A., Wagner, D.: A Scalable, Delegatable Pseudonym Protocol Enabling
Ownership Transfer of RFID Tags. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 276–290. Springer, Heidelberg (2006)
37. Nguyen, X., Jordan, M., Sinopoli, B.: A kernel-based learning approach to ad hoc sensor network localization. ACM Transactions on Sensor Networks (2005)
38. Ni, L.M., Liu, Y., Lau, Y.C., Patil, A.: LANDMARC: Indoor Location Sensing Using Active RFID. ACM Wireless Networks 10(6), 701–710 (2004)
39. Nikitin, P.V., Rao, K.V.S., Lazar, S.: An Overview of Near Field UHF RFID. In: IEEE Inter- national Conference on RFID 2007, pp. 167–174 (March 2007)
40. Ohkubo, M., Suzuki, K., Kinoshita, S.: Cryptographic approach to privacy-friendly tags. In:
Proc. RFID Privacy Workshop (2003)
41. Rappaport, T.S.: Wireless Communications - Principles & Practice, 2nd edn. Prentice Hall PTR, Englewood Cliffs (2003)
42. RFIDNews. EarthSearch launches GPS-RFID hybrid solution, http://www.rfidnews.org/2009/03/16/
earthsearch-launches-gps-rfid-hybrid-solution
43. Sallai, J., Ledeczi, A., Amundson, I., Koutsoukos, X., Maroti, M.: Using RF received phase for indoor tracking. HotEmNets (June 2010)
44. Seshadri, V., Zaruba, G.V., Huber, M.: A Bayesian sampling approach to in-door localization of wireless devices using received signal strength indication. In: Proc. of the IEEE Int. Conf.
on Pervasive Computing and Communications (PerCom), pp. 75–84 (2005)
45. Sharma, S.E., Weiss, S.A., Engels, D.W.: RFID systems and security and privacy implica- tions. In: Kaliski Jr., B.S., Kocá, Cá .K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp.
454–469. Springer, Heidelberg (2003)
46. Tayebi, A., Gomez, J., Saez de Adana, F., Gutierrez, O.: The application of ray-tracing to mobile localization using the direction of arrival and received signal strength in multipath indoor environments. Progress In Electromagnetics Research 91, 1–15 (2009)
47. van Le, T., Burmester, M., de Medeiros, B.: Universally Composable and Forward-Secure RFID Authentication and Authenticated Key Exchange. In: Proc. of the ACM Symp. on In- formation, Computer, and Communications Security (ASIACCS 2007), pp. 242–252. ACM Press, New York (2007)
48. WISP. Wireless Identification and Sensing Platform, Intel Labs, Seattle, http://seattle.intel-research.net/wisp/
49. Youssef, M., Agrawala, A.: The horus WLAN location determination system. In: MobiSys, pp. 205–218 (2005)
50. Zhang, T., Chen, Z., Ouyang, Y., Hao, J., Xiong, Z.: An Improved RFID-Based Locating Algorithm by Eliminating Diversity of Active Tags for Indoor Environment. The Computer Journal 52(8), 902–909 (2009)
51. Zhao, Y., Liu, Y., Ni, L.M.: VIRE: Active RFID-based localization using virtual reference elimination. In: Proceedings of ICPP (2007)
52. Zhou, J., Shi, J.: RFID localization algorithms and applications, a review. Journal of Intelli- gent Manufacturing, 1–13 (2008)
with Provenance
Sherman S.M. Chow1, Cheng-Kang Chu2, Xinyi Huang2, Jianying Zhou2, and Robert H. Deng3
1 University of Waterloo smchow@math.uwaterloo.ca
2 Institute for Infocomm Research {ckchu,xhuang,jyzhou}@i2r.a-star.edu.sg
3 Singapore Management University robertdeng@smu.edu.sg
Abstract. One concern in using cloud storage is that the sensitive data should be confidential to the servers which are outside the trust domain of data owners. Another issue is that the user may want to preserve his/her anonymity in the sharing or accessing of the data (such as in Web 2.0 applications). To fully enjoy the benefits of cloud storage, we need a confidential data sharing mechanism which is fine-grained (one can specifywhocan accesswhich classesof his/her encrypted files), dynamic (the total number of users is not fixed in the setup, and any new user can decrypt previously encrypted messages), scalable (space requirement does not depend on the number of decryptors), accountable (anonymity can be revoked if necessary) and secure (trust level is minimized).
This paper addresses the problem of building a secure cloud storage system which supports dynamic users and data provenance. Previous system is based on specific constructions and does not offer all of the aforementioned desirable properties. Most importantly, dynamic user is not supported. We study the various features offered by cryptographic anonymous authentication and encryption mechanisms; and instantiate our design with verifier-local revocable group signature and identity- based broadcast encryption with constant size ciphertexts and private keys. To realize our concept, we equip the broadcast encryption with the dynamic ciphertext update feature, and give formal security guarantee against adaptive chosen-ciphertext decryption and update attacks.
Keywords: Anonymity, broadcast encryption, cloud storage, dynamic encryption, group signatures, pairings, secure provenance.
1 Introduction
New computing paradigms keep emerging. One notable example is the cloud computing paradigm, a new economic computing model made possible by the ad- vances in networking technology, where a client can leverage a service provider’s
Funded by A*STAR project SecDC-112172014.
D. Naccache (Ed.): Quisquater Festschrift, LNCS 6805, pp. 442–464, 2012.
c Springer-Verlag Berlin Heidelberg 2012
computing, storage or networking infrastructure. With the unprecedented expo- nential growth rate of information, there is an increasing demand for outsourcing data storage to cloud services such as Microsoft’s Azure and Amazon’s S3.
The use of public cloud infrastructure introduces significant security and pri- vacy risks. For the sensitive data, one can always use data encryption before outsourcing to mitigate the confidentiality concern. However, the hurdle often lies in its management. Consider that a certain organization is a cloud service client; different individual users within an organization should have different ac- cess privileges of the organization’s data. The cloud client may not want to trust the cloud server in performing the access control faithfully, or put thewholesys- tem under the control of a reference monitor inside a trusted hypervisor. Apart from the management of access control, dynamic user management is also an important feature for anypracticalsystem. New users may join the system after the data is encrypted, and it is desirable that a new user can decrypt previ- ously created ciphertexts if necessary. This also implies that the same copy of ciphertext can be decryptable by more than one user, and one may not want to maintain multiple ciphertexts corresponding to the same plaintext data, either for easier data management or minimizing storage overhead.
Another issue is privacy. A cloud client hoping to enforce access control does not necessary need to let the cloud server to know the identity of the users.
Actually, anonymity is a desirable feature for many web or collaborative ap- plications. Active involvement of discussion or collaboration over web can be partially attributed to the (pseudo) anonymity perceived by the users. On the other hand, perfect anonymity might be abused by misbehaving users. It is thus equally important to supportdata provenance, especially, to record who created, modified, deleted data stored in a cloud.
Can the current advances in cryptography solve our problem? Recall that us- ing group signatures, each group member can sign a message on behalf of a group such that anyone can verify that the group signature is produced by someone enrolled to the group, but not exactly whom. Can we just employ any group signature scheme for the data provenance, and any public key encryption for the data confidentiality requirement of cloud storage? Concretely, for a user to upload (encrypted) data, he or she has to sign the ciphertext using the member signing key. The cloud service provider accepts this ciphertext if the signature is valid. All the users’ action regarding insertion, modification and deletion will be accountable due to the use of group signature as an anonymous authentica- tion mechanism. A group manager can then open the signature to reveal the uploader’s identity in case the data is in dispute. Indeed, it is actually the ap- proach taken by a recent secure provenance system for cloud computing [12]. We revisit this problem, identify and realize the missing features which are desirable in the cloud setting, investigate the subtle issues involved in the interaction of these two cryptographic primitives, and contribute to the study of secure cloud storage system in the following four aspects.