Visible to the public Elliptic Curve Cryptography from ACM, 2014, Part 1

SoS Newsletter- Advanced Book Block

SoS Logo

Elliptic Curve Cryptography

ACM (2014)

 Part 1


In Issue Number 4 of the 2015 Newsletter, the editors offered publications of interest about Elliptic Curve Cryptography from IEEE sources in five parts.  This bibliography adds research work published by the Association for Computing Machinery (ACM) in 2014.

Andrea Höller, Norbert Druml, Christian Kreiner, Christian Steger, Tomaz Felicijan; Hardware/Software Co-Design of Elliptic-Curve Cryptography for Resource-Constrained Applications; DAC '14 Proceedings of the 51st Annual Design Automation Conference, June 2014, Pages 1-6. Doi: 10.1145/2593069.2593148 Abstract: ECC is an asymmetric encryption providing a comparably high cryptographic strength in relation to the key sizes employed. This makes ECC attractive for resource-constrained systems. While pure hardware solutions usually offer a good performance and a low power consumption, they are inflexible and typically lead to a high area.  Here, we show a flexible design approach using a 163-bit GF(2m) elliptic curve and an 8-bit processor. We propose improvements to state-of-the-art software algorithms and present innovative hardware/software codesign variants. The proposed implementation offers highly competitive performance in terms of performance and area.
Keywords: Elliptic Curve Cryptography, Embedded Devices, RFID (ID#: 15-4504)


Yu-Fang Chen, Chang-Hong Hsu, Hsin-Hung Lin, Peter Schwabe, Ming-Hsien Tsai, Bow-Yaw Wang, Bo-Yin Yang, Shang-Yi Yang; Verifying Curve25519 Software; CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 299-309. Doi:  10.1145/2660267.2660370 Abstract: This paper presents results on formal verification of high-speed cryptographic software. We consider speed-record-setting hand-optimized assembly software for Curve25519 elliptic-curve key exchange presented by Bernstein et al. at CHES 2011. Two versions for different microarchitectures are available. We successfully verify the core part of the computation, and reproduce detection of a bug in a previously published edition. An SMT solver supporting array and bit-vector theories is used to establish almost all properties. Remaining properties are verified in a proof assistant with simple rewrite tactics. We also exploit the compositionality of Hoare logic to address the scalability issue. Essential differences between both versions of the software are discussed from a formal-verification perspective.
Keywords: boolector, coq, elliptic-curve cryptography, hoare logic, optimized assembly, smt solver (ID#: 15-4505)


Ruan de Clercq, Leif Uhsadel, Anthony Van Herrewege, Ingrid Verbauwhede;  Ultra Low-Power Implementation of ECC on the ARM Cortex-M0+; DAC '14 Proceedings of the 51st Annual Design Automation Conference, June 2014, Pages 1-6. Doi:10.1145/2593069.2593238 Abstract: In this work, elliptic curve cryptography (ECC) is used to make a fast, and very low-power software implementation of a public-key cryptography algorithm on the ARM Cortex-M0+. An optimization of the López-Dahab field multiplication method is proposed, which aims to reduce the number of memory accesses, as this is a slow operation on the target platform. A mixed C and assembly implementation was made; a random point multiplication requires 34.16 μJ, whereas our fixed point multiplication requires 20.63 μJ. Our implementation's energy consumption beats all other software implementations, on any platform, by a factor of at least 3.3.
Keywords: ECC, Embedded, Low-Power, Public-key cryptography (ID#: 15-4506)


Eun-Jun Yoon, Kee-Young Yoo; A Biometric-Based Authenticated Key Agreement Scheme Using ECC for Wireless Sensor Networks; SAC '14 Proceedings of the 29th Annual ACM Symposium on Applied Computing, March 2014, Pages 699-705. Doi: 10.1145/2554850.2555045 Abstract: Recently, various user authentication schemes have successfully drawn researchers' attention and been studied widely in order to guarantee secure communication for wireless sensor networks (WSNs). This paper proposes a new biometric-based authenticated key agreement scheme using Elliptic Curve Cryptosystem (ECC) for WSN to minimize the complexity of computational costs between the sensor node and the GW-node and fit low-power sensor network environments. Compared with previous schemes, the newly proposed scheme has the following more practical characteristics: (1) it provides secure session key agreement function by adopting elliptic curve cryptosystem, (2) it can reduce the total execution time and memory requirement due to the elliptic curve cryptography, (3) it is not only secure against well-known cryptographical attacks but also provides perfect forward secrecy, and (4) it does not require the user password and uses only hash function. Analysis results show that the proposed scheme is extremely suitable for use in WSNs since it provides security, reliability, and efficiency.
Keywords: authentication, biometrics, impersonation attack, key agreement, security, wireless sensor networks (ID#: 15-4507)


Binod Vaidya, Dimitrios Makrakis, Hussein Mouftah;  Effective Public Key Infrastructure for Vehicle-to-Grid Network; DIVANet '14 Proceedings of the Fourth ACM International Symposium on Development and Analysis Of Intelligent Vehicular Networks And Applications, September 2014, Pages 95-101. Doi: 10.1145/2656346.2656348 Abstract: A growth of electric vehicle (EV) technologies likely leads a fundamental shift not only in transportation sector but also in the existing electric power grid infrastructure. In Smart grid infrastructure, vehicle-to-grid (V2G) network can be formed such that participating EVs can be used to store energy and supply this energy back to the power grid when required. To realize proper deployment of V2G network, charging infrastructure having various entities such as charging facility, clearinghouse, and energy provider has to be constructed. So use of Public key infrastructure (PKI) is indispensable for provisioning security solution in V2G network. The ISO/IEC 15118 standard is ascribed that incorporates X.509 PKI solution for V2G network. However, as traditional X.509 based PKI for V2G network has several shortcomings, we have proposed an effectual PKI for a V2G network that is built on based on elliptic curve cryptography and self-certified public key technique having implicit certificate to reduce certificate size and certificate verification time. We show that the proposed solution outperforms the existing solution.
Keywords: ECC, ISO/IEC 15118, PKI, X.509, implicit certificate, smart grid, vehicle-to-grid network (ID#: 15-4508)


Jo Vliegen, Nele Mentens, Ingrid Verbauwhede;  Secure, Remote, Dynamic Reconfiguration of FPGAs; ACM Transactions on Reconfigurable Technology and Systems (TRETS), Volume 7 Issue 4, January 2015, Article No. 35.  Doi:  10.1145/2629423 Abstract: With the widespread availability of broadband Internet, Field-Programmable Gate Arrays (FPGAs) can get remote updates in the field. This provides hardware and software updates, and enables issue solving and upgrade ability without device modification. In order to prevent an attacker from eavesdropping or manipulating the configuration data, security is a necessity.  This work describes an architecture that allows the secure, remote reconfiguration of an FPGA. The architecture is partially dynamically reconfigurable and it consists of a static partition that handles the secure communication protocol and a single reconfigurable partition that holds the main application. Our solution distinguishes itself from existing work in two ways: it provides entity authentication and it avoids the use of a trusted third party. The former provides protection against active attackers on the communication channel, while the latter reduces the number of reliable entities. Additionally, this work provides basic countermeasures against simple power-oriented side-channel analysis attacks.  The result is an implementation that is optimized toward minimal resource occupation. Because configuration updates occur infrequently, configuration speed is of minor importance with respect to area. A prototype of the proposed design is implemented, using 5,702 slices and having minimal downtime.
Keywords: DPR, FPGA, partial reconfiguration, remote, secure (ID#: 15-4509)


Debapriya Basu Roy, Debdeep Mukhopadhyay, Masami Izumi, Junko Takahashi; Tile Before Multiplication: An Efficient Strategy to Optimize DSP Multiplier for Accelerating Prime Field ECC for NIST Curves; DAC '14 Proceedings of the 51st Annual Design Automation Conference, June 2014, Article 177, Pages 1-6. Doi: 10.1145/2593069.2593234 Abstract: High speed DSP blocks present in the modern FPGAs can be used to implement prime field multiplication to accelerate Elliptic Curve scalar multiplication in prime fields. However, compared to logic slices, DSP blocks are scarce resources, hence its usage needs to be optimized. The asymmetric 25 × 18 signed multipliers in FPGAs open a new paradigm for multiplier design, where operand decomposition becomes equivalent to a tiling problem. Previous literature has reported that for asymmetric multiplier, it is possible to generate a tiling (known as non-standard tiling) which requires less number of DSP blocks compared to standard tiling, generated by school book algorithm. In this paper, we propose a generic technique for such tiling generation and generate this tiling for field multiplication in NIST specified curves. We compare our technique with standard school book algorithm to highlight the improvement. The acceleration in ECC scalar multiplication due to the optimized field multiplier is experimentally validated for P-256. The impact of this accelerated scalar multiplication is shown for the key encapsulation algorithm PSEC-KEM (Provably Secure Key Encapsulation Mechanism).
Keywords: DSP Blocks, ECC, FPGA, NIST Curves (ID#: 15-4510)


Gilles Barthe, François Dupressoir, Pierre-Alain Fouque, Benjamin Grégoire, Jean-Christophe Zapalowicz; Synthesis of Fault Attacks on Cryptographic Implementations; CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 1016-1027. Doi:  10.1145/2660267.2660304 Abstract: Fault attacks are attacks in which an adversary with physical access to a cryptographic device, say a smartcard, tampers with the execution of an algorithm to retrieve secret material. Since the seminal Bellcore attack on modular exponentiation, there has been extensive work to discover new fault attacks against cryptographic schemes and develop countermeasures against such attacks. Originally focused on high-level algorithmic descriptions, these efforts increasingly focus on concrete implementations. While lowering the abstraction level leads to new fault attacks, it also makes their discovery significantly more challenging. In order to face this trend, it is therefore desirable to develop principled, tool-supported approaches that allow a systematic analysis of the security of cryptographic implementations against fault attacks.  We propose, implement, and evaluate a new approach for finding fault attacks against cryptographic implementations. Our approach is based on identifying implementation-independent mathematical properties, or fault conditions. We choose fault conditions so that it is possible to recover secret data purely by computing on sufficiently many data points that satisfy them. Fault conditions capture the essence of a large number of attacks from the literature, including lattice-based attacks on RSA. Moreover, they provide a basis for discovering automatically new attacks: using fault conditions, we specify the problem of finding faulted implementations as a program synthesis problem. Using a specialized form of program synthesis, we discover multiple faulted attacks on RSA and ECDSA. Several of the attacks found by our tool are new, and of independent interest. 
Keywords: automated proofs, fault attacks, program synthesis, program verification (ID#: 15-4511)


Peter Chapin, Christian Skalka;  SpartanRPC: Remote Procedure Call Authorization in Wireless Sensor Networks; ACM Transactions on Information and System Security (TISSEC), Volume 17 Issue 2, November 2014, Article No. 5. Doi: 10.1145/2644809 Abstract: We describe SpartanRPC, a secure middleware technology that supports cooperation between distinct security domains in wireless sensor networks. SpartanRPC extends nesC to provide a link-layer remote procedure call (RPC) mechanism, along with an enhancement of configuration wirings that allow specification of remote, dynamic endpoints. RPC invocation is secured via an authorization logic that enables servers to specify access policies and requires clients to prove authorization. This mechanism is implemented using a combination of symmetric and public key cryptography. We report on benchmark testing of a prototype implementation and on an application of the framework that supports secure collaborative use and administration of an existing WSN data-gathering system.
Keywords: Remote procedure call, sensor networks, trust management (ID#: 15-4512)


Gary Anthes; French Team Invents Faster Code-Breaking Algorithm; Communications of the ACM, Volume 57 Issue 1, January 2014, Pages 21-23. Doi: 10.1145/2555807 Abstract: New method can crack certain cryptosystems far faster than earlier alternatives.
Keywords:  (not provided) (ID#: 15-4513)


Pawel Szalachowski, Stephanos Matsumoto, Adrian Perrig; PoliCert: Secure and Flexible TLS Certificate Management; CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 406-417.  Doi: 10.1145/2660267.2660355  Abstract: The recently proposed concept of publicly verifiable logs is a promising approach for mitigating security issues and threats of the current Public-Key Infrastructure (PKI). Although much progress has been made towards a more secure infrastructure, the currently proposed approaches still suffer from security vulnerabilities, inefficiency, or incremental deployment challenges.  In this paper we propose PoliCert, a comprehensive log-based and domain-oriented architecture that enhances the security of PKI by offering: a) stronger authentication of a domain's public keys, b) comprehensive and clean mechanisms for certificate management, and c) an incentivised incremental deployment plan. Surprisingly, our approach has proved fruitful in addressing other seemingly unrelated problems such as TLS-related error handling and client/server misconfiguration.
Keywords: certificate validation, public log servers, public-key certificate, public-key infrastructure, security policy, ssl, tls (ID#: 15-4514)


S. Prayla Shyry; Novel Enhanced Encryption Algorithm for Shared Key Generation; ICONIAAC '14 Proceedings of the 2014 International Conference on Interdisciplinary Advances in Applied Computing, October 2014, Article No. 41. Doi:  10.1145/2660859.2660953 Abstract: The central theme in dynamic environments is secured transmission of packets to remote Cooperative group. In dynamic environments, a new encrypted shared key has to be generated for every join/leave event and forwarded to the key distribution centre (KDC) of the requester. Existing algorithms have used rekeying options for shared key generation. But it requires more bandwidth and time which ultimately degrades the performance of the network. In this paper, a novel Enhanced Encryption Algorithm (EEA) for generating a secured (encrypted) shared key is proposed for the transmission of packets in dynamic environments.
Keywords: Key Distribution Centre, Re-keying, Shared key (ID#: 15-4515)


Marco Tiloca; Efficient Protection of Response Messages in DTLS-Based Secure Multicast Communication; SIN '14 Proceedings of the 7th International Conference on Security of Information and Networks, September 2014, Pages  466. Doi: 10.1145/2659651.2659668 Abstract: DTLS is a standardized security protocol designed to provide end-to-end secure communication among two peers, and particularly considered for the emerging Internet of Things. In order to protect group communication, the IETF is currently working on a method to secure multicast messages through the same DTLS security services. However, such an approach relies on traditional DTLS sessions to protect unicast responses to multicast messages. This increases the amount of security material stored by group members and can have a relevant impact on network performance. In this paper we propose an extension to the IETF approach which allows to efficiently protect group responses by reusing the same group key material. Our proposal does not require to establish additional DTLS sessions, thus preserving high communication performance within the group and limiting storage overhead on group members. Furthermore, we discuss a suitable key management policy to provision and renew group key material.
Keywords: DTLS, Group communication, Multicast, Security (ID#: 15-4516)


Vireshwar Kumar, Jung-Min Park, Kaigui Bian; Blind Transmitter Authentication for Spectrum Security and Enforcement; CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security,  November 2014, pages 787-798. Doi: 10.1145/2660267.2660318  Abstract: Recent advances in spectrum access technologies, such as cognitive radios, have made spectrum sharing a viable option for addressing the spectrum shortage problem. However, these advances have also contributed to the increased possibility of "hacked" or "rogue" radios causing harm to the spectrum sharing ecosystem by causing significant interference to other wireless devices. One approach for countering such threats is to employ a scheme that can be used by a regulatory entity (e.g., FCC) to uniquely identify a transmitter by authenticating its waveform. This enables the regulatory entity to collect solid evidence of rogue transmissions that can be used later during an adjudication process. We coin the term Blind Transmitter Authentication (BTA) to refer to this approach. Unlike in the existing techniques for PHY-layer authentication, in BTA, the entity that is authenticating the waveform is not the intended receiver. Hence, it has to extract and decode the authentication signal "blindly" with little or no knowledge of the transmission parameters. In this paper, we propose a novel BTA scheme called Frequency offset Embedding for Authenticating Transmitters (FEAT). FEAT embeds the authentication information into the transmitted waveform by inserting an intentional frequency offset. Our results indicate that FEAT is a practically viable approach and is very robust to harsh channel conditions. Our evaluation of FEAT is based on theoretical bounds, simulations, and indoor experiments using an actual implementation.
Keywords: cognitive radios, phy-layer authentication, spectrum sharing and management, transmitter identification (ID#: 15-4517)


David Basin, Cas Cremers, Tiffany Hyun-Jin Kim, Adrian Perrig, Ralf Sasse, Pawel Szalachowski; ARPKI: Attack Resilient Public-Key Infrastructure;  CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 382-393. Doi:  10.1145/2660267.2660298 Abstract: We present ARPKI, a public-key infrastructure that ensures that certificate-related operations, such as certificate issuance, update, revocation, and validation, are transparent and accountable. ARPKI is the first such infrastructure that systematically takes into account requirements identified by previous research. Moreover, ARPKI is co-designed with a formal model, and we verify its core security property using the Tamarin prover. We present a proof-of-concept implementation providing all features required for deployment. ARPKI efficiently handles the certification process with low overhead and without incurring additional latency to TLS. ARPKI offers extremely strong security guarantees, where compromising n-1 trusted signing and verifying entities is insufficient to launch an impersonation attack. Moreover, it deters misbehavior as all its operations are publicly visible.
Keywords: attack resilience, certificate validation, formal validation, public log servers, public-key infrastructure, tls (ID#: 15-4518)


Mario Cornejo, Sylvain Ruhault; Characterization of Real-Life PRNGs under Partial State Corruption; CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 1004-1015. Doi: 10.1145/2660267.2660377 Abstract: Pseudo-random number generators (PRNGs) are widely used as a randomness source in cryptographic applications. It is essential for their security that the internal state, in which the entropy is accumulated, is kept secret. However, this assumption is unrealistic for PRNGs that are implemented in software, as the internal state can be partially corrupted through memory corruption bugs such as buffer overflows or through faults attacks. The recent Heartbleed bug gives us a concrete illustration of this vulnerability. In this work we study several widely used PRNGs from different popular providers, including OpenSSL, OpenJDK, Android, IBM and Bouncy Castle and we characterize how they handle their internal states. We formalize a framework based on the most recent and strongest security model called robustness of PRNGs to analyze these PRNGs and their implementations. With this framework we capture the notion of how much of the internal state must be corrupted in order to generate a predictable output. Using this framework, we determine the number of bits of the internal state that an attacker needs to corrupt in order to produce a predictable output. We also show that two of the PRNGs do not require state compromise to generate a non-random output. To the best of our knowledge, we present the first thorough characterization of an IBM implementation of a PRNG.
Keywords: android, java, openssl, randomness, security models (ID#: 15-4519)


Kuan-Chung Huang, Yu-Chen Wu, Che-Wei Chang, Tei-Wei Kuo, Chi-Sheng Shih, Qingxu Deng; Real-time Process Synchronization for Systems with Accelerators; RACS '14 Proceedings of the 2014 Conference on Research in Adaptive and Convergent Systems, October 2014, Pages 350-355. Doi:  10.1145/2663761.2664220 Abstract: This work is motivated by the needs to manage the priority inversion problem without sacrificing the utilization of increasingly popular hardware accelerators. A new mechanism is developed to dedicate accelerators to selected higher-priority tasks. The floor and ceiling priorities of accelerators are thus proposed as an extension of the concept of semaphore priority ceiling to guarantee at most two priority inversions for any real-time task in a uniprocessor system with multiple accelerators. The properties of the proposed concept are explored with respect to blocking behaviors over the CPU and accelerators and are verified by a series of experiments, for which the insight of the simple but effective idea is evaluated and presented.
Keywords: blocking time analysis, dedicated accelerators, synchronization protocols (ID#: 15-4520)


Jun Tao, Jun Ma, Melissa Keranen, Jean Mayo, Ching-Kuang Shene, Chaoli Wang; RSAvisual: A Visualization Tool for the RSA Cipher; SIGCSE '14 Proceedings of the 45th ACM Technical Symposium on Computer Science Education, March 2014, Pages 635-640. Doi: 10.1145/2538862.2538891 Abstract: This paper describes a visualization tool RSAvisual that helps students learn and instructors teach the RSA cipher. This tool permits the user to visualize the steps of the RSA cipher, do encryption and decryption, learn simple factorization algorithms, and perform some elementary attacks. The demo mode of RSAvisual can be used for classroom presentation and self-study. With the practice mode, the user may go through steps in encryption, decryption, the Extended Euclidean algorithm, two simple factorization algorithms and three elementary attacks. The user may compute the output of each operation and check for correctness. This helps students learn the primitive operations and how they are used in the RSA cipher. The opportunity for self-study provides an instructor with greater flexibility in selecting a lecture pace for the detailed materials. Classroom evaluation was positive and very encouraging.
Keywords: cryptography, visualization (ID#: 15-4521)


Raghav V. Sampangi, Srinivas Sampalli; HiveSign: Dynamic Message Signatures For Resource-Constrained Wireless Networks; Q2SWinet '14 Proceedings of the 10th ACM Symposium on QoS and Security for Wireless and Mobile Networks, September 2014, Pages 33-40. Doi: 10.1145/2642687.2642699 Abstract: Radio Frequency Identification (RFID) and Wireless body area network (WBAN) are two of the emerging wireless networks that are becoming increasingly popular, owing to their applicability in a variety of domains and longevity-based designs. However, the flexibility they offer and their reduced manufacturing cost come with a trade-off — they have severe implicit hardware restrictions. These restrictions limit their ability to store a large amount of data and/or perform sophisticated computation, thereby leading them to be classified as resource-constrained wireless networks. Their constraints further limit the security that can be implemented on these devices, necessitating design of optimized solutions for security. In our paper, we present a new approach that generates dynamic message signatures using simple logical operations, hashing and pseudorandom number generation (PRNG) to accomplish integrity and entity authentication. Our approach provides a means to verify the integrity of both the message as well as the key. We validate our proposal using security evaluation and complexity analysis.

Keywords: dynamic message signatures, entity authentication, message signatures, security in resource-constrained networks (ID#: 15-4522)


Muhammad Rizwan Asghar, Ashish Gehani, Bruno Crispo, Giovanni Russello; PIDGIN: Privacy-Preserving Interest and Content Sharing In Opportunistic Networks; ASIA CCS '14 Proceedings of the 9th ACM Symposium On Information, Computer And Communications Security, June 2014, Pages 135-146. Doi:  10.1145/2590296.2590303 Abstract: Opportunistic networks have recently received considerable attention from both industry and researchers. These networks can be used for many applications without the need for a dedicated IT infrastructure. In the context of opportunistic networks, content sharing in particular has attracted significant attention. To support content sharing, opportunistic networks often implement a publish-subscribe system in which users may publish their own content and indicate interest in other content through subscriptions. Using a smartphone, any user can act as a broker by opportunistically forwarding both published content and interests within the network. Unfortunately, opportunistic networks are faced with serious privacy and security issues. Untrusted brokers can not only compromise the privacy of subscribers by learning their interests but also can gain unauthorised access to the disseminated content. This paper addresses the research challenges inherent to the exchange of content and interests without: (i) compromising the privacy of subscribers, and (ii) providing unauthorised access to untrusted brokers. Specifically, this paper presents an interest and content sharing solution that addresses these security challenges and preserves privacy in opportunistic networks. We demonstrate the feasibility and efficiency of the solution by implementing a prototype and analysing its performance on smart phones.
Keywords: encrypted CP-ABE policies, privacy-preserving content sharing, secure haggle, secure opportunistic networks, sensitive policy enforcement (ID#: 15-4523)



Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.