AltSci Cell

First off the tl;dr for those in a hurry.

My SPS source code has been available since July 2022. It's not the only implementation.

So the short explanation is that the design of pickTetriminoSeed, the function that is the basis for the whole of TetrisGYM SPS (v4 and v5 seeds) has a weakness that Tetris original rom does not. The attached seeds are a list of seeds that fall into the same sequence before piece 100. This is caused by @invalidIndex. There are 276 seeds. Because of how the LFSR in generateNextPseudorandomNumber works, it's not just 276 seeds that do that, it's ~2x that. This is true of just about everything I've checked so instead of 4 million unique seeds, we have about 20k-80k sequences that a player can expect to get (research not complete). And because of how it locks, it continues indefinitely. This is probably beyond the capacity of a person to memorize, but we could see players memorize a small fraction of favorable and unfavorable sequences for a benefit in competition. Let's start the work of writing an improved SPS shall we?

Details

The detail is that once you have noticed that you're on a seed you know, you can play more or less aggressively. Let's take a look at some the most consistent seeds in all of TetrisGYM SPS. I call these the 0012a7 seeds but it's actually way more accurate to call them the 1616c3 seeds -- because that is the value in the seed that these seeds fall into. Funny enough, the way that SPS works, 1616c3 is not a member of this class.

In case you think this is some sort of fluke or that I am cherry picking. Let me assure you. Here we see that all 276 seeds do indeed contain the value TZJOIZSJLSOIZSOLOZLZTZO. That should be proof.

for seed in $(cat tetris_sps_vuln2d_1616c3_5800c4.txt ); do 
    python3 tetris_sps.py "$seed" 500 | grep TZJOIZSJLSOIZSOLOZLZTZO; 
done |wc
    276     276  138276

Deeper into the Research

So far we've only talked about the 0012a7 group. So let's talk about how many groups exist.

I wrote tetris_sps_vuln.py to give us a very large file containing the "seed" at any given point in time for all seeds -- only 30 deep.

pypy3 tetris_sps_vuln.py >tetris_sps_vuln2.txt

The resulting file tetris_sps_vuln2.txt is only 238.0 MiB compressed with xz, 3,360.0 MiB uncompressed.

This saves us the time of running a long-running script on all the seeds every time we want to learn more.

If we pick a random seed we can use tetris_sps_vuln2.txt.xz to find the sequences that it generates.

054bcf is the most prolific seed that starts with 0, so let's check it out. You might consider this cherry picking, but look below on actually random seeds if you're not convinced.

xzcat tetris_sps_vuln2.txt.xz |grep 054bcf >054bcf_1.txt

We get 443 seeds that end up with 054bcf in them, but not all of those are going to have the same sequence. Let's take a look.

grep '054bcf 224ed0' 054bcf_1.txt |wc
    269    8070   56490

269 of them contain the sequence that 054bcf does. So these can be called the 054bcf seeds.

grep -v '054bcf 224ed0' 054bcf_1.txt |head -n1
0d6eb2 78c4b3 4d79b4 ae69b5 9b8eb6 1115b7 2608b8 625cb9 fa7dba 730fbb cd7cbc 2b63bd 1e90be b31cbf c95ec0 052fc1 2054c2 1a74c3 5adcc4 330dc5 587cc6 9449c7 f5bac8 d24fc9 393bca 3802cb 4a74cc d53ecd a0ebce 054bcf

Ok that one just ends with 054bcf which doesn't help us.

grep -v '054bcf 224ed0' 054bcf_1.txt |grep -v '054bcf$' |head -n1
1114b7 2608b8 625cb9 fa7dba 730fbb cd7cbc 2b63bd 1e90be b31cbf c95ec0 052fc1 2054c2 1a74c3 5adcc4 330dc5 587cc6 9449c7 f5bac8 d24fc9 393bca 3802cb 4a74cc d53ecd a0ebce 054bcf 449cd0 51b1d1 43c1d2 0505d3 0a00d4

So this one goes 054bcf 449cd0. So let's find ones that do that.

grep '054bcf 449cd0' 054bcf_1.txt |wc
    152    4560   31920

152 + 269 = 421 so that is just about all of them. Let's find the stragglers.

grep -v -e '054bcf 449cd0' -e '054bcf 224ed0' 054bcf_1.txt |gawk '{print $29}' |sort |uniq -c
     14 a0ebce
      8 d075ce

Ok they all end in 054bcf. So I assume they fit into one of the other classes. Even if they don't... It doesn't matter except mathematically. You can probably guess where the rest of this paper is going. I'd love to write a mathematical proof for the existence of the vulnerability that I found, but we are not quite there. Instead we'll have to accept cryptanalysis of the PRNG that we know and love --- TetrisGYM SPS.

So to prove cryptanalysis it is customary to have a peer encrypt a plaintext with the cipher with a key that is unknown to the cryptographer and have the cryptographer decipher it with their technique. I will offer that challenge to the first person to contact me on discord or other communications. To show how easy it is, I'll do it here so that no one is confused on the method.

Because our PRNG is used for tetris and not for cryptography, it makes more sense to come up with a list of seeds that fall into the sequence than it does to decrypt a message. So I'll generate a random seed.

./randseed1.py
0d4405

A fairly picked seed. It's just chance that it starts with 0. I chose not to reroll to keep the randomness fair.

grep 0d4405 vuln_hist_0a.txt
      1 0d4405

We see that this is not like 054bcf in any way. It's only ever found once in the whole vuln. That doesn't matter. We can't use tetris_sps_vuln2.txt so we'll use print_seeds.py instead.

pypy3 print_seeds.py 0d4405 >0d4405_1.txt
for seed in $(cat 0d4405_1.txt); do grep "$seed" vuln_hist_?a.txt; done >0d4405_1a.txt

Every seed has more than one appearance in the vulnerability db tetris_sps_vuln2.txt.xz.

Picking one that isn't too far along but is also far along enough 726621. This could be a false positive but let's hope.

xzcat tetris_sps_vuln2.txt.xz |grep 726621 >726621_1.txt

All we care about is if the sequence we see in our random seed is found elsewhere. Nothing else. So we take the two values in succession and see if they are in there.

grep "$(grep -A1 726621 0d4405_1.txt |tr '\n' ' ')" 726621_1.txt |wc
     74    2220   15540

This is a good sign but let's just make sure that they

grep -A20 726621 0d4405_1.txt |tr '\n' ' '; echo
726621 678122 914e23 0fed24 e7ee25 ab1826 0f2b27 c9d228 fc4129 fa2b2a 0c962b dc192c edf62d de012e 731d2f 544630 7dd131 3aba32 d7a833 5f4334 6d1135

grep "$(grep -A1 726621 0d4405_1.txt |tr '\n' ' ')" 726621_1.txt |head -n 1
082609 89f20a 7b470b ce530c e8090d e4c70e b7520f 045e10 9a9511 48e812 c18a13 7e4414 ce3315 6b0f16 ed9617 5d0718 570519 67e51a 22681b 68741c d6611d d0db1e f5501f 127a20 726621 678122 914e23 0fed24 e7ee25 ab1826

pypy3 print_seeds.py 082609 >082609_1.txt

grep -A20 726621 082609_1.txt |tr '\n' ' '; echo
726621 678122 914e23 0fed24 e7ee25 ab1826 0f2b27 c9d228 fc4129 fa2b2a 0c962b dc192c edf62d de012e 731d2f 544630 7dd131 3aba32 d7a833 5f4334 6d1135

And there is my proof of cryptanalysis. Do you want more seeds that have the same? Sure. Let's do that.

for seed in $(grep "$(grep -A1 726621 0d4405_1.txt |tr '\n' ' ')" 726621_1.txt |gawk '{print $1}'); do pypy3 print_seeds.py "$seed" |grep -A20 726621 |tr '\n' ' '; echo; done
726621 678122 914e23 0fed24 e7ee25 ab1826 0f2b27 c9d228 fc4129 fa2b2a 0c962b dc192c edf62d de012e 731d2f 544630 7dd131 3aba32 d7a833 5f4334 6d1135

74 seeds collide into this sequence. Let's go ahead and check so that we understand what we're doing.

for seed in $(grep "$(grep -A1 726621 0d4405_1.txt |tr '\n' ' ')" 726621_1.txt |gawk '{print $1}'); do echo "$seed"; done |randomize2.py 2024-10-31b |head -n 10
67280c
e2cf07
931d0e
082709
d9e908
27ca0a
d0120d
ed1e0b
74040d
152906

AA=$(for seed in $(grep "$(grep -A1 726621 0d4405_1.txt |tr '\n' ' ')" 726621_1.txt |gawk '{print $1}'); do echo "$seed"; done |randomize2.py 2024-10-31b |head -n 10)

for seed in $AA; do python3 tetris_sps.py "$seed" 500; done

Javantea out.