More Web Proxy on the site http://driver.im/

article

Accurate estimates of the data complexity and success probability for various cryptanalyses

Authors:

Céline Blondeau,

Benoît Gérard,

Jean-Pierre TillichAuthors Info & Claims

Designs, Codes and Cryptography, Volume 59, Issue 1-3

Pages 3 - 34

https://doi.org/10.1007/s10623-010-9452-2

Published: 01 April 2011 Publication History

Abstract

Many attacks on encryption schemes rely on statistical considerations using plaintext/ciphertext pairs to find some information on the key. We provide here simple formulae for estimating the data complexity and the success probability which can be applied to a lot of different scenarios (differential cryptanalysis, linear cryptanalysis, truncated differential cryptanalysis, etc.). Our work does not rely here on Gaussian approximation which is not valid in every setting but use instead a simple and general approximation of the binomial distribution and asymptotic expansions of the beta distribution.

References

[1]

Vaudenay S.: Decorrelation: a theory for block cipher security. J. Cryptol. 16, 249-286 (2003).

Digital Library

[2]

Tardy-Corfdir A., Gilbert H.: A known plaintext attack of FEAL-4 and FEAL-6. In: CRYPTO '91. LNCS, vol. 576, pp. 172-181. Springer-Verlag, Heidleberg (1992).

[3]

Matsui M.: Linear cryptanalysis method for DES cipher. In: EUROCRYPT '93. LNCS, vol. 765, pp. 386-397. Springer-Verlag, Heidlberg (1993).

[4]

Matsui M.: The first experimental cryptanalysis of the data encryption standard. In: CRYPTO '94. LNCS, vol. 839, pp. 1-11. Springer-Verlag, Heidleberg (1994).

[5]

Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4, 3-72 (1991).

Digital Library

[6]

Selçuk A.A.: On probability of success in linear and differential cryptanalysis. J. Cryptol. 21, 131-147 (2008).

Digital Library

[7]

Lai X., Massey J.L., Murphy S.: Markov Ciphers and differential cryptanalysis. In: LNCS, vol. 547, pp. 17-38. Springer, Heidleberg (1991).

[8]

Knudsen L.R.: Truncated and higher order differentials. In: FSE '94. LNCS, vol. 1008, pp. 196-211. Springer-Verlag, Heidleberg (1994).

[9]

Junod P.: On the optimality of linear, differential, and sequential distinguishers. In: EUROCRYPT '03. LNCS, vol. 2656, pp. 17-32. Springer-Verlag, Heidleberg (2003).

[10]

Baignères T., Junod P., Vaudenay S.: How far can we go beyond linear cryptanalysis? In: ASIACRYPT '04. LNCS, vol. 3329, pp. 432-450. Springer-Verlag, Heidleberg (2004).

[11]

Baignères T., Vaudenay S.: The complexity of distinguishing distributions. In: ICITS '08. LNCS, vol. 5155, pp. 210-222. Springer-Verlag, Heidleberg (2008).

[12]

Junod P.: On the complexity of Matsui's attack. In: SAC '01. LNCS, vol. 2259, pp. 199-211. Springer-Verlag, Heidleberg (2001).

[13]

Junod P., Vaudenay S.: Optimal key ranking procedures in a statistical cryptanalysis. In: FSE '03. LNCS, vol. 2887, pp. 235-246. Springer-Verlag, Heidleberg (2003).

[14]

Nyberg K.: Generalized Feistel networks. In: ASIACRYPT '96. LNCS, vol. 1163, pp. 91-104. Springer-Verlag, Heidleberg (1996).

[15]

Harpes C., Kramer G., Massey J.: A generalization of linear cryptanalysis and the applicability of Matsui's piling-up lemma. In: EUROCRYPT '95. LNCS, vol. 921, pp. 24-38. Springer-Verlag, Heidleberg (1995).

[16]

Cover T., Thomas J.: Information theory. Wiley series in communications. Wiley, New York (1991).

[17]

Arriata R., Gordon L.: Tutorial on large deviations for the binomial distribution. Bull. Math. Biol. 51, 125-131 (1989).

[18]

Langford S.K., Hellman M.E.: Differential-linear cryptanalysis. In: CRYPTO '94. LNCS, vol. 839, pp. 17-25. Springer-Verlag, Heidleberg (1994).

[19]

Biham E., Shamir A.: Differential cryptanalysis of the full 16-round DES. In: CRYPTO'92. LNCS, vol. 740, pp. 487-496. Springer-Verlag, Heidleberg (1993).

[20]

Biham E., Biryukov A., Shamir A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: EUROCRYPT '99. LNCS, vol. 1592, pp. 12-23. Springer-Verlag, Heidleberg (1999).

[21]

David H., Nagaraja H.: Order Statistics, third edn. Wiley series in Probability Theory. Wiley, New York (2003).

Cited By

Lin YSun L(2024)Related-Tweak and Related-Key Differential Attacks on HALFLOOP-48Applied Cryptography and Network Security10.1007/978-3-031-54776-8_14(355-377)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54776-8_14
Ma SJin CShi ZCui TGuan J(2023)Correlation Attacks on SNOW-V-Like Stream Ciphers Based on a Heuristic MILP ModelIEEE Transactions on Information Theory10.1109/TIT.2023.332634870:6(4478-4491)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3326348
Ma SJin CGuan J(2023)Fast Correlation Attacks on K2 Stream CipherIEEE Transactions on Information Theory10.1109/TIT.2023.327121769:8(5426-5439)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3271217
Show More Cited By

Accurate estimates of the data complexity and success probability for various cryptanalyses
1. Theory of computation

Recommendations

Success probability of multiple/multidimensional linear cryptanalysis under general key randomisation hypotheses

This work considers statistical analysis of attacks on block cyphers using several linear approximations. A general and unified approach is adopted. To this end, the general key randomisation hypotheses for multidimensional and multiple linear ...
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 ...
Multiple differential cryptanalysis: theory and practice
FSE'11: Proceedings of the 18th international conference on Fast software encryption

Differential cryptanalysis is a well-known statistical attack on block ciphers. We present here a generalisation of this attack called multiple differential cryptanalysis. We study the data complexity, the time complexity and the success probability of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Designs, Codes and Cryptography

Designs, Codes and Cryptography Volume 59, Issue 1-3

April 2011

352 pages

ISSN:0925-1022

Issue’s Table of Contents

Copyright © Copyright © 2011 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 24 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lin YSun L(2024)Related-Tweak and Related-Key Differential Attacks on HALFLOOP-48Applied Cryptography and Network Security10.1007/978-3-031-54776-8_14(355-377)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54776-8_14
Ma SJin CShi ZCui TGuan J(2023)Correlation Attacks on SNOW-V-Like Stream Ciphers Based on a Heuristic MILP ModelIEEE Transactions on Information Theory10.1109/TIT.2023.332634870:6(4478-4491)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3326348
Ma SJin CGuan J(2023)Fast Correlation Attacks on K2 Stream CipherIEEE Transactions on Information Theory10.1109/TIT.2023.327121769:8(5426-5439)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3271217
Liu JSun L(2023)Distinguisher and Related-Key Attack on HALFLOOP-96Information Security and Cryptology – ICISC 202310.1007/978-981-97-1235-9_2(19-40)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-97-1235-9_2
Yu QJia KZou GZhang G(2022)Differential Cryptanalysis of Round-Reduced SPEEDY FamilyInformation Security and Cryptology10.1007/978-3-031-26553-2_14(272-291)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-26553-2_14
Shi ZJin CZhang JCui TDing LJin Y(2022)A Correlation Attack on Full SNOW-V and SNOW-ViAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-07082-2_2(34-56)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-07082-2_2
Sun LWang WWang M(2021)Improved Attacks on GIFT-64Selected Areas in Cryptography10.1007/978-3-030-99277-4_12(246-265)Online publication date: 29-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-99277-4_12
Harmouch YEl Kouch R(2018)Brownian Techniques for Constructing High-Strong Cryptographic S-boxesProceedings of the 2nd International Conference on Smart Digital Environment10.1145/3289100.3289104(19-26)Online publication date: 18-Oct-2018
https://dl.acm.org/doi/10.1145/3289100.3289104
Samajder SSarkar P(2018)Multiple (Truncated) Differential CryptanalysisCryptography and Communications10.1007/s12095-017-0268-z10:6(1137-1163)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s12095-017-0268-z
Paul GRay S(2018)On data complexity of distinguishing attacks versus message recovery attacks on stream ciphersDesigns, Codes and Cryptography10.1007/s10623-017-0391-z86:6(1211-1247)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10623-017-0391-z
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents