Applied Cryptography and Network Security

We enrich the classical notion of group key exchange (GKE) protocols by a new property that allows each pair of users to derive an independent

peer-to-peer (p2p) key

on-demand and without any subsequent communication; this, in addition to the classical

group key

shared amongst all the users. We show that GKE protocols enriched in this way impose new security challenges concerning the secrecy and independence of both key types. The special attention should be paid to possible collusion attacks aiming to break the secrecy of p2p keys possibly established between any two non-colluding users.

In our constructions we utilize the well-known parallel Diffie-Hellman key exchange (PDHKE) technique in which each party uses the same exponent for the computation of p2p keys with its peers. First, we consider PDHKE in GKE protocols where parties securely transport their secrets for the establishment of the group key. For this we use an efficient multi-recipient ElGamal encryption scheme. Further, based on PDHKE we design a generic compiler for GKE protocols that extend the classical Diffie-Hellman method. Finally, we investigate possible optimizations of these protocols allowing parties to

re-use

their exponents to compute both group and p2p keys, and show that not all such GKE protocols can be optimized.

In the paper “Stronger Security of Authenticated Key Exchange” [1, 2], a new security model for authenticated key exchange protocols (eCK) is proposed. The new model is suggested to be at least as strong as previous models for key exchange protocols. The model includes a new notion of an

Ephemeral Key Reveal

adversary query, which is claimed in e.g. [2,3, 4] to be at least as strong as the

Session-state Reveal

query. We show that

Session-state Reveal

is stronger than

Ephemeral Key Reveal

, implying that the eCK security model is incomparable to the CK model [5, 6]. In particular we show that the proposed NAXOS protocol from [1, 2] does not meet its security requirements if the

Session-state Reveal

query is allowed in the eCK model. We discuss the implications of our result for some related protocols proven correct in the eCK model, and discuss the interaction between

Session-state Reveal

and protocol transformations.

“Secure Device Pairing” is the process of bootstrapping secure communication between two devices over a short- or medium-range wireless channel (such as Bluetooth, WiFi). The devices in such a scenario can neither be assumed to have a prior context with each other nor do they share a common trusted authority. Fortunately, the devices can generally be connected using auxiliary physical channel(s) (such as audio, visual, tactile) that can be authenticated by the device user(s), thus forming the basis for pairing. However, lack of good quality output interfaces (e.g, a speaker, display) and/or receivers (e.g., microphone, camera) on certain devices makes pairing a very challenging problem in practice.

We consider the problem of “

rushing user

” behavior in device pairing. A rushing user is defined as a user who in a rush to connect her devices, would skip through the pairing process, if possible. Most prior pairing methods, in which the user decides the final outcome of pairing, are vulnerable to rushing user behavior – the user can simply “accept” the pairing, without having to correctly take part in the decision process. In this paper, we concentrate on most common pairing scenarios (such as pairing of a WiFi laptop and an access point), whereby one device (access point) is constrained in terms output interfaces, while the other (laptop) has a decent quality output interface but no receiver. We present the design and usability analysis of two novel pairing methods, which are resistant to a rushing user and require only minimal device interfaces on the constrained device. One of the most appealing applications of our proposal is in defending against common threat of “Evil Twin” attacks in public places (e.g, cyber-cafes, airport lounges).

We examine the use of randomness extraction and expansion in key agreement (KA) protocols to generate uniformly random keys in the standard model. Although existing works provide the basic theorems necessary, they lack details or examples of appropriate cryptographic primitives and/or parameter sizes. This has lead to the large amount of min-entropy needed in the (non-uniform) shared secret being overlooked in proposals and efficiency comparisons of KA protocols. We therefore summarize existing work in the area and examine the security levels achieved with the use of various extractors and expanders for particular parameter sizes. The tables presented herein show that the shared secret needs a min-entropy of at least 292 bits (and even more with more realistic assumptions) to achieve an overall security level of 80 bits using the extractors and expanders we consider. The tables may be used to find the min-entropy required for various security levels and assumptions. We also find that when using the short exponent theorems of Gennaro et al., the short exponents may need to be much longer than they suggested.

We present an innovative technique to add elliptic curve points with the form

P

±

Q

, and discuss its application to the generation of precomputed tables for the scalar multiplication. Our analysis shows that the proposed schemes offer, to the best of our knowledge, the lowest costs for precomputing points on both single and multiple scalar multiplication and for various elliptic curve forms, including the highly efficient Jacobi quartics and Edwards curves.

Two-party Secure Function Evaluation (SFE) is a very useful cryptographic tool which allows two parties to evaluate a function known to both parties on their private (secret) inputs. Some applications with sophisticated privacy needs require the function to be known only to one party and kept private (hidden) from the other one. However, existing solutions for SFE of private functions (PF-SFE) deploy Universal Circuits (UC) and are still very inefficient in practice.

In this paper we bridge the gap between SFE and PF-SFE with SFE of what we call

semi-private functions

(SPF-SFE), i.e., one function out of a given class of functions is evaluated without revealing which one.

We present a general framework for SPF-SFE allowing a fine-grained trade-off and tuning between SFE and PF-SFE covering both extremes. In our framework, semi-private functions can be composed from several privately programmable blocks (PPB) which can be programmed with one function out of a class of functions. The framework allows efficient and secure embedding of constants into the resulting circuit to improve performance. To show practicability of the framework we have implemented a compiler for SPF-SFE based on the Fairplay SFE framework.

SPF-SFE is sufficient for many practically relevant privacy-preserving applications, such as privacy-preserving credit checking which can be implemented with our framework and compiler as described in the paper.

This paper examines secure two-party computation of functions which depend only on the Hamming distance of the inputs of the two parties. We present efficient protocols for computing these functions. In particular, we present protocols which are secure in the sense of full simulatability against malicious adversaries.

We show different applications of this family of functions, including a protocol we call

m

-point-SPIR, which is an efficient variant of symmetric private information retrieval (SPIR). It can be used if the server’s database contains

N

entries, at most

N

/log

N

of which have individual values, and the rest are set to some default value. This variant of PIR is unique since it can be based on the existence of OT alone.

Computing Set Intersection privately and efficiently between two mutually mistrusting parties is an important basic procedure in the area of private data mining. Assuring robustness, namely, coping with potentially arbitrarily misbehaving (i.e., malicious) parties, while retaining protocol efficiency (rather than employing costly generic techniques) is an open problem. In this work the first solution to this problem is presented.

We propose a new variant of the Cramer-Shoup KEM (key encapsulation mechanism). The proposed variant is more efficient than the original Cramer-Shoup KEM scheme in terms of public key size and encapsulation cost, but is proven to be (still) secure against chosen ciphertext attack in the standard model, relative to the Decisional Diffie-Hellman problem.

In this paper, we present an efficient Identity-based Online / Offline Encryption (IBOOE) scheme. An IBOOE scheme allows one to split the encryption into two phases. In the offline phase, most heavy computations such as exponentiation or pairing, if any, are done in this phase. Yet it does not require the knowledge of the plaintext or the receiver’s identity. This nice property allows it can be executed ‘offline’, or inside some powerful device. The next phase is called the online phase, where only light computations such as integer addition, multiplication or hashing are needed, together with the plaintext and the receiver’s identity. This can be executed inside some embedded device such as smart card or wireless sensor where the computation power is very limited. We propose an efficient IBOOE scheme, with great improvement in the computation requirement of both the offline, online encryption phase and decryption phase, together with much shorten ciphertext over previous schemes. Our scheme can be proven secure in the random oracle model.

We present a new variant of Attribute based encryption (ABE) called Dual-Policy ABE. Basically, it is a conjunctively combined scheme between Key-Policy and Ciphertext-Policy ABE, the two previous available types of ABE. Dual-Policy ABE allows

simultaneously

two access control mechanisms over encrypted data: one involves policies over

objective

attributes ascribed to data and the other involves policies over

subjective

attributes ascribed to user credentials. The previous two types of ABE can only allow either functionality above one at a time.

In this paper, we propose a notion of threshold tag-based encryption schemes that simplifies the notion of threshold identity-based encryption schemes, and we show a conversion from any stag-CCA-secure threshold tag-based encryption schemes to CCA-secure threshold public-key encryption schemes. Moreover, we give two concrete constructions of stag-CCA-secure threshold tag-based encryption schemes, under the decisional bilinear Diffie-Hellman assumption and the decisional linear assumption, respectively. Thus, we obtain two concrete constructions of threshold public-key encryption schemes, both of which are non-interactive, robust and can be proved secure without random oracle model. Our threshold public-key encryption schemes are conceptually more simple and shown to be more efficient than those of Boneh, Boyen and Halevi.

Malware analysis is critical for malware detection and prevention. To defeat malware analysis and detection, today malware commonly adopts various sophisticated anti-detection techniques, such as performing debugger, emulator, and virtual machine fingerprinting, and camouflaging its traffic as normal legitimate traffic. These mechanisms produce more and more stealthy malware that greatly challenges existing malware analysis schemes.

In this work, targeting application level stealthy malware, we propose Malyzer,

the key of which is to defeat malware anti-detection mechanisms at startup and runtime so that malware behavior during execution can be accurately captured and distinguished.

For analysis, Malyzer always starts a copy, referred to as a shadow process, of any suspicious process on the same host by defeating all startup anti-detection mechanisms employed in the process. To defeat internal runtime anti-detection attempts, Malyzer further makes this shadow process mutually invisible to the original suspicious process. To defeat external anti-detection attempts, Malyzer makes as if the shadow process runs on a different machine to the outside. Since ultimately malware will conduct local information harvesting or dispersion, Malyzer constantly monitors the shadow process’s behavior and adopts a hybrid scheme for its behavior analysis. In our experiments, Malyzer can accurately detect all malware samples that employ various anti-detection techniques.

We examine the problem of message recognition by reviewing the definitions and the security model in the literature. In particular, we examine the Jane Doe protocol, which was proposed by Lucks et al., more closely and note its inability to recover in case of a certain adversarial disruption. Our paper saves this well-studied protocol from its unrecoverable state when such adversarial disruption occurs. We propose a new message recognition protocol, which is based on the Jane Doe protocol, and incorporate the resynchronization technique within the protocol itself. That is, without having to provide a separate resynchronization procedure, we overcome the recoverability problem of the Jane Doe protocol. Moreover, we enumerate all possible attacks against the new protocol and show that none of the attacks can occur. We further prove the security of the new protocol and its ability to self-recover once the disruption has stopped.

In 2004, Matsushita and Imai proposed a

k

-resilient public-key traitor tracing scheme which has sublinear ciphertext size 4

k

 + 2 + (

n

/2

k

) with efficient black-box tracing against self-defensive pirates, where

n

,

k

are the total number of subscribers and the maximum number of colluders. After that, in 2006, they presented a hierarchical key assignment method to reduce the ciphertext size into 4

k

 + 5 + log(

n

/2

k

) by combining a complete binary tree with the former scheme.

In this paper, we show that the proposed schemes are vulnerable to our attack which makes pirate keys able to avoid the black-box tracing. Their schemes are based on multiple polynomials and our attack use a combination between different polynomials. The latter scheme can be broken by other attacks which use secret values of the key generation polynomial or use partial keys.

All content distribution systems are vulnerable to the attack of rebroadcasting: in a pirate rebroadcast a pirate publishes the content in violation of the licensing agreement. This attack defeats any tracing mechanism that requires interaction with the pirate decoder for identifying compromised keys. Merely tracing pirate rebroadcasts is of little use and one should be also able to revoke the involved traitor keys. The only currently known scheme addressing this issue is implemented as part of the Advanced Access Content System (AACS) used in Blu-Ray and HD-DVD disks. In this paper we perform an analysis of this construction and we find it has serious limitations: the number of revocations is bound by the size of the receiver storage (for the actual parameters reported this is merely 85 keys).

We address the limitations of the state of the art (i) by formally modeling the problem of tracing and revoking pirate rebroadcasts and (ii) by presenting the first efficient constructions of tracing and revoking pirate rebroadcasts that are capable of performing tracing for

unlimited numbers

of traitors and revoking

unlimited numbers

of users. We present three instantiations of our framework: our first construction achieves a linear communication overhead in the number of revoked users and traitors and is capable of eliminating a pirate rebroadcast by any number of traitors in time that depends logarithmically in the number of users and polynomially on the number of revocations and traitors. Our second construction assumes a fixed bound on the number of traitors and improves the elimination time to depend only logarithmically on the number of revocations. Both of these constructions require merely a binary marking alphabet. Our third construction utilizes a larger marking alphabet and achieves even faster pirate rebroadcast elimination; our analysis improves the previously known bound for the same alphabet size due to Fiat and Tassa from Crypto’99 while offering revocation explicitly.

Releasing a classical digital signature faces to privacy issues. Indeed, there are cases where the prover needs to authenticate some data without making it possible for any malicious verifier to transfer the proof to anyone else. It is for instance the case for e-passports where the signature from the national authority authenticates personal data. To solve this problem, we can prove knowledge of a valid signature without revealing it. This proof should be non-transferable.

We first study deniability for signature verification. Deniability is essentially a weaker form of non-transferability. It holds as soon as the protocol is finished (it is often called offline non-transferability).

We introduce Offline Non-Transferable Authentication Protocol (ONTAP) and we show that it can be built by using a classical signature scheme and a deniable zero-knowledge proof of knowledge. For that reason, we use a generic transform for

Σ

-protocols.

Finally, we give examples to upgrade signature standards based on RSA or ElGamal into an ONTAP. Our examples are well-suited for implementation in e-passports.

Network coding has been shown to improve the capacity and robustness in networks. However, since intermediate nodes modify packets en-route, integrity of data cannot be checked using traditional MACs and checksums. In addition, network coded systems are vulnerable to pollution attacks where a single malicious node can flood the network with bad packets and prevent the receiver from decoding the packets correctly. Signature schemes have been proposed to thwart such attacks, but they tend to be too slow for online per-packet integrity.

Here we propose a

homomorphic MAC

which allows checking the integrity of network coded data. Our homomorphic MAC is designed as a drop-in replacement for traditional MACs (such as HMAC) in systems using network coding.

Though Gennaro et al. discussed the algorithmic tamper proof (ATP) devices using the personal identification number (PIN) with less tamper-proof devices, and proposed counter units which count the number of wrong attempts in user authentication; however, as for the counter unit, they only constructed one which counts the

total

number of wrong attempts. Although large number for the limit of wrong attempts is required for usability, it allows an attacker to search PIN up to the limit and degrades the security. The construction of secure counter units which count the number of

consecutive

wrong attempts remains as an open problem. In this paper, we first formalize the ATP security of counter units, and propose two constructions of counter unit which count the number of consecutive wrong attempts. The security of each construction can be proven under the assumptions of secure signature scheme and random function. The former one is required to store two states in secure memory area (

RP

 − 

Mem

) with low computation cost; and the latter one has high computation cost but is required to store only one state in

RP

 − 

Mem

. This shows the trade-off between the costs of hardware and algorithm.

Being able to access and provide Internet services anonymously is an important mechanism to ensure freedom of speech in vast parts of the world. Offering location-hidden services on the Internet requires complex redirection protocols to obscure the locations and identities of communication partners. The anonymity system Tor supports such a protocol for providing and accessing TCP-based services anonymously. The complexity of the hidden service protocol results in significantly higher response times which is, however, a crucial barrier to user acceptance. This communication overhead becomes even more evident when using limited access networks like cellular phone networks. We provide comprehensive measurements and statistical analysis of the bootstrapping of client processes and different sub-steps of the Tor hidden service protocol under the influence of limited access networks. Thereby, we are able to identify bottlenecks for low-bandwidth access networks and to suggest improvements regarding these networks.

In this paper, we present a semi-free-start collision attack on the compression function for all Twister variants with negligible complexity. We show how this compression function attack can be extended to construct collisions for Twister-512 slightly faster than brute force search. Furthermore, we present a second-preimage and preimage attack for Twister-512 with complexity of about 2

384

and 2

456

compression function evaluations, respectively.

CubeHash

is a family of hash functions submitted by Bernstein as a

SHA-3

candidate. In this paper, we provide two different cryptanalysis approaches concerning its collision resistance. Thanks to the first approach, related to truncated differentials, we computed a collision for the

CubeHash

-1/36 hash function, i.e. when for each iteration 36 bytes of message are incorporated and one call to the permutation is applied. Then, the second approach, already used by Dai, much more efficient and based on a linearization of the scheme, allowed us to compute a collision for the

CubeHash

-2/4 hash function. Finally, a theoretical collision attack against

CubeHash

-2/3,

CubeHash

-4/4 and

CubeHash

-4/3 is described. This is currently by far the best known cryptanalysis result on this

SHA-3

candidate.

Boole is a hash function designed by Gregory Rose and was submitted to the NIST Hash competition. It is a stream cipher based hash function which produces digests up to 512 bits. Different variants exist, namely Boole16, Boole32 and Boole64 where the number refers to word size in bits. Boole64 is considered as the official submission. In this paper we demonstrate a collision attack with complexity 2

65

for the 64-bit variant and 2

33

for the 32-bit variant. The amount of memory required is negligible. Since the attack on Boole32 is practical, we present an example for a collision.

Users of online-collaboration tools and network storage services place considerable trust in their providers. This paper presents a novel approach for protecting data integrity in revision control systems hosted by an untrusted provider. It guarantees atomic read and write operations on the shared data when the service is correct and preserves fork-linearizability when the service is faulty. A prototype has been implemented on top of the Subversion revision control system; benchmarks show that the approach is practical.

The upcoming 802.11w amendment to the 802.11 standard eliminates the 802.11 deauthentication and disassociation Denial of Service (DoS) vulnerabilities. This paper presents two other DoS vulnerabilities: one vulnerability in draft 802.11w implementations discovered by IEEE 802.11 TGw, and one new vulnerability in 802.11, which is still present in the 802.11w amendment. Attacks exploiting the first vulnerability are significantly more efficient than any known 802.11 DoS attacks, while attacks exploiting the second vulnerability have efficiency and feasability equivalent to a disassociation attack. This paper provides an experimental verification of these attacks, demonstrating their feasability using freely available software and off the shelf hardware. Finally, the root cause of these vulnerabilities is discussed and a backwards compatible solution proposed.

Rule-based packet classification plays a central role in network intrusion detection systems such as Snort. To enhance performance, these rules are typically compiled into a

matching automaton

that can quickly identify the subset of rules that are applicable to a given network packet. The principal metrics in the design of such an automaton are its size and the time taken to match packets at runtime. Previous techniques for this problem either suffered from high space overheads (i.e., automata could be exponential in the number of rules), or matching time that increased quickly with the number of rules. In contrast, we present a new technique that constructs polynomial size automata. Moreover, we show that the matching time of our automata is insensitive to the number of rules. Our experimental results demonstrate substantial improvements in space requirements, as well the runtime of Snort.

We present the new NTRUEncrypt parameter generation algorithm, which is designed to be secure in light of recent attacks that combine lattice reduction and meet-in-the-middle (MITM) techniques. The parameters generated from our algorithm have been submitted to several standard bodies and are presented at the end of the paper.

In 1988, Håstad proposed the classical broadcast attack against public key cryptosystems. The scenario of a broadcast attack is as follows. A single message is encrypted by the sender directed for several recipients who have different public keys. By observing the ciphertexts only, an attacker can derive the plaintext without requiring any knowledge of any recipient’s secret key. Håstad’s attack was demonstrated on the RSA algorithm, where low exponents are used. In this paper, we consider the broadcast attack in the lattice-based cryptography, which interestingly has never been studied in the literature. We present a general method to rewrite lattice problems that have the same solution in one unique easier problem. Our method is obtained by intersecting lattices to gather the required knowledge. These problems are used in lattice based cryptography and to model attack on knapsack cryptosystems. In this work, we are able to present some attacks against both lattice and knapsack cryptosystems. Our attacks are heuristics. Nonetheless, these attacks are practical and extremely efficient. Interestingly, the merit of our attacks is not achieved by exploring the weakness of the trapdoor as usually studied in the literature, but we merely concentrate on the problem itself. As a result, our attacks have many security implications on most of the lattice-based or knapsack cryptosystems.

Consider CRT-RSA with

N

 = 

pq

,

q

 < 

p

 < 2

q

, public encryption exponent

e

and private decryption exponents

d

p

,

d

q

. Jochemsz and May (Crypto 2007) presented that CRT-RSA is weak when

d

p

,

d

q

are smaller than

N

0.073

. As a follow-up work of that paper, we study the partial key exposure attack on CRT-RSA when some Most Significant Bits (MSBs) of

d

p

,

d

q

are exposed. Further, better results are obtained when a few MSBs of

p

(or

q

) are available too. We present theoretical results as well as experimental evidences to justify our claim. We also analyze the case when the decryption exponents are of different bit sizes and it is shown that CRT-RSA is more insecure in this case (than the case of

d

p

,

d

q

having the same bit size) considering the total bit size of

d

p

,

d

q

.

Side-channel attacks are an important class of attacks against cryptographic devices and profiled side-channel attacks are the most powerful type of side-channel attacks. In this scenario, an adversary first uses a device under his control in order to build a good leakage model. Then, he takes advantage of this leakage model to exploit the actual leakages of a similar target device and perform a key recovery. Since such attacks are divided in two phases (namely profiling and online attack), the question of how to best evaluate those two phases arises. In this paper, we take advantage of a recently introduced framework for the analysis of side-channel attacks to tackle this issue. We show that the quality of a profiling phase is nicely captured by an information theoretic metric. By contrast, the effectiveness of the online key recovery phase is better measured with a security metric. As an illustration, we use this methodology to compare the two main techniques for profiled side-channel attacks, namely template attacks and stochastic models. Our results confirm the higher profiling efficiency of stochastic models when reasonable assumptions can be made about the leakages of a device.

A large variety of side channel analyses performed on embedded devices involve the linear correlation coefficient as wrong-key distinguisher. This coefficient is actually a sound statistical tool to quantify linear dependencies between univariate variables. However, when those dependencies are non-linear, the correlation coefficient stops being pertinent so that another statistical tool must be investigated. Recent works showed that the

Mutual Information

measure is a promising candidate, since it detects any kind of statistical dependency. Substituting it for the correlation coefficient may therefore be considered as a natural extension of the existing attacks. Nevertheless, the first applications published at CHES 2008 have revealed several limitations of the approach and have raised several questions. In this paper, an in-depth analysis of side channel attacks involving the mutual information is conducted. We expose their theoretical foundations and we assess their limitations and assets. Also, we generalize them to higher orders where they seem to be an efficient alternative to the existing attacks. Eventually, we provide simulations and practical experiments that validate our theoretical analyses.

The elliptic curve digital signature algorithm (ECDSA) is used in many devices to provide authentication. In the last few years, more and more ECDSA implementations have been proposed that allow the integration into resource-constrained devices like RFID tags. Their resistance against power-analysis attacks has not been scrutinized so far. In this article, we provide first results of power-analysis attacks on an RFID device that implements ECDSA. To this end, we designed and implemented a passive RFID-tag prototype. The core element of the prototype is a low-power ECDSA implementation realized on 180 nm CMOS technology. We performed power and electromagnetic attacks on that platform and describe an attack that successfully reveals the private-key during signature generation. Our experiments confirm that ECDSA-enabled RFID tags are susceptible to these attacks. Hence, it is important that they implement countermeasures which prevent the forging of digital signatures.