This is for a distributed system: we don't want to have to maintain synchronization of random streams neither enforce uniqueness of pads because this would require some synchronization.

Alice and Bob met once. They agreed on a secret (S) and a symmetric cipher (C). Let's assume S is 128 bits in length.

Then, they want to communicate in the following way.

Alice want to send a message (M) to bob. Alice generate a random number (R). Let's assume R is also 128 bits in length. She symmetrically encrypt R using S and C. This become the message header (H), also 128 bits long. Then, she use R to generate the pad for M, using a cryptographically strong random number generator. The generator she uses must be non repeating: it will never produce the same output twice. She obtain (M'), the encrypted message.

Then, Alice send to Bob the concatenation of H and M'.

On his side, Bob will first decipher H to generate the pad to decipher M'.

I think the risk of reusing a pad is only 1/(2^256), which looks terribly small.

Let's say that if Alice and BOB want a MAC, then they agree on a second secret and a MAC scheme and will encrypt concatenate(MAC(M),M) instead of just M.

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Stream_cipher $\:$ en.wikipedia.org/wiki/Block_cipher_mode_of_operation#CTR $\hspace{.53 in}$ $\endgroup$ – user991 Oct 2 '15 at 12:29
  • 1
    $\begingroup$ There are quite a few posts to this site which attempt to "extend OTP". Like those, this idea is not in fact a OTP - it depends on the strength of the PRNG and uses a fixed-length key, not a pad. Also, as Ricky points out, it is related to existing well-known cipher designs. So if you have come up with this from thinking through the problem, well done, but like many good ideas and inventions it is not new. $\endgroup$ – Neil Slater Oct 2 '15 at 12:51

The question describes a stream cipher with key $S$, using $C_S(R)$ to transmit a random session key $R$, and a keystream (or pad) generated from $R$ using a CSPRNG to encipher the message.

This is not an OTP; and contrary to an OTP, it is not secure against a computationally unbounded adversary, who hypothetically, knowing a plaintext/ciphertext pair significantly more than 128 bits, could find by enumeration the (much probably unique) $S$ that could have generated that pair, breaking the system entirely.

Another error is made in computing the risk of reusing a keystream (or pad). It raises with the number of messages. Odds of reusing the same $R$ on or before $n$ messages are $$1-\prod_{j=0}^{n-1}\Big(1-{j\over2^{128}}\Big)$$ which for small $n$ is about $n(n-1)2^{-129}$; it that happens, the keystreams are the same, and that's detectable by the identical header, and exploitable for cryptanalysis assuming a known plaintext, or plaintext with enough redundancy.

Even for two messages, odd of key reuse are $2^{-128}$ (not $2^{-256}$), and become near $2^{-41}$ for $n=2^{44}$. Which is still perfectly fine in practice.

  • 1
    $\begingroup$ Thanks for the detailed answer. Also, note that the scheme can be hardened by having Alice ensure that she doesn't use the same random number twice. Also, in a two persons system, they could both ensure that they don't use a random number they already used or that the other party already used. Unfortunately, I don't know how to guarantee that in a system with more than two peers and where they can all start to communicate at the same time. $\endgroup$ – daruma Oct 2 '15 at 14:49

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.