의사 난수 생성기 기반 안전한 비밀번호 생성기

1. 서론

본 연구는 지속적으로 발생하는 비밀번호 유출 문제와 이로 인한 개인정보 노출 위험을 다룹니다. 웹사이트 보안도 중요하지만, 비밀번호 자체의 고유한 강도가 가장 중요합니다. 일반적인 취약점에는 키워드, 유행어, 사용자 정보 기반 비밀번호 및 비밀번호 재사용이 포함됩니다. AI 및 대규모 언어 모델의 발전은 공격자가 비밀번호를 더 효과적으로 추측할 수 있는 능력을 더욱 강화하고 있습니다.

이에 대응하여, 본 논문은 안전한 의사 난수 생성기(PRNG)를 기반으로 구축된 안전한 비밀번호 생성기를 제안합니다. 핵심 PRNG는 HMAC, CMAC 또는 KMAC과 같은 암호화 기본 요소를 사용하여 고품질 난수를 생성하도록 구성되며, 이 난수는 비밀번호 생성에 사용됩니다. 이 시스템은 프로세스의 시드(seed)로 사용할 선택적 사용자 입력(해시 대상 메시지, TBHM)을 허용합니다. 주요 기여 내용은 다음과 같습니다:

HMAC, CMAC 및 KMAC 기반 안전한 PRNG 구축.
다양한 문자 집합과 길이에서 생성된 비밀번호의 보안 분석 및 AES-128 및 AES-256과의 강도 비교.
NIST SP 800-90B를 사용한 난수성의 실증적 검증(엔트로피 및 독립 동일 분포(IID) 테스트 중심).

2. 관련 연구

2.1. 선형 합동 생성기 기반 의사 난수 생성기

일반적인 프로그래밍 언어(C, Java)는 선형 합동 생성기(LCG)를 사용합니다. 시드 $k$가 주어지면, 수열은 다음과 같이 생성됩니다: $f_0(k) \equiv a \oplus k \ (\text{mod} \ m)$ 및 $f_i(k) \equiv a \times f_{i-1}(k) + c \ (\text{mod} \ m)$. 이 방법은 상태를 역으로 추적할 수 있기 때문에 안전하지 않습니다: $f_{i-1}(k) \equiv (f_i(k) - c) \times a^{-1} \ (\text{mod} \ m)$, 이는 시드와 전체 수열을 노출시킵니다.

2.2. 안전한 의사 난수 생성기

안전한 PRNG는 NIST SP 800-108 Rev. 1에 명시된 암호화 기본 요소를 기반으로 합니다.

2.2.1. HMAC 기반

보안은 해시 함수(예: SHA2, SHA3)의 단방향 속성에 의존합니다. 키 $k$와 메시지 $M$에 대해 HMAC은 다음과 같이 계산됩니다: $r_{hmac}(k, M) = h((k \oplus opad) \ || \ h((k \oplus ipad) \ || \ M))$. 길이 $L$의 난수 비트스트림을 생성하기 위해 카운터 모드가 사용됩니다: $M_i = i \ || \ \text{KDF} \ || \ 0x00 \ || \ M \ || \ L$, 이는 출력 $r_{hmac,i}$를 생성합니다.

2.2.2. CMAC 기반

보안은 CBC 모드의 AES 블록 암호에 의존합니다. 메시지 $M$은 블록 $M'_1, M'_2, ...$으로 분할됩니다. 프로세스는 반복됩니다: $c_{i+1} = AES(k, c_i \oplus M'_{i+1})$, 여기서 $c_0 = Pad0(0)$. 최종 출력 $r_{cmac}$는 특정 패딩(Pad1) 후 마지막 암호 블록에서 도출됩니다.

2.2.3. KMAC 기반

KECCAK 스펀지 함수(SHA-3의 기반)를 활용하며, 결정론적 난수 비트 생성에 적합한 유연하고 강력한 MAC 기능을 제공합니다.

2.3. 난수성 검증 방법

본 논문은 엔트로피 소스 검증을 위한 사실상의 표준인 NIST SP 800-90B 프레임워크를 채택합니다. 여기에는 두 가지 중요한 검증 도구 모음이 포함됩니다:

엔트로피 평가: 생성된 비트스트림의 최소 엔트로피 양을 추정하여 예측 불가능성을 나타냅니다.
IID(독립 동일 분포) 테스트: 출력 비트가 통계적으로 독립적이고 동일한 분포를 따르는지 확인하기 위한 일련의 통계적 테스트(예: 카이제곱, 콜모고로프-스미르노프)입니다.

3. 제안하는 안전한 비밀번호 생성기

제안된 시스템 아키텍처는 단순하지만 강력합니다:

입력/시드: 선택적 사용자 제공 TBHM을 수락합니다. 제공된 경우 처리되며, 그렇지 않으면 시스템 생성 안전 시드가 사용됩니다.
안전한 PRNG 코어: TBHM/시드는 세 가지 암호화 PRNG 구성(HMAC 기반, CMAC 기반, KMAC 기반) 중 하나에 입력되어 암호학적으로 강력한 의사 난수 비트 시퀀스를 생성합니다.
비밀번호 구성: 난수 비트는 사용자 정의 또는 시스템 정의 문자 집합(예: 영숫자 + 기호)에 매핑되어 원하는 길이의 비밀번호를 생성합니다.

보안 분석: 본 논문은 생성된 비밀번호의 보안이 PRNG 출력의 엔트로피와 문자 집합의 크기에 직접적으로 달려 있다고 주장합니다. 비교 분석을 수행하여, PRNG 출력이 진정한 난수라고 가정할 때, 이 방법으로 생성된 94자 집합의 16자 비밀번호가 AES-128 또는 AES-256 키와 견줄 만하거나 그 이상의 무차별 대입 공격 저항성을 제공할 수 있음을 보여줍니다.

4. 실험 결과 및 분석

실험적 검증은 본 논문의 핵심 강점입니다.

엔트로피 검증: 세 가지 PRNG 유형(HMAC-SHA256, CMAC-AES256, KMAC256) 모두에서 생성된 난수 시퀀스는 NIST SP 800-90B 엔트로피 평가를 통과하여, 출력 비트당 이상값 1에 가까운 높은 최소 엔트로피를 보여주었습니다.
IID 검증: 시퀀스는 IID 테스트 도구 모음도 통과하여, 비트가 통계적으로 독립적이고 동일하게 분포되며 감지 가능한 패턴이나 편향이 없음을 확인했습니다.
성능: 주요 초점은 아니지만, 논문은 계산 효율성을 언급합니다. HMAC-SHA256과 KMAC256은 비슷한 속도를 보였으며, CMAC-AES256은 블록 암호 연산으로 인해 약간 느렸지만, 모두 비밀번호 생성에 실용적인 범위 내에 있었습니다.

차트 설명 (암시적): 막대 차트는 세 가지 PRNG 방법에 대한 최소 엔트로피 추정치(비트당 비트)를 이상값 1.0과 비교하는 데 효과적일 것입니다. 모든 막대는 1.0에 매우 가까울 것입니다. 두 번째 차트는 주요 IID 테스트(예: 카이제곱, 콜모고로프-스미르노프)의 p-값을 보여줄 수 있으며, 모든 값이 일반적인 유의성 임계값(예: 0.01)보다 훨씬 높아 통과를 나타냅니다.

5. 결론 및 향후 연구

본 연구는 암호화 PRNG를 기반으로 한 안전한 비밀번호 생성 프레임워크를 성공적으로 입증했습니다. 제안된 방법은 NIST 표준에 의해 엄격하게 검증된 충분한 난수성을 가진 비밀번호를 생성합니다. 향후 연구 방향은 다음과 같습니다:

브라우저 확장 프로그램이나 비밀번호 관리자에 생성기 통합.
장기적 보안을 보장하기 위해 PRNG의 기반으로 포스트-퀀텀 암호화 알고리즘(예: 격자, 해시 기반) 탐구.
표준 암호화 모델 하에서의 공식적 보안 증명 개발.

6. 독창적 분석 및 전문가 통찰

핵심 통찰: 이 논문은 새로운 암호화 기본 요소를 발명하는 것이 아니라, 검증된 기존 요소(HMAC, CMAC, KMAC)를 체계적으로 적용하고 검증하여 평범하지만 중요한 비밀번호 생성 문제를 해결하는 것입니다. 그 진정한 가치는 이론적 암호학과 실용적 보안 관행 사이의 간극을 메우고, 금표준인 NIST 테스트 도구 모음을 사용하여 그 출력이 목적에 적합함을 엄격하게 증명하는 데 있습니다.

논리적 흐름: 논증은 타당합니다: 1) 표준 LCG는 암호학적으로 깨졌습니다. 2) 암호화 MAC으로 구축된 안전한 PRNG는 입증 가능하게 견고합니다. 3) 따라서, 그러한 PRNG에서 파생된 비밀번호는 그 견고성을 상속받습니다. 4) 이 주장은 이론뿐만 아니라 엄격한 실증적 테스트(NIST SP 800-90B) 통과로 검증됩니다. 이러한 종단 간 검증은 많은 "안전한 비밀번호 생성기" 도구들이 부족한 부분입니다.

강점과 결점:
강점: 방법론적 엄격함은 칭찬할 만합니다. NIST SP 800-90B를 검증에 사용하는 것은 암호화 알고리즘이 CAVP(암호화 알고리즘 검증 프로그램)를 통해 검증되는 방식과 유사하게, 즉시 신뢰성을 높입니다. AES 키 강도와의 비교는 보안 팀에게 실용적이고 이해하기 쉬운 보안 지표입니다.
결점: 논문은 통제된 이상적인 환경에서 작동합니다. 초기 시드/TBHM이 충분한 엔트로피를 가진다고 가정하는데, 이는 실제 시스템에서 중요하면서도 종종 취약한 연결 고리입니다. "선택적" 사용자 입력은 양날의 검입니다; 약하고 예측 가능한 사용자 문구(예: "mypassword")는 전체 암호화 구성을 훼손할 수 있으며, 이 위험은 완전히 정량화되지 않았습니다. 더욱이, NIST의 2023년 리뷰 "Post-Quantum Cryptography: A Ten-Year Journey"에서 언급된 바와 같이, 이 분야는 양자 내성 알고리즘으로 이동하고 있습니다. 논문의 구성은 고전 컴퓨터에 대해 안전하지만, 장기적 양자 내성이 불확실한 SHA2/AES에 의존합니다.

실행 가능한 통찰: 보안 설계자에게 이 논문은 청사진을 제공합니다. 자체 PRNG를 만들지 마십시오. 확립된 암호화 구성을 빌딩 블록으로 사용하십시오. 더 중요한 것은 검증, 검증, 검증입니다. Linux Foundation의 CCC(공통 기준 인증) 노력과 같은 조직에서 강조하는 관행처럼, 중요한 난수 생성 시스템에 NIST 테스트와 같은 지속적인 엔트로피 검증을 통합하십시오. 제품 개발을 위해, 즉각적인 시사점은 시스템의 LCG 기반 비밀번호 생성을 안전하게 조달된 시드를 사용하는 KMAC 또는 HMAC-SHA256 기반 생성기로 교체하는 것입니다. 미래 대비 단계는 SHA-3/KECCAK 기반 설계(예: KMAC)로 프로토타이핑을 시작하고, 궁극적인 통합을 위해 NIST의 포스트-퀀텀 암호학 표준 발전을 모니터링하는 것입니다.

7. 기술적 상세 및 수학적 공식화

핵심 수학적 연산은 관련 연구(2장)에 정의되어 있습니다. 주요 공식은 다음과 같습니다:

LCG (안전하지 않음): $f_i(k) \equiv a \times f_{i-1}(k) + c \ (\text{mod} \ m)$
HMAC: $r_{hmac}(k, M) = h((k \oplus opad) \ || \ h((k \oplus ipad) \ || \ M))$
PRNG용 카운터 모드의 HMAC: $M_i = i \ || \ \text{KDF} \ || \ 0x00 \ || \ M \ || \ L$
CMAC (CBC-MAC) 반복: $c_{i+1} = AES(k, c_i \oplus M'_{i+1})$

비밀번호 생성은 난수 정수 $R$(PRNG 출력에서)을 문자 인덱스에 매핑합니다: $\text{index} = R \ \text{mod} \ |S|$, 여기서 $|S|$는 문자 집합의 크기입니다.

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

사례 연구: 레거시 시스템의 비밀번호 생성기 평가
시나리오: 레거시 웹 애플리케이션이 임시 사용자 비밀번호 생성에 수정된 LCG를 사용합니다. 보안 감사가 필요합니다.
프레임워크 적용:

PRNG 유형 식별: 소스 코드 검사. 발견: seed = (a * seed + c) % m; LCG 변형임을 확인.
암호화 보안 평가: LCG는 결정론적이고 역변환이 가능합니다. 공격자가 연속된 몇 개의 비밀번호를 획득하면 시드를 풀고 모든 미래 비밀번호를 예측할 수 있어, NIST SP 800-63B의 인증자 난수성 지침을 위반합니다.
논문의 방법을 사용한 개선안 제안:
- 시드 소스: 시스템 시간 시드를 CSPRNG(예: Linux의 /dev/urandom, Windows의 CryptGenRandom)로 교체.
- 코어 생성기: 논문의 설계에 따라 HMAC-SHA256 기반 PRNG 구현.
- 검증: 새 생성기에서 대규모 샘플(1,000,000 비트)을 생성하고 배포 전에 NIST STS(통계적 테스트 도구 모음) 또는 SP 800-90B의 엔트로피 추정기를 실행하여 난수성을 확인.

이 프레임워크는 평가를 "무작위로 보이는가?"에서 "표준화된 암호화 검증을 통과하는가?"로 전환합니다.

9. 미래 응용 및 발전 방향

이 원칙들은 사용자 비밀번호를 넘어 확장됩니다:

API 키 및 토큰 생성: 마이크로서비스 아키텍처 내에서 암호학적으로 무작위한 API 키 및 세션 토큰을 자동 생성.
안전한 기본 구성: IoT 장치나 소프트웨어 설치 프로그램에 이러한 생성기를 내장하여 고유하고 강력한 기본 관리자 비밀번호를 생성함으로써 광범위한 기본 자격 증명 공격을 완화.
포스트-퀀텀 진화: KMAC 기반 구성은 본질적으로 양자 내성으로 간주되는 SHA-3(KECCAK)을 기반으로 합니다. 이 생성기는 "암호화 민첩성" 시스템의 기초가 될 수 있습니다. 암호화 커뮤니티가 양자 컴퓨팅 시대를 준비함에 따라, 향후 연구는 CRYSTALS-Kyber 또는 해시 기반 서명과 같은 NIST 표준화 포스트-퀀텀 알고리즘 기반 PRNG를 통합해야 합니다.
비밀번호 관리자 및 SSO와의 통합: 이 생성기는 오픈 소스 비밀번호 관리자 또는 Single Sign-On (SSO) 시스템의 핵심 구성 요소가 되어 투명하게 감사 가능한 비밀번호 난수 소스를 제공할 수 있습니다.

10. 참고문헌

M. Bishop, “Computer Security: Art and Science”, Addison-Wesley, 2019.
NIST, “Special Publication 800-63B: Digital Identity Guidelines”, 2020.
NIST, “Special Publication 800-90B: Recommendation for the Entropy Sources Used for Random Bit Generation”, 2018.
NIST, “Special Publication 800-108 Rev. 1: Recommendation for Key Derivation Using Pseudorandom Functions”, 2022.
NIST, “FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions”, 2015.
J. Kelsey, B. Schneier, D. Wagner, “Secure Applications of Low-Entropy Keys”, Information Security Workshop, 1997.
M. Dworkin, “Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication”, NIST SP 800-38B, 2005.
NIST, “Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process”, 2022. [Online]. Available: https://csrc.nist.gov/projects/post-quantum-cryptography
Linux Foundation, “Common Criteria Certification and Open Source”, 2023. [Online]. Available: https://www.linuxfoundation.org/

목차