Ⅰ. 서론

SHACAL-2⁽⁴⁾는 NESSIE(New European Schemes for Signatures, Integrity, and Encryption) 프로젝트에 제안된 256-비트 블록 암호이다. 이는 국제 표준 해쉬 알고리즘 SHA-2^⑼ 의 압축 함수에 기반을 두었으며, 최근 NESSIE 프로젝트의 256-비트 블록 암호로 선정되었다.

현재까지 SHACAL-2⁽⁴⁾ 블록 암호에 대한 암호 학적 분석 결과는 불능 차분 특성을 이용한 30-라운 드 SHACAL-2의 안전성 평가만 이루어졌다.^⑸ 〔5〕에 의해 소개된 공격은 마지막 3 라운드의 비선형관계식을 이용한 14-라운드 불능 차분 특성을 기반으로 하고 있다.

본 논문에서는 14-라운드 부정 차분 특성을 17- 라운드 특성으로 확장하고자 〔5〕에 표현된 3-라운드 비선형 관계식을 이용한다. 확장된 17-라운드 특성 은 512-비트 키를 사용하는 32-라운드 SHACAL -2에 대해 전수 조사 공격 보다 빠른 공격을 가능케 한다. 또한 본 논문에서는 10-라운드 포화 특성을 13-라운드 특성으로 확장하기 위해 3-라운드 비선 형 관계식을 이용한다. 확장된 13-라운드 특성은 512-비트 키를 사용하는 28-라운드 SHACAL-2에 대해 전수 조사 공격 보다 빠른 공격을 가능케 한다. 본 논문의 분석과〔5〕의 분석 결과의 비교는 표 1과 같다.

표 1. SHACAI-2의 분석 결과 비교

CP: 선택 평문, 시간: 암호화 단위, 메모리: 바이트 단위

Ⅱ. SHACAL-2 블록 암호의 소개

H. Handschuch와 D. Naccache에 의해 제안 된 SHACAL-2⁽⁴⁾는 국제 표준 해쉬 함수 알고리즘 SHA-2^⑼의 압축 함수에 기반을 두었으며, 다양한 키 길이(최대 512 비트)를 가지는 256-비트 블록 암호이다. SHACAL-2 암호화 과정은 다음과 같다. 

256 비트 평문은 여덟 개의 32 비트 워드 A, B, C, D, E, F, G, H로 분할된다. 32 비트 워드 * 를 寸번째 라운드 입력 값이라 하면, 평문 P는 \(A^{0}, B^{0}, C^{0}, D^{0}, E^{0}, F^{0}, G^{0}, H^{0}\)으로표현되며, 64 라운드 과정을 거친 후 암호문은 \(A^{64}, B^{64}, C^{64}, D^{64},E^{64}, F^{64}, G^{64}, H^{64}\)이다. i( =0, ..., 63)번째 라운드 암호화 과정은 다음과 같다.

여기서 +는 법 2³² 덧셈을 의미하며, Wⁱ는 32 비트 라운드 키, Kⁱ는 32 비트 라운드 상수 값이다

그림1.SHACAL-2의 i번째 라운드 암호화 과정 

(각 라운드 상수값은〔9〕을 참조하라). 위에 정의된 6번째 라운드 암호화 과정에 사용하는 함수는 다음과 같다.

여기서 X는 32 비트 워드 X의 보수를 의미하며, S_i(X)는 32 비트 워드 X의 i비트 오른쪽 순환을 의미한다(즉, Si(X)=X《t).

\(\begin{aligned} &T_{1}^{i+1}=H^{i}+\sum_{1}\left(E^{i}\right)+C h\left(E^{i}, F^{i}, G^{i}\right)+K^{i}+W^{i} \\ &T_{2}^{i+1}=\sum_{0}\left(A^{i}\right)+M a j\left(A^{i}, B^{i}, C^{i}\right) \\ &H^{i+1}=G^{i} \\ &G^{n+1}=F^{i} \\ &F^{i+1}=E^{i} \\ &E^{i+1}=D^{i}+T_{1}^{i+1} \\ &D^{i+1}=C^{i} \\ &C^{i+1}=B^{i} \\ &B^{i+1}=A^{i} \\ &A^{i+1}=T_{1}^{i+1}+T_{2}^{i+1} \end{aligned}\)

\(\begin{aligned} C h(X, Y, Z) &=(X \& Y) \oplus(\neg X \& Z) \\ \operatorname{Maj}(X, Y, Z) &=(X \& Y) \oplus(X \& Z) \oplus(Y \& Z) \\ \sum_{0}(X) &=S_{2}(X) \oplus S_{13}(X) \oplus S_{22}(X) \\ \sum_{1}(X) &=S_{6}(X) \oplus S_{11}(X) \oplus S_{25}(X) \end{aligned}\)

SHACAL-2의 키는 최대 512 비트까지 허용되며 512 비트 보다 작은 키에 대해서는 0 스트링을 패딩하여 총 512 비트를 생성한 후 사용한다. 하지만 SHACAL-2는 128 비트 보다 작은 키의 사용은 지양한다. 512 비트 키 스트링을 \(W=\left[W^{0} \mid\right.\)\(\left.\begin{array}{l|l|l} W^{1} & \cdots & W^{15} \end{array}\right]\)와 같이 표시하면, 2048 비트 키 확장 과정은 다음과 같다.

\(\begin{gathered} W^{i}=\sigma_{1}\left(W^{i-2}\right)+W^{i-7}+\sigma_{0}\left(W^{i-15}\right)+W^{i-16}, 16 \leqq i \leqq 63 \\ \sigma_{0}(x)=S_{7}(x) \oplus S_{18}(x) \oplus R_{3}(x) \\ \sigma_{1}(x)=S_{17}(x) \oplus S_{19}(x) \oplus R_{10}(x) \end{gathered}\)

여기서 R_i(x)는 32 비트 워드 /의 C비트 오른쪽 쉬프트를 의미한다. (즉. R_i(x) = x«i).

Ⅲ. 차분-선형 유형 공격

1994년 Langford와 Hellmane은 [6]에서 차분 공격⁽¹⁾과 선형 공격⁽⁷⁾을 결합하는 차분-선형 공격 방법을 소개하였다. 차분-선형 공격 방법①iffer- ential-Linear Cryptanalysis)의 일반화된 형태 는 다음과 같다.

차분 특성을 표현하기 위하여 본 논문에서는 입력 차분을 \(\Omega_{P}\)으로. 출력 차분을 \(\Omega_T\)으로 표기한다. 또한 선형 근사식을 표현하기 위하여 입력 비트 마스 크, 출력 비트 마스크, 부분 키 비트 마스크를 각각 \(\lambda_{P}, \ \lambda_{T}, \ \lambda_{K}\)으로 표기한다. E를 블록 암호라 정의 할 때, \(E=E_{1} \circ E_{0}\)라 가정하자. 차분 특성과 선형 근사식의 결합은 부분 암호 E₀에 확률 P를 가지는 차분 특성 \(\Omega_{P} \rightarrow \Omega_{T}\) 와, 부분 암호 E₁ 에 확률 \(\frac{1}{2}+q\)을 가지는 선형 근사식 \(\lambda_{P} \longrightarrow \lambda_{T}\)을 이용한다. P와 P*를 차분 조건 \(P \oplus P^{*}=\Omega_{P}\)을 만족하는 평문 쌍 이라 가정할 때 Langford와 Hellman은 E₀에 확률 1을 가지는 부정 차분 특성 \(\Omega_{P} \rightarrow \Omega_{T}\)을 이용하였다. \(E_{0}(P) \oplus E_{0}\left(P^{*}\right)\)의 값은 확률 1로 특정 위치의 값이 고정된다. 따라서 적당한 비트 마스크 \(\lambda_p\)를 통해 한 비트 방정식을 유도할 수 있다. 즉. \(\lambda_{P} \cdot\left(E_{0}(P) \oplus E_{0}\left(P^{*}\right)\right)=a\)은 확률 1로 성립한다. 단, a의 값은 0 또는 1이며, a = \(\lambda_{P} \cdot \Omega_{T}\)이다. 또한 부분 암호 E₁의 선형 근사식 존재성에 대한 가정에 따라 확률 \(\frac{1}{2}+q\) 또는 바이어스 q를 가지는 두 개의 선형 근사식

\(\begin{aligned} &\lambda_{P} \cdot E_{\mathrm{0}}(P) \oplus \lambda_{T} \cdot E_{1}\left(E_{0}(P)\right) \oplus \lambda_{K} \cdot K=0 \text { 와 } \\ &\lambda_{P} \cdot E_{\mathrm{0}}\left(P^{*}\right) \oplus \lambda_{T} \cdot E_{\mathrm{y}}\left(E_{0}\left(P^{*}\right)\right) \oplus \lambda_{K} \cdot K=0 \end{aligned}\)

을 얻을 수 있다. 단, K는 부분 암호 E₁에 사용하는 부분 키이다. 따라서, 〔7〕에 소개된 piling up lemma를 사용하여 확률 \(\frac{1}{2}+2 q^{2}\left(=\frac{1}{2}+2^{2-1} \cdot q \cdot q\right)\)을 갖는 선형 근사식을 다음과 같이 얻을 수 있다.

\(\lambda_{T} \cdot E_{1}\left(E_{0}(P)\right) \oplus \lambda_{T} \cdot E_{1}\left(E_{0}\left(P^{*}\right)\right)=a\)       (1)

따라서 (1)을 이용한 선형 공격을 수행하기 위해서 O(q^-4)개의 선택 평문 쌍을 요구한다.

2002년 〔2〕에서 Biham, Dunkleman, Keller 는 위의 차분-선형 공격은 차분 특성이 1보다 작은 경우로 확장할 수 있음을 소개하였다. 이러한 분석 방법을 향상된 차분-선형 공격 (Enhanced Differential-Linear Cryptanalysis)이라 부르며, 일반화 된 공격 형태는 다음과 같다.

부분 암호 E₀에 확률 p(≤ 1)를 가지는 차분 특성 \(\Omega_{P} \rightarrow \Omega_{T}\)이 존재한다고 가정하자. 평문 쌍 P와 P*가 차분 특성 \(\Omega_{P} \rightarrow \Omega_{T}\)을 만족한다면(확률 p에 따라 성립한다), 확률 1을 가지고 한 비트 방정식 \(\lambda_{P} \cdot\left(E_{0}(P) \oplus E_{0}\left(P^{*}\right)\right)=a\)이 성립한다. 반면, 평문 쌍 P와 P*가 차분 특성 \(\Omega_{P} \rightarrow \Omega_{T}\)을 만족하지 않는 다면(확률 1-P에 따라 성립한다), \(\lambda_{P} \cdot\left(E_{0}(P) \oplus\right.\)\(\left.E_{0}\left(P^{*}\right)\right)\)의 값은 랜덤하게 분포한다고 가정한다. 따라서 위의 두 경우를 모두 고려하여 차분 조건 \(P \oplus P^{*}=\Omega_{P}\)을 만족하는 평문 쌍 P와 P*는 확률 \(\frac{1}{2}+\frac{p}{2}\left(=p \cdot 1+(1-p) \cdot \frac{1}{2}\right)\)를 가지고 한 비트 방정식 \(\lambda_{P} \cdot\left(E_{0}(P) \oplus E_{0}\left(P^{*}\right)\right)=a\)을 얻을 수 있다.

부분 암호 E₁의 두 개의 선형 근사식

\(\begin{aligned} &\lambda_{P} \cdot E_{0}(P) \oplus \lambda_{T} \cdot E_{1}\left(E_{0}(P)\right) \oplus \lambda_{K} \cdot K=0 \text { 와 } \\ &\lambda_{P} \cdot E_{0}\left(P^{*}\right) \oplus \lambda_{T} \cdot E_{1}\left(E_{0}\left(P^{*}\right)\right) \oplus \lambda_{K} \cdot K=0 \end{aligned}\)

을 이용하여 차분-선형 공격과 유사하게 확률\(\frac{1}{2}+2 p q^{2}\left(=\frac{1}{2}+2^{3-1} \cdot \frac{p}{2} \cdot q^{2}\right)\)로 성립하는 선형근사식 (1)을 얻을 수 있다. 따라서 향상된 차분-선 형 공격을 수행하기 위해서 \(O\left(p^{-2} q^{-4}\right)\)개의 선택 평문 쌍을 요구한다. 특별히 선형 근사식의 확률이 1 이라면, 확률 \(\frac{1}{2}+\frac{p}{2}\left(=\frac{1}{2}+2^{3-1} \cdot \frac{p}{2} \cdot\left(\frac{1}{2}\right)^{2}\right)\)로 선형 근사식 (1)이 성립하며, O(p^-2)개의 선택 평문 쌍을 이용하여 공격할 수 있다.

지금부터 위의 차분-선형 분석 기술을 통해 유도 할 수 있는 몇 가지 가능한 차분-선형 유형 공격을 소개한다. 본 논문에서는 차분 공격 또는 차분 공격 의 변이 공격과 선형 공격 또는 선형 공격의 변이 공격을 결합하여 분석하는 모든 분석 방법을 차분- 선형 유형 공격이라 표현한다.

차분-선형 공격은 평문 쌍을 이용하는 대신에 평문 집합을 이용하는 경우로 확장할 수 있다. 평문 집합은 특정 비트에 포화상태를 만족하는 포화 집합 이라고 가정하자. 포화 집합이란 평문의 특정 72비트 자리에 가능한 모든 값이 정확하게 한 번씩 분포되어 있는 집합을 의미한다. 부분 암호 E₀에 확률 1을 갖는 포화 특성⁽³⁾이 존재한다고 가정하자. 따라서 특정 n비트 자리에 포화 상태를 만족하는 2ⁿ개로 구성된 평문 집합을 \(P_{i}\left(i=0, \ldots, 2^{n}-1\right)\)으로 표현한다면, 적당한 비트 마스크 \(\lambda_p\)를 이용하여 확률 1로 성립하는 한 비트 방정식 \(\lambda_{P} \cdot\left(\oplus_{i=0}^{2^{n}-1} E_{0}\left(P_{i}\right)\right)=0\)을 유도할 수 있다. 부분 암호 E₁에 확률 \(\frac{1}{2}+q\)를 가지는 선형 근사식의 존재에 따라 각 평문 P_i에 대해 선형 근사식 \(\lambda_{P} \cdot E_{0}\left(P_{i}\right) \oplus \lambda_{T} \cdot E_{1}\left(E_{0}\left(P_{i}\right)\right) \oplus\lambda_{K} \cdot K=0\)을 나타낼 수 있다. 따라서 piling up lemma에 의해 확률 \(\frac{1}{2}+2^{2^{n}-1} q^{2^{n}}\)로 성립하는 선형 근사식 (2)를 얻을 수 있다.

\(\lambda_{T} \cdot\left(\bigoplus_{i=0}^{2^{n}-1} E_{1}\left(E_{0}\left(P_{i}\right)\right)\right)=0\)       (2)

선형 근사식 (2)를 이용한 선형 공격을 수행하기 위해서 \(O\left(\left(2^{2^{n}-1} q^{2^{\prime \prime}}\right)^{-2}\right)\)개의 선택 평문 쌍이 필요하다. 따라서 위의 공격은 q의 값이 \(\frac{1}{2}\)에 매우 근접 하거나 \(\frac{1}{2}\)값을 갖는 블록 암호인 경우에 효과적으로 적용할 수 있다. 본 논문에서는 위의 분석 방법에 사용되는 특성을 포화-선형 특성 (square-linear distinguisher)이라 부른다.

더 나아가서 본 논문에서는 부분 암호 E₁의 선형 근사식을 이용하는 대신에 비선형 근사식을 이용하는 방법으로 확장한다. 만약 공격에 사용할 수 있는 비선형 근사식이 임의의 선형 근사식 보다 좋은 확 률로 성립한다면, 비선형 근사식을 이용하여 블록 암호의 분석에 효과적으로 적용할 수 있다. 본 논문에서는 차분 특성에 비선형 근사식을 결합한 형태를차분-비선형 특성 (differential-nonlinear dis- tinguisher)이라 하고, 포화 특성에 비선형 근사식 을 결합한 형태를 포화-비선형 특성(square-non- linear distinguisher)이라 부른다.

Ⅳ. SHACAL-2에 대한 차분-선형 유형 공격

이 절에서는 축소 라운드 SHACAL-2의 차분-선 형 유형 공격에 대한 안전성을 논의한다. 시작에 앞 서 본 논문에서 사용하는 표기법을 정의한다. 단, 워드의 비트 위치는 가장 오른쪽 최하위 비트부터 0 으로 시작하며, 왼쪽으로 갈수록 커진다.

□ P : 256 비트 평문, P=(A, ... , H) 또는 P = (A⁰, ... , H⁰).

□ P^r: r번째 라운드의 256 비트 입력 값, P^r=(A^r, …, H^r).

□ x_i^r : X^r의 i 번째 비트, JT e {A ■■■, IT, W, 欢}.

□ 苟“ : “의 W 번째 비트

□ ?: 알 수 없는 값 또는 알 수 없는 값들의 모임

□ e, : 寸번째 비트를 제외한 모든 비트가 0인 32 비 트 워드.

口 气, …": eq … ©6;1 또는 단, M=

口 气…: 标, ...為번째 자리의 값은 1, (U + 1) ~ 31번째 자리의 값은 0, 1, 또는 알 수 없는 값이고, 毎<…< 養의 妃...為를 제외한 자 리의 값은 0인 32 비트 워드.

□ %: :j번째 자리의 값은 0, 玄번째를 제외한 모든 자리의 값은 0, 1, 또는 알 수 없는 값을 갖는 32비트 워드.

□ CS[Constant Set) : 하나의 32 비트 상수가 2彩 개로 구성되어 있는 집합.

□ PSePermutation Set) : 32 비트에 가능한 모든 값을 한번 씩 순서에 관계없이 포함하는 집합.

□ -PS : 동일 라운드에서 用 집합의 원소 X를 순서를 고려한다면, —PS는 로 구성된 32 비트 가능한 모든 값을 갖는 집합. 즉, 순서를 고려한 PS의 원소와 -PS의 원소의 합은 모두 0이 된다.

□ BS{Balanced Set) : 임의의 값을 갖지만, 그들 의 합(XOR)은 0이 되는 232개로 구성된 집합 만약 이러한 성질이 0번째 비트에서 만족한다면, 昭으로 표기한다.

이 절에서 소개하는 모든 공격은〔5〕의 3-라운드 비선형 관계식을 이용한다. 3-라운드 비선형 관계식 은 다음과 같다.

楣는 비선형 함수 NF(Ar + \Br + \--, Hr + \Kr, 町, 俨+ 1, 叮+ 2)의 출력 값으로 표현할 수 있다. 이 함수를 간단하게 NFE3로 표시한다. 단, 0 M r M 61.

#

위 비선형 방정식의 顷拓曜妒_2, 此;₃은 다음과 같이 표현할 수 있다.

#

4.1 차분-비선형 툭성을 이용한 32-라운드 SHA- CAL-2 공격

이 절에서는 14-라운드 부정 차분 특성을 구성하는 방법을 소개한 후, 이 차분 특성에 앞서 설명한 3-라운드 비선형 관계식을 연결하는 방법을 설명한다. 또한 구성된 17-라운드 차분-비선형 특성을 이용한 32-라운드 SHACAL-2 공격을 설명한다. 14-라운드 부정 차분 특성을 구성하기에 앞서 차분 확률을 계산하기 위해 사용하는 SHACAL-2의 두 가지 차분 성질을 소개한다.

SHACAL-2의 첫 번째 차분 성질은 XOR 연산 과 법 덧셈 연산의 사용으로부터 유도할 수 있다. Z=X+ Y, Z' = X" + 广라고 가정하자. 단, 각각의 X, 匸X, , :广는 균일하게 분포하는 32 비트 난 수이다.

□ 만약 屜x' = q이고 r= r 라면, 확률 3「를 가지고 O' < 31, fc > l, j + k-l < 30), Z®Z' = e, 小…丿을 만족한다. 특별히 顶 = 31인 경우에 확률 1로 施厅 = 知을 만족한다.

□ 만약 x®x' = ej이고 y© r- = %라면, 확률 를 가지고(顶 <31』2 l, j + k-l < 30), Z®Z' = e小…e. i을 만족한다. 특별히 j = 31 인 경우에 확률 1로 Z&Z, = 0 을 만족한다.

□ 만약 X®X- = e“_ , Y® r- = e史 이고, / > 丿. 라 면, Z每8 = e"을 만족한다. 만약 Z®Z" = 勺~ 을 만족한다면, 이는 또한 Z* eZ = 矣 임을 의미한다. 단, 0 < k

SHACAL-2의 두 번째 차분 성질은 6와 Maj 함수로부터 유도된다. 이 함수는 비트별 연산이므로, 각 함수는 3 비트 입력에 1 비트 출력 값을 갖는 부 울 함수로 생각할 수 있다. 표 2는 6와 Maj 함수 의 비트별 XOR 차분 특성을 나타낸다. 첫 번째 세 개의 열은 의 여덟 가지 가능한 입력 차분 값을 표현하며, 다음 두 열은 각 함수 (免와 Maj$] 출력 차분 값을 표현한다. 마지막 두 열에서 0은 출 력 차분 값이 항상 0임을 의미하고, 1은 출력 차분 값이 항상 1임을 의미한다. 반면, 0/1은 출력 차분 값이 확률 1/2로 0을 확률 1/2로 1을 만족함을 의미한다.

표 2. 함수 ch와 Maj의 XOR 차분 분포표

또한 6와 Maj 함수로부터 발생하는 차분 확률 은 평문 쌍의 특정 비트를 고정함으로써 조절 가능 하다. 즉, 평문 쌍의 특정 비트를 고정하여 처음 몇 라운드에 대한 차분 확률을 극대화 할 수 있다. 6 함수에 대한 한 가지 예를 설명한다. 만약 6의 입력 차분 형태가 (0, 0, 1)과 같다면, 출력 차분 값은 0/1이다. 하지만 차분 (0, 0, 1)을 만족하는 두 개의 입력 값을 (1.0, 0)와 (1Q1)으로 선택한다면, Ch 의 출력 차분 값은 확률 1을 가지고 0값을 가진다. 따라서 평문 쌍의 특정 비트를 고정하여 처음 몇 라 운드의 6로부터 발생하는 차분 확률을 극대화 할 수 있다.

지금부터 14-라운드 부정 차분 특성을 구성하는 방법을 소개한다. 평문 쌍 P=(A, B, C, D, E, F, G, H、), P* = 3*, *, *, FHD, B, , r GE , C 는 차분(0, 0, 即, 0, 0, 었, 3, , 0)을 만족하고 (단, 7昭 = {9, 18, 29}, 払= {6, 9, 18, 20, 25, 29}), 표 3과 같이 고정된 비 트 값을 갖는다고 가정하자. 위의 조건을 만족하는 는 14 라운드 과정 후에 여덟 번째 워평문 쌍 P, P*드의 최하위 비트 차분 厶格은 확률 2%로 0를 만 족한다. 14-라운드 부정 차분 특성에 대한 자세한 차분 경로는 표 4를 통해 확인할 수 있다. 표 5에 나타나 있는 확률은 SHACAL-2의 두 가지 차분 성질을 이용하여 쉽게 확인할 수 있다.

표 3. 평문 쌍 F, P*의 고정 비트

표 4. SHACAL-2의 14-라운드 부정 차분 특성에 대한 가능한 ΔE10

표 5. SHACAL-2의 14-라운드 부정 차분 특성

14-라운드 부정 차분 특성과 3-라운드 비선형 방 정식의 결합은 厶萬4에 의해 이루어진다. 따라서 厶丑"의 값이 %가 되는 다양한 부정 차분 특성을 고려하여 위의 14-라운드 부정 차분 특성의 확률을 개선할 수 있다. 표 4의 14-라운드 부정 차분 특성 중 처음 9 라운드 같은 부정 차분 특성을 고려하 여, △步의 값이 %형태를 가지는 다양한 형태의 △E迎을 계산할 수 있다(표 4를 참조하라). 이 결 과에 기초하여 14-라운드 부정 차분 특성 확률은2-187(« 1. 2-22+4 . 2~23+9 . 2~24 +16 . 2-25 +. 厂26 + 42 . 2-27 + 51. 2-28)으로 개선할 수 있다

위에서 구성한 14-라운드 부정 차분 특성의 확률 3’은 확률 2^19-7(=2-18'7 + y . (1-2~18-7))을 가지는 선형 근사식 확률로 전환할 수 있다. 즉, 차분 (0, 0, eMi, 0, 0, e3i, e.Mt, 0) < 만족하고, 표 3과 같이 고정된 비트 값을 가지는 평문 쌍 P* , P는 확률 * + 2 - '打을 가지고 /* = 场”를 만족한다. 확률 *+2「戚7의 확인을 위해 [(J개의 다른 키에 대해 2 34개의 평문 쌍을 가지고, 厶沽'의 값의 분포를 테스트 하였다. 2 34개의 평문 쌍에 대한 이론적인 결과는 2 33+ 20170(= 2 34 . (七 + 2 -07))인 반면, 실제 구현 결과는 2 33 + 153189, 2 33+ 159168, 233+161745, 233+168761, 233 + 173142, 233 + 175476, 233 +177866, 233+196441, 233 +197654, 233 + 217151의 값을 얻을 수 있었다. 테스트를 통한 결과는 14-라운드 특성의 확률이 이론적인 평가 号 + 2 - 戚7보다 높다는 것을 알 수 있다. 이러한 결과 값의 차이는 厶丑"의 값이 % 값을 가지는 부 정 차분 특성 중 적은 경우만 고려했기 때문이다. 따라서 14-라운드 선형 근사식 확률은 §+2-戚7보다 작지 않음을 알 수 있다.

앞서 차분-선형 공격의 일반적인 형태를 언급한 것과 같이 위의 부정 차분 특성에 3■■라운드 비선형 방정식을 결합할 수 있다. 위의 조건에 맞게 구성된 평문 쌍 P, P'는 확률 考+ 2 을 가지고 碍 = '을 만족하기 때문에, 확률 号 + 2 '登을 가지고 다음 식이 성립함을 알 수 있다.

#(3)

따라서 확률 -y+ 2 37을 가지는 17-라운드 차분-비선형 특성을 구성할 수 있다.

다음 알고리즘1은 위의 17-라운드 차분-비선형 특성을 이용하여 512 비트 키를 사용하는 32-라운 드 SHACAL-2의 공격과정을 설명한다.

알고리즘 1

1. 차분 (SS3, 。, (仏以弓山。)을 가지고, 표 3의 조건을 만족하는 2424(=(23) .(2-1")-2)개의 평문 쌍을 선택한다. 각 평문 쌍에 대응하는 암호문 쌍을 요구한다.

2. 463 비트 키 俨', 戸°, …, 俨。, 站, , 떠, , …, S쎠, Z滯, 妒, …, 竣, 尻7, 쎠7, ..., ■成, Z麻, 诚5의 값을 추측한다. 32-라운드 SHACAL-2의 암호 문 쌍을 가지고 厶의 값을 얻기 위해서는 463 비트 키의 값의 추측을 요구한다. 더욱 자세한 사항은〔5〕을 참조하라.

3. 각각의 암호문 쌍과 추측한 키를 사용하여 부 분 복호화를 수행하고 식 (3)의 성립 여부를 테스트 한다. 식 (3)를 만족하는 평문 쌍의 수가 2, 侦+ 222와 같거나 크다면, 추측한 키를 저장한다. 만약 그렇지 않다면 단계 2로 돌아 간다.

4. 단계 3을 통과한 키에 대해서, 나머지 49 비 트에 대한 전수 조사를 수행한다. 만약 추측된 512 비트 키가 옳은 키라면 32-라운드 SAHCAL-2의 마스터 키로 출력하고, 그렇지 않다면, 단계 2로 돌아간다.

알고리즘1의 데이터 복잡도는 2昭선택 평문을 요 구하며, 공격에 사용되는 메모리는 암호문 쌍의 저장 공간에 의존하므로 약 2484(= 243'4 . 32)바이트 를 요구한다.

또한 알고리즘1의 계산 복잡도는 다음과 같이 평가할 수 있다. 단계 1의 계산 복잡도는 2434 32-라운드 SHACAL-2 암호화 과정을 요구하며 (데이터 수집 단계), 단계 3의 계산 복잡도는 평균 2504-2(=y . 쁘 . 2434 . 2463)32-라운드 SHAGAL -2 암호화 과정을 요구한다. 七 은 단계 3에서 수행하는 462 비트 키의 평균 조사 비율을 의미 한다. 단계 3을 통과하는 462 비트 키의 수를 평가 하기 위하여 다음과 같은 통계적인 방법을 사용한다. 올바르지 않은 키에 대해서는 A*의 값은 랜덤하게 분포한다. 이는 奇 = NF', 을 만족하는 암호 문 쌍의 수가 이항분포 X~ 血几(2)写土)를 따른다 는 것을 의미한다. 이항분포는 쉽게 정규 분포로 근 사할 수 있다. 즉, X~ Ngf. 단. /z = 241'4, 尸=24。.4 따라서 勿=丝二4)~皿(0, 1)이고 aPr[X> 24L4 + 222] =7^[Z> 3.5813] - 2-脇을 확인할 수 있다. 단계 3을 통과하는 올바르지 않은 463 비트 키의 기대값은 평균 2449-7(= § . 2463 . 厂明) 이므로, 단계 4의 계산 복잡도는 약 24987(= 24497 . 249)이다. 따라서 위 공격의 전체 계산 복잡도는 약 2504-2 32-라운드 SHACAL-2 암호화 과정을 요 구한다.

위의 분석 과정에 따르면 이항분포 X~ Bin (2%专+ 2-W7)을 갖는 옳은 키에 대해서 단계 3 을 통과할 확률은 약 98%임을 확인할 수 있다. 따라서 위 공격의 성공 확률은 약 98%이다.

또한 알고리즘1은〔8〕에 제시된 키 랭킹 과정으 로 바꾸어 생각할 수 있다. 즉, 단계 3에서 2 ”" + 2 22보다 크거나 같은 값을 갖는 키를 저장 하는 대신에 (2 462 - 2 45。.3)개 키의 카운터 값 보 다큰 2 450.3(= 2 463 . 2 - 27) 개의 키를 저장할 수 있다. ⑻에 제시된 order statistic을 사용하면 키 랭킹 과정을 이용한 공격의 성공 확률이 앞서 제 시한 공격의 성공 확률과 같음을 확인할 수 있다. 하지만 키 랭킹 과정은 모든 7]능한 2 m3개의 키를 저장하기 위한 거대한 메모리를 요구한다.

4.2 포화-비선형 특성을 이용한 28-라운드 SHA- CAL-2 공격

본 문단에서는 13-라운드 포화-비선형 특성을 묘 사하고. 이를 이용하여 28-라운드 SHACAL-2의 안전성을 분석한다.

전 절에서는 14-라운드 부정 차분 특성과 3-라운 드 비선형 특성을 연결한 17-라운드 차분-비선형 특성을 이용한 공격을 소개하였다. 이와 유사하게 본 절에서는 10-라운드 포화 특성과 앞서 묘사한 3-라 운드 비선형 특성을 연결한 13-라운드 포화-비선형 특성을 소개한다. 10-라운드 포화 특성은 다음과 같이 잘 선택된 평문 집합을 통하여 구성할 수 있다. 만약 232개로 구성된 평문 집합 £任 (o, o, 尸S, CS, , 1, CS-PS, CS') 寸 = 0, ..., 232-1 를 선택한다면(단, 0과 1은 각각 32 비트 워드 0000000S와를 나타낸다), 10 라운드 후에 여덟 번째 워드 의 최하위 비트는 균일 성질을 만족한다. 즉, 咪匕困&=0. 표 6은 확률 1을 만족하는 포화 특성을 자세하게 설명한다. 앞서 설명하였다시피 10- 라운드 포화 특성에 3-라운드 비선형 특성을 결합한다. 따라서 13-라운드 포화-비선형 특성은 확률 1로 다음과 같은 식이 성립한다.

#(9)

다음 알고리즘2는 위의 14-라운드 포화-비선형 특성을 이용하여 512 비트 키를 사용하는 32-라운 드 SHACAL-2의 공격과정을 설명한다.

알고리즘2

1. (0, 0, FS, CS, 1, CS, -RS, CS) 형태를 갖는 463개의 집합을 선택한다. 각 평문 집합 에 대응하는 암호문 집합을 요구한다.

2. 463 비트 키 俨7, 俨七…双展, 遮, 武, ..., 瞄 疏, 切..., 溫, 站‘诚, …, 武, u#, u# 의 값을 주측한다.

3. 각각의 암호문 집합에 대해서 추측한 키를 사용하여 부분 복호화를 수행하고 식 (4)의 성 립 여부를 테스트 한다. 식 (4)을 만족하지 않는다면, 2 단계로 돌아간다. 만약 그렇지 않 다면 추측한 키를 저장한다.

4. 단계 3을 통과한 키에 대해서, 나머지 49 비 트에 대한 전수 조사를 수행한다. 만약 추측 된 512 비트 키가 옳은 키라면 28-라운드 SHACAL-2의 마스터 키로 출력하고, 그렇지 않다면, 단계 2로 돌아간다.

알고리즘2의 데이터 복잡도는 463 . 2 32선택 평 문을 요구하며, 공격에 사용되는 메모리는 245'9 (=463 . 232 . 萍)바이트를 요구한다.

또한 알고리즘2의 계산 복잡도는 다음과 같이 평가 할 수 있다. 단계 1의 계산 복잡도는 463 - 2 32 28- 라운드 SHACAL-2 암호화 과정을 요구하며(데이터 수집 단계), 단계 3의 계산 복잡도는 평균 2494 1 (=1.—.(濟3 .尹+2如2 .产+…+以.评))282 28-라운드 SHACAL-2 암호화 과정을 요구한다. 단계 3을 통과하는 키 개수의 기대값은 약 1 (= 2463 . 2- 463) 이므로, 단계 4의 계산 복잡도는 약 2 49 28-라운드 SHACAL-2 암호화 과정을 요구 한다. 따라서 위 공격의 전체 계산 복잡도는 약 2 494 1 28-라운드 SHACAL-2 암호화 과정을 요 구한다.

Ⅴ. 결론

본 논문은 SHACAL-2의 차분-선형 공격을 다양한 경우로 확장한 차분-선형 유형 공격에 대해 소개 하였다. 차분-비선형 특성을 이용하여 2434 선택 평 문의 데이터 복잡도와 2施42의 계산 복잡도를 가지고 32-라운드 SHACAL-2를 공격하였다. 이는 SHACAL-2에 대한 가장 효과적인 분석 결과이다. 또한 본 논문에서는 포화-비선형 특성을 사용하여 463 - 232 선택 평문의 데이터 복잡도와 2知4」의 계 산 복잡도를 가지고 수행할 수 있는 28-라운드 SHACAL-2의 공격을 소개하였다.

본 논문은 기존의 차분-선형 공격을 응용하여 차 분 특성 대신 포화 특성, 선형 특성 대신 비선형 특성을 사용함으로써 분석 방법의 다양화를 꾀하였다. 비록 본 논문에서는 다루고 있지 않지만 이밖에 다양한 결합방식의 블록 암호 분석 방법이 존재하며, 이에 대한 연구는 블록 암호의 심도 있는 안전성 평 가에 중요한 기여를 할 것이다.