기대 엔트로피: 비밀번호 강도 평가를 위한 새로운 척도

1. 서론 및 배경

본 논문은 무작위 또는 무작위에 가까운 비밀번호의 강도를 추정하기 위해 설계된 새로운 척도인 기대 엔트로피를 소개합니다. 이 연구의 동기는 기존 비밀번호 강도 평가 도구들의 실용적 격차에서 비롯되었습니다. 고전적인 조합론 기반 공식(예: $\log_2(\text{문자 공간}^{\text{길이}})$)은 수십 비트 단위의 결과를 출력하는 반면, 산업 표준인 NIST 엔트로피 추정 도구는 0과 1 사이의 정규화된 최소 엔트로피 점수를 제공합니다. 이러한 불일치는 직접적인 비교와 직관적인 해석을 어렵게 만듭니다. 기대 엔트로피는 NIST 도구와 동일한 0-1 척도로 강도 추정치를 제공함으로써 이 격차를 메웁니다. 예를 들어, 값이 0.4라면 공격자가 비밀번호를 찾기 위해 가능한 총 추측 횟수의 최소 40%를 완전 탐색해야 함을 의미합니다.

본 연구는 물리 계층 보안 방법을 사용하여 Wi-Fi 디바이스 프로비저닝(ComPass 프로토콜)을 위한 강력한 대칭 비밀번호를 생성하는 데 초점을 맞춘 "PHY2APP" 프로젝트의 맥락에서 진행되었으며, 이는 견고하고 확장 가능한 강도 척도의 필요성을 강조합니다.

2. 다양한 엔트로피 정의

엔트로피는 무질서, 무작위성 또는 불확실성을 측정합니다. 다양한 정의가 비밀번호 강도에 다르게 적용됩니다.

2.1 최소 엔트로피

$H_{\infty} = -\log_2(\max(p_i))$로 정의되며, 여기서 $p_i$는 요소의 확률입니다. 이는 최악의 시나리오를 나타내며, 가장 가능성 높은 결과를 추측하는 난이도를 측정합니다. 이는 NIST 도구의 출력 기반이 됩니다.

2.2 섀넌 엔트로피

$H_1 = -\sum_{i=1}^{N} p_i \log_2 p_i$로 정의됩니다. 이는 정보 내용의 평균 측정치를 제공하지만, 비밀번호 길이와 공격자의 최적 전략을 무시하기 때문에 비밀번호 크래킹 맥락에서 실제 추측 난이도와 무관하다는 비판을 받습니다.

2.3 하틀리 엔트로피

$H_0 = \log_2 N$으로 정의되며, 분포의 크기(알파벳 크기)만 측정하고 문자 확률을 완전히 무시합니다.

2.4 추측 엔트로피

$G = \sum_{i=1}^{N} p_i \cdot i$로 정의되며, 여기서 추측은 확률이 감소하는 순서로 정렬됩니다. 이는 최적의 공격자가 필요로 하는 기대 추측 횟수를 측정합니다. 이는 실제 크래킹 시간과 더 직접적으로 관련이 있지만 정규화되지 않았습니다.

3. 기대 엔트로피

3.1 정의 및 공식화

기대 엔트로피는 추측 엔트로피 개념을 기반으로 하지만 [0, 1] 척도로 정규화됩니다. 핵심 아이디어는 단일 비밀번호의 구성을 통해 강도를 추정하는 것입니다. 이는 서로소인 문자 집합: 소문자 $L$ (|L|=26), 대문자 $U$ (26), 숫자 $D$ (10), 기호 $S$ (32)를 고려하며, 영어의 경우 총 크기 94의 전체 문자 공간 $K$를 형성합니다.

단일 비밀번호에 대한 완전한 수학적 유도는 제시된 발췌문에서 암시되지만 완전히 명시적이지는 않지만, 이 척도는 기본적으로 최적의 공격자가 필요로 하는 노력을 전체 탐색 공간에 상대적으로 정규화합니다. $G$가 추측 엔트로피이고 $N$이 가능한 비밀번호의 총 수(예: 전체 공간의 경우 $94^{\text{길이}}$)라면, 정규화된 형태는 개념적으로 $E \approx G / N_{eff}$와 관련될 수 있으며, 여기서 $N_{eff}$는 비밀번호 구성을 고려한 효과적인 탐색 공간 크기입니다.

3.2 해석 및 척도

핵심 혁신은 해석 가능한 척도입니다. 기대 엔트로피 값 $\alpha$ (여기서 $0 \le \alpha \le 1$)는 공격자가 비밀번호를 해독하기 위해 필요한 총 추측 횟수(최적 순서로)의 최소 $\alpha$ 비율을 수행해야 함을 의미합니다. 값 1은 공격자가 완전한 무차별 대입 탐색을 수행해야 하는 이상적인 무작위성을 나타냅니다. 이는 NIST 최소 엔트로피 척도와 직관적으로 일치하여 시스템 설계자의 비교 및 의사 결정을 용이하게 합니다.

4. 핵심 통찰 및 분석가 관점

핵심 통찰: Reaz와 Wunder는 단순히 또 다른 엔트로피 척도를 제안하는 것이 아닙니다. 그들은 보안 공학에서 중요한 사용성 및 해석 가능성 격차를 해결하려고 시도하고 있습니다. 실제 문제는 복잡성 측정법의 부재가 아니라, 조합론 도구가 "80비트!"라고 외치는 반면 NIST는 "0.7"이라고 속삭일 때 발생하는 인지적 마찰입니다. 기대 엔트로피는 실용적인 번역기 역할을 하여 암호화 강도를 통합된 대시보드에서 실행 가능한 확률적 위험 점수로 변환합니다.

논리적 흐름: 주장은 우아하게 단순합니다: 1) 기존 척도들은 서로 다른 행성(비트 대 정규화 점수)에 살고 있어 혼란을 초래합니다. 2) 추측 엔트로피($G$)는 공격자의 현실에 더 가깝지만 경계가 없습니다. 3) 따라서 $G$를 효과적인 탐색 공간에 상대적으로 정규화하여 공격자의 필요 노력 비율에 직접 매핑되는 0-1 점수를 생성합니다. 이는 이론적(NIST의 최소 엔트로피)과 실용적(비밀번호 크래커의 작업량)을 연결합니다.

강점과 결점: 강점은 우아한 단순성과 즉각적인 해석 가능성으로, 정책 입안자와 시스템 설계자에게는 축복입니다. 그러나 문제는 분포 가정에 있습니다. 이 척도의 정확도는 단일 비밀번호 샘플 내에서 문자의 확률 분포 $p_i$를 올바르게 모델링하는 데 크게 의존하며, 이는 악명 높게 어려운 통계적 문제입니다. 긴 비트 스트림을 테스트하는 NIST 도구와 달리, 이를 짧은 16자 비밀번호에 적용하려면 편향에 민감할 수 있는 견고한 추정기가 필요합니다. 발췌문에 따르면, 이 논문은 단일 인스턴스에 대한 이 추정 과정을 완전히 상세히 설명하지 않으며, 이것이 아킬레스건입니다.

실행 가능한 통찰: 보안 팀의 경우, 이 척도를 비밀번호 생성 API나 Active Directory 플러그인에 통합하여 실시간적이고 직관적인 강도 피드백("귀하의 비밀번호를 해독하려면 추측의 60%가 필요합니다")을 제공할 수 있습니다. 연구자들에게 다음 단계는 모델을 보정하기 위해 실제 크래킹 도구(예: Hashcat 또는 John the Ripper)에 대한 엄격하고 대규모의 경험적 검증이어야 합니다. 기대 엔트로피 0.8이 정말로 탐색 공간의 80%를 의미합니까? 이는 GAN이 다른 보안 영역을 공격하는 데 사용되는 방식과 유사하게, 적대적 AI 모델에 대한 증명이 필요합니다. 개념은 유망하지만, 그 운영 유용성은 기계 생성 비밀번호의 통제된 환경을 넘어 투명하고 동료 검증된 검증에 달려 있습니다.

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

개요된 개념을 기반으로, 비밀번호에 대한 기대 엔트로피 $H_E$를 개념적으로 구성할 수 있습니다. 길이 $l$의 비밀번호가 알파벳 $\mathcal{A}$에서 추출되고, 각 문자 위치에 대한 연관된 확률 분포(비밀번호 자체 또는 참조 코퍼스에서 추정될 수 있음)를 가진다고 가정합니다.

정렬된 확률 벡터: 크기 $N = |\mathcal{A}|^l$의 전체 비밀번호 공간에 대해, 이론적으로 모든 가능한 비밀번호를 선택될 확률(생성 모델에 따라)의 내림차순으로 정렬할 수 있습니다.
추측 엔트로피: 최적의 공격자에 대한 기대 추측 횟수는 $G = \sum_{i=1}^{N} p_i \cdot i$이며, 여기서 $p_i$는 $i$번째로 가능성 높은 비밀번호의 확률입니다.
정규화: 균일 분포에 대한 가능한 최대 $G$는 $(N+1)/2$입니다. 노력의 정규화된 측정치는 다음과 같이 정의될 수 있습니다: $$ H_E \approx \frac{2 \cdot G - 1}{N} $$ 이는 균일 분포(완전한 무작위성)를 $N$이 커짐에 따라 $H_E \to 1$로 매핑하고, 매우 예측 가능한 비밀번호($G$가 작은 경우)를 0에 가까운 값으로 매핑합니다.
실용적 추정: 단일 비밀번호의 경우, 그 "순위" 또는 그보다 더 가능성 높은 모든 비밀번호의 누적 확률을 추정해야 합니다. 비밀번호의 순위까지의 누적 확률 질량이 $\alpha$라면, $H_E \approx 1 - \alpha$입니다. 이는 값 0.4가 공간의 40%를 탐색함을 의미한다는 논문의 설명과 일치합니다.

단일 샘플로부터 이를 추정하는 정확하고 효율적인 알고리즘이 저자들이 암시하는 핵심 기술 기여입니다.

6. 실험 결과 및 차트 설명

참고: 제공된 PDF 발췌문에는 구체적인 실험 결과나 차트가 포함되어 있지 않습니다. 다음은 이러한 척도에 대한 일반적인 검증 연구가 포함할 내용에 기반한 설명입니다.

기대 엔트로피에 대한 포괄적인 평가는 다음과 같은 차트를 포함할 가능성이 높습니다:

차트 1: 척도 비교 산점도. 이 차트는 비밀번호를 두 축에 표시합니다: X축은 고전적 비트 강도(예: $\log_2(94^l)$), Y축은 기대 엔트로피(0-1)를 보여줍니다. 점들의 구름은 두 측정법 간의 상관관계(또는 부재)를 드러내며, 길지만 예측 가능한(낮은 기대 엔트로피) 비밀번호를 강조합니다.
차트 2: 크래킹 저항 곡선. 이는 공격자(규칙 기반 공격을 사용하는 Hashcat과 같은 도구)가 기대 엔트로피 점수(예: 0.0-0.1, 0.1-0.2...)별로 구분된 비밀번호를 해독하기 위해 실제로 탐색해야 하는 탐색 공간의 비율을 보여줍니다. 이상적인 척도는 예측 노력(엔트로피)이 실제 노력과 동일한 완벽한 대각선을 보일 것입니다. 대각선에서의 편차는 추정 오류를 나타냅니다.
차트 3: 점수 분포. 다양한 비밀번호 유형에 대한 기대 엔트로피 점수를 보여주는 히스토그램: 기계 생성(예: ComPass 프로토콜), 규칙이 있는 인간 생성, 규칙이 없는 인간 생성. 이는 척도가 비밀번호 생성 방법을 구별하는 능력을 시각적으로 입증할 것입니다.

검증해야 할 핵심 결과는 다음과 같은 주장입니다: "특정 값, 예를 들어 0.4의 기대 엔트로피를 가진다는 것은 공격자가 총 추측 횟수의 최소 40%를 완전 탐색해야 함을 의미합니다." 이를 위해서는 경험적 공격 시뮬레이션이 필요합니다.

7. 분석 프레임워크: 예시 사례

시나리오: 94자 인쇄 가능 ASCII 공간을 사용하는 시스템에 대한 두 개의 12자 비밀번호 평가.

비밀번호 A (사람이 선택): Summer2024!
비밀번호 B (기계 생성): k9$Lp@2W#r1Z

고전적 비트 강도: 둘 다 동일한 이론적 최대값을 가집니다: $\log_2(94^{12}) \approx 78.7$ 비트.

기대 엔트로피 분석:

비밀번호 A: 구조가 일반적입니다: 사전 단어("Summer"), 예측 가능한 연도("2024"), 일반적인 접미사 기호("!"). 확률적 모델(유출된 비밀번호로 훈련된 마르코프 체인과 같은)은 이 패턴에 높은 확률을 할당할 것입니다. 가능성 높은 비밀번호의 정렬된 목록에서의 순위는 매우 낮을 것이며, 이는 더 가능성 높은 비밀번호의 누적 확률이 높음을 의미합니다. 따라서 기대 엔트로피는 낮을 것입니다(예: 0.05-0.2), 이는 공격자가 최적화된 추측 순서의 처음 5-20% 내에서 이를 발견할 가능성이 높음을 나타냅니다.
비밀번호 B: 무작위로 보이며, 명백한 패턴이 없고, 위치별로 문자 집합을 혼합합니다. 확률적 모델은 이 특정 시퀀스에 매우 낮고 대략 균일한 확률을 할당할 것입니다. 순위는 매우 높을 것입니다(정렬된 목록의 중간/끝 부분에 가깝습니다). 따라서 기대 엔트로피는 높을 것입니다(예: 0.7-0.95), 이는 공격자가 공간의 대부분을 탐색해야 함을 나타냅니다.

이 예시는 기대 엔트로피가 고전 공식의 동일한 비트 강도보다 더 미묘하고 현실적인 위험 평가를 제공하는 방법을 보여줍니다.

8. 적용 전망 및 향후 방향

즉각적인 적용 분야:

실시간 비밀번호 강도 측정기: 웹 및 애플리케이션 가입 흐름에 기대 엔트로피를 통합하여 사용자에게 직관적이고 백분율 기반의 강도 표시기를 제공합니다.
보안 정책 시행: 조직은 단순한 복잡성 규칙 대신 최소 기대 엔트로피 임계값(예: 0.6)을 설정하여 정책을 추정된 크래킹 노력에 직접 연결할 수 있습니다.
자동화된 시스템 감사: 기존 비밀번호 데이터베이스(해시된)를 스캔하여 집단적 기대 엔트로피 분포를 추정하고 심각하게 약한 비밀번호를 가진 계정을 식별합니다.

향후 연구 방향:

견고한 단일 샘플 추정기: 단일 비밀번호의 확률/순위를 정확하게 추정하여 $H_E$를 도출하는 통계적 방법(예: 신경망 언어 모델, n-그램 모델 또는 블룸 필터 사용)을 개발하고 비교합니다.
적대적 평가: 첨단 비밀번호 크래킹 도구 및 AI 모델(예: 비밀번호용 생성적 적대 신경망 프레임워크의 적용인 PassGAN)에 대해 척도를 테스트하여 예측된 노력이 실제 크래킹 시간과 일치하는지 확인합니다.
비밀번호 이상의 적용: 정규화된 "노력 비율" 개념을 암호화 키(비트가 표준인 경우) 또는 생체 인식 템플릿과 같은 다른 비밀에 적용하여 다양한 인증 요소 간 통합 강도 척도를 생성합니다.
표준화 노력: 기대 엔트로피 또는 그 원리를 NIST와 같은 기관에 제안하여 디지털 신원 지침(예: SP 800-63B)의 향후 개정판에 포함시킵니다.

9. 참고문헌

독일 연방 교육연구부(BMBF). PHY2APP 프로젝트 보조금 세부사항.
M. Dell'Amico, P. Michiardi, Y. Roudier, "Password Strength: An Empirical Analysis," in Proceedings of IEEE INFOCOM, 2010. (비밀번호 강도 방법에 대한 조사 대표).
국립표준기술연구소(NIST). Entropy Estimation Suite. [온라인]. 이용 가능: https://github.com/usnistgov/entropy-estimation
NIST 특별 간행물 800-90B. Recommendation for the Entropy Sources Used for Random Bit Generation.
J. Kelsey, K. A. McKay, M. Turan, "Predictive Models for Min-Entropy Estimation," in Proceedings of CHES, 2015.
K. Reaz, G. Wunder, "ComPass: A Protocol for Secure and Usable Wi-Fi Device Provisioning," in Proceedings of ACM WiSec, 2023. (맥락상 가정).
C. E. Shannon, "A Mathematical Theory of Communication," The Bell System Technical Journal, vol. 27, pp. 379–423, 623–656, 1948.
R. V. L. Hartley, "Transmission of Information," The Bell System Technical Journal, vol. 7, no. 3, pp. 535–563, 1928.
J. Bonneau, "The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords," in Proceedings of IEEE Symposium on Security and Privacy, 2012.
J. L. Massey, "Guessing and Entropy," in Proceedings of IEEE International Symposium on Information Theory (ISIT), 1994.
C. Cachin, Entropy Measures and Unconditional Security in Cryptography. 박사 학위 논문, ETH Zurich, 1997.
J. O. Pliam, "The Disparity between Work and Entropy in Cryptology," 1998. [온라인]. 이용 가능: https://eprint.iacr.org/1998/024
B. Hitaj, P. Gasti, G. Ateniese, F. Perez-Cruz, "PassGAN: A Deep Learning Approach for Password Guessing," in Proceedings of ACNS, 2019. (적대적 AI 평가를 위한 외부 참고문헌).