무작위성

암호학

2025.10.08 22:28

보안 및 암호학 목적으로 난수가 필요하다면 난수는 예측할 수 없어야 한다.
애플리케이션은 일반적으로 무작위정을 운영체제에 의존하며, 운영체제는 실행되는 장치 유형에 따라 다른 트릭을 사용하여 무작위성을 수집한다. 무작위성의 일반적인 근원(entrypy source)은 하드웨어 인터럽트(마우스 움직임 등), 소프트웨어 인터럽트, 하드디스크 탐색 시간 등의 타이밍이 될 수 있다.
열 잡음과 같은 예측불가한 외부 물리현상으로 무작위적을 추출하는 하드웨어 난수 생성기를 진난수 생성기(TRNG, True random number generators)라고도 한다.
무작위성 추출기(randommness extractor)는 이런 여러 노이즈 소스를 정리하고 수집해야 한다. 허나 많은 난수를 빠르게 필요로 하는 경우 이 프로세스가 병목이 될 수 있다.
따라서 OS는 의사 난수 생성기(PRNG, pseudorandom number generator)를 사용해 난수 생성을 최적화한다.
- 암호학적으로 안전한 PRNG를 CPRNG(Cryptographically secure PRNG), DRBG(Deterministic random bit generator)라 부르기도 한다.
- PRNG에는 시드라는 초기 비밀이 필요하다. 동일한 시드를 사용하면 PRNG가 동일한 난수 시퀀스를 생성한다.
- Forward secrecy: 상태가 손상된 경우 이전에 생성된 난수를 검색할 수 없다.
- Backward secrecy: PRNG의 상태가 손상되어도 새로운 엔트로피를 재주입할 수 있다. 미래 비밀성, 손상 후 보안(PCS)이라고도 한다.
리눅스는 ChaCha20 스트림 암호 기반 PRNG를, 맥 OS는 SHA-1 해시 함수 기반의 PRNG를 사용한다. 맥과 리눅스에선 커맨드라인 도구 dd를 사용하여 /dev/urandom의 16바이트를 읽을 수 있다. (단, 장치를 부팅한 후 너무 일찍 사용하면 충분한 엔트로피를 제공하지 않을 수 있다. 리눅스에서는 /proc/sys/kernel/random/entropy_avail로 현재 엔트로피 레벨을 확인할 수 있다.)
Terminal window
```
$ dd if=/dev/urandom bs=16 count=1 2> /dev/null | xxd -p
3a8075d386520f5247b4ea56d6d2807f
```
공개적 무작위성
- 많은 참가자가 확인할 수 있는 방식으로 임의의 스트림을 생성해야하는 경우가 있을 수 있다.
- 이 스트림은 예측할 수 없으며 관측자가 변경할 수 없어야한다.
- 검증 가능한 방식으로 난수를 얻기 위한 VRF(Verifiable random function)이란 구조가 있다. VRF는 아래 단계로 동작한다.
  1. 키 페어를 생성하고 검증 키와 공개 시드를 게시한다.
  2. 난수를 생성하려면 공개 시드에 서명하고 서명을 해시한다. 다이제스트는 난수며, 서명도 증거로 게시된다.
  3. 누구나 난수를 검증하기 위해 서명을 해시하여 난수와 일치하는지 확인하고, 공개 시드 및 검증키로 서명이 올바른지 확인할 수 있다.
- 이 구조는 공개 시드를 카운터처럼 사용하여 많은 난수를 생성하도록 확장될 수 있다. 그런데 서명이 고유하고 공개 시드가 고정되어 있기에 서명자가 다른 난수를 생성할 방법이 없다.
  - 이를 해결하기 위해 draft-irtf-cfrg-vrf-08에선 ECDSA를 사용하여 VRF를 구현하는 방법을 지정했다.
- decentralized randomness beacon
  - 일반적인 솔류션은 단일 키가 아닌 임곗값 분산 키(threshold distributed key)와 함께 VRF를 사용하는 것이다. 임곗값 분산 키는 많은 참가자에게 분할되고, 임곗값만큼의 참가자가 메시지에 서명한 후에만 주어진 메시지에 고유한 유효한 서명을 생성하는 키다.
  - 인기있는 탈중앙화 무작위 비컨 중 하나로 drand가 있으며 여러 조직과 대학에서 공동으로 운영한다. https://leagueofentrypy.com에서 사용할 수 있다.
키 파생(KDF, Key derivation function)
- 하나의 비밀에서 더 많은 비밀을 도출하는데 사용할 수 있는 구조는 PRNG만 있는 것이 아니다. 이러한 키 파생은 암호학에서 자주 발생하는 패턴이다.
- 키 파생 함수는 여러 면에서 PRN와 비슷하지만 아래와 같은 차이점이 았다.
  - KDF에서는 (충분한 엔트로피가 있는 한) 균일하게 무작위인 비밀이 반드시 필요하지는 않다. 덕분에 키 교환 출력으로부터 비밀을 유도하는 데 유용하며, 엔트로피는 높지만 편향된 결과를 출력한다. 반면 이렇게 생성된 비밀은 균일하게 무작위적이다.
  - KDF는 보통 참가자가 동일한 키를 여러 번 다시 파생시켜야하는 프로토콜에 사용된다. 그래서 KDF에서는 결정론적 성격을 기대하는 반면, PRNG는 더 많은 엔트로피로 자주 다시 시드함으로써 역방향 비밀성을 제공하기도 한다.
  - KDF는 보통 많은 난수를 생성하도록 설계되지 않았다.
HKDF(HMAC-based KDF)
- RFC 5869에 정의된 KDF로, HMAC을 사용하여 입력 키 자료(IKM, Input Keying Material)로부터 암호학적으로 강력한 키를 파생한다.
- HKDF는 Extract-then-Expand 패턴으로 동작하는 2단계 구조를 가진다.
- HKDF-Extract
  - 입력 키 자료(IKM)와 선택적 salt를 받아 고정 길이의 의사 난수 키(PRK, Pseudorandom Key)를 추출한다.
  - PRK = HMAC-Hash(salt, IKM)
  - IKM이 편향되어 있거나 충분히 무작위적이지 않은 경우에도 균일하게 분산된 PRK를 생성한다.
  - salt는 선택적이지만 사용하는 것이 권장된다. salt가 없으면 해시 길이만큼의 0 바이트가 사용된다.
  - Diffie-Hellman 키 교환 결과처럼 엔트로피는 높지만 균일하지 않은 입력에 특히 유용하다.
- HKDF-Expand
  - PRK와 선택적 컨텍스트 정보(info), 원하는 출력 길이(L)를 받아 출력 키 자료(OKM, Output Keying Material)를 생성한다.
  - info 매개변수는 동일한 IKM에서 서로 다른 용도의 키를 파생하는 데 사용된다. (예: “encryption key”, “MAC key”)
  - 최대 255 × HashLen 바이트까지 확장 가능하다. (SHA-256의 경우 8160바이트)
  - 내부적으로 HMAC을 반복 적용하여 원하는 길이의 출력을 생성한다.

참고

응용Keytool 암호학Alice and Bob 암호학Kerckhoffs's principle 암호학암호학 goBSON goCommand line argument, flag