차례
- 난수발생기 개요
- 난수발생기 구조
- 표준 난수 발생기
- 난수 발생기의 안전성 분석
- 안전성 평가 기법과 안전한 활용
난수발생기 개요
난수발생기란?
난수발생기(RBG : Random Bit Generator) 기능
- 암호시스템에 필요한 난수 제공
- 이상적으로는 동전 던지기의 결과를 기대
- 암호시스템과 암호 모듈의 운용에 필수적인 요소
요구되는 성질
- 예측 불가능성
- ()
- ()
난수발생기와 보안 시스템
난수발생기의 용도
- 비밀키 암호에 사용되는 암호키 생성
- 공개키 암호의 파라미터 생성
- 기타 : nonce, salt 등
현대 암호의 안전성
- 보안시스템의 암호기능에서 난수 발생기의 사용은 필수
- 암호의 안전성 확보는 완벽한 난수 발생기 사용을 전제로 가능
난수발생기의 용도(1) 암호키
암호키의 생성
- 블록 암호의 암호키
- RSA 공개키 암호의 소수 생성
난수발생기의 용도(2) Salt
사용자 인증(로그인)용 패스워드의 저장
- 패스워드는 암호화된 형태로 시스템에 저장되어야 함
- 암호화 방식
- 해쉬함수를 이용하는 방법
- 비밀키 암호로 암호화하는 방법
난수발생기의 용도(3) Bit Commitment
원거리의 Alice와 Bob이 동전던지기 게임을 할 수 있을까?
- Alice : 난수 R1, R2 생성
- Alice : 동전을 던진 결과 a
- Alice : 해쉬값 H(R1,R2,a)와 R2를 Bob에게 전달
- Bob은 Alice의 동전 던진 결과를 b로 예측하여 공개
- Alice는 a를 공개하고, 증거자료로 R1, R2를 전송
- 해쉬값을 계산하여 결과를 검증
난수발생기 관련 용어들
의사난수 발생기(PRNG, DRNG)
- PRNG : Pseudo Random Number Generator
- 일정한 알고리즘에 따라 초기값(seed)로 부터 난수를 생성
- 알고리즘과 초기값이 모든 출력을 결정
진난수 발생기(TRNG)
- TRNG : True Random Number Generator
- 물리적 잡음을 기반으로 난수를 생성하는 장치
기타용어
- DRNG : Determenistic RNG
- DRBG : Deterministic Random Bit Gengerator
난수발생기 종류
TRNG, PRNG의 기본구조를 기반으로 다양한 조합이 가능
- 디지털화(Conversion to binary), 난수생성 알고리즘(Determenistic Algorithm)
난수발생기의 구현
하드웨어 난수발생기
- 하드웨어 장치에서 발생되는 잡음원을 이용한 난수 생성
- 잡음원의 편향된 성질을 보정하는 과정이 필요
- 잡음원(엔트로피 소스) : 열잡음원, 링오실레이터, 빔스플릿터 등
소프트웨어 난수발생기
- 외부의 잡음원 공급을 전제로 결정론적 알고리즘을 사용
- 잡음원 : OS 잡음(마우스 포인터 위치, 프로세스 id 등), 사용자 입력 등
난수발생기의 중요성
난수발생기의 중요성
- 암호시스템의 안전성은 이상적인 난수발생기를 사용해야 보장할 수 있음
- 암호학적 안전성 증명 모델도 완벽한 난수발생기의 사용을 전제로 함
- 난수발생기의 취약성은 보안 매개변수의 안전성을 약화시킴
암호의 안전성과 난수(1)
Caesar Cipher
- 평문(P), 암호문 (C), 암호키(K)의 관계
- \(C = Ek(M) = M+k mod 26)
- 암호키의 종류(26가지)가 너무 적어 안전하지 않음
단순치환 암호
- 암호키(=치환표) : A~Z를 무작위로 섞는 방법
- 암호키의 종류는 26!=4∗1026로 충분히 큼
- 출력되는 암호문에 평문 정보가 노출됨
안전한 암호화의 조건
- 암호문읜 난수와 구별할 수 없어야 한다. (평문을 추측할 수 있는 정보를 제공하지 않아야 한다.)
- 암호키는 공격자가 예측할 수 없어야 한다. (키 공간이 충분히 크고, 랜덤하게 선택되어, 공격자가 사용된 키를 맞출 확률이 낮아야 한다.)
난수발생기 구조
난수 생성 이론
Deterministic Extractor
- 결정론적 알고리즘 만으로는 엔트로피 소스로부터 좋은 난수를 얻을 수 없다.
- Extractor 알고리즘을 고정할 때, 주어진 입력 엔트로피가 우수하지만 출력이 균등분포에 근접하지 않는 예가 항상 존재한다.
Seeded Extractor
- Seed의 선택에 따라 extractor가 달라지도록 설계하면 균등분포에 근접한 출력을 얻는다.
- 단, seed의 선택을 잘 해야 한다.
- Ext(X;S) ~= (Uniform, S)
OS 난수발생기 구조
3단계 구조 : 엔트로피 수집, 시드 생성, 난수생성 알고리즘
- 엔트로피 수집 : 잡음원으로부터 엔트로피 수집, 시스템 의존적
- 시드 생성 : 시드(PRNG의 입력) 생성
- 의사난수 생성 알고리즘 : 표준화된 암호 알고리즘
LRNG 구조
- 커널 모드에서 수집된 엔트로피를 pool로 관리하여 출력
- Blocking Model(/dev/random)와 non-Blocking Model(/dev/urandom) 모드
- 디바이스로 마운트되어 작동
- 하드웨어 등의 환경에 따라 달라질 수 있다.
WRNG 구조 (윈도우 난수 발생기)
- 유저모드의 인스턴스로 생성되어 동작 (여러 WRNG 공존)
- 엔트로피 관리가 없어 Blocking Model은 제공하지 않음
표준 난수발생기
ISO/IEC 표준 모델
- ISO/IEC 18031 표준문서에 정의된 난수 발생기
미국의 NIST 모델
- SP800-90A 의 난수발생기 모델 : DRBG
독일의 BSI 모델
- AIS.31
한국 KCMVP의 난수발생기
암호모듈 검증제도의 알고리즘
- Hash_DRBG : sha224/256/384/512
- HMAC_DRBG : HMAC(sha224/~~)
- CTR_DRBG : ARIA128/192/256, LEA128/192/256
난수 발생기의 안전성 분석
난수발생기의 안전성
Backtracking resistence
Prediction resistence
- 공격자가 현재의 상태정보를 알 수 있을 때
- 이전 정보를 보호하는 것 (업데이트 알고리즘을 잘 만들기)
- 향후 출력을 보호하는 것 (다음 단계로 넘어갈 때 엔트로피 소스 넣기)
엔트로피 수집의 취약성
엔트로피 수집 단계의 취약성
- 충분한 엔트로피를 수집하지 못하면 난수의 출력이 예측 가능함
- 대부분의 취약성은 엔트로피 수집단계에서 발생함
- 시스템에서 활용 가능한 잡음원이 충분히 확보되어야 함
비트코인 지갑의 취약성
- 시스템 난수발생기의 취약성으로 전자지갑 탈취
- 비트코인 공개키 암호의 안전성에 치명적 손상 유발
모바일 환경에서의 엔트로피
- 키보드, 마우스 등의 가용 잡음원 부족
- 충분한 엔트로피의 소스를 확보해야 함
엔트로피 수집 - Windows
윈도우 환경에서의 엔트로피 소스
- GetCurrentProcessID()
- GetCurrentThreadID()
- GetLocalTime()
- GetDiskFreeSpace()
- GetComputerName()
- GetUserName()
- .....이 외에도 많이있지만 쓸만한 게 별로 없다
각 운영체제 환경에서의 난수발생기
- Linux 계열의 난수 발생 함수 : /dev/random, /dev/unrandom
- unramdom은 non blocking 방식, 내부 소스로 의사 임의(pseudio-random) 비트를 만듬
- MacOS에서는 둘간의 차이가 없이 동작
- 솔라리스, NetBSD, Tru 64유닉스, AIX, HP-UX 11i v2에서도 이용가능
- 윈도 NT의 경우 비슷한 기능이 ksecdd.sys를 통해 제공되지만 \Device\KsecDD라는 특수 파일을 읽는 것은 유닉스에서처럼 동작하지 않는다. 유사난수 바이트를 발생하는 문서화된 방식은 CryptGenRandom과 RtlGenRandom이 있다.
- 도스의 경우 해당 기능을 네이티브로 지원하지는 않지만 noise.sys[16]라는 타사 오픈 소스 드라이버가 있으며, 이를 통해 RANDOM$과 URANDOM$이라는 두 장치를 만들어내며 랜덤 데이터 접근을 위해 /DEV/RANDOM$, /DEV/URANDOM$으로도 접근이 가능하다.
시드 생성 단계의 취약성
엔트로피 축적/시드 생성 단계에서의 취약성
- ios 난수 발생기 취약점
- 안드로이드 난수발생기 취약점
난수생성의 알고리즘의 취약성
의사난수생성 알고리즘의 취약성
- 알고리즘의 취약성 우려제기
- 미국의 NIST의 난수발생 알고리즘 표준
- 백도어 심어 놓음 -> 스노든의 폭로
- 2014 ISO 회의에서 표준 철회
Dual_EC_DRBG란?
- 타원곡선 이산대수 문제 기반 의사난수발생기
- 미국 ANSI 표준, ISO
- NIST가 권장 파라미터를 제공
암호 전문가가 Dual_EC_DRBG의 취약성 지적
- P = eQ
- rP : Seed, rQ : Output
- 그런데 NSA가 e를 알고 있다는 의혹 제기
- e를 알고 있다면 새로운 난수를 계속 알 수 있음
- 하지만 의혹을 증명할 수는 없다.
안전성 평가 기법과 안전한 활용
난수발생기의 안전성 평가
안전성 평가의 중요성
- 난수 발생기의 취약성은 암호시스템 전체로 전파
- 특히 예측 가능한 출력이 발생하면 치명적
평가의 어려움
- 현실적으로 이상적인 난수에 도달할 수 없음
- 충분히 이상적인 난수에 근접함을 입증해야 함
- 개발자, 시험기관, 검증기관 모두에게 어려운 문제
난수발생기 평가 기준
난수발생기 평가 방법
- 수집되는 엔트로피의 건전성 평가
- 출력난수의 통계적 랜덤성 평가
난수발생기 평가 기준
- ISO/IEC 19790/24759
통계적 난수성 검정의 한계
- 통계적 난수성 검정은 편리한 도구이나 암호학적 안전성을 보장하지는 않는다.
엔트로피 개요
엔트로피 개념
- 데이터가 가진 실제 정보량을 정량적으로 측정한 값
- 엔트로피가 높다는 건 확률은 낮다고 얘기할 수 있음
- random variable의 확률분포가 엔트로피를 결정
엔트로피 종류
- 샤논(shannon) 엔트로피 : 가지고 있는 정보량의 기대값
- 민(Min) 엔트로피 : 확률 멕시멈의 정보량
요약
보안시스템의 안전성과 난수발생기
- 현대암호의 안전성은 난수발생기에 의존함
- 암호키와 보안매개변수 생성에 사용되는 난수발생기의 안전성이 확보되어야 함
난수발생기 평가의 어려움
- 암호 알고리즘의 경우 테스트 벡터의 확인으로 안전성을 확인하는 KAT(Known Answer Test)가 가능함
- (작성중)