CPython PRNG의 출력에서 시드를 역으로 찾기

AI 요약

TimeLord는 CPython의 의사난수 생성기(PRNG)가 만들 특정 출력열을 먼저 정하고, 그 출력열을 내놓는 정수 시드를 거꾸로 구성하는 Python 데모입니다. 기본 예시는 동전 던지기 코드가 앞면 100번을 연속으로 출력하게 만드는 시드입니다. 최대 1,000번 연속 앞면을 만들며, 원하는 문장을 출력하는 시드도 생성합니다. 난수 생성 도중 상태를 바꾸거나 setstate()를 호출하지 않습니다. 미리 계산한 정수를 일반적인 random.Random(seed)에 넣으면 됩니다.

드물게 나온 결과와 미리 고른 결과

공정한 동전을 독립적으로 100번 던져 앞면만 나올 확률은 매우 낮습니다. 하지만 TimeLord는 시드를 먼저 무작위로 뽑은 다음 결과를 관찰하지 않습니다. 원하는 출력부터 정하고, 그 결과가 나오도록 시드를 역으로 찾습니다. 따라서 출력은 재현 가능해도 시드가 독립적이고 무작위로 선택됐다는 뜻은 아닙니다. 결과가 사전에 정해져 있었다고 가정해 계산한 확률과, 결과를 얻으려고 여러 조건을 살핀 뒤 선택한 경우의 확률은 다릅니다. 글은 이 차이를 사후 선택(post-selection), 다중 비교 효과(look-elsewhere effect), 선택 편향(selection bias)과 연결합니다.

MT19937 출력에 제약을 걸기

CPython의 표준 random 모듈은 MT19937 Mersenne Twister를 사용합니다. 글의 동전 예시에서 randrange(2)는 getrandbits(2)를 호출하고, 값이 2보다 작지 않으면 다시 뽑습니다. 출력값이 앞면에 해당하는 1이 되려면 상위 두 비트를 01로 맞추면 됩니다. 이 값은 이미 2보다 작으므로 재추첨도 일어나지 않습니다. 따라서 앞면 하나마다 출력 비트 두 개를 제약합니다. 앞면 100번에는 200개, 1,000번에는 2,000개의 제약이 필요합니다.

MT19937의 상태는 약 20,000비트 규모입니다. 글은 MT19937의 상태 전이인 twist와 출력 변환인 temper가 2원 유한체 GF(2)에서 선형 연산으로 표현된다는 점을 이용합니다. TimeLord는 상태 비트를 기호적으로 표현하고, twist와 temper를 거쳐 나오는 비트에 원하는 조건을 세운 뒤 XOR 기반 선형 방정식을 풉니다. 제약하지 않은 상태 비트는 자유롭게 정합니다. 생성기 상태 배열의 624개 출력 단위를 넘어서는 출력열도 다루므로, 1,000번 앞면처럼 여러 출력 블록에 걸친 조건도 구성합니다.

상태에서 일반 정수 시드로 되돌리기

MT19937 상태만 만들었다면 random.setstate()로 주입할 수도 있습니다. 하지만 TimeLord는 그렇게 하지 않습니다. CPython이 임의 길이의 Python 정수를 32비트 단어들로 나누고 init_by_array 초기화 알고리즘에 넣는 과정을 역으로 풉니다. 그 결과 구성한 상태를 만들어내는 624개의 리틀엔디언 32비트 시드 단어를 찾고, 이를 하나의 큰 양의 정수로 합칩니다. 이후 데모 코드는 그 정수를 random.Random(seed)에 전달할 뿐입니다.

시드 생성은 python3 find_heads_seed.py 1000처럼 실행하며, 결과는 seed_1000_heads.txt에 저장합니다. 생성된 시드를 demo_heads.py에 넘기면 앞면 출력만 확인합니다. 시드 구성 단계와 출력 단계가 분리되어 있어, 출력 프로그램에는 역산 로직이 없습니다. 기본 설정은 운영체제 엔트로피로 자유 비트를 채우므로 실행할 때마다 조건을 만족하는 시드가 달라집니다. --free-seed 42를 지정하면 자유 비트 선택도 고정해 같은 시드를 다시 만들 수 있습니다.

텍스트 출력과 구현 범위

텍스트 기능은 randrange(128)로 ASCII 문자를 출력합니다. 이 호출은 8비트를 요청하므로 문자 하나마다 원하는 ASCII 값에 해당하는 비트 8개를 제약합니다. 생성기는 메시지 끝에 ASCII 30과 31을 붙이고, 데모는 이 두 문자를 감지해 출력을 멈춥니다. 입력 메시지에 같은 연속 제어 문자 쌍이 있으면 거부합니다. 예를 들어 CPython 3.9.6에서 특정 문장을 반복한 2,490자 접두부와 종료 문자는 일관된 제약으로 풀렸지만, 2,491자에서는 모순이 발생했습니다. 이 수치는 해당 문장에 대한 측정 결과이며, 모든 메시지에 적용되는 최대 길이는 아닙니다.

TimeLord는 CPython의 MT19937 구현과 정수 시드 처리 방식에 의존합니다. 다른 Python 구현이나 시드 알고리즘이 다른 생성기에서는 같은 동작을 보장하지 않습니다. MT19937은 암호화에 적합한 생성기도 아닙니다. 이 프로젝트가 보여주는 것은 난수 모듈의 결함이 아니라, 관찰된 출력이 매우 드물어 보이더라도 초기 조건을 결과에 맞춰 선택했다면 그 인상을 그대로 확률로 해석할 수 없다는 점입니다.

Lobsters 반응

• @cceckman — 이 기법으로 생일 축하 메시지를 만드는 글을 통해 알게 됐습니다.
• @bakkot — CPython이 이전 버전과의 호환성 때문에 PRNG를 바꾸지 않으려는 건 이해합니다. 물론 호환성을 깨는 변경을 꺼리는 것만은 아니지만요. 그래도 아직 Mersenne Twister를 쓰고 있다는 건 정말 놀랍습니다.
• @scruss — Tristan Miller가 쓴 「The Great Commodore/Microsoft Easter Egg War」(TPUG 뉴스레터, 2015년 가을)가 떠오릅니다. Commodore BASIC의 RND 함수에 이스터 에그가 숨겨져 있다고 주장하는 글입니다. 예시 코드는 RND에 125708, 33435700, 17059266을 넣고 난수로 문자를 출력하다가 bill gates sucks를 표시합니다.
• @aleyan — 앞면 100번 시드가 4.88KB네요! 다음 과제는 PRNG를 같은 상태로 만드는 더 짧은 시드를 찾는 일인 것 같습니다. Mersenne Twister를 Python Iceberg의 수면 바로 아래에 넣어뒀는데, 깊은 곳에서 시드를 찾는 항목을 새로 추가해야겠네요.

원문: GitHub / 번역·요약: Trawling