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

목차

1. 서론

비밀번호는 여전히 가장 보편적인 사용자 인증 방법입니다. 이에 따라 비밀번호 추측은 공격적 보안 테스트(크래킹)와 방어적 강도 평가를 뒷받침하는 사이버 보안 연구의 핵심 구성 요소입니다. 규칙 기반 열거부터 마르코프 체인 및 PCFG와 같은 통계 모델에 이르는 전통적인 방법은 효율성과 다양성에 본질적인 한계가 있습니다. 딥러닝, 특히 자동회귀 신경망의 등장은 패러다임 전환을 약속했습니다. 그러나 결정적인 병목 현상이 지속되었습니다: 표준 무작위 샘플링 생성 방법입니다. 이는 중복 비밀번호를 초래하고, 더 해롭게는 생성 순서가 무작위가 되어 공격자가 방대하고 비효율적인 목록을 일일이 살펴봐야 합니다. 본 논문은 SOPG(탐색 기반 순차적 비밀번호 생성)를 소개합니다. 이는 자동회귀 비밀번호 추측 모델이 비밀번호를 확률의 대략적인 내림차순으로 생성하도록 설계된 새로운 방법으로, 공격 효율을 극적으로 증가시킵니다.

2. 배경 및 관련 연구

2.1 비밀번호 추측의 진화

비밀번호 추측은 뚜렷한 단계를 거쳐 진화해 왔습니다. 초기 방법은 사전 공격과 수동으로 제작된 변형 규칙(예: John the Ripper)에 의존했으며, 이는 경험적이고 경험에 의존적이었습니다. 대규모 비밀번호 유출(예: 2009년 RockYou)의 확산은 데이터 기반 통계적 접근법을 가능하게 했습니다. 마르코프 모델(Weir 외, 2009)과 확률적 문맥 자유 문법(PCFG)(Ma 외, 2014)은 생성에 대한 보다 체계적이고 확률 기반의 프레임워크를 제공했지만, 과적합의 위험이 있었고 비밀번호 구조의 복잡한 장거리 의존성을 모델링할 능력이 부족했습니다.

2.2 신경망 접근법

딥러닝 모델, 특히 PassGAN(Hitaj 외, 2017)과 같은 생성적 적대 신경망(GAN) 및 LSTM 또는 GPT 아키텍처 기반의 자동회귀 모델은 데이터에서 직접 비밀번호의 확률 분포를 학습합니다. 이들은 매우 다양하고 현실적인 비밀번호를 생성할 수 있습니다. 그러나 일반적으로 각 생성 단계에서 학습된 분포로부터 무작위 샘플링(예: 다항 샘플링)을 사용합니다. 이 근본적인 과정은 완전한 비밀번호 확률의 전역적 순위와 무관하여 SOPG가 해결하고자 하는 비효율성을 초래합니다.

3. SOPG 방법론

3.1 핵심 개념

SOPG는 비밀번호 생성을 확률적 샘플링 문제에서 유도된 탐색 문제로 재구성합니다. 다음 문자를 무작위로 선택하는 대신, 탐색 알고리즘(빔 서치 또는 최상 우선 탐색의 변종일 가능성 있음)을 사용하여 가능한 비밀번호 후속 조합의 공간을 탐색하고, 더 높은 추정 확률을 가진 완전한 비밀번호로 이어지는 경로를 우선시합니다. 목표는 $P(비밀번호|모델)$에 따른 진정한 내림차순 정렬에 가깝게 비밀번호 목록을 출력 순서로 제공하는 것입니다.

3.2 탐색 알고리즘

PDF 초록은 구체적인 알고리즘을 자세히 설명하지 않지만, 설명된 동작은 후보 비밀번호 접두사의 우선순위 큐를 유지하는 방법을 시사합니다. 각 단계에서 가장 유망한 접두사(가장 높은 누적 확률)를 확장하여 신경망에 다음 문자 분포를 질의하고 새로운 후보를 생성합니다. 비밀번호 공간의 고확률 영역을 먼저 체계적으로 탐색함으로써 가장 가능성 높은 비밀번호를 조기에 생성하고 본질적으로 중복을 방지합니다.

3.3 SOPGesGPT 모델

저자들은 GPT 기반 아키텍처에 자신들의 방법을 구현하여 SOPGesGPT를 생성합니다. GPT 모델(예: 디코더 전용 트랜스포머)은 유출된 비밀번호 데이터셋에서 시퀀스의 다음 문자를 예측하도록 학습됩니다. SOPG는 그런 다음 이 학습된 모델 위에 생성/추론 방법으로 적용되어 표준 샘플링을 대체합니다.

4. 기술적 세부사항 및 수학적 공식화

자동회귀 모델은 비밀번호 $\mathbf{x} = (x_1, x_2, ..., x_T)$의 확률을 조건부 확률의 곱으로 정의합니다: $$P(\mathbf{x}) = \prod_{t=1}^{T} P(x_t | x_1, ..., x_{t-1})$$ 여기서 $x_t$는 위치 $t$의 문자이고, $T$는 비밀번호 길이입니다. 표준 샘플링은 $x_t \sim P(\cdot | x_1, ..., x_{t-1})$을 선택합니다.

SOPG는 개념적으로 $P(\mathbf{x})$가 감소하는 순서로 시퀀스 $\mathbf{x}$를 찾고 출력하는 것을 목표로 합니다. 이는 노드가 접두사이고, 에지 비용이 $-\log P(x_t | 접두사)$와 관련 있으며, 목표는 총 비용이 증가하는 순서(즉, 확률이 감소하는 순서)로 경로(비밀번호)를 열거하는 트리에서의 최단 경로 탐색 문제로 볼 수 있습니다. 균일 비용 탐색(UCS) 또는 그 제한된 변종인, 큰 빔 너비와 동적 가지치기를 사용한 빔 서치와 같은 알고리즘이 이 근사적 순서를 달성할 수 있습니다. 핵심은 탐색의 최전선이 현재 경로의 확률 점수에 의해 우선순위가 매겨진다는 점입니다.

5. 실험 결과 및 분석

5.1 무작위 샘플링과의 비교

논문은 동일한 기본 모델에서 SOPG와 표준 무작위 샘플링을 비교하는 설득력 있는 결과를 제시합니다. 주요 발견 사항:

• 중복 제로: SOPG는 고유한 목록을 생성하는 반면, 무작위 샘플링은 많은 반복을 생성하여 계산 노력을 낭비합니다.
• 우수한 공격 효율성: 동일한 커버 비율(테스트 세트에서 크래킹된 비밀번호의 백분율)을 달성하기 위해 SOPG는 훨씬 적은 모델 추론이 필요하고 훨씬 작은 총 목록을 생성합니다. 이는 실제 시나리오에서 더 빠른 비밀번호 크래킹으로 직접 이어집니다.

5.2 최신 기술 대비 벤치마크

SOPGesGPT는 주요 비밀번호 추측 모델인 OMEN(마르코프), FLA, PassGAN(GAN), VAEPass(VAE) 및 동시대의 PassGPT와 비교 벤치마크를 수행했습니다. 단일 사이트 테스트에서:

• 커버 비율: SOPGesGPT는 35.06%를 달성하여 OMEN 대비 254%, FLA 대비 298%, PassGAN 대비 421%, VAEPass 대비 380%, PassGPT 대비 81% 향상되었습니다.
• 유효 비율: 논문은 또한 "유효 비율"에서도 선두를 주장하며, 이는 SOPG의 주요 강점인 조기 생성된 비밀번호의 품질 또는 적중률과 관련된 지표일 가능성이 있습니다.

이는 성능에 있어서 생성 방법(SOPG)이 모델 아키텍처만큼 중요하다는 것을 보여줍니다.

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

비밀번호 추측 모델 평가 프레임워크:

1. 모델 아키텍처 및 학습: 기본 신경망은 무엇인가?(GAN, VAE, 자동회귀 트랜스포머) 어떻게 학습되는가?
2. 생성 방법: 학습된 모델에서 비밀번호가 어떻게 생성되는가? (예: 무작위 샘플링, 빔 서치, SOPG). 이는 논문의 핵심 초점입니다.
3. 순서화 및 효율성: 이 방법이 유용한 순서(확률 내림차순)로 비밀번호를 생성하는가? 계산/추측 효율성은 어떠한가?
4. 다양성 및 중복: 새로운 비밀번호를 생성하는가 아니면 많은 중복을 생성하는가?
5. 벤치마크 성능: 표준 데이터셋(예: RockYou)에서의 커버 비율, 유효 비율 및 속도.

비코드 사례 연구: 동일한 학습된 GPT 비밀번호 모델을 사용하는 두 공격자, 앨리스와 밥을 고려해 보십시오. 앨리스는 표준 무작위 샘플링을 사용합니다. 밥은 SOPG를 사용합니다. 1000개의 비밀번호 테스트 세트를 크래킹하기 위해 앨리스의 소프트웨어는 350개를 크래킹하기 위해 1000만 개의 추측을 생성해야 할 수 있으며, 그 중 30%가 중복입니다. 밥의 SOPG 기반 소프트웨어는 동일한 350개를 크래킹하기 위해 최적의 순서로 단 100만 개의 고유 추측만 생성할 수 있습니다. 밥의 공격은 자원 효율성이 10배 더 높고 더 빠르게 완료됩니다.

7. 적용 전망 및 향후 방향

직접적인 적용 분야:

• 능동적 비밀번호 강도 테스트: 보안 팀은 SOPG가 강화된 모델을 사용하여 가장 가능성 높은 공격 벡터를 먼저 생성함으로써 제안된 비밀번호 정책을 더 효율적으로 감사할 수 있습니다.
• 포렌식 비밀번호 복구: 합법적인 비밀번호 복구 도구는 SOPG를 통합하여 제한된 시간/계산 예산 내에서 성공률을 높일 수 있습니다.

향후 연구 방향:

• 하이브리드 모델: SOPG의 순차적 생성과 다른 아키텍처의 강점 결합(예: 대규모 언어 모델의 의미적 지식 통합).
• 적응형/온라인 SOPG: 부분적 공격 결과로부터의 피드백을 기반으로 실시간으로 탐색 전략 수정.
• 방어적 대응책: SOPG와 같은 순차적, 확률 기반 공격에 특별히 강인한 새로운 비밀번호 해싱 또는 저장 기술 연구.
• 비밀번호 이상의 적용: 순차적 생성 패러다임을 피싱 URL 또는 악성코드 변종 생성과 같은 다른 보안 영역에 적용.

8. 참고문헌

1. Weir, M., Aggarwal, S., Medeiros, B., & Glodek, B. (2009). Password Cracking Using Probabilistic Context-Free Grammars. In IEEE Symposium on Security and Privacy.
2. Ma, J., Yang, W., Luo, M., & Li, N. (2014). A Study of Probabilistic Password Models. In IEEE Symposium on Security and Privacy.
3. Hitaj, B., Gasti, P., Ateniese, G., & Perez-Cruz, F. (2017). PassGAN: A Deep Learning Approach for Password Guessing. In International Conference on Applied Cryptography and Network Security.
4. Goodfellow, I., et al. (2014). Generative Adversarial Nets. Advances in Neural Information Processing Systems.
5. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners. OpenAI Blog.
6. Melicher, W., et al. (2016). Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks. In USENIX Security Symposium.

9. 원문 분석 및 전문가 논평