CLEFIA is a 128-bit block cipher proposed by Shirai et al. in 2007. On its saturation attack, Tsunoo et al. reported peculiar saturation characteristics in 2010. They formulated some hypotheses on the existence of the characteristics with no proof. In this paper we have theoretically proved their hypotheses. In their attack scenario, we show that the mod-2 distribution is a code word of Extended Hamming code, and then proof is given by using the property of Hadamard transform.

We introduce an efficient interpolation attack which gives the tighter upper bound of the complexity and the number of pairs of plaintexts and ciphertexts required for the attack. In the previously known interpolation attack there is a problem in that the required complexity for the attack can be overestimated. We solve this problem by first, finding the actual number of coefficients in the polynomial used in the attack by using a computer algebra system, and second, by finding the polynomial with fewer coefficients by choosing the plaintexts. We apply this interpolation attack to the block cipher SNAKE and succeeded in attacking many ciphers in the SNAKE family. When we evaluate the resistance of a block cipher to interpolation attack, it is necessary to apply the interpolation attack described in this paper.

RDES cryptosystem is an n-round DES in which an probabilistic swapping is added onto the right half of the input in each round. It is more effective than a simple increase of DES rounds for a countermeasure against differential attack. In this paper, we show that the RDES is also effective against linear cryptanalysis. We applied Matsui's search algorithm to find the best expression for RDES-1 and RDES-2. The results are as follows: (a) The 16-round RDES-1 is approximately as strong as a 22-round DES, and the 16-round RDES-2 is approximately as strong as a 29-round DES. (b) Linear cryptanalysis for a 16-round RDES-1 and a 16-round RDES-2 requires more than 264 known-plaintexts.

Multiple-Input Multiple-Output (MIMO) wireless systems offer both high data rates and high capacity. Since different signals are transmitted by different antennas simultaneously, interference occurs between the transmitted signals. Each receive antenna receives all the signals transmitted by each transmit antenna simultaneously. The receiver has to detect each signal from the multiplexed signal. A Minimum Mean Square Error (MMSE) algorithm is used for spatial filtering. MMSE filtering can realize low complexity signal detection, but the signal output by MMSE filtering suffers from interference by the other signals. MMSE-SIC combines MMSE filtering and Soft Interference Cancellation (SIC) with soft replicas and can achieve good Bit Error Rate (BER) performance. If an irregular LDPC code or a turbo code is used, the reliability and BER of the information bits output by the decoder are likely to be higher and better than the parity bits. In MMSE-SIC, bits with poor reliability lower the accuracy of soft replica estimation. When the soft replica is inaccurate, the gain obtained by SIC is small. M-ary Phase Shift Keying (PSK) and M-ary Quadrature Amplitude Modulation (QAM) also achieve high data rates. Larger constellations such as 8 PSK and 16 QAM transfer more bits per symbol, and the number of bits per symbol impacts the accuracy of SIC. Unfortunately, increasing the number of bits per symbol is likely to lower the accuracy of soft replica estimation. In this paper, we evaluate three mapping schemes for MMSE-SIC with an LDPC code and a turbo code with the goal of effectively increasing the SIC gain. The first scheme is information reliable mapping. In this scheme, information bits are assigned to strongly protected bits. In the second scheme, parity reliable mapping, parity bits are assigned to strongly protected bits. The last one is random mapping. Computer simulations show that in MMSE-SIC with an irregular LDPC code and a turbo code, information reliable mapping offers the highest SIC gain. We also show that in MMSE-SIC with the regular LDPC code, the gains offered by the mapping schemes are very small.

The block cipher CAST-256 based on CAST-128 was a candidate algorithm for the AES round 1. In this paper we present a first result of a differential attack on CAST-256 reduced to 9 quad-rounds. One of the three round functions of CAST-256 has differential characteristics, for which a non-zero inputxor results in a zero outputxor, with high probability. This type of characteristic is the most useful for differential attack. We also show that CAST-256 has weak keys with respect to differential attack. Thus CAST-256 reduced to 9 quad-rounds can be attacked using 2123 chosen plaintexts in the case of differentially weak keys. The time complexity is about 2100 encryptions. Immunity to differential cryptanalysis of CAST-256 is not necessarily improved compared with CAST-128. Only 5 rounds of CAST-128 can be attacked using a similar differential characteristic.

In this paper, we describe a technique for optimizing the algebraic method that is applied to higher order differential attack. The higher order differential attack is a well-known attack on block ciphers, in which we derive an attack equation to determine a round key from a property of a higher order differential of a target block cipher. The algebraic method is a linearization of the attack equation and determines the true key by a method such as Gaussian elimination. Our technique is based on linear dependency and can reduce the complexity of that method. We also describe a technique that allows the algebraic method to be used as an attack equation that holds probabilistically. We demonstrate this method by attacking a five-round MISTY1 and show that it needs 221.6 chosen plaintexts and 228.0 encryption times. The computer simulation took about two minutes to complete.

Accurate values for occurrence probabilities of the template used in the overlapping template matching test included in NIST randomness test suite (NIST SP800-22) have been analyzed. The inaccurate values used in the NIST randomness test suite cause significant difference of pass rate. When the inaccurate values are used and significance level is set to 1%, the experimental mean value of pass rate, which is calculated by use of random number sequences taken from DES (Data Encryption Standard), is about 98.8%. In contrast, our new values derived from a set of recurrence formulas for the NIST randomness test suite give an empirical distribution of pass rate that meets the theoretical binomial distribution. Here, the experimental mean value of pass rate is about 99%, which corresponds to the significance level 1%.

Irregular LDPC codes can achieve better error rate performance than regular LDPC codes. However, irregular LDPC codes have higher error floors than regular LDPC codes. The Ordered Statistic Decoding (OSD) algorithm achieves approximate Maximum Likelihood (ML) decoding. ML decoding is effective to lower error floors. However, the OSD estimates satisfy the parity check equation of the LDPC code even the estimates are wrong. Hybrid decoder combining LLR-BP decoding algorithm and the OSD algorithm cannot also lower error floors, because wrong estimates also satisfy the LDPC parity check equation. We proposed the concatenated code constructed with an inner irregular LDPC code and an outer Cyclic Redundancy Check (CRC). Owing to CRC, we can detect wrong codewords from OSD estimates. Our CRC-LDPC code with hybrid decoder can lower error floors in an AWGN channel. In wireless communications, we cannot neglect the effects of the channel. The OSD algorithm needs the ordering of each bit based on the reliability. The Channel State Information (CSI) is used for deciding reliability of each bit. In this paper, we evaluate the Block Error Rate (BLER) of the CRC-LDPC code with hybrid decoder in a fast fading channel with perfect and imperfect CSIs where 'imperfect CSI' means that the distribution of channel and those statistical average of the fading amplitudes are known at the receiver. By computer simulation, we show that the CRC-LDPC code with hybrid decoder can lower error floors than the conventional LDPC code with hybrid decoder in the fast fading channel with perfect and imperfect CSIs. We also show that combining error detection with the OSD algorithm is effective not only for lowering the error floor but also for reducing computational complexity of the OSD algorithm.

SOBER-128 is a stream cipher designed by Rose and Hawkes in 2003. It can be also used for generating Message Authentication Codes (MACs) and an authenticated encryption. The developers claimed that it is difficult to forge MACs generated by both functions of SOBER-128, though, the security assumption in the proposal paper is not realistic in some instances. In this paper, we examine the security of these message authentication mechanisms of SOBER-128 under security channel model. As a result, we show that both a MAC generation and an authenticated encryption are vulnerable against differential cryptanalysis. The success probabilities of the MAC forgery attack are estimated at 2-6 and 2-27 respectively. In addition, we show that some secret bits are revealed if a key is used many times.

Multiple-Input Multiple-Output (MIMO) systems can achieve high data-rate and high capacity transmission. In MIMO systems, eigen-beam space division multiplexing (E-SDM) that achieves much higher capacity by weighting at the transmitter based on feedback channel state information (CSI) has been studied. Early studies for E-SDM have assumed perfect CSI at the transmitter. However, in practice, the CSI fed back to the transmitter from the receiver becomes outdated due to the time-varying nature of the channels and feedback delay. Therefore, an outdated E-SDM cannot achieve the full performance possible. In this paper, we evaluate the performance of E-SDM with methods for reducing performance degradation due to feedback delay. We use three methods: 1) method that predicts CSI at future times when it will be used and feeds the predicted CSI back to the transmitter (denoted hereafter as channel prediction); 2), 3) method that uses the receive weight based on zero-forcing (ZF) or minimum mean square error (MMSE) criterion instead of those based on singular value decomposition (SVD) criterion (denoted hereafter as ZF or MMSE-based receive weight). We also propose methods that combine channel prediction with ZF or MMSE-based receive weight. Simulation results show that bit error rate (BER) degradation of E-SDM in the presence of feedback delay is reduced by using methods for reducing performance degradation due to feedback delay. We also show that methods that combine channel prediction with ZF or MMSE-based receive weight can achieve good BER even when the large feedback delay exists.

In the linear cryptanalysis (LC), to decrease the number of plain/cipher text pairs required for successful attack against DES, it is necessary to improve the effectiveness of the linear approximate expression and to decrease the number of key bits in the expression to be exhaustively searched for. In the previous work, we proposed a linear sieve method to improve the effectiveness of the linear approximate expression. On the other hand, the number of key bits increased. To suppress the number of key bits, we propose Fixed Sieve Linear Cryptanalysis (FS-LC) with fixed sieve key of the linear sieve method. With FS-LC against 8-round DES, we showed the number of plain/cipher text pairs required for sucessful attack is less than that of LC. Furthmore, we extended FS-LC with Kaliski's techniques using the multiple linear approximate expressions to intoroduce Fixed Sieve multiple Linear Cryptanalysis (FS-mLC). With FS-mLC against 8-round DES, computer simulation revealed that it is possible to solve its encryption-key with 220 plain/cipher text pairs. The number of pairs is about a half of the Matsui's 1-round linear cryptanalysis cases.

This paper reports the strength of a pseudorandom number generator MUGI, which was published as a stream cipher by Hitachi, Ltd. in 2001, against linear cryptanalysis. MUGI is one of the recommended ciphers of CRYPTREC, which is a project for the e-Government in Japan. It has two internal states called state and buffer, which are updated by a linear function λ and a non-linear function ρ. The non-linear function ρ and the linear function λ have already been analyzed, independently. In this paper, whole MUGI is analyzed by truncated linear cryptanalysis. The analysis of λ function is based on the state variables method. The result is combined to the result of the analysis of ρ function to make a trellis diagram. Viterbi search is conducted on the diagram to find the best possible linear path under 64-bit truncated linear cryptanalysis. As the result, the upper bound of the maximum linear characteristic probability is estimated as less than 2-138. Therefore, MUGI is secure against linear cryptanalysis.

The encryption algorithm Camellia is a 128 bit block cipher proposed by NTT and Mitsubishi, Japan. Since the algebraic degree of the outputs after 3 rounds is greater than 128, designers estimate that it is impossible to attack Camellia by higher order differential. In this paper, we show a new higher order differential attack which controls the value of differential using proper fixed value of plaintext. As the result, we found that 6-round F-function can be attacked using 8th order differentials. The attack requires 217 chosen plaintexts and 222 F-function operations. Our computer simulation took about 2 seconds for the attack. If we take 2-R elimination algorithm, 7-round F-function will be attacked using 8th order differentials. This attack requires 219 chosen plaintexts and 264 F-function operations, which is less than exhaustive search for 128 bit key.

Following the last proposal of the nonlinear Piece in Hand method, which has 3-layer structure, 2-layer nonlinear Piece in Hand method is proposed. Both of them aim at enhancing the security of existing and future multivariate public key cryptosystems. The new nonlinear Piece in Hand is compared with the 3-layer method and PMI+, which was proposed by Ding, et al.

This paper proposes novel calculuses of linearizing attack that can be applied to higher order differential attack. Higher order differential attack is a powerful and versatile attack on block ciphers. It can be roughly summarized as follows: (1) Derive an attack equation to estimate the key by using the higher order differential properties of the target cipher, (2) Determine the key by solving an attack equation. Linearizing attack is an effective method of solving attack equations. It linearizes an attack equation and determines the key by solving a system of linearized equations using approaches such as the Gauss-Jordan method. We enhance the derivation algorithm of the coefficient matrix for linearizing attack to reduce computational cost (fast calculus 1). Furthermore, we eliminate most of the unknown variables in the linearized equations by making the coefficient column vectors 0 (fast calculus 2). We apply these algorithms to an attack of the five-round variant of KASUMI and show that the attack complexity is equivalent to 228.9 chosen plaintexts and 231.2 KASUMI encryptions.

CLEFIA is a 128-bit block cipher proposed by Shirai et al. at FSE2007. It has been reported that CLEFIA has a 9-round saturation characteristic, in which 32bits of the output of 9-th round 112-th order differential equals to zero. By using this characteristic, a 14-round CLEFIA with 256-bit secret key is attacked with 2113 blocks of chosen plaintext and 2244.5 times of data encryption. In this paper, we focused on a higher order differential of CLEFIA. This paper introduces two new concepts for higher order differential which are control transform for the input and observation transform for the output. With these concepts, we found a new 6-round saturation characteristic, in which 24bits of the output of 6-th round 9-th order differential equals to zero. We also show a new 9-round saturation characteristic using 105-th order differential which is a 3-round extension of the 6-round one. If we use it, instead of 112-th order differential, using the meet-in-the-middle attack technique for higher order differential table, the data and computational complexity for the attack to 14-round CLEFIA can be reduced to around 2-5, 2-34 of the conventional attack, respectively.

Since the proposal of differential cryptanalysis and linear cryptanalysis in 1991 and 1993, respectively, the resistance to these cryptanalysis has been studied. In FSE2, Knudsen proposed a method of attacking block ciphers that used the higher order differential, and in FSE4, Jakobsen and Knudsen applied it to a cipher proposed by Nyberg and Knudsen. Their approach, however, requires large complexity of running time. In this paper, we improve this attack and show that our improved algorithm requires much fewer chosen texts and much less complexity than those of previous works.

This paper proposes a dynamically randomized version of DES (called RDES) in which a input-dependent swapping Sk(X) is added onto the right half of the input in each round of DES. This new scheme decreases the probability of success in differential cryptanalysis because it decreases the characteristic probability. Each "best" two-round characteristic probability is analyzed for typical schemes of the RDES: (i) RDES-1 with a simple one-level swapping, (ii) RDES-1' with an optimal one-level swapping, (iii) RDES-2 with a simple two-level swapping, and (iv) RDES-2' with an optimal two-level swapping. The main results are as follows. (a) The differential attacks on the 16-round RDES-1' and the 16-round RDES-2 require more computational time than the exhaustive search. (b) A differential attack is substantially inapplicable to the 16-round RDES-2' because more than 263 chosen plaintext pairs are required. (c) The encryption/decryption speed of the n-round RDES is almost the same as that of the n-round DES.