당신과 나, 그리고 우리 둘 다 신뢰하는 서버로 컴퓨터 포커를하자. 서버는 우리가 플레이하기 직전에 32 비트 시드로 초기화 된 의사 난수 생성기를 사용합니다. 약 40 억 개의 갑판이 있습니다.

나는 내 손에 5 장의 카드를받습니다. 분명히 우리는 Texas Hold ‘Em을하고 있지 않습니다. 카드가 나에게, 하나는 당신에게, 하나는 나에게, 하나는 당신에게, 등등 처리된다고 가정하자. 덱에 첫 번째, 세 번째, 다섯 번째, 일곱 번째 및 아홉 번째 카드가 있습니다.

이전에 의사 난수 생성기를 각 시드마다 한 번씩 40 억 번 실행하고 각각에 대해 생성 된 첫 번째 카드를 데이터베이스에 기록했습니다. 첫 번째 카드가 스페이드의 여왕이라고 가정합니다. 이는 가능한 모든 덱 52 개 중 하나에서 첫 번째 카드로만 표시되므로 가능한 덱을 40 억에서 8 천만 정도 정도로 줄였습니다.

내 두 번째 카드가 세 개의 하트라고 가정합니다. 이제 스페이드 여왕을 첫 번째 숫자로 만드는 8 천만 종자를 사용하여 RNG를 8 천만 번 더 실행합니다. 이 작업에는 몇 초가 걸립니다. 나는 세 번째 카드, 즉 내 손에 두 번째 카드로 세 개의 하트를 생성하는 모든 데크를 기록합니다. 이는 다시 데크의 약 2 %에 불과하므로 이제는 2 백만 데크로 줄었습니다.

제 손에있는 세 번째 카드가 7 개의 클럽이라고 가정합니다. 나는 두 카드를 다루는 200 만 종자 데이터베이스를 가지고있다. 7 개의 클럽을 세 번째 카드로 만드는 데크의 2 %를 찾기 위해 RNG를 2 백만 번 더 실행하면 4 만 데크에 불과합니다.

이것이 어떻게 진행되는지 봅니다. RNG 40000을 네 번 더 실행하여 네 번째 카드를 생산하는 모든 씨앗을 찾고 800 데크까지 데려 간 다음 800 번 더 실행하여 다섯 번째 카드를 생산하는 ~ 20 개의 씨앗을 얻습니다. 20 개의 카드 덱을 생성하면 20 개의 손 중 하나가 있다는 것을 알고 있습니다. 또한, 나는 다음에 무엇을 그릴 지에 대해 아주 잘 알고 있습니다.

이제 왜 진정한 무작위성이 중요합니까? 당신이 설명하는 방식으로, 당신은 분배 가 중요 하다고 생각 하지만, 분배는 프로세스를 무작위로 만드는 것이 아닙니다. 예측 불가능 성은 공정을 무작위로 만드는 것입니다.

최신 정보

(현재 구조적이지 않기 때문에 삭제 된) 의견에 따르면, 이것을 읽은 사람들의 적어도 0.3 %가 내 요지에 대해 혼란스러워합니다. 사람들이 점을 내가 만든, 또는 악화되지 않은에 대해 주장 할 때, 주장 에 대해 나는 점 않았다 내가 그들을하지 않은 가정을 확인한 다음 나는 더 명확하게 조심스럽게 설명 할 필요가 있음을 알고있다.

단어 배포와 관련 하여 특히 혼란스러워 보이므로 사용법을 신중하게 호출하고 싶습니다.

당면한 질문은 다음과 같습니다.

• 의사 난수와 실제 난수는 어떻게 다릅니 까?
• 차이점이 왜 중요한가요?
• 차이점은 PRNG의 결과 분포와 관련이 있습니까?

포커를 할 수있는 임의의 카드 덱을 생성하는 완벽한 방법을 고려하여 시작합시다 . 그런 다음 데크 생성을위한 다른 기술이 어떻게 다른지 살펴보고 그 차이를 활용할 수 있는지 살펴 보겠습니다.

마술 상자에 레이블이 붙어 있다고 가정 해 봅시다 TRNG. 입력으로 우리는 정수 n을 1보다 크거나 같게하고, 그 출력으로서 1과 n 사이의 정수 (정수)를 제공합니다. 상자의 출력은 전체적으로 예측할 수 없으며 (1 이외의 숫자가 지정된 경우) 1과 n 사이의 숫자는 다른 것과 같습니다. 즉, 분포 가 균일 하다는 것입니다 . (우리가 수행 할 수있는 다른 고급 무작위 통계 검사가 있습니다. 나는이 주장이 내 주장에 맞지 않기 때문에이 점을 무시하고 있습니다. TRNG는 가정에 의해 완벽하게 통계적으로 무작위입니다.)

우리는 섞이지 않은 카드 덱으로 시작합니다. 상자에 1에서 52 사이의 숫자, 즉 TRNG(52). 숫자가 무엇이든, 우리는 분류 된 덱에서 그 많은 카드를 세어 그 카드를 제거합니다. 뒤섞인 데크에서 첫 번째 카드가됩니다. 그런 다음 TRNG(51)두 번째 카드를 선택 하도록 요청 하고 동일한 작업을 수행합니다.

그것을 보는 또 다른 방법은 52입니다! = 52 x 51 x 50 … x 2 x 1 가능한 데크, 대략 2 ²²⁶ 입니다. 우리는 그중 하나를 무작위로 선택했습니다.

이제 우리는 카드를 다룹니다. 내 카드를 볼 때 어떤 카드를 가지고 있는지 전혀 모릅니다. (내가 가지고있는 카드가 없다는 명백한 사실을 제외하고) 같은 확률로 모든 카드가 될 수 있습니다.

제가 이것을 명확하게 설명하도록하겠습니다. 우리는 각 개별 출력의 균일 한 분포 를 가지고 있습니다 TRNG(n). 각각 1과 n 사이의 숫자를 확률 1 / n으로 선택합니다. 또한이 프로세스의 결과로 52 개 중 하나를 선택했습니다! 1/52의 확률! 그래서 분포 가능한 데크 가능한 갑판의 위에 세트가 있다 또한 균일.

괜찮아.

이제 레이블이 적은 마법 상자가 있다고 가정 해 봅시다 PRNG. 사용하기 전에 부호없는 32 비트 숫자 로 시드 해야합니다 .

ASIDE : 왜 32 입니까? 64 또는 256 또는 10000 비트 숫자로 시드 할 수 없습니까? 확실한. 그러나 (1) 실제로 대부분의 상용 PRNG는 32 비트 숫자로 시드되며, (2) 시드를 만들기 위해 10000 비트의 임의성이 있으면 PRNG를 사용하는 이유는 무엇입니까? 이미 10000 비트의 무작위 소스가 있습니다!

어쨌든 PRNG의 작동 방식으로 돌아갑니다. 시딩 후 사용하는 것과 같은 방식으로 사용할 수 있습니다 TRNG. 즉, 숫자 n을 전달하면 1과 n 사이의 숫자를 포함합니다. 또한, 그 출력의 분포는 다소 균일 합니다. 즉 PRNG, 우리가 1에서 6 사이의 숫자를 요청할 때, 씨앗이 무엇이든 관계없이 대략 6 분의 1의 1, 2, 3, 4, 5 또는 6을 얻습니다.

나는이 점을 몇 번 강조하고 싶다. 왜냐하면 그것은 특정 주석가들을 혼란스럽게 만드는 점이기 때문이다. PRNG의 분포는 적어도 두 가지 방식으로 균일하다. 먼저 특정 종자를 선택한다고 가정하십시오. PRNG(6), PRNG(6), PRNG(6)...백만 번의 시퀀스 는 1에서 6 사이의 숫자 분포를 균등하게 분배 할 것으로 예상됩니다 . 둘째, 백만 개의 다른 시드를 선택하고 각 시드에 대해 PRNG(6) 한 번 호출 하면 다시 1에서 5까지의 균일 한 분포가 예상됩니다. 6. 이러한 작업 중 하나에서 PRNG의 균일 성은 내가 설명하는 공격과 관련이 없습니다 .

이 과정은 상자의 동작이 실제로 완전히 결정적이므로 의사 난수 라고합니다. 시드에 따라 2 ^{개의 32} 가지 가능한 동작 중 하나를 선택합니다 . 즉, 일단 시딩되면 균일 한 분포를 PRNG(6), PRNG(6), PRNG(6), ... 갖는 일련 의 숫자를 생성 하지만, 그 순서는 전체적으로 시드에 의해 결정됩니다. PRNG (52), PRNG (51) … 등의 일련의 호출에 대해 2 ^{개의 32 개의} 가능한 시퀀스가 ​​있습니다. 씨앗은 본질적으로 우리가 얻는 것을 선택합니다.

데크를 생성하기 위해 서버는 이제 시드를 생성합니다. (우리는 다시 그 시점에 온 것이다 어떻게?.) 그런 다음 그들은 전화 PRNG(52), PRNG(51)이전과 비슷한 갑판을 생성하는 등등합니다.

이 시스템은 내가 설명한 공격에 취약합니다. 먼저 서버를 공격하기 위해 먼저 상자 자체에 0을 시드하고 요청 PRNG(52)하고 적어 둡니다. 그런 다음 1로 다시 시드하고 요청하고 PRNG(52)최대 2 ³² -1까지 기록하십시오.

이제 PRNG를 사용하여 데크를 생성하는 포커 서버는 어떻게 든 시드를 생성해야합니다. 그들이 그렇게하는 것은 중요하지 않습니다. 그들은 TRNG(2^32)정말 무작위 씨앗을 얻기 위해 전화 를 걸 수 있습니다. 또는 그들은 현재 시간을 씨앗으로 삼을 수 있습니다. 나는 당신이 몇시인지 알고 있습니다. 내 공격의 요점은 데이터베이스가 있기 때문에 중요하지 않다는 것입니다 . 첫 카드를 볼 때 가능한 씨앗의 98 %를 제거 할 수 있습니다. 두 번째 카드를 볼 때 98 % 더 많은 것을 제거 할 수 있습니다. 결국 몇 가지 가능한 씨앗을 얻을 수있을 때까지 당신의 손에 무엇이 있는지 알 수 있습니다.

다시 한 번, 여기서 백만 번을 호출 PRNG(6)하면 각 숫자의 약 1/6을 얻게 된다는 가정을 강조하고 싶습니다 . 그 분포는 (거의) 균일 하며, 그 분포의 균일성에 관심이 있다면 괜찮습니다. 문제의 요점은 우리가 관심 을 갖는 다른 배포판이 PRNG(6)있습니까? 대답은 ‘ 예’ 입니다. 우리는 예측할 수없는 것도 염려 합니다.

문제를 보는 또 다른 방법 은 PRNG가 2 ^{32 개의} 가능한 동작 중에서 선택하기 때문에 백만 PRNG(6)번의 호출을 분배 해도 괜찮을 수 있지만 가능한 모든 데크를 생성 할 수는 없습니다. ^2,226 개의 데크 중 2 ³² 개만 생성 할 수 있습니다 . 작은 분수. 따라서 모든 데크 세트에 대한 분포 는 매우 나쁩니다. 그러나 여기서도 근본적인 공격 은 작은 산출량으로 과거와 미래의 행동 을 성공적으로 예측할 수 있다는 점 입니다. PRNG

이것을 세 번 또는 네 번 말씀 드리고자합니다. 여기에는 세 가지 분포가 있습니다. 첫째, 랜덤 32 비트 시드를 생성하는 프로세스의 분포. 그것은 완벽하게 임의적이고 예측할 수 없으며 균일 할 수 있으며 공격은 여전히 ​​유효합니다 . 둘째,에 백만 번의 전화 분배 PRNG(6). 그것은 완벽하게 균일 할 수 있으며 공격은 여전히 ​​작동합니다. 셋째, 의사 난수 처리 과정에서 선택한 데크의 분포에 대해 설명했습니다. 그 분포는 매우 열악합니다. IRL 가능한 데크의 작은 부분 만 선택할 수 있습니다. 공격은 출력에 대한 부분적인 지식을 기반으로 PRNG의 행동 예측 가능성 에 달려 있습니다.

ASIDE :이 공격은 공격자가 PRNG에서 사용하는 정확한 알고리즘이 무엇인지 알고 있거나 추측 할 수 있어야합니다. 그것이 현실적인지 아닌지는 공개 된 질문입니다. 그러나 보안 시스템을 설계 할 때 공격자가 프로그램의 모든 알고리즘을 알고 있더라도 공격으로부터 보호되도록 보안 시스템을 설계해야합니다 . 다시 말해, 보안을 유지하기 위해 보안을 유지해야하는 보안 시스템 부분을 “키”라고합니다. 시스템이 보안에 의존하여 사용하는 알고리즘에 의존하는 경우 키에는 해당 알고리즘이 포함 됩니다. 그것은 매우 약한 입장입니다!

계속합니다.

이제라는 레이블이 붙은 세 번째 마법 상자가 있다고 가정 해 봅시다 CPRNG. 의 암호화 강도 버전입니다 PRNG. 32 비트 시드가 아닌 256 비트 시드가 필요합니다. 그것은 PRNG종자가 2,256 ^개의 가능한 행동 중 하나에서 선택하는 특성 과 공유됩니다 . 다른 기계와 마찬가지로 CPRNG(n)1과 n 사이의 균일 한 결과 분포 를 생성하기 위한 많은 호출이 1 / n의 시간마다 발생한다는 특성이 있습니다. 우리는 그것에 대해 우리의 공격을 실행할 수 있습니까?

우리의 원래 공격은 씨앗에서까지 ^{32 개의} 매핑 을 저장해야 합니다 PRNG(52). 그러나 ²²⁵⁶ 은 훨씬 더 큰 숫자입니다. CPRNG(52)여러 번 실행 하여 결과를 저장하는 것은 완전히 불가능 합니다.

그러나 씨앗에 대한 사실을 추론 할 수있는 다른 방법 이 있다고 가정 해 봅시다 CPRNG(52). 우리는 지금까지 꽤 멍청했습니다. 가능한 모든 조합을 무차별하게 적용했습니다. 우리는 마법 상자를 들여다보고 그것이 어떻게 작동하는지 알아 내고, 출력을 기반으로 씨앗에 관한 사실을 추론 할 수 있습니까?

제 자세한 설명이 너무 복잡하지만 추론 없음 불가능되도록 CPRNGs 교묘하게 설계되어 어떠한 의 첫 번째 출력의 씨앗에 대한 유용한 사실 CPRNG(52)또는에서 어떤 출력의 일부를 얼마나 큰 상관없이 .

이제 서버가 CPRNG데크를 생성 하는 데 사용한다고 가정 해 봅시다 . 256 비트 시드가 필요합니다. 그 씨앗을 어떻게 선택합니까? 공격자가 예측할 수있는 값을 선택하면 갑자기 공격이 다시 실행됩니다 . 우리는 2 개의 확인할 수있는 경우 ²⁵⁶ 가능한 씨앗을 만 사십억 그들의 서버에 의해 선택 될 가능성이 후, 우리는 다시 사업에 있습니다 . 우리는이 공격을 다시 시작할 수 있으며, 생성 될 수있는 적은 수의 씨앗에만주의를 기울입니다.

따라서 서버는 256 비트 숫자가 균일하게 분배 되도록해야합니다. 즉, 가능한 모든 시드가 1/2 ^256의 확률로 선택됩니다 . 기본적으로 서버는에 TRNG(2^256)-1대한 시드를 생성하기 위해 호출해야합니다 CPRNG.

서버를 해킹하고 피어링하여 어떤 시드가 선택되었는지 확인할 수 있습니까? 이 경우 공격자는 CPRNG의 완전한 과거와 미래를 알고 있습니다. 서버 작성자는이 공격을 막아야합니다! (물론이 공격을 성공적으로 수행 할 수 있다면 돈을 은행 계좌로 직접 이체 할 수도 있습니다. 그래서 그다지 흥미롭지 않을 수도 있습니다. 요점은 씨앗은 추측하기 어려운 비밀이어야합니다. 실제로 임의의 256 비트 숫자는 추측하기가 어렵습니다.)

심층 방어에 대한 이전 시점으로 돌아 가면 256 비트 시드 가이 보안 시스템 의 핵심 입니다. CPRNG의 개념은 키가 안전한 한 시스템이 안전하다는 것입니다 . 알고리즘에 대한 다른 모든 사실을 알고 있더라도 키를 비밀로 유지할 수있는 한 상대방의 카드는 예측할 수 없습니다.

시드는 비밀이 유지되고 균일하게 분산되어 있어야합니다. 그렇지 않은 경우 공격을 수행 할 수 있기 때문입니다. 우리는 산출물의 분포 CPRNG(n)가 균일 하다고 가정합니다 . 가능한 모든 데크 세트에 대한 분포는 어떻습니까?

2있다 : 당신은 말할 수 ²⁵⁶ CPRNG에 의해 가능한 시퀀스 출력, 만 2가 ²²⁶ 가능한 데크. 따라서 데크보다 시퀀스가 ​​더 많으므로 괜찮습니다. 가능한 모든 IRC 데크는 이제이 시스템에서 (높은 확률로) 가능합니다. 그리고 그것은 좋은 주장입니다 …

2 ²²⁶ 은 52! 의 근사값 입니다. 나누십시오. (2) ²⁵⁶ / 52! 한 가지 때문에 52가 될 수 있습니다. 3으로 나눌 수 있지만 2의 거듭 제곱은 없습니다! 이것은 정수가 아니기 때문에 모든 데크가 가능한 상황 이지만 일부 데크는 다른 데크보다 가능성이 높습니다 .

확실하지 않으면 숫자가 작은 상황을 고려하십시오. 세 개의 카드 A, B 및 C가 있다고 가정합니다. 8 비트 시드가있는 PRNG를 사용하여 256 개의 가능한 시드가 있다고 가정하십시오. PRNG(3)시드 에 따라 256 개의 가능한 출력이 있습니다 . 256을 3으로 균등하게 나눌 수 없기 때문에 1/3을 A로, 1/3을 B로, 1/3을 C로하는 방법은 없습니다.

마찬가지로 52는 2 ²⁵⁶ 으로 균등하게 분할되지 않으므로 선택한 첫 번째 카드로 일부 카드에 대한 편향과 다른 카드와의 편향이 있어야합니다.

32 비트 시드가있는 원래 시스템에는 엄청난 편향이 있었고 가능한 대부분의 데크는 생산되지 않았습니다. 이 시스템에서는 모든 데크를 생산할 수 있지만 데크 분배에는 여전히 결함이 있습니다. 일부 데크는 다른 데크 보다 약간 더 높습니다.

이제 문제는 : 이 결함에 기반한 공격이 있습니까? 대답은 실제로는 아닐 것입니다 . CPRNG는 시드가 실제로 무작위 인 경우 와와 의 차이를 계산하는 것이 계산적으로 불가능 하도록 설계되었습니다 .CPRNGTRNG

자, 요약하자.

의사 난수와 실제 난수는 어떻게 다릅니 까?

그것들은 그들이 보여주는 예측 수준이 다릅니다.

• 진정한 난수는 예측할 수 없습니다.
• 시드를 결정하거나 추측 할 수 있으면 모든 의사 난수를 예측할 수 있습니다.

차이점이 왜 중요한가요?

시스템의 보안이 예측할 수없는 응용 프로그램이 있기 때문에 .

• TRNG를 사용하여 각 카드를 선택하면 시스템을 사용할 수 없습니다.
• CPRNG를 사용하여 각 카드를 선택하는 경우 시드를 예측할 수없고 알 수없는 경우 시스템이 안전합니다.
• 시드 공간이 작은 일반 PRNG를 사용하면 시드를 예측할 수 없는지 또는 알 수 없는지에 관계없이 시스템이 안전하지 않습니다. 작은 종자 공간은 내가 설명한 종류의 무차별 대입 공격에 취약합니다.

차이는 PRNG의 출력 분포와 관련이 있습니까?

개별 호출 에 대한 분배의 균일 성 또는 부족 RNG(n)은 내가 설명한 공격과 관련이 없습니다.

우리가 살펴본 바와 같이, a PRNG와 CPRNG가능한 모든 데크의 개별 데크를 선택할 확률이 낮게 분포되어있다. 은 PRNG상당히 나쁘다, 그러나 둘 다 문제가있다.

질문 하나 더 :

TRNG가 CPRNG보다 훨씬 낫고 PRNG보다 훨씬 낫다면 왜 CPRNG 나 PRNG를 사용합니까?

두 가지 이유가 있습니다.

첫째 : 비용. TRNG는 비싸다 . 진정한 난수 생성은 어렵습니다. CPRNG 는 시드에 대해 TRNG를 한 번만 호출하면 임의로 많은 호출에 대해 좋은 결과를 제공 합니다. 단점은 물론 그 씨앗을 비밀로 유지해야한다는 것입니다 .

둘째 : 때때로 우리 는 예측 성을 원하며 우리가 관심을 갖는 것은 좋은 분포입니다. 테스트 스위트의 프로그램 입력으로 “임의의”데이터를 생성하고 버그가 표시되면 테스트 스위트를 다시 실행하면 버그가 다시 생성된다는 것이 좋을 것입니다!

나는 그것이 훨씬 더 명확 해지기를 바랍니다.

마지막으로, 이것을 즐겼다면 무작위와 순열에 관한 추가 내용을 읽을 수 있습니다.

• 무작위 데이터를 균등하게 분배했다고 가정합니다. 주어진 비 균일 분포로 어떻게 변환합니까?
• 일부 GUID가 무작위로 생성되는 이유는 무엇입니까? 모든 비트가 무작위입니까? (아니요) 진정한 무작위성의 원천으로 GUID에 의존 할 수 있습니까? (아니!)
• 팩 토릭 표기법을 사용하여 큰 난수를 어떻게 생성 할 수 있습니까?
  • 이를 임의 순열로 바꾸려면 어떻게해야합니까?
• 랜덤 순열에 대해 여기에 설명 된 공격을 어떻게 적용 할 수 있습니까?
• 구현하기 위해 나머지 기술을 사용하여 얼마나 많은 바이어스가 도입 RNG(n)됩니까?

답변

 sqrt(N * 35.0 / 12.0).

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

( RC4( IV + Key ) ) XOR (message)