[CS][알기 쉬운 정보보호개론 3판] Chapter13. 난수

 

 

 

난수의 용도

• 키 생성
  • 난수를 안쓰면 인간의 의지가 들어가서 예측이 쉬워진다.
  • 대칭 암호나 메세지 인증 코드 (공개X)
• 키 쌍 생성
  • 공개키 암호나 디지털 서명
• 초기화 벡터(IV) 생성
  • 블록 암호 모드인 CBC, CFB, OFB
• 비표(nonce) 생성
  • 재전송 공격 방지나 블록 암호의 CTR 모드
• 솔트 생성
  • 패스워드를 기초로 한 암호화 (PBE)
• 일회용 패드
  • 패딩에 사용되는 열을 생성
• 아무리 강한 암호 알고리즘이라도 키가 공격자에게 알려져 버리면 아무 의미가 없다.
• 난수를 사용해서 키를 만들어, 공격자에게 키를 간파당하지 않도록 한다. (사람의 의지↓)
• 현재 사용되고 있는 대부분의 보안 프로토콜에서 난수가 사용되고 있다.
  • 암호 알고리즘에서 각종 키 생성 in protocol
  • 프로토콜에서 재전송 공격(Replay Attack)을 막기 위한 방법

 

 

난수의 성질

• 무작위성 (Randomness)
  • 수열의 비트 분포가 균등해야 한다.
  • 즉, 0과 1이 등장하는 빈도가 거의 비슷해야 한다. (5:5)
  • 암호 기술에 사용하는 난수는 무작위성을 가지고 있는 것만으로는 불충분
• 예측 불가느엉 (Unpredictability)
  • 수열의 일부를 보고 그 다음 비트를 예상할 수 없어야 한다.
  • 과거에 출력한 의사난수열이 공격자에게 알려져도 다음에 출력하는 의사난수를 공격자를 알아맞힐 수 없다는 성질
  • ( 알고리즘은 공격자에게 알려져 있다고 가정하고 seed를 사용한다. )
• 재현 불가능성
  • 같은 수열을 똑같이 재현할 수 없다는 성질
  • 재현하기 위해서는 수열 그 자체를 보존해야만 하는 성질
  • 소프트웨어만으로는 재현 불가능성을 갖는 난수열 생성 불가 + 하드웨어도 동원되어야 한다.

 

 

 

진성 난수와 의사 난수

• 진성난수 스트림 (True Random Number Stream)
  • 엔트로피 소스 (컴퓨터의 물리적 환경에서 얻을 수 있는 값)이 입력으로 사용된다.
  • Ex. 시간, GPS 위치, 주변 색깔 등
• 의사난수 스트림 (Pseudorandom Number Stream)
  • 실제로 많이 사용된다.
  • seed(종자)와 이전 비트열 값이 입력으로 사용된다.
  • 의사 난수의 종류
    • 약한 의사난수 : 무작위성만을 갖는 의사난수
    • 강한 의사난수 : 예측 불가능성까지 갖는 의사난수

 

 

 

재현 불가능한 난수

• 재현 불가능한 물리 현상으로부터 정보를 취득
• 예시
  • 주위의 온도나 소리의 변화
  • 사용자의 마우스 위치 정보
  • key stroke 입력 시간 간격
  • 다양한 하드웨어로부터 얻어진 정보
• 진성난수 (Real Random Number)
  • 재현 불가능한 난수
  • 아래 세가지 성질을 가진다.
    • 무작위성
    • 예측 불가능성
    • 재현 불가능성

 

 

 

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

• (진성) 난수 생성기 (random number generator, (T)RNG) : 주로 하드웨어로 생성
• 의사난수 생성기 (pseudo random number generator, PRNG) : 소프트웨어로 생성, 진짜로 비슷한 가짜

알기 쉬운 정보보호개론 3판

 

 

 

구체적인 의사난수 생성기

• 무작위 방법
  • 암호 기술에서 사용하는 난수는 예측 불가능성을 가져야 하므로 주기가 짧으면 안된다.
• 선형 합동법 (linear congruential method)
  • 일반적으로 가장 많이 사용되는 의사난수 생성기 (대부분의 Random 함수)
  • 암호 기술에 사용하면 안된다.
  • 현재 의사난수의 값을 A배하고, C를 더한 다음, M으로 나눈 나머지를 다음 의사난수로 선택한다.
  • 예측불가능성이 없다는 단점이 있다. (A,C,M의 값을 알면 난수 값을 알 수 있어서)
  • = 안전하지 않다
  • 무작위성 준수, 예측 불가능성 미준수

알기 쉬운 정보보호개론 3판

• 일방향 해시 함수를 사용하는 방법
  • 해시 함숫값의 무작위성을 이용한 것으로 예측 불가능성을 갖는다.
  • seed 값을 동일하게 쓰면 재현할 수 있어서 진성난수는 아니다.

알기 쉬운 정보보호개론 3판

• 암호를 사용하는 방법
  • 해시 함수 이용 방법에서 해시 함수 대신 암호화 알고리즘을 넣는다.
• 일방향 해시 함수와 암호를 사용하는 방법의 공통점
  • 무작위성, 예측 불가능성 준수
  • 재현 불가능성 미준수 (seed가 같은 값이면 같은 난수열을 출력)
  • = 진성난수열이 나오지는 않는다.
• ANSI X9.17 : PGP에서 사용하는 의사 난수 생성기

 

 

 

난수 알고리즘 선택 시 주의점

• 반드시 “이 난수 알고리즘은 암호나 보안 용도로 사용할 수 있는가”를 확인
• 난수로 뛰어난 알고리즘이라 하더라도 예측불가능성을 갖추지 못한 것은 암호나 보안 용도로 사용하면 안된다.
  • Ex. 메르센 트위스터 → $2^n-1$에서 n=소수이면, 인수분해가 안되므로 소수이다. 이때 n을 메르센 소수라고 한다.
  • Ex. 선형합동법 → 사용X
• 안전하다고 알려진 알고리즘
  • Java : java.util.Random은 보안용으로 사용하면 안되고 java.security.SecureRandom 클래스를 사용해야 한다.
  • Ruby : Random 클래스는 보안용으로 부적절하며, SecureRandom을 사용하도록 한다.