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]

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.

18:11 [Pub][ePrint]

Dividing last level caches into slices is a popular method to prevent memory accesses from becoming a bottleneck on modern multicore processors. In order to assess and understand the benefits of cache slicing in detail, a precise knowledge of implementation details such as the slice selection algorithm are of high importance.

However, slice selection methods are mostly unstudied, and processor manufacturers choose not to publish their designs, nor their design rationale.

In this paper, we present a tool that allows to recover the slice selection algorithm for Intel processors. The tool uses cache access information to derive equations that allow the reconstruction of the applied slice selection algorithm. Thereby, the tool provides essential information for performing last level cache attacks and enables further exploration of the behavior of modern caches.

The tool is successfully applied to a range of Intel CPUs with different slices and architectures. Results show that slice selection algorithms have become more complex over time by involving an increasing number of bits of the physical address. We also demonstrate that among the most recent processors, the slice selection algorithm depends on the number of CPU cores rather than the processor model.

18:11 [Pub][ePrint]

Emerging applications such as the Internet of Things require security solutions that are small and low cost, yet feature solid protection against a wide range of sophisticated attacks. Lightweight cryptographic schemes such as the Speck cipher that was recently proposed by the NSA aim to solve some of these challenges. However, before using Speck in any practical application, sound protection against side-channel attacks must be in place. In this work, we propose a bit-serialized implementation of Speck, to achieve minimal area footprint. We further propose a Speck core that is provably secure against first-order side-channel attacks using a threshold implementation technique which depends on secure multiparty computation. The resulting design is a tiny crypto core that provides AES-like security in under 45 slices on a low-cost Xilinx Spartan 3 FPGA. The first-order side-channel resistant version of the same core needs less than 100 slices. The security of the protected core is validated by state-of-the-art side-channel leakage detection tests.

18:11 [Pub][ePrint]

We explicitly present a homomorphic encryption scheme with a flexible encoding of plaintexts. We prove its security under the LWE assumption, and innovatively show how the scheme can be used to handle computations over both binary strings and real numbers. In addition, using the scheme and its features, we build fast and secure systems of

- linear regression using gradient descent, namely finding a reasonable linear relation between data items which remain encrypted. Compared to the best previous work over a simulated dataset of $10^8$ records each with 20 features, our system dramatically reduces the server running time from about 8.75 hours (of the previous work) to only about 10 minutes.

- biometric authentication, in which we show how to reduce ciphertext sizes by half and to do the computation at the server very fast, compared with the state-of-the-art.

Moreover, as key rotation is a vital task in practice and is recommended by many authorized organizations for key management,

- we show how to do key rotation over encrypted data, without any decryption involved, and yet homomorphic properties of ciphertexts remain unchanged. In addition, our method of doing key rotation handles keys of different security levels (e.g., 80- and 128-bit securities), so that the security of ciphertexts and keys in our scheme can be \"updated\", namely can be changed into a higher security level.