[논문]DLCT를 활용한 향상된 차분선형 분석

김현우; 김성겸; 홍득조; 성재철; 홍석희

doi:10.13089/jkiisc.2018.28.6.1379

DLCT를 활용한 향상된 차분선형 분석
Improved Differential-Linear Cryptanalysis Using DLCT 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.28 no.6, 2018년, pp.1379 - 1392

김현우 (고려대학교) , 김성겸 (고려대학교) , 홍득조 (전북대학교) , 성재철 (서울시립대학교) , 홍석희 (고려대학교)

초록
AI-Helper

차분선형 분석의 복잡도는 라운드 독립성, 선형 근사식 독립성, 차분 경로를 만족하지 못하는 경로에 대한 균일성 가정 아래 계산되는 차분선형 특성의 확률에 큰 영향을 받는다. 따라서 차분선형 특성의 정확한 확률을 계산하는 것은 공격의 유효성과 관련된 매우 중요한 문제이다. 본 논문은 차분선형 분석을 위한 새로운 개념 DLCT(Differential-Linear Connectivity Table)를 제안한다. 그리고 DLCT를 적용하여 선형 근사식 독립성 가정을 완화할 수 있는 차분선형 특성의 향상된 확률 계산 방법을 제안하며, DES와 SERPENT에 적용하여 기존 분석결과를 재분석한다. DES의 7-라운드 차분선형 특성의 확률은 $1/2+2^{-5.81}$, SERPENT의 9-라운드 차분선형 특성의 확률은 $1/2+2^{-57.9}$로 다시 계산되었고 공격에 필요한 데이터 복잡도는 각각 $2^{0.2}$, $2^{2.2}$배 감소한다.

Abstract ▼ AI-Helper

The complexity of the differential-linear cryptanalysis is strongly influenced by the probability of the differential-linear characteristic computed under the assumption of round independence, linear approximation independence, and uniformity for the trail that does not satisfy differential trail. Therefore, computing the exact probability of the differential-linear characteristic is a very important issue related to the validity of the attack. In this paper, we propose a new concept called DLCT(Differential-Linear Connectivity Table) for the differential-linear cryptanalysis. Additionally, we propose an improved probability computation technique of differential-linear characteristic by applying DLCT. By doing so, we were able to weaken linear approximation independence assumption. We reanalyzed the previous results by applying DLCT to DES and SERPENT. The probability of 7-round differential-linear characteristic of DES is $1/2+2^{-5.81}$, the probability of 9-round differential-linear characteristic of SERPENT is computed again to $1/2+2^{-57.9}$, and data complexity required for the attack is reduced by $2^{0.2}$ and $2^{2.2}$ times, respectively.

주제어

표/그림 (10)

그림 Fig. 1. The 4-Round Differential Characteristic Used in [4] (where V ∈{1,..., F_x}, W∈{0,8}, X ∈{0,8}, Y ∈{0,2}, Z ∈{0,2}, M∈{0,...,7} and ′?′ means random value in {0,1})
그림 Fig. 2. The 3-Round Linear Approximation Used in [4]
표 Table 1. The Part of DLCT of PRESENT S-box(row means input difference and column means output mask of S-box).
그림 Fig. 3. The input difference and output mask for the 5-Round S-box 5 where the DLCT is applied after the 4-Round Differential Characteristic (the value ′?0????′ before S-box indicates the difference. 0 means zero difference, ′?′ means random value in {0,1} and the value ′1111′ after the S-box means the bits to be masked).
그림 Fig. 4. Differential Distribution Graph of 32 input difference values in DES.
표 Table 2. The Part of DLCT of the S-box 5 in DES. Input difference(Δ_i ) have 32 values, output mask(α) is 0xF and C_i means DLCT_S (Δ_i ,α)
그림 Fig. 5. Differential and Linear Representation Example
그림 Fig. 6. The input difference and output mask (the state before S-box 5 is the difference and the state after the S-box 5 is the mask bits) for 4-Round S-box 5 to which DLCT is applied after 3-Round Differential Characteristic. ′?′ means random value in {0,1} and a shaded portion denotes a mask bit).
그림 Fig. 7. Differential Distribution Graph of 64 input difference values in SERPENT.
표 Table 3. The Part of DLCT of two S-boxes in SERPENT (entire size of DLCT is 256 by 256). Input difference(Δ_i ) have 64 values, output mask is 0x48 and C_i means DLCT_S (Δ_i ,α) .

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

가설 설정

많은 블록 암호 분석 연구는 위의 가정 1을 전제로 이루어져 왔으며 정확하진 않지만, 합리적인 가정으로서 간주 되고 있다. 본 논문은 기본적으로 가정 1을 전제로 한다.

제안 방법

2015년에는 Jiqiang Lu가 자동화 탐색 기법을 사용하여 전체 차분 특성을 탐색하고 Biham 등이 사용했던 확장된 차분선형 특성의 확률 계산에 필요한 가정을 완화했다. 그리고 이를 DES에 적용하여 Biham 등의 결과보다 더 긴 라운드의 차분선형 특성을 구성하였다[8]. 차분선형 분석은 소개된 이후에 다양한 암호들에 대한 적용이 이루어지고 있으며, 더 높은 확률을 갖는 차분선형 특성을 구성하기 위한 연구가 이루어지고 있다.
2018년 Carlos Cid 등은 부메랑 쿼텟 분석 도구인 BCT(Boomerang Connectivity Table)를 제안하였고 이를 통해 쿼텟의 존재성 문제를 해결하였다. 또한, S-box Switch 기법에서 S-box 입력 값들의 상호 종속성으로 인해 발생하는 일반화된 스위칭 효과(generalized switching effect)를 제안하여 쿼텟의 확률을 개선 시켰다[15].
이를 위해 본 논문은 DLCT(Differential-Linear Connectivity Table)를 제안하며, DLCT를 적용한 새로운 특성의 확률 계산 방법을 제안한다. 제안하는 방법은 차분의 균일 분포(uniform distribution) 가정을 사용하여 일반화될 수 있으며, 균일 분포 가정을 사용하지 않는다면 실험적인 결과를 바탕으로 차분선형 특성의 확률을 계산할 수 있다.
Jiqiang Lu는 [8]에서, 자동화 탐색 기법을 사용하여 모든 특성을 탐색함으로써 가정 3을 완화하고 확률 계산을 진행하였다. 이를 통해 전체 차분 특성을 탐색할 수 있는 실험 범위 내에서 Biham 등의 결과보다 더 긴 라운드의 차분선형 특성을 구성하였다.
이를 위해 본 논문은 DLCT(Differential-Linear Connectivity Table)를 제안하며, DLCT를 적용한 새로운 특성의 확률 계산 방법을 제안한다. 제안하는 방법은 차분의 균일 분포(uniform distribution) 가정을 사용하여 일반화될 수 있으며, 균일 분포 가정을 사용하지 않는다면 실험적인 결과를 바탕으로 차분선형 특성의 확률을 계산할 수 있다. 균일 분포 가정에서 벗어날수록 더 정확한 확률을 계산할 수 있다.

대상 데이터

본 장에서는 앞서 소개한 식 (6)과 (7)을 사용하여 실제 DES와 SERPENT에 대한 차분선형 특성의 확률을 다시 계산하고 더 정확한 확률을 얻은 결과를 제시한다. 실험은 2⁴⁰의 데이터를 사용하였으며 평문과 키의 비율을 조정하고, 임의의 난수 값으로 설정하여 진행되었다.

데이터처리

따라서 더 정확한 확률을 계산하기 위해선 실제와 근사한 w_i값들을 알아야 한다. 본 논문에서는각 w_i의 값의 평균을 실험적으로 측정하였으며 실험 값의 분포는 Fig. 5와 같다. 측정한 w_i값들을 이용 하여 다시 전체 차분선형 특성의 확률을 계산할 수 있고, 전체 차분선형 특성의 확률은 식 (7)을 이용 하여 계산하면 다음과 같다.

이론/모형

일반적으로 다음 가정 1을 사용하여 반복 블록 암호를 마코브 블록 암호(markov block cipher)로 간주하여 확률을 계산한다[16]. 디퍼렌셜의 확률은 차분 특성을 구성하는 각 한 라운드 차분 특성 확률의 곱으로 전체 확률을 계산하며, 선형 근사의 경우 Piling-up Lemma[2]를 사용하여 계산한다.
본 논문에서는 차분 특성 및 선형 근사를 표현하기 위하여 [6]에서 Biham 등이 사용한 표기법을 동일 하게 사용한다. 1/4의 확률로 이동하는 차분은 굵은 화살표로 표시를 하고 1/8의 확률로 이동하는 차분은 얇은 화살표로 표시한다.

성능/효과

이 방법을 실제로 Biham 등이 제안한 DES의 7-라운드 차분선형 특성과 SERPENT의 9-라운드 차분선형 특성에 적용하여 확률을 다시 계산한다. DES의경우 확률이 1/2+2^-5.81으로 계산되었고 기존 분석 결과와 비교하여 데이터 복잡도가 약 2^0.2배 감소한다. SERPENT의 경우 확률이 1/2+2^-57.
로 계산하였다. 구성한 특성으로 SERPENT의 11-라운드 변형에 대한 키 복구 공격을 진행하였으며, 약 2^125.3의 평문을 사용하여 72.1%의 성공률로 공격했다. 본 논문에서 SERPENT에 대한 9-라운드 차분 선형 특성의 바이어스는 약 2^-57.
의 값을 실제와 근사한 값으로 적용하면 전체 차분선형 특성의 확률을 더 정확하게 계산할 수 있다. 다시 계산된 차분선형 특성의 확률은 기존에 계산한 DES의 7-라운드 차분선형 특성의 확률보다 증가했음을 알 수 있다.
따라서 DLCT를 사용하면 선형 근사의 적어도 한 라운드는 가정 2를 완화하여 계산할 수 있게 된다. 다시 말해서, 선형 근사의 전체 확률을 가정 2를 사용하지 않고 계산할 수는 없지만, 적어도 선형 근사의 처음 한 라운드는 DLCT 를 사용함으로써 좀 더 정확한 값을 계산할 수 있다.
차분선형 특성을 구성하여 실제 암호에 대한 공격을 진행할 때에는 O(p-2 q-4 )의 데이터 복잡도가 필요하다. 따라서 기존에 계산된 차분선형 특성의 확률과 비교하여 본 논문에서 다시 계산한 확률이 더 좋을 경우, 공격 복잡도가 줄어든다. 본 논문은 기존에 사용했던 차분선형 특성을 바꾸지 않고 새로운 확률 계산 방법으로 다시 확률을 계산했기 때문에 기존에 사용했던 공격 알고리즘은 똑같이 적용되며, 향상된 확률 정도에 따라 공격 복잡도가 개선된다.
본 논문에서 SERPENT에 대한 9-라운드 차분 선형 특성의 바이어스는 약 2-57.9로 계산되었으며 이결과는 기존의 분석 결과와 비교하여 데이터 복잡도가 약 22.2 ≈ 4.6배 줄어든다.
본 논문에서는 7-라운드 차분선형 특성의 확률을 DLCT를 적용하여 0.0178≃ 2-5.81으로 다시 계산하였으며, 실제 구별 공격 시 데이터 복잡도가 약 20.2 ≈ 1.15배 줄어든다.
본 논문에서는 논문에서 제안하는 DLCT(Differential -Linear Connectivity Table)를 사용하여 두 선형 근사의 입력 값이 독립적이라는 가정 2를 완화하여 차분선형 특성의 확률을 계산하는 방법을 제안하고 실제로 DES와 SERPENT에 적용하여 다시 계산한 결과, 기존에 제시된 결과보다 개선된 확률을 얻을 수 있었다.
따라서 기존에 계산된 차분선형 특성의 확률과 비교하여 본 논문에서 다시 계산한 확률이 더 좋을 경우, 공격 복잡도가 줄어든다. 본 논문은 기존에 사용했던 차분선형 특성을 바꾸지 않고 새로운 확률 계산 방법으로 다시 확률을 계산했기 때문에 기존에 사용했던 공격 알고리즘은 똑같이 적용되며, 향상된 확률 정도에 따라 공격 복잡도가 개선된다.
선형 근사 입력 값의 종속성에 의해, 전체 차분선형 특성의 확률은 기존 결과보다 증가할 수도 있고 감소할 수도 있다. 그러나 대부분 DLCT의 입력 차분은 부정 차분 형태이므로 가능한 입력 차분의 분포를 측정하면 더 정확한 확률을 계산 수 있다.
실제 값과 근사한 wi를 사용하여 차분선형 특성의 확률을 다시 계산하면 기존에 계산된 확률보다 약 21.1 ≈ 2.14배 증가한 확률을 얻을 수 있다.
위의 결과처럼, 각 w_i의 값을 실제와 근사한 값으로 적용하면 전체 차분선형 특성의 확률을 더 정확하게 계산할 수 있다. 다시 계산된 차분선형 특성의 확률은 기존에 계산한 DES의 7-라운드 차분선형 특성의 확률보다 증가했음을 알 수 있다.
적용하는 암호에 따라서 확률의 개선 정도는 다를수 있는데, SERPENT의 경우 바이어스가 2배 이상 개선되었으며 이는 데이터 복잡도를 4배 이상 감소시키게 된다. 이러한 결과를 통해 기존에 차분선형 특성의 확률 계산이 독립성 가정으로 인해 다소 정확하지 못하게 계산되어 온 것을 확인할 수 있다. 본 논문에서 제안하는 DLCT를 적용한 계산 방법을 사용하면 이러한 문제를 조금이나마 해결할 수 있다.

후속연구

그러나 기존에 제안된 확률 계산 방법은 실제 분석에서 만족하지 못하는 몇 가지 독립성 가정들을 요구하기 때문에 계산된 확률이 실제 확률과 차이가 생길 수 있다. 따라서 가정을 완화 하여 확률 계산을 할 수 있다면 기존의 결과보다 더 정확한 안전성 분석이 가능하다.

질의응답

핵심어	질문	논문에서 추출한 답변
	차분선형 분석의 복잡도는 무엇에 큰 영향을 받는가?	차분선형 분석의 복잡도는 라운드 독립성, 선형 근사식 독립성, 차분 경로를 만족하지 못하는 경로에 대한 균일성 가정 아래 계산되는 차분선형 특성의 확률에 큰 영향을 받는다. 따라서 차분선형 특성의 정확한 확률을 계산하는 것은 공격의 유효성과 관련된 매우 중요한 문제이다.
	차분 분석이란?	차분 분석(differential cryptanalysis)은 평문의 차분이 암호화가 진행되면서 암호문의 차분에 어떠한 영향을 미치는지 분석하는 암호 분석 기법으로, Biham과 Shamir에 의해 1990년 처음 소개되었다[1]. 선형 분석(linear cryptanalysis)은 평문과 암호문, 그리고 키 사이의 관계를 선형 식으로 근사시켜서 분석하는 암호 분석 기법으로 Matsui에 의해 1992년 처음 소개되었다[2].
	1994년 Langford와 Hellman은 확률 1인 3-라운드 (부정) 차분 특성과 확률이 가장 좋은 3-라운드 선형 근사를 연결하여 6-라운드의 특성을 구성 하는 차분선형 분석 기법을 제안한 이유는?	차분 특성 및 선형 근사는 일정 라운드 이상으로 길게 구성할 경우, 해당 특성을 만족할 확률이 매우 낮아지기 때문에 분석에 사용할 수 없게 된다. 따라서 1994년 Langford와 Hellman은 확률 1인 3-라운드 (부정) 차분 특성과 확률이 가장 좋은 3-라운드 선형 근사를 연결하여 6-라운드의 특성을 구성 하는 차분선형 분석 기법을 제안했다[3].

참고문헌 (16)

Biham, Eli, and Adi Shamir. "Differential cryptanalysis of DES-like cryptosystems." Journal of CRYPTOLOGY 4(1), pp. 3-72, 1991.

상세보기
Matsui, Mitsuru. "Linear cryptanalysis method for DES cipher." Workshop on the Theory and Application of of Cryptographic Techniques. Springer, Berlin, Heidelberg, pp. 386-397, 1993.
Langford, Susan K., and Martin E. Hellman. "Differential-linear cryptanalysis." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, pp. 17-25, 1994.
Biham, Eli, Orr Dunkelman, and Nathan Keller. "Enhancing differential-linear cryptanalysis." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, pp. 254-266, 2002.
FIPS, PUB. "46-3: Data encryption standard (des)." National Institute of Standards and Technology 25(10) 1-22, 1999
Biham, Eli, Orr Dunkelman, and Nathan Keller. "Differential-linear cryptanalysis of Serpent." International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, pp. 9-21, 2003.
Biham, Eli, Ross Anderson, and Lars Knudsen. "Serpent: A new block cipher proposal." International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, pp. 222-238, 1998.
Lu, Jiqiang. "A methodology for differential-linear cryptanalysis and its applications." Designs, Codes and Cryptography 77(1), pp. 11-48, 2015

상세보기
Wagner, David. "The boomerang attack." International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, pp. 156-170, 1999.
Kelsey, John, Tadayoshi Kohno, and Bruce Schneier. "Amplified boomerang attacks against reduced-round MARS and Serpent." International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, pp. 75-93, 2000.
Biham, Eli, Orr Dunkelman, and Nathan Keller. "The rectangle attack-rectangling the Serpent." International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, pp. 340-357, 2001.
Biryukov, Alex, and Dmitry Khovratovich. "Related-key cryptanalysis of the full AES-192 and AES-256." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, pp. 1-18, 2009.
Dunkelman, Orr, Nathan Keller, and Adi Shamir. "A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony." Annual Cryptology Conference. Springer, Berlin, Heidelberg, pp. 393-410, 2010.
Murphy, Sean. "The return of the cryptographic boomerang." IEEE Transactions on Information Theory 57(4), pp. 2517-2521, 2011.

상세보기
Cid, Carlos, et al. "Boomerang Connectivity Table: A New Cryptanalysis Tool." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, pp. 683-714, 2018.
Lai, Xuejia, James L. Massey, and Sean Murphy. "Markov ciphers and differential cryptanalysis." Workshop on the Theory and Application of of Cryptographic Techniques. Springer, Berlin, Heidelberg, pp.17-38, 1991.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증