Math.random()은 정말 랜덤일까?

[JavaScript] Math.random()은 정말 랜덤일까?

TL; DR;

자바스크립트는 어떻게 Math.random 함수에서 난수를 생성하는가?

• JS는 아무것도 하지 않는다. 브라우저에 따라 달라진다.
• 현재 대부분의 브라우저는 xorshift128+ 라는 알고리즘을 사용한다.
• xorshift128+에 의해 생성된 숫자는 난수를 생성하는 것이 아닌, 특정 값에 공식을 대입한 수학식이다.

Math.random()

Math.random() 은 0 이상 1미만의 부동 소숫점 난수를 생성하는 함수이며, 이 점을 이용해 아래와 같이 사용해 랜덤한 값을 만들 수 있습니다.

0 <= x < 1 난수 생성

Math.random();

두 값 사이의 난수 생성

getRandom = (min, max) => Math.random() * (max - min) + min;

두 값 사이의 (정수)난수 생성

getRandom = (min, max) => {
  min = Math.ceil(min);
  max = Math.floor(max);

  return Math.floor(Math.random() * (max - min) + min);
}

그렇다면 Math.random 함수를 호출했을 때 무슨 일이 벌어질까요? 난수를 생성하는 함수라 하는데, 정말 무작위로 생성되는 것일까요?

랜덤이란 무엇인가?

먼저, 랜덤이란 무엇인지에 대해 생각해볼 수 있습니다. 랜덤은 '무작위'로 발생하는 어떠한 패턴을 의미합니다.

동전 던지기를 해서 앞뒷 면을 맞추는 것 또한 우리는 랜덤하다 라고 생각할 수 있습니다.

하지만, 동전의 크기와 부피, 바람의 세기, 던지는 방향과 힘, 동전과 지면 사이의 거리 등을 모두 맞춰주면 동전 던지기의 결과는 항상 동일할 것입니다. 하지만 우리는 그것을 항상 일정하게 맞출 수 없기에 랜덤하다 라고 생각하는 것입니다.

컴퓨터에서 랜덤을 만들 수 있을까?

컴퓨터는 단순히 0과 1을 계산하는 매우 빠른 계산기 라는 말도 있습니다. 일상 생활에서 역시 우연의 일치로 랜덤이 만들어지는데, 단순히 입력된 값을 계산하는 컴퓨터에서는 랜덤을 어떻게 계산할 수 있을까요? 랜덤한 값을 반환하는 알고리즘을 컴퓨터를 이용해 계산해야 하는 것인데, 이 것 자체가 모순입니다.

Math.random()이 난수를 생성하는 방법

Math.random 함수는 실제로 무작위 값을 반환하지 않습니다.

놀랍게도, Math.random 함수는 난수를 생성하지 않습니다. 하지만, 무작위 값에 대한 테스트를 할 때는 매우 유용하게 사용될 수 있습니다.

난수 생성 알고리즘은 PRNG(pseudo-random number generator)이라고도 불리며, K&R C 프로그래밍 언어 책에서의 pseudo-random 반환 함수는 아래와 같이 정의되어 있습니다.

unsigned long int rand_next = 1;

int rand () {
  rand_next = rand_next * 1103515245 + 12345;

  return ((unsigned int)(rand_next / 65536) % 32768);
}

위 C 코드를 js로 변경하면 아래와 같이 됩니다.

let rand_next = 1;

const rand = () => {
  rand_next = rand_next * 1103515245 + 12345;

  return Math.round(rand_next / 65536) % 32768;
}

위 두 코드는 C에서 값을 처리하는 방법과 js에서 값을 처리하는 방법이 달라 다른 결과를 내보이며, 단순 이래를 돕기 위한 코드입니다.

난수 생성 알고리즘은 무작위한 값을 생성할 수 없습니다. 특정 공식을 사용해 무작위로 보일 수 있지만, 결국 난수를 계속해서 생성하면 반복되어 어떠한 패턴을 나타냅니다.

난수 생성 알고리즘은 이 패턴이 나오기까지의 기간 즉, 몇 번의 반복 끝에 패턴을 유추할 수 있는지에 따라 품질이 달라지며, 이 수가 크면 클 수록 크래킹하기가 어려워집니다. 그렇다면 JavaScript가 사용하는 PRNG는 무엇일까요?

브라우저에 따라 다릅니다.

Math.random() 을 구현하는 방법은 정형화되어 있지 않으며, PRNG 알고리즘이 하드코딩되어 함께 제공되지도 않습니다. 대신 ECMAScript 사양을 준수하여 알고리즘을 사용합니다.

아래는 Math.random()의 ECMAScript Language Spec 입니다.

Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

위 사항이 지침이며, 이것을 따르는 것은 결국 브라우저가 해야하는 일입니다. 브라우저가 이를 수행하기 위해 Marsenne-Twister , Multiply With Carry 또는 Linear Congruential Generator 등의 알고리즘을 사용했었습니다.

결국 중요한 것은 브라우저가 계산에 사용할 알고리즘을 결정하고 있다는 것입니다. 위 알고리즘을 사용하는 것은 이전의 방식이며, 현재 주요 브라우저의 경우 위 알고리즘의 사용을 멈추고 xorshift128+ 알고리즘을 사용하고 있습니다.

해당 알고리즘은 이전 알고리즘보다 난수인 '척'을 더 잘 하고 있으며, 매우 가볍고 계산 속도가 빨라서 전반적으로 채택되었습니다.

각 브라우저별로 해당 알고리즘을 어떻게 사용하고 있는지는 알 수 없습니다. 하지만 xorshift128+ 알고리즘의 기본적인 동작 방법은 알 수 있습니다.

const state = [0, 1];

function xorshift128plus () {
  let s1 = state[0];
  let s0 = state[1];

  state[0] = s0; s1 ^= s1 << 23;
  s1 ^= s1 >> 17; s1 ^= s0;
  state[1] = s1;

  return state[0] + state[1];
}

위 코드는 단순 계산과 대입을 반복합니다. 하지만 위 코드를 보고 s1 ^= s1 << 23? 이게 뭐야? 라고 얘기할 수 있습니다. 이것은 비트 연산자이며, 1과 0의 수준에서 데이터를 조작하는 연산자입니다. 간단히 연산자에 대한 소개를 하겠습니다.

<< (좌측 쉬프트)

1. 10 << 4 이라 할 때 10을 2진수로 변경합니다 (0000 1010).
2. 변경한 2진수의 좌측 4개의 수를 좌측으로 밀어냅니다 (1010 0000).
3. 10 << 4를 할 경우, 32 + 128 = 160 이 됩니다.

>> (우측 쉬프트)

• 좌측 쉬프트와 반대로 동작합니다.

=^ (xor 대입 연산자)

• xor 연산자의 경우 and, or과 같은 논리 연산자입니다.
• true and true => true, true or false => true
• 위와 같이 값을 전달받는데 true와 false를 받는 경우에만 true를 반환합니다.
  • true xor false => true
  • true xor true => false
  • false xor false => flase

이것은 비트 연산에도 사용할 수 있습니다. 13과 26을 xor 연산하도록 하겠습니다.

1. 우선 13을 2진수로 변경합니다(0000 1101)
2. 26 역시 2진수로 변경합니다(0001 1010).

0000 1101
0001 1010
---
0001 0111

→ 즉 계산 결과, 16 + 4 + 2 + 1 = 23이 됩니다.

이제 xorshift128plus 함수를 이해할 수 있게 되었으며, 컴퓨터에서의 난수는 사실 수학적 공식에 의해 만들어지는 값이라는 것을 알게 되었습니다.

Math.random()은 왜 위험한가?

https://hackerone.com/reports/678989

crypto-js에서 난수 생성을 위해 Math.random() 함수를 사용할 때 시드가 동일한 취약점이 발견된 적이 있습니다.

$ node --random_seed=42 -e "console.log(require('crypto-js').lib.WordArray.random(16))"
{ words: [ -1477405629, 964516052, 1254255372, 1089500106 ],
  sigBytes: 16 }

$ node --random_seed=42 -e "console.log(require('crypto-js').lib.WordArray.random(16))"
{ words: [ -1477405629, 964516052, 1254255372, 1089500106 ],
  sigBytes: 16 }

Math.random 함수는 시드 값을 설정할 수 없습니다. 때문에 내부 시드값과 Math.random 함수에서 사용하는 알고리즘이 밝혀진다면 매우 치명적일 것입니다.

위 사건으로 인해 시간을 들이면 내부 Math.random 함수의 시드 값을 확인하는 것이 가능할 것이라고 유추되어서 Math.random 함수는 현재 crypto-js에서 사용되지 않습니다.

어떻게 해결할 수 있나?

Browser

• window.crypto.getRandomValues

Node.js

• require('crypto').randomBytes

---

• Xorshift+ wiki
• V8 math-random
• Google Chrome 3.0 (Beta) Math.random vulnerability