난수발생기 개론

by 엉뚱도마뱀 posted Nov 22, 2017
?

Shortcut

PrevPrev Article

NextNext Article

ESCClose

Larger Font Smaller Font Up Down Go comment Print

차례

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

난수발생기 개요

난수발생기란?

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

안전한 암호화의 조건

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

난수발생기 구조

난수 생성 이론

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

Articles

1 2 3 4 5 6