Structural Analysis of Cryptographic Sequences using Stringology-Based Fingerprinting

기술 요약: 문자열학 기반 지문 인식을 이용한 암호학적 시퀀스의 구조 분석

문제 제기
스트림 암호, 의사난수 생성기 (PRNG), 블록 암호 모드와 같은 암호학적 원시 함수들은 통계적으로 무작위 데이터와 구별할 수 없는 시퀀스를 생성하도록 설계되어 있습니다. 전통적인 평가는 빈도 분포, 런 길이, 엔트로피와 같은 전역적 속성을 검증하기 위해 NIST STS, TestU01 과 같은 통계적 무작위성 테스트 스위트에 크게 의존합니다. 그러나 이러한 테스트들은 이상적인 무작위성으로부터의 중대한 편차를 탐지하도록 주로 설계된 것이지, 근본적인 결정론적 생성기의 구체적인 구조적 행동을 특징화하기 위해 설계된 것은 아닙니다. 암호 알고리즘은 모듈러 덧셈, 비트 회전, 치환, XOR 과 같은 구조화된 내부 연산에 의존하므로, 순수 통계적 방법으로는 탐지하지 못하는 미묘한 구조적 특성을 도입할 수 있습니다. 따라서 이러한 시퀀스를 심볼 문자열로 해석하여 내부 패턴 구조를 분석하는 프레임워크가 필요합니다.

방법론: 문자열학 기반 지문 인식 (SBF) 프레임워크
본 논문은 구조적 패턴 통계를 추출하기 위해 암호학적 출력을 심볼 문자열로 취급하는 문자열학 기반 지문 인식 (SBF) 프레임워크를 제안합니다. 이 프레임워크는 다음과 같은 워크플로우로 작동합니다:

1. 시퀀스 변환: 암호학적 출력 (키스트림, 암호문) 은 이진 심볼 문자열 ($S \in \{0, 1\}^n$) 로 변환됩니다.
2. 패턴 추출: 슬라이딩 윈도우 분석을 사용하여 프레임워크는 여러 패턴 길이 ($m$) 에 걸쳐 부분 문자열 빈도 통계를 계산합니다. 이는 시퀀스 $S$ 내에서 패턴 $P$의 발생 횟수를 $f(P, S) = |\{i \mid S_{i:i+m-1} = P\}|$로 정의하여 세는 것입니다.
3. 특징 집계: 추출된 통계는 다음을 포착하는 특징 벡터로 집계됩니다:
   • 부분 문자열 빈도 분포: 패턴 발생의 정규화된 횟수.
   • 반복 패턴: 특정 부분 문자열이 반복되는 빈도.
   • 엔트로피 특성: 분포 균일성의 측정치.
4. 지문 구성: 이러한 특징들은 시퀀스 생성기의 구조적 행동을 특징화하는 컴팩트한 지문 벡터 ($X \in \mathbb{R}^d$) 로 매핑됩니다.
5. 비교 분석: 프레임워크는 패턴 편차 점수 ($D$) 와 패턴 엔트로피 ($H$) 와 같은 지표를 사용하여 암호 생성 시퀀스 (CGS) 의 지문을 균일 무작위 시퀀스 (URS) 와 비교합니다.

주요 기여

• SBF 프레임워크 도입: 문자열학 기법을 사용하여 암호학적 시퀀스의 구조적 분석을 위한 새로운 프레임워크를 소개합니다.
• 패턴 기반 지문 인식: 전역 무작위성 지표뿐만 아니라 부분 문자열 통계를 사용하여 시퀀스 생성기를 특징화하는 표현 방법을 제안합니다.
• 실험적 증명: 실험적 평가를 통해 문자열학 기반 패턴 분석이 암호학적 시퀀스와 균일 무작위 시퀀스 사이의 측정 가능한 구조적 차이를 드러낼 수 있음을 입증합니다.

실험 결과
평가에는 각각 2,048 비트 ($2^{12}$) 길이의 20,000 개의 시퀀스 (10,000 개의 CGS 및 10,000 개의 URS) 데이터셋이 사용되었습니다. 8, 16, 32 비트 길이의 부분 문자열 패턴이 분석되었습니다.

• 패턴 빈도: 암호 생성 시퀀스는 무작위 시퀀스에 비해 약간 더 높은 구조적 집중을 보였습니다 (예: 8 비트 패턴의 경우 정규화된 빈도가 0.54 대 0.50).
• 편차 점수: 패턴 편차 지표 ($D$) 는 모든 패턴 길이에 걸쳐 일관되게 0 이 아닌 점수 (0.09 에서 0.13 범위) 를 산출하여 두 소스 간의 측정 가능한 구조적 변이를 나타냈습니다.
• 엔트로피: 암호 생성 시퀀스는 무작위 시퀀스의 이론적 최대치에 비해 약간 낮은 엔트로피 값 (예: 8 비트 패턴의 경우 7.6 대 8.0) 을 보여 미미한 패턴 집중을 시사했습니다.
• 반복: 부분 문자열 반복 횟수에 대한 분석은 두 시퀀스 유형 간의 반복 행동에서 작지만 뚜렷한 차이를 드러냈습니다.

의의 및 주장
본 논문은 관찰된 구조적 신호가 작지만 측정 가능하며 균일 무작위 시퀀스에서 발견되는 노이즈와 구별된다고 주장합니다. 저자들은 이러한 발견이 실용적인 암호학적 취약점을 의미하지는 않는다고 강조합니다. 현대 알고리즘은 여전히 무작위 데이터와 계산적으로 구별할 수 없습니다. 대신, SBF 프레임워크의 의의는 추가적인 분석적 관점을 제공한다는 데 있습니다. 이는 전통적인 전역 통계 테스트를 보완하여 암호 생성기의 구조적 행동과 내부 규칙성을 연구하는 도구 역할을 합니다. 이 연구는 문자열학 기법을 암호 평가 워크플로우에 통합하면 시퀀스 생성기의 구조적 견고성에 대한 더 풍부한 이해를 제공할 수 있음을 시사합니다.