logo

English

이곳의 프로그래밍관련 정보와 소스는 마음대로 활용하셔도 좋습니다. 다만 쓰시기 전에 통보 정도는 해주시는 것이 예의 일것 같습니다. 질문이나 오류 수정은 siseong@gmail.com 으로 주세요. 감사합니다.

난수발생기 개론

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

Shortcut

PrevPrev Article

NextNext Article

Larger Font Smaller Font Up Down Go comment Print
?

Shortcut

PrevPrev Article

NextNext Article

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

List of Articles
No. Subject Author Date Views
113 TCP/IP State Transition - TCP 스택 포팅 시 참조 file digipine 2017.11.02 197132
112 언어 IDE 별로 git ignore 파일을 자동으로 만들어 주는 사이트 엉뚱도마뱀 2018.12.17 126068
111 What is Android Repo? and Manual, Download file digipine 2017.11.02 100764
110 [Linux] ubuntu 16.04에 QT Creator 설치하기 digipine 2017.11.02 24872
109 [Swift, MacOS] 맥 한글 파일명이 윈도우에서 자소 분리되는 현상 해결, NFD, NFC 엉뚱도마뱀 2018.12.11 20544
108 Linux init.d 에서 등록하기. 부팅 시 자동실행 설정 digipine 2017.11.03 13474
107 FFT (Fast Fourier Transform) 고속 푸리에 변환 예제 소스 digipine 2017.10.29 12841
106 Photoshop CC 2018 한글 영문 변환 언어팩, 포토샵 언어변경 file 엉뚱도마뱀 2018.07.04 8866
105 Phabricator 설치 가이드 우분투 16.04 기준 digipine 2017.11.02 6722
104 ATmega8 MCU 간의 TWI 기능을 이용한 I2C 통신 digipine 2017.11.02 6511
103 WinPCap과 Ethereal, Wireshark 을 이용한 스니핑(Sniffing) digipine 2017.10.29 5819
» 난수발생기 개론 엉뚱도마뱀 2017.11.22 4787
101 비밀번호 해쉬에 Salt(소금) 첨가하기 file 엉뚱도마뱀 2017.11.23 4669
100 공짜 무료 C/C++ 컴파일러들 file digipine 2017.10.28 4666
99 [iOS] Bluetooth로 App을 백그라운드 모드로 실행는 방법 lizard2019 2020.02.11 3949
98 [Linux, OSX] pfctl - Packet FIlter Control 사용법 digipine 2017.11.02 3767
97 OpenAL 사용법 정리 1 digipine 2017.11.01 3733
96 WIN CE, GPS - NMEA protocol - GPS Virtual Driver digipine 2017.10.28 3310
95 Xcode 없이 맥에 '명령어 라인 도구(Command Line Tools)'를 설치하는 방법 엉뚱도마뱀 2018.12.26 3279
94 LibVLC 미디어 재생기 프로그래밍 방법 C++, QT 엉뚱도마뱀 2018.04.20 2927
Board Pagination Prev 1 2 3 4 5 6 Next
/ 6