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

Research output: Contribution to journal › Article › peer-review

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%.

Original language	English
Pages (from-to)	2-8
Number of pages	7
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E88-A
Issue number	1
DOIs	https://doi.org/10.1093/ietfec/E88-A.1.2
Publication status	Published - 2005 Jan

Keywords

Block cipher
Linear cryptanalysis
Multiple linear cryptanalsis

ASJC Scopus subject areas

Signal Processing
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering
Applied Mathematics

Access to Document

10.1093/ietfec/E88-A.1.2

Cite this

@article{5e4f38a9256d40e8a714983addfdc203,

title = "Linear attack using multiple linear approximations",

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 240.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.",

keywords = "Block cipher, Linear cryptanalysis, Multiple linear cryptanalsis",

author = "Jun Choi and Deukjo Hong and Seokhie Hong and Sangjin Lee",

year = "2005",

month = jan,

doi = "10.1093/ietfec/E88-A.1.2",

language = "English",

volume = "E88-A",

pages = "2--8",

journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",

issn = "0916-8508",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "1",

}

TY - JOUR

T1 - Linear attack using multiple linear approximations

AU - Choi, Jun

AU - Hong, Deukjo

AU - Hong, Seokhie

AU - Lee, Sangjin

PY - 2005/1

Y1 - 2005/1

N2 - 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 240.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.

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 240.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.

KW - Block cipher

KW - Linear cryptanalysis

KW - Multiple linear cryptanalsis

UR - http://www.scopus.com/inward/record.url?scp=27544479542&partnerID=8YFLogxK

U2 - 10.1093/ietfec/E88-A.1.2

DO - 10.1093/ietfec/E88-A.1.2

M3 - Article

AN - SCOPUS:27544479542

SN - 0916-8508

VL - E88-A

SP - 2

EP - 8

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 1

ER -

Linear attack using multiple linear approximations

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this