# Is this distributed OTP scheme secure?

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.

• – user991
Oct 2, 2015 at 12:29
• 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. Oct 2, 2015 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.