안전한 난수 만들기

안전한 난수 만들기

작성자
태인태인
카테고리
📗 스터디
작성일
2024년 08월 26일
태그
Linux
Web
🚧
이 글은 광운대학교 중앙동아리 COM’s 학술회지로서 작성되었습니다.

Introduction

우리는 디지털 시대를 살아가면서 로또 번호 추첨부터 게임 아이템 획득, 암호화 키 생성, 심지어 과학적 시뮬레이션에 이르기까지 다양한 분야에서 '무작위성'을 마주한다. 컴퓨터는 이러한 무작위성을 제공하기 위해 난수 생성기를 사용하지만, 결정론적인 기계인 컴퓨터가 생성하는 숫자가 진정으로 무작위일 수 있을까? Math.random()과 같은 일반적인 난수 생성 함수는 사실 '의사 난수'를 생성하며, 특정 알고리즘에 따라 결정론적으로 동작한다. 이는 예측 가능성이라는 약점을 내포하고 있어, 보안이 중요한 영역에서는 사용이 제한될 수밖에 없다. 본 글에서는 난수 생성의 개념과 한계점을 심층적으로 분석하고, 진정한 무작위성을 추구하는 다양한 시도들을 살펴보고자 한다. 더 나아가, 암호학적으로 안전한 난수 생성을 위한 실질적인 방법들을 제시하고, 미래의 난수 생성 기술 발전 방향에 대한 전망을 제시하고자 한다.

Background Theory

난수(Random Number)

난수는 무작위로 생성된 숫자를 의미하며, 예측 불가능성, 균등 분포, 통계적 독립성 등의 특징을 가지고 있다. 난수는 암호학, 과학적 시뮬레이션, 게임, 통계학 등 다양한 분야에서 중요한 역할을 수행한다. 암호학에서는 암호화 키 생성, 인증 토큰 생성, 보안 프로토콜 설계 등에 사용되어 정보 보안을 강화하는 데 중요한 역할을 한다. 과학적 시뮬레이션에서는 몬테카를로 시뮬레이션과 같은 과학적 모델링에서 무작위적인 입력 값을 제공하여 현실 세계를 더욱 정확하게 모사하는 데 활용된다. 게임에서는 게임 아이템 획득, 적의 움직임 패턴 생성 등에 사용되어 게임의 재미와 몰입도를 높이는 데 기여한다. 통계학에서는 샘플링, 랜덤 변수 생성 등에 사용되어 통계적 분석의 정확성을 확보하는 데 필수적이다.

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

컴퓨터는 주어진 입력에 따라 예측 가능하고 논리적인 출력을 제공하도록 설계되어 있으므로, 컴퓨터는 예측할 수 없는 암호화 키를 생성하는 데 필요한 임의의 데이터를 생성할 수 없다. 따라서 대부분의 프로그래밍 언어에서 제공하는 난수 생성 함수는 의사 난수 생성기(PRNG)를 사용한다. 유사 난수 생성기라고도 한다. PRNG는 특정 알고리즘과 Seed*을 기반으로 난수처럼 보이는 수열을 생성하는데, 이러한 알고리즘은 주로 선형 합동 생성기 (LCG), 메르센 트위스터 (Mersenne Twister) 등을 사용하며, 초기값을 통해 생성되는 수열이 결정된다. PRNG는 계산 속도가 빠르고 구현이 간편하다는 장점이 있지만, 알고리즘과 초기값을 알면 생성될 난수 수열을 예측할 수 있다는 예측 가능성, 일정한 주기를 가지고 있으며, 주기가 끝나면 동일한 수열이 반복된다는 주기성, 그리고 PRNG가 생성하는 난수는 완벽하게 균등 분포를 따르지 않을 수 있으며, 특정 패턴을 보일 수 있다는 통계적 편향의 한계점을 가진다.
*Seed(시드) : 의사 난수 생성기를 초기화하는 데 사용되는 숫자이다.

진정 난수 생성기 (TRNG, True Random Number Generator)

PRNG와 달리, 진정 난수 생성기 (TRNG) 는 물리적인 현상을 이용하여 예측 불가능한 난수를 생성한다. 대표적인 예로는 방사성 동위원소의 붕괴, 대기 노이즈, 열잡음, 양자 현상 등이 있다. 방사성 동위원소의 붕괴는 양자 역학적 현상으로, 예측 불가능한 시간 간격으로 발생하며, 대기 중의 전자기파, 열잡음 등은 무작위적인 패턴을 보이며, 이를 측정하여 난수를 생성할 수 있다. 전자 부품에서 발생하는 열잡음은 예측 불가능한 신호이며, 이를 증폭하여 난수를 생성할 수 있으며, 양자 역학의 불확정성 원리를 이용하여 예측 불가능한 난수를 생성하는 것도 가능하다. TRNG는 진정한 무작위성을 제공하지만, 구현이 복잡하고 비용이 많이 든다는 단점이 있다.
TRNG의 예시로, 웹 보안 및 CDN 솔루션을 제공하는 기업인Cloudflare에서 암호화에 필요한 난수를 생성하기 위해 라바 램프를 활용하는 독특한 방법을 들 수 있다. 라바 램프 내부의 왁스는 예측 불가능한 형태로 움직이며, Cloudflare는 이 움직임을 카메라로 촬영하여 난수 생성의 엔트로피 소스로 활용한다. 엔트로피는 무작위성의 정도를 나타내는 척도이며, 엔트로피가 높을수록 무작위성이 높다. 시드는 PRNG의 초기값으로, 시드가 다르면 생성되는 난수 수열도 다르다. 이는 물리적인 현상을 기반으로 하므로 예측이 매우 어려우며, 암호학적으로 안전한 난수를 생성하는 데 효과적이다. Cloudflare는 이러한 방식을 "LavaRand"라고 부르며, 데이터 센터의 보안을 강화하는 데 활용하고 있다.

암호학적으로 안전한 의사 난수 생성기 (CSPRNG, Cryptographically Secure Pseudo Random Number Generator)

보안 분야에서는 예측 불가능성이 매우 중요하다. 암호화 키 생성, 인증 토큰 생성 등에 PRNG를 사용할 경우, 공격자가 난수 생성 알고리즘과 초기값을 알아내어 다음 난수를 예측할 수 있기 때문이다. 따라서 보안 분야에서는 암호학적으로 안전한 의사 난수 생성기 (CSPRNG) 를 사용해야 한다. CSPRNG는 PRNG의 한 종류이지만, 보안 및 암호학적 요구 사항을 만족하도록 설계되어 충분한 수준의 예측 불가능한 난수를 생성한다. CSPRNG는 하드웨어 이벤트(마우스 움직임, 시스템 인터럽트 타이밍 등), 시스템 상태(시스템 시간, CPU 온도 등), 그리고 하드웨어 장치(CPU의 TRNG) 등 다양한 소스로부터 엔트로피를 얻어와 초기값으로 사용한다. 충분한 엔트로피를 통해 초기값을 설정하고 생성기를 초기화한 후, PRNG와 같이 내부 알고리즘을 통해 안전한 난수를 빠르게 생성한다. 또한, 새로운 엔트로피가 등장할 때마다 생성기를 재초기화하여 예측 불가능성을 더욱 높인다. CSPRNG는 TRNG만큼 안전하면서 PRNG만큼 빠르고 효율적인 난수 생성을 가능하게 한다.
대부분의 운영체제 및 프로그래밍 언어에서 이러한 CSPRNG를 사용할 수 있도록 기능을 제공하고 있다. 운영체제 및 프로그래밍 언어 별 사용가능한 함수는 다음 표와 같다.
OS/Language
Function/File
Linux, macOS
/dev/random과 /dev/urandom 파일에 운영체제 레벨에서 수집한 엔트로피 저장.
Windows
Cryptography API: Next Generation (CNG)의 BCryptGenRandom 함수
Node.js
crypto.randomBytes, crypto.randomInt(v14 이상) 함수
Python
os.urandom 함수
Java
java.security.SecureRandom 함수
C#
System.Security.Cryptography.RandomNumberGenerator.Create 함수

리눅스 커널의 난수 생성

리눅스 커널의 drivers/char/random.c 코드를 살펴보면 어떻게 엔트로피를 수집해 운영체제 커널의 get_random_bytes과 같은 함수에서 난수를 생성하는 데 활용하는지 알 수 있다. 운영체제 커널에서는 여러 하드웨어 소스에서 엔트로피를 수집하는데, 아래와 같은 루틴을 따른다.
사진2. Entropy collection routines (‘random.c’ from Linux Kernel)
사진2. Entropy collection routines (‘random.c’ from Linux Kernel)
이렇게 다양한 소스로부터 수집한 엔트로피는 Blake2s 해시 함수를 사용하여 관리되며, mix_pool_bytes 함수를 통해 새로운 엔트로피가 추가된다.
사진3. mix_pool_bytes() 함수 (‘random.c’ from Linux Kernel)
사진3. mix_pool_bytes() 함수 (‘random.c’ from Linux Kernel)
위의 루틴 중 일부를 살펴보자면, add_interrupt_randomness() 함수에서는 인터럽트 발생 시점의 타이밍, 인터럽트 번호, CPU 사이클 카운터 등을 엔트로피 풀에 추가한다.
사진4. add_interrupt_randomness() 함수 (‘random.c’ from Linux Kernel)
사진4. add_interrupt_randomness() 함수 (‘random.c’ from Linux Kernel)
add_disk_randomness() 함수는 디스크의 탐색 시간을 엔트로피 소스로 사용한다. add_timer_randomness 함수를 통해 입력 풀에 추가하고 엔트로피를 계산한다.
사진5. add_disk_randomness() 함수 (‘random.c’ from Linux Kernel)
사진5. add_disk_randomness() 함수 (‘random.c’ from Linux Kernel)
add_input_randomness() 함수는 입력 장치의 인터럽트 타이밍과 이벤트 정보를 엔트로피 소스로 사용한다. add_timer_randomness 함수를 통해 입력 풀에 추가하고 엔트로피를 계산한다.
사진6. add_input_randomness() 함수 (‘random.c’ from Linux Kernel)
사진6. add_input_randomness() 함수 (‘random.c’ from Linux Kernel)

Web Cryptography API를 사용한 Javascript에서의 난수 생성

JavaScript에서 암호학적으로 안전한 난수를 생성하기 위해 Web Crypto API를 활용할 수 있다. Web Crypto API는 브라우저에서 암호화 기능을 제공하는 API이며, Crypto.getRandomValues() 함수를 통해 암호학적으로 안전한 난수를 생성할 수 있다. 아래 예시와 같이32비트 부호 없는 정수형 배열을 생성하고, window.crypto.getRandomValues(array) 함수를 사용하여 암호학적으로 안전한 난수를 생성하여 배열에 저장한다. 생성된 난수를 0과 1 사이의 값으로 정규화하고, 정규화된 난수를 지정된 범위 내의 정수로 변환하여 사용할 수 있다.
사진7. Crypto API를 사용해 1~10의 난수를 생성하는 코드
사진7. Crypto API를 사용해 1~10의 난수를 생성하는 코드

Conclusion

컴퓨터에서 완벽한 무작위성을 구현하는 것은 불가능에 가까운 일이다. 0과 1의 디지털 세계는 본질적으로 결정론적인 특성을 지니고 있어 예측 가능하고 논리적인 출력을 제공하기 때문이다. 그러나 암호화, 시뮬레이션, 게임 등 다양한 분야에서 안전하고 신뢰할 수 있는 난수 생성은 필수적이다. 단순한 알고리즘에 기반한 PRNG는 예측 가능성이라는 치명적인 약점을 가지고 있어 보안에 취약할 수 있다. 반면, 물리적 현상에 기반한 TRNG는 높은 수준의 무작위성을 제공하지만, 구현 복잡성과 비용, 그리고 속도 측면에서 한계를 보인다. CSPRNG는 PRNG의 효율성과 TRNG의 보안성을 결합한 현실적인 대안으로, 다양한 소스에서 엔트로피를 수집하고 암호학적으로 안전한 알고리즘을 사용하여 난수를 생성한다. 리눅스 커널의 random.c 코드는 시스템 이벤트, 하드웨어 난수 등을 조합하여 CSPRNG를 구현하는 방법을 보여준다. 또한, Web Cryptography API와 같은 표준 인터페이스는 개발자가 웹에서 CSPRNG를 활용하여 안전한 난수를 생성할 수 있도록 지원한다. 앞으로 양자 컴퓨팅과 같은 새로운 기술의 발전과 함께 난수 생성 기술은 더욱 발전할 것이다. 양자 난수 생성기(QRNG)는 진정한 무작위성을 제공할 잠재력을 지니고 있다. 이러한 흐름과 함께 높은 무작위성을 가진 난수 생성은 안전한 디지털 환경을 조성하는 데 더욱 핵심적인 역할을 수행할 것이다.
 

References

➢ “유사난수” Wikipedia. (2024, Aug 25) https://ko.wikipedia.org/wiki/%EC%9C%A0%EC%82%AC%EB%82%9C%EC%88%98
➢ “Cryptographically secure pseudorandom number generator” Wikipedia. (2024, Aug 25) https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
➢ 민후. ‘컴퓨터는 랜덤을 모른다?! 난수 생성에 숨겨진 비밀” 네이버 블로그. https://m.blog.naver.com/1strider/222983680828
➢ Cloudflare. “라바 램프는 인터넷 암호화에 어떻게 도움이 될까요?” Cloudflare 블로그. https://www.cloudflare.com/ko-kr/learning/ssl/lava-lamp-encryption/
➢ Mozilla Developer Network. “Crypto.getRandomValues().” Mozilla Developer Network. https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValues

댓글

guest