Security, Privacy, and Applied Cryptography Engineering

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.

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.

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.

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.

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.

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 2⁴⁹⁶ and memory complexity of 2¹¹². 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 2⁵⁰⁵ and memory complexity of 2¹¹².

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 2^66.11 and 2^66.19, respectively. Both attacks require the same data and memory complexities of 2⁵¹ chosen plaintexts and 2^64.8 64-bit blocks, respectively.

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 2⁴⁹ chosen plaintexts, time complexity of 2^114.8 8-Sbox layers Hierocrypt-L1 encryptions and memory complexity of 2¹⁰⁶ 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.

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).

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.

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.

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.

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.

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).

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.

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.

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.

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.

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 OKS−secure 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 OKS−secure 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 CDV−secure SSCD scheme, where a stronger form of cheating is allowed. The share size of our CDV−secure scheme is also one bit longer than the existing lower bound.