Improved Differential and Linear Active S-Boxes Search Techniques for Feistel Type Ciphers

ZHANG Lei; WU Wenling

doi:10.1049/cje.2015.04.020

Volume 24 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2015 > 24(2): 343-348

ZHANG Lei and WU Wenling, “Improved Differential and Linear Active S-Boxes Search Techniques for Feistel Type Ciphers,” Chinese Journal of Electronics, vol. 24, no. 2, pp. 343-348, 2015, doi: 10.1049/cje.2015.04.020

Citation:

ZHANG Lei and WU Wenling, “Improved Differential and Linear Active S-Boxes Search Techniques for Feistel Type Ciphers,” Chinese Journal of Electronics, vol. 24, no. 2, pp. 343-348, 2015, doi: 10.1049/cje.2015.04.020

Citation:

PDF( 315 KB)

Improved Differential and Linear Active S-Boxes Search Techniques for Feistel Type Ciphers

doi: 10.1049/cje.2015.04.020

ZHANG Lei¹,
WU Wenling^1,2

1.
Trusted Computing and Information Assurance Laboratory, Institute of Software, Beijing 100190, China;
2.
State Key Laboratory of Computer Science, Institute of Software, Beijing 100190, China

Funds: This work is supported by the National Natural Science Foundation of China (No. 61202420, No. 61272476, No. 61232009) and the National Basic Research Program of China (973 Program) (No. 2013CB338002).

Publish Date: 2015-04-10

Abstract

Abstract

We propose improved differential and linear active S-boxes search techniques for Feistel type ciphers. We give a uniform representation of Feistel type structures which can benefit the analysis of differential propagation. By analyzing the properties of Feistel type environment, we present some important observations of differential propagation and propose a notion of equivalent state set which can narrow down the search space noticeably. We present a practical algorithm to improve the search of active S-boxes for Feistel type ciphers. It is basically a Viterbi search operating on equivalent state set and also adopts the pruning mechanism. Our experimental results show that the improved algorithm have advantages in respect to memory and time complexities, and it can be applied efficiently to Feistel cipher with large blocks. The search program can be implemented in normal PC, which will be more practical and useful for the designers and cryptanalysts.
- Block cipher,
- Feistel type ciphers,
- Differential and linear active S-boxes,
- Automatic search technique

FullText(HTML)

References(13)

References

A. Biryukov and D. Khovratovich, “Related-key cryptanalysis of the full AES-192 and AES-256”, Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, pp.1-18, 2009.

A. Biryukov and I. Nikolic, “Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to AES, Camellia, Khazad and others”, Proceedings of the 29th International Conference on the Theory and Application of Cryptographic Techniques, French Riviera, pp.322-344, 2010.

C. Bouillaguet, P. Derbez and P.A. Fouque, “Automatic search of attacks on round-reduced AES and applications”, Proceedings of the 31th International Cryptology Conference, Santa Barbara, CA, USA, pp.169-187, 2011.

W.L. Wu and L. Zhang, “LBlock: A lightweight block cipher”, Proceedings of the 9th International Conference on Applied Cryptography and Network Security, Nerja, Spain, pp.327-344, 2011.

K. Nyberg, “Generalized Feistel networks”, Proceedings of the 2nd International Conference on the Theory and Applications of Cryptology and Information Security, Kyongju, Korea, pp.90-104, 1996.

B. Schneier and J. Kelsey, “Unbalanced Feistel networks and block cipher design”, Proceedings of the 3rd International Workshop on Fast Software Encryption, Cambridge, UK, pp.121-144, 1996.

T. Suzaki and K. Minematsu, “Improving the generalized Feistel”, Proceedings of the 17th International Workshop on Fast Software Encryption, Seoul, Korea, pp.19-39, 2010.

M. Matsui, “On correlation between the order of S-boxes and the strength of DES”, Proceedings of the 13th Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, pp.366-375, 1994.

A. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm”, IEEE Transactions on Information Theory, Vol.13, No.2, pp.260-269, 1967.

T. Shirai and B. Preneel, “On Feistel ciphers using optimal diffusion mappings across multiple rounds”, Proceedings of the 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, pp.1-15, 2004.

Y. Igarashi and T. Kaneko, “On the truncated path search for the maximum differential characteristic probability on a generalized Feistel-type block cipher”, Proceedings of the IEEE 2010 International Symposium on Information Theory and its Applications, Taichung, Taiwan, pp.784-788, 2010.

Z. Gong, Y.Y. Luo, X.J. Lai, et al., “On the security of doubleblock-length hash functions with rate 1”, Chinese Journal of Electronics, Vol.21, No.3, pp.566-570, 2012.

Y.B. Zhou, W.L. Wu, N.N. Xu, et al., “Differential fault attack on Camellia”, Chinese Journal of Electronics, Vol.18, No.1, pp.13-19, 2009.

Relative Articles

Supplements(0)

Cited By

Proportional views