Factorio의 난수 생성기 리버싱하기 — LFSR 선형성을 이용한 게임 내 RNG 예측

본문

Factorio의 Space Age DLC는 제작 시 일정 확률로 더 높은 품질 등급의 아이템을 얻는 품질 시스템을 도입했습니다. 개발사 Wube는 이를 '기본적으로 통계' 문제라고 설명했지만, 저자는 결정론적 게임에서 무작위가 가능한 이유는 의사난수 생성기(PRNG) 덕분이며, 같은 알고리즘을 병렬로 돌리면 미래의 '무작위' 결과를 예측할 수 있다는 점에 착안해 프로젝트를 시작했습니다.

사용 알고리즘 추적 — taus88

저자는 먼저 11년 전 Factorio 포럼에서 전직 Wube 개발자 Cube가 남긴 답변을 발견했습니다. 'taus88을 선택한 이유는 boost의 생성기 중 가장 빨라서'라는 내용이었습니다. Boost.Random의 taus88은 3개의 선형 피드백 시프트 레지스터(LFSR) 출력을 XOR한 구조입니다. 이를 검증하기 위해 저자는 게임과 함께 배포되는 .pdb 디버그 심볼을 이용해 Ghidra(이후 Binary Ninja)로 바이너리를 디컴파일했고, RandomGenerator::getInt()에서 3개의 시드를 독립적으로 갱신한 뒤 XOR해 반환하는 코드를 확인했습니다. 상수가 원래 정의와 달라 보이는 것은 컴파일러의 상수 폴딩 최적화 때문이며, 저자는 두 구현을 sympy 기반 Python 코드로 옮겨 한 스텝씩 진행시켜 모든 비트가 동일하게 갱신됨을 기호적으로 증명했습니다.

LFSR의 선형성과 상태 복원

LFSR은 GF(2), 즉 XOR을 덧셈·AND를 곱셈으로 하는 체(field) 위에서 동작하기 때문에 상태 전이를 행렬 곱으로 표현할 수 있습니다. n비트 LFSR의 최대 주기는 2ⁿ−1이며, 피드백 탭의 선택이 주기 길이를 결정합니다. 이 선형성 덕분에 충분한 출력을 관찰하면 내부 상태를 연립방정식으로 풀어 복원할 수 있는데, 이것이 LFSR이 암호학적으로 약한 이유입니다. taus88의 LFSR은 32비트 워드 위에서 각각 31, 29, 28비트 크기로 동작해 하위 비트가 상위 비트에 선형 종속이므로 전이 행렬을 축소해 full rank를 회복한 뒤 역행렬을 구합니다. 3개 LFSR을 하나의 큰 상태 벡터로 쌓으면, 연속한 3개의 출력을 관찰하는 것만으로 전체 내부 상태를 푸는 선형 시스템이 완성됩니다.

게임 내 구현과 한계

Python으로 만든 첫 solver는 Factorio Lua API로 연속 난수 3개를 얻어 상태 복원과 미래 출력 예측에 성공했습니다. 이후 저자는 게임 내 자원만으로 구현하기 위해 회로 네트워크 기반 예측기를 만들었습니다. 절차는 △관찰을 통한 현재 RNG 샘플링 △내부 상태 계산 △미래 상태 예측 △각 미래 호출의 품질 등급 계산 △어댑터를 통한 활용 순서입니다. 실제로 이를 이용해 RNG 결과가 legendary로 나올 타이밍에만 제작을 수행해, 기본 아이템에서 legendary까지 높은 확률로 도달하는 모습을 영상으로 공개했습니다. 다만 Factorio 2.1에서 RNG 사용 방식이 변경되어 게임 내 구현은 2.0에서만 동작하며, RNG 자체의 이론적 분석은 여전히 유효합니다.

Hacker News 반응

• @jvanderbot — 설명이 더할 나위 없습니다. 놀라운 작업이에요. 요약하자면: 게임 안에서 RNG 출력 예측기를 만들어 RNG가 legendary를 굴릴 타이밍에만 제작하게 한 겁니다. 기본 등급에서 legendary까지 놀라울 정도로 높은 비율로요. 글 맨 위의 영상을 자세히 보세요 — 기사를 다 읽고 나서야 제가 본 게 무엇인지 실감이 났습니다. 대단합니다.
• @strstr — 대학 입문 수업에서 비슷한 걸 더 쉽게 해봤습니다. 가위바위보를 포함한 반 대항 경연에서 무승부를 난수로 처리했는데, Java의 PRNG를 조작해서 모든 무승부를 이길 수 있었습니다. PRNG가 첫 호출 시 마이크로초 시간으로 시드됐거든요. RNG를 여러 번 호출해 엔트로피를 모으고 가능한 시드 시간을 스캔해 시드를 찾은 뒤, 무승부에서 이기도록 PRNG를 준비시켰습니다. 구현을 잘못했을 수도 있지만 이론은 맞았던 것 같습니다.
• @rogueaine — 그건 기사가 제안한 내용과는 전혀 다릅니다. 저자는 선형 시프트 레지스터 계수의 행렬과 그 전치 행렬을 만들어, 이를 기반으로 회로 네트워크를 구성해 (샌드박스에서) 다음 상태를 예측하고 레시피를 지시했습니다.
• @strstr — 기사 인용: '관찰을 통한 현재 RNG 샘플링, 현재 내부 RNG 상태 계산, 미래 내부 상태 예측, 각 미래 호출의 품질 등급 계산, 그리고 어댑터를 통한 예측 등급 활용.' 엔트로피→시드(내부 RNG 상태) 단계에는 물론 더 많은 수학이 필요했고요. 솔직히 리버스 엔지니어링과 메모리 검사만으로 수학 없이 시드를 추출할 수도 있었을 것 같긴 합니다. 제가 했던 버전은 품질이 아니라 무승부 처리를 예측하는 거였습니다.
• @PennRobotics — Stardew Valley에는 난수 시드가 두 개 있습니다. 하나는 일반 캐릭터 시드이고, 다른 하나는 세이브 파일 분석으로 알 수 있는 멀티플레이어 ID입니다. 다만 Switch에서는 세이브 파일 접근이 어렵고 RNG도 PC와 달라서, 여행 상점 목록을 보고 캐릭터 시드를 계산하는 시드 크래커가 있습니다. 다른 시드를 깨는 도구는 덜 중요하고 관찰도 어려워서인지 아직 못 찾았고 직접 만들 시간도 없네요. 지오드 내용물을 분석하면 분리할 수 있을 것 같지만…

원문: gegell.github.io / 번역·요약: Trawling