차분 암호 분석의 기초

차분 암호분석(Biham과 Shamir, 1990)은 평문 쌍 사이의 차이가 암호를 통과하며 어떻게 전파되는지 분석하는 선택 평문 공격입니다. 높은 확률로 예측 가능한 출력 차이를 만들어 내는 입력 차이를 찾으면, 공격자는 통계적으로 키 비트를 복구할 수 있습니다.

XOR 기반 암호에서는 차분을 ΔX = X XOR X'로 정의합니다. 덧셈 기반 암호에서는 차분을 ΔX = X - X' mod 2^n으로 정의합니다. XOR 차분은 XOR 키 결합과 교환되므로 가장 일반적으로 사용됩니다(차분 쌍에서는 키 스케줄의 효과가 상쇄됩니다).

차분 쌍 (P, P')에는 입력 차분 ΔP = P XOR P'가 있습니다. 암호화 후에는 출력 차분 ΔC = C XOR C'를 갖는 (C, C')가 됩니다. 유용한 차분은 높은 확률 p로 성립하는 ΔP → ΔC입니다. 즉, 차분이 ΔP인 많은 (P, P') 쌍이 출력 차분 ΔC를 만들어 냅니다.

DDT(차분 분포표)는 각 입력 차분 Δx와 출력 차분 Δy에 대해 S(x) XOR S(x XOR Δx) = Δy를 만족하는 입력 x의 개수를 셉니다. 2^n으로 나누면 확률이 됩니다. 좋은 S-상자의 최대 DDT 값은 2(확률 1/2^{n-1})이며, 강한 차분이 없어야 합니다.

r라운드 블록 암호에서는 각 라운드 전이가 알려진 확률을 갖는 ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1}의 수열을 찾습니다. 라운드별 확률을 곱하면 전체 확률은 p = p1 * p2 * ... * p_{r-1}가 됩니다. 공격에는 마지막 라운드 키를 복구하기 위해 2/p개의 쌍이 사용됩니다.

높은 확률의 r-1라운드 차분이 있으면 N = 2/p개의 평문 쌍을 수집합니다. 각 후보 마지막 라운드 키 K'에 대해 두 암호문을 한 라운드 복호화하고, 결과를 XOR한 다음, 차분이 ΔU_{r-1}와 일치하는지 확인합니다. 올바른 K'는 약 N/2번 일치하고, 잘못된 키는 약 N/2^{bit_size}번 일치합니다.

AES S-상자는 GF(2^8)에서의 곱셈 역원에 아핀 변환을 적용해 만듭니다. DDT 최댓값은 256개 중 4이므로 S-상자 하나의 차분 확률은 4/256 = 1/64 이하입니다. AES에는 라운드마다 S-상자 4개가 있지만, 광폭 경로 설계는 전체 차분 경로의 확률이 2^{-100}보다 작도록 보장합니다.

Joan Daemen의 광폭 경로 설계(AES/Rijndael에 사용)는 MixColumns의 분기 수 B를 정의합니다. 하나의 라운드를 통과하는 모든 비자명 차분 경로에서는 최소 B개의 S-상자가 활성화됩니다. 4개 라운드에 라운드당 S-상자 4개를 적용하면 활성 S-상자가 최소 25개가 되므로 확률이 2^{-100}보다 작아집니다.

절단 차분은 차분의 일부만 지정합니다. 예를 들어 정확한 차분값이 아니라 어떤 열이 활성화되었는지만 지정합니다. 전체 차분이 너무 약한 더 많은 라운드에 대한 공격이 가능해집니다. 축소 라운드 AES, SERPENT 및 기타 SPN 암호에 사용됩니다.

불가능 차분은 어떤 키에서도 절대로 발생할 수 없는 (ΔP, ΔC) 쌍입니다. 관찰된 (P, P') 쌍을 이 차분으로 매핑하는 키는 모두 제거할 수 있습니다. 충분한 쌍을 수집하면 잘못된 키가 모두 제거되고 올바른 키만 남습니다.

부메랑 공격(Wagner, 1999)은 짧은 차분 두 개를 결합한 적응형 선택 평문/암호문 공격입니다. 암호를 두 부분으로 나누고 각 부분에 짧고 높은 확률의 차분을 적용하므로, 하나의 차분만으로 가능한 것보다 더 많은 라운드에 대한 공격을 수행할 수 있습니다.

암호분석에서 차분 분포표(DDT)는 어떤 목적으로 사용됩니까?

차분 암호분석은 높은 확률로 입력 차이가 출력 차이로 전파되는 현상을 이용합니다. AES는 DDT에 최적화된 S-상자와 광폭 경로 설계를 통해 이에 대응합니다. 다음 주제: 선형 암호분석과 근사표.