Topics in Cryptology – CT-RSA 2007

mv3 is a new word based stream cipher for encrypting long streams of data. A direct adaptation of a byte based cipher such as rc4 into a 32- or 64-bit word version will obviously need vast amounts of memory. This scaling issue necessitates a look for new components and principles, as well as mathematical analysis to justify their use. Our approach, like rc4’s, is based on rapidly mixing random walks on directed graphs (that is, walks which reach a random state quickly, from any starting point). We begin with some well understood walks, and then introduce nonlinearity in their steps in order to improve security and show long term statistical correlations are negligible. To minimize the short term correlations, as well as to deter attacks using equations involving successive outputs, we provide a method for sequencing the outputs derived from the walk using three revolving buffers. The cipher is fast — it runs at a speed of less than 5 cycles per byte on a Pentium IV processor. A word based cipher needs to output more bits per step, which exposes more correlations for attacks. Moreover we seek simplicity of construction and transparent analysis. To meet these requirements, we use a larger state and claim security corresponding to only a fraction of it. Our design is for an adequately secure word-based cipher; our very preliminary estimate puts the security close to exhaustive search for keys of size ≤ 256 bits.

SHACAL-1 is a 160-bit block cipher with variable key length of up to 512-bit key based on the hash function SHA-1. It was submitted to the NESSIE project and was accepted as a finalist for the 2nd phase of evaluation. Since its introduction, SHACAL-1 withstood extensive cryptanalytic efforts. The best known key recovery attack on the full cipher up to this paper has a time complexity of about 2⁴²⁰ encryptions.

In this paper we use an observation due to Saarinen to present an elegant related-key attack on SHACAL-1. The attack can be mounted using two to eight unknown related keys, where each additional key reduces the time complexity of retrieving the actual values of the keys by a factor of 2⁶². When all eight related-keys are used, the attack requires 2^101.3 related-key chosen plaintexts and has a running time of 2^101.3 encryptions. This is the first successful related-key key recovery attack on a cipher with varying round constants.

We mathematically explore a model for the shortness and security for passwords that are stored in hashed form. The model is implicitly in the NIST publication [8] and is based on conditions of the Shannon, Guessing and Min Entropy. We establish various new relations between these three notions of entropy, providing strong improvements on existing bounds such as the McEliece-Yu bound from [7] and the Min entropy lowerbound on Shannon entropy [3]. As an application we present an algorithm generating near optimally short passwords given certain security restrictions. Such passwords are specifically applicable in the context of one time passwords (e.g. initial passwords, activation codes).

The task of developing protocols for humans to securely authenticate themselves to a remote server has been an interesting topic in cryptography as a replacement for the traditional, less secure, password based systems. The protocols proposed in literature are based on some underlying difficult mathematical problem, which are tuned so as to make them easily computable by humans. As a result these protocols are easily broken when desired to be efficiently executable. We present a Human Identification Protocol based on the ability of humans to efficiently process an image given a secret predicate. It is a challenge-response protocol in which a subset of images presented satisfies a secret predicate shared by the challenger and the user. We conjecture that it is hard to guess this secret predicate for adversaries, both humans and programs. It can be efficiently executed by humans with the knowledge of the secret which in turn is easily memorable and replaceable. We prove the security of the protocol separately for human adversaries and programs based on two separate assumptions and justify these assumptions with the help of an example implementation.

This article presents a rare case of a deterministic second preimage attack on a cryptographic hash function. Using the notion of controllable output differences, we show how to construct second preimages for the SMASH hash functions. If the given preimage contains at least n + 1 blocks, where n is the output length of the hash function in bits, then the attack is deterministic and requires only to solve a set of n linear equations. For shorter preimages, the attack is probabilistic.

A digital signature scheme that achieves an optimal bandwidth (generating signatures as short as possible) is called an optimal signature scheme. The previous optimal signature schemes all need the random permutations (or the ideal ciphers) with large block size as building blocks. However, the practical cipher with large block size such as Halevi and Rogaway’s CMC-mode should call the underlying secure block cipher with small block size many times each time. This makes the previous optimal signature schemes which use the large domain permutation (or the ideal cipher) less efficient in the real world, even if there exist the methods that can encipher the messages with larger domain. On the other hand, all the practical signature schemes are not optimal in bandwidth including PSS-R, FDH, DSA, etc. Hence, the problem on how to design a practical, efficient and optimal signature scheme remains open.

This paper uses two random oracles and an ideal cipher with a smaller block size to design an optimal padding for signature schemes. The ideal cipher in our scheme can be implemented with a truly real block cipher (e.g. AES). Therefore, we provide a perfect solution to the open problem. More precisely, we design a practical, efficient and optimal signature scheme. Particularly, in the case of RSA, the padding leads the signature scheme to achieve not only optimality in bandwidth but also a tight security.

In 2002, Micali and Rivest raised an open problem as to whether directed transitive signatures exist or not. In 2003, Hohenberger formalized the necessary mathematical criteria for generic directed transitive signature scheme, showing that the edge signatures in such a scheme form a special (and powerful) mathematical group, called Abelian trapdoor group with infeasible inversion, which is not known to exist. In this paper, we consider a directed graph whose transitive reduction is a directed tree, on which we propose a natural RSA-based directed transitive signature scheme \(\mathcal{RSADTS}\). In this particular case, we have answered the open problem raised by Micali and Rivest. We have proved that \(\mathcal{RSADTS}\), associated to a standard digital signature scheme, is transitively unforgeable under adaptive chosen-message attack if the RSA inversion problem over a cyclic group is hard and the standard digital signature is secure. Furthermore, \(\mathcal{RSADTS}\) has even better performance than \(\mathcal{RSATS}\)-1 in certain circumstance.

Multi-signatures allow multiple signers to jointly authenticate a message using a single compact signature. Many applications however require the public keys of the signers to be sent along with the signature, partly defeating the effect of the compact signature. Since identity strings are likely to be much shorter than randomly generated public keys, the identity-based paradigm is particularly appealing for the case of multi-signatures. In this paper, we present and prove secure an identity-based multi-signature (IBMS) scheme based on RSA, which in particular does not rely on (the rather new and untested) assumptions related to bilinear maps. We define an appropriate security notion for interactive IBMS schemes and prove the security of our scheme under the one-wayness of RSA in the random oracle model.

At Financial Crypto 2006, Golle presented a novel framework for the privacy preserving computation of a stable matching (stable marriage). We show that the communication complexity of Golle’s main protocol is substantially greater than what was claimed in that paper, in part due to surprising pathological behavior of Golle’s variant of the Gale-Shapley stable matching algorithm. We also develop new protocols in Golle’s basic framework with greatly reduced communication complexity.

Known compact e-cash schemes are constructed from signature schemes with efficient protocols and verifiable random functions. In this paper, we introduce a different approach. We construct compact e-cash schemes from bounded accumulators. A bounded accumulator is an accumulator with a limit on the number of accumulated values. We show a generic construction of compact e-cash schemes from bounded accumulators and signature schemes with certain properties and instantiate it using an existing pairing-based accumulator and a new signature scheme. Our scheme revokes the secret key of the double-spender directly and thus supports more efficient coin tracing. The new signature scheme has an interesting property that is has the message space of a cyclic group \(\mathbb{G}_1\) equipped with a bilinear pairing, with efficient protocol to show possession of a signature without revealing the signature nor the message. We show that the new scheme is secure in the generic group model. The new signature scheme may be of independent interest.

We present a new design principle for building a batch processing protocol for interactive proofs. First, a generic method to achieve batch processing is proposed when dealing with an NP-relation with certain homomorphicity. It is shown that the method preserves zero-knowledgeness and knowledge-soundness. Second, for some NP-relation that has no such homomorphicity, we illustrate that the relation can be decomposed into a homomorphic relation(hence we have a batch process) and another NP-relation that is proven using an efficient protocol. Such a decomposition provides an advantage in terms of efficiency.

This report studies timing attacks on NTRUEncrypt based on variation in the number of hash calls made on decryption. The attacks apply to the parameter sets of [8,6]. To mount the attacker, an attacker performs a variable amount of precomputation, then submits a relatively small number of specially constructed ciphertexts for decryption and measures the decryption times. Comparison of the decryption times with the precomputed data allows the attacker to recover the key in greatly reduced time compared to standard attacks on NTRUEncrypt. The precomputed data can be used for all keys generated with a specific parameter set and tradeoffs exist that increase the amount of precomputation in order to decrease the time required to recover an individual key. For parameter sets in [3] that claim k-bit security but are vulnerable to this attack, we find that an attacker can typically recover a single key with about k/2 bits of effort.

Finally, we describe a simple means to prevent these attacks by ensuring that all operations take a constant number of SHA calls. The recommended countermeasure does not break interoperability with the parameter sets of [8,6] and has only a slight effect on performance.

In this article we discuss different types of template attacks on masked implementations. All template attacks that we describe are applied in practice to a masked AES software implementation on an 8-bit microcontroller. They all break this implementation. However, they all require quite a different number of traces. It turns out that a template-based DPA attack leads to the best results. In fact, a template-based DPA attack is the most natural way to apply a template attack to a masked implementation. It can recover the key from about 15 traces. All other attacks that we present perform worse. They require between about 30 and 1800 traces. There is no difference between the application of a template-based DPA attack to an unmasked and to a masked implementation. Hence, we conclude that in the scenario of template attacks, masking does not improve the security of an implementation.

Side-channel attacks on block ciphers and public key algorithms have been discussed extensively. However, there is only sparse literature about side-cannel attacks on stream ciphers. The few existing references mainly treat timing [8] and template attacks [10], or provide a theoretical analysis [6], [7] of weaknesses of stream cipher constructions. In this paper we present attacks on two focus candidates, Trivium and Grain, of the eSTREAM stream cipher project. The attacks exploit the resynchronization phase of ciphers. A novel concept for choosing initial value vectors is introduced, which totally eliminates the algorithmic noise of the device, leaving only the pure side-channel signal. This attack allows to recover the secret key with a small number of samples and without building templates. To prove the concept we apply the attack to hardware implementations of the ciphers. For both stream ciphers we are able to reveal the complete key.

We introduce a new robust cache-based timing attack on AES. We present experiments and concrete evidence that our attack can be used to obtain secret keys of remote cryptosystems if the server under attack runs on a multitasking or simultaneous multithreading system with a large enough workload. This is an important difference to recent cache-based timing attacks as these attacks either did not provide any supporting experimental results indicating if they can be applied remotely, or they are not realistically remote attacks.

Privacy concerns in many aspects of electronic communication trigger the need to re-examine – with privacy in mind – familiar security services, such as authentication and key agreement.

An Affiliation-Hiding Group Key Agreement (AH-AGKA) protocol (also known as Group Secret Handshake) allows a set of participants, each with a certificate issued by the same authority, to establish a common authenticated secret key. In contrast to standard AGKA protocols, an AH-AGKA protocol has the following privacy feature: If Alice, who is a member of a group G, participates in an AH-AGKA protocol, none of the other protocol participants learn whether Alice is a member of G, unless these participants are themselves members of group G. Such protocols are useful in suspicious settings where a set of members of a (perhaps secret) group need to authenticate each other and agree on a common secret key, without revealing their affiliations to outsiders.

In this paper, we propose an efficient password-authenticated key exchange (PAKE) based on RSA, called RSA-EPAKE. Unlike SNAPI using a prime pubic key e greater than an RSA modulus n, RSA-EPAKE uses the public key e of a 96-bit prime, where e = 2H(n, s) + 1 for some s. By the Prime Number Theorem, it is easy to find such an s. But the probability that an adversary finds n and s with \(\gcd(e, \phi(n)) \neq 1\) is less than 2^− 80. Hence, in the same as SNAPI, RSA-EPAKE is also secure against e-residue attacks. The computational load on Alice (or Server) and Bob (or Client) in RSA-EPAKE is less than in the previous RSA-based PAKEs such as SNAPI, PEKEP ,CEKEP, and QR-EKE. In addition, the computational load on Bob in RSA-EPAKE is less than in PAKEs based on Diffie-Hellman key exchange (DHKE) with a 160-bit exponent. If we exclude perfect forward secrecy from consideration, the computational load on Alice is a little more than that in PAKEs based on DHKE with a 160-bit exponent. In this paper, we compare RSA-EPAKE with SNAPI, PEKEP, and CEKEP in computation and the number of rounds, and provide a formal security analysis of RSA-EPAKE under the RSA assumption in the random oracle model.

The concept of erasure-tolerant information authentication was recently introduced to study an unconditionally secure setting where it is allowed to lose a limited number of message letters during transmission. Even if a part of the message is lost, the verifier will still be able to check the authenticity of some or all of the received message letters. In general, there might be some letters whose authenticity cannot be verified although they have arrived at the recipient’s side. These letters will be discarded.

We consider a special case when the verifier can always check the authenticity of all received message letters. This property is desirable since no data will be lost due to the verifier’s inability to verify its authenticity (i.e., the scheme does not introduce additional degradation of the quality of the received information). We provide necessary and sufficient conditions for a set system based erasure-tolerant authentication scheme to be non-degrading. We also discuss efficient implementations and propose a provably secure stream authentication scheme that makes use of erasure-tolerant authentication codes.

In 1999, two signature schemes based on the flexible RSA problem (a.k.a. strong RSA problem) were independently introduced: the Gennaro-Halevi-Rabin (GHR) signature scheme and the Cramer-Shoup (CS) signature scheme. Remarkably, these schemes meet the highest security notion in the standard model. They however differ in their implementation. The CS scheme and its subsequent variants and extensions proposed so far feature a loose security reduction, which, in turn, implies larger security parameters. The security of the GHR scheme and of its twinning-based variant are shown to be tightly based on the flexible RSA problem but additionally (i) either assumes the existence of division-intractable hash functions, or (ii) requires an injective mapping into the prime numbers in both the signing and verification algorithms.

In this paper, we revisit the GHR signature scheme and completely remove the extra assumption made on the hash functions without relying on injective prime mappings. As a result, we obtain a practical signature scheme (and an on-line/off-line variant thereof) whose security is solely and tightly related to the strong RSA assumption.

Standard signature schemes are usually designed only to achieve weak unforgeability – i.e. preventing forgery of signatures on new messages not previously signed. However, most signature schemes are randomised and allow many possible signatures for a single message. In this case, it may be possible to produce a new signature on a previously signed message. Some applications require that this type of forgery also be prevented – this requirement is called strong unforgeability.

At PKC2006, Boneh Shen and Waters presented an efficient transform based on any randomised trapdoor hash function which converts a weakly unforgeable signature into a strongly unforgeable signature and applied it to construct a strongly unforgeable signature based on the CDH problem. However, the transform of Boneh et al only applies to a class of so-called partitioned signatures. Although many schemes fall in this class, some do not, for example the DSA signature. Hence it is natural to ask whether one can obtain a truly generic efficient transform based on any randomised trapdoor hash function which converts any weakly unforgeable signature into a strongly unforgeable one. We answer this question in the positive by presenting a simple modification of the Boneh-Shen-Waters transform. Our modified transform uses two randomised trapdoor hash functions.

This work presents a bit-slice implementation of the Whirlpool hash function for 64-bit CPUs, which processes a single input block in one pass. It describes the general approach for developing the formulas and presents the results. This implementation does not need table lookups that depend on the data, which makes it immune against cache timing attacks, e.g. if used in an HMAC. Moreover, it requires 63% less memory (code and data) than the reference implementation of Whirlpool, and the performance of an implementation in C that uses some SSE2 instructions is only about 40% less. Additional improvements seem possible.