6
$\begingroup$

There is an apparently provably secure cipher that was proposed by Diffie, but enhanced by R.A. Rueppel. The scheme, which was mentioned in Applied Cryptography, works like this:

  1. Measure the length of the plain-text, $n$.
  2. Multiply it by $128$.
  3. Generate this much ($128·n$ bytes of) real random data and split it out into 128 byte-arrays of length each equal to the plain-text. This can be thought as a two dimensional array:
    1. One of the indices gives the sequence number ($0\dots 127$).
    2. One of the indices gives the position in the sequence, $0 \dots n-1$.
  4. Use a 128-bit key to choose which of these streams to XOR together. Each bit of the key corresponds to "yes/no" on whether to use particular sequence. All the selected sequences are XORed together to make a single keystream, $K$.
  5. Compute $P \oplus K$ to give the cipher-text $C$.
  6. Serialize the two dimensional array and append it to the cipher text.
  7. Send the whole package to Bob, who can then decrypt by de-serializing the matrix and selecting the same rows.

Apparently, this scheme is completely secure. The attacker has to examine every possible combination of sequences ($2^{127}$ on average) in order to break the encryption scheme.

What is the proof of this? I can't find the paper that discusses this anywhere.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

This looks totally weak. If you know 128 bits of known plaintext, you can infer the corresponding 128 bits of keystream. The keystream being the multiplication of the random matrix by the key (in the vector space $\mathbb{F}_2^{128}$), the key is then revealed through a basic matrix inversion.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting, this may be completely wrong then. The algorithm is mentioned in Applied Cryptography. The original Diffie algorithm used 2^k strings, and the key just selected what string to use. The modification was to use a linear combination of just k strings - but the paper discussing the modification was unreferenced in the text. It said that the paper used a linear combination of the k strings and it was equally secure. I used XOR as the linear combination in my example. Perhaps this is the source of my mistake. $\endgroup$
    – Simon Johnson
    Commented Nov 28, 2011 at 17:36
  • 2
    $\begingroup$ Can something be perfectly secure and still vulnerable to a known-plaintext key recovery? $\endgroup$
    – Ethan Heilman
    Commented Nov 28, 2011 at 20:03
1
$\begingroup$

I have done quite a bit of Google searching and apparently the description of the algorithm along with its proof of security is detailed in Contemporary cryptology: the science of information integrity.

At this stage I have no idea whether the algorithm matches what is listed above. Probably not as the construction is insecure. I'll keep digging and fix this comment when I have some more information.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Did you ever get around digging deeper so you could “fix this comment”? $\endgroup$
    – e-sushi
    Commented Dec 24, 2013 at 17:18
  • $\begingroup$ I actually bought the book this was referenced in Applied Cryptography. It didn't contain the proof. It's a bit of a mystery. The thing is, if the claim in AC is true, that would actually be a usable perfectly secure cipher. Many people would take a cipher-text expansion of x128 if it delivered perfect security. The fact that nobody mentions it anywhere seems to indicate that either I'm mistaken in how I think it works, or that it never existed in the first place and Schneier simply made a mistake. $\endgroup$
    – Simon Johnson
    Commented Dec 24, 2013 at 20:55
  • $\begingroup$ Thanks for the update. Much appreciated… I somewhat ended up with the same question mark hovering above my head, so I couldn't help asking. Good thing to know I'm not the only one left wondering. I'll remember to drop a line here in case I ever stumble upon proof. (Merry Xmas btw.) $\endgroup$
    – e-sushi
    Commented Dec 25, 2013 at 5:29
  • $\begingroup$ Almost forgot: this site mentions the cipher, explaining isomorph cipher (description page) is an “evolution” of it (translated: they merely pushed it from 128 bits to 1024 bits). There's a PDF (with questionable styling choices) that mentions their cipher on page 38. Not much there, but… some “vague” hinting at proof. $\endgroup$
    – e-sushi
    Commented Dec 25, 2013 at 6:00
  • $\begingroup$ To me, the whole security of Diffie's cipher boils down to $K$ being transmitted over a separate, secret, and secure channel — like they nicely animated here. As soon as an attacker can intercept $K$, security is hosed… personally, I think there's not much difference to simply using the $K$ channel to transmit OTP instead of index positions of a (publicly known) dictionary. OTOH, it's 07:00am local time on Christmas day… so, I might be missing something. ;) $\endgroup$
    – e-sushi
    Commented Dec 25, 2013 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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