International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

2015-05-06
15:17 [Pub][ePrint] Dickson Polynomials that are Involutions, by Pascale Charpin and Sihem Mesnager and Sumanta Sarkar

  Dickson polynomials which are permutations are interesting combinatorial objects and well studied. In this paper, we describe Dickson polynomials of the first kind in $\\mathbb{F}_2[x]$ that are involutions over finite fields of characteristic $2$. Such description is obtained using modular arithmetic\'s tools. We give results related to the cardinality and the number of fixed points (in the context of cryptographic application) of this corpus. We also present a class of Dickson involutions with high degree.



12:17 [Pub][ePrint] Dumb Crypto in Smart Grids: Practical Cryptanalysis of the Open Smart Grid Protocol, by Philipp Jovanovic and Samuel Neves

  This paper analyses the cryptography used in the Open Smart Grid Protocol

(OSGP). The authenticated encryption (AE) scheme deployed by OSGP is a

non-standard composition of RC4 and a home-brewed MAC, the ``OMA digest\'\'.

We present several practical key-recovery attacks against the OMA digest. The

first and basic variant can achieve this with a mere $13$ queries to an OMA

digest oracle and negligible time complexity. A more sophisticated version

breaks the OMA digest with only $4$ queries and a time complexity of about

$2^{25}$ simple operations. A different approach only requires one arbitrary

valid plaintext-tag pair, and recovers the key in an average of $144$

\\emph{message verification} queries, or one ciphertext-tag pair and $168$

\\emph{ciphertext verification} queries.

Since the encryption key is derived from the key used by the OMA digest, our

attacks break both confidentiality and authenticity of OSGP.





2015-05-05
21:17 [Pub][ePrint] Survey on Cryptographic Obfuscation, by Máté Horváth

  The recent result of Garg et al. (FOCS 2013) changed the previously pessimistic attitude towards general purpose cryptographic obfuscation. Since their first candidate construction, several authors proposed newer and newer schemes with more persuasive security arguments and better efficiency. At the same time, indistinguishability obfuscation proved its extreme usefulness by becoming the basis of many solutions for long-standing open problems in cryptography e.g. functional or witness encryption and others.

In this survey, we give an overview of recent research, focusing on the theoretical results on general purpose obfuscation, particularly, indistinguishability obfuscation.



21:17 [Pub][ePrint] A study of Pair Encodings: Predicate Encryption in prime order groups, by Shashank Agrawal and Melissa Chase

  Pair encodings and predicate encodings, recently introduced by Attrapadung (Eurocrypt 2014) and Wee (TCC 2014) respectively, greatly simplify the process of designing and analyzing predicate and attribute-based encryption schemes. However, they are still somewhat limited in that they are restricted to composite order groups, and the information theoretic properties are not sufficient to argue about many of the schemes. Here we focus on pair encodings, as the more general of the two. We first study the structure of these objects, then propose a new relaxed but still information theoretic security property. Next we show a generic construction for predicate encryption in prime order groups from our new property; it results in either selective or full security depending on the encoding, and gives security under SXDH or DLIN. Finally, we demonstrate the range of our new property by using it to design the first selectively secure CP-ABE scheme with constant size ciphertexts.



21:17 [Pub][ePrint] On the Optimality of Non-Linear Computations of Length-Preserving Encryption Schemes, by Mridul Nandi

  It is well known that three and four rounds of balanced Feistel cipher or Luby-Rackoff (LR) encryption for two blocks messages are pseudorandom permutation (PRP) and strong pseudorandom permutation (SPRP) respectively. A {\\bf block} is $n$-bit long for some positive integer $n$ and a (possibly keyed) {\\bf block-function} is a nonlinear function mapping all blocks to themselves, e.g. blockcipher. XLS (eXtended Latin Square) with three blockcipher calls was claimed to be SPRP and later which is shown to be wrong. Motivating with these observations, we consider the following questions in this paper: {\\em What is the minimum number of invocations of block-functions required to achieve PRP or SPRP security over $\\ell$ blocks inputs}? To answer this question, we consider all those length-preserving encryption schemes, called {\\bf linear encryption mode}, for which only nonlinear operations are block-functions. Here, we prove the following results for these encryption schemes:

(1) At least $2\\ell$ (or $2\\ell-1$) invocations of block-functions are required to achieve SPRP (or PRP respectively). These bounds are also tight.

(2) To achieve the above bound for PRP over $\\ell > 1$ blocks, either we need at least two keys or it can not be {\\em inverse-free} (i.e., need to apply the inverses of block-functions in the decryption). In particular, we show that a single-keyed block-function based, inverse-free PRP needs $2\\ell$ invocations.

(3) We show that 3-round LR using a single-keyed pseudorandom function (PRF) is PRP if we xor a block of input by a masking key.



21:17 [Pub][ePrint] STRIBOB / WHIRLBOB Security Analysis Addendum, by Markku-Juhani O. Saarinen

  This memo collects references to published cryptanalytic results

which are directly relevant to the security evaluation of CAESAR first

round algorithm STRIBOB and its second round tweaked variant, WHIRLBOB.

During the first year after initial publication of STRIBOB and WHIRLBOB,

no cryptanalytic

breaks or other serious issues have emerged. The main difference in

the security between the two variants is that WHIRLBOB allows easier

creation of constant-time software implementations resistant to cache

timing attacks.



21:17 [Pub][ePrint] HETest: A Homomorphic Encryption Testing Framework, by Mayank Varia and Sophia Yakoubov and Yang Yang

  In this work, we present a generic open-source software framework that can evaluate the correctness and performance of homomorphic encryption software. Our framework, called HEtest, auto- mates the entire process of a test: generation of data for testing (such as circuits and inputs), execution of a test, comparison of performance to an insecure baseline, statistical analysis of the test results, and production of a LaTeX report. To illustrate the capability of our framework, we present a case study of our analysis of the open-source HElib homomorphic encryption software. We stress though that HEtest is written in a modular fashion, so it can easily be adapted to test any homomorphic encryption software.



21:17 [Pub][ePrint] Order-Revealing Encryption and the Hardness of Private Learning, by Mark Bun and Mark Zhandry

  An order-revealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying plaintexts. We show how to use order-revealing encryption to separate computationally efficient PAC learning from efficient $(\\epsilon, \\delta)$-differentially private PAC learning. That is, we construct a concept class that is efficiently PAC learnable, but for which every efficient learner fails to be differentially private. This answers a question of Kasiviswanathan et al. (FOCS \'08, SIAM J. Comput. \'11).

To prove our result, we give a generic transformation from an order-revealing encryption scheme into one with strongly correct comparison, which enables the consistent comparison of ciphertexts that are not obtained as the valid encryption of any message. We believe this construction may be of independent interest.



21:17 [Pub][ePrint] Optimized Interpolation Attacks on LowMC, by Itai Dinur and Yunwen Liu and Willi Meier and Qingju Wang

  LowMC is a collection of block cipher families introduced at Eurocrypt 2015 by Albrecht et al. Its design is optimized for instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. A unique feature of LowMC is that its internal affine layers are chosen at random, and thus each block cipher family contains a huge number of instances. The Eurocrypt paper proposed two specific block cipher families of LowMC, having 80-bit and 128-bit keys.

In this paper, we mount interpolation attacks (algebraic attacks introduced by Jakobsen and Knudsen) on LowMC, and show that a practically significant fraction of $2^{-38}$ of its 80-bit key instances could be broken $2^{23}$ times faster than exhaustive search. Moreover, essentially all instances that are claimed to provide 128-bit security could be broken about $1000$ times faster. In order to obtain these results, we had to develop novel techniques and optimize the original interpolation attack in new ways. While some of our new techniques exploit specific internal properties of LowMC, others are more generic and could be applied, in principle, to any block cipher.



21:17 [Pub][ePrint] Non-invasive Spoofing Attacks for Anti-lock Braking Systems, by Yasser Shoukry and Paul Martin and Paulo Tabuada and Mani B. Srivastava

  This work exposes a largely unexplored vector of physical-layer attacks with demonstrated consequences in automobiles. By modifying the physical environment around analog sensors such as Antilock Braking Systems (ABS), we exploit weaknesses in wheel speed sensors so that a malicious attacker can inject arbitrary measurements to the ABS computer which in turn can cause life-threatening situations. In this paper, we describe the development of a prototype ABS spoofer to enable such attacks and the potential consequences of remaining vulnerable to these attacks. The class of sensors sensitive to these attacks depends on the physics of the sensors themselves. ABS relies on magnetic--based wheel speed sensors which are exposed to an external attacker from underneath the body of a vehicle. By placing a thin electromagnetic actuator near the ABS wheel speed sensors, we demonstrate one way in which an attacker can inject magnetic fields to both cancel the true measured signal and inject a malicious signal, thus spoofing the measured wheel speeds. The mounted attack is of a non-invasive nature, requiring no tampering with ABS hardware and making it harder for failure and/or intrusion detection mechanisms to detect the existence of such an attack. This development explores two types of attacks: a disruptive, naive attack aimed to corrupt the measured wheel speed by overwhelming the original signal and a more advanced spoofing attack, designed to inject a counter-signal such that the braking system mistakenly reports a specific velocity. We evaluate the proposed ABS spoofer module using industrial ABS sensors and wheel speed decoders, concluding by outlining the implementation and lifetime considerations of an ABS spoofer with real hardware.



21:17 [Pub][ePrint] What Information is Leaked under Concurrent Composition?, by Vipul Goyal and Divya Gupta and Abhishek Jain

  Achieving security under concurrent composition is notoriously hard. Indeed, in the plain model, far reaching impossibility results for concurrently secure computation are known. On the other hand, some positive results have also been obtained according to various weaker notions of security (such as by using a super-polynomial time simulator). This suggest that somehow, ``not all is lost in the concurrent setting.\"

In this work, we ask what and exactly how much private information can the adversary learn by launching a concurrent attack? ``Can he learn all the private inputs in all the sessions? Or, can we preserve the security of some (or even most) of the sessions fully while compromising (a small fraction of) other sessions? Or is it the case that the security of all (or most) sessions is (at least partially) compromised? If so, can we restrict him to learn an arbitrarily small fraction of input in each session?\" We believe the above questions to be fundamental to the understanding of concurrent composition. Indeed, despite a large body of work on the study of concurrent composition, in our opinion, the understanding of what exactly is it that goes wrong in the concurrent setting and to what extent is currently quite unsatisfactory.

Towards that end, we adopt the knowledge-complexity based approach of Goldreich and Petrank [STOC\'91] to quantify information leakage in concurrently secure computation. We consider a model where the ideal world adversary (a.k.a simulator) is allowed to query the trusted party for some ``leakage\'\' on the honest party inputs. We obtain both positive and negative results, depending upon the nature of the leakage queries available to the simulator. Informally speaking, our results imply the following: in the concurrent setting, ``significant loss\" of security (translating to high leakage in the ideal world) in some of the sessions is unavoidable if one wishes to obtain a general result. However on the brighter side, one can make the fraction of such sessions to be an arbitrarily small polynomial (while fully preserving the security in all other sessions). Our results also have an implication on secure computation in the bounded concurrent setting [Barak-FOCS\'01]: we show there exist protocols which are secure as per the standard ideal/real world notion in the bounded concurrent setting. However if the actual number of sessions happen to exceed the bound, there is a graceful degradation of security as the number of sessions increase. (In contrast, prior results do not provide any security once the bound is exceeded.)

In order to obtain our positive result, we model concurrent extraction as the classical set-covering problem and develop, as our main technical contribution, a new sparse rewinding strategy. Specifically, unlike previous rewinding strategies which are very ``dense\'\', we rewind ``small intervals\'\' of the execution transcript and still guarantee extraction. This yields other applications as well, including improved constructions of precise concurrent zero-knowledge [Pandey et al.-Eurocrypt\'08] and concurrently secure computation in the multiple ideal query model [Goyal et al.-Crypto\'10].

In order to obtain our negative results, interestingly, we employ techniques from the regime of leakage-resilient cryptography [Dziembowski-Pietrzak-FOCS\'08].