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

목차

1. 서론

웹사이트 계정 및 비밀번호 유출 사고가 지속적으로 보고되면서 정보 보안과 비밀번호 보안의 중요성이 더욱 부각되고 있습니다. 웹사이트 취약점도 한 원인이지만, 비밀번호 자체의 내재적 보안이 무엇보다 중요합니다. 일반적으로 발견되는 안전하지 않은 비밀번호 관행에는 키워드 기반 비밀번호, 흔히 쓰이는 구문 사용, 개인정보 포함, 비밀번호 재사용 등이 있습니다. 인공지능과 대규모 언어 모델의 발전은 공격자로 하여금 비밀번호를 더 효과적으로 추측할 수 있는 능력을 부여하고 있습니다.

본 연구는 암호학적으로 안전한 의사 난수 생성기(PRNG)를 기반으로 한 안전한 비밀번호 생성기를 제안합니다. 키 기반 해시 메시지 인증 코드(HMAC), 암호 기반 메시지 인증 코드(CMAC) 또는 KECCAK 메시지 인증 코드(KMAC)를 사용하여 PRNG를 구성하고, 이를 통해 생성된 안전한 난수를 비밀번호 생성에 활용합니다. 생성된 숫자의 난수성은 NIST SP 800-90B 표준에 따라 엔트로피 및 독립 동일 분포(IID) 테스트를 통해 검증됩니다.

주요 기여:

• 비밀번호 생성을 위한 HMAC, CMAC, KMAC 기반 안전한 PRNG 구성.
• 다양한 문자 집합과 길이 제약 하에서의 비밀번호 보안 분석 및 AES-128/256과의 비교.
• NIST SP 800-90B 엔트로피 및 IID 테스트를 통한 실증적 검증.

2. 관련 연구

2.1. 선형 합동 생성기 기반 PRNG

C나 Java와 같은 언어에서 흔히 사용되는 LCG는 선형 점화 관계를 사용하여 일련의 숫자를 생성합니다. 시드 $k$가 주어지면 초기값 $f_0(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)$에 의해 생성됩니다. 그러나 LCG는 $f_{i-1}(k) \equiv (f_i(k) - c) \times a^{-1} \ (\text{mod} \ m)$를 사용하여 상태를 역산할 수 있기 때문에 안전하지 않으며, 시드와 전체 수열이 노출될 수 있습니다.

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

LCG의 취약점을 해결하기 위해 암호학적으로 안전한 PRNG가 필수적입니다. 본 논문은 NIST에서 권고하는 세 가지 구성을 중심으로 다룹니다.

2.2.1. HMAC 기반 PRNG

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

2.2.2. CMAC 기반 PRNG

보안성은 고급 암호 표준(AES)에 기반합니다. 키 $k$와 함께 암호 블록 체인(CBC) 모드를 사용하여 메시지 $M$을 블록 $M'_1, M'_2, ...$으로 분할합니다. 암호문은 반복적으로 계산됩니다: $c_{i+1} = AES(k, c_i \oplus M'_{i+1})$, 여기서 $c_0 = Pad0(0)$입니다. 최종 출력 $r_{cmac}$은 마지막 블록에서 도출됩니다.

2.2.3. KMAC 기반 PRNG

SHA-3 (KECCAK) 해시 함수를 기반으로 하는 KMAC은 가변 길이 출력을 제공하며, 양자내성암호 후보로 강력하게 고려됩니다. 그 구성은 유사한 인증 해싱 원칙을 따르며, 높은 보안성을 보장합니다.

2.3. 난수성 검증 방법

NIST SP 800-90B 표준은 난수 생성기의 품질을 평가하는 방법론을 제공합니다. 두 가지 핵심 측면이 평가됩니다:

• 엔트로피 검증: 데이터 내 비트당 예측 불가능성 또는 "난수성"을 측정합니다. 높은 엔트로피는 안전한 비밀번호에 중요합니다.
• IID (독립 동일 분포) 검증: 생성된 수열이 통계적으로 독립적이고 동일한 분포를 따르는지 테스트하여 패턴이나 상관관계가 존재하지 않음을 보장합니다.

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

시스템 아키텍처는 두 가지 주요 단계로 구성됩니다:

1. 안전한 난수 생성: 사용자는 선택적으로 해시 대상 메시지(TBHM)를 제공할 수 있습니다. 이는 암호화 키와 함께 선택된 안전한 PRNG(HMAC/CMAC/KMAC 기반)에 의해 처리되어 암호학적으로 강력한 난수 비트열을 생성합니다.
2. 비밀번호 생성: 난수 비트는 사용자 정의 또는 시스템 정의 문자 집합(예: 영숫자 및 기호 포함)에 지정된 길이로 매핑되어 최종 텍스트 기반 비밀번호를 생성합니다. 보안 강도는 문자 집합 크기와 비밀번호 길이가 제공하는 엔트로피를 고려하여 AES-128/256에 상대적으로 분석됩니다.

4. 실험 및 결과

4.1. 실험 환경

PRNG 출력의 난수성을 검증하기 위한 실험이 수행되었습니다. 테스트 스위트는 세 가지 PRNG 유형 모두에서 생성된 대량의 난수 샘플에 대해 NIST SP 800-90B 평가 절차(엔트로피 추정 및 IID 테스트)를 구현했습니다.

4.2. 난수성 검증 결과

결과 요약: 제안된 HMAC, CMAC 및 KMAC 기반 PRNG는 모두 NIST SP 800-90B 엔트로피 및 IID 검증 테스트를 성공적으로 통과했습니다. 생성된 수열은 진정한 난수성으로부터 통계적으로 유의미한 편차를 보이지 않아, 암호학적 비밀번호 생성에 적합함이 확인되었습니다.

차트 설명 (가상): 세 가지 PRNG 유형에 대한 최소 엔트로피 추정치(비트당 비트)를 NIST 통과 기준선과 비교하는 막대 그래프. 세 개의 막대 모두 기준선을 크게 상회하며, KMAC가 가장 높은 값을, HMAC-SHA3와 CMAC-AES256이 그 뒤를 따르는 것으로 나타날 것입니다.

4.3. 성능 분석

계산 효율성(예: 초당 생성 횟수)에 대한 비교 분석이 수행되었습니다. CMAC 기반 생성기(AES-NI 하드웨어 가속 사용)가 일반적으로 가장 높은 처리량을 보였으며, HMAC 기반(SHA2/SHA3)이 그 뒤를 이었고, KMAC는 계산 부하가 더 크지만 강력한 양자내성암호 보안 특성을 제공합니다.

5. 결론 및 향후 연구

본 연구는 암호학적으로 안전한 PRNG(HMAC, CMAC, KMAC)를 기반으로 구축된 안전한 비밀번호 생성기를 성공적으로 설계하고 검증했습니다. 생성된 비밀번호의 보안성은 이러한 기반 암호 프리미티브의 입증된 견고성과 PRNG 출력의 검증된 높은 난수성에서 비롯됩니다. 향후 연구에는 생성기를 브라우저 확장 프로그램이나 비밀번호 관리자에 통합하는 것, 비밀번호 외에 암호화 키 생성에의 활용 탐구, 그리고 전체 시스템에 대한 부채널 공격 저항성 분석 수행 등이 포함됩니다.

6. 원문 분석 및 전문가 코멘트

핵심 통찰: 이 논문은 사이버 보안의 영원한 약점인 인간이 선택한 비밀번호에 대한 실용적이고 공학 중심의 대응입니다. 그 핵심 가치는 새로운 암호학이 아니라, 특정하고 영향력 있는 사용 사례에 대해 기존의 검증된 구조(HMAC, CMAC, KMAC)의 올바른 적용과 엄격한 검증에 있습니다. 비밀번호 생성을 사용자의 머리에서 검증된 암호화 프로세스로 옮기는 것이 키 교환을 위해 대칭 암호에서 비대칭 암호로 전환하는 것과 유사한 근본적인 보안 업그레이드임을 올바르게 지적합니다.

논리적 흐름: 논리는 건전하며 고전적인 응용 연구 패턴을 따릅니다: 문제 정의(약한 비밀번호) → 일반적 해결책 비판(안전하지 않은 LCG) → 강력한 해결책 제안(CSPRNG 기반 생성기) → 실증적 검증(NIST 테스트). 검증 기준으로 NIST SP 800-90B를 선택한 것은 암호학적 맥락에서 난수성을 평가하는 사실상의 표준이므로 결과에 즉각적인 신뢰성을 부여한다는 점에서 훌륭합니다.

강점과 결점:
강점: 이 논문의 가장 큰 강점은 실용적 검증입니다. 많은 제안은 설계 단계에서 멈춥니다. 출력을 NIST의 엄격한 테스트에 적용함으로써 저자들은 채택에 중요한 구체적인 보안 증거를 제공합니다. SHA-3 기반 KMAC의 포함은 NIST의 진행 중인 양자내성암호 표준화 과정에서 언급된 바와 같이, 양자 컴퓨팅 이후 시대를 고려한 선견지명을 보여줍니다.
결점/누락: 분석이 다소 고립되어 있습니다. 중요한 결점은 시드 관리에 대한 논의가 부족하다는 점입니다. PRNG의 시드가 예측 가능하거나 유출되면 그 보안성은 무너집니다. 시스템은 HMAC/CMAC/KMAC를 위한 초기 암호화 키를 어떻게 생성, 저장, 보호합니까? 이는 알고리즘 자체만큼 중요합니다. 또한, 비밀번호 강도를 AES와 비교하는 것은 유용하지만, 기존 비밀번호 생성기(예: KeePass 또는 1Password) 및 그들의 기반 PRNG(예: ChaCha20 사용)와의 보다 직접적인 비교는 경쟁 우위에 대한 더 나은 맥락을 제공할 것입니다.

실행 가능한 통찰: 보안 실무자에게 이 논문은 청사진 역할을 합니다. 실행 1: 보안에 민감한 작업에 LCG 또는 유사한 비암호학적 RNG(예: `rand()`) 사용을 즉시 중단하십시오. 실행 2: 비밀번호 생성기를 구축하거나 감사할 때 주요 체크리스트 항목은 다음과 같아야 합니다: 1) CSPRNG 사용(NIST SP 800-90A의 HMAC_DRBG, CTR_DRBG 또는 여기의 구성), 2) NIST SP 800-90B 또는 Dieharder와 같은 스위트로 출력 검증, 3) 높은 엔트로피 소스(예: Linux의 `getrandom()`)로부터 강력한 시드 생성 구현. 논문은 2번에 성공적으로 초점을 맞추었지만, 1번과 3번은 전체 그림의 동등하게 중요한 부분입니다.

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

제안된 생성기의 보안성은 기반 암호 함수에 달려 있습니다. 주요 수학적 연산은 다음과 같습니다:

• HMAC: $r_{hmac}(k, M) = h((k \oplus opad) \ || \ h((k \oplus ipad) \ || \ M))$
• CMAC (CBC-MAC): $c_{i+1} = E(k, c_i \oplus M_{i+1})$, 여기서 $E$는 블록 암호(AES)입니다.
• 비밀번호 엔트로피: 생성된 비밀번호의 엔트로피 $H$는 $H = L \cdot \log_2(N)$이며, 여기서 $L$은 비밀번호 길이이고 $N$은 문자 집합의 크기입니다. 94자 집합에서 16자 비밀번호의 경우, $H \approx 16 \cdot \log_2(94) \approx 105$ 비트입니다.

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

사례 연구: 웹 애플리케이션 비밀번호 재설정 기능 감사
시나리오: 웹 앱이 "비밀번호 찾기"를 클릭한 사용자에게 임시 비밀번호를 생성합니다.
프레임워크 적용:

1. RNG 식별: 서버 측 코드를 검사합니다. `Math.random()` (JavaScript) 또는 PHP의 간단한 LCG를 발견하는 것은 치명적 결함입니다.
2. 엔트로피 소스 평가: PRNG는 어떻게 시드됩니까? 시스템 엔트로피(`/dev/urandom`, `CryptGenRandom`)를 사용합니까?
3. 제안된 솔루션에 매핑: 결함 있는 RNG를 이 논문의 설계를 구현한 모듈로 교체할 것을 권고합니다. 예를 들어, `os.urandom(32)`의 시드와 SHA256을 사용하는 `hmac.new`를 활용한 Python 함수입니다.
4. 출력 검증 (구현 후): 1,000,000개의 임시 비밀번호 샘플을 생성하고, 비트 스트림으로 변환한 후, NIST STS 스위트(관련 테스트 스위트)를 실행하여 난수성을 보장합니다.

이 프레임워크는 논문의 이론을 구체적인 감사 및 개선 체크리스트로 전환합니다.

9. 미래 응용 및 방향

핵심 기술은 사용자 비밀번호 생성 이상의 응용 분야를 가집니다:

• API 키 및 토큰 생성: 마이크로서비스 아키텍처를 위한 안전하고 무작위적인 API 키 및 세션 토큰 생성.
• 안전한 기본 자격 증명: IoT 디바이스 펌웨어에 이러한 생성기를 내장하여 각 디바이스마다 고유하고 강력한 기본 비밀번호를 생성함으로써 일반적인 기본값을 기반으로 한 광범위한 공격을 완화.
• 암호학적 시드 생성: 고품질 출력은 다른 암호 시스템의 시드 생성 또는 난스 및 초기화 벡터(IV) 생성에 사용될 수 있습니다.
• 비밀번호 관리자와의 통합: 이 알고리즘은 오픈소스 비밀번호 관리자의 핵심 엔진으로 통합되어 투명하고 감사 가능한 난수 소스를 제공할 수 있습니다.
• 양자내성암호 대비: NIST의 FIPS 202 및 SP 800-185 표준과 조화를 이루며, 양자 컴퓨팅 이후 시대를 대비하기 위해 KMAC 기반 생성기의 추가 탐구 및 최적화.

10. 참고문헌

1. M. Bishop, "Computer Security: Art and Science," Addison-Wesley, 2003.
2. NIST, "Special Publication 800-63B: Digital Identity Guidelines," 2017.
3. NIST, "Special Publication 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators," 2015.
4. NIST, "Special Publication 800-90B: Recommendation for the Entropy Sources Used for Random Bit Generation," 2018.
5. J. Kelsey, B. Schneier, D. Wagner, "Secure Applications of Low-Entropy Keys," ISW '97.
6. D. D. Hwang, B. B. Gupta, "A Study of Password Security and Its Implications," JIS, 2019.
7. NIST, "FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions," 2015.
8. NIST, "SP 800-185: SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash," 2016.
9. M. S. Turan, E. Barker, J. Kelsey, "Recommendation for Random Bit Generator (RBG) Constructions," NIST SP 800-90C, 2016.
10. P. G. Neumann, "Illustrative Risks to the Public in the Use of Computer Systems and Related Technology," ACM SIGSOFT, 1995.