Every keyed DNA operation is affine: algebraic limits of DNA diffusion layers in image encryption

기술 요약: "모든 키 기반 DNA 연산은 아핀(affine)이다: 이미지 암호화에서 DNA 확산 계층의 대수적 한계"

문제 정의
15년 이상 이미지 암호화 방식들은 카오스 시스템과 결합된 DNA 코딩을 활용해 왔다. 광범위한 통계적 평가(엔트로피, 히스토그램 등)에도 불구하고, 이러한 방식들은 놀라울 정도로 유사한 대수적 공격에 의해 반복적으로 무너져 왔다. 기존 문헌들은 $4! = 24$개의 가능한 인코딩 규칙을 단순한 옵션 목록으로 취급해 왔으나, 이 숫자가 아핀 군 $AGL(2, 2)$의 차수와 일치한다는 사실을 인식하지 못했다. 결과적으로, DNA 확산 계층의 근본적인 대수적 약점, 즉 비선형성의 결여가 간과되어 왔다. 본 논문은 구조적 질문을 다룬다: DNA 설계 공간 내에서 도달 가능한 대수적 차수는 무엇이며, 왜 이전의 암호 해독들이 일관되게 성공했는가?

방법론
저자들은 특정 스킴에 국한된 암호 해독이 아닌 구조적 대수 분석을 채택한다. 본 연구는 출판된 구성들을 반영하는 다음과 같은 작업 가설에 기초한다:

1. 알파벳: 계층은 4개 기호 알파벳($\Sigma = \{A, C, G, T\}$)에서 작동하며, 이는 $\mathbb{F}_2^2$와 동일시된다.
2. 연산: 확산은 $4 \times 4$ 연산 테이블을 통해 기호별로 수행된다.
3. 복호 가능성: 연산은 첫 번째 인자에 대해 역원이 존재해야 한다(고정된 키에 대한 전단사 함수).
4. 균형성: 체인 구조에서 연산은 두 번째 인자에 대해 균형을 이루어야 한다(고고정된 평문에 대한 전단사 함수).

방법론은 다음을 포함한다:

• 군론적 증명: 모든 전단사 함수의 성질을 결정하기 위해 대칭군 $Sym(\Sigma)$의 크기를 아핀 군 $AGL(2, 2)$와 비교한다.
• 전수 조사: 331,776개의 허용 가능한 연산 테이블과 576개의 라틴 방격(Latin square) 연산을 기계적으로 검증한다(역원 및 균형 조건 충족).
• 대수적 지표: 모든 허용 가능한 연산에 대해 대수적 차수(algebraic degree), 차분 균일도(differential uniformity, DU), 비선형성(nonlinearity, NL)을 계산한다.
• 비교 분석: 최근의 "체인형(chained)" 설계(현재 블록이 이전 블록에 의존하는 구조)를 평가하고, 제로 비용 대체 연산을 제안한다.
• 코퍼스 분석: 분야 내 채택 현황을 평가하기 위해 154개의 문헌을 서지학적으로 검토한다.

주요 기여

1. 불가능성 정리 (정리 1): 본 논문은 모든 복호 가능한 키 기반 DNA 연산은 아핀임을 증명한다. $|AGL(2, 2)| = 24 = |Sym(\Sigma)|$이므로, DNA 알파벳의 모든 전단사 함수는 $\mathbb{F}_2$ 상의 아핀 맵이다. 결과적으로 인코딩 규칙, 키 스케줄, 라운드의 모든 합성(composition)은 대수적 차수가 1인 아핀 변환이 된다. 이는 왜 이전의 공격들(예: [4, 13, 14])이 성공했는지를 설명한다. 그들은 특정 결함을 이용한 것이 아니라 설계 공간 자체의 내재적 구조를 공략한 것이다.

2. 천장 정리 (정리 6): 저자들은 유일한 탈출 경로인 두 개의 평문 의존 피연산자 사용(체이닝)을 조사한다. 이 경우에도 대수적 차수는 2로 제한됨을 증명한다. 나아가, 모든 576개의 허용 가능한 연산(차수가 4인 라틴 방격)에 대해 차분 균일도는 최악의 값($DU=16$)에 고정되어 있으며, 비선형성은 0($NL=0$)이다. 어떤 연산을 선택하더라도 이러한 지표를 개선할 수 없다.

3. 경계 정리 (정리 8): 장애물은 연산이 아닌 알파벳 크의 특성임이 확인되었다. 본 논문은 $AGL(m, 2) = Sym(\Sigma_m)$이 $m \le 2$일 때만 성립함을 증명한다. 따라서 4글자 DNA 알파벳은 모든 전단사 함수가 아핀인 가장 큰 크기이다. 더 큰 알파벳(예: 8글자)은 풍부한 비아핀 치환을 허용한다.

4. 체인 설계의 진단: 체인 구조를 사용하는 네 가지 최신 스킴을 분석한다. 두 가지 결함을 식별하였다:

   • 아핀 메뉴: 두 개의 피연산자를 사용하더라도 연산 메뉴의 절반(XOR, XNOR)은 여전히 아핀이므로, 체인의 비선형성은 운에 맡겨지게 된다.
   • 결합 법칙의 붕괴: 결합 법칙이 성립하는 연산(예: $Z_4$ 덧셈)을 사용하면 체인이 접두사 합(prefix sum)으로 붕괴되어, $2^k - 1$개의 이미지 독립적 선형 구조를 축적하게 된다.

5. 제로 비용 대체: 특정 비결합적, 차수-2 연산을 제안한다. 이는 동일한 테이블 크기와 복호 비용을 유지하면서도, 체인의 대수적 차수가 길이에 따라 증가하도록 보장하며 선형 구조를 상수로 제한하여 기존 결합 설계의 결함을 제거한다.

6. 실험적 검증: 표준 통계 팩키지(엔트로피, NPCR, UACI)가 이러한 대수적 차이를 감지하지 못함을 입증한다. 문헌에서 보고된 "아발란체 효과(avalanche effect)"는 확산 계층 자체의 결과가 아니라 이미지 해시 시딩(이미지 해시가 키스트림 전체를 변경함)에 의한 결과임을 보여준다. 시드가 고정될 경우, 해당 계층의 확산은 미미하다.

결과

• 아핀성: 모든 331,776개의 허용 가능한 키 기반 연산은 아핀이다(차수 1).
• 체이닝의 한계: 두 개의 평문 피연산자를 사용하는 경우에도 최대 차수는 2이며, 모든 허용 가능한 연산에 대해 $DU=16, NL=0$이다.
• 선형 구조: 결합적 체이닝은 $2^k - 1$개의 선형 구조를 축적하는 반면, 제안된 비결합적 대체 연산은 이를 상수로 3으로 유지한다.
• 통계적 맹목성: 세 가지 변체(기존 방식, 제한된 방식, 대체 방식)는 대수적 특성이 매우 다름에도 불구하고 통계적으로 구분이 불가능하다.
• 코퍼스 격차: 122개의 설계 논문을 검토한 결과, "대수적 차수(algebraic degree)", "차분 균일도(differential uniformity)", "대수적 약점(algebraic weakness)"이라는 용어는 단 한 번도 등장하지 않았다. 지식은 참고 문헌에는 존재하지만 설계 커뮤니티에는 도달하지 못했다.

의의 및 주장
본 논문은 대수적 차수가 DNA 기반 이미지 암호화 평가에서 누락된 핵심 지표라고 주장한다. 저자들은 다음과 같이 주장한다:

• DNA 방식의 반복적인 실패는 우연이 아니라 4글자 알파벳의 대수적 구조에 따른 필연적 결과이다.
• 표준 통계 팩키지는 이러한 구조적 약점을 탐지하기에 불충분하다.
• 제안된 "인증서"(차수, DU, NL 계산)는 계산 비용이 매우 저렴하며(수 초 내 완료), 평가 표에 반드시 포함되어야 한다.
• 분야는 4글자 알파벳 내에서 연산을 제한하거나 교체하거나(개선), 비선형성을 달성하기 위해 4글자 알파벳을 완전히 포기해야 한다.

저자들은 제안된 대체 연산이 "수리가 아닌 개선"이라고 명시하며 겸손한 태도를 취한다. 이는 4글자 알파벳의 근본적 한계(차수 $\le 2, DU=16, NL=0$)를 극복하기 위해서는 알파벳 크기를 변경하지 않는 한 불가능하기 때문이다. 이 연구는 새로운 공격 벡터를 제시하기보다는 설계 측면에서의 진단 역할을 수행한다.