International Association
for Cryptologic Research

We investigate two attacks on the PRINCE block cipher in the most realistic scenario, when the attacker only has a minimal amount of known plaintext available. The first attack is called Accelerated Exhaustive Search, and is able to recover the key for up to the full 12-round PRINCE with a complexity slightly lower than the security claim given by the designers. The second attack is a meet-in-the-middle attack, where we show how to successfully attack 8- and 10-round PRINCE with only two known plaintext/ciphertext pairs. Both attacks take advantage of the fact that the two middle rounds in PRINCE are unkeyed, so guessing the state before the first middle round gives the state after the second round practically for free. These attacks are the fastest until now in the known plaintext scenario for the 8 and 10 reduced-round versions and the full 12-round of PRINCE.

In the cloud computing era, in order to avoid the computational burdens, many recommendation service providers tend to outsource their collaborative filtering computations to third-party cloud servers. In order to protect service quality and privacy for end users, both the integrity of computation results and the confidentiality of original dataset need to be guaranteed. In this paper, we analyze two integrity verification approaches by Vaidya et al. and demonstrate their performances. In particular, we analyze the verification via auxiliary data approach which is only briefly mentioned in the original paper, and demonstrate the experimental results (with better performances). We then propose a new solution to outsource all computations of the weighted Slope One algorithm in multi-server setting and provide experimental results. We finally discuss the possibility of using homomorphic encryption to achieve both integrity and confidentiality guarantees.

We propose a computationally secure and non-interactive verifiable secret sharing scheme that can be efficiently constructed from any monotone Boolean circuit.

By non-interactive we mean that the dealer needs to be active only once, where he posts a public message as well as a private message to each shareholder. In the random oracle model, we can even avoid interaction between shareholders. By efficient, we mean that we avoid generic zero-knowledge techniques.

Such efficient constructions were previously only known from linear secret sharing schemes (LSSS). It is believed that the class of access structures that can be handled with polynomial size LSSS is incomparable to the class that can be recognized by polynomial size monotone circuits, so in this sense we extend the class of access structures with efficient and non-interactive VSS.

KATAN and KTANTAN are two lightweight families of hardware oriented block ciphers proposed by Canni{\`e}re et al. at CHES 2009. They have different versions of 32-, 48- and 64-bit state, all of which work with an 80-bit key. Inspired by the Trivium stream cipher, these families have an innovative structure based on two non-linear feedback shift registers. Such a structure attracts the attention of cryptanalysts and consequently a variety of security analyses have been published. Although the KTANTAN family is already regarded as a broken cipher, the full-round KATAN family is still secure.

In this paper, by exploiting several properties of the KATAN round function as well as the slow diffusion of key bits, we propose some techniques to extend the number of rounds covered by multidimensional meet in the middle attack on all versions of the KATAN family of block ciphers. Our results show that this method can attack up to 206, 148 and 129 reduced-round versions of KATAN32, KATAN48 and KATAN64, respectively, with only 2 or 3 pairs of known plaintext. This cryptanalysis covers the highest number of rounds to date.

Our work is still far from a full-round attack, so it could not be considered as a threat to this family of block ciphers yet. We state that KATAN is still safe to use.

Outsourcing paradigm has become a hot research topic in the cryptography community, where computation workloads can be outsourced to cloud servers by the resource-constrained devices, such as RFID tags. The computation of bilinear pairings is the most expensive operation in pairing-based cryptographic primitives. In this paper, we present two new algorithms for secure outsourcing the computation of bilinear pairings. One is secure in the OMTUP model. The other, which provides flexible checkability, is in the TUP model. Compared with the state-of-the-art algorithms, our proposal is more efficient.

In this paper security aspects of the existing symmetric key encryption schemes based on Hadamard matrices are examined. Hadamard matrices itself have symmetries like one circulant core or two circulant core. Here, we are exploiting the inherent symmetries of Hadamard matrices and are able to perform attacks on these encryption schemes. It is found that entire key can be obtained by observing the ciphertext.

The successful candidate will work as part of the Information Security Research group led by Professor Muttukrishnan Rajarajan in the School and with other project collaborators from Intelligent Voice and University of Reading. He/she will participate in the development of searchable encryption techniques to extract keywords from encrypted data stored in the Cloud.

Person Specification: The candidate should have a PhD in Computer Science or Engineering with interest in cryptography and Cloud Security and should have strong mathematical and C++ programming skills. In addition the person is expected to show excellent verbal and written communication skills and also a good track record of publications in IEEE Security & Privacy journals and conferences.

Closing date for applications: 25 February 2016

Contact: Professor M Rajarajan

More information: http://www.jobs.ac.uk/job/AUC165/research-associate/

Ishai, Kushilevitz, Ostrovsky and Sahai (STOC`07, SIAM JoC 2009) introduced the powerful ``MPC-in-the-head'' technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a ``black-box'' way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so called oblivious-transfer hybrid to an adaptive ZK proof for any NP-language, in a ``black-box'' way assuming only one-way functions. Our basic construction based on Goldreich-Micali-Wigderson's 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the NP relation. Previously such proofs relied on an expensive Karp reduction of the NP language to Graph Hamiltonicity (Lindell and Zarosim (TCC`09, Journal of Cryptology 2011)). We also improve our basic construction to obtain the first linear-rate adaptive ZK proofs by relying on efficient maliciously secure 2PC protocols. Core to this construction is a new way of transforming 2PC protocols to efficient (adaptively secure) instance-dependent commitment schemes.

As our second contribution, we provide a general transformation to construct a randomized encoding of a function $f$ from any 2PC protocol that securely computes a related functionality (in a black-box way). We show that if the 2PC protocol has mild adaptive security guarantees then the resulting randomized encoding (RE) can be decomposed to an offline/online encoding.

As an application of our techniques, we show how to improve the construction of Lapidot and Shamir (Crypto`90) to obtain ``input-delayed'' ZK proofs which are proofs where the honest prover's algorithm does not require the actual statement until the last round. Our transformation also yields the simplest constructions of both static and adaptive ZK proofs from standard 2PC protocols of Yao and Goldreich-Micali-Wigderson.

Outsourcing data to remote storage servers has become more and more popular, but the related security and privacy concerns have also been raised. To protect the pattern in which a user accesses the outsourced data, various oblivious RAM (ORAM) constructions have been designed. However, when existing ORAM designs are extended to support multi-user scenarios, they become vulnerable to stealthy privacy attacks targeted at revealing the data access patterns of innocent users, even if only one curious or compromised user colludes with the storage server. To study the feasibility and costs of overcoming the above limitation, this paper proposes a new ORAM construction called Multi-User ORAM (MU-ORAM), which is resilient to stealthy privacy attacks. The key ideas in the design are (i) introduce a chain of proxies to act as a common interface between users and the storage server, (ii) distribute the shares of the system secrets delicately to the proxies and users, and (iii) enable a user and/or the proxies to collaboratively query and shuffle data. Through extensive security analysis, we quantify the strength of MU-ORAM in protecting the data access patterns of innocent users from attacks, under the assumption that the server, users, and some but not all proxies can be curious but honest, compromised and colluding. Cost analysis has been conducted to quantify the extra overhead incurred by the MU-ORAM design.

Key-exchange protocols such as TLS, SSH, IPsec, and ZRTP are highly configurable, with typical deployments supporting multiple protocol versions, cryptographic algorithms and parameters. In the first messages of the protocol, the peers negotiate one specific combination: the protocol mode, based on their local configurations. With few notable exceptions, most cryptographic analyses of configurable protocols consider a single mode at a time. In contrast, downgrade attacks, where a network adversary forces peers to use a mode weaker than the one they would normally negotiate, are a recurrent problem in practice.

How to support configurability while at the same time guaranteeing the preferred mode is negotiated? We set to answer this question by designing a formal framework to study downgrade resilience and its relation to other security properties of key-exchange protocols. First, we study the causes of downgrade attacks by dissecting and classifying known and novel attacks against widely used protocols. Second, we survey what is known about the downgrade resilience of existing standards. Third, we combine these findings to define downgrade security, and analyze the conditions under which several protocols achieve it. Finally, we discuss patterns that guarantee downgrade security by design, and explain how to use them to strengthen the security of existing protocols, including a newly proposed draft of TLS 1.3.

The Russian Federation's standardization agency has recently published a hash function called Streebog and a 128-bit block cipher called Kuznyechik. Both of these algorithms use the same 8-bit S-Box but its design rationale was never made public.

In this paper, we reverse-engineer this S-Box and reveal its hidden structure. It is based on a sort of 2-round Feistel Network where exclusive-or is replaced by a finite field multiplication. This structure is hidden by two different linear layers applied before and after. In total, five different 4-bit S-Boxes, a multiplexer,two 8-bit linear permutations and two finite field multiplications in a field of size $2^{4}$ are needed to compute the S-Box.

The knowledge of this decomposition allows a much more efficient hardware implementation by dividing the area and the delay by 2.5 and 8 respectively. However, the small 4-bit S-Boxes do not have very good cryptographic properties. In fact, one of them has a probability 1 differential.

We then generalize the method we used to partially recover the linear layers used to whiten the core of this S-Box and illustrate it with a generic decomposition attack against 4-round Feistel Networks whitened with unknown linear layers. Our attack exploits a particular pattern arising in the Linear Approximations Table of such functions.

Domain-Specific Pseudonymous Signature schemes were recently proposed for privacy preserving authentication of digital identity documents by the BSI, German Federal Office for Information Security. The crucial property of domain-specific pseudonymous signatures is that a signer may derive unique pseudonyms within a so called domain. Now, the signer's true identity is hidden behind his domain pseudonyms and this pseudonyms are unlinkable, i.e. it is infeasible to correlate two pseudonyms with a single user. In this paper we take a critical look at the security definitions and constructions of domain-specific pseudonymous signatures proposed by far. We review two articles which propose ``sound and clean'' security definitions and point out some issues present in this models. Some of this issues may have a strong practical impact on constructions provable secure in this models. Additionally, we point out some worrisome facts about the proposed schemes and their security analysis.

In recent years, a new approach has been developed for verifying security protocols with the aim of combining the benefits of symbolic attackers and the benefits of unconditional soundness: the technique of the computationally complete symbolic attacker of Bana and Comon (BC). In this paper we argue that the real breakthrough of this technique is the recent introduction of its version for indistinguishability because, with the extensions we introduce here, for the first time, there is a computationally sound symbolic technique that is syntactically strikingly simple, to which translating standard computational security notions is a straightforward matter, and that can be effectively used for verification of not only equivalence properties, but trace properties of protocols as well. We first fully develop the core elements of this newer version by introducing several new axioms. We illustrate the power and the diverse use of the introduced axioms on simple examples first. We introduce an axiom expressing the Decisional Diffie-Hellman property. We analyze the Diffie-Hellman key exchange, both in its simplest form and an authenticated version as well. We provide computationally sound verification of real-or-random secrecy of the Diffie-Hellman key exchange protocol for multiple sessions, without any restrictions on the computational implementation other than the DDH assumption. We also show authentication for a simplified version of the station-to-station protocol using UF-CMA assumption for digital signatures. Finally, we axiomatize IND-CPA, IND-CCA1 and IND-CCA2 security properties and illustrate their usage.

Brakerski showed that linearly decryptable fully homomorphic encryption (FHE) schemes cannot be secure in the chosen plaintext attack (CPA) model. In this paper, we show that linearly decryptable FHE schemes cannot be secure even in the ciphertext only security model. Then we consider the maximum security that a linearly decryptable FHE scheme could achieve. This paper designs fully homomorphic symmetric key encryption (FHE) schemes without bootstrapping (that is, noise-free FHE schemes). The proposed FHE schemes are based on quaternion/octonion algebra and Jordan algebra over finite rings Z_n and are secure in the weak ciphertext-only security model assuming the hardness of solving multivariate quadratic equation systems and solving univariate high degree polynomial equation systems in Z_n. It is up to our knowledge that this is the first noise-free FHE scheme that has ever been designed with a security proof (even in the weak ciphertext-only security model). It is argued that the weak ciphertext-only security model is sufficient for various applications such as privacy preserving computation in cloud. As an example, the proposed FHE schemes are used to construct obfuscated programs. This example could be further used to show that the scheme presented in this paper could be combined with existing FHE schemes with bootstrapping to obtain more efficient FHE schemes with bootstrapping in the fully CPA model. At the end of the paper, we point out the insecurity of several recently proposed noise-free FHE schemes

Outsourcing secure multiparty computation(SMC) protocols has allowed resource-constrained devices to take advantage of these developing cryptographic primitives with great efficiency. While the existing constructions for outsourced SMC guarantee input and output privacy, they require that all parties know the function being evaluated. Thus, stronger security guarantees are necessary in applications where the function itself needs to be kept private. We develop the first linear-complexity protocols for outsourcing private function evaluation (PFE), a subset of SMC protocols that provide both input and function privacy. Assuming a semi-honest function holder, we build on the most efficient two-party PFE constructions to develop outsourced protocols that are secure against a semi-honest, covert, or malicious Cloud server and malicious mobile devices providing input to the function. Our protocols require minimal symmetric key operations and only two rounds of communication from the mobile participants. As a secondary contribution, we develop a technique for combining public and private sub-circuits in a single computation called partially-circuit private (PCP) garbling. This novel garbling technique allows us to apply auxiliary circuits to check for malicious behavior using only free-XOR overhead gates rather than the significantly more costly PFE gate construction. These protocols demonstrate the feasibility of outsourced PFE and provide a first step towards developing privacy-preserving applications for use in Cloud computing.

Event date: 6 July to 8 July 2016
Submission deadline: 26 June 2016
Notification: 10 July 2016

This is a full-time position is for up to 5 years, starting from April 1st 2016. The responsibilities include research and teaching. Successful applicants should hold a doctoral degree in Computer Science, or a related field,with post-qualification teaching and research experience. A research track record in Theoretical Computer Science, in the areas of Automated Verification, Computational Algebra, Computational Number Theory, or Logic is preferred.

Closing date for applications: 5 February 2016

Contact: James Worrell (jbw (at) cs.ox.ac.uk)

More information: http://www.cs.ox.ac.uk/news/1048-full.html

Am Institut für Enterprise Systems (InES) der Universität Mannheim ist zum nächstmöglichen Zeitpunkt eine Stelle zu besetzen für einen Post-Doc als Leiter des Kompetenzbereichs Security Analytics

Wir suchen Kandidaten mit abgeschlossener Promotion und nachgewiesenen Kompetenzen in mindestens einen der Bereiche „Angewandte IT-Sicherheit“ und „Datenanalyse“ und die Bereitschaft, sich gegebenenfalls in den anderen einzuarbeiten. Zu den Aufgaben gehören die eigenständige Beantragung und Durchführung von Forschungsprojekten sowie die fachliche Betreuung der entsprechenden Projektmitarbeiter. Erfahrungen in der Kooperation mit der Wirtschaft sind ein Vorteil. Die Position ist zunächst auf ein Jahr befristet. Es besteht die Option auf eine Verlängerung im Rahmen der üblichen Befristungsregelungen.

Aussagekräftige Bewerbungen sind möglichst in elektronischer Form zu richten an stuckenschmidt (at) uni-mannheim.de. Für Rückfragen stehen Prof. Stuckenschmidt und Prof. Armknecht zur Verfügung. Weitere Informationen zum InES finden sich im Web (http://www.ines.uni-mannheim.de).

Closing date for applications:

Contact: Prof. Heiner Stuckenschmidt - stuckenschmidt (at) uni-mannheim.de

Simeck is a new family of lightweight block ciphers proposed by Yang $et\ al.$ in CHES'15, which has efficient hardware implementation. In this paper, we find differentials with low hamming weight and high probability for Simeck using K\"olbl's tool, then we consider the links between the differential and linear characteristic to construct linear hulls for Simeck. We give improved linear hull attack with dynamic key-guessing techniques on Simeck according to the property of the AND operation. Our best results cover Simeck 32/64 reduced to 23 rounds, Simeck 48/96 reduced to 30 rounds, Simeck 64/128 reduced to 37 rounds. Our result is the best known so far for any variant of Simeck.

The simple matrix encryption scheme (Tao-Diene-Tang-Ding, PQCrypto 2013) has a problem of decryption failures. Quite recently, Petzoldt-Ding-Wang (http://eprint.iacr.org/2016/010) proposed a new version of this scheme called the tensor simple matrix encryption scheme to remove decryption failures by using a tensor product of two small matrices as its secret key. However, it is much weaker than the original scheme. In this note, we show that the tensor simple matrix encryption scheme is equivalent to a weak version of the original simple matrix encryption scheme.