International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2012-11-01
18:17 [Pub][ePrint]

We introduce the \\emph{linear centralizer method} for a passive adversary

to extract the shared key in group-theory based key exchange protocols (KEPs).

We apply this method to obtain a polynomial time cryptanalysis of the

\\emph{Commutator KEP}, introduced by Anshel--Anshel--Goldfeld in 1999 and considered

extensively ever since.

We also apply this method to the \\emph{Centralizer KEP}, introduced by Shpilrain--Ushakov in 2006.

Our method is proved to be of polynomial time using a technical lemma

about sampling invertible matrices from a linear space of matrices.

18:17 [Pub][ePrint]

We revisit hardness-preserving constructions of a PRF from any length doubling PRG when there is a non-trivial upper bound $q$ on the number of queries that the adversary can make to the PRF. Very recently, Jain, Pietrzak, and Tentes (TCC 2012) gave a hardness-preserving construction of a PRF that makes only $O(\\log q)$ calls to the underlying PRG when $q = 2^{n^\\epsilon}$ and $\\epsilon \\geq \\frac{1}{2}$. This dramatically improves upon the efficiency of the GGM construction. However, they explicitly left open the question of whether such constructions exist when $\\epsilon < \\frac{1}{2}$. In this work, we make progress towards answering this question. In particular we give constructions of PRFs that make only $O(\\log q)$ calls to the underlying PRG even when $q = 2^{n^\\epsilon}$, for $0 18:17 [Pub][ePrint] An increasing number of embedded security applications---which traditionally have been heavily reliant on secret and/or proprietary solutions---apply the principle of open evaluation. A recent example is the specification of an open security protocol stack for car immobilizer applications by Atmel, which has been presented at ESCAR 2010. This stack is primarily intended to be used in conjunction with automotive transponder chips of this manufacturer, but could in principle be deployed on any suitable type of transponder chip. In this paper we re-evaluate the security of this protocol stack. We were able to uncover a number of security vulnerabilities. We show that an attacker with a cheap standard reader close to such a car key can track it, lock sections of its EEPROM, and even render its immobilizer functionality completely useless. After eavesdropping on a genuine run of the authentication protocol between the car key and the car, an attacker is enabled to read and write the memory of the car key. Furthermore, we point out the threats of relay attacks and session hijacking, which require slightly more elaborate attack setups. For each of the indicated attacks we propose possible fixes and discuss their overhead. 18:17 [Pub][ePrint] Usually a communication link is securedby means of a symmetric-key algorithm. For that, amethod is required to securely establish a symmetric key for that algorithm. This old key establishment problem is still relevant and of paramount importance both in existing computer networks and new large-scale ubiquitous systems comprising resource-constrained devices. Identity-based pairwise key agreement allows for the generation of a common key between two parties given a secret keying material owned by the first party and the identity of the second one. However, existing methods, e.g., based on polynomials, are prone to collusion attacks. In this paper we discuss a new key establishment scheme aiming at fully collusion-resistant identity-based symmetric-key agreement. Our scheme, the HIMMO algorithm, relies on two design concepts: Hiding Information and Mixing Modular Operations. Collusion attacks on schemes from literature cannot readily be applied to our scheme; our security analysis further shows that HIMMO\'s design principles prevent an attacker from performing a number of attacks. Also, the simple logic of the HIMMO algorithm allows for very efficient implementations in terms of both speed and memory. Finally, being an identitybasedsymmetric-key establishment scheme, HIMMO allows for efficient real-world key exchange protocols. 2012-10-31 10:21 [Event][New] Submission: 7 January 2013 Notification: 31 January 2013 From March 18 to March 20 Location: Cambridge, England More Information: http://spw.stca.herts.ac.uk/ 2012-10-30 00:17 [Pub][JoC] Abstract Recent targeted attacks have increased significantly in sophistication, undermining the fundamental assumptions on which most cryptographic primitives rely for security. For instance, attackers launching an Advanced Persistent Threat (APT) can steal full cryptographic keys, violating the very secrecy of “secret” keys that cryptographers assume in designing secure protocols. In this article, we introduce a game-theoretic framework for modeling various computer security scenarios prevalent today, including targeted attacks. We are particularly interested in situations in which an attacker periodically compromises a system or critical resource completely, learns all its secret information and is not immediately detected by the system owner or defender. We propose a two-player game between an attacker and defender called FlipIt or The Game of “Stealthy Takeover.” In FlipIt, players compete to control a shared resource. Unlike most existing games, FlipIt allows players to move at any given time, taking control of the resource. The identity of the player controlling the resource, however, is not revealed until a player actually moves. To move, a player pays a certain move cost. The objective of each player is to control the resource a large fraction of time, while minimizing his total move cost. FlipIt provides a simple and elegant framework in which we can formally reason about the interaction between attackers and defenders in practical scenarios. In this article, we restrict ourselves to games in which one of the players (the defender) plays with a renewal strategy, one in which the intervals between consecutive moves are chosen independently and uniformly at random from a fixed probability distribution. We consider attacker strategies ranging in increasing sophistication from simple periodic strategies (with moves spaced at equal time intervals) to more complex adaptive strategies, in which moves are determined based on feedback received during the game. For different classes of strategies employed by the attacker, we determine strongly dominant strategies for both players (when they exist), strategies that achieve higher benefit than all other strategies in a particular class. When strongly dominant strategies do not exist, our goal is to characterize the residual game consisting of strategies that are not strongly dominated by other strategies. We also prove equivalence or strict inclusion of certain classes of strategies under different conditions. Our analysis of different FlipIt variants teaches cryptographers, system designers, and the community at large some valuable lessons: 1. Systems should be designed under the assumption of repeated total compromise, including theft of cryptographic keys. FlipIt provides guidance on how to implement a cost-effective defensive strategy. 2. Aggressive play by one player can motivate the opponent to drop out of the game (essentially not to play at all). Therefore, moving fast is a good defensive strategy, but it can only be implemented if move costs are low. We believe that virtualization has a huge potential in this respect. 3. Close monitoring of one’s resources is beneficial in detecting potential attacks faster, gaining insight into attacker’s strategies, and scheduling defensive moves more effectively. Interestingly, FlipIt finds applications in other security realms besides modeling of targeted attacks. Examples include cryptographic key rotation, password changing policies, refreshing virtual machines, and cloud auditing. • Content Type Journal Article • Pages 1-59 • DOI 10.1007/s00145-012-9134-5 • Authors • Marten van Dijk, RSA Laboratories, Cambridge, MA, USA • Ari Juels, RSA Laboratories, Cambridge, MA, USA • Alina Oprea, RSA Laboratories, Cambridge, MA, USA • Ronald L. Rivest, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA • Journal Journal of Cryptology • Online ISSN 1432-1378 • Print ISSN 0933-2790 From: Fri, 26 Oct 2012 12:00:56 GMT 2012-10-29 15:17 [Pub][ePrint] We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary\'s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder to prove than its classical analogue. Next, we show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, we present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but we prove that a four-wise independent family is sufficient for one-time security. 15:17 [Pub][ePrint] We give three new algorithms to solve the isomorphism of polynomial\'\' problem, which was underlying the hardness of recovering the secret-key in some multivariate trapdoor one-way functions. In this problem, the adversary is given two quadratic functions, with the promise that they are equal up to linear changes of coordinates. Her objective is to compute these changes of coordinates, a task which is known to be harder than Graph-Isomorphism. Our new algorithm build on previous work in a novel way. Exploiting the birthday paradox, we break instances of the problem in time$q^{2n/3}$(rigorously) and$q^{n/2}$(heuristically), where$q^n$is the time needed to invert the quadratic trapdoor function by exhaustive search. These results are obtained by turning the algebraic problem into a combinatorial one, namely that of recovering partial information on an isomorphism between two exponentially large graphs. These graphs, derived from the quadratic functions, are new tools in multivariate cryptanalysis. 15:17 [Pub][ePrint] Secure sketches and fuzzy extractors enable the use of biometric data in cryptographic applications by correcting errors in noisy biometric readings and producing cryptographic materials suitable for authentication, encryption, and other purposes. Such constructions work by producing a public sketch, which is later used to reproduce the original biometric and all derived information exactly from a noisy biometric reading. It has been previously shown that release of multiple sketches associated with a single biometric presents security problems for certain constructions. We continue the analysis to demonstrate that all other constructions in the literature are also prone to similar problems and cannot be safely reused. To mitigate the problem, we propose for each user to store one short secret string for all possible uses of her biometric, and show that simple constructions in the computational setting have numerous advantageous security and usability properties under standard hardness assumptions. Our constructions are generic in that they can be used with any existing secure sketch as a black box. 15:17 [Pub][ePrint] Embedding an element of a finite field into auxiliary groups such as elliptic curve groups or extension fields of finite fields has been useful tool for analysis of cryptographic problems such as establishing the equivalence between the discrete logarithm problem and Diffie-Hellman problem or solving the discrete logarithm problem with auxiliary inputs (DLPwAI). Actually, Cheon\'s algorithm solving the DLPwAI can be regarded as a quantitative version of den Boer and Maurer. Recently, Kim showed in his dissertation that the generalization of Cheon\'s algorithm using embedding technique including Satoh\'s \\cite{Sat09} is no faster than Pollard\'s rho algorithm when$d\\nmid (p\\pm 1)$. In this paper, we propose a new approach to solve DLPwAI concentrating on the behavior of function mapping between the finite fields rather than using an embedding to auxiliary groups. This result shows the relation between the complexity of the algorithm and the number of absolutely irreducible factors of the substitution polynomials, hence enlightens the research on the substitution polynomials. More precisely, with a polynomial$f(x)$of degree$d$over$\\mathbf{F}_p$, the proposed algorithm shows the complexity$O\\left(\\sqrt{p^2/R}\\log^2d\\log p\\right)$group operations to recover$\\alpha$with$g, g^{\\alpha}, \\dots, g^{\\alpha^{d}}$, where$R$denotes the number of pairs$(x, y)\\in\\mathbf{F}_p\\times \\mathbf{F}_p$such that$f(x)-f(y)=0$. As an example using the Dickson polynomial, we reveal$\\alpha$in$O(p^{1/3}\\log^2{d}\\log{p})$group operations when$d|(p+1)$. Note that Cheon\'s algorithm requires$g, g^{\\alpha}, \\dots, g^{\\alpha^{d}}, \\dots, g^{\\alpha^{2d}}\$ as an instance for the same problem.

15:17 [Pub][ePrint]

We describe plausible lattice-based constructions with properties that

approximate the sought-after multilinear maps in hard-discrete-logarithm

groups, and show that some applications of such multi-linear maps can

be realized using our approximations.

The security of our constructions relies on seemingly hard problems in

ideal lattices, which can be viewed as extensions of the assumed

hardness of the NTRU function.