[암호 스터디 #2] 무작위성

2019. 9. 27. 22:59

2.1 무작위 대 비무작위

11010110 과 00000000

둘 중 무엇이 더 무작위해 보이는가?

대부분의 사람들은 11010110이 더 무작위해 보인다고 한다. 하지만 확률로 따져보았을 때, 둘은 1/(2^8)의 확률로 동일하게 생성된다. 여기서 사람들이 무작위성(randomness)을 식별할 때 저지르는 두 가지 오류를 확인할 수 있다.

1) 비무작위성(non-randomness)을 무작위성으로 오해 : 단지 무작위해보인다는 이유로 무작위하게 생성되었다고 생각하는 실수

2) 무작위성을 비무작위성으로 오해 : 어떠한 패턴을 보고 그런 패턴이 발생한 이유가 있을 것이라고 생각하는 실수

** 보안을 위해서 무작위해 보이는 것과 실제로 무작위한 것을 구별하는 것은 굉장히 중요!!

2.2 확률분포로서의 무작위성

- 확률분포

: 주어진 과정의 무작위성에 관해 알아야 할 모든 정보를 제공한다.

: 무작위 과정의 모든 가능한 결과에 부여된 확률(probability)을 나열한 것이다.

- 균등분포 ( uniform distribution : 또는 고른 분포 )

: 모든 결과의 발생 가능성이 같다.

ex) 128비트 키를 무작위로 고르게 선택한다면 1/(2^128) 만큼 의 확률로 선택

- 비균등분포 ( non-uniform distribution )

: 확률들이 모두 같지는 않은 분포

ex) 동전 던지기에서 앞면과 뒷면이 나올 확률이 다르다고 가정할 때.

-> 이러한 동전을 가리켜 ' 편향되었다(biased) ' 라고 한다.

2.3 엔트로피 : 불확실성의 측도

- 엔트로피

: 시스템에 존재하는 무질서의 측도(measure)

: 어떤 무작위 과정이 의외의 결과를 내는 경우가 얼마나 많은지를 나타내는 값

: 정보를 비트들의 개수로 표현할 수 있게 이진 로그를 사용

: 수식에서 음의 합을 사용하는 이유 : log(1/2) 면 (물론 이진로그) 음의 값이 나오기 때문에 엔트로피를 음수가 아닌 값으로 맞춰주기 위해서 음의 합 사용

: 엔트로피는 확률분포가 균등분포일 때 최대 ( 균등분포는 모든 확률이 같기 때문에 불확실성이 최대 )

-> 만약 5가지의 선택사항이 있을 때

a) 모든 확률은 1/5로 같음

b) 1/25, 18/25, 2/25, 3/25, 1/25 각각 이런 확률

그러면 a)는 모든 확률이 같기 때문에 무엇이 선택될 지 예측 불가능

b)는 2번이 선택될 것이라 예측 가능

** 정리를 해보면

엔트로피가 높다??? 예측이 어렵고, 랜덤하다.

2.4 난수 발생기(RNG)와 의사난수 발생기(PRNG)

암호 시스템은 무작위성을 얻기 위해 다음과 같은 구성요소를 갖추어야 한다.

1) 불확실성의 원천 또는 엔트로피원(source of entropy) : 난수 발생기 ( random number generator, RNG )가 담당

2) 엔트로피원으로부터 고품질 무작위 비트를 산출하는 암복호화 알고리즘 : 의사난수 발생기 ( pseudorandom number generators, PRNG )가 담당

- RNG : 디지털 시스템 안에서 아날로그 세계의 엔트로피를 이용해서 예측 불가능한 비트들을 산출하는 소프트웨어 또는 하드웨어 구성요소 ( ex) 온도, 음향적 잡음, 공기의 난류, 정전기, 시스템에 부착된 sensor, 입출력장치, 네트워크나 디스크활동, 시스템 로그, 실행중인 프로세스들, 키 입력이나 마우스 이동 등 )

-> 좋은 엔트로피원일 수 있지만, 공격자의 조작과 악용에 취약, 난수 비트들을 생성하는 속도 느림

- PRNG : 적은 수의 진정한 난수 비트들로부터 다수의 인위적인 난수 비트들을 신뢰성 있게 산출

RNG vs PRNG

느리다 빠르다 (비교적)

비결정론적 결정론적

엔트로피가 높다는 보장 X 최고의 엔트로피 보장

** 결정론적 : 예측 그대로 동작하는 알고리즘, 어떤 특정 입력이 들어오면 언제나 똑같은 과정을 거쳐 언제나 똑같은 결과를 내놓는다.

2.4.1 PRNG의 작동 방식

주기적으로 RNG로부터 받은 난수 비트들을 이용해서 큰 메모리 버퍼(entropy pool)의 내용을 갱신.

엔트로피 풀이 PRNG의 엔트로피원이다.

의사난수 비트열을 생성하기 위해 DRBG( Deterministic random bit generator, 결정론적 난수 비트 발생기 ) 알고리즘 실행. DRBG는 같은 입력을 넣으면 같은 출력이 나옴 -> 같은 입력을 두 번 제공하지 말아야 한다.

작동과정에서 PRNG는 다음 세 가지 연산 수행

1) init() : 엔트로피 풀, PRNG 내부 상태 초기화

2) refresh(R) : 어떤 자료 R( RNG 에서 얻은 자료 ) 을 이용해서 엔트로피 풀 갱신 -> 임의의 통계적 편향 제거

3) next(N) : N개의 의사난수 비트 생성 후 엔트로피 풀 갱신

2.4.2 보안 관련 문제

PRNG에 요구되는 몇 가지 고수준 사항

1) 역추적 저항성 ( backtracking resistance; 순방향 비밀성 ) : 이전에 생성된 비트들을 절대로 다시 생성할 수 없어야 한다. -> refresh, next 연산에서 내부 상태를 갱신할 때 수행되는 변환들이 비가역적이어야 한다.

2) 예측 저항성 ( prediction resistance; 역방향 비밀성 ) : 이후의 비트들을 예측하는 것이 불가능해야 한다. -> 공격자가 알지 못하고 추측하기 힘든 R 값으로 refresh를 호출해야한다.

2.4.4 암호학적 PRNG와 비암호학적 PRNG

비암호학 PRNG : 응용 프로그램에서 균등 분포 무작위 비트열을 산출하도록 설계된 것들, 안전하지 않다.

암호 PRNG : 잘 분포된 비트들을 산출하는 데 쓰이는 바탕 연산들의 강도에 신경 쓰기 때문에 예측 불가능.

하지만 여러 시스템에 쓰이는 것은 대부분 비암호 PRNG임. ex) 메르센 트위스터

- 메르센 트위스터 ( Mersenne Twister, MT )

: PHP, 파이썬, R, Ruby를 비롯한 여러 시스템에 쓰이는 비암호 PRNG이다.

: 통계적 편향이 없는 균등분포 무작위 비트열을 생성하지만 예측 가능하다 -> 내부 작동 방식을 살펴보면 죄다 xor 을 통해서만 상호작용하기 때문이다.

* 비트들의 XOR 결합을 선형결합이라고 부른다. -> 선형결합은 예측이 가능하다. ( AND 결합은 비선형결합 )

2.5 실제로 쓰이는 PRNG들

데스크톱과 노트북, 네트워크 라우터나 센톱박스 같은 내장 시스템을 비롯한 대부분의 플랫폼은 운영체제 차원에서 암호학적 PRNG를 제공.

가장 널리 쓰이는 PRNG는

1) 여러 Unix 기반 시스템이 제공하는 것

2) Windows가 제공하는 것

3) 인텔 마이크로프로세서에 쓰이는 하드웨어 기반 PRNG 이다.

2.5.1 Unix 기반 시스템에서 무작위 비트 생성

장치파일 /dev/urandom 은 암호 PRNG를 제공하는 사용자 영역 인터페이스이다.

신뢰성 있는 무작위 비트들을 얻을 때 이 장치 파일을 생성한다.

리눅스가 사용하는 PRNG는 drivers/char/random.c 에 정의되어있고 SHA-1 해시 함수를 이용하여 원본 엔트로피 비트 -> 신뢰성 있는 의사난수 비트를 만듦.

/dev/urandom은 비차단 ( non-blocking ) 풀 , /dev/random은 차단 풀을 사용

** /dev/urandom 과 /dev/random은 무슨 차이일까?

/dev/random은 엔트로피 양을 추정하여 엔트로피 수준이 낮으면 비트들을 돌려주지 않는다. 이것이 좋은 방식인 것 같지만 신뢰성이 낮기로 악명이 높고, 공격자가 그것을 속여 넘길 수 있다고 한다.

그리고 추정된 엔트로피를 상당히 빨리 소진하여, 엔트로피가 높아지길 기다리느라 응용프로그램이 느려진다. (DOS 가능)

이래서 /dev/random은 별로라고 한다!!

2.5.2 Windows의 CryptGenRandom() 함수

예전 버전의 Windows 에서는 운영체제의 PRNG에 대한 사용자 영역 인터페이스로 CryptGenRandom() 함수가 쓰였다.

최근 버전의 Windows 에서는 Cryptography API: Next Generation(CNG) 라는 API의 BCryptGenRandom()함수가 쓰인다.

윈도우 PRNG는 커널 모드 드라이버 cng.sys(전에는 ksecdd.sys) 에서 엔트로피를 가져오는데 느슨하게 말하면 포르투나에 기초한다. (난수를 얻는 과정 꽤나 복잡)

CryptGenRandom() - 핸들을 이용하여 암복호화 문맥 얻어야함 -> 이 과정에서 잘못될 기회가 늘어남

BCryptGenRandom() - 핸들 없이 가능!

2.5.3 하드웨어 기반 PRNG: 인텔 마이크로프로세서의 RDRAND 명령

응용 프로그램은 RDRAND라는 어셈블리 명령을 통해 인텔의 이 PRNG에 접근.

운영체제와는 독립적인 인터페이스 제공, 이론상 소프트웨어 PRNG보다 빠름

2.6 문제 발생 요인들

다음 4가지의 예시를 보쟈!

2.6.1 불충분한 엔트로피원

- 넷스케이프 브라우저 SSL 구현은 128 비트 PRNG 종잣값을 계산할 때

global variable seed;
RNG_CREATEContext()
    (seconds, microseconds) = 하루 중 시간
    pid = 프로세스 id; ppid = 부모 프로세스 id; /* 각 15 비트 */
    a = mklcpr(microseconds);
    b = mklcpr(pid + seconds + (ppid << 12));
    seed = MD5(a, b);

mklcpr(x)
 return ((0xDEECE66D * x + 0x2BBB62DC) >> 1);

MD5()

이 의사코드에 따라 계산을 하는데

seconds 를 알아버리면 microseconds의 seconds/10^6 이므로 이 때 엔트로피가 log(10^6) 즉 약 20비트.. 여기서 큰 빵꾸가 나기 때문에 엔트로피가 128비트가 안된다.. 그래서 문제 발생함.

또한 b를 구하는 과정에서 ppid 를 왼쪽으로 12비트 shift 해서 3비트가 겹쳐버려서 여기서의 엔트로피 15(pid)+12(ppid) 이므로 3비트 빵꾸남 원래 15+15 여야 하는 데 그래서 문제 발생!!

2.6.2 시동 시점의 엔트로피 부족

시동(booting) 도중 아직 엔트로피가 충분히 수집되지 않은 시점에서 엔트로피를 계산하는 장치가 많다는 것을 조사를 통해 얻음 -> 엔트로피가 충분치 않다 보니 서로 다른 시스템의 PRNG들이 동일한 기본 엔트로피원으로부터 동일한 난수비트들을 생성 -> 동일 키 생성됨

prng.seed(종잣값)
p = prng.generate_random_prime()
q = prng.generate_random_prime()
n = p*q
/* 결과적으로 n이 같아지는 시스템 */

생성 도중에 추가적인 엔트로피 주입되는 키 생성 방안을 의사코드로 나타내면 아래와 같다.

prng.seed(종잣값)
p = prng.generate_random_prime()
prng.add_entropy()
q = prng.generate_random_prime()
n = p*q

이 시스템에서 p가 같다 하더라도 추가적인 엔트로피 주입으로 인해 n은 달라진다. 하지만 n과 n' 의 최대공약수를 계산하면 공통인 소인수인 p를 알아낼 수 있기에 문제가 생긴다. (문제 : 개인키를 알아낼 수 있음)

2.6.3 비암호 PRNG

앞서 말했듯이 비암호 PRNG는 안전하지 않다.

예를 들어 위키백과를 비롯한 여러 위키 사이트는 Media Wiki를 사용한다. Media Wiki는 무작위성을 활용해서 보안 토큰이나 임시 패스워드를 생성했으며 이때 mt_rand() 함수를 이용하여 생성했다. mt_rand()는 메르센 트위스터이다.. 예측 가능하단 소리! 그래서 안전하지 않다!!

2.6.4 무작위성은 강하지만 표본 추출에 문제가 있는 사례

Cryptocat 이라는 채팅 프로그램은 보안 통신을 제공하도록 설계되었다.

0~9 의 숫자들을 고르게 분포하려고 했는데 0부터 255까지의 모든 수를 10으로 나눈 나머지에서는 0~9가 고르게 분포되지 않는다. ( 1 byte = 8 bits 라서 0부터 255 )

그래서 이 개발자들은 다음과 같은 방법을 사용했다.

Cryptocat.random = function() {
    var x,o ='';
    while(o.length < 16) {
          x = state.getBytes(1);
          if(x[0] <=250)
              o += x[0] % 10;
     }
}

10의 특정 배수인 250을 조건으로 해서 그 미만의 수에서만 10으로 나눈 나머지를 취하고 그외는 버리는 방법을 사용했다. 근데 250을 10으로 나누면 0이라는 수가 한번 더 나오게 되서 균등하지 못하게 된다. 그래서 엔트로피가 낮아진다.

'Cryptography > 처음 배우는 암호화' 카테고리의 다른 글

[암호스터디 #6] 해시 함수 (0)	2020.04.26
[암호스터디 #5] 스트림 암호 (0)	2020.04.17
[암호 스터디 #4] 블록 암호 (1)	2020.04.05
[암호 스터디 #3] 암호학적 보안 (0)	2019.12.03
[암호 스터디 #1] 암호화 (1)	2019.09.27

h32j00