# How to break this PRNG encryption scheme? [closed]

Suppose we have the following symmetric algorithm:

key = random bits
G = PRNG(seed: key)
input = [0,1,1,0,1,0,0,0, 0,1,1,0,1,0,0,1] // "hi" in ascii


The key can be thought of as a sufficiently large bit string (say 256 bits).

encrypted = []
for each decrypted_bit in input
random = G.generate()
encrypted_bit = first_bit_of(random) XOR decrypted_bit
first_bit_of(random) = first_bit_of(random) XOR decrypted_bit
append_to(encrypted, encrypted_bit)
G.seed(random)


The decryption algorithm seeds the PRNG with the same key, and performs the following actions:

decrypted = []
for each encrypted_bit in encrypted
random = G.generate()
decrypted_bit = first_bit_of(random) XOR encrypted_bit
first_bit_of(random) = first_bit_of(random) XOR decrypted_bit
append_to(decrypted, decrypted_bit)
G.seed(random)


Suppose each message sent is prepended with a randomly generated 512 bit string, causing the random generator to output different ciphertexts for the same input.

How do I break this scheme? Can I find a pattern in the PRNG using a known-plaintext attack? The current PRNG is the Mersenne Twister "MT19937", generating 64 bits. What PRNGs are vulnerable to this? Which aren't?

Some additional information: For a key with the value 9145160492174859451, "hi" is encrypted to

[0,0,1,0,0,0,0,0,
1,1,0,0,0,1,0,1]


The message

4Glx2[153b(9.#}PY\$G~r.sI4s-?"HiQid6Em\q&8M?#P^sQX&-oJ4UJ-_c4U<1?hi


Encrypts the last two characters as

[1,0,0,1,0,1,0,1
0,0,0,1,1,1,1,1]

• I think the description is a bit off - although still understandable (assigning to a function and such). I guess that for a 64 bit state you should be able to find cycles. Otherwise it looks like a micro form of CBC to me :) – Maarten Bodewes Aug 30 '15 at 15:58
• How long is random from G.generate()? – otus Aug 30 '15 at 16:45
• @otus: currently 64 bits, but I suppose it is best if they are at least 128. – Ultimate Hawk Aug 30 '15 at 16:48
• You might want to edit the question to make it less broad. As-is, you are asking a truckload of things: How do I break this scheme? Can I find a pattern in the PRNG using a known-plaintext attack? … What PRNGs are vulnerable to this? Which aren't? – What have you tried? Did you check for patterns yourself? What research have you done in relation to MT and/or the vulnerability of PRNGs in this setup? Did you check things like the matasano crypto challenge “Create the MT19937 stream cipher and break it”? Did you read papers like CryptMT? – e-sushi Sep 1 '15 at 13:51
• @e-sushi: No, I'm still learning a about different things within cryptography. I'm in the chaos at the start of learning new things. Reading the link you sent right now. – Ultimate Hawk Sep 1 '15 at 15:00