main-content

## Über dieses Buch

This book constitutes the refereed proceedings of the 5th International Conference on Security, Privacy, and Applied Cryptography Engineering, SPACE 2015, held in Jaipur, India, in October 2015.

The 17 full papers presented in this volume were carefully reviewed and selected from 57 submissions. The book also contains 4 invited talks in full-paper length. The papers are devoted to various aspects of security, privacy, applied cryptography, and cryptographic engineering.

## Inhaltsverzeichnis

### Efficient Protocol for Authenticated Email Search

Abstract
Executing authenticated computation on outsourced data is currently an area of major interest in cryptology. Large databases are being outsourced to untrusted servers without appreciable verification mechanisms. As adversarial server could produce erroneous output, clients should not trust the server’s response blindly. Primitive set operations like union, set difference, intersection etc. can be invoked on outsourced data in different concrete settings and should be verifiable by the client. One such interesting adaptation is to authenticate email search result where the untrusted mail server has to provide a proof along with the search result. Recently Ohrimenko et al. proposed a scheme for authenticating email search. We suggest significant improvements over their proposal in terms of client computation and communication resources by properly recasting it in two-party settings. In contrast to Ohrimenko et al. we are able to make the number of bilinear pairing evaluation, the costliest operation in verification procedure, independent of the result set cardinality for union operation. We also provide an analytical comparison of our scheme with their proposal which is further corroborated through experiments.
Sanjit Chatterjee, Sayantan Mukherjee, Govind Patidar

### Analyzing Traffic Features of Common Standalone DoS Attack Tools

Abstract
Research on denial of service (DoS) attack detection is complicated due to scarcity of reliable, widely available and representative contemporary input data. Efficiency of newly proposed DoS detection methods is continually verified with obsolete attack samples and tools. To address this issue, we provide a comparative analysis of traffic features of DoS attacks that were generated by state-of-the-art standalone DoS attack tools. We provide a classification of different attack traffic features, including utilized evasion techniques and encountered anomalies. We also propose a new research direction for the detection of DoS attacks at the source end, based on repeated attack patterns recognition.
Vit Bukac, Vashek Matyas

### Design of Cyber Security for Critical Infrastructures: A Case for a Schizoid Design Approach

Abstract
In this invited talk, we argue that designing cyber security of critical infrastructure requires a spilt-personality approach to design as opposed to design for correctness or for performance. Designing a functionally correct system, or a performance constrained system is fundamentally different in the sense that such design requires us to build models and to systematically refine models towards implementation such that correctness is preserved between refinements, and performance optimizations are introduced during refinements. Designing systems with cyber-security properties requires us to not only build models from theoretical principles, but also require modeling possible behaviors of an adversary. Modeling adversarial behavior is akin to test-driven model refinement, and hence not so different from certain approaches used when our goal is functionally correct design. However, for cyber-physical systems, we often need to detect an ongoing cyber attack since safe guards for cyber security often depend on assumptions which can be invalidated (e.g., insider attacks may invalidate perimeter security assumptions). Detecting ongoing attacks requires detecting behavioral anomalies in the physical system under cyber control – thus requiring us to build models from data. Machine learning approaches could be used to build such models. This we view as a schizoid approach – since the designer has to not only model the system from physical principles, he/she also has to build nominal behavioral models from data. While arguing this point of view, we introduce a virtual SCADA (supervisory control and data acquisition) laboratory we have built to help design cyber security of critical systems. The majority of this talk focuses on describing this software based virtual laboratory called VSCADA. Most of this research is published in [8,11] and summarized here for the sake of exposition to the present audience.
Avik Dayal, Yi Deng, Sandeep K. Shukla

### Designing for Attack Surfaces: Keep Your Friends Close, but Your Enemies Closer

Abstract
It is no surprise to say that attackers have the upper hand on security practitioners today when it comes to host security. There are several causes for this problem ranging from unsafe programming languages to the complexity of modern systems at large, but fundamentally, all of the parties involved in constructing and deploying systems lack a methodology for reasoning about the security impact of their design decisions. Previous position papers have focused on identifying particular parties as being “enemies” of security (e.g., users and application developers), and proposed removing their ability to make securityrelevant decisions. In this position paper, we take this approach a step further by “keeping the enemies closer,” whereby the security ramifications of design and deployment decisions of all parties must be evaluated to determine if they violate security requirements or are inconsistent with other party’s assumptions. We propose a methodology whereby application developers, OS distributors, and system administrators propose, evaluate, repair, and test their artifacts to provide a defensible attack surface, the set of entry points available to an attacker. We propose the use of a hierarchical state machine (HSM) model as a foundation for automatically evaluating attack surfaces for programs, OS access control policies, and network policies. We examine how the methodology tasks can be expressed as problems in the HSM model for each artifact, motivating the possibility of a comprehensive, coherent, and mostly-automated methodology for deploying systems to manage accessibility to attackers.
Trent Jaeger, Xinyang Ge, Divya Muthukumaran, Sandra Rueda, Joshua Schiffman, Hayawardh Vijayakumar

### Improving Application Security through TLS-Library Redesign

Abstract
Research has revealed a number of pitfalls inherent in contemporary TLS libraries. Common mistakes when programming using their APIs include insufficient certificate verification and the use of weak cipher suites. These programmer errors leave applications susceptible to man-in-the-middle attacks. Furthermore, current TLS libraries encourage system designs which leave the confidentiality of secret authentication and session keys vulnerable to application flaws. This paper introduces libtlssep (pronounced lib.tē.el.sep), a new, open-source TLS library which provides a simpler API and improved security architecture. Applications that use libtlssep spawn a separate process whose role is to provide one or more TLS-protected communication channels; this child process assures proper certificate verification and isolates authentication and session keys in its separate memory space. We present a security, programmability, and performance analysis of libtlssep.
Leo St. Amour, W. Michael Petullo

### How Not to Combine RC4 States

Abstract
Over the past few years, an attractive design paradigm has emerged, that aims to produce new stream cipher designs, by combining one or more independently produced RC4 states. The ciphers so produced turn out to be faster than RC4 on any software platform, mainly because the average number of internal operations used in the cipher per byte of keystream produced is usually lesser than RC4. One of the main efforts of the designers is to ensure that the existing weaknesses of RC4 are not carried over to the new ciphers so designed. In this work we will look at two such ciphers RC4B (proposed by Zhang et. al.) and Quad-RC4/m-RC4 (proposed by Maitra et. al.). We will propose distinguishing attacks against all these ciphers, and look at certain design flaws that made these ciphers vulnerable.

### Preimage Analysis of the Maelstrom-0 Hash Function

Abstract
Maelstrom-0 is the second member of a family of AES-based hash functions whose designs are pioneered by Paulo Baretto and Vincent Rijmen. According to its designers, the function is designed to be an evolutionary lightweight alternative to the ISO standard Whirlpool. In this paper, we study the preimage resistance of the Maelstrom-0 hash function using its proposed 3CM chaining construction. More precisely, we apply a meet-in-the-middle preimage attack on the compression function and combine it with a guess and determine approach which allows us to obtain a 6-round pseudo preimage for a given compression function output with time complexity of 2496 and memory complexity of 2112. Then, we propose a four stage attack in which we adopt another meet-in-the-middle attack and a 2-block multicollision approach to defeat the two additional checksum chains and turn the pseudo preimage attack on the compression function into a preimage attack on the hash function. Using our approach, preimages of the 6-round reduced Maelstrom-0 hash function are generated with time complexity of 2505 and memory complexity of 2112.
Riham AlTawy, Amr M. Youssef

### Meet-in-the-Middle Attacks on Round-Reduced Khudra

Abstract
Khudra is a hardware-oriented lightweight block cipher that is designed to run efficiently on Field Programmable Gate Arrays. It employs an 18-rounds Generalized type-2 Feistel Structure with a 64-bit block length and an 80-bit key. In this paper, we present Meet-in-the-Middle (MitM) attacks on 13 and 14 round-reduced Khudra. These attacks are based on finding a distinguisher that is evaluated offline independently of the key. Then in an online phase, some rounds are appended before and after the distinguisher and the correct key candidates for these rounds are checked whether they verify the distinguisher property or not. Using this technique, we find two 6-round distinguishers and use them to attack 13 and 14 rounds of Khudra with time complexity of 266.11 and 266.19, respectively. Both attacks require the same data and memory complexities of 251 chosen plaintexts and 264.8 64-bit blocks, respectively.
Mohamed Tolba, Ahmed Abdelkhalek, Amr M. Youssef

### Improved Key Recovery Attack on Round-reduced Hierocrypt-L1 in the Single-Key Setting

Abstract
Hierocrypt-L1 is a 64-bit block cipher with a 128-bit key. It was selected among the Japanese e-Government 2003 recommended ciphers list and has been reselected in the 2013 candidate recommended ciphers list. In this work, we cryptanalyze Hierocrypt-L1 in the single-key setting. In particular, we construct a 5 S-box layers distinguisher that we utilize to launch a meet-in-the-middle attack on 8 S-box layers round-reduced Hierocrypt-L1 using the differential enumeration technique. Our attack allows us to recover the master key with data complexity of 249 chosen plaintexts, time complexity of 2114.8 8-Sbox layers Hierocrypt-L1 encryptions and memory complexity of 2106 64-bit blocks. Up to the authors’ knowledge, this is the first cryptanalysis result that reaches 8 S-box layers of Hierocrypt-L1 in the single-key setting.
Ahmed Abdelkhalek, Mohamed Tolba, Amr M. Youssef

### S-boxes, Boolean Functions and Codes for the Resistance of Block Ciphers to Cryptographic Attacks, with or without Side Channels

Abstract
The choice of functions $$S: \mathbb{F}_2^n\mapsto \mathbb{F}_2^m$$ to be used as substitution boxes (S-boxes), fastly implementable and contributing to resisting attacks is a crucial question for the design of block ciphers. We summary the state of the art in this domain, considering also the case m < n which has been less studied. We also recall the method for protecting block ciphers against side channel attacks (SCA) by masking, and how the S-boxes can be processed in order to ensure this protection. We state a related open problem, also interesting for its own sake. We eventually see how Boolean functions, vectorial functions and error correcting codes can be used in different ways for reducing the cost of masking while keeping the same resistance to some SCA and also for allowing resisting fault injection attacks (FIA).
Claude Carlet

### Simulations of Optical Emissions for Attacking AES and Masked AES

Abstract
In this paper we present a novel attack based on photonic emission analysis targeting software implementations of AES. We focus on the particular case in which the attacker can collect the photonic emission of a limited number of sense amplifiers (e.g. only one) of the SRAM storing the S-Box. The attack consists in doing hypothesis on the secret key based on the knowledge of the partial output of the SubBytes operation. We also consider the possibility to attack a masked implementation of AES using the photonic emission analysis. In the case of masking, the attacker needs 2 leakages of the same encryption to overcome the randomization of the masks. For our analysis, we assume the same physical setup described in other previous works. Reported results are based on simulations with some hypothesis on the probability of photonic emission of a single transistor.
Guido M. Bertoni, Lorenzo Grassi, Filippo Melzani

### Fault Tolerant Infective Countermeasure for AES

Abstract
Infective countermeasures have been a promising class of fault attack countermeasures. However, they have been subjected to several attacks owing to lack of formal proofs of security and improper implementations. In this paper, we first provide a formal information theoretic proof of security for one of the most recently proposed state of the art infective countermeasures against DFA, under the assumption that the adversary does not change the flow sequence or skip any instruction. Subsequently, we identify weaknesses in the infection mechanism of the countermeasure that could be exploited by attacks which change the flow sequence. Furthermore, we propose an augmented infective countermeasure scheme obtained by introducing suitable randomizations that reduce the success probabilities of such attacks. All the claims have been validated by supporting simulations and real life experiments on a SASEBO-W platform. We also compare the fault tolerance provided by our proposed countermeasure scheme against that provided by the existing scheme.
Sikhar Patranabis, Abhishek Chakraborty, Debdeep Mukhopadhyay

### Modified Transparency Order Property: Solution or Just Another Attempt

Abstract
S-boxes are usual targets of side-channel attacks and it is an open problem to develop design techniques for S-boxes with improved DPA resistance. One result along that line is the transparency order, a property that attempts to characterize the resilience of S-boxes against DPA attacks. Recently, it was shown there exist flaws with the original definition of transparency, which resulted in the new definition - modified transparency order. This paper develops techniques for constructions using the modified transparency as a guiding metric. For the 4×4 size, we significantly improve modified transparency order while remaining in the optimal classes. Experimental results are provided assuming a noisy HW leakage model to show the proposed S-boxes are more resistant than the original one of the PRESENT algorithm. We conclude with reports on 4×4 and 8×8 S-boxes where the results indicate that the modified transparency order could be a more useful metric than the transparency order. However, both measures are far from definitive solution on how to improve the DPA resistance.
Stjepan Picek, Bodhisatwa Mazumdar, Debdeep Mukhopadhyay, Lejla Batina

### Investigating SRAM PUFs in large CPUs and GPUs

Abstract
Physically unclonable functions (PUFs) provide data that can be used for cryptographic purposes: on the one hand randomness for the initialization of random-number generators; on the other hand individual fingerprints for unique identification of specific hardware components. However, today’s off-the-shelf personal computers advertise randomness and individual fingerprints only in the form of additional or dedicated hardware.
This paper introduces a new set of tools to investigate whether intrinsic PUFs can be found in PC components that are not advertised as containing PUFs. In particular, this paper investigates AMD64 CPU registers as potential PUF sources in the operating-system kernel, the bootloader, and the system BIOS; investigates the CPU cache in the early boot stages; and investigates shared memory on Nvidia GPUs. This investigation found non-random non-fingerprinting behavior in several components but revealed usable PUFs in Nvidia GPUs.
Pol Van Aubel, Daniel J. Bernstein, Ruben Niederhagen

### Reconfigurable LUT: A Double Edged Sword for Security-Critical Applications

Abstract
Modern FPGAs offer various new features for enhanced reconfigurability and better performance. One of such feature is a dynamically Reconfigurable LUT (RLUT) whose content can be updated internally, even during run-time. There are many scenarios like pattern matching where this feature has been shown to enhance the performance of the system. In this paper, we study RLUT in the context of secure applications. We describe the basic functionality of RLUT and discuss its potential applications for security. Next, we design several case-studies to exploit RLUT feature in security critical scenarios. The exploitation are studied from a perspective of a designer (e.g. designing countermeasures) as well as a hacker (inserting hardware Trojans).
Debapriya Basu Roy, Shivam Bhasin, Sylvain Guilley, Jean-Luc Danger, Debdeep Mukhopadhyay, Xuan Thuy Ngo, Zakaria Najm

### Architecture Considerations for Massively Parallel Hardware Security Platform

Building a Workhorse for Cryptography as a Service
Abstract
Cryptography as a service (CaaS) provides means for executing sensitive cryptographic operations when the primary computing platform does not offer the required level of trust and security. Instead of executing operations like document signing directly by an application running in untrusted environment, the operation keys are only present in trusted environment used by CaaS. Once the operation keys are put in place, the applications use a CaaS interface to obtain results of sensitive operations - document signatures - executed by CaaS. A typical scenario is the use of virtual computing platform in the cloud. Use of CaaS reduces impact of the potential compromise of this virtual platform and simplifies subsequent recovery. The attacker will not learn the value of sensitive keys (e.g., signing keys) and is only able to use the keys for a limited time. The CaaS is enabling technology for a large number of use cases where security is important. The concept of scalable and universally available CaaS has also far-reaching usability, security, legal, and economics consequences of cloud use. In this position paper, we focus on requirements for building a CaaS platform – what are the options and challenges to build hardware and software components for CaaS suitable for usage scenarios with different load patterns and user requirements. We propose a suitable architecture for CaaS that can be shared by a large number of concurrent users, i.e., providing access to a large number of cryptographic keys. We also provide practical results from our prototype implementation.
Dan Cvrček, Petr Švenda

### Efficient and Secure Elliptic Curve Cryptography for 8-bit AVR Microcontrollers

Abstract
The AVR family of 8-bit microcontrollers is widely used in several applications demanding secure communications and protection against physical attacks, such as side-channel analysis. In this context, processing, storage and energy demands of cryptographic software must be low, requirements which are met by ECC. At the 128-bit security level, two recently proposed curves are an attractive option for 8-bit microcontrollers: Curve25519 for Diffie-Hellman key exchange, and Ed25519 for signature. Simple power analysis is a significant threat to AVR applications, but efficient and side-channel tested implementations of SPA countermeasures for ECC protocols have not yet been dealt with in this platform, in the literature. This paper describes an efficient implementation of ECDH-Curve25519 and EdDSA-Ed25519-SHA512 for the ATmega328P platform. Our implementation provides protection against timing attacks, SPA and template SPA. The resistance against SPA is evaluated through the test vector leakage assessment (TVLA) methodology based on Welch’s t-test, using the Chipwhisperer platform.
Erick Nascimento, Julio López, Ricardo Dahab

### Towards Practical Attribute-Based Signatures

Abstract
An attribute-based signature (ABS) is a special digital signature created using a dynamic set of issued attributes. For instance, a doctor can sign a medical statement with his name, medical license number and medical speciality. These attributes can be verified along with the signature by any verifier with the correct public keys of the respective attribute issuers. This functionality not only makes ABS a much more flexible alternative to the standard PKI-based signatures, but also offers the ability to create privacy-preserving signatures. However, none of the ABS constructions presented in the literature is practical or easily realizable. In fact, to the best of our knowledge, there is currently no ABS implementation used in practice anywhere. This is why we put forward a new ABS technique based on the IRMA attribute-based authentication. IRMA already has an efficient and practical smart-card implementation, and an experimental smart-phone implementation too. They are currently used in several pilot projects.
In this paper, we propose an ABS scheme based on the existing IRMA technology, extending the currently available IRMA devices with ABS functionality. We study the practical issues that arise due to the introduction of the signature functionality to an existing attribute-based authentication scheme, and we propose possible cryptographic and infrastructural solutions. We also discuss use cases and implementation aspects.
Brinda Hampiholi, Gergely Alpár, Fabian van den Broek, Bart Jacobs

### Hierarchical Ring Signatures Revisited – Unconditionally and Perfectly Anonymous Schnorr Version

Abstract
We propose a ring signature scheme that creates short signatures for large rings. The scheme allows signers to reuse previously created signatures to enlarge the ring size without expanding the size of signature itself. The relation between signatures is a tree structure in which each signature is a node built upon its predecessors. The set of potential signers of a node grows exponentially with the tree height while the size of the signature may remain even constant. We give the specific example of the scheme built on the top of Schnorr ring signatures. We prove its unconditional anonymity and unforgeability in ROM.
Łukasz Krzywiecki, Małgorzata Sulkowska, Filip Zagórski

### Compact Accumulator Using Lattices

Abstract
An accumulator is a succinct aggregate of a set of values where it is possible to issue short membership proofs for each accumulated value. A party in possession of such a membership proof can then demonstrate that the value is included in the set. In this paper, we present the first lattice-based accumulator scheme that issues compact membership proofs. The security of our scheme is based on the hardness of the Short Integer Solution problem.

### Almost Optimum Secret Sharing with Cheating Detection

Abstract
A (t,n, δ) secret sharing scheme with cheating detection property (SSCD) is a t-out-of-n threshold secret sharing scheme that has the following additional property; the probability that any t malicious players can successfully cheat (without being caught) an honest player by opening forged shares and causing the honest player to reconstruct the wrong secret is at most δ. There are two flavors of security for such schemes known as OKS and CDV. The lower bound on share sizes for an OKSsecure SSCD scheme is known, and concrete schemes in which share sizes are equal to (or almost the same as) the lower bound have been proposed, albeit with some limitations. We first present a OKSsecure scheme with share sizes only one bit longer than its existing lower bound. Our construction is free from any special requirements. We next present a CDVsecure SSCD scheme, where a stronger form of cheating is allowed. The share size of our CDVsecure scheme is also one bit longer than the existing lower bound.