Computer Science/Network Security

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

y-seo 2023. 12. 6. 11:38

 

 
 

난수의 용도

  • 키 생성
    • 난수를 안쓰면 인간의 의지가 들어가서 예측이 쉬워진다.
    • 대칭 암호나 메세지 인증 코드 (공개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을 사용하도록 한다.