research-article

Attacking cryptographic schemes based on "perturbation polynomials"

Authors:

Martin Albrecht,

Craig Gentry,

Shai Halevi,

Jonathan KatzAuthors Info & Claims

CCS '09: Proceedings of the 16th ACM conference on Computer and communications security

Pages 1 - 10

https://doi.org/10.1145/1653662.1653664

Published: 09 November 2009 Publication History

Get Access

Abstract

We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use "perturbation polynomials" to add "noise" to polynomialbased systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes.

Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc 2007), the access-control schemes of Subramanian et al. (PerCom 2007), and the authentication schemes of Zhang et al. (INFOCOM 2008). Our results cast doubt on the viability of using "perturbation polynomials" for designing secure cryptographic schemes.

References

[1]

S. Ar, R. Lipton, R. Rubinfeld, and M. Sudan. Reconstructing Algebraic Functions from Mixed Data. phSIAM J. Computing 28(2): 487--510, 1998.

Digital Library

Google Scholar

[2]

R. Blom. An Optimal Class of Symmetric Key Generation Systems. Eurocrypt'84.

Digital Library

Google Scholar

[3]

C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro, and Moti Yung. Perfectly Secure Key Distribution for Dynamic Conferences. Information and Computation 146(1): 1--23, 1998.

Digital Library

Google Scholar

[4]

W. A. Stein et al. Sage Mathematics Software (Version 3.3).The Sage Development Team, 2009, http://www.sagemath.org.

Google Scholar

[5]

N.V. Subramanian, C. Yang, and W. Zhang. Securing Distributed Data Storage and Retrieval in Sensor Networks. 5th IEEE Intl. Conference on Pervasive Computing and Communications (PerCom), 2007.

Digital Library

Google Scholar

[6]

W. Zhang, N. Subramanian, and G. Wang. Lightweight and Compromise-Resilient Message Authentication in Sensor Networks. 27th IEEE Conference on Computer Communications(INFOCOM), 2008.

Google Scholar

[7]

W. Zhang, M. Tran, S. Zhu, and G. Cao. A Random Perturbation-based Scheme for Pairwise Key Establishment in Sensor Networks. 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2007.

Digital Library

Google Scholar

Cited By

View all

Jing ZChen MHongbo F(2017)WSN key management scheme based on fully bomomorphic encryption2017 29th Chinese Control And Decision Conference (CCDC)10.1109/CCDC.2017.7978504(7304-7309)Online publication date: May-2017
https://doi.org/10.1109/CCDC.2017.7978504
Moussavi AShamsi M(2017)A Polynomial-Based Key Distribution Approach for Wireless Sensor NetworksIranian Journal of Science and Technology, Transactions A: Science10.1007/s40995-017-0330-x42:1(13-20)Online publication date: 14-Dec-2017
https://doi.org/10.1007/s40995-017-0330-x
Yang XLin JYu WMoulema PFu XZhao W(2015)A Novel En-Route Filtering Scheme Against False Data Injection Attacks in Cyber-Physical Networked SystemsIEEE Transactions on Computers10.1109/TC.2013.17764:1(4-18)Online publication date: Jan-2015
https://doi.org/10.1109/TC.2013.177
Show More Cited By

Index Terms

Attacking cryptographic schemes based on "perturbation polynomials"
1. Security and privacy
  1. Network security

Recommendations

A random perturbation-based scheme for pairwise key establishment in sensor networks
MobiHoc '07: Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing

A prerequisite for secure communications between two sensor nodes is that these nodes exclusively share a pairwise key. Although numerous pairwise key establishment (PKE) schemes have been proposed in recent years, most of them have no guarantee for ...
A constrained random perturbation vector-based pairwise key establishment scheme for wireless sensor networks
MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing

This paper presents a Constrained Random Perturbation Vector-based (CRPV) pairwise key establishment scheme and its variant, CRPV+ scheme, for wireless sensor networks (WSNs). Compared to all existing schemes which satisfy only some requirements in a so-...
Security analysis of three cryptographic schemes from other cryptographic schemes
CISC'05: Proceedings of the First SKLOIS conference on Information Security and Cryptology

Relations between various cryptographic schemes make it possible to build a new cryptographic scheme from (some components of) other kinds of cryptographic schemes. Recently, three new schemes are proposed by exploiting these relationships: a group ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CCS '09: Proceedings of the 16th ACM conference on Computer and communications security

November 2009

664 pages

ISBN:9781605588940

DOI:10.1145/1653662

General Chair:
Ehab Al-Shaer
University of North Carolina, Charlotte, USA
,
Program Chairs:
Somesh Jha
University of Wisconsin, USA
,
Angelos D. Keromytis
Columbia University, USA and Symantec Research Labs Europe, France

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '09

Sponsor:

SIGSAC

CCS '09: 16th ACM Conference on Computer and Communications Security 2009

November 9 - 13, 2009

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '24

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 14 - 18, 2024

Salt Lake City , UT , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
633
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jing ZChen MHongbo F(2017)WSN key management scheme based on fully bomomorphic encryption2017 29th Chinese Control And Decision Conference (CCDC)10.1109/CCDC.2017.7978504(7304-7309)Online publication date: May-2017
https://doi.org/10.1109/CCDC.2017.7978504
Moussavi AShamsi M(2017)A Polynomial-Based Key Distribution Approach for Wireless Sensor NetworksIranian Journal of Science and Technology, Transactions A: Science10.1007/s40995-017-0330-x42:1(13-20)Online publication date: 14-Dec-2017
https://doi.org/10.1007/s40995-017-0330-x
Yang XLin JYu WMoulema PFu XZhao W(2015)A Novel En-Route Filtering Scheme Against False Data Injection Attacks in Cyber-Physical Networked SystemsIEEE Transactions on Computers10.1109/TC.2013.17764:1(4-18)Online publication date: Jan-2015
https://doi.org/10.1109/TC.2013.177
Rohith GBhuvaneswari MKannaki S(2015)Optimization of dynamic resistance against malicious attacks & collusion through enhanced authentication schemes in application to smartcard2015 IEEE Seventh National Conference on Computing, Communication and Information Systems (NCCCIS)10.1109/NCCCIS.2015.7295905(5-10)Online publication date: Feb-2015
https://doi.org/10.1109/NCCCIS.2015.7295905
Subha SSankar U(2015)Message authentication and wormhole detection mechanism in wireless sensor network2015 IEEE 9th International Conference on Intelligent Systems and Control (ISCO)10.1109/ISCO.2015.7282382(1-4)Online publication date: Jan-2015
https://doi.org/10.1109/ISCO.2015.7282382
Chowdhury ADasBit S(2015)LMAC: A Lightweight Message Authentication Code for Wireless Sensor Network2015 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2015.7417118(1-6)Online publication date: Dec-2015
https://doi.org/10.1109/GLOCOM.2015.7417118
Gnana Sambandam KKamalanaban E(2015)Message Authentication and Source Privacy in Wi-FiProceedings of the International Conference on Soft Computing Systems10.1007/978-81-322-2674-1_31(319-329)Online publication date: 8-Dec-2015
https://doi.org/10.1007/978-81-322-2674-1_31
Anil Kumar BBhaskara Rao NSunitha M(2015)Authentication of the Message through Hop-by-Hop and Secure the Source Nodes in Wireless Sensor NetworksProceedings of the 3rd International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 201410.1007/978-3-319-12012-6_87(785-791)Online publication date: 2015
https://doi.org/10.1007/978-3-319-12012-6_87
Li JLi YRen JWu J(2014)Hop-by-Hop Message Authenticationand Source Privacy in WirelessSensor NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.11925:5(1223-1232)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1109/TPDS.2013.119
Vincy JKrithika SGowtham K(2014)Design of cryptosystem based on ECC algorithm using hexadecimal values of character2014 International Conference on Green Computing Communication and Electrical Engineering (ICGCCEE)10.1109/ICGCCEE.2014.6922205(1-6)Online publication date: Mar-2014
https://doi.org/10.1109/ICGCCEE.2014.6922205
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A random perturbation-based scheme for pairwise key establishment in sensor networks

A constrained random perturbation vector-based pairwise key establishment scheme for wireless sensor networks

Security analysis of three cryptographic schemes from other cryptographic schemes