Linear Attack Using Multiple Linear Approximations

Jun CHOI; Deukjo HONG; Seokhie HONG; Sangjin LEE

doi:10.1093/ietfec/e88-a.1.2

Linear Attack Using Multiple Linear Approximations

Jun CHOI, Deukjo HONG, Seokhie HONG, Sangjin LEE

Full Text Views

0

Cite this

Summary :

One of Kaliski and Robshaw's algorithms, which is used for the linear attack on block ciphers with multiple linear approximations and introduced as Algorithm 2M in this paper, looks efficient but lacks any theoretical and mathematical description. It means there exists no way to estimate the data complexity required for the attack by the algorithm except experiments of the reduced variants. In this paper we propose a new algorithm using multiple linear approximation. We achieve the theoretical and mathematical analysis of its success probability. The new algorithm needs about 2^40.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.1 pp.2-8

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietfec/e88-a.1.2

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Symmetric Key Cryptography

Cite this

Copy

Jun CHOI, Deukjo HONG, Seokhie HONG, Sangjin LEE, "Linear Attack Using Multiple Linear Approximations" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 1, pp. 2-8, January 2005, doi: 10.1093/ietfec/e88-a.1.2.
Abstract: One of Kaliski and Robshaw's algorithms, which is used for the linear attack on block ciphers with multiple linear approximations and introduced as Algorithm 2M in this paper, looks efficient but lacks any theoretical and mathematical description. It means there exists no way to estimate the data complexity required for the attack by the algorithm except experiments of the reduced variants. In this paper we propose a new algorithm using multiple linear approximation. We achieve the theoretical and mathematical analysis of its success probability. The new algorithm needs about 2^40.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.1.2/_p

Copy

@ARTICLE{e88-a_1_2,
author={Jun CHOI, Deukjo HONG, Seokhie HONG, Sangjin LEE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Linear Attack Using Multiple Linear Approximations},
year={2005},
volume={E88-A},
number={1},
pages={2-8},
abstract={One of Kaliski and Robshaw's algorithms, which is used for the linear attack on block ciphers with multiple linear approximations and introduced as Algorithm 2M in this paper, looks efficient but lacks any theoretical and mathematical description. It means there exists no way to estimate the data complexity required for the attack by the algorithm except experiments of the reduced variants. In this paper we propose a new algorithm using multiple linear approximation. We achieve the theoretical and mathematical analysis of its success probability. The new algorithm needs about 2^40.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.},
keywords={},
doi={10.1093/ietfec/e88-a.1.2},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Linear Attack Using Multiple Linear Approximations
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2
EP - 8
AU - Jun CHOI
AU - Deukjo HONG
AU - Seokhie HONG
AU - Sangjin LEE
PY - 2005
DO - 10.1093/ietfec/e88-a.1.2
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2005
AB - One of Kaliski and Robshaw's algorithms, which is used for the linear attack on block ciphers with multiple linear approximations and introduced as Algorithm 2M in this paper, looks efficient but lacks any theoretical and mathematical description. It means there exists no way to estimate the data complexity required for the attack by the algorithm except experiments of the reduced variants. In this paper we propose a new algorithm using multiple linear approximation. We achieve the theoretical and mathematical analysis of its success probability. The new algorithm needs about 2^40.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.
ER -