tutorial

Improbable differential cryptanalysis

Author:

Cihangir TezcanAuthors Info & Claims

SIN '13: Proceedings of the 6th International Conference on Security of Information and Networks

Page 457

https://doi.org/10.1145/2523514.2523587

Published: 26 November 2013 Publication History

Get Access

Abstract

Statistical attacks on block ciphers make use of a property of the cipher so that an event occurs with different probabilities depending on whether or not the correct key is used. For instance, differential cryptanalysis [3] and truncated differential cryptanalysis [5] consider characteristics or differentials which show that a particular output difference should be obtained with a relatively high probability when a particular input difference is used. Hence, when the correct key is used, the predicted differences occur more frequently.

On the other hand, impossible differential cryptanalysis [2] uses an impossible differential which shows that a particular difference cannot occur for the correct key (i.e. the probability of this event is exactly zero). Therefore, if these differences are satisfied under a trial key, then it cannot be the correct one. Thus, the correct key can be obtained by eliminating all or most of the wrong keys.

However, in a recent study [7] we showed that it is also possible to obtain differentials so that the predicted differences occur less frequently for the correct key. This new cryptanalytic technique is called the improbable differential cryptanalysis and the impossible differential cryptanalysis is just a special case of it. Thus, improbable differential cryptanalysis bridges the gap between differential and impossible differential cryptanalysis.

Substitution layer of cryptographic algorithms mostly consists of substitution boxes (S-boxes) and in order to provide better security against known attacks, S-boxes are selected depending on their cryptographic properties like differential probability, linear bias, algebraic degree, and branch number. For instance, differential attacks highly use the differential probabilities of the S-boxes. Recently we proposed a new property of S-boxes that we call undisturbed bits [8] which can be used to obtain better truncated, impossible or improbable differentials.

In this tutorial, we will start by describing differential, truncated and impossible differential cryptanalysis. We will then describe the improbable differential cryptanalysis and the expansion technique that expands impossible differentials to improbable differentials. As an example for the expansion technique, we will discuss the improbable differential attacks on CLEFIA [6] in detail. Then we will describe the concept of undistubed bits and discuss their effects on the block ciphers PRESENT [4] and Serpent [1].

References

[1]

E. Biham, R. J. Anderson, and L. R. Knudsen. Serpent: A new block cipher proposal. In S. Vaudenay, editor, FSE, volume 1372 of Lecture Notes in Computer Science, pages 222--238. Springer, 1998.

Digital Library

Google Scholar

[2]

E. Biham, A. Biryukov, and A. Shamir. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. J. Cryptology, 18(4): 291--311, 2005.

Digital Library

Google Scholar

[3]

E. Biham and A. Shamir. Differential Cryptanalysis of DES-like Cryptosystems. J. Cryptology, 4(1): 3--72, 1991.

Digital Library

Google Scholar

[4]

A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin, and C. Vikkelsoe. PRESENT: An ultra-lightweight block cipher. In P. Paillier and I. Verbauwhede, editors, CHES, volume 4727 of Lecture Notes in Computer Science, pages 450--466. Springer, 2007.

Digital Library

Google Scholar

[5]

L. R. Knudsen. Truncated and higher order differentials. In B. Preneel, editor, FSE, volume 1008 of Lecture Notes in Computer Science, pages 196--211. Springer, 1994.

Google Scholar

[6]

T. Shirai, K. Shibutani, T. Akishita, S. Moriai, and T. Iwata. The 128-bit blockcipher CLEFIA (extended abstract). In A. Biryukov, editor, FSE, volume 4593 of Lecture Notes in Computer Science, pages 181--195. Springer, 2007.

Digital Library

Google Scholar

[7]

C. Tezcan. The improbable differential attack: Cryptanalysis of reduced round CLEFIA. In G. Gong and K. C. Gupta, editors, INDOCRYPT, volume 6498 of Lecture Notes in Computer Science, pages 197--209. Springer, 2010.

Google Scholar

[8]

C. Tezcan. Improbable differential attacks on PRESENT using undisturbed bits. Journal of Computational and Applied Mathematics, 2013, http://dx.doi.org/10.1016/j.cam.2013.06.023.

Digital Library

Google Scholar

Cited By

View all

Bhagat VKumar SGupta SChaube M(2022)Lightweight cryptographic algorithms based on different model architectures: A systematic review and futuristic applicationsConcurrency and Computation: Practice and Experience10.1002/cpe.742535:1Online publication date: 30-Oct-2022
https://doi.org/10.1002/cpe.7425

Index Terms

Improbable differential cryptanalysis

Recommendations

Improbable Differential Attacks on Serpent using Undisturbed Bits
SIN '14: Proceedings of the 7th International Conference on Security of Information and Networks

A recently introduced S-box evaluation criteria called undisturbed bits allow the attacker to construct longer truncated, impossible or improbable differentials. In this paper, we analyze the security of Serpent against impossible and improbable ...
Impossible differential cryptanalysis of reduced-round ARIA and Camellia

This paper studies the security of the block ciphers ARIA and Camellia against impossible differential cryptanalysis. Our work improves the best impossible differential cryptanalysis of ARIA and Camellia known so far. The designers of ARIA expected no ...
Improbable Differential from Impossible Differential: On the Validity of the Model
Proceedings of the 14th International Conference on Progress in Cryptology INDOCRYPT 2013 - Volume 8250

Differentials with low probability are used in improbable differential cryptanalysis to distinguish a cipher from a random permutation. Due to large diffusion, finding such differentials for actual ciphers remains a challenging task. At Indocrypt 2010, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIN '13: Proceedings of the 6th International Conference on Security of Information and Networks

November 2013

483 pages

ISBN:9781450324984

DOI:10.1145/2523514

General Chairs:
Atilla Elçi
Aksaray University, Turkey
,
Manoj Singh Gaur
Malaviya National Institute of Technology, India
,
Mehmet A. Orgun
Macquarie University, Australia
,
Oleg B. Makarevich
Southern Federal University, Russia

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

In-Cooperation

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 November 2013

Check for updates

Qualifiers

Tutorial

Conference

SIN '13

Sponsor:

MNIT
Aksaray Univ.
SFedU

SIN '13: The 6th International Conference on Security of Information and Networks

November 26 - 28, 2013

Aksaray, Turkey

Acceptance Rates

Overall Acceptance Rate 102 of 289 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
123
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bhagat VKumar SGupta SChaube M(2022)Lightweight cryptographic algorithms based on different model architectures: A systematic review and futuristic applicationsConcurrency and Computation: Practice and Experience10.1002/cpe.742535:1Online publication date: 30-Oct-2022
https://doi.org/10.1002/cpe.7425

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Improbable Differential Attacks on Serpent using Undisturbed Bits

Impossible differential cryptanalysis of reduced-round ARIA and Camellia

Improbable Differential from Impossible Differential: On the Validity of the Model