Symfrog-512: High-Capacity Sponge-Based AEAD Cipher (1024-bit State)

SymFrog-512: 고용량 스펀지 기반 AEAD 암호화 방식

1. 문제 정의 (Problem)

현대 암호학에서 스펀지 (Sponge) 구조와 듀플렉스 (Duplex) 구성은 SHA-3 및 Keccak 와 같은 표준을 통해 널리 사용되고 있습니다. 그러나 기존 방식들은 특정 용도에 맞춰 최적화되거나, 인증된 암호화 (AEAD) 시나리오에서保守적인 보안 마진 (Security Margin) 을 유지하기 위해 용량 (Capacity) 이 상대적으로 작거나 처리 속도 (Throughput) 와 보안성 간의 균형을 맞추는 데 한계가 있을 수 있습니다.
이 논문은 **1024 비트의 큰 상태 (State)**를 가진 커스텀 순열 (Permutation) 을 기반으로 하여, **높은 보안성 (Conservative Generic Bounds)**과 실용적인 구현 가능성을 동시에 달성하는 새로운 AEAD(Authenticated Encryption with Associated Data) 방식을 설계하는 것을 목표로 합니다.

2. 방법론 (Methodology)

SymFrog-512 는 다음과 같은 핵심 구성 요소와 설계 원칙을 기반으로 합니다.

• 커스텀 순열 (P1024-v2):
  • 상태 크기: 1024 비트 (16 개의 64 비트 워드).
  • 구조: 512 비트의 속도 (Rate, $r$) 와 512 비트의 용량 (Capacity, $c$) 으로 분할됨.
  • 라운드 함수: 24 라운드로 구성되며, 다음과 같은 계층을 포함합니다.
    1. AddRoundConstants: SHAKE256 으로 생성된 결정적 상수를 용량 부분에 XOR.
    2. Mixer: 상태의 절반 (Rate) 과 나머지 절반 (Capacity) 을 XOR 하여 상호 의존성 생성.
    3. Chi (비선형성): Keccak 와 유사한 비트 연산 기반의 비선형 변환 적용.
    4. Kick Layer: 홀수/짝수 인덱스 간의 곱셈 기반 혼합 (Oddness mask 사용) 및 비트 시프트.
    5. Rotate & Shuffle: 워드별 회전 (Rot) 및 고정된 P-box 를 통한 위치 변경.
• AEAD 모드 (Duplex Sponge):
  • 초기화: 1024 비트 키와 256 비트 논스 (Nonce) 를 사용하여 상태를 초기화한 후 순열 적용.
  • 데이터 흡수: 연관 데이터 (AD) 와 암호문을 64 바이트 블록 단위로 흡수하며, 각 블록마다 도메인 분리 바이트 (Domain Separation Bytes) 를 XOR 하여 위계적 구분.
  • 출력 변환 (Output Transform): 단순한 Rate 추출 대신, Rate 와 Capacity 를 혼합하고 SplitMix64 최종화 함수 (Finalizer) 를 적용하여 512 비트 키스트림을 생성. 이는 Capacity 의 확산을 강화하고 단순한 "Rate 읽기" 패턴을 방지.
  • 태깅: 암호화 후 256 비트 (32 바이트) 의 인증 태그를 생성하여 부가 데이터와 암호문의 무결성을 보장.
• 파일 형식 및 키 도출:
  • 152 바이트 헤더 (Magic, 버전, 플래그, Salt, Nonce, 길이 등) 와 32 바이트 헤더 인증 태그를 포함.
  • Argon2id 를 통한 패스워드 기반 키 도출 (KDF) 지원 또는 1024 비트 원시 키 직접 사용.
  • 헤더 태그 검증을 통해 잘못된 키 사용 시 조기 거부 (Early Reject) 가능.

3. 주요 기여 (Key Contributions)

1. 고용량 스펀지 설계: 512 비트의 큰 용량 ($c=512$) 을 채택하여 충돌 기반 공격에 대한 이론적 안전 마진을 극대화했습니다.
2. 새로운 1024 비트 순열 (P1024-v2): 64 비트 연산에 최적화된 곱셈 기반 'Kick' 레이어와 Chi 비선형성을 결합한 새로운 순열 구조를 제안했습니다.
3. 완전한 명세 및 구현: GitHub 에 공개된 참조 구현 코드와 완벽하게 일치하는 정밀한 명세서를 제공합니다.
4. 강건한 파일 포맷: 헤더 인증, 고정 시간 (Constant-time) 태그 비교, 원자적 파일 쓰기 (Atomic rename) 등을 포함한 실용적인 암호화 파일 형식을 정의했습니다.
5. 실증적 검증: 벤치마크, 확산 (Diffusion) 체크, 회귀 테스트 (Regression artifacts) 를 포함한 검증 데이터를 제공합니다.

4. 결과 (Results)

• 성능 (Benchmarks):
  • 순열 속도: 64 비트 환경에서 P1024-v2 순열 한 번 실행에 약 435.1 ns 소요 (200,000 회 반복).
  • 처리량: 64 MiB 버퍼 기준 AEAD 핵심 암호화 경로의 처리 속도는 131.7 MiB/s (I/O 및 키 도출 제외).
• 보안 분석 (Security Analysis):
  • 이상 순열 모델 (Ideal Permutation Model): P1024-v2 가 무작위 순열로 가정될 때, IND-CPA(기밀성) 및 INT-CTXT(인증성) 에 대한 보안 한계를 증명했습니다.
  • 충돌 확률: $q$번의 순열 호출에 대한 충돌 확률은 $q^2 / 2^{c+1}$로, $c=512$이므로 현실적인 작업 부하에서는 무시할 수 있는 수준입니다.
  • 태그 안전성: 256 비트 태그는 위조 시도당 $2^{-256}$의 확률로만 성공할 수 있습니다.
• 확산 특성 (Avalanche Effect):
  • 단일 비트 입력 차이가 24 라운드 후 상태 전체에 약 512 비트 (무작위 기대치) 로 확산되는 것을 확인했습니다. 평균 해밍 거리는 4 라운드 이후 무작위 수준에 근접합니다.
• 테스트 벡터: 다양한 길이 (0~1MB 이상) 의 평문에 대해 암호화/복호화 일관성을 검증하고 SHA-256 체크섬을 제공했습니다.

5. 의의 및 결론 (Significance)

SymFrog-512 는 보안성과 성능의 균형을 중시하는 실험적인 AEAD 설계입니다.

• 보안 마진: 512 비트의 큰 용량과 256 비트의 긴 태그/논스를 통해 미래의 컴퓨팅 파워 증가나 새로운 공격 기법에 대비한 '보수적 (Conservative)'인 안전성을 제공합니다.
• 구현 용이성: 복잡한 대수적 구조 대신 64 비트 정수 연산, 비트 시프트, XOR, 곱셈 등 현대 CPU 에서 효율적으로 실행 가능한 연산 위주로 설계되어 구현이 용이합니다.
• 실용성: Argon2id 지원, 안전한 파일 쓰기, 헤더 인증 등 실제 배포 환경에서 발생할 수 있는 오류와 공격을 방지하는 엔지니어링적 세부 사항이 철저히 반영되었습니다.

이 논문은 P1024-v2 순열에 대한 공개적인 암호 분석 (Cryptanalysis) 을 장려하며, 향후 더 정교한 보안 증명과 다양한 아키텍처에서의 성능 평가를 위한 기초를 마련했습니다.