[컴퓨터 보안] Random Bit Generation and Stream Ciphers

Random Numbers(난수)가 사용되는 곳들

• Key distribution
• Session key generation
• symmetric stream encryption에서 bit stream 생성
• RSA public-key encryption 알고리즘에서 key 생성

 

난수의 특성

• Randomness
  • Uniform distribution: 나오는 값들의 분포가 동일 -> 0과 1에서 각각의 개수(분포)가 동일해야 한다.
  • Independence: 긴 sequence를 봤을 때, 부분 부분 간의 관계성이 없어야 한다.
• Unpredictability
  • 앞에서 동전 앞이 나와도, 다음에 뭐가 나올지 몰라야 한다.
  • Forward unpredictabiliy: 지금 나온 값을 봐도, 다음에 나올 값을 몰라(예측할 수 없어)야 한다.
  • Backward unpredictabiliy: 지금 나온 값을 보고, seed를 예측할 수 없어야 한다.

 

 

Pseudorandom Numbers

• 완전히 랜덤 하게 출력하기는 어려워서, 마치 난수처럼 보이는 pseudorandom number를 사용한다.
• seed를 넣어서 deterministic 한 알고리즘을 돌림.

 

 

TRNG(True Random Number Generator)

• 진짜 난수 생성기 -> 진짜 랜덤
• 물리적인 환경에서 가져온 entropy source를 사용함.
  • 하드디스크가 회전하면서 전자기적 움직임(오류를 포함), 마우스 움직임, 시스템 시간 등을 사용 -> seed로 사용
  • 이러한 아날로그 source를 binary output으로 변환하여 사용한다.
• bias 처리 과정이 필요할 수 있다.
  • 동전을 던지는데, 실제로 앞면이 나올 확률이 더 높다면, 이런 비율을 조정해 줘야 한다.
• NIST SP 800-90B

 

PRNG(Psedorandom Number Generator)

• Deterministic algorithm
  • input이 정해지면 output이 정해짐
  • 즉, seed 값을 잘 보호해야 함.
• NIST SP 800-90A에 정의됨

 

PRF(Pseudorandom Function)

• PRNG는 반복해서 계속 stream을 생성하지만, PRF는 필요한 만큼의 bit만 생성

 

Randomness와 Unpredictability를 측정할 테스트

• Frequency test: 0과 1의 개수 카운트
• Runs test: 연속되어 나오는 길이(예: 11112)를 제한
• Maurer's universal statistical test: 정보 손실 없이 sequence 압축 

 

 

PRNG 설계

• randomizing input 데이터 효과를 이용하는 암호 알고리즘
  • 대칭 블록 암호
  • 비대칭 암호 -> 공개키 암호
  • hash function & MAC

 

 

PRNG: Linear congruential generators

• $X_{n+1}$ = (a$X_n$+c) mod m
• 이런 식으로 작동되는 난수 생성기는 unpredictable 하지 않다.
• 즉, 암호키 생성 시 사용하기에 적절하지 않다. -> rand 함수 같은 거 사용하면 안 됨
• 단순 시뮬레이션을 위해서는 써도 좋음.

 

 

Conditioning

• TRNG는 randomness를 위해서 nondeterministic source를 사용한다.
  • 오디오나 디스크에서 나오는 예측 불가능한 소스들을 이용해서 TRN를 만든다.
  • 여기에 있는 bias를 제거하는 과정이 conditioning이다.
• Conditioning: TRNG entropy source의 bias를 제거하는 과정
  • conditioning algorithm/deskewing algorithm 사용
• Biased
  • 후처리 과정 거쳐서 처리
• Entorpy rate 
  • 1111 -> enrtopy 낮음,  13354 -> enrtopy 높음
  • entropy rate가 높아야 랜덤하다고 볼 수 있다.

• Ring Oscillator에서 시간이 지남에 따라(Not gate를 지남에 따라) 값이 바뀜 -> 우측의 그래프 참고

 

 

 

Intel이 제공하는 Digital Random Number Generator

• Instruction으로 RDSEED와 RDRAND 제공
• RDSEED: 다른 PRNG의 seed를 가지고 싶을 때 사용
  • #진짜 랜덤 #Non-Deterministic #srand 느낌
• RDRAND: 그 이외에는 RDRAND를 사용하면 됨.
  
  • #PRNG #rand 느낌

 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]