부메랑 분석과 차분-선형 분석의 연결표에 관한 연구

Abstract

블록암호의 대표적인 분석 기법은 차분 분석과 선형근사 분석이다. 대부분의

블록암호 분석 기법은 이 둘로부터 파생되었다. 그리고 차분 분석과 선형근사

분석으로부터 파생된 분석 기법 중에 부메랑 분석과 차분-선형 분석이 존재한

다. 이 둘은 긴 라운드의 차분 경로 또는 선형 경로를 현실적으로 찾기 어려

운 문제를 해결하기 위하여, 비교적 찾기 쉬운 짧은 차분 경로 또는 선형 경

로를 연결함으로써 긴 부메랑 경로 또는 차분-선형 경로를 구성하여 암호 알

고리즘을 분석하는 기법이다. 부메랑 분석과 차분-선형 분석은 대부분의 암호

알고리즘에 대하여 좋은 결과를 보여주어 일반적인 분석 기법으로 자리매김하

였다. 두 경로를 연결하기 위해서는 경로 간에 독립성을 가정하거나 종속성을

계산해야만 한다. 이로부터 처음부터 독립성을 가정하고 분석하거나, 주어진

경로들에 대하여 종속성을 계산하는 방법들이 제시되었다. SPN 구조 블록암

호의 종속성을 찾는 일반화된 기법으로 2018년, 부메랑 연결표(BCT,

Boomerang Connectivity Table)가 C. Cid 등에 의해, 그리고 2019년 차분-선

형 연결표(DLCT, Differential-linear Connectivity Table)가 Achiya Bar-On 등에

의해 소개되었다. 그러나 이 연결표들을 생성하는 것은 s-box에 대해서만 정

의되었고, ARX 기반 블록암호의 법 연산에는 적용이 불가하였다. 본 논문에서

는 법 연산에 대하여 부메랑 연결표와 차분-선형 연결표의 원소를 계산하는

기법을 보이고, 이를 ARX 기반 블록암호 LEA와 SPECK에 적용하여 기존 분석

기법들 보다 더 긴 부메랑 경로와 차분-선형 경로를 찾는다.