SOPG: 자동회귀 신경망을 위한 탐색 기반 순서형 비밀번호 생성

1. 서론

비밀번호는 단순성과 유연성으로 인해 여전히 사용자 인증의 주요 수단으로 남아 있습니다. 이에 따라 비밀번호 추측은 공격적 보안 테스트(예: 침투 테스트, 비밀번호 복구)와 방어적 강도 평가 모두에 필수적인 사이버 보안 연구의 핵심 구성 요소입니다. 규칙 기반 공격부터 마르코프 체인 및 PCFG와 같은 통계 모델에 이르기까지 전통적인 방법들은 확장성과 적응성에 본질적인 한계를 지니고 있습니다.

딥러닝, 특히 GPT와 같은 자동회귀 신경망의 등장은 데이터에서 직접 복잡한 비밀번호 분포를 학습함으로써 패러다임 전환을 약속했습니다. 그러나 중요한 간과 사항은 생성 전략이었습니다. 표준 샘플링 방법(예: 무작위 샘플링, top-k)은 비밀번호를 무작위 순서로 생성하여 심각한 비효율성을 초래합니다: 높은 중복률과 공격 초기에 높은 확률(따라서 더 가능성 높은) 비밀번호를 우선시하지 못하는 문제입니다. 본 논문은 SOPG (탐색 기반 순서형 비밀번호 생성)을 소개합니다. 이는 자동회귀 모델이 확률의 대략적인 내림차순으로 비밀번호를 생성하도록 강제하여 비밀번호 추측 공격의 효율성을 극적으로 증가시키는 새로운 방법입니다.

2. 배경 및 관련 연구

2.1 비밀번호 추측 기술의 진화

비밀번호 추측은 뚜렷한 단계를 거쳐 진화해 왔습니다:

규칙 기반 및 사전 공격: 수동 규칙과 단어 목록에 의존했습니다. 전문가 지식에 크게 의존하며 새로운 패턴을 놓치기 쉬웠습니다.
통계 모델 (예: 마르코프, PCFG): 확률적 프레임워크를 도입했습니다. OMEN 및 FLA와 같은 모델은 성능 향상을 보였지만 일반화 및 긴 꼬리 분포에 어려움을 겪었습니다.
딥러닝 시대: PassGAN (GAN 기반), VAEPass (VAE 기반), PassGPT (GPT 기반)과 같은 모델들은 수동 특징 공학 없이 복잡한 고차원 비밀번호 분포를 모델링하기 위해 신경망을 활용합니다.

2.2 신경망 접근법

GPT와 같은 자동회귀 모델은 시퀀스의 확률을 토큰 단위로 모델링하기 때문에 비밀번호 생성에 특히 적합합니다: $P(password) = \prod_{t=1}^{T} P(c_t | c_1, ..., c_{t-1})$. 이를 통해 가변 길이 비밀번호 생성을 허용하고 문맥적 의존성을 효과적으로 포착합니다.

2.3 생성 순서 문제

저자들이 확인한 핵심 비효율성은 모델 능력이 아니라 생성 순서입니다. 학습된 모델에서 무작위 샘플링은 비밀번호의 가능성과 관계없이 비밀번호를 생성합니다. 성공적인 사전 공격을 위해서는 높은 확률의 비밀번호를 먼저 생성하는 것이 최우선입니다. SOPG는 무작위 샘플링을 지시적 탐색 알고리즘으로 대체하여 이 문제를 해결합니다.

3. SOPG 방법론

3.1 핵심 원리

SOPG는 비밀번호 생성을 확률적 과정에서 최우선 탐색 문제로 변환합니다. 목표는 가능한 비밀번호 시퀀스 공간(트리)을 추정 확률이 높은 순서에서 낮은 순서로 시퀀스를 출력하는 순서로 탐색하는 것입니다.

3.2 탐색 알고리즘

이 방법은 우선순위 큐(예: 빔 탐색 변형 또는 확률적 확장 알고리즘)를 사용합니다. 각 단계에서 누적 확률이 가장 높은 부분 시퀀스가 하나의 토큰으로 확장됩니다. 부분 시퀀스 $s = (c_1, ..., c_k)$의 확률은 모델에 의해 추정됩니다: $P(s) = \prod_{t=1}^{k} P(c_t | c_1, ..., c_{t-1})$. 탐색은 종료 조건(예: 시퀀스 종료 토큰)이 충족될 때까지 계속되어 완전한 비밀번호를 출력합니다. 다음 비밀번호는 큐에서 다음으로 우수한 부분 시퀀스에서 탐색을 재개하여 생성됩니다.

시퀀스 확장을 위한 핵심 공식: 노드(부분 시퀀스)를 확장할 때, 새로운 후보 시퀀스 $s'$ (토큰 $c$를 $s$에 추가하여 형성됨)의 우선순위는 결합 확률입니다: $Priority(s') = P(s) \cdot P(c | s)$. 탐색은 항상 현재 가장 높은 우선순위를 가진 노드를 확장합니다.

3.3 자동회귀 모델과의 통합

SOPG는 모델에 구애받지 않습니다. 사전 학습된 자동회귀 모델(예: GPT 변형)을 순수히 확률 추정기 $P(c_t | context)$로 사용합니다. 탐색 알고리즘은 이 추정기에 대한 호출을 조정하여 시퀀스 공간을 체계적으로 탐색합니다.

4. 기술적 구현: SOPGesGPT

4.1 모델 아키텍처

저자들은 GPT 아키텍처(예: Transformer 디코더 블록)를 기반으로 구축되고 유출된 비밀번호 코퍼스에서 학습된 비밀번호 추측 모델인 SOPGesGPT를 구현합니다. 이 모델은 실제 비밀번호의 문자/바이트 수준 분포를 학습합니다.

4.2 확률 추정 및 탐색

생성 중에 SOPGesGPT는 단순히 샘플링하지 않습니다. 대신, 주어진 부분 시퀀스에 대해 다음 토큰에 대한 전체 어휘 목록의 확률 분포를 계산합니다. SOPG 알고리즘은 이러한 확률을 사용하여 우선순위 큐에서 탐색 경계를 순위 매기고 관리합니다.

주요 성능 지표 (개념적)

커버리지 비율
테스트 세트에서 해독된 목표 비밀번호의 백분율.

유효 비율
생성된 고유하고 유효한 비밀번호의 비율.

추론 효율성
주어진 커버리지에 도달하는 데 필요한 모델 호출/추측 횟수.

5. 실험 결과 및 분석

5.1 실험 설정

실험은 실제 유출된 비밀번호 데이터 세트(예: RockYou)에서 수행되었습니다. 모델은 데이터의 일부에 대해 학습되었으며, 그 추측 성능은 보류된 테스트 세트에 대해 평가되었습니다.

5.2 무작위 샘플링과의 비교

결과: 동일한 기본 GPT 모델에서의 SOPG 대 표준 무작위 샘플링.

중복 제거: SOPG는 본질적으로 고유한 비밀번호를 생성합니다; 무작위 샘플링은 많은 중복을 생성합니다.
순서 효율성: 동일한 커버리지 비율(예: 10%)을 달성하기 위해 SOPG는 무작위 샘플링보다 훨씬 적은 추론 횟수와 훨씬 적은 총 비밀번호 생성만을 필요로 했습니다. 이는 SOPG의 순서형 생성이 가능성 높은 비밀번호를 훨씬 더 일찍 "명중"시키기 때문입니다.

차트 함의: 커버리지 대 추측 횟수 플롯은 SOPG 곡선이 초기에 급격히 상승하는 반면, 무작위 샘플링 곡선은 느리고 선형적으로 상승하여 우수한 공격 효율성을 보여줄 것입니다.

5.3 최신 기술 대비 벤치마크

결과: SOPGesGPT는 OMEN, FLA, PassGAN, VAEPass, PassGPT와 단일 사이트 테스트에서 비교되었습니다.

커버리지 비율: SOPGesGPT는 35.06%의 커버리지 비율을 달성했습니다.
상대적 개선: 이는 OMEN 대비 254%, FLA 대비 298%, PassGAN 대비 421%, VAEPass 대비 380%, PassGPT 대비 81% 증가를 나타냅니다.
유효 비율: SOPGesGPT는 또한 비밀번호 생성의 유효 비율에서도 선두를 달렸습니다.

차트 함의: 모든 모델의 커버리지 비율을 비교하는 막대 차트는 SOPGesGPT의 막대가 다른 모든 막대보다 극적으로 높게 나타나 시각적으로 그 우수한 성능을 확인시켜 줄 것입니다.

5.4 주요 성능 지표

실험은 SOPG가 신경망 비밀번호 추측의 핵심 비효율성을 해결한다는 것을 확실히 입증합니다. 성능 향상은 주로 더 나은 기본 모델(비록 GPT가 강력하지만)에서 오는 것이 아니라, 모든 추측이 가능한 한 효과적이도록 보장하는 순서형 생성 전략에서 비롯됩니다.

6. 분석 프레임워크 및 사례 연구

시나리오: 보안 회사가 기업 시스템의 비밀번호 강도를 감사하는 임무를 맡았습니다. 그들은 학습된 자동회귀 비밀번호 모델을 보유하고 있습니다.

전통적 접근법 (무작위 샘플링): 감사관은 1천만 개의 비밀번호를 생성합니다. 무작위성과 중복으로 인해 높은 확률의 비밀번호 "회사이름2023!"은 5백만 번의 추측 후에야 나타날 수 있어 시간과 계산 자원을 낭비합니다.

SOPG 강화 접근법: SOPG와 동일한 모델을 사용하여 감사관은 확률 내림차순으로 비밀번호를 생성합니다. "회사이름2023!" 및 기타 일반적인 패턴들은 처음 10만 번의 추측 내에 나타납니다. 감사는 취약성에 대한 결정적인 평가(예: "사용자 비밀번호의 30%가 100만 번의 추측으로 해독 가능")에 훨씬 더 빠르고 적은 계산으로 도달합니다.

프레임워크 요점: SOPG는 확률 모델을 고수익 공격 도구로 변환하기 위한 체계적이고 효율적인 프레임워크를 제공하여 각 모델 추론에 대한 투자 수익을 극대화합니다.

7. 향후 응용 및 연구 방향

능동적 비밀번호 강도 검사기: 실시간 비밀번호 생성 시스템에 통합하여 SOPG 기반 공격을 시뮬레이션하고 약한 비밀번호를 즉시 거부합니다.
향상된 보안 교육: SOPG 생성 목록을 사용하여 시스템 관리자를 위한 더 현실적인 "일반 비밀번호" 블랙리스트를 생성합니다.
적대적 머신러닝: SOPG의 효율성 연구는 순서형 지능형 추측에 더 강력한 비밀번호 정책 또는 해싱 알고리즘 설계와 같은 더 나은 방어로 이어질 수 있습니다.
비밀번호 외부: SOPG 원리는 가능성에 따른 순서형 출력이 유익한 다른 자동회귀 생성 작업에 적용될 수 있습니다. 예를 들어 소프트웨어 퍼징을 위한 테스트 케이스 생성 또는 신약 개발에서 화합물 공간 탐색 등이 있습니다.
탐색 효율성 연구: 더 큰 비밀번호 공간을 처리하기 위해 탐색 알고리즘 자체의 추가 최적화(예: 더 정교한 휴리스틱 사용, 병렬화).

8. 참고문헌

M. Jin, J. Ye, R. Shen, H. Lu, "Search-based Ordered Password Generation of Autoregressive Neural Networks," Manuscript Under Review.
J. T. G. H. M. Weir, "Using Probabilistic Context-Free Grammars for Password Guessing," in Proceedings of the 5th USENIX conference on Offensive technologies, 2009.
A. Radford, et al., "Language Models are Unsupervised Multitask Learners," OpenAI Blog, 2019. (GPT 기초 논문)
B. Hitaj, et al., "PassGAN: A Deep Learning Approach for Password Guessing," in Proceedings of the 16th International Conference on Applied Cryptography and Network Security, 2019.
M. Pasquini, et al., "PassGPT: Password Modeling and (Guessed)Strength Evaluation with Large Language Models," arXiv preprint arXiv:2306.01745, 2023.
P. G. Kelley, et al., "Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms," in IEEE Symposium on Security and Privacy, 2012.

9. 원문 분석 및 전문가 통찰

핵심 통찰: 이 논문의 탁월함은 새로운 신경망 아키텍처를 발명하는 데 있지 않고, 강력한 AI 모델의 적용에 존재하는 중요하지만 간과된 체계적 결함을 식별하고 정밀하게 수정하는 데 있습니다. 이는 비밀번호 추측을 위해 생성 순서가 단순한 구현 세부 사항이 아니라, 이론적으로 강력한 모델과 실질적으로 효율적인 무기 사이의 결정적 요소임을 인식합니다. 이는 순수 모델 능력(PassGAN에서 PassGPT로의 진행에서 볼 수 있듯이 수익 체감이 있는 군비 경쟁)에서 생성 전략 최적화로 연구 초점을 이동시킵니다. 이는 더 알고리즘적이고 근본적인 개선입니다.

논리적 흐름: 주장은 매우 설득력이 있습니다: 1) 자동회귀 모델은 비밀번호 분포 학습에 탁월합니다. 2) 이 분포에서의 무작위 샘플링은 공격에 매우 비효율적입니다. 3) 따라서 지능적으로 샘플링해야 합니다. SOPG의 해결책—생성을 확률 트리에 대한 최우선 탐색으로 취급하는 것—은 이 논리를 알고리즘으로 우아하고 직접적으로 변환한 것입니다. 이는 모델의 핵심 역량(확률 추정)을 활용하여 자체 탐색을 안내함으로써 효율성의 선순환을 창출합니다.

강점과 결점: 강점은 부인할 수 없습니다: 동시대 모델 대비 81-421%의 개선은 성숙한 분야에서 압도적인 승리이며, 이 개념의 최고 중요성을 입증합니다. 이 방법은 또한 우아하게 모델에 구애받지 않아 기존 자동회귀 비밀번호 모델에 대한 플러그인 업그레이드가 됩니다. 그러나 간접적으로 인정된 잠재적 결점은 비밀번호당 계산 오버헤드입니다. 우선순위 큐를 유지하고 쿼리하는 것은 단일 샘플링 단계보다 더 비쌉니다. 논문은 커버리지에 필요한 총 비밀번호 수의 대규모 감소를 보여줌으로써 이에 정당하게 반박하며, 트레이드오프가 압도적으로 긍정적임을 보여줍니다. 실제 공격자에게 더 깊은 결점은 모델의 출력 분포에 대한 직접적인 확률 접근을 가정한다는 점입니다. 이는 고급 해싱(Argon2와 같은)이나 페퍼를 사용하는 강화된 시스템에서는 성립하지 않을 수 있습니다. 2012년 Kelley 등의 추측 알고리즘 시뮬레이션 연구에서 언급된 바와 같이, 실제 위협 모델은 복잡합니다.

실행 가능한 통찰: 사이버 보안 전문가들에게 이 논문은 명령입니다: AI 모델에서 순진한 샘플링을 사용하는 모든 비밀번호 강도 평가를 즉시 중단하십시오. 도구들은 현실적인 위험 평가를 제공하기 위해 SOPG와 유사한 순서형 생성을 통합해야 합니다. 연구자들에게 경로는 명확합니다: 다음 개척지는 하이브리드 접근법입니다. SOPG의 순서형 탐색을 GAN의 모드 붕괴 회피 이점 또는 VAE의 잠재 공간 탐색과 결합하십시오. 더 나아가, 대규모 언어 모델(LLM)이 멀티모달이 됨에 따라, 향후 "비밀번호 추측"은 소셜 미디어에서 수집된 사용자 페르소나 데이터를 기반으로 그럴듯한 패스프레이즈를 생성하는 것을 포함할 수 있으며, SOPG가 생성을 안내할 것입니다. 방어 커뮤니티는 이에 상응하여 대응해야 하며, NIST 지침에서 권장하는 바와 같이 구성 규칙을 넘어 비밀번호 관리자 사용과 FIDO2/WebAuthn 표준의 광범위한 채택을 촉진하여 가장 효율적인 추측 공격조차도 쓸모없게 만들어야 합니다.

목차