💻 computer science

Analyzing Linear Layers in Related-Differential Cryptanalysis

본 논문은 AES 유사 암호의 선형 계층에서 관련-차분 구조의 존재를 체계적으로 조사하여, 모든 비-MDS 행렬, 모든 홀수 차수 대칭 MDS 행렬, 그리고 대부분의 순환 행렬에 대해 그러한 취약점이 불가피함을 증명하고, 동시에 $\mathbb{F}_{2^m}$ 위의 $3 \times 3$ MDS 행렬에 대한 완전한 특성을 제시한다.

원저자: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

게시일 2026-05-28

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 비밀을 보호하기 위해 고보안 금고 (디지털 잠금장치) 를 구축한다고 상상해 보세요. 아무도 이를 뚫지 못하도록 하기 위해 **선형 계층 (Linear Layer)**이라는 특수한 혼합 장치를 사용합니다. 이 장치는 데이터를 받아 섞고 분산시켜, 입력의 아주 작은 변화가 출력에서 거대하고 혼란스러운 변화로 이어지도록 만듭니다. 이를 '확산 (diffusion)'이라고 합니다.

수십 년간 암호학자들은 MDS 행렬이라는 특정 유형의 혼합 장치를 사용해 왔습니다. 이는 무언가를 완벽하게 분산시키는 데 있어 '골드 스탠다드'이기 때문입니다. 그들은 "우리가 MDS 행렬을 사용하면 안전하다"고 생각했습니다.

그러나 이 논문은 그 사고방식에 숨겨진 결함을 드러냅니다. 즉, 혼합 장치가 '골드 스탠다드' (MDS) 라 하더라도 **관련 차분 (Related Differentials)**이라는 비밀 약점이 여전히 존재할 수 있다는 것입니다.

다음은 저자들이 발견한 내용을 간단한 비유로 설명한 것입니다:

1. '골드 스탠다드'만으로는 부족합니다

MDS 성질을 잉크 한 방울이 종이 한 장 전체에 퍼진다는 보장으로 생각하세요.

과거의 믿음: 기계가 잉크를 완벽하게 퍼뜨린다면 (MDS), 그것은 안전합니다.
새로운 발견: 저자들은 기계가 잉크를 완벽하게 퍼뜨리지 않는다면 (Non-MDS), 비밀 약점이 반드시 존재한다는 것을 증명했습니다.
비유: 비밀 메시지를 방 안에 숨기려 한다고 상상해 보세요. 방이 작고 지저분하다면 (Non-MDS), 도둑이 쉽게 패턴을 찾아 몰래 들어갈 수 있습니다. 저자들은 오직 완벽하게 넓고 정리된 방 (MDS) 만이 안전할 가능성이 있다는 것을 증명했습니다. 하지만 넓은 방을 가지고 있다고 해서 안전이 보장되는 것은 아닙니다. 방의 모양도 중요하기 때문입니다.

2. '대칭의 함정'

많은 혼합 장치는 **대칭적 (Symmetric)**으로 설계됩니다. 이는 나비처럼 뒤집어도 똑같이 보인다는 의미입니다. 이는 구축하기 쉽기 때문에 인기가 있습니다.

발견: 저자들은 대칭적인 기계가 홀수 개의 부분 (예: 3x3 또는 5x5) 을 가지고 있다면, 항상 취약하다는 것을 발견했습니다.
비유: 홀수 명의 댄서가 있는 춤추는 바닥을 상상해 보세요. 그들이 어떻게 짝을 지으려 해도, 한 명의 댄서는 항상 중앙에 혼자 서 있게 되어 예측 가능한 패턴을 만듭니다. 저자들은 홀수 크기의 대칭 기계에서는 해커가 이용할 수 있는 '남은' 패턴이 항상 존재한다는 것을 증명했습니다. 아무리 잘 만들더라도 홀수라는 숫자 자체가 이 특정 유형의 공격에 대해 본질적으로 약하게 만듭니다.

3. '원형 패턴' 문제

또 다른 인기 있는 설계는 **순환 행렬 (Circulant Matrix)**입니다. 기어 패턴이 원형으로 반복되는 컨베이어 벨트를 상상해 보세요. 이는 효율적이고 빠릅니다.

발견: 저자들은 이러한 원형 장치를 조사하고 크기 (n 이라고 함) 에 기반한 규칙을 발견했습니다.
- 원의 크기가 3 의 배수 (3, 6, 9 등) 이거나 4 의 배수 (4, 8, 12 등) 이면 취약합니다.
- 실제로 그들은 크기가 매우 구체적인 숫자가 아닌 한 (구체적으로 12 의 배수에서 2 또는 10 만큼 떨어진 숫자가 아닌 경우), 기계는 취약하다는 것을 증명했습니다.
비유: 시계 다이얼을 생각하세요. 3 단계나 4 단계로 시계를 돌아다니려 하면, 결국 예측 가능한 방식으로 같은 지점을 반복하게 됩니다. 저자들은 대부분의 원형 설계에서 해커가 보안을 우회할 수 있는 기어 속의 '단축 경로'를 찾을 수 있음을 보여주었습니다.

4. 3x3 기계에 대한 '완벽한 레시피'

마지막으로, 저자들은 가장 작고 일반적인 크기인 3x3 행렬에 집중했습니다.

문제: 이전의 '안전한' 3x3 기계 찾기 시도는 불완전했습니다. 그들은 일부 재료를 빠뜨린 레시피를 제시했습니다.
해결책: 저자들은 15 가지 구체적인 규칙 (수학적 방정식) 으로 구성된 완전한 레시피를 작성했습니다.
비유: 케이크를 굽는다고 상상해 보세요. 이전의 요리사들은 "소금을 쓰지 마세요"라고 말했습니다. 하지만 저자들은 "사실 소금, 설탕, 밀가루, 달걀, 우유, 그리고 11 가지 다른 특정 재료를 정확한 조합으로 피해야 합니다"라고 말했습니다. 그들은 피해야 할 15 가지 항목의 체크리스트를 제공했습니다. 당신의 3x3 기계가 이 15 가지 규칙을 모두 따른다면 안전합니다. 하나라도 어기면 취약해집니다.
결과: 그들은 존재하는 3x3 기계의 수와 실제로 안전한 것의 수를 세어 보았습니다. 그 결과 '안전한' 것들이 우리가 생각했던 것보다 훨씬 희귀하다는 것을 발견했습니다.

결론 요약

이 논문은 디지털 잠금장치를 위한 안전 검사관과 같습니다. 그들은 우리에게 다음과 같이 말했습니다:

Non-MDS 기계는 확실히 안전하지 않습니다. (MDS 를 사용해야 합니다.)
홀수 크기의 대칭 기계는 확실히 안전하지 않습니다. (대칭성을 원한다면 홀수 숫자를 사용하지 마세요.)
대부분의 원형 기계는 안전하지 않습니다. (크기가 매우 구체적이지 않는 한.)
3x3 기계의 경우, 약한 잠금장치를 짓지 않도록 보장하는 정확한 체크리스트가 여기 있습니다.

저자들은 새로운 잠금장치를 발명하지 않았습니다. 그들은 우리가 이미 구축하고 있는 잠금장치에 숨겨진 균열이 있는지 더 잘 확인할 수 있는 방법을 제공했을 뿐입니다.

기술적 요약: 관련 차분 암호분석에서의 선형 계층 분석

문제 제기
SPN 기반 블록 암호 (예: AES) 에서 선형 확산 계층은 일반적으로 최적의 분기 수와 고전적 차분 및 선형 암호분석에 대한 저항성을 보장하기 위해 최대 거리 분리 (MDS) 행렬을 사용하여 구현됩니다. 그러나 Daemen 과 Rijmen(2009) 및 Bardeh 와 Rijmen(2022) 의 최근 연구는 MDS 행렬이 여전히 '관련 차분 (related-differential)' 구조를 나타낼 수 있음을 밝혔습니다. 이러한 구조는 AES-128 에 대한 7 라운드 키 복구 공격과 같은 공격에 활용될 수 있는 관련 차분 특성을 구성할 수 있게 합니다. 이전 연구들은 특정 사례 (예: 4×4 순환 행렬, 3×3 자기역행렬) 에서 관련 차분을 식별해 왔으나, 어떤 선형 계층 구조가 본질적으로 이러한 차분을 피하거나 허용하는지에 대한 체계적인 이해는 아직 불완전한 상태입니다. 본 논문은 유한 체 위의 선형 계층이 관련 차분을 피하는 조건을 조사하여, 이러한 특정 암호분석 벡터에 본질적으로 저항적인 행렬 클래스를 식별하는 것을 목표로 합니다.

방법론
저자들은 $\mathbb{F}_{2^m}$ 특성 2 의 유한 체에 대한 이론적 대수적 접근법을 사용합니다. 방법론은 다음과 같습니다:

관련 차분 정의: Daemen 과 Rijmen 의 정의를 활용하여, 두 차분 $(u, Mu) $와$ (v, Mv) $가 모든 좌표에 대해$ x_i \cdot y_i \cdot (x_i \oplus y_i) = 0 $조건을 만족할 때 입력 쌍$ (u, v) $와 출력 쌍$ (Mu, Mv)$가 '관련'되어 있다고 정의합니다.
구조적 분석: 행렬 속성 (MDS 성질, 대칭성, 순환 구조) 과 비자명한 관련 차분 쌍의 존재 간의 관계를 조사합니다.
다항식 분해: 순환 행렬의 경우, 저자들은 행렬 연산을 몫환 $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$ 에서의 다항식 곱셈으로 매핑합니다. 지수의 모듈로 산술 (모듈로 2, 3, 4) 에 기반하여 변환 다항식을 분해하여 관련 출력 차분을 생성하는 특정 입력 차분 쌍을 구성합니다.
사례별 열거: $3 \times 3$ 경우의 경우, 저자들은 임의의 MDS 행렬을 대표 형태 $M = D_1 M_1 D_2$ (여기서 $D_i$ 는 대각 행렬이고 $M_1$ 은 특정 대표 행렬) 로 분해하는 방식을 활용합니다. 입력 차분 삼중항 $(u, v, u \oplus v)$ 의 모든 가능한 해밍 가중치 패턴을 체계적으로 분석하여 관련 차분의 부재에 대한 필요충분 대수적 조건을 유도합니다.

주요 기여 및 결과

MDS 속성의 필요성:
본 논문은 MDS 속성이 관련 차분을 피하기 위한 필수 조건임을 증명합니다. 구체적으로 정리 2는 모든 비-MDS 행렬이 적어도 하나의 비자명한 관련 차분 쌍을 허용함을 보여줍니다. 이는 저항적인 선형 계층에 대한 탐색 공간을 MDS 행렬 클래스로 엄격히 제한합니다.
대칭 행렬의 취약성:
저자들은 홀수 차원에서의 대칭성이 본질적인 취약점임을 확립합니다. 정리 4는 모든 홀수 차수 대칭 MDS 행렬이 관련 차분을 허용함을 증명합니다. 이 결과는 본질적으로 대칭적이므로 취약한 Type 2 Cauchy 기반 MDS 행렬과 홀수 차수 좌측 순환 행렬 (부록 2 및 3) 을 포함한 광범위한 구성들을 배제합니다.
순환 행렬의 취약성:
본 논문은 순환 행렬에 대한 포괄적인 특성을 제공합니다. 행렬 차수 $n$ 의 모듈로 속성을 분석함으로써, 저자들은 정리 5에서 차수가 $n$ 인 순환 MDS 행렬이 $n \not\equiv \pm 2 \pmod{12}$ 일 때 관련 차분을 허용함을 증명합니다. 이는 $3 \times 3$ 및 $4 \times 4$ 사례에 대한 이전 발견을 일반화하여 취약한 광범위한 차수 클래스를 식별합니다.
$3 \times 3$ 행렬의 완전한 특성화:
$3 \times 3$ 사례를 재검토하여 저자들은 완전한 대수적 특성을 유도합니다. 정리 7은 대표 $3 \times 3$ MDS 행렬의 매개변수에 대한 15 개의 필요충분 다항식 제약 조건의 명시적 집합을 제공합니다. 이 15 개 조건 중 어느 하나가 충족되면 해당 행렬은 관련 차분을 허용하며, 어느 것도 충족되지 않으면 행렬은 저항적입니다.
- 본 논문은 이전 특성화 (예: Otal 등) 가 불완전했다고 지적합니다.
- 이 특성을 사용하여 저자들은 다양한 유한 체 ( $\mathbb{F}_{2^m}$ ) 위의 관련 차분이 전혀 없는 $3 \times 3$ MDS 행렬의 정확한 수를 계산하였으며, 저항성 행렬 집합이 모든 MDS 행렬의 엄격한 부분집합임을 입증했습니다 (표 I).

의의 및 주장
본 논문은 관련 차분 암호분석에 저항하기 위한 구조적 전제조건에 대한 체계적인 조사를 제공한다고 주장합니다. 그 주요 의의는 다음과 같습니다:

한계 설정: MDS 속성만으로는 저항성이 불충분하며, 특정 구조적 속성 (홀수 차수 대칭성, 특정 순환 차수) 이 취약성을 보장함을 증명합니다.
설계 기준 정제: $3 \times 3$ 행렬에 대한 구체적이고 검증 가능한 15 개의 대수적 제약 조건 세트를 제공하여, 설계자가 이 차원에서 저항성 행렬을 포괄적으로 검증하거나 구성할 수 있게 합니다.
미래 구축 방향 제시: 비-MDS 행렬이 본질적으로 취약하며 많은 일반적인 대칭 구성이 실패한다는 점을 식별함으로써, 향후 연구가 비대칭 (또는 짝수 차수 대칭) 이면서 저항성을 위해 유도된 특정 대수적 제약 조건을 모두 만족하는 MDS 행렬을 구축하는 방향으로 이끌고 있습니다.

저자들은 $3 \times 3$ 사례가 완전히 특성화되었지만, 이러한 결과를 $4 \times 4$ 행렬로 확장하고 관련 차분이 없는 경량 효율적 MDS 행렬을 구축하는 것은 여전히 열린 과제로 남아 있다고 결론지었습니다. 또한 $n \equiv \pm 2 \pmod{12}$ 인 순환 행렬에 대한 미해결 사례는 향후 증명을 위한 가설로 제시된다고 덧붙였습니다.