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$

closed as too broad by e-sushi Sep 1 '15 at 14:08

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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