五十部 孝典

Whitebox cryptography aims to provide security for cryptographic algorithms in an untrusted environment where the adversary has full access to their implementation. Typical security goals for whitebox cryptography include key extraction security and decomposition security: Indeed, it should be infeasible to recover the secret key from the implementation and it should be hard to decompose the implementation by finding a more compact representation without recovering the secret key, which mitigates code lifting. Whereas all published whitebox implementations for standard cryptographic algorithms such as DES or AES are prone to practical key extraction attacks, there have been two dedicated design approaches for whitebox block ciphers: ASASA by Birykov et al. at ASIACRYPT'14 and SPACE by Bogdanov and Isobe at CCS'15. While ASASA suffers from decomposition attacks, SPACE reduces the security against key extraction and decomposition attacks in the white box to the security of a standard block cipher such as AES in the standard blackbox setting. However, due to the security-prioritized design strategy, SPACE imposes a sometimes prohibitive performance overhead in the real world as it needs many AES calls to encrypt a single block. In this paper, we address the issue by designing a family of dedicated whitebox block ciphers SPNbox and a family of underlying small block ciphers with software efficiency and constant-time execution in mind. While still relying on the standard blackbox block cipher security for the resistance against key extraction and decomposition, SPNbox attains speed-ups of up to 6.5 times in the black box and up to 18 times in the white box on Intel Skylake and ARMv8 CPUs, compared to SPACE. The designs allow for constant-time implementations in the blackbox setting and meet the practical requirements to whitebox cryptography in real-world applications such as DRM or mobile payments. Moreover, we formalize resistance towards decomposition in form of weak and strong space hardness at various security levels. We obtain bounds on space hardness in all those adversarial models. Thus, for the first time, SPNbox provides a practical whitebox block cipher that features well-understood key extraction security, rigorous analysis towards decomposition security, demonstrated real-world efficiency on various platforms and constant-time implementations. This paves the way to enhancing susceptible real-world applications with whitebox cryptography.

The all-subkeys recovery (ASR) attack is an extension of the meet-in-the-middle attack, which allows evaluating the security of a block cipher without analyzing its key scheduling function. Combining the ASR attack with some advanced techniques such as the function reduction and the repetitive ASR attack, we show the improved ASR attacks on the 7-round reduced FOX64 and FOX128. Moreover, the improved ASR attacks on the 119-, 105- and 99-round reduced KATAN32, KATAN48 and KATAN64, and the 42-round reduced SHACAL-2 are also presented, respectively. As far as we know, all of those attacks are the best single-key attacks with respect to the number of attacked rounds in literature.

The need for software security in untrusted environments is ever increasing. White-box cryptography aims to ensure the security of cryptographic algorithms when the attacker has full access to their implementations. However, there is no secure white-box implementation of standard block ciphers such as DES and AES known to date: All published techniques have been practically broken. In this paper, we revisit white-box cryptography and propose a family of white-box secure block ciphers SPACE with several novel features. The design of SPACE is such that the key-extraction security in the white box reduces to the well-studied problem of key recovery for block ciphers (AES in our example) in the standard black-box setting. Moreover, to mitigate code lifting, we introduce the notion of space hardness. It measures the difficulty of compressing the white-box implementation of a cipher, and quantifies security against code lifting by the amount of code that needs to be extracted from the implementation by a white-box attacker to maintain its functionality. SPACE includes several variants with different white-box code sizes. Therefore, it is applicable to a wide range of environments and use cases. One of the variants called N-SPACE can be implemented with different code sizes while keeping the cipher itself unchanged. SPACE offers a high level of space hardness: It is difficult to find a compact but still functional representation of SPACE given its white-box implementation. This property has several useful consequences for applications. First, it gets more challenging for a DRM attacker (e.g. in a pay TV setting) to scale a code-lifting attack and to distribute the break. Moreover, this paves the way for mass-surveillance resistant cryptography: If a large proportion of users dedicates a significant part of their computers' storage (e.g. HDD) to white-box SPACE implementations, it will be much more complex or even infeasible for governmental agencies to deal with the keys of all users simultaneously due to the limited storage available, forcing them to focus on targeted attacks instead. This consequence is especially important given Snowden's revelations on the extent of the mass surveillance practice by NSA and GCHQ. Finally, the usage of SPACE ciphers can mitigate the damage of having malware in security-critical systems such as networks processing top-secret data: As those are typically insulated from the Internet, the capacity of the communication channel from inside to outside the system is often limited, making it infeasible for Trojans to transmit the necessary key material.

In the past few years, lightweight cryptography has become a popular research discipline with a number of ciphers and hash functions proposed. The designers' focus has been predominantly to minimize the hardware area, while other goals such as low latency have been addressed rather recently only. However, the optimization goal of low energy for block cipher design has not been explicitly addressed so far. At the same time, it is a crucial measure of goodness for an algorithm. Indeed, a cipher optimized with respect to energy has wide applications, especially in constrained environments running on a tight power/energy budget such as medical implants. This paper presents the block cipher Midori (The name of the cipher is the Japanese translation for the word Green.) that is optimized with respect to the energy consumed by the circuit per bt in encryption or decryption operation. We deliberate on the design choices that lead to low energy consumption in an electrical circuit, and try to optimize each component of the circuit as well as its entire architecture for energy. An added motivation is to make both encryption and decryption functionalities available by small tweak in the circuit that would not incur significant area or energy overheads. We propose two energy-efficient block ciphers Midori128 and Midori64 with block sizes equal to 128 and 64 bits respectively. These ciphers have the added property that a circuit that provides both the functionalities of encryption and decryption can be designed with very little overhead in terms of area and energy. We compare our results with other ciphers with similar characteristics: it was found that the energy consumptions of Midori64 and Midori128 are by far better when compared ciphers like PRINCE and NOEKEON.

While traditionally cryptographic algorithms have been designed with the black-box security in mind, they often have to deal with a much stronger adversary - namely, an attacker that has some access to the execution environment of a cryptographic algorithm. This can happen in such grey-box settings as physical side-channel attacks or digital forensics as well as due to Trojans. In this paper, we aim to address this challenge for symmetric-key cryptography. We study the security of the Advanced Encryption Standard (AES) in the presence of explicit leakage: We let a part of the internal secret state leak in each operation. We consider a wide spectrum of settings - from adversaries with limited control all the way to the more powerful attacks with more knowledge of the computational platform. To mount key recoveries under leakage, we develop several novel cryptanalytic techniques such as differential bias attacks. Moreover, we demonstrate and quantify the effect of uncertainty and implementation countermeasures under such attacks: black-boxed rounds, space randomization, time randomization, and dummy operations. We observe that the residual security of AES can be considerable, especially with uncertainty and basic countermeasures in place.

RC4 is a widely-used stream cipher, adopted in many standard protocols, such as WEP, WPA and SSL/TLS, as a standard encryption algorithm. Isobe et al. proposed a plaintext recovery attack on RC4 in the broadcast setting, where the same plaintext is encrypted with different secret keys. Their attack is able to recover the first 257 bytes by exploiting the biases of the initial bytes of a keystream. In this paper, we propose two types of full plaintext recovery attacks that are able to recover all the bytes, even after the 258th byte, of a plaintext, unlike Isobe et al.'s attack. To achieve this, we combine the use of multiple keystream biases appropriately. The first attack utilizes the initial byte biases and Mantin's long-term bias. This attack can recover the first 1000 terabytes of a plaintext from 234 ciphertexts with a probability of almost one. The second attack is based on two long-term biases. Since this attack does not rely on the biases of the initial bytes of the RC4 keystream, it can recover any byte of a plaintext, even if the initial bytes are disregarded. Given 235 ciphertexts encrypted by different keys, any byte of a target plaintext can be recovered with a probability close to one.

In FSE 2013, Isobe et al. proposed efficient plaintext recovery attacks on RC4 in the broadcast setting where the same plaintext is encrypted with different user keys. Their attack is able to recover first 1000 terabytes of a plaintext with probability of almost one, given 2(34) ciphertexts encrypted by different keys. Since their attack essentially exploits biases in the initial (1st to 257th) bytes of the keystream, it does not work any more if such initial bytes are disregarded. This paper proposes two advanced plaintext recovery attacks that can recover any byte of a plaintext without relying on initial biases, i.e., our attacks are feasible even if initial bytes of the keystream are disregarded. The first attack is the modified Isobe et al. 's attack. Using the partial knowledge of the target plaintext, e.g., only 6 bytes of the plaintext, the other bytes can be recovered with the high probability from 2(34) ciphertexts. The second attack does not require any previous knowledge of a plaintext. In order to achieve it, we develop a guess-and-determine plaintext recovery method based on two strong long-term biases. Given 2(35) ciphertexts, any byte of a plaintext can be recovered with probability close to one.

This paper investigates the practical security of RC4 in broadcast setting where the same plaintext is encrypted with different user keys. We introduce several new biases in the initial (1st to 257th) bytes of the RC4 keystream, which are substantially stronger than known biases. Combining the new biases with the known ones, a cumulative list of strong biases in the first 257 bytes of the RC4 keystream is constructed. We demonstrate a plaintext recovery attack using our strong bias set of initial bytes by the means of a computer experiment. Almost all of the first 257 bytes of the plaintext can be recovered, with probability more than 0.8, using only 2(32) ciphertexts encrypted by randomly-chosen keys. We also propose an efficient method to extract later bytes of the plaintext, after the 258th byte. The proposed method exploits our bias set of first 257 bytes in conjunction with the digraph repetition bias proposed by Mantin in EUROCRYPT 2005, and sequentially recovers the later bytes of the plaintext after recovering the first 257 bytes. Once the possible candidates for the first 257 bytes are obtained by our bias set, the later bytes can be recovered from about 2(34) ciphertexts with probability close to 1.

RC4 is a stream cipher designed by Rivest in 1987. It is the most famous stream cipher and widely used e.g., SSL/TLS, WEP and WPA. Although RC4 in particular implementations and settings such as theWEP implementation and the broadcast setting, was already broken, RC4 itself is not completely broken yet. In 2011, Teramura et al. generalized classes of weak keys of RC4 by using the predictive state, which are special classes of the internal state of RC4. The total number of Teramura et al.'s weak keys is approximately 2117.29. Their weak-key attack can recover a 128-bit secret key with efficiency of 295.10, where efficiency is defined as time complexity per success probability of the attack. This attack works only if particular patterns of the keystream are observed. In this paper, we further expand weak-key space of RC4. By thoroughly analyzing the relation between the key and the initial state of the pseudorandom generation algorithm, we can find new classes of predictive state which are utilized for key recovery attacks. As a result, 2118.58 keys can be defined as new weak keys, whose number is more than twice the number of Teramura et al.'s weak keys. Moreover, our attack is applicable to any keystream, while Teramura et al.'s attack is feasible only in particular patterns of the keystream. Given any keystream, our weak-key attack can recover a 128-bit secret key with efficiency of 2115.11. Our attack is the best-known single-key key recovery attack on RC4 with respect to efficiency. In addition, if we focus on specific keystreams similar to Teramura et al.'s attack, the 128-bit secret key can be recovered with efficiency of 276.32, which is more efficient than Teramura et al.'s attack. © 2014 Information Processing Society of Japan.

After the disclosure of the RC4 algorithm in 1994, a number of keystream biases of RC4 were reported, e.g., Mantin and Shamir showed that the second byte of the keystream is biased to 0, Sepehrdad et al. found that the l-th byte of the keystream is biased to -l, and Maitra et al. showed that 3rd to 255th bytes of the keystream are also biased to 0, where l is the keylength in byte. However, it is unknown that which bias is strongest in each byte of initial bytes. This paper comprehensively analyzes initial keystream biases of RC4. In particular, we introduce several new biases in the initial (1st to 257th) bytes of the RC4 keystream, which are substantially stronger than known biases. Combining the new biases with the known ones, a complete list of strongest single-byte biases in the first 257 bytes of the RC4 keystream is constructed for the first time. Then, we show that our set of these biases are applicable to plaintext recovery attacks, key recovery attacks and distinguishing attacks.

This paper gives a first security evaluation of a lightweight stream cipher RAKAPOSHI. In particular, we analyze a slide property of RAKAPOSHI such that two different Key-IV pairs generate the same keystream but n-bit shifted. To begin with, we demonstrate that any Key-IV pair has a corresponding slide Key-IV pair that generates an n-bit shifted keystream with a probability of 2^-2n. In order to experimentally support our results, some examples of such pairs are given. Then, we show that this property is able to be converted into key recovery attacks on RAKAPOSHI. In the related-key setting, our attack based on the slide property can recover a 128-bit key with a time complexity of 2⁴¹ and 2³⁸ chosen IVs. Moreover, by using a variant of slide property called partial slide pair, this attack is further improved, and then a 128-bit key can be recovered with a time complexity of 2³³ and 2³⁰ chosen IVs. Finally, we present a method for speeding up the brute force attack by a factor of 2 in the single key setting.

We revisit meet-in-the-middle (MITM) attacks on block ciphers. Despite recent significant improvements of the MITM attack, its application is still restrictive. In other words, most of the recent MITM attacks work only on block ciphers consisting of a bit permutation based key schedule such as KTANTAN, GOST, IDEA, XTEA, LED and Piccolo. In this paper, we extend the MITM attack so that it can be applied to a wider class of block ciphers. In our approach, MITM attacks on block ciphers consisting of a complex key schedule can be constructed. We regard all subkeys as independent variables, then transform the game that finds the user-provided key to the game that finds all independent subkeys. We apply our approach called all subkeys recovery (ASR) attack to block ciphers employing a complex key schedule such as CAST-128, SHACAL-2, KATAN, FOX128 and Blowfish, and present the best attacks on them with respect to the number of attacked rounds in literature. Moreover, since our attack is simple and generic, it is applied to the block ciphers consisting of any key schedule functions even if the key schedule is an ideal function. © 2013 Springer-Verlag Berlin Heidelberg.

We propose new generic key recovery attacks on Feistel-type block ciphers. The proposed attack is based on the all subkeys recovery approach presented in SAC 2012, which determines all subkeys instead of the master key. This enables us to construct a key recovery attack without taking into account a key scheduling function. With our advanced techniques, we apply several key recovery attacks to Feistel-type block ciphers. For instance, we show 8-, 9- and 11-round key recovery attacks on n-bit Feistel ciphers with 2n-bit key employing random keyed F-functions, random F-functions, and SP-type F-functions, respectively. Moreover, thanks to the meet-in-the-middle approach, our attack leads to low-data complexity. To demonstrate the usefulness of our approach, we show a key recovery attack on the 8- round reduced CAST-128, which is the best attack with respect to the number of attacked rounds. Since our approach derives the lower bounds on the numbers of rounds to be secure under the single secret key setting, it can be considered that we unveil the limitation of designing an efficient block cipher by a Feistel scheme such as a low-latency cipher.

KATAN/KTANTAN is a family of hardware oriented block ciphers proposed at CHES 2009. Although the KTANTAN family have been broken by a meet-in-the-middle approach, the KATAN family are secure at present. In this paper, we investigate the KATAN family in the related-key boomerang framework with several techniques. By using an efficient differential characteristics search method, long boomerang distinguishers can be built. Furthermore, the key recovery phase is optimized by exploiting several properties of the round function such as the high linearity of the round function and the slow key diffusion. As a result, we can attack 174, 145 and 130 rounds of KATAN32, KATAN48 and KATAN64, which substantially improve the known best results whose attacked rounds are 120, 103, 94 rounds, respectively. Our attacks are confirmed by various experimental verifications, especially, we give concrete right quartets for KATAN32. © 2013 Springer-Verlag.

The GOST block cipher is the Russian encryption standard published in 1989. In spite of considerable cryptanalytic efforts over the past 20 years, a key recovery attack on the full GOST block cipher without any key conditions (e.g., weak keys and related keys) has not been published yet. In this paper, we show the first single-key attack, which works for all key classes, on the full GOST block cipher. To begin, we develop a new attack framework called Reflection-Meet-in-the-Middle Attack. This approach combines techniques of the reflection attack and the meet-in-the-middle (MITM) attack. Then we apply it to the GOST block cipher employing bijective S-boxes. In order to construct the full-round attack, we use additional novel techniques which are the effective MITM techniques using equivalent keys on a small number of rounds. As a result, a key can be recovered with a time complexity of 2225 encryptions and 232 known plaintexts. Moreover, we show that our attack is applicable to the full GOST block cipher using any S-boxes, including non-bijective S-boxes. © 2012 International Association for Cryptologic Research.

This paper gives a first security evaluation of a lightweight stream cipher RAKAPOSHI. In particular, we analyze a slide property of RAKAPOSHI such that two different Key-IV pairs generate the same keystream but n-bit shifted. To begin with, we demonstrate that any Key-IV pair has a corresponding slide Key-IV pair that generates an nbit shifted keystream with a probability of 2-2n. In order to experimentally support our results, some examples of such pairs are given. Then, we show that this property is able to be converted into key recovery attacks on RAKAPOSHI. In the related-key setting, our attack based on the slide property can recover a 128-bit key with a time complexity of 241 and 238 chosen IVs. Moreover, by using a variant of slide property called partial slide pair, this attack is further improved, and then a 128-bit key can be recovered with a time complexity of 233 and 230 chosen IVs. Finally, we present a method for speeding up the brute force attack by a factor of 2 in the single key setting. © 2013 Information Processing Society of Japan.

In this paper, we analyze a slide property of RAKAPOSHI stream cipher. To begin, we show that any Key-IV pair has a corresponding slide Key-IV pair that generates an n-bit shifted keystream with probability of 2 -2n . Then we exploit this property in order to develop a key recovery attack on RAKAPOSHI in the related key setting. Our attack is able to recover a 128-bit key with time complexity of 2 41 and 2 38 chosen IVs. The result reveals that RAKAPOSHI is vulnerable to the related key attack. After that, we consider a variant of the slide property, called partial slide property. It enables us to construct a method for speeding up the brute force attack by a factor of 2 in the single key setting. Finally, we consider a slide property of K2 v2.0 stream cipher, and discuss the possibility of an attack exploiting the slide property. © Springer-Verlag Berlin Heidelberg 2012.

In this paper, we present a new technique to construct a collision attack from a particular preimage attack which is called a partial target preimage attack. Since most of the recent meet-in-the-middle preimage attacks can be regarded as the partial target preimage attack, a collision attack is derived from the meet-in-the-middle preimage attack. By using our technique, pseudo collisions of the 43-step reduced SHA-256 and the 46-step reduced SHA-512 can be obtained with complexities of 2(126) and 2(254.5), respectively. As far as we know, our results are the best pseudo collision attacks on both SHA-256 and SHA-512 in literature. Moreover, we show that our pseudo collision attacks can be extended to 52 and 57 steps of SHA-256 and SHA-512, respectively, by combined with the recent preimage attacks on SHA-2 by bicliques. Furthermore, since the proposed technique is quite simple, it can be directly applied to other hash functions. We apply our algorithm to several hash functions including Skein and BLAKE, which are the SHA-3 finalists. We present not only the best pseudo collision attacks on SHA-2 family, but also a new insight of relation between a meet-in-the-middle preimage attack and a pseudo collision attack.

In this paper, we investigate the security of the lightweight block ciphers against the meet-in-the-middle (MITM) attack. Since the MITM attack mainly exploits low key-dependency in a key expanding function, the block ciphers having a simple key expanding function are likely to be vulnerable to the MITM attack. On the other hand, such a simple key expanding function leads compact implementation, and thus is utilized in several lightweight block ciphers. However, the security of such lightweight block ciphers against the MITM attack has not been studied well so far. We apply the MITM attack to the ciphers, then give more accurate security analysis for them. Specifically, combining thorough analysis with new techniques, we present the MITM attacks on 29, 8, 16, 14 and 21 rounds of XTEA, LED-64, LED-128, Piccolo-80 and Piccolo-128, respectively. Consequently, it is demonstrated that the MITM attack is the most powerful attack in the single-key setting on those ciphers with respect to the number of attacked rounds. Moreover, we consider the possibility of applying the recent speed-up keysearch based on MITM attack to those ciphers. © 2012 Springer-Verlag.

The GOST block cipher is the Russian encryption standard published in 1989. In spite of considerable cryptanalytic efforts over the past 20 years, a key recovery attack on the full GOST block cipher without any key conditions (e.g., weak keys and related keys) has not been published yet. In this paper, we show a first single-key attack, which works for all key classes, on the full GOST block cipher. To construct the attack, we develop a new attack framework called Reflection-Meet-in-the- Middle Attack. This approach combines techniques of the reflection attack and the meet-in-the-middle attack. We apply it to the GOST block cipher with further novel techniques which are the effective MITM techniques using equivalent keys on short rounds. As a result, a key can be recovered with 2(225) computations and 2(32) known plaintexts.

We propose a new 64-bit blockcipher Piccolo supporting 80 and 128-bit keys. Adopting several novel design and implementation techniques, Piccolo achieves both high security and notably compact implementation in hardware. We show that Piccolo offers a sufficient security level against known analyses including recent related-key differential attacks and meet-in-the-middle attacks. In our smallest implementation, the hardware requirements for the 80 and the 128-bit key mode are only 683 and 758 gate equivalents, respectively. Moreover, Piccolo requires only 60 additional gate equivalents to support the decryption function due to its involution structure. Furthermore, its efficiency on the energy consumption which is evaluated by energy per bit is also remarkable. Thus, Piccolo is one of the competitive ultra-lightweight blockciphers which are suitable for extremely constrained environments such as RFID tags and sensor nodes.

This paper shows new preimage attacks on reduced Tiger and SHA-2. Indesteege and Preneel presented a preimage attack oil Tiger reduced to 13 rounds (out of 24) with a complexity of 2(128.5). Our new preimage attack finds a one-block preimage of Tiger reduced to 16 rounds with a complexity of 2(161). The proposed attack is based on meet-in-the-middle attacks. It seems difficult to find "independent; words" of Tiger at first glance, since its key schedule function is much more complicated than that of MD4 or MD5. However, we developed techniques to find independent words efficiently by controlling its internal variables. Surprisingly, the similar techniques can be applied to SHA-2 including both SHA-256 and SHA-512. We present a one-block preimage attack on SHA-256 and SHA-512 reduced to 24 (out of 64 and 80) steps with a complexity of 2(240) and 2(480), respectively. To the best of our knowledge, our attack is the best known preimage attack on reduced-round Tiger and our preimage attack on reduced-step SHA-512 is the first result. Furthermore, our preimage attacks can also be extended to second preimage attacks directly, because our attacks can obtain random preimages from an arbitrary IV and an arbitrary target.

In this paper, we propose an effective key recovery attack on stream ciphers Py and Pypy with chosen IVs. Our method uses an internal-state correlation based on the vulnerability that the randomization of the internal state in the KSA is inadequate, and it improves two previous attacks proposed by Wu and Preneel (a WP-1 attack and a WP-2 attack). For a 128-bit key and a 128-bit IV, the WP-1 attack can recover a key with 223 chosen IVs and time complexity 2(72). First, we improve the WP-1 attack by using the internal-state correlation (called a P-1 attack). For a 128-bit key and a 128-bit IV, the P-1 attack can recover a key with 223 chosen IVs and time complexity 248, which is 1/2(24) of that of the WP-1 attack. The WP-2 attack is another improvement on the WP-1 attack, and it has been known as the best previous attack against Py and Pypy. For a 128-bit key and a 128-bit IV, the WP-2 attack can recover a key with 223 chosen IVs and time complexity 2(24). Second, we improve the WP-2 attack by using the internal-state correlation as well as the P-1 attack (called a P-2 attack). For a 128-bit key and a 128-bit IV, the P-2 attack can recover a key with 223 chosen IVs and time complexity 224, which is the same capability as that of the WP-2 attack. However, when the IV size is from 64 bits to 120 bits, the P-2 attack is more effective than the WP-2 attack. Thus, the P-2 attack is the known best attack against Py and Pypy.