Topics in Cryptology – CT-RSA 2009

Identity-Based Encryption (IBE) offers an interesting alternative to PKI-enabled encryption as it eliminates the need for digital certificates. While revocation has been thoroughly studied in PKIs, few revocation mechanisms are known in the IBE setting. Until quite recently, the most convenient one was to augment identities with period numbers at encryption. All non-revoked receivers were thus forced to obtain a new decryption key at discrete time intervals, which places a significant burden on the authority. A more efficient method was suggested by Boldyreva, Goyal and Kumar at CCS’08. In their

revocable

IBE scheme, key updates have logarithmic (instead of linear in the original method) complexity for the trusted authority. Unfortunately, security could only be proved in the selective-ID setting where adversaries have to declare which identity will be their prey at the very beginning of the attack game. In this work, we describe an adaptive-ID secure

revocable

IBE scheme and thus solve a problem left open by Boldyreva

et al.

.

In [14], Boneh and Katz introduced a primitive called

encapsulation

scheme, which is a special kind of commitment scheme. Using the encapsulation scheme, they improved the generic transformation by Canetti, Halevi, and Katz [17] which transforms any semantically secure identity-based encryption (IBE) scheme into a chosen-ciphertext secure public key encryption (PKE) scheme (we call the

BK transformation

). The ciphertext size of the transformed PKE scheme directly depends on the parameter sizes of the underlying encapsulation scheme. In this paper, by designing a size-efficient encapsulation scheme, we further improve the BK transformation. With our proposed encapsulation scheme, the ciphertext overhead of a transformed PKE scheme via the BK transformation can be that of the underlying IBE scheme plus 384-bit, while the original BK scheme yields that of the underlying IBE scheme plus at least 704-bit, for 128-bit security. Our encapsulation scheme is constructed from a pseudorandom generator (PRG) that has a special property called

near collision resistance

, which is a fairly weak primitive. As evidence of it, we also address how to generically construct a PRG with such a property from any one-way permutation.

We introduce the first universally anonymous, thus key-private, IBE whose security is based on the standard quadratic residuosity assumption. Our scheme is a variant of Cocks IBE (which is not anonymous) and is efficient and highly parallelizable.

Digital Enhanced Cordless Telecommunications (DECT) is a standard for connecting cordless telephones to a fixed telecommunications network over a short range. The cryptographic algorithms used in DECT are not publicly available. In this paper we reveal one of the two algorithms used by DECT, the DECT Standard Authentication Algorithm (DSAA). We give a very detailed security analysis of the DSAA including some very effective attacks on the building blocks used for DSAA as well as a common implementation error that can practically lead to a total break of DECT security. We also present a low cost attack on the DECT protocol, which allows an attacker to impersonate a base station and therefore listen to and reroute all phone calls made by a handset.

In this paper we study key exchange protocols in a model where the key exchange takes place between devices with limited displays that can be compared by a human user. If the devices display the same value then the human user is convinced that the key exchange terminated successfully and securely, and if they do not then the user knows that it came under attack. The main result of this paper is a rigorous proof that the numeric comparison mode for device pairing in Bluetooth version 2.1 is secure, under appropriate assumptions regarding the cryptographic functions used. Our proof is in the standard model and in particular does not model any of the functions as random oracles. In order to prove our main result, we present formal definitions for key exchange in this model and show our definition to be equivalent to a simpler definition. This is a useful result of independent interest that facilitates an easier security analysis of protocols in this model.

Key insulation (KI) and Intrusion resilience (IR) are methods to protect a user’s key against exposure by utilizing periodic communications with an auxiliary helper. But existing work assumes a secure channel between user and helper. If we want to realize KI or IR in practice we must realize this secure channel. This paper looks at the question of how to do this when the communication is over what we are more likely to have in practice, namely a public channel such as the Internet or a wireless network. We explain why this problem is not trivial, introduce models and definitions that capture the desired security in a public channel setting, and provide a complete (and surprising) answer to the question of when KI and IR are possible over a public channel. The information we provide is important to guide practitioners with regard to the usage of KI and IR and also to guide future research in this area.

Zero-knowledge set is a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003) which enables a prover to commit a set to a verifier, without revealing even the size of the set. Later the prover can give zero-knowledge proofs to convince the verifier of membership/non-membership of elements in/not in the committed set. We present a new primitive called

Statistically Hiding Sets

(SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee, rather than one based on efficient simulation. Then we present a new scheme for statistically hiding sets, which does not fit into the “Merkle-tree/mercurial-commitment” paradigm that has been used for

all

zero-knowledge set constructions so far. This not only provides efficiency gains compared to the best schemes in that paradigm, but also lets us provide

statistical

hiding; previous approaches required the prover to maintain growing amounts of state with each new proof for such a statistical security.

Our construction is based on an algebraic tool called

trapdoor DDH groups

(TDG), introduced recently by Dent and Galbraith (ANTS 2006). However the specific hardness assumptions we associate with TDG are different, and of a strong nature — strong RSA and a knowledge-of-exponent assumption. Our new knowledge-of-exponent assumption may be of independent interest. We prove this assumption in the generic group model.

In the setting of multiparty computation a set of parties with private inputs wish to compute some joint function of their inputs, whilst preserving certain security properties (like privacy and correctness). An adaptively secure protocol is one in which the security properties are preserved even if an adversary can adaptively and dynamically corrupt parties during a computation. This provides a high level of security, that is arguably necessary in today’s world of active computer break-ins. Until now, the work on adaptively secure multiparty computation has focused almost exclusively on the setting of an honest majority, and very few works have considered the honest minority and two-party cases. In addition, significant computational and communication costs are incurred by most protocols that achieve adaptive security.

In this work, we consider the two-party setting and assume that honest parties may

erase

data. We show that in this model it is possible to securely compute any two-party functionality in the presence of

adaptive semi-honest adversaries

. Furthermore, our protocol remains secure under concurrent general composition (meaning that it remains secure irrespective of the other protocols running together with it). Our protocol is based on Yao’s garbled-circuit construction and, importantly, is as efficient as the analogous protocol for static corruptions. We argue that the model of adaptive corruptions with erasures has been unjustifiably neglected and that it deserves much more attention.

A redactable signature scheme for a string of objects supports verification even if multiple substrings are removed from the original string. It is important that the redacted string and its signature do not reveal anything about the content of the removed substrings. Existing schemes completely or partially leak a piece of information: the lengths of the removed substrings. Such length information could be crucial in many applications, especially when the removed substring has low entropy. We propose a scheme that can hide the length. Our scheme consists of two components. The first component

$\mathcal{H}$

, which is a “collision resistant” hash, maps a string to an unordered set, whereby existing schemes on unordered sets can then be applied. However, a sequence of random numbers has to be explicitly stored and thus it produces a large signature of size at least (

mk

)-bits where

m

is the number of objects and

k

is the size of a key sufficiently large for cryptographic operations. The second component uses RGGM tree, a variant of GGM tree, to generate the pseudo random numbers from a short seed, expected to be of size

O

(

k

 + 

tk

log

m

) where

t

is the number of removed substrings. Unlike GGM tree, the structure of the proposed RGGM tree is random. By an intriguing statistical property of the random tree, the redacted tree does not reveal the lengths of the substrings removed. The hash function

$\mathcal{H}$

and the RGGM tree can be of independent interests.

On-line/Off-line signatures are used in a particular scenario where the signer must respond quickly once the message to be signed is presented. The idea is to split the signing procedure into two phases: the off-line and on-line phases. The signer can do some pre-computations in off-line phase before he sees the message to be signed.

In most of these schemes, when signing a message

m

, a partial signature of

m

is computed in the off-line phase. We call this part of signature the off-line signature token of message

m

. In some special applications, the off-line signature tokens might be exposed in the off-line phase. For example, some signers might want to transmit off-line signature tokens in the off-line phase in order to save the on-line transmission bandwidth. Another example is in the case of on-line/off-line threshold signature schemes, where off-line signature tokens are unavoidably exposed to all the users in the off-line phase.

This paper discusses this exposure problem and introduces a new notion: divisible on-line/off-line signatures, in which exposure of off-line signature tokens in off-line phase is allowed. An efficient construction of this type of signatures is also proposed. Furthermore, we show an important application of divisible on-line/off-line signatures in the area of on-line/off-line threshold signatures.

We describe a new tool for the search of collisions for hash functions. The tool is applicable when an attack is based on a differential trail, whose probability determines the complexity of the attack. Using the linear algebra methods we show how to organize the search so that many (in some cases — all) trail conditions are always satisfied thus significantly reducing the number of trials and the overall complexity.

The method is illustrated with the collision and second preimage attacks on the compression functions based on Rijndael. We show that slow diffusion in the Rijndael (and AES) key schedule allows to run an attack on a version with a 13-round compression function, and the S-boxes do not prevent the attack. We finally propose how to modify the key schedule to resist the attack and provide lower bounds on the complexity of the generic differential attacks for our modification.

The Zémor-Tillich hash function has remained unbroken since its introduction at CRYPTO’94. We present the first

generic

collision and preimage attacks against this function, in the sense that the attacks work for any parameters of the function. Their complexity is the

cubic root

of the birthday bound; for the parameters initially suggested by Tillich and Zémor they are very close to being practical. Our attacks exploit a separation of the collision problem into an easy and a hard component. We subsequently present two variants of the Zémor-Tillich hash function with essentially the same collision resistance but reduced outputs of 2

n

and

n

bits instead of the original 3

n

bits. Our second variant keeps only the hard component of the collision problem; for well-chosen parameters the best collision attack on it is the birthday attack.

In this paper, we present a statistical saturation attack that combines previously introduced cryptanalysis techniques against block ciphers. As the name suggests, the attack is statistical and can be seen as a particular example of partitioning cryptanalysis. It extracts information about the key by observing non-uniform distributions in the ciphertexts. It can also be seen as a dual to saturation (

aka

square, integral) attacks in the sense that it exploits the diffusion properties in block ciphers and a combination of active and passive multisets of bits in the plaintexts. The attack is chosen-plaintext in its basic version but can be easily extended to a known-plaintext scenario. As an illustration, it is applied to the block cipher PRESENT proposed by Bogdanov

et al.

at CHES 2007. We provide theoretical arguments to predict the attack efficiency and show that it improves previous (linear, differential) cryptanalysis results. We also provide experimental evidence that we can break up to 15 rounds of PRESENT with 2

35.6

plaintext-ciphertext pairs. Eventually, we discuss the attack specificities and possible countermeasures. Although dedicated to PRESENT, it is an open question to determine if this technique improves the best known cryptanalysis for other ciphers.

In this paper we analyze recently introduced questions for masked logic styles in general and for one such logic style called MDPL in particular. The DPA resistance of MDPL suffers significantly from a problem called early propagation, which denotes a data-dependent time of evaluation of logic cells depending on input signal-delay differences. Experiments on a prototype chip show that in case of specific MDPL modules like the analyzed AES coprocessor, early propagation does not unconditionally break the DPA resistance of MDPL. Investigations indicate that this might be due to the regular structure of the particular MDPL circuit, which is assumed to cause only relatively “small” signal delay differences. Furthermore, in this article it is shown that the recently proposed, so-called PDF-attack could not be turned into a successful practical attack in our environment. Finally, the recently raised question whether MDPL has special requirements in terms of the generation of random mask bits or not is discussed theoretically.

CTC is a toy cipher designed in order to assess the strength of algebraic attacks. While the structure of CTC is deliberately weak with respect to algebraic attacks, it was claimed by the designers that CTC is secure with respect to statistical attacks, such as differential and linear cryptanalysis. After a linear attack on CTC was presented, the cipher’s linear transformation was tweaked to offer more diffusion, and specifically to prevent the existence of 1-bit to 1-bit approximations (and differentials) through the linear transformation. The new cipher was named CTC2, and was analyzed by the designers using algebraic techniques.

In this paper we analyze the security of CTC2 with respect to differential and differential-linear attacks. The data complexities of our best attacks on 6-round, 7-round, and 8-round variants of CTC2 are 64, 2

15

, and 2

37

chosen plaintexts, respectively, and the time complexities are dominated by the time required to encrypt the data.

Our findings show that the diffusion of CTC2 is relatively low, and hence variants of the cipher with a small number of rounds are relatively weak, which may explain (to some extent) the success of the algebraic attacks on these variants.

We show that a recently proposed construction by Rosen and Segev can be used for obtaining the first public key encryption scheme based on the McEliece assumptions which is secure against adaptive chosen ciphertext attacks in the standard model.

We propose and analyze a multivariate encryption scheme that uses odd characteristic and an embedding in its construction. This system has a very simple core map

F

(

X

) = 

X

2

, allowing for efficient decryption. We also discuss ways to make this decryption faster with specific parameter choices. We give heuristic arguments along with experimental data to show that this scheme resists all known attacks.

We design communication efficient two-party and multi-party protocols for the longest common subsequence (LCS) and related problems. Our protocols achieve privacy with respect to passive adversaries, under reasonable cryptographic assumptions. We benefit from the somewhat surprising interplay of an efficient block-retrieval PIR (Gentry-Ramzan, ICALP 2005) with the classic “four Russians” algorithmic design. This result is the first improvement to the communication complexity for this application over generic results (such as Yao’s garbled circuit protocol) and, as such, is interesting as a contribution to the theory of communication efficiency for secure two-party and multiparty applications.

Proxy re-encryption (PRE) allows a proxy to convert a ciphertext encrypted under one key into an encryption of the same message under another key. The main idea is to place as little trust and reveal as little information to the proxy as necessary to allow it to perform its translations. At the very least, the proxy should not be able to learn the keys of the participants or the content of the messages it re-encrypts. However, in all prior PRE schemes, it is easy for the proxy to determine between which participants a re-encryption key can transform ciphertexts. This can be a problem in practice. For example, in a secure distributed file system, content owners may want to use the proxy to help re-encrypt sensitive information

without

revealing to the proxy the

identity

of the recipients.

In this work, we propose key-private (or anonymous) re-encryption keys as an additional useful property of PRE schemes. We formulate a definition of what it means for a PRE scheme to be secure and key-private. Surprisingly, we show that this property is not captured by prior definitions or achieved by prior schemes, including even the secure obfuscation of PRE by Hohenberger et al. (TCC 2007). Finally, we propose the first key-private PRE construction and prove its CPA-security under a simple extension of Decisional Bilinear Diffie Hellman assumption and its key-privacy under the Decision Linear assumption in the standard model.

We present the first dynamic universal accumulator that allows (1) the accumulation of elements in a DDH-hard group

$\mathbb{G}$

and (2) one who knows

x

such that

y

 = 

g

x

has — or has

not

— been accumulated, where

g

generates

$\mathbb{G}$

, to efficiently prove her knowledge of such

x

in zero knowledge, and hence without revealing, e.g.,

x

or

y

.

We introduce the

Attribute-Based Anonymous Credential System

, which allows the verifier to authenticate anonymous users according to any access control policy expressible as a formula of

possibly negated

boolean user attributes. We construct the system from our accumulator.

In many applications, it is desirable to work with signatures that are short, and yet where

many

messages from

different

signers be verified very quickly. RSA signatures satisfy the latter condition, but are generally thousands of bits in length. Recent developments in pairing-based cryptography produced a number of “short” signatures which provide equivalent security in a fraction of the space. Unfortunately, verifying these signatures is computationally intensive due to the expensive pairing operation. Toward achieving “short and fast” signatures, Camenisch, Hohenberger and Pedersen (Eurocrypt 2007) showed how to

batch verify

two pairing-based schemes so that the total number of pairings was independent of the number of signatures to verify.

In this work, we present both theoretical and practical contributions. On the theoretical side, we introduce new batch verifiers for a wide variety of regular, identity-based, group, ring and aggregate signature schemes. These are the first constructions for batching group signatures, which answers an open problem of Camenisch et al. On the practical side, we implement each of these algorithms and compare each batching algorithm to doing individual verifications. Our goal is to test whether batching is practical; that is, whether the benefits of removing pairings significantly outweigh the cost of the additional operations required for batching, such as group membership testing, randomness generation, and additional modular exponentiations and multiplications. We experimentally verify that the theoretical results of Camenisch et al. and this work, indeed, provide an efficient, effective approach to verifying multiple signatures from (possibly) different signers.

We study the problem of traversing a hash chain with dynamic helper points (called pebbles). Basically, two kinds of algorithms for this problem are known to date. Jakobsson algorithm is a single-layer fractal algorithm with the computational cost of ⌈log

n

⌉ (hash evaluations per chain link) and ⌈log

n

⌉ pebbles. Coppersmith-Jakobsson algorithm is a complicated double-layer fractal algorithm that improves efficiency at the expense of simplicity; with a complex movement pattern and some extra pebbles, it reduces the computational cost by half. Specifically, Coppersmith-Jakobsson algorithm requires

$\lfloor \frac{1}{2}\log n \rfloor$

hash evaluations per chain link and ⌈log

n

⌉ + ⌈log(log

n

 + 1) ⌉ pebbles, which attains an almost optimal complexity. We introduce a new hash chain traversal algorithm that achieves both simplicity and efficiency. While our algorithm is based on the simple single-layer fractal structure of the Jakobsson algorithm, it reduces the computational cost by half without using extra pebbles; specifically,

$\lceil \frac{1}{2}\log n \rceil$

hash evaluations per chain link and ⌈log

n

⌉ pebbles are needed.

A technique for computing the quotient (

$\lfloor ab/n \rfloor$

) of Euclidean divisions from the difference of two remainders

$(ab \pmod{n} - ab \pmod{n+1})$

was proposed by Fischer and Seifert. The technique allows a 2ℓ-bit modular multiplication to work on most ℓ-bit modular multipliers. However, the cost of the quotient computation rises sharply when computing modular multiplications larger than 2ℓ bits with a recursive approach. This paper addresses the computation cost and improves on previous 2ℓ-bit modular multiplication algorithms to return not only the remainder but also the quotient, resulting in an higher performance in the recursive approach, which becomes twice faster in the quadrupling case and four times faster in the octupling case. In addition to Euclidean multiplication, this paper proposes a new 2ℓ-bit Montgomery multiplication algorithm to return both of the remainder and the quotient.

Bit-decomposition of secret shared values – securely computing sharings of the binary representation – is an important primitive in multi-party computation. The problem of performing this task in a constant number of rounds has only recently been solved.

This work presents a novel approach at constant-rounds bit-decomposition. The basic idea provides a solution matching the big-

$\mathcal{O}$

-bound of the original while decreasing the hidden constants. More importantly, further solutions

improve

asymptotic complexity with only a small increase in constants, reducing it from

$\mathcal O(\ell{\rm log}(\ell))$

to

$\mathcal O({\ell}{\rm log}^*(\ell))$

and even lower. Like previous solutions, the present one is unconditionally secure against both active and adaptive adversaries.

Broad impossibility results have been proven regarding the feasibility of obtaining protocols that remain secure under concurrent composition when there is no honest majority. These results hold both for the case of general composition (where a secure protocol is run many times concurrently with arbitrary other protocols) and self composition (where a single secure protocol is run many times concurrently). One approach for bypassing these impossibility results is to consider more limited settings of concurrency. In this paper, we investigate a restriction that we call

local sequentiality

. In this setting, every honest party in the multi-party network runs its protocol executions strictly sequentially (thus, sequentiality is preserved locally, but not globally). Since security is preserved under global sequential composition, one may conjecture that it also preserved under local sequentiality. However, we show that local sequentiality does

not

help. That is, any protocol that is secure under local sequentiality is also secure under concurrent self composition (when the scheduling is fixed). Thus, known impossibility results apply.

We show a simple chosen-ciphertext attack against a public key encryption scheme with non-interactive opening (PKENO) presented by Damgård, Kiltz, Hofheinz and Thorbek in CT-RSA 2008. In a PKENO scheme a receiver can convincingly reveal to a verifier what the result of decrypting a ciphertext

C

is, without interaction and without compromising the confidentiality of non-opened ciphertexts. A special interesting feature of PKENO is that a verifier can even ask for opening proofs on invalid ciphertexts. Those opening proofs will convince the verifier that the ciphertext was indeed invalid. We show that one of the schemes by Damgård

et al.

does not achieve the claimed security goal. Next we provide a fix for it. The repaired scheme presents essentially no overhead and is proven secure under the Decisional Bilinear Diffie-Hellman assumption in the standard model.

OAEP is one of the few standardized and widely deployed public-key encryption schemes. It was designed by Bellare and Rogaway as a scheme based on a trapdoor permutation such as RSA. RSA-OAEP is standardized in RSA’s PKCS #1 v2.1 and is part of several standards. RSA-OAEP was shown to be IND-CCA secure in the random oracle model under the standard RSA assumption. However, the reduction is not tight, meaning that the guaranteed level of security is not very high for a practical parameter choice. We first observe that the situation is even worse because the analysis was done in the single-query setting, i.e. where an adversary gets a single challenge ciphertext. This does not take into account the fact that in reality an adversary can observe multiple ciphertexts of related messages. The results about the multi-query setting imply that the guaranteed concrete security can degrade by a factor of

q

, which is the number of challenge ciphertexts an adversary can get. We re-visit a very simple but not well-known modification of the RSA-OAEP encryption which asks that the RSA function is only applied to a part of the OAEP transform. We show that in addition to the previously shown fact that security of this scheme is tightly related to the hardness of the RSA problem, security does not degrade as the number of ciphertexts an adversary can see increases. Moreover, this scheme can be used to encrypt long messages without using hybrid encryption. We believe that this modification to the RSA-OAEP is easy to implement, and the benefits it provides deserves the attention of standard bodies.

After attacking the RSA by injecting fault and corresponding countermeasures, works appear now about the need for protecting RSA public elements against fault attacks. We provide here an extension of a recent attack [BCG08] based on the public modulus corruption. The difficulty to decompose the

“Left-To-Right”

exponentiation into partial multiplications is overcome by modifying the public modulus to a number with known factorization. This fault model is justified here by a complete study of faulty prime numbers with a fixed size. The good success rate of this attack combined with its practicability raises the question of using faults for changing algebraic properties of finite field based cryptosystems.

This paper reports a successful Fault Analysis (FA) attack against a prototype AES (Advanced Encryption Standard) hardware implementation using a logic-level countermeasure called Random Switching Logic (RSL). The idea of RSL was proposed as one of the most effective countermeasures for preventing Differential Power Analysis (DPA) attacks. The RSL technique was applied to AES and a prototype ASIC was implement with a 0.13-

μ

m standard CMOS library. Although the main purpose of using RSL is to enhance the DPA resistance, our evaluation results for the ASIC reveal that the DPA countermeasure of RSL can negatively affect the resistance against FA attacks. We show that the circuits using RSL has a potential vulnerability against FA attacks by increasing the clock frequency.

Radio-frequency identification (RFID) is an emerging technology that has found its way into many applications, even in security related areas. Integration of cryptographic algorithms into RFID tags is necessary and the implementation of them needs to be secure against side-channel analysis (SCA) attacks. RFID tags operating in the ultra-high frequency (UHF) range are susceptible to so-called parasitic-backscatter attacks, which can be applied from a distance. In this article, we evaluate the efficiency of the detached power-supply countermeasure by applying it to a smart card and performing differential power analysis (DPA) attacks. Consecutively, we discuss the suitability of this countermeasure for protecting passive UHF tags from parasitic-backscatter attacks. The results show that the non-ideal properties of the analog switches used by the detached power supply decrease the effectiveness of this countermeasure. Moreover, we have identified side-channel leakage at the I/O pin of the smart card as a considerable problem for the detached power-supply approach. We conclude that utilizing the detached power supply to protect passive UHF tags from parasitic-backscatter attacks is feasible, if the integration interval is sufficiently long and the analog switches have adequate properties. However, longer integration intervals also increase the power loss of the tag, resulting in reduced read ranges.

Fault Analysis is a powerful cryptanalytic technique that enables to break cryptographic implementations embedded in portable devices more efficiently than any other technique. For an RSA implemented with the Chinese Remainder Theorem method, one faulty execution suffices to factorize the public modulus and fully recover the private key. It is therefore mandatory to protect embedded implementations of RSA against fault analysis.

This paper provides a new countermeasure against fault analysis for exponentiation and RSA. It consists in a

self-secure

exponentiation algorithm, namely an exponentiation algorithm that provides a direct way to check the result coherence. An RSA implemented with our solution hence avoids the use of an extended modulus (which slows down the computation) as in several other countermeasures. Moreover, our exponentiation algorithm involves 1.65 multiplications per bit of the exponent which is significantly less than the 2 required by other self-secure exponentiations.