Skip to main content



Symmetric Key Encryption

Cryptanalysis of a Generalized Unbalanced Feistel Network Structure

This paper reevaluates the security of GF-NLFSR, a new kind of generalized unbalanced Feistel network structure that was proposed at ACISP 2009. We show that GF-NLFSR itself reveals a very slow diffusion rate, which could lead to several distinguishing attacks. For GF-NLFSR containing n sub-blocks, we find an n 2-round integral distinguisher by algebraic methods and further use this integral to construct an (n 2 + n − 2)-round impossible differential distinguisher. Compared with the original (3n − 1)-round integral and (2n − 1)-round impossible differential, ours are significantly better.
Another contribution of this paper is to introduce a kind of non-surjective attack by analyzing a variant structure of GF-NLFSR, whose provable security against differential and linear cryptanalysis can also be provided. The advantage of the proposed non-surjective attack is that traditional non-surjective attack is only applicable to Feistel ciphers with non-surjective (non-uniform) round functions, while ours could be applied to block ciphers with bijective ones. Moreover, its data complexity is \(\mathcal{O}(l)\) with l the block length.
Ruilin Li, Bing Sun, Chao Li, Longjiang Qu

Improved Algebraic Cryptanalysis of QUAD, Bivium and Trivium via Graph Partitioning on Equation Systems

We present a novel approach for preprocessing systems of polynomial equations via graph partitioning. The variable-sharing graph of a system of polynomial equations is defined. If such graph is disconnected, then the corresponding system of equations can be split into smaller ones that can be solved individually. This can provide a tremendous speed-up in computing the solution to the system, but is unlikely to occur either randomly or in applications. However, by deleting certain vertices on the graph, the variable-sharing graph could be disconnected in a balanced fashion, and in turn the system of polynomial equations would be separated into smaller systems of near-equal sizes. In graph theory terms, this process is equivalent to finding balanced vertex partitions with minimum-weight vertex separators. The techniques of finding these vertex partitions are discussed, and experiments are performed to evaluate its practicality for general graphs and systems of polynomial equations. Applications of this approach in algebraic cryptanalysis on symmetric ciphers are presented: For the QUAD family of stream ciphers, we show how a malicious party can manufacture conforming systems that can be easily broken. For the stream ciphers Bivium and Trivium, we achieve significant speedups in algebraic attacks against them, mainly in a partial key guess scenario. In each of these cases, the systems of polynomial equations involved are well-suited to our graph partitioning method. These results may open a new avenue for evaluating the security of symmetric ciphers against algebraic attacks.
Kenneth Koon-Ho Wong, Gregory V. Bard

On Multidimensional Linear Cryptanalysis

Matsui’s Algorithms 1 and 2 with multiple approximations have been studied over 16 years. In CRYPTO’04, Biryukov et al. proposed a formal framework based on m statistically independent approximations. Started by Hermelin et al. in ACISP’08, a different approach was taken by studying m-dimensional combined approximations from m base approximations. Known as multidimensional linear cryptanalysis, the requirement for statistical independence is relaxed. In this paper we study the multidimensional Alg. 1 of Hermelin et al.. We derive the formula for N, the number of samples required for the attack and we improve the algorithm by reducing time complexity of the distillation phase from 2 m N to 2m2 m  + mN, and that of the analysis phase from 22m to 3m2 m . We apply the results on 4- and 9-round Serpent and show that Hermelin et al. actually provided a formal model for the hypothesis of Biryukov et al. in practice, and this model is now much more practical with our improvements.
Phuong Ha Nguyen, Lei Wei, Huaxiong Wang, San Ling

Side-Channel Analysis of the K2 Stream Cipher

In this paper we provide the first side-channel analysis of the K2 stream cipher. K2 is a fast and secure stream cipher built upon the strengths of SNOW 2.0. We apply timing attacks, power analysis, and differential fault analysis to K2. We show that naively implemented K2 is vulnerable to cache-timing attacks, and describe how to implement efficient countermeasures to protect K2 against side-channel attacks in hardware and software.
Matt Henricksen, Wun She Yap, Chee Hoo Yian, Shinsaku Kiyomoto, Toshiaki Tanaka

On Unbiased Linear Approximations

In this paper we explore the recovery of key information from a block cipher when using unbiased linear approximations of a certain form. In particular we develop a theoretical framework for their treatment and we confirm their behaviour with experiments on reduced-round variants of DES. As an application we show a novel form of linear cryptanalysis using multiple linear approximations which can be used to extract key information when all pre-existing techniques would fail.
Jonathan Etrog, Matthew J. B. Robshaw

Hash Functions

Distinguishers for the Compression Function and Output Transformation of Hamsi-256

Hamsi is one of 14 remaining candidates in NIST’s Hash Competition for the future hash standard SHA-3. Until now, little analysis has been published on its resistance to differential cryptanalysis, the main technique used to attack hash functions. We present a study of Hamsi’s resistance to differential and higher-order differential cryptanalysis, with focus on the 256-bit version of Hamsi. Our main results are efficient distinguishers and near-collisions for its full (3-round) compression function, and distinguishers for its full (6-round) finalization function, indicating that Hamsi’s building blocks do not behave ideally.
Jean-Philippe Aumasson, Emilia Käsper, Lars Ramkilde Knudsen, Krystian Matusiewicz, Rune Ødegård, Thomas Peyrin, Martin Schläffer

Second-Preimage Analysis of Reduced SHA-1

Many applications using cryptographic hash functions do not require collision resistance, but some kind of preimage resistance. That’s also the reason why the widely used SHA-1 continues to be recommended in all applications except digital signatures after 2010. Recent work on preimage and second preimage attacks on reduced SHA-1 succeeding up to 48 out of 80 steps (with results barely below the 2 n time complexity of brute-force search) suggest that there is plenty of security margin left.
In this paper we show that the security margin is actually somewhat lower, when only second preimages are the goal. We do this by giving two examples, using known differential properties of SHA-1. First, we reduce the complexity of a 2nd-preimage shortcut attack on 34-step SHA-1 from an impractically high complexity to practical complexity. Next, we show a property for up to 61 steps of the SHA-1 compression function that violates some variant of a natural second preimage resistance assumption, adding 13 steps to previously best known results.
Christian Rechberger

Some Observations on Indifferentiability

At Crypto 2005, Coron et al. introduced a formalism to study the presence or absence of structural flaws in iterated hash functions. If one cannot differentiate a hash function using ideal primitives from a random oracle, it is considered structurally sound, while the ability to differentiate it from a random oracle indicates a structural weakness. This model was devised as a tool to see subtle real world weaknesses while in the random oracle world. In this paper we take in a practical point of view. We show, using well known examples like NMAC and the Mix-Compress-Mix (MCM) construction, how we can prove a hash construction secure and insecure at the same time in the indifferentiability setting. These constructions do not differ in their implementation but only on an abstract level. Naturally, this gives rise to the question what to conclude for the implemented hash function.
Our results cast doubts about the notion of “indifferentiability from a random oracle” to be a mandatory, practically relevant criterion (as e.g., proposed by Knudsen [17] for the SHA-3 competition) to separate good hash structures from bad ones.
Ewan Fleischmann, Michael Gorski, Stefan Lucks

Public Key Cryptography

Adaptive and Composable Non-committing Encryptions

In this paper, a new non-committing encryption protocol without failure during the course of a channel setup procedure is constructed and analyzed in the universally composable (UC) framework. We show that the proposed non-committing scheme realizes the UC-security in the presence of adaptive adversary assuming that the decisional Diffie-Hellman problem is hard.
Huafei Zhu, Tadashi Araragi, Takashi Nishide, Kouichi Sakurai

Relations among Notions of Complete Non-malleability: Indistinguishability Characterisation and Efficient Construction without Random Oracles

We study relations among various notions of complete non-malleability, where an adversary can tamper with both ciphertexts and public-keys, and ciphertext indistinguishability. We follow the pattern of relations previously established for standard non-malleability. To this end, we propose a more convenient and conceptually simpler indistinguishability-based security model to analyse completely non-malleable schemes. Our model is based on strong decryption oracles, which provide decryptions under arbitrarily chosen public keys. We give the first precise definition of a strong decryption oracle, pointing out the subtleties in different approaches that can be taken. We construct the first efficient scheme, which is fully secure against strong chosen-ciphertext attacks, and therefore completely non-malleable, without random oracles.
Manuel Barbosa, Pooya Farshim

Strong Knowledge Extractors for Public-Key Encryption Schemes

Completely non-malleable encryption schemes resist attacks which allow an adversary to tamper with both ciphertexts and public keys. In this paper we introduce two extractor-based properties that allow us to gain insight into the design of such schemes and to go beyond known feasibility results in this area. We formalise strong plaintext awareness and secret key awareness and prove their suitability in realising these goals. Strong plaintext awareness imposes that it is infeasible to construct a ciphertext under any public key without knowing the underlying message. Secret key awareness requires it to be infeasible to produce a new public key without knowing a corresponding secret key.
Manuel Barbosa, Pooya Farshim

A Multi-trapdoor Commitment Scheme from the RSA Assumption

Gennaro introduced the notion of multi-trapdoor commitments which is a stronger form of trapdoor commitment schemes at CRYPTO 2004. Multi-trapdoor commitments have several cryptographic applications. For example, Gennaro proposed a conversion that makes a non-interactive multi-trapdoor commitment scheme into a non- interactive and reusable non-malleable commitment scheme and a compiler that transforms any proof of knowledge into concurrently non-malleable one. Gennaro gave constructions of multi-trapdoor commitments, but they rely on stronger assumptions, such as the strong RSA assumption, the q-strong Diffie-Hellman assumption.
In this paper, we propose a non-interactive multi-trapdoor commitment scheme from the standard RSA assumption. Thus, as a corollary of our result, we obtain a non-interactive and reusable non-malleable commitment scheme from the standard RSA assumption. Our scheme is based on the Hohenberger-Waters signature scheme proposed at CRYPTO 2009. Several non-interactive and reusable non-malleable commitment schemes (in the common reference string model) have been proposed, but all of them rely on stronger assumptions (e.g., strong RSA).
Ryo Nishimaki, Eiichiro Fujisaki, Keisuke Tanaka

Identity-Based Chameleon Hash Scheme without Key Exposure

The notion of chameleon hash function without key exposure plays an important role in designing chameleon signatures. However, all of the existing key-exposure free chameleon hash schemes are presented in the setting of certificate-based systems. In 2004, Ateniese and de Medeiros questioned whether there is an efficient construction for identity-based chameleon hashing without key exposure.
In this paper, we propose the first identity-based chameleon hash scheme without key exposure based on the three-trapdoor mechanism, which provides an affirmative answer to the open problem.
Xiaofeng Chen, Fangguo Zhang, Willy Susilo, Haibo Tian, Jin Li, Kwangjo Kim

The Security Model of Unidirectional Proxy Re-Signature with Private Re-Signature Key

In proxy re-signature (PRS), a semi-trusted proxy, with some additional information (a.k.a., re-signature key), can transform Alice’s (delegatee) signature into Bob’s (delegator) signature on the same message, but cannot produce an arbitrary signature on behalf of either the delegatee or the delegator. In this paper, we investigate the security model of proxy re-signature, and find that the previous security model proposed by Ateniese and Honhenberger at ACM CCS 2005 (referred to as the AH model) is not complete since it does not cover all possible attacks. In particular, the attack on the unidirectional proxy re-signature with private re-signature key. To show this, we artificially design such a proxy re-signature scheme, which is proven secure in the AH model but suffers from a specific attack. Furthermore, we propose a new security model to solve the problem of the AH model. Interestingly, the previous two private re-signature key, unidirectional proxy re-signature schemes (one is proposed by Ateniese and Honhenberger at ACM CCS 2005, and the other is proposed by Libert and Vergnaud at ACM CCS 2008), which are proven secure in the AH model, can still be proven secure in our security model.
Jun Shao, Min Feng, Bin Zhu, Zhenfu Cao, Peng Liu

Security Estimates for Quadratic Field Based Cryptosystems

We describe implementations for solving the discrete logarithm problem in the class group of an imaginary quadratic field and in the infrastructure of a real quadratic field. The algorithms used incorporate improvements over previously-used algorithms, and extensive numerical results are presented demonstrating their efficiency. This data is used as the basis for extrapolations, used to provide recommendations for parameter sizes providing approximately the same level of security as block ciphers with 80, 112, 128, 192, and 256-bit symmetric keys.
Jean-François Biasse, Michael J. Jacobson, Alan K. Silvester

Solving Generalized Small Inverse Problems

We introduce a “generalized small inverse problem (GSIP)” and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of \(f(x_0, x_1, \ldots , x_n)=x_0 h(x_1, \ldots , x_n)+C=0 (\bmod \; M)\) for an n-variate polynomial h, non-zero integers C and M. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving f = 0, which are systematically transformed from a lattice basis for solving h = 0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in logM in an explicit form. Since GSIPs include some RSA-related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.
Noboru Kunihiro


One-Time-Password-Authenticated Key Exchange

To reduce the damage of phishing and spyware attacks, banks, governments, and other security-sensitive industries are deploying one-time password systems, where users have many passwords and use each password only once. If a single password is compromised, it can be only be used to impersonate the user once, limiting the damage caused. However, existing practical approaches to one-time passwords have been susceptible to sophisticated phishing attacks.
We give a formal security treatment of this important practical problem. We consider the use of one-time passwords in the context of password-authenticated key exchange (PAKE), which allows for mutual authentication, session key agreement, and resistance to phishing attacks. We describe a security model for the use of one-time passwords, explicitly considering the compromise of past (and future) one-time passwords, and show a general technique for building a secure one-time-PAKE protocol from any secure PAKE protocol. Our techniques also allow for the secure use of pseudorandomly generated and time-dependent passwords.
Kenneth G. Paterson, Douglas Stebila

Predicate-Based Key Exchange

We provide the first description of and security model for authenticated key exchange protocols with predicate-based authentication. In addition to the standard goal of session key security, our security model also provides for credential privacy: a participating party learns nothing more about the other party’s credentials than whether they satisfy the given predicate. Our model also encompasses attribute-based key exchange since it is a special case of predicate-based key exchange.
We demonstrate how to realize a secure predicate-based key exchange protocol by combining any secure predicate-based signature scheme with the basic Diffie-Hellman key exchange protocol, providing an efficient and simple solution.
James Birkett, Douglas Stebila

Attribute-Based Authenticated Key Exchange

We introduce the concept of attribute-based authenticated key exchange (AB-AKE) within the framework of ciphertext-policy attribute-based systems. A notion of AKE-security for AB-AKE is presented based on the security models for group key exchange protocols and also taking into account the security requirements generally considered in the ciphertext-policy attribute-based setting. We also introduce a new primitive called encapsulation policy attribute-based key encapsulation mechanism (EP-AB-KEM) and then define a notion of chosen ciphertext security for EP-AB-KEMs. A generic one-round AB-AKE protocol that satisfies our AKE-security notion is then presented. The protocol is generically constructed from any EP-AB-KEM that achieves chosen ciphertext security. Finally, we propose an EP-AB-KEM from an existing attribute-based encryption scheme and show that it achieves chosen ciphertext security in the generic group and random oracle models. Instantiating our AB-AKE protocol with this EP-AB-KEM will result in a concrete one-round AB-AKE protocol also secure in the generic group and random oracle models.
M. Choudary Gorantla, Colin Boyd, Juan Manuel González Nieto

Optimally Tight Security Proofs for Hash-Then-Publish Time-Stamping

We study the security of hash-then-publish time-stamping schemes and concentrate on the tightness of security reductions from the collision-resistance of the underlying hash functions. While the previous security reductions create a quadratic loss in the security in terms of time-success ratio of the adversary being protected against, this paper achieves a notably smaller loss of power 1.5. This is significant for two reasons. Firstly, the reduction is asymptotically optimally tight, as the lower bound of 1.5 on the power was proven recently by the authors in ACISP 2009 and this is the first application for which optimality in this sense can be demonstrated. Secondly, the new reduction is the first one efficient enough to allow meaningful security guarantees to be given for a global-scale time-stamping service based on 256 bit hash functions, which considerably increases the efficiency of possible practical solutions.
Ahto Buldas, Margus Niitsoo

Additive Combinatorics and Discrete Logarithm Based Range Protocols

We show how to express an arbitrary integer interval \(\mathcal{I} = [0, H]\) as a sumset \(\mathcal{I} = \sum_{i=1}^\ell G_i * [0, u - 1] + [0, H']\) of smaller integer intervals for some small values ℓ, u, and H′ < u − 1, where b * A = {b a : a ∈ A} and \(A + B = \{a + b : a \in A \land b \in B\}\). We show how to derive such expression of \(\mathcal{I}\) as a sumset for any value of 1 < u < H, and in particular, how the coefficients G i can be found by using a nontrivial but efficient algorithm. This result may be interesting by itself in the context of additive combinatorics. Given the sumset-representation of \(\mathcal{I}\), we show how to decrease both the communication complexity and the computational complexity of the recent pairing-based range proof of Camenisch, Chaabouni and shelat from ASIACRYPT 2008 by a factor of 2. Our results are important in applications like e-voting where a voting server has to verify thousands of proofs of e-vote correctness per hour. Therefore, our new result in additive combinatorics has direct relevance in practice.
Rafik Chaabouni, Helger Lipmaa, Abhi Shelat

Proof-of-Knowledge of Representation of Committed Value and Its Applications

We present a zero-knowledge argument system of representation of a committed value. Specifically, for commitments C = Commit 1(y), \(D={\sf Commit}_2(\vec{x})\), of value y and a tuple \(\vec{x}=(x_1, \ldots, x_L)\), respectively, our argument system allows one to demonstrate the knowledge of \((\vec{x}, y)\) such that \(\vec{x}\) is a representation of y to bases h 1, ..., h L . That is, \(y=h_1^{x_1}\cdots h_L^{x_L}\). Our argument system is zero-knowledge and hence, it does not reveal anything such as \(\vec{x}\) or y. We note that applications of our argument system are enormous. In particular, we show how round-optimal cryptography systems, where privacy is of a great concern, can be achieved. We select three interesting applications with the aim to demonstrate the significance our argument system. First, we present a concrete instantiation of two-move concurrently-secure blind signature without interactive assumptions. Second, we present the first compact e-cash with concurrently-secure withdrawal protocol. Finally, we construct two-move traceable signature with concurrently-secure join. On the side note, we present a framing attack against the original traceable signature scheme within the original model.
Man Ho Au, Willy Susilo, Yi Mu

Network Security

Pattern Recognition Techniques for the Classification of Malware Packers

Packing is the most common obfuscation method used by malware writers to hinder malware detection and analysis. There has been a dramatic increase in the number of new packers and variants of existing ones combined with packers employing increasingly sophisticated anti-unpacker tricks and obfuscation methods. This makes it difficult, costly and time-consuming for anti-virus (AV) researchers to carry out the traditional static packer identification and classification methods which are mainly based on the packer’s byte signature.
In this paper, we present a simple, yet fast and effective packer classification framework that applies pattern recognition techniques on automatically extracted randomness profiles of packers. This system can be run without AV researcher’s manual input. We test various statistical classification algorithms, including k −Nearest Neighbor, Best-first Decision Tree, Sequential Minimal Optimization and Naive Bayes. We test these algorithms on a large data set that consists of clean packed files and 17,336 real malware samples. Experimental results demonstrate that our packer classification system achieves extremely high effectiveness (> 99%). The experiments also confirm that the randomness profile used in the system is a very strong feature for packer classification. It can be applied with high accuracy on real malware samples.
Li Sun, Steven Versteeg, Serdar Boztaş, Trevor Yann

Repelling Sybil-Type Attacks in Wireless Ad Hoc Systems

We consider ad hoc wireless networks and adversaries that try to gain control over the network by Sybil attacks, that is by emulating more physical nodes that are really under his control.We present the first defense method that works for the case when the adversary controls more than one device and these devices have some prior agreement on strategy executed and share preloaded secrets.
Marek Klonowski, Michał Koza, Mirosław Kutyłowski


Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!