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).

2015-07-16
18:11 [Pub][ePrint]

Statistical analysis of attacks on symmetric ciphers often require assuming the normal behaviour of a test statistic.

Typically such an assumption is made in an asymptotic sense. In this work, we consider concrete versions of some important

normal approximations that have been made in the literature. To do this, we use the Berry-Ess\\\'{e}en theorem to derive

explicit bounds on the approximation errors. Analysing these error bounds in the cryptanalytic context throws up several

surprising results. One important implication is that this puts in doubt the applicability of the order statistics

based approach for analysing key recovery attacks on block ciphers. This approach has been earlier used to obtain several

results on the data complexities of (multiple) linear and differential cryptanalysis. The non-applicability of the order

statistics based approach puts a question mark on the data complexities obtained using this approach. Fortunately, we

are able to recover all of these results by utilising the hypothesis testing framework. Detailed consideration of the

error in normal approximation also has implications for $\\chi^2$ and the log-likelihood ratio (LLR) based test statistics.

The normal approximation of the $\\chi^2$ test statistics has some serious and counter-intuitive restrictions. One such

restriction is that for multiple linear cryptanalysis as the number of linear approximations grows so does the requirement

on the number of plaintext-ciphertext pairs for the approximation to be proper. The issue of satisfactorily addressing the

problems with the application of the $\\chi^2$ test statistics remains open. For the LLR test statistics, previous work

used a normal approximation followed by another approximation to simplify the parameters of the normal approximation. We

derive the error bound for the normal approximation which turns out to be difficult to interpret. We show that the approximation

required for simplifying the parameters restricts the applicability of the result. Further, we argue that this approximation

is actually not required. More generally, the message of our work is that all cryptanalytic attacks should properly derive and

interpret the error bounds for any normal approximation that is made.

18:11 [Pub][ePrint]

We show the first positive results for the indifferentiability security of the confusion-diffusion networks (which are extensively used in the design of block ciphers and hash functions). In particular, our result shows that a constant number of confusion-diffusion rounds is sufficient to extend the domain of a public random permutation.

18:11 [Pub][ePrint]

A secure ad-hoc survey scheme enables a survey authority to independently (without any interaction) select an ad-hoc group of registered users based only on their identities (e.g., their email addresses), and create a survey where only selected users can anonymously submit exactly one response.

We present a formalization of secure ad-hoc surveys and present:

* an abstract provably-secure implementation based on standard cryptographic building blocks (which in particular are implied by the existence of enhanced trapdoor permutations in the CRS model);

* a practical instantiation of our abstract protocol, called ANONIZE, which is provably-secure in the random oracle model based on cryptographic assumptions on groups with bilinear maps.

As far as we know, ANONIZE constitutes the first implementation of a large-scale secure computation protocol (of non-trivial functionalities) that can scale to millions of users.

18:11 [Pub][ePrint]

MISTY1 is a block cipher designed by Matsui in 1997. It was well evaluated and standardized by projects, such as CRYPTREC, ISO/IEC, and NESSIE. In this paper, we propose a key recovery attack on the full MISTY1, i.e., we show that 8-round MISTY1 with 5 FL layers does not have 128-bit security. Many attacks against MISTY1 have been proposed, but there is no attack against the full MISTY1. Therefore, our attack is the first cryptanalysis against the full MISTY1. We construct a new integral characteristic by using the propagation characteristic of the division property, which was proposed in 2015. We first improve the division property by optimizing a public S-box and then construct a 6-round integral characteristic on MISTY1. Finally, we recover the secret key of the full MISTY1 with $2^{63.58}$ chosen plaintexts and $2^{121}$ time complexity. Moreover, if we can use $2^{63.994}$ chosen plaintexts, the time complexity for our attack is reduced to $2^{107.9}$. Note that our cryptanalysis is a theoretical attack. Therefore, the practical use of MISTY1 will not be affected by our attack.

18:11 [Pub][ePrint]

Following the line of work presented recently by Bellare, Paterson and Rogaway, we formalize and investigate the resistance of linear secret-sharing schemes to mass surveillance. This primitive is widely used to design IT systems in the modern computer world, and often it is implemented by a proprietary code that the provider (\"big brother\") could manipulate to covertly violate the privacy of the users (by implementing Algorithm-Substitution Attacks or ASAs). First, we formalize the security notion that expresses the goal of big brother and prove that for any linear secret-sharing scheme there exists an undetectable subversion of it that efficiently allows surveillance. Second, we formalize the security notion that assures that a sharing scheme is secure against ASAs and construct the first sharing scheme that meets this notion. This work could serve as an important building block towards constructing systems secure against mass surveillance.

18:11 [Pub][ePrint]

We present the first information-theoretic steganographic protocol with an asymptotically optimal ratio of key length to message length that operates on arbitrary covertext distributions with constant min-entropy. Our results are also applicable to the computational setting: our stegosystem can be composed over a pseudorandom generator to send longer messages in a computationally secure fashion. In this respect our scheme offers a significant improvement in terms of the number of pseudorandom bits generated by the two parties in comparison to previous results known in the computational setting. Central to our approach for improving the overhead for general distributions is the use of combinatorial constructions that have been found to be useful in other contexts for derandomization: almost $t$-wise independent function families.

18:11 [Pub][ePrint]

For $q$ a prime power, the discrete logarithm problem (DLP) in $\\mathbb{F}_{q}^{\\times}$ consists in finding, for any $g \\in \\mathbb{F}_{q}^{\\times}$ and $h \\in \\langle g \\rangle$, an integer $x$ such that $g^x = h$. For each prime $p$ we exhibit infinitely many extension fields $\\mathbb{F}_{p^n}$ for which the DLP in $\\mathbb{F}_{p^n}^{\\times}$ can be solved in expected quasi-polynomial time.

18:11 [Pub][ePrint]

Multi-server authentication is going to be an integral part of remote authentication with the passage of time. The remote authentication has been part and parcel of internet based communication. In the last decade several multi-server authentication techniques has been presented. However there is still a need of more efficient and robust techniques. Lately, Saraswathi et al., presented a multi-server authentication scheme that has been found under much vulnerability like stolen card attack, misrepresentation attack, and forward secrecy attacks. This paper presents the cryptanalysis for Saraswathi et al. scheme and shows the review analysis.

18:11 [Pub][ePrint]

Cryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these protocols, however, deals almost exclusively with classical attackers. If we accept that quantum information processing is the most realistic model of physically feasible computation, then we must ask: what classical protocols remain secure against quantum attackers?

Our main contribution is showing the existence of classical two-party protocols for the secure evaluation of any polynomial-time function under reasonable computational assumptions (for example, it suffices that the learning with errors problem be hard for quantum polynomial time). Our result shows that the basic two-party feasibility picture from classical cryptography remains unchanged in a quantum world.

18:11 [Pub][ePrint]

In this paper, we show efficient implementations of binary field multiplication over ARMv8.

We exploit an advanced 64-bit polynomial multiplication (\\texttt{PMULL}) supported by ARMv8

and conduct multiple levels of asymptotically faster Karatsuba multiplication.

Finally, our method conducts binary field multiplication within 57 and 153 clock cycles for B-251 and B-571, respectively.

Our proposed method on ARMv8 improves the performance by a factor of $5.5 \\sim 7.2$ times than previous techniques on ARMv7.

18:11 [Pub][ePrint]

Side channels provide additional information to skilled adversaries that reduce the effort to determine an unknown key. If sufficient side channel information is available, identification of the secret key can even become trivial. However, if not enough side information is available, some effort is still required to find the key in the key space (which now has reduced entropy). To understand the security implications of side channel attacks it is then crucial to evaluate this remaining effort in a meaningful manner. Quantifying this effort can be done by looking at two key questions: first, how deep\' (at most) is the unknown key in the remaining key space, and second, how expensive\' is it to enumerate keys up to a certain depth?

We provide results for these two challenges. Firstly, we show how to construct an extremely efficient algorithm that accurately computes the rank of a (known) key in the list of all keys, when ordered according to some side channel attack scores. Secondly, we show how our approach can be tweaked such that it can be also utilised to enumerate the most likely keys in a parallel fashion. We are hence the first to demonstrate that a smart and parallel key enumeration algorithm exists.