2
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – Maarten Bodewes Aug 30 '15 at 15:58
  • $\begingroup$ How long is random from G.generate()? $\endgroup$ – otus Aug 30 '15 at 16:45
  • $\begingroup$ @otus: currently 64 bits, but I suppose it is best if they are at least 128. $\endgroup$ – Ultimate Hawk Aug 30 '15 at 16:48
  • $\begingroup$ 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? $\endgroup$ – e-sushi Sep 1 '15 at 13:51
  • $\begingroup$ @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. $\endgroup$ – Ultimate Hawk Sep 1 '15 at 15:00