Factorio RNG 역공학: taus88 상태를 읽어 전설 품질 제작 순간을 예측한 2년 작업
- Factorio가 쓰는 난수 생성기는 Boost.Random의 taus88임. 2014년 Wube 전 개발자 Cube가 포럼에 남긴 "boost 생성기 중 가장 빨라서 골랐다"는 답변에서 출발함
- taus88은 LFSR(선형 피드백 시프트 레지스터) 3개를 XOR로 결합한 구조라, 계수를 전치해 선형대수로 내부 상태를 역산할 수 있음. 저자는 게임 바이너리에 함께 배포된 .pdb 심볼로 디컴파일해 이를 확인함
- 저자는 게임 안에 RNG 출력을 예측하는 회로 네트워크를 세워, 품질 상승 롤이 겹치는 순간에만 제작해 일반 등급에서 전설 등급을 높은 비율로 뽑아냄
- 이 기법은 Factorio 2.1에서 RNG 사용 방식이 바뀌면서 깨짐. 2.0에서만 동작하고, RNG 알고리즘 자체는 그대로라 이론 부분은 유효함
- 저자는 이 작업에 2년을 썼고, 필요한 사전 지식은 기초 선형대수뿐이라고 밝힘
Hacker News opinions
그냥 대단함. 딱히 덧붙일 말이 없음.
TL;DR은 게임 안에 RNG 예측기를 붙여서 전설이 뜰 롤에만 제작한 거임. 글 위쪽 영상 처음 볼 땐 뭐가 뭔지 몰랐는데 다 읽고 다시 보니 소름 돋았음.
미친 사람임. 천재고.
나도 학교 다닐 때 더 쉬운 버전을 해봤음. 가위바위보 대회에서 동점 처리용 난수를 조작했는데, Java PRNG가 첫 호출에 usec 시각으로 시드되는 걸 이용해서 후보 시각을 훑어 시드를 찾고 동점을 다 이겼음. 구현은 틀렸을 거 같은데 이론은 맞았음 lol.
그거랑 이 글은 전혀 다름. 저자는 선형 시프트 레지스터 계수를 전치해서 회로 네트워크로 다음 상태를 예측하고 레시피를 돌린 거임.
초기 온라인 포커도 서버 시각을 시드로 쓰고 PRNG도 약했음. 홀 카드랑 커뮤니티 카드 몇 판만 보고 시드를 정확히 알아내서 다른 사람 카드까지 다 예측했다는 얘기가 있음.
대단한 작업임!
스타듀밸리는 시드가 두 개인데 하나는 멀티플레이 ID라 세이브 파일을 뜯으면 나옴. 근데 스위치판은 세이브 접근도 어렵고 RNG도 PC판과 다름. 여행 상인 목록으로 캐릭터 시드를 크래킹하는 툴은 있는데 멀티 ID 쪽은 못 봤음. 지오드 내용물을 보면서 순서를 좁혀가면 스위치에서도 될 텐데 코드는 공개돼 있으니 세 단계만 거치면 됨.
저 게임에서 본 것 중 제일 흑마법임. 나는 벨트 밸런서랑 철도 교차로만 남 블루프린트 쓰는 중급인데 저게 어떻게 되는 건지 감도 안 옴.
taus88이 1996년 RNG라는 게 제일 놀라움. 최신 C++ 표준도 boost도 요즘 PRNG가 더 빠르면서 테스트도 잘 통과한다는 걸 모르는 건가 싶었음. 근데 위 인용은 2014년 글이고 지금 boost는 좀 알고 있더라.
LFSR 더 파보고 싶으면 이 글 보면 됨.
이런 집념이 멋짐. 이제 시작 자원 패치를 지도 리셋 없이 골라먹을 수 있겠네.
글 끝에 2년 걸렸다고 써 있음. 학위 하나 수준임.
이제 광맥 위치까지 예측되면 잠은 더 못 자겠다.