TY - GEN

T1 - Improving linear cryptanalysis of LOKI91 by probabilistic counting method

AU - Sakurai, Kouichi

AU - Furuya, Souichi

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - We improve linear cryptanalysis by introducing a technique of probabilistic counting into the maximum likelihood stage. In the original linear cryptanalysis based on maximum likelihood method with deterministic counting, the number of effective key and text bits is a multiple of the number of bit involved in the input to some S-box. Then, when larger S-boxes are used, 2R-method and even the 1R-methods can become impractical just because the number of effective text and key bits become excessive. Though 2R-method is practical for attacking DES, existing examples of ciphers where 2R-method is impractical include LOKI91. We overcome this problem by selecting a part of the effective key bits and investigating the probabilistic behavior of the remained effective key bits. The previous attacks discusses deterministic evaluation of the given approximated formula only when all values of the effective text/key bits are known, while we compute the probability that the approximated formula with unknown inputs equals to zero. This extension of linear cryptanalysis make useful for 2R-attack on LOKI91, then improves the performance of previous attacks. Furthermore, we implemented some experiments of attacks on 4-round LOKI91, and confirmed the effectiveness of our method.

AB - We improve linear cryptanalysis by introducing a technique of probabilistic counting into the maximum likelihood stage. In the original linear cryptanalysis based on maximum likelihood method with deterministic counting, the number of effective key and text bits is a multiple of the number of bit involved in the input to some S-box. Then, when larger S-boxes are used, 2R-method and even the 1R-methods can become impractical just because the number of effective text and key bits become excessive. Though 2R-method is practical for attacking DES, existing examples of ciphers where 2R-method is impractical include LOKI91. We overcome this problem by selecting a part of the effective key bits and investigating the probabilistic behavior of the remained effective key bits. The previous attacks discusses deterministic evaluation of the given approximated formula only when all values of the effective text/key bits are known, while we compute the probability that the approximated formula with unknown inputs equals to zero. This extension of linear cryptanalysis make useful for 2R-attack on LOKI91, then improves the performance of previous attacks. Furthermore, we implemented some experiments of attacks on 4-round LOKI91, and confirmed the effectiveness of our method.

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

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

U2 - 10.1007/bfb0052340

DO - 10.1007/bfb0052340

M3 - Conference contribution

AN - SCOPUS:84943147885

SN - 3540632476

SN - 9783540632474

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 114

EP - 133

BT - Fast Software Encryption - 4th International Workshop, FSE 1997, Proceedings

A2 - Biham, Eli

PB - Springer Verlag

T2 - 4th International Workshop on Fast Software Encryption, FSE 1997

Y2 - 20 January 1997 through 22 January 1997

ER -