기술 요약: 일반화된 PNE 프레임워크: 싱코페이션(Syncopation)을 통한 ChaCha의 확장

1. 문제 정의

스트림 암호인 ChaCha, 특히 256비트 변형은 TLS, SSH, QUIC와 같은 실제 프로토콜에서 널리 사용되고 있다. 이러한 광범위한 사용에도 불구하고, 라운드 수가 감소된 ChaCha의 보안 마진은 집중적인 암호해독 연구의 대상이 되어 왔다. 본 연구 이전에는 256비트 ChaCha의 7라운드에 대한 가장 효과적인 키 복구 공격들이 (시간 복잡도가 종종 $2^{220}$을 초과하는) 7라운드 또는 7.25라운드에 국한되어 있었으며, 단일 키 설정(single-key setting)에서 7.5라운드에 대해 무차별 대입 공격($2^{256}$)보다 빠른 공격이 성공적으로 입증된 사례는 없었다. 또한, 관련 키 설정(related-key setting)에서의 8라운드 변형(ChaCha8)의 보안성 역시 효율적인 공격 측면에서 거의 탐구되지 않은 상태였다.

ChaCha의 차분 암호해독(differential cryptanalysis)에서의 핵심 과제는 식별된 확률적 중립 비트(Probabilistic Neutral Bits, PNB)의 수와 역방향 근사(backward approximation)의 상관관계 사이의 트레이드오프에 있다. 전통적인 방법들은 높은 상관관계를 유지하면서 동시에 대량의 PNB 세트를 찾는 데 어려움을 겪으며, 이는 미트 인 디 미들(meet-in-the-middle) 공격의 효율성을 제한한다. 또한, "강한 키(strong keys)"(적절한 IV가 차분 특성을 만족시키지 못하는 키)에 대한 이전의 분석들은 모든 경우에 대해 포괄적인 이론적 정당성이 부족했다.

2. 방법론

본 논문은 PNB를 기반으로 한 정교한 차분 암호해독 프레임워크를 도입하고, 이를 PNE(Probabilistic Neutral Expressions) 기반 프레임워크로 일반화한다. 이 방법론은 세 가지 주요 기술적 기둥으로 구성된다:

2.1 PNB를 위한 싱코페이션(Syncopation) 기법

저자들은 다수의 PNB를 찾는 것과 높은 상관관계를 유지하는 것 사이의 모순을 해결하기 위해 "싱코페이션"을 도입한다.

• 개념: 역방향 근사 함수 $f$를 $f = f_1 \circ f_0$로 분해한다. 이 기법은 특정 비-PNB 비트(제한된 비트, restricted bits)에 대한 제약을 적용하여, 첫 번째 부분($f_0$)의 출력이 PNB(싱코페이션 비트)로부터 독립적이 되도록 보장한다.
• 메커니즘: ARX 구조 내의 모듈러 덧셈 및 뺄셈의 특성을 활용하여, 저자들은 캐리 전파(carry propagation)를 제어할 수 있는 조건을 도출한다. 이를 통해 특정 세그먼트의 출력이 알려진 공개 값과 비-PNB에 의해서만 결정되도록 하여, PNB에 대한 의존성을 효과적으로 "싱코페이션(엇박자화)"한다.
• 결과: 이 기법은 역방향 근사의 상관관계를 크게 증폭시킨다. 저자들은 또한 수익성 있는 싱코페이션 세그먼트를 체계적으로 결정하기 위한 도구(Algorithm 1)와 최적의 조건부 PNB(CPNB) 세트를 구축하기 위한 그리디 알고리즘(Algorithm 2)을 제공한다.

2.2 일반화된 PNE 프레임워크

효율성을 더욱 향상시키기 위해, 본 논문은 PNB 개념을 **확률적 중립 표현식(Probabilistic Neutral Expressions, PNE)**으로 일반화한다.

• 키 추측 전략: 원래의 키 비트를 직접 추측하는 대신, 암호의 구조(예: 회전 및 XOR을 포함한 선형 결합)에 맞게 설계된 가역 함수 $H$를 사용하여 등가 키 $H(K)$를 추측한다.
• 캐리 보존(Carry-Preserving) 기법: 모듈러 덧셈을 위한 새로운 기법이 도입된다. 공개 데이터에 선형 조건을 부과함으로써, 알려지지 않은 키 비트(PNB)를 알지 못하더라도 모듈러 덧셈의 캐리 벡터를 결정할 수 있다. 이는 비선형 연산을 단순화하여, 근사가 알려지지 않은 키 부분을 무시하면서도 높은 상관관계를 유지할 수 있게 한다.
• 통합: 이 프레임워크를 통해, 특히 후반 라운드나 상태 행렬의 특정 대각선에서 전통적인 PNB가 희소한 시나리오에서도 더 많은 중립 요소(PNE)를 발견할 수 있다.

2.3 정교화된 순방향 차분 분석(Forward Differential Analysis)

본 논문은 ChaCha의 첫 번째 라운드를 지배하는 차분 방정식에 대한 심도 있는 이론적 분석을 제공한다.

• 강한 키 분석: 저자들은 (IV가 차분을 만족시키지 못하는) "강한 키"의 존재에 대한 포괄적인 이론적 설명을 제공하며, 이는 기존 연구가 두 가지 경우만을 다루었던 것과 달리 내부 상태 변수의 8가지 모든 케이스를 다룬다. 저자들은 약 29.6875%의 키가 강한 키임을 증 proves한다.
• 효율적인 쌍 생성: 차분 방정식을 분석함으로써, 저자들은 차분 제약을 만족시키기 위해 플립(flip)할 수 있는 특정 IV 비트들을 식별하여, 옳은 쌍(right pairs)을 찾는 데 필요한 데이터 복잡도를 줄인다.

3. 주요 기여

1. 싱코페이션 기법: ARX 구조적 특성을 활용하여 역방향 근사 상관관계를 증폭시키는 새로운 방법으로, 더 효율적인 PNB 선택을 가능하게 한다.
2. 일반화된 PNE 프레임back Framework: 등가 키 표현식과 캐리 보존 기법을 사용하는 PNB 방식의 확장으로, 더 적은 비트 추측과 더 높은 상관관계를 가능하게 한다.
3. 이론적 완전성: 첫 번째 라운드의 모든 차분 케이스에 대한 강한 키 확률의 완전한 이론적 도출을 제공하여, 기존의 부분적인 분석을 수정하고 확장하였다.
4. 새로운 공격 결과:
   • 256비트 ChaCha: 무차별 대입보다 빠른 7.5라운드에 대한 최초의 키 복구 공격($2^{254.6}$ 시간 복잡도). 7 및 7.25 라운드에 대한 개선된 공격(복잡도 감소).
   • ChaCha8 (관련 키): 256비트 ChaCha8(8라운드)에 대한 최초의 관련 키 공격으로, 고정된 차이를 가진 키 쌍을 사용할 때 $2^{253.3}$의 시간 복잡도를 입증하였다.
   • 128비트 ChaCha: 6.5 라운드에 대한 개선된 공격 및 7 라운드(마지막 회전을 제외한 $7\ll$)에 대한 새로운 공격.

4. 결과

본 논문은 다음과 같은 구체적인 공격 복잡도(시간/데이터)를 제시한다:

• 256비트 ChaCha7:
  • $2^{210.3}$ 시간 / $2^{103.3}$ 데이터 (89개의 CPNB 사용 시).
  • $2^{216.9}$ 시간 / $2^{68.9}$ 데이터 (74개의 CPNB 사용 시).
  • 5라운드 DL 구별자(distinguisher)에 싱코페이션을 적용하여 $2^{187.2}$ 시간 / $2^{108.2}$ 데이터로 개선됨.
• 256비트 ChaCha7.25:
  • $2^{220.0}$ 시간 / $2^{109}$ 데이터.
• 256비트 ChaCha7.5:
  • $2^{254.6}$ 시간 / $2^{125.3}$ 데이터. 이는 무차별 대입($2^{256}$)보다 빠른 7.5 라운드에 대한 최초의 공격이다.
• 256비트 ChaCha8 (관련 키):
  • $2^{253.3}$ 시간 / $2^{99.2}$ 데이터. 이는 관련 키 모델에서 256비트 보안 주장을 무너뜨린다.
• 128비트 ChaCha:
  • ChaCha6.5: $2^{114.3}$ 시간 / $2^{100.3}$ 데이터.
  • ChaCha7$\ll$: $2^{122.9}$ 시간 / $2^{108.8}$ 데이터.

5라운드 및 6라운드 ChaCha(64개의 미지 키 비트)에 대한 실험적 검증을 통해, 이론적 상관관계 개선 및 성공 확률(5라운드 약 70%, 6라운드 62.5-71.4%)을 확인하였다.

5. 의의 및 주장

본 논문은 ChaCha의 보안 분석에서 "작지만 어려운 진전"을 이루었다고 주장한다. 주요 의의는 다음과 같다:

• 7.5라운드 장벽 돌파: 256비트 ChaCha 7.5 라운드에 대해 무차별 대입 탐색보다 효율적인 키 복구 공격을 최초로 입증하였다.
• ChaCha8에 대한 최초의 관련 키 공격: 특정 차이를 가진 키 쌍이 허용될 경우 ChaCha8이 256비트 보안을 달성하지 못함을 보여줌으로써, 8라운드 변형의 실질적인 보안 가설에 도전하였다.
• 방법론적 발전: 싱코페이션 기법과 일반화된 PNE 프레임워크(캐리 보존 및 새로운 키 추측 전략 포함)의 도입은 Salsa나 Chaskey와 같은 다른 설계에도 적용 가능한, ARX 기반 암호 분석을 위한 더욱 강력한 도구 세트를 제공한다.

저자들은 이러한 공격들이 실제 배포되는 20라운드 ChaCha를 위협하지는 않지만, 라운드 수가 감소된 변형들의 보안 마진을 유의미하게 좁히며 8라운드 관련 키 설정에서의 이론적 취약점을 강조한다고 명시적으로 밝히고 있다.