난수

어디서 쓰이나

난수 random numbers는 많은 암호학 기반의 네트워크 알고리즘과 프로토콜에서 사용되고 있다.

• AES와 같은 알고리즘의 session key generation
• 대칭 암호 bit stream 생성
• RSA
• DF(Diffie-Hellman)
• 전자 서명

필요한 특징

1. Randomness
2. Unpredictability

random number니까 당연히 randomness한 성질을 가질 필요가 있다. 자세하게는 randomness의 2가지 측면을 살펴볼 수 있다.

하나는 Uniform distribution으로 bit로 나타난 난수에 대해 0과 1의 분포가 고르게 있어야 한다는 성질이다.

다른 하나는 Independence로 각 위치의 값이 다른 위치의 값과 연관이 없어야 한다. 즉, 독립적인 하나의 수로 역할을 다 한다.

두 번째 성질인 Unpredictability는 앞의 수를 보고 pattern을 파악하거나 다음 수를 예측할 수 없어야 한다는 성질이다.

주로 진짜 난수 생성말고 의사 난수 생성에서 필요한 성질이라고 할 수 있다. 참고로 의사 난수 생성은 처음 Seed값으로 진짜 난수 생성값을 이용한다.

TRNG, PRNG, PRF

TRNG: True Random Number Generator
PRNG: Pseudo Random Number Generator
PRF: Pseudo Random Function

PRNG는 deterministic하다는 특징이 있다. 이 말은 통계적으로 랜덤하지 못하다는 의미를 가진다. 따라서 위에서 설명한 난수의 필요한 특징을 만족할 필요가 있는데 이건 어떻게 확인하나? 뒤에서 설명할 randomness test를 통해 확인할 수 있다. 좋은 deterministic alogrithm이라면 진짜 난수랑 구분할 수 없을 정도의 수준이겠다.

TRNG input

TRNG의 input으로 entropy source를 사용한다. 화학시간에 배우는 그 엔트로피 성질을 의미한다. 예측불가능하고 무질서한 특징이 있겠다.

ex)

• keystroke timing patterns: 사람마다 키보드 누르는 타이밍이 다른 점을 이용
• disk electrical activity: disk의 전기 신호
• mouse movement
• system clock

위의 소스를 가지고 binary stream으로 바꾸면 그게 entropy source가 되고 이걸 이용해서 진짜 난수를 만들 수 있다. 선택적으로 bias 처리를 할 수 있는데 확률적으로 동일한 분포를 가질 수 있도록 전처리하는 과정이다.

이러헥 진짜 난수를 생성하면 좋겠지만 부수적인 비용이 많이 들기 때문에 의사 난수를 생성하는 경우가 많다.

PRNG

위의 그림에서 seed를 인풋으로 하는데 보통 진짜 난수로 생성한 값을 seed로 설정해서 random한 bit stream을 생성한다.

deterministic algorithm을 통해 난수를 생성한다.

PRF와의 차이점

PRNG는 symmetric stream cipher에서 자주 사용한다. 이유는 bit stream을 open-ended, 끝이 정해지지 않게 생성하기 때문이다.

반대로 PRF는 정해진 길이만큼의 난수를 생성하기 때문에 symmetric encryption에서 key나 nonce(initial vector)를 정하는데 사용된다.

Random test

앞에서 언급한 내용으로 적절한 난수임을 검증하는데 사용되는 테스트다. SP 800-22의 15가지 목록 중에 3가지만 살펴보자.

1. Frequency test: 0과 1의 분포가 적절하게 형성됐는 지 확인하는 검사로 정규분포를 생각하면 이해하기 쉽다.

2. Runs Test: run이란 끊기지 않고 연속하는 0이나 1의 개수를 의미하는데, compression에서 run-length coding을 알고 있다면 이해하기 쉬울 것이다. 통계상 난수에서 run의 개수를 보고 검사하고자 하는 난수의 run의 개수가 적절한지 판단하는 검사다.

3. Maurer's universal statistical test: 보통 압축을 할 때 동일하게 반복하는 pattern이 있다면 압축 효율이 잘 나온다. 반대로 난수가 압축이 잘 된다는 것은 동일한 패턴이 자주 나온다는 뜻으로 안 좋다고 보면 된다. 따라서 이 특징을 이용해 난수를 검사하는 것.

그래서 보통 난수 생성은 어떻게 ?

앞에서 계속 언급했지만 그림과 같이 의사 난수 생성 seed로 TRN값을 넣어주면 된다.

Algorithm Design

크게 두 가지로 나눌 수 있는데 처음부터 난수를 생성하기 위한 알고리즘과 기존에 존재하는 암호학 알고리즘을 기반으로 한 알고리즘으로 나뉜다.

• 처음부터 난수 생성 목적
  • Linear Congruential Generator
• 암호학 알고리즘 기반
  • Symmetric block ciphers
  • asymmetric ciphers (좋은데 느림)
  • Hash functions / MAC(Message Authentication Code)

Linear Congruential Generator

$m$ : mod
$a$ : 곱셈용
$c$ : 덧셈용
$X_0$ : 시작 변수 = seed

$m>0$
$0<a<m$
$0\leq c<m$
$0\leq X_0 < m$

$X_{n+1}=(aX_n+c)mod\ m$

우리가 사용하는 C언어의 rand함수가 이 방법을 사용한다.

근데 mod를 생략하고 공격한다고 가정해보자.
X와 관련한 3가지 값만 안다면 연립방정식을 통해 a, c, $X_0$를 알아낼 수 있다.

따라서 이 방법은 보안이 중요한 곳에서 사용하지 않는다.

Block cipher Modes of Operation을 이용한 난수 생성

• CTR
• OFB

앞 포스터에서 소개한 mode들인데 preprocessing이 가능한 방법들이다. 자세한 설명은 생략하겠지만 평문이 들어오기 전에 XOR을 할 수 있는 stream을 생성할 수 있고 이 방법으로 난수를 생성하는 것이다.

Stream cipher

RSA를 만든 Ron Rivest의 cipher라는 의미를 가진 stream cipher가 있다.

RC4인데 예전 와이파이 알고리즘으로 WPA에 사용됐지만 지금은 취약한 알고리즘이라 판단하여 사용을 중단했다. 참고로 요즘 와이파이는 WEP2 등을 사용한다.

또다른 알고리즘으로 ChaCha20이 있는데 예전 유럽에서 결성한 암호학 그룹에서 stream cipher 중 eSTREAM에서 Salsa가 있었다. 우리나라 LEA와 같은 ARX구조를 가지고 있는데 여기서 파생된 것이 차차20이다.

TLS

transport layer 위에 안전한 레이어 하나를 쌓아 올린 것이다.

Intel DRNG

이 내용은 가볍게 살펴보고 지나갔지만 관심이 있다면 직접 찾아보는 것을 권한다.

정리

난수가 어디서 필요한 지 그리고 난수라고 하려면 어떤 기준이 있는지에 대해 알아봤다. 거기에 난수를 생성하는 알고리즘들에 대해 알아봤다. 이전부터 session key, nonce, initial vector 등은 어떻게 생성하는 지 그리고 생성한 값이 안전한지에 대한 궁금증이 많았는데 이번 내용을 공부하면서 궁금증이 해결됐다. 특히 암호학 알고리즘을 기반으로 난수를 생성하는 것이 흥미로웠다.