International Association
for Cryptologic Research

In this survey, we describe a general key exchange protocol based on semidirect product of (semi)groups (more specifically, on extensions of (semi)groups by automorphisms), and then focus on practical instances of this general idea. This protocol can be based on any group or semigroup, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when this protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. The focus then shifts to selecting an optimal platform (semi)group, in terms of security and efficiency. We show, in particular, that one can get a variety of new security assumptions by varying an automorphism used for a (semi)group extension.

While \textsf{Salsa} and \textsf{ChaCha} are well known software oriented stream ciphers, since the work of Aumasson et al in FSE 2008 there aren't many significant results against them. The basic model of their attack was to introduce differences in the IV bits, obtain biases after a few forward rounds, as well as to look at the Probabilistic Neutral Bits (PNBs) while reverting back. In this paper we first consider the biases in the forward rounds, and estimate an upper bound on the number of rounds till such biases can be observed. For this, we propose a hybrid model (under certain assumptions), where initially the nonlinear rounds as proposed by the designer are considered, and then we employ their linearized counterpart. The effect of reverting the rounds with the idea of PNBs is also considered. Based on the assumptions and analysis, we conclude that 12 rounds of \textsf{Salsa} and \textsf{ChaCha} should be considered sufficient for 256-bit keys under the current best known attack models.

In December 2015, Juniper Networks announced that unknown attackers had added unauthorized code to ScreenOS, the operating system for their NetScreen VPN routers. This code created two vulnerabilities: an authentication bypass that enabled remote administrative access, and a second vulnerability that allowed passive decryption of VPN traffic. Reverse engineering of ScreenOS binaries revealed that the first of these vulnerabilities was a conventional back door in the SSH password checker. The second is far more intriguing: a change to the Q parameter used by the Dual EC pseudorandom number generator. It is widely known that Dual EC has the unfortunate property that an attacker with the ability to choose Q can, from a small sample of the generator's output, predict all future outputs. In a 2013 public statement, Juniper noted the use of Dual EC but claimed that ScreenOS included countermeasures that neutralized this form of attack.

In this work, we report the results of a thorough independent analysis of the ScreenOS randomness subsystem, as well as its interaction with the IKE VPN key establishment protocol. Due to apparent flaws in the code, Juniper's countermeasures against a Dual EC attack are never executed. Moreover, by comparing sequential versions of ScreenOS, we identify a cluster of additional changes that were introduced concurrently with the inclusion of Dual EC in a single 2008 release. Taken as a whole, these changes render the ScreenOS system vulnerable to passive exploitation by an attacker who selects Q. We demonstrate this by installing our own parameters, and showing that it is possible to passively decrypt a single IKE handshake and its associated VPN traffic in isolation without observing any other network traffic.

We consider the question of whether average-case PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only known source for average-case PPAD hardness.

Central in the study of obfuscation-based PPAD hardness is the SINK-OF-VERIFIABLE-LINE (SVL) problem, an intermediate step in constructing hard-on-average instances of the PPAD-complete problem SOURCE-OR-SINK. Within the framework of black-box reductions we prove the following results:

-- Average-case PPAD hardness (and even average-case SVL hardness) does not imply any form of cryptographic hardness (not even one-way functions).

-- Average-case SVL hardness cannot be based either on standard cryptographic assumptions or on average-case PPAD hardness (and is thus not essential for PPAD hardness).

-- Any attempt for basing the average-case hardness of SOURCE-OR-SINK on standard cryptographic assumptions must result in instances with a nearly-exponential number of solutions.

Taken together, our results imply that while it may still be possible to base average-case PPAD hardness on standard cryptographic assumptions, any black-box attempt must significantly deviate from the obfuscation-based approach: It cannot go through the SVL problem, and it must result in SOURCE-OR-SINK instances with a nearly-exponential number of solutions.

In 2012, NIST standardized SHA-512/224 and SHA-512/256, two truncated variants of SHA-512, in FIPS 180-4. These two hash functions are faster than SHA-224 and SHA-256 on 64-bit platforms, while maintaining the same hash size and claimed security level. So far, no third-party analysis of SHA-512/224 or SHA-512/256 has been published. In this work, we examine the collision resistance of step-reduced versions of SHA-512/224 and SHA-512/256 by using differential cryptanalysis in combination with sophisticated search tools. We are able to generate practical examples of free-start collisions for 44-step SHA-512/224 and 43-step SHA-512/256. Thus, the truncation performed by these variants on their larger state allows us to attack several more rounds compared to the untruncated family members. In addition, we improve upon the best published collisions for 24-step SHA-512 and present practical collisions for 27 steps of SHA-512/224, SHA-512/256, and SHA-512.

We present a new strategy for partitioning proofs, and use it to obtain new tightly secure encryption schemes. Specifically, we provide the following two conceptual contributions:

- A new strategy for tight security reductions that leads to compact public keys and ciphertexts.

- A relaxed definition of non-interactive proof systems for non-linear (``OR-type'') languages. Our definition is strong enough to act as a central tool in our new strategy to obtain tight security, and is achievable both in pairing-friendly and DCR groups.

We apply these concepts in a generic construction of a tightly secure public-key encryption scheme. When instantiated in different concrete settings, we obtain the following:

- A public-key encryption scheme whose chosen-ciphertext security can be tightly reduced to the DLIN assumption in a pairing-friendly group. Ciphertexts, public keys, and system parameters contain 6, 24, and 2 group elements, respectively. This improves heavily upon a recent scheme of Gay et al. (Eurocrypt 2016) in terms of public key size, at the cost of using a symmetric pairing.

- The first public-key encryption scheme that is tightly chosen-ciphertext secure under the DCR assumption. While the scheme is not very practical (ciphertexts carry 29 group elements), it enjoys constant-size parameters, public keys, and ciphertexts.

Motivated by the subversion of ``trusted'' public parameters in mass-surveillance activities, this paper studies the security of NIZKs in the presence of a maliciously chosen common reference string. We provide definitions for subversion soundness, subversion witness indistinguishability and subversion zero knowledge. We then provide both negative and positive results, showing that certain combinations of goals are unachievable but giving protocols to achieve other combinations.

Secure communications between mobile subscribers and their associated operator networks require mutual authentication and key derivation protocols. The 3GPP standard provides the AKA protocol for just this purpose. Its structure is generic, to be instantiated with a set of seven cryptographic algorithms. The currently-used proposal instantiates these by means of a set of AES-based algorithms called MILENAGE; as an alternative, the ETSI SAGE committee submitted the TUAK algorithms, which rely on a truncation of the internal permutation of Keccak.

In this paper, we provide a formal security analysis of the AKA protocol in its complete three-party setting. We formulate requirements with respect to both Man-in-the-Middle (MiM) adversaries, i.e. key-indistinguishability and impersonation security, and to local untrusted serving networks, denoted “servers”, namely state-confidentiality and soundness. We prove that the unmodified AKA protocol attains these properties as long as servers cannot be corrupted. Furthermore, adding a unique server identifier suffices to guarantee all the security statements even in in the presence of corrupted servers. We use a modular proof approach: the first step is to prove the security of (modified and unmodified) AKA with generic cryptographic algorithms that can be represented as a unitary pseudorandom function –PRF– keyed either with the client’s secret key or with the operator key. A second step proceeds to show that TUAK and MILENAGE guarantee this type of pseudorandomness, though the guarantee for MILENAGE requires a stronger assumption. Our paper provides (to our knowledge) the first complete, rigorous analysis of the original AKA protocol and these two instantiations. We stress that such an analysis is important for any protocol deployed in real-life scenarios.

Trustworthy generation of public random numbers is necessary for the security of many cryptographic applications. It was suggested to use the inherent unpredictability of blockchains as a source of public randomness. Entropy from the Bitcoin blockchain in particular has been used in lotteries and has been suggested for a number of other applications ranging from smart contracts to election auditing. In this Arcticle, we analyse this idea and show how an adversary could manipulate these random numbers, even with limited computational power and financial budget.

This is an excellent opportunity to join a Cyber Security practise experiencing rapid growth in the United Arab Emirates. They are currently seeking experienced Crypto Experts with the following knowledge to join their team:

• Proficient in AES algorithm design.
• Expert in block and stream cipher, key management, hybrid approach, hashing.
• Knowledge in substitution, permutation, confusion & diffusion mechanism.
• Cryptanalysis: Differential, Linear, Side channel attack, Plain & Cipher text etc,.
• Knowledge in crypto events, such as, Caesar competition.
• History of different symmetric key algorithms.
• Mathematics degree is preferred.
• Should be ready to start design algorithm as soon as join.

On offer is an attractive TAX FREE expatriate package, the opportunity to learn from some of the most highly qualified in the business and genuine career opportunities.

Closing date for applications: 29 August 2016

Contact: Hilary (at) talentboutique.ae

Event date: 8 June to 10 June 2016

Event date: 13 May 2016

The main objective of the research in the Embedded System Security Group is to propose efficient and robust hardware architectures aimed at applied cryptography and telecom that are resistant to passive and active cryptographic attacks. Currently, the central theme of this research consists in designing architectures for secure embedded systems implemented in logic devices such as FPGAs and ASICs. More information on http://laboratoirehubertcurien.fr/spip.php?article213.

For a new project which addresses the problem of secure and privacy in MPSoC architectures, we proposes a Post Doc position to work on security evaluation of heterogeneous MPSoC. We are looking for candidates with an outstanding Ph.D in hardware security and a strong publication record in this field. Strong knowledge in side channel attacks and countermeasures, digital system (VHDL, FPGA) design would be appreciated. Knowledge of French is not mandatory.

The Post-Doc position will start in 2016 (flexible starting date), it is funded for 24 month.

To apply please send your detailed CV (with publication list), motivation for applying (1 page) and names of at least two people who can provide reference letters (e-mail).

Closing date for applications: 15 June 2016

Contact:

Dr. Lilian BOSSUET lilian.bossuet(at)univ-st-etienne.fr

Applications are invited for a Post-Doc post at the School of Computing Science, Newcastle University, UK. The post is funded by European Research Council (ERC), until end of Dec 2017. The project is on investigating \"self-enforcing e-voting\", but the candidate has the flexibility to work with a team of researchers on a diversified range of topics that concern real-world security, e.g., authenticated key exchange, BitCoin, NFC payment security, e-auction, e-passport and mobile sensor security.

The successful applicant will join a vibrant and growing Secure and Resilient Systems (SRS) research group at the School of computing Science, Newcastle University. So far research works in the group have been largely driven by tackling real-world security problems, with some of the research outcomes adopted by international standards and deployed in large-scale commercial applications.

About us: The School of Computing Science at Newcastle University is recognised as one of the fourteen Academic Centres of Excellence in Cyber Security Research (ACEs-CSR) in the UK. In the latest 2014 Research Excellence Framework (REF) assessment which included all UK universities, Newcastle University CS was ranked the 1st in the UK for its Research Impact.

How to apply: follow the online application link below. To help speed up the process, please also send your CV and a brief cover letter to feng.hao (at) ncl.ac.uk.

Closing date for applications: 10 May 2016

More information: http://www.jobs.ac.uk/job/AUE162/d35883r-research-assistant-associate-e-voting/

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity.

In this paper, we focus on Reed-Muller codes with evaluation polynomials of total degree $d\lesssim\Gs\sqrt{q}$ for some $\Gs\in(0,1)$. By introducing a local decoding of Reed-Muller codes via the concept of codex that has been used for arithmetic secret sharing \cite{C11,CCX12}, we are able to locally recover arbitrarily large number $k$ of coordinates simultaneously at the cost of querying $O(k\sqrt{q})$ coordinates, where $q$ is the code alphabet size. It turns out that our local decoding of Reed-Muller codes shows ({\it perhaps surprisingly}) that accessing $k$ locations is in fact cheaper than repeating the procedure for accessing a single location for $k$ times. In contrast, by repetition of local decoding for recovery of a single coordinate, one has to query $\Omega(k\sqrt{q}\log k/\log q)$ coordinates for $k=q^{\Omega(\sqrt{q})}$ (and query $O(kq)$ coordinates for $k=q^{O(\sqrt{q})}$, respectively). Furthermore, our decoding success probability is $1-\Ge$ with $\Ge=O\left(\left(\frac1{\sqrt{q}}\right)^k\right)$. To get the same success probability from repetition of local decoding for recovery of a single coordinate, one has to query $O(k^2\sqrt{q}\log k/\log q)$ coordinates (or $O(k^2q)$ coordinates for $k=q^{O(\sqrt{q})}$, respectively). In addition, our local decoding also works for recovery of one single coordinate as well and it gives a better success probability than the one by repetition of local decoding on curves. The main tool to realize codex is based on algebraic function fields (or more precisely, algebraic geometry codes). Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in \cite{BR94}.

Group signatures are a central cryptographic primitive that has received a considerable amount of attention from the cryptographic community. They allow members of a group to anonymously sign on behalf of the group. Membership is overseen by a designated group manager. There is also a tracing authority that can revoke anonymity by revealing the identity of the signer if and when needed, to enforce accountability and deter abuse. For the primitive to be applicable in practice, it needs to support fully dynamic groups, i.e. users can join and leave at any time. In this work we take a close look at existing security definitions for fully dynamic group signatures. We identify a number of shortcomings in existing security definitions and fill the gap by providing a formal rigorous security model for the primitive. Our model is general and is not tailored towards a specific design paradigm and can therefore, as we show, be used to argue about the security of different existing constructions following different design paradigms. Our definitions are stringent and when possible incorporate protection against maliciously chosen keys. In the process, we identify a subtle issue inherent to one design paradigm, where new members might try to implicate older ones by means of back-dated signatures. This is not captured by existing models. We propose some inexpensive fixes for some existing constructions to avoid the issue.

In this work we demonstrate various weaknesses of the random number generator (RNG) in the OpenSSL cryptographic library. We show how OpenSSL's RNG, knowingly in a low entropy state, potentially leaks low entropy secrets in its output, which were never intentionally fed to the RNG by client code, thus posing vulnerabilities even when in the given usage scenario the low entropy state is respected by the client application. Turning to the core cryptographic functionality of the RNG, we show how OpenSSL's functionality for adding entropy to the RNG state fails to be effectively a mixing function. If an initial low entropy state of the RNG was falsely presumed to have 256 bits of entropy based on wrong entropy estimations, this causes attempts to recover from this state to succeed only in long term but to fail in short term. As a result, the entropy level of generated cryptographic keys can be limited to 80 bits, even though thousands of bits of entropy might have been fed to the RNG state previously. In the same scenario, we demonstrate an attack recovering the RNG state from later output with an off-line effort between $2^{82}$ and $2^{84}$ hash evaluations, for seeds with an entropy level $n$ above 160 bits. We also show that seed data with an entropy of $160$ bits, fed into the RNG, under certain circumstances, might be recovered from its output with an effort of $2^{82}$ hash evaluations. These results are highly relevant for embedded systems that fail to provide sufficient entropy through their operating system RNG at boot time and rely on subsequent reseeding of the OpenSSL RNG. Furthermore, we identify a design flaw that limits the entropy of the RNG's output to 240 bits in the general case even for an initially correctly seeded RNG, despite the fact that a security level of 256 bits is intended.

We describe the design and implementation of efficient signature and key-exchange schemes for the AVR~ATmega and ARM Cortex~M0 microcontrollers, targeting the 128-bit security level. Our algorithms are based on an efficient Montgomery ladder scalar multiplication on the Kummer surface of Gaudry and Schost's genus-2 hyperelliptic curve, combined with the Jacobian point recovery technique of Costello, Chung, and Smith. Our results are the first to show the feasibility of software-only hyperelliptic cryptography on constrained platforms, and represent a significant improvement on the elliptic-curve state-of-the-art for both key exchange and signatures on these architectures. Notably, our key exchange scalar multiplication software runs in under 9740k cycles on the ATmega, and under 2650k cycles on the Cortex M0.

The Kalray MPPA-256 processor is based on a recent low-energy manycore architecture. In this article, we investigate its performance in multiprecision arithmetic for number-theoretic applications. We have developed a library for modular arithmetic that takes full advantage of the particularities of this architecture. This is in turn used in an implementation of the ECM, an algorithm for integer factorization using el-liptic curves. For parameters corresponding to a crypt-analytic context, our implementation compares well to state-of-the-art implementations on GPU, while using much less energy.