Is this distributed OTP scheme secure?

Question

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.

Answer 1

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.