#11 난수

1. 난수가 사용되는 암호 기술

1) 난수 용도

○ 키 생성

- 대칭 암호 / 메시지 인증 코드

○ 키 쌍 생성

- 공개 키 암호 / 디지털 서명

○ 초기화 벡터(IV) 생성

- 블록 암호 모드인 CBC, CFB, OFB

○ Nonce 생성

- 재전송 공격 방지나 블록 암호의 CTR 모드

○ 솔트 (salt) 생성

- 패스워드를 기초로 한 암호화(PBE)

○ 일회용 패드

- 패딩에 사용되는 열을 생성

2) 난수 목적

문제: 아무리 강한 암호 알고리즘이라도 키가 공격자에게 알려져 버리면 아무 의미가 없음

해결: 난수를 사용해서 키를 만들어, 공격자에게 키를 간파당하지 않도록 하는 것

2. 난수의 성질

  난수의 성질 분류

(1) 무작위성

▷ 통계적인 편중이 없이 수열이 무작위로 되어 있는 성질

▷ [아무렇게] 로 보이는 성질

▷ 의사 난수열의 통계적인 성질을 조사해서 치우침이 없도록 하는 성질

- 난수 검정 : 의사 난수열의 무작위성을 조사하는 것

▷ 암호 기술에 사용하는 난수는 무작위성을 가지고 있는 것만으로는 불충분

- 약한 의사난수 : 무작위성만을 갖는 의사난수

(2) 예측 불가능성

▷ 과거의 수열로부터 다음 수를 예측할 수 없다는 성질

▷ 공격자에게 간파당하지 않는다는 예측 불가능성이 필요

▷ 과거에 출력한 의사 난수열이 공격자에게 알려져도 다음에 출력하는 의사난수를 공격자는 알아 맞힐 수 없다는 성질

▷ 알고리즘은 공격자에게 알려져 있다고 가정하고 종자를 사용

- 종자(seed) : 공격자에게 비밀

   ◎ 강한 의사난수

 □ 약한 의사난수

- 무작위성만을 갖는 의사난수

□ 강한 의사난수

- 예측 불가능성을 갖는 의사난수

- 예측 불가능성을 가지면 당연히 무작위성을 가짐

(3) 재현 불가능성

▷ 한 난수열이 주어졌을 때 동일한 수열을 재현할 수 없는 성질

▷ 재현하기 위해서는 그 난수열 자체를 보존해두는 것 외에는 방법이 없는 성질

▷ 소프트웨어만으로는 재현 불가능성을 갖는 난수열 생성 불가

▷ 소프트웨어는 의사난수열만 생성가능

(소프트웨어가 돌아가는 컴퓨터는 유한의 내부 상태밖에 없기 때문)

     ◎ 주기

   □ 소프트웨어가 생성하는 수열은 언젠가는 반복됨

   □ 반복이 다시 시작할 때까지의 수열의 길이를 주기(period) 라고 함

   □ 주기를 갖는 수열은 재현 불가능하지 않음

즉, 재현 불가능한 난수는 위의 3가지 성질을 모두 가진다.

무작위성 / 예측 불가능성 / 재현 불가능성

3. 의사난수 생성기

1) 난수 생성기와 의사난수 생성기

▷ 난수 생성기 (Random Number Generator; RNG)

- 하드웨어로 생성

▷ 의사난수 생성기 (Pseudo Random Number Generator; PRNG)

- 소프트웨어로 생성

- 주기성을 가짐

▷ 의사난수 생성기의 구조

- 난수 내부상태 + 종자(seed) = 의사난수 생성

2) 의사난수 생성기의 내부 상태

- 의사난수 생성기가 관리하고 있는 메모리 값

- 의사난수 생성기는 메모리의 값(내부 상태)을 기초로 해서 계산을 수행

- 그 계산 결과를 의사난수로서 출력

- 다음 의사난수의 요구에 대비해서, 자신의 내부 상태를 변화

3) 의사난수 생성 알고리즘

▷ 의사난수 생성 알고리즘은 다음 2가지 기능을 합한 것

 (1) 의사난수를 계산하는 방법

 (2) 내부 상태를 변화시키는 방법

4) 의사난수 생성기의 종자(seed)

- 의사난수 생성기의 내부 상태 초기화에 필요

- 랜덤한 비트 열

- 종자는 자신만의 비밀로 유지

4. 구체적 의사난수 생성기

1) 무작위 방법

▷ 긴 주기

- 암호 기술에서 사용하는 난수는 예측 불가능성을 가져야 하므로 주기가 짧아서는 안됨

▷ 복잡한 알고리즘 보다는 명확한 알고리즘

- 프로그래머가 자세한 내용을 이해할 수 없는 알고리즘으로 생성한 난수는 예측 불가능성을 갖는지 어떤지 평가를 할 수 없음

2) 선형 합동법 (Linear Congruential Method)

- 일반적으로 가장 많이 사용되는 의사난수 생성기

- 암호 기술에 사용하면 안됨

- 현재 의사난수의 값을 A배하고 C를 더한 다음, M으로 나눈 나머지를 다음 의사난수로 선택함

3) 선형합동법의 단점

▷ 선형 합동법은 [예측 불가능성]이 없음

▷ 선형 합동법은 암호 기술에 사용해서는 절대로 안됨

ex: 선형 합동법을 사용하는 함수

  - C 라이브러리 함수 rand

  - Java의 Java.util.Random 클래스

  - 이들을 암호 기술에서 사용해서는 안됨

4) 일방향 해시 함수를 사용하는 방법

▷ 일방향 해시 함수(ex. SHA-1)를 사용해서 예측 불가능성을 갖는 의사난수 열(강한 의사난수) 을 생성하는 의사난수 생성기를 만들 수 있음

▷ 일방향 해시 함수의 일방향성이 의사난수 생성기의 예측 불가능성을 보장

5) 절차

1. 의사난수의 종자를 사용해서 내부 상태(카운터)를 초기화
2. 일방향 해시 함수를 사용해서 카운터의 해시 값 생성
3. 그 해시 값을 의사난수로서 출력
4. 카운터를 1 증가
5. 필요한 만큼의 의사난수가 얻어질 때까지 (2)~(4) 반복

6) 잘못 만들어진 의사난수 생성기 (가정)

1. 의사난수의 종자를 사용해서 내부 상태(카운터)를 초기화
2. 일방향 해시 함수를 사용해서 카운터의 해시 값을 생성
3. 해시 값을 의사난수로서 출력
4. 그 해시 값을 새로운 내부 상태로 함
5. 필요한 만큼의 의사난수가 얻어질 때까지 (2)~(4) 반복

7) 왜 예측 불가능성이 없는건가?

▷ 마지막에 출력한 의사난수의 해시 값을 취해서 다음 의사난수를 생성하므로 예측 불가능성을 갖지 않음

▷ 예측 불가능성을 갖기 위해서는 일방향 해시 함수의 일방향성을 사용하는 것이 포인트

8) 암호를 사용하는 방법

▷ 암호를 사용해서 [강한 의사난수] 를 생성하는 의사난수 생성기를 만들 수 있음

▷ AES 와 같은 대칭 암호나 RSA 와 같은 공개 키 암호 중 어느 것을 사용해도 무방

▷ 암호의 기밀성이 의사난수 생성기의 예측 불가능성을 보장

9) 암호를 사용한 의사난수 생성 절차

1. 내부 상태(카운터)를 초기화
2. 키를 사용해서 카운터를 암호화
3. 그 암호문을 의사난수로서 출력
4. 카운터를 1 증가
5. 필요한 만큼의 의사난수가 얻어질 때까지 (2)~(4) 반복   

10) 왜 내부 상태 추측을 못하나?

▷ 공격자는 의사난수로부터 역산해서 [내부 상태와 암호화된 현재 시각의 XOR] 을 간파할 수 없음

- 이유 : 간파하기 위해서는 암호를 해독해야만 함

▷ 공격자는 지금까지 출력된 의사난수열로부터 의사난수 생성기의 내부 상태를 추측 못함

5. 의사난수 생성기에 대한 공격

1) 종자에 대한 공격

▷ 종자의 중요성

- 의사난수의 [종자]는 암호의 [키]에 필적

- 종자가 공격자에게 노출되면, 그 의사난수 생성기가 생성한 모든 의사난수열은 공격자에게 노출됨

▷ 종자 선택

- 재현 불가능성을 갖는 [진정한 난수] 선택

2) 랜덤 풀에 대한 공격

▷ 랜덤 풀

- 종자로 사용할 랜덤 비트 열을 사전에 만들어 비축해 놓은 파일

- 암호 소프트웨어가 의사난수 종자가 필요할 경우 필요한 만큼의 랜덤한 비트 열을 꺼내서 사용

- 랜덤 풀 자체는 특별한 정보를 가지지 않지만 유익한 정보 저장을 위해 필요하므로 잘 지켜야 함