2
$\begingroup$

Consider the following modification of RC4 to give some "ciphertext feedback"

i ← 0
j ← 0
C ← 0  -- We will remember the previous output ciphertext byte.
repeat
    i ← (i + 1) mod 256
    j ← (j + S[i] + C) mod 256  -- Use the previous ciphertext byte
                                -- for "ciphertext feedback".
    S[i] ↔ S[j]
    input P                     -- Read the next byte of plaintext
    C ← S[(S[i] + S[j]) mod 256] xor P
    output C                    -- Output the next byte of ciphertext

It would be nice to be able to use RC4 in some sort of plaintext-dependent mode like this, to avoid various stream cipher weaknesses while still having a cheap cipher that is easy to implement.

Is there something obvious (or non-obvious) that goes wrong here? [Edit: Other than my ability to write appropriate pseudocode on the first try.]

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ please. do. not. use. RC4. for. anything. and more importantly: do. not. roll. your. own. crypto. $\endgroup$
    – SEJPM ♦
    Nov 17 '15 at 20:27
  • 1
    $\begingroup$ That is not like ciphertext feedback. It's more like output feedback. $\endgroup$
    – otus
    Nov 17 '15 at 21:56
  • 1
    $\begingroup$ I dorked the pseudocode. Thanks for noticing my stupidity. I'll edit the question and try again. $\endgroup$
    – PO8
    Nov 18 '15 at 1:49
  • $\begingroup$ I. will. not. use. RC4. for. anything. important. and more importantly: I. asked. for. review. because. I. was. interested. in. the. analysis. I can well believe that something goes wrong here. I would love to learn something by seeing what problems this has. Dot-texting at me is not helping. $\endgroup$
    – PO8
    Nov 18 '15 at 1:58
  • 1
    $\begingroup$ In general, I don't think you'll find that people are overly willing to spend time and/or effort analyzing bespoke novel constructions around broken ciphers. $\endgroup$
    – Stephen Touset
    Nov 18 '15 at 2:04
3
$\begingroup$

At least one thing goes very wrong: if an adversary can obtain the ciphertext for a few short chosen plaintexts and the same reused key/initial state, that allows reconstructing the state because the indexes vary in a controlled way. That certainly works if we obtain the ciphertext for the $2^{24}$ plaintexts consisting of the 3 bytes $u$ $v$ $w$ $0$ (basically, we can make some hyptohesis on a few state bytes, and confirm or rule it out based on the ciphertext for that chosen plaintext); or something on that tune. Likely, it is possible to mount an attack requiring much less chosen plaintext.

It might even be possible to mount an iteratively chosen plaintext attack working without key reuse.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks much!! As I suspected, I have learned something. I think I see the general idea, I'm not quite seeing the details of how to construct the attack you're proposing. One ends up essentially solving a bunch of simultaneous equations in the state, I guess? $\endgroup$
    – PO8
    Nov 18 '15 at 6:51
  • $\begingroup$ @PO8: I don't pretend that I fully see the details of the attacks I'm thinking of. However I'm confident that the one in the first paragraph can be made to work. Won't bet for the one in the last paragraph. $\endgroup$
    – fgrieu ♦
    Nov 18 '15 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.