RNG++

RNG++

• Category: Crypto
• Score: 213/500
• Solves: 21/428

This is actually a broken version of RNG+++.

Description

I encrypted the flag and messages by xoring them with a random number generator.

Overview

You got a simple LCG with $s_{i+1} = A s_i + C \pmod{M}$, where $A,C$ are prime and $M$ is a power of $2$. The flag are encrypted by xor it with initial state $s_0$. Some random messages are generated by randmsg are encrypted by the same way.

Solution

The first thing to notice is randmsg generated messages are all decimal digits, and they are 0x30 to 0x39 in ASCII. It is obvious that their binary representation are all 0011????, so we can get serveral non continuous bits of states $s_i$.

The most simple unintended solution is to use z3. You just let the state be $\log_2{M}$ bits unsigned bitvector, and write LCG and specify the constraints, and it will magically found the state, so you can get the flag too.

Another more mathematical unintended solution by @Kuruwa: Since $M$ is a power of $2$, reducing it to $\bmod{2^{8i}}$ works too. And just do some bruteforce searching over the digits to see if it holds.

The intended solution will be in the writeup of RNG+++.