Applied Cryptography and Network Security

Recently, there are several generic transformation techniques proposed for converting unforgeable signature schemes (the message in the forgery has not been signed yet) into strongly unforgeable ones (the message in the forgery could have been signed previously). Most of the techniques are based on trapdoor hash functions and all of them require adding supplementary components onto the original key pair of the signature scheme. In this paper, we propose a new generic transformation which converts

any

unforgeable signature scheme into a strongly unforgeable one, and also keeps the key pair of the signature scheme unchanged. Our technique is based on

strong one-time signature schemes

. We show that they can be constructed efficiently from any one-time signature scheme that is based on one-way functions. The performance of our technique also compares favorably with that of those trapdoor-hash-function-based ones. In addition, this new generic transformation can also be used for attaining strongly unforgeable signature schemes in other cryptographic settings which include certificateless signature, identity-based signature, and several others. To the best of our knowledge, similar extent of versatility is not known to be supported by any of those comparable techniques. Finally and of independent interest, we show that our generic transformation technique can be modified to an

on-line/off-line

signature scheme, which possesses a very efficient signing process.

The “hash-sign-switch” paradigm was firstly proposed by Shamir and Tauman with the aim to design an efficient on-line/off-line signature scheme. However, all existing on-line/off-line signature schemes based on Shamir-Tauman’s paradigm suffer from the key exposure problem of chameleon hashing. That is, if the signer applies the same hash value more than once to obtain two signatures on two different messages, the recipient can obtain a hash collision and use it to recover the signer’s trapdoor information. Therefore, the signer should pre-compute and store plenty of different chameleon hash values and the corresponding signatures on the hash values in the off-line phase, and send the collision and the signature for a certain hash value in the on-line phase. Hence, the computation and storage cost for the off-line phase and the communication cost for the on-line phase in Shamir-Tauman’s signature scheme are still a little more overload.

In this paper, we first introduce a special double-trapdoor hash family based on the discrete logarithm assumption to solve this problem. We then apply the “hash-sign-switch” paradigm to propose a much more efficient generic on-line/off-line signature scheme. Additionally, we use a one-time trapdoor/hash key pair for each message signing, which prevents the recipient from recovering the trapdoor information of the signer and computing other collisions.

We propose GMSS, a new variant of the Merkle signature scheme. GMSS is the first Merkle-type signature scheme that allows a

cryptographically unlimited

(2

80

) number of documents to be signed with one key pair. Compared to recent improvements of the Merkle signature scheme, GMSS reduces the signature size as well as the signature generation cost.

Today’s protocol specifications only define the behaviour of principals representing communication endpoints. But in addition to endpoints, networks contain midpoints, which are machines that observe or filter traffic between endpoints. In this paper, we explain why midpoints should handle protocols differently from endpoints and thus midpoint specifications are needed. With a case study, using the TCP protocol and three different firewalls as midpoints, we illustrate the consequences of the current lack of protocol specifications for midpoints, namely that the same protocol is implemented differently by the different firewalls. We then propose a solution to the problem: We give an algorithm that generates a midpoint automaton from specifications of endpoint automata. We prove that the resulting midpoint automata are correct in that they forward only those messages that could have resulted from protocol-conform endpoints. Finally, we illustrate the algorithm on the TCP protocol.

A successful computer system intrusion is often resulted from an attacker combining exploits of individual vulnerability. This can be modelled by attack models and attack graphs to provide a global view on system security against attacker’s goal. However, as the size and complexity of attack models and attack graphs usually greatly exceeds human ability to visualize, understand and analyze, a scheme is required to identify important portions of attack models and attack graphs. Mehta

et al.

proposed to rank states of an attack model by the probability of an adversary reaching a state by a sequence of exploiting individual vulnerabilities in a previous scheme. Important portions can hence be identified by ranks of states. However, Mehta

et al.

’s ranking scheme is based on the PageRank algorithm which models a web surfing scenario, but has not considered much on the dissimilarity between web surfing scenarios and computer system intrusion scenarios. In this paper, we extend Mehta

et al.

’s scheme by taking into consideration dissimilarity between web surfing scenarios and computer system intrusion scenarios. We experiment with the same network model used in Mehta

et al.

’s scheme and have the results compared. The experiments yielded promising results that demonstrated consistent ranks amongst varying parameters modelled by our ranking scheme.

Untraceability

and

unreuseability

are essential security properties for electronic cash protocols. Many protocols have been proposed to meet these two properties. However, most of them have not been formally proved to be untraceable and unreuseable. In this paper we propose to use the applied pi calculus as a framework for describing and analyzing electronic cash protocols, and we analyze Ferguson’s electronic cash protocol as a case study. We believe that this approach is suitable for many different electronic cash protocols.

In 2006, the inventors of TRMC public key cryptosystem proposed a new variant of TRMC, TRMC-4, which can resist the existing attack, in particular, the Joux et al attack. In this paper, we show that the new version is vulnerable to attack via the linearization equations (LE) method. For any given valid ciphertext and its corresponding TRMC-4 public key, we can derive the corresponding plaintext within 2

24

$\mathbb{F}_{2^8}$

-operations, after performing once for the public key a computation of complexity less than 2

34

. Our results are confirmed by computer experiments.

In the RSA system, balanced modulus

N

denotes a product of two large prime numbers

p

and

q

, where

q

 < 

p

 < 2

q

. Since Integer-Factorization is difficult,

p

and

q

are simply estimated as

${\sqrt{N}}$

. In the Wiener attack,

$2\sqrt{N}$

is adopted to be the estimation of

p

 + 

q

in order to raise the security boundary of private-exponent

d

. This work proposes a novel approach, called EPF, to determine the appropriate prime-factors of

N

. The estimated values are called ”EPFs of

N

”

, and are denoted as

p

E

and

q

E

. Thus

p

E

and

q

E

can be adopted to estimate

p

 + 

q

more accurately than by simply adopting

$2\sqrt{N}$

. In addition, we show that the Verheul and Tilborg’s extension of the Wiener attack can be considered to be brute-guessing for the MSBs of

p

 + 

q

. Comparing with their work, EPF can extend the Wiener attack to reduce the cost of exhaustive-searching for 2

r

 + 8 bits down to 2

r

 − 10 bits, where

r

depends on

N

and the private key

d

. The security boundary of private-exponent

d

can be raised 9 bits again over Verheul and Tilborg’s result.

In this paper, we introduce a timing attack scheme against a 160-bit modular multiplication with Blakley’s algorithm. It is assumed that a set of public inputs are multiplied by a secret parameter and running time of each multiplication is given, but the multiplication result is not known and a machine similar to victim machine isn’t available. The proposed attack extracts all 160 bits of the secret parameter. Running time of Blakley’s algorithm is analyzed and it is shown that running time of each step is dependent on the running time of other steps. The dependencies make the parameters of the attack be dependent on the secret key, while it makes the attack rather complicated. A heuristic algorithm is used to find the parameters of the attack. As a real scenario, the attack is applied against on-line implementation of Digital Signature Algorithm, which employs Blakley’s modular multiplication. Practical results show that secret key of DSA will be found using 1,000,000 timing samples.

The Advanced Encryption Standard is used in many embedded devices to provide security. In the last years, several researchers have proposed to enhance general-purpose processors with custom instructions to increase the efficiency of cryptographic algorithms. In this work we have evaluated the impact of such instruction set extensions on the implementation security of AES. We have compared several AES implementation options which incorporate state-of-the-art software countermeasures against power-analysis attacks—with and without the use of instruction set extensions. For both scenarios we provide a thorough analysis for different countermeasures with regard to security, performance, and memory. We have found that even a moderate level of protection requires a considerable overhead both in terms of speed and memory. The instruction set extensions, which have been solely designed to increase performance, help to reduce this overhead, but it still remains high. An implementation with proper protection through software countermeasures is only feasible in a setting where the need for resistance against power analysis outweighs the need for performance.

Protocols for group key exchange (GKE) are cryptographic algorithms that describe how a group of parties communicating over a public network can come up with a common secret key. Due to their critical role in building secure multicast channels, a number of GKE protocols have been proposed over the years in a variety of settings. However despite many impressive achievements, it still remains a challenging problem to design a secure GKE protocol which scales very well for large groups. Our observation is that all constant-round authenticated GKE protocols providing forward secrecy thus far are not fully scalable, but have a computation complexity that scales only linearly in group size. Motivated by this observation, we propose a new and the first forward-secure authenticated GKE protocol that achieves both constant round complexity and logarithmic computation complexity. In particular, our GKE protocol is fully scalable in all key metrics when considered in the context of a broadcast network. The scalability of the protocol is achieved by using a complete binary tree structure combined with a so-called “nonce-chained authentication technique”. Besides its scalability, our protocol features provable security against active adversaries under the decisional Diffie-Hellman assumption. We provide a rigorous proof of security for the protocol in a well-defined formal model of communication and adversary capabilities. The result of the current work means that forward-secure generation of session keys even for very large groups can be now done both securely and efficiently.

The one-way function tree (OFT) scheme proposed by Balenson

et al.

is widely regarded as an efficient key management solution for multicast communication in large dynamic groups. Following Horng’s claim that the original OFT scheme was vulnerable to a collusion attack, Ku

et al.

studied the collusion attack on OFT and proposed a solution to prevent the attack. The solution, however, requires to broadcast about

h

2

 + 

h

(

h

is the height of the key tree) keys for every eviction operation, whereas the original OFT scheme only requires about

h

keys. This modified OFT scheme thus loses a key advantage that the original OFT has over the logical key hierarchy (LKH) scheme, that is a halving in broadcast size. In this paper, we revisit collusion attacks on the OFT scheme. We generalize the examples of attacks given by Horng and Ku

et al.

to a generic collusion attack on OFT, and derive necessary and sufficient conditions for such an attack to exist. We then show a solution for preventing collusion attacks while minimizing the average broadcast size. Our simulation results show that the proposed solution allows OFT to outperform LKH in many cases.

The practical success of broadcast encryption hinges on the ability to (1) revoke the access of compromised keys and (2) determine which keys have been compromised. In this work we focus on the latter, the so-called

traitor tracing

problem. The first method utilizes a Bayesian hierarchical model to replace a crucial step in a well known tracing algorithm. Previously, this step relied on worst case bounds, which often overestimate the number of tests needed to diagnose compromised keys. The second is an adaptive tracing algorithm that selects forensic tests according to the

information gain

criteria. The results of the tests refine an explicit model of our beliefs that certain keys are compromised. In choosing tests based on this criteria, we significantly reduce the number of tests, as compared to the state-of-the-art techniques, required to identify compromised keys.

Many protocols that are based on homomorphic encryption are private only if a client submits inputs from a limited range

$\mathcal{S}$

. Conditional disclosure of secrets (CDS) helps to overcome this restriction. In a CDS protocol for a set

$\mathcal{S}$

, the client obtains server’s secret if and only if the client’s inputs belong to

$\mathcal{S}$

and thus the server can guard itself against malformed queries. We extend the existing CDS protocols to work over additively homomorphic cryptosystems for every set from

NP/

poly

. The new construction is modular and easy to apply. As an example, we derive a new oblivious transfer protocol with log-squared communication and a millionaire’s protocol with logarithmic communication. We also implement private, universally verifiable and robust multi-candidate electronic voting so that all voters only transmit an encryption of their vote. The only hardness assumption in all these protocols is that the underlying public-key cryptosystem is IND-CPA secure and the plaintext order does not have small factors.

Existing protocols for private set intersection are based on homomorphic public-key encryption and the technique of representing sets as polynomials in the cryptographic model. Based on the ideas of these protocols and the two-dimensional verifiable secret sharing scheme, we propose a protocol for private set intersection in the information-theoretic model. By representing the sets as polynomials, the set intersection problem is converted into the task of computing the common roots of the polynomials. By sharing the coefficients of the polynomials among parties, the common roots can be computed out using the shares. As long as more than 2

n

/3 parties are semi-honest, our protocol correctly computes the intersection of

n

sets, and reveals no other information than what is implied by the intersection and the secrets sets controlled by the active adversary. This is the first specific protocol for private set intersection in the information-theoretic model as far as we know.

Recently there has been a significant amount of work on privacy-preserving set operations, including: set intersection [14,6,21,9], testing set disjointness [17], multi-set operations [18], and set union [16,1,18] . In this paper, we introduce novel protocols for privacy- preserving set union in the malicious adversary model. More specifically, each participant inputs a set of values, and at the end of the protocol, each participant learns the items that are in at least one participant’s set without learning the frequency of the items or which participant(s) contributed specific items. To our knowledge our protocol is the most efficient privacy-preserving set union protocol for the malicious adversary model to date.

Based on the notion of accumulators, we propose a new cryptographic scheme called universal accumulators. This scheme enables one to commit to a set of values using a short accumulator and to efficiently compute a membership witness of any value that has been accumulated. Unlike traditional accumulators, this scheme also enables one to efficiently compute a nonmembership witness of any value that has not been accumulated. We give a construction for universal accumulators and prove its security based on the strong RSA assumption. We further present a construction for dynamic universal accumulators; this construction allows one to dynamically add and delete inputs with constant computational cost. Our construction directly builds upon Camenisch and Lysyanskaya’s dynamic accumulator scheme. Universal accumulators can be seen as an extension to dynamic accumulators with support of nonmembership witness. We also give an efficient zero-knowledge proof protocol for proving that a committed value is not in the accumulator. Our dynamic universal accumulator construction enables efficient membership revocation in an anonymous fashion.

We present the first practical

unlinkable secret handshake

scheme. An unlinkable secret handshake is a two-way authentication protocol in a PKI setting which protects privacy and anonymity of

all

information about the participants to

everyone

except of their intended authentication partners. Namely, if entity A certified by organization

CA

A

wants to authenticate itself only to other entities certified by

CA

A

, and, symmetrically, entity B certified by

CA

B

wants to authenticate itself only to entities also certified by

CA

B

, then a secret handshake protocol authenticates these parties and establishes a fresh shared key between them if and only if

CA

A

 = 

CA

B

and the two parties entered valid certificates for this CA into the protocol. If, however

CA

A

 ≠ 

CA

B

, or

CA

A

 = 

CA

B

but either

A

or

B

is not certified by this CA, the secret handshake protocol reveals

no information

to the participants except of the bare fact that their inputs do not match. In other words, an Unlinkable Secret Handshake scheme is a perfectly private authentication method in the PKI setting: One can establish authenticated communication with parties that possess the credentials required by one’s policy, and at the same time one’s affiliation

and

identity remain perfectly secret to everyone except of the parties to whom one wants to authenticate.

Efficient secret handshake schemes, i.e. authentication protocols which protect the privacy of participants’ affiliations, were proposed before, but participants in these schemes remained

linkable

. Namely, an attacker could recognize all the instances of the protocol executed by the same entity. Secondly, the previous schemes surrendered user’s privacy if the certificates of this user were revoked, and our scheme alleviates this problem as well. Unlinkable schemes were proposed as well, but they either relied on single-use certificates, or did not support revocation, or required instantaneous propagation of revocation information.

Crucial ingredients in our construction of unlinkable secret handshakes are chosen-ciphertext secure key-private encryption and multi-encryption schemes, and the first efficient construction of a key-private group key management scheme, which is a stateful analogue of (key-private) public key broadcast encryption.

In a proxy re-encryption scheme a semi-trusted proxy converts a ciphertext for Alice into a ciphertext for Bob without seeing the underlying plaintext. A number of solutions have been proposed in the public-key setting. In this paper, we address the problem of Identity-Based proxy re-encryption, where ciphertexts are transformed from one

identity

to another. Our schemes are compatible with current IBE deployments and do not require any extra work from the IBE trusted-party key generator. In addition, they are non-interactive and one of them permits multiple re-encryptions. Their security is based on a standard assumption (DBDH) in the random oracle model.

Constructing identification schemes is one of the fundamental problems in cryptography, and is very useful in practice. An identity-based identification (IBI) scheme allows a prover to identify itself to a public verifier who knows only the claimed identity of the prover and some common information. In this paper, we propose a simple and efficient framework for constructing IBI schemes. Unlike some related framework which constructs IBI schemes from some standard identification schemes, our framework is based on some more fundamental assumptions on intractable problems. Depending on the features of the underlying intractable problems presumed in our framework, we can derive IBI schemes secure against passive, active and concurrent adversaries. We show that the framework can capture a large class of schemes currently proposed, and also has the potential to cover many newly constructed schemes. As an example, based on the Katz-Wang standard signature scheme, we propose a new IBI scheme that is secure against active adversaries in a concurrent manner. It can be seen that our framework also help simplify the security proofs for new IBI schemes. Finally, and of independent interest, we define a new notion for proof systems called Witness Dualism. This notion is weaker than that of witness indistinguishable and we show that it is enough for constructing an IBI scheme secure against the most powerful type of adversaries defined.

We present two transforms to acquire chosen ciphertext security from tag based techniques. The first one requires the separability of underlying primitives. By separability, informally, we mean the encryption algorithm has special structures and can process the identity and the message independently. Compared with generic transforms [8],it significantly reduces the ciphertext size overhead with only marginal computation cost. Compared with [11], the only known technique which directly achieves chosen ciphertext secure public key encryption from separable identity based primitives, it only requires selective-Tag/ID security of underlying primitives. Our second transform is less efficient but performs generically. Both transforms preserve the public verifiability of underlying primitives, and can be extended to hierarchical identity based encryption (HIBE) and threshold settings. As an independent interest, we also investigate the security requirements of chameleon hash functions to build strongly unforgeable one-time signatures.

ID-based public key cryptosystem can be a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. Certified e-mail protocols provide for fair exchange in which the intended recipient gets the e-mail content if and only if the mail originator receives an irrefutable receipt for the e-mail. In this paper we present an optimistic certified e-mail protocol in an ID-based setting. The protocol makes use of verifiable encryption of ID-based digital signatures as building blocks. We offer arguments for the fairness, efficiency, and provable security of our new protocol.

We study a new model for data authentication over peer-to-peer (p2p) storage networks, where data items are stored, queried and authenticated in a totally decentralized fashion. The model captures the security requirements of emerging distributed computing applications. We present an efficient construction of a

distributed Merkle tree

(DMT), which realizes an authentication tree over a p2p network, thus extending a fundamental cryptographic technique to distributed environments. We show how our DMT can be used to design an

authenticated distributed hash table

that is secure against replay attacks and consistent with the update history. Our scheme is built on top of a broad class of existing p2p overlay networks and achieves generality by using only the basic functionality of object location. We use this scheme to design the first efficient

distributed authenticated dictionary

.

As various applications of wireless ad hoc networks have been proposed, security has become one of the big research challenges and is receiving increasing attention. Recently, Several security schemes for wireless ad hoc networks have been proposed using identity-based signcryption schemes. However, almost all identity-based signcryption schemes that have been proposed until now are based on a single private key generator, which is not suitable for multi-domain ad hoc networks. In this paper, we propose a new identity-based signcryption scheme based on multiple private key generators, which is more suitable for multi-domain ad hoc networks. We prove its semantical security under the Decisional Bilinear Diffie-Hellman assumption in the random oracle model.

Security of group communication for large mobile wireless sensor network hinges on efficient key distribution and key management mechanism. As the wireless medium is characterized by its lossy nature, reliable communication cannot be assumed in the key distribution schemes. Therefore, self-healing is a good property for key distribution in wireless applications. The main idea of self-healing key distribution scheme is that even if during a certain session some broadcast messages are lost due to network faults, the users are capable of recovering lost session keys on their own, without requesting additional transmission from the group manager. The only requirement for a user to recover the lost session keys, is its membership in the group both before and after the sessions in which the broadcast packets containing the keys are sent. Self-healing approach of key distribution is stateless in the sense that a user who has been off-line for some period is able to recover the lost session keys immediately after coming back on-line. In this paper, we propose two constructions for scalable self-healing key distribution with

t

revocation capability. The novelty of our constructions are that we apply a different and more efficient self-healing mechanism compared to the ones in the literature using one-way key chain. The main improvements that our proposed schemes achieve over previous approaches are

(a)

communication bandwidth reduces from

O

((

tj

 + 

j

 − 

t

 − 1)log

q

) to

O

((

t

 + 1)log

q

), and

(b)

computation costs for our first and second constructions reduce from

O

(2

tj

 + 

j

) to

O

(2

t

 + 1) and

O

(2(

t

2

 + 

t

)) respectively,

where

m

is the maximum number of sessions,

j

is the current session number,

t

is the maximum number of compromised group members that may collude and

q

is a large prime number. We achieve this result without any increase in the storage complexity. The schemes are scalable to very large groups in highly mobile, volatile and hostile network. We prove in an appropriate security framework that our constructions are computationally secure and achieve both forward secrecy and backward secrecy.

We present two broadcast authentication protocols based on delayed key disclosure. Our protocols rely on symmetric-key cryptographic primitives and use cryptographic puzzles to provide efficient broadcast authentication in different application scenarios, including those with resource-constrained wireless devices such as sensor nodes. The strong points of the protocols proposed are that one protocol allows instantaneous message origin authentication, whereas the other has low communication overhead. In addition to formalizing and analyzing these specific protocols, we carry out a general analysis of broadcast authentication protocols based on delayed key disclosure. This analysis uncovers fundamental limitations of this class of protocols in terms of the required accuracy of message propagation time estimations, if the protocols are to guarantee security and run efficiently.

XTR public key system was introduced at Crypto 2000, which is based on a method to present elements of a subgroup of a multiplicative group of a finite field. Its application in cryptographic protocols leads to substantial savings both in communication and computational overhead without compromising security. It was shown how the use of finite extension fields and subgroups can be combined in such a way that the number of bits to be exchanged is reduced by a factor 3.

In this paper we show how to more compress the communication overhead. The compressed XTR leads to a factor 6 reduction in the representation size compared to the traditional representation and achieves as twice compactness as XTR. The computational overhead of it is a little worse than that of XTR, however the compressed XTR requires only about additional 6% computational effort. If finding 4-th roots of unity is pre-computed, then the computational overhead is only 1% compared to that of original XTR. Furthermore, the required size of public key data of it reduces about 26% from that of XTR.

The NTRU cryptosystem is a ring-based public key system using hard problems over lattices. There has been an extensive research on efficient implementation of NTRU operations, including recent results such as Bailey et al.’s software implementation over a resource-constrained device and Gaubatz et al.’s hardware implementation using only 3,000 gates. In this paper, we present a new algorithm to improve further the performance of NTRU. We speed up the encryption and decryption operations of NTRU up to 32% using some temporary memory, and if we can use precomputation, then the speed-up becomes up to 37%. Our method is based on the observation that specific sub-operations are repeated frequently in the underlying polynomial operations of NTRU.

Recently, in order to eliminate the use of certificates in certified public key cryptography and the key-escrow problem in identity based cryptography, the notion of certificateless public key cryptography was introduced. In this paper, to construct an efficient certificateless signature (CLS) scheme, we present a new approach compactly and orthogonally combining short signatures using bilinear maps. Our approach is conceptually simple but effective to improve efficiency greatly. In the proposed CLS scheme a full private key of a user is a single group element and signature verification requires only one pairing operation. In addition, our CLS scheme has a flexible structure which can be easily extended to a certificateless signature scheme with additional properties such as certificateless ring and blind signature schemes.

In PKC 2006, Chow, Boyd and González Neito introduced the notion of security mediated certificateless (SMC) cryptography. SMC cryptography equips certificateless cryptography with instantaneous revocation. They presented a formal security model with two constructions for SMC encryption. This paper studies SMC signatures. We first present a security analysis of a previous attempt by Ju

et al.

in constructing a SMC signature scheme. We then formalize the notion of SMC signatures and propose the first concrete provable scheme without bilinear pairing. Our scheme is existential unforgeable in the random oracle model based on the intractability of the discrete logarithm problem, has a short public key size, and achieves a trust level which is the same as that of a traditional public key signature.

In 1990, Boyar, Chaum, Damgård and Pedersen introduced

convertible undeniable signatures

which limit the self-authenticating property of digital signatures but can be converted by the signer to ordinary signatures. Michels, Petersen and Horster presented, in 1996, an attack on the Elgamal-based seminal scheme of Boyar

et al.

and proposed a repaired version without formal security analysis. In this paper, we modify their protocol so that it becomes a generic one and it provides an advanced feature which permits the signer to universally convert

achronously

all signatures pertaining to a specific time period. We supply a formal security treatment of the modified scheme: we prove, in the generic group model, that the protocol is existentially unforgeable and anonymous under chosen message attacks, assuming new assumptions (though reasonable) on the underlying hash function.