2016 암호여름학교 - 난수발생기 강의

차례

• 난수발생기 개요
• 난수발생기 구조
• 표준 난수 발생기
• 난수 발생기의 안전성 분석
• 안전성 평가 기법과 안전한 활용

난수발생기 개요

난수발생기란?

난수발생기(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∗10262641026로 충분히 큼
• 출력되는 암호문에 평문 정보가 노출됨

안전한 암호화의 조건

• 암호문읜 난수와 구별할 수 없어야 한다. (평문을 추측할 수 있는 정보를 제공하지 않아야 한다.)
• 암호키는 공격자가 예측할 수 없어야 한다. (키 공간이 충분히 크고, 랜덤하게 선택되어, 공격자가 사용된 키를 맞출 확률이 낮아야 한다.)

난수발생기 구조

난수 생성 이론

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()
• .....이 외에도 많이있지만 쓸만한 게 별로 없다

리눅스 환경에서의 엔트로피 소스(LPRNG가 사용하는 엔트로피 종류)

• ~~~

시드 생성 단계의 취약성

엔트로피 축적/시드 생성 단계에서의 취약성

• 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)가 가능함
• (작성중)