Stringology-Based Cryptanalysis for EChaCha20 Stream Cipher

1. 연구 배경 및 문제 정의 (Problem)

• 배경: ChaCha20 은 TLS 1.3 및 IoT 통신 등 보안이 중요한 분야에서 사실상의 표준으로 널리 사용되고 있습니다. 이를 개선하기 위해 상태 행렬을 4×4 에서 6×6 으로 확장하고, 회전 (Rotation) 상수를 추가한 EChaCha20이 제안되었습니다.
• 문제점: 기존 암호 분석은 NIST SP 800-22 와 같은 통계적 무작위성 테스트 (STS) 나 전통적인 차분 분석에 의존합니다. 그러나 이러한 방법들은 비트 수준의 전체적인 무작위성은 평가할 수 있으나, ARX(Add-Rotate-XOR) 구조의 내부적인 **국소적 약점 (Localized Weaknesses)**이나 단어 (Word) 단위 패턴을 탐지하는 데 한계가 있을 수 있습니다.
• 연구 목적: EChaCha20 의 개선 사항 (확장된 상태 행렬, 수정된 Quarter-Round Function) 이 미세한 키스트림 패턴, 회전 편향 (Rotational Bias), 또는 부분적 충돌을 유발하여 통계적 판별자 (Distinguisher) 로 악용될 수 있는지 체계적으로 검증하는 것입니다.

2. 방법론 (Methodology)

이 논문은 문자열학 (Stringology) 기법을 암호 분석에 적용하는 새로운 프레임워크를 제안합니다.

• 핵심 알고리즘:
  • KMP (Knuth-Morris-Pratt) 및 Boyer-Moore (BM) 알고리즘을 32 비트 워드 단위의 암호 분석에 맞게 적응 (Adaptation) 시켰습니다.
  • 기존 문자열 매칭 알고리즘은 텍스트 처리에 사용되지만, 이를 EChaCha20 의 32 비트 워드 구조에 맞춰 수정하여 **m-gram 패턴 (8, 16, 32 비트)**의 빈도 분포를 분석했습니다.
• 하이브리드 접근법:
  • KMP 의 결정론적 백트래킹과 BM 의 휴리스틱 점프 (Skip) 기법을 결합한 하이브리드 알고리즘을 개발했습니다.
  • XOR 연산을 패턴 매칭 로직에 직접 통합하고, 32 비트 워드 정렬을 최적화하여 대규모 데이터 처리 효율을 높였습니다.
• 실험 설계:
  • 데이터셋: 100 만 개 (1 Million) 의 키스트림 블록을 생성하여 대규모 분석을 수행했습니다.
  • 시나리오: Known Plaintext Environment (KPE) 와 Chosen Plaintext Environment (CPE) 를 가정하여 공격자의 능력을 모델링했습니다.
  • 분석 단계:
    1. 패턴 빈도 분석: KMP/BM 을 사용하여 비트열 수준의 반복 패턴 탐지.
    2. 차분 암호 분석 (Differential Cryptanalysis): 회전 차분 (Rotational Differential) 을 주입하여 Quarter-Round Function (QR-F) 의 확산 (Diffusion) 속도와 충돌 확률 측정.

3. 주요 기여 (Key Contributions)

1. 문자열학 기반 암호 분석 (SBC) 프레임워크 제안: ARX 기반 암호의 내부 구조에 정렬된 (Structurally-aligned) 32 비트 워드 단위로 패턴을 탐지하는 새로운 분석 기법을 정립했습니다.
2. 알고리즘 최적화: KMP 와 BM 알고리즘을 암호 분석에 특화시켜, 기존 브루트포스 방식보다 6.2 배 빠른 속도로 대규모 키스트림을 스캔할 수 있도록 개선했습니다.
3. EChaCha20 의 구조적 보안 평가: EChaCha20 의 6×6 상태 행렬과 추가 회전 상수 (4 비트, 2 비트) 가 실제 확산 속도와 무작위성에 미치는 영향을 실증적으로 검증했습니다.

4. 실험 결과 (Results)

• 의사난수성 (Pseudorandomness):
  • 16 비트 및 32 비트 수준: EChaCha20 은 강력한 의사난수성을 유지하며, 통계적으로 유의미한 패턴 반복이나 편향이 발견되지 않았습니다.
  • 8 비트 수준: 고정 키 (Fixed-key) 환경에서 초기 블록의 일부 8 비트 패턴에서 미세한 편향이 관찰되었으나, 이는 가변 키 환경에서는 사라지며 암호의 구조적 결함이라기보다는 초기 상태 초기화의 영향으로 판단되었습니다.
• 회전 차분 분석 및 확산 (Diffusion):
  • 충돌 감소: QR-F 1 회 실행 시 약 $2^{-19.2}$의 충돌 확률이 관찰되었으나, 2 회 실행 후에는 $2^{-24}$로 급격히 감소했습니다.
  • 완전 확산: 3 회 라운드 이후에는 100 만 번의 실험에서 충돌이 전혀 관측되지 않았습니다. 이는 ChaCha20 보다 한 라운드 더 빠른 확산 속도를 보여줍니다.
  • 눈사태 효과 (Avalanche Effect): 2 라운드 이후 비트 플립 확률이 이상적인 0.5 에 수렴하여 균일한 확산이 이루어짐을 확인했습니다.
• 성능: 하이브리드 KMP-BM 알고리즘은 초당 3.6 GB 의 처리 속도를 달성하여 기존 BM(3.2 GB/s) 보다 12.5% 빠르고, 정밀도 (Precision) 는 0.97 로 매우 높았습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 보안성 입증: EChaCha20 은 기존 ChaCha20 대비 확장된 상태 크기와 추가 회전 상수로 인해 회전 차분 공격에 대한 저항성이 강화되었으며, 3 라운드 이내에 완전한 상태 확산을 달성하여 높은 보안 마진을 가짐이 입증되었습니다.
• 분석 방법론의 혁신: 전통적인 통계 테스트만으로는 놓칠 수 있는 구조적 편향을 탐지하기 위해 문자열 매칭 알고리즘을 암호 분석에 적용하는 새로운 패러다임을 제시했습니다. 이는 ARX 암호의 평가 도구로서 SBC(Stringology-Based Cryptanalysis) 의 유효성을 입증합니다.
• 실용적 가치: 제안된 방법은 대규모 키스트림 데이터를 실시간에 가깝게 분석할 수 있어, 향후 암호 표준의 검증 및 새로운 스트림 암호 설계에 있어 강력한 보조 도구로 활용될 수 있습니다.

요약: 본 논문은 EChaCha20 이 기존 ChaCha20 의 한계를 극복하고 강력한 확산 속도와 무작위성을 유지하고 있음을, KMP 와 Boyer-Moore 알고리즘을 기반으로 한 대규모 문자열 패턴 분석을 통해 실증적으로 증명했습니다.