1
$\begingroup$

Assume I have an encryption scheme $E(k,m) = (P(k,r), G(r) ⊕ m) $ and given that $G$ is a PRG , $P$ is a PRP and $r$ is a random n-bit nonce.

My question is:

If I run this encryption twice with the same message but different r (due to nonce behavior), will I get the same c?

I know that PRG is deterministic, but in this case, the $r$ always changes.

Please help!

Improve this question
$\endgroup$
7
  • $\begingroup$ What are the key generation and decryption algorithms? $\endgroup$
    – fkraiem
    Commented Dec 14, 2017 at 6:06
  • $\begingroup$ Edited! For the decryption algorithm, I don't really know. This is just a thought. Does the decryption matter a lot? $\endgroup$
    – ThomasWest
    Commented Dec 14, 2017 at 6:08
  • 1
    $\begingroup$ Yes it matters, because if the receiver cannot decrypt, what you have is not even an encryption scheme in the first place. Also, what is $P$? $\endgroup$
    – fkraiem
    Commented Dec 14, 2017 at 6:10
  • $\begingroup$ I see, is it possible to construct one from this? I honestly didn't expect this at all. $\endgroup$
    – ThomasWest
    Commented Dec 14, 2017 at 6:12
  • $\begingroup$ Ok, now it's good (the decryption algorithm is obvious; it wasn't before). $\endgroup$
    – fkraiem
    Commented Dec 14, 2017 at 6:13

1 Answer 1

Reset to default
1
$\begingroup$

If I run this encryption twice with the same message but different $r$ (due to nonce behavior), will I get the same $c$?

No.

Lets split this question into the two elements of $c = (c_1, c_2)$ where $c_1 = P(k,r)$ and $c_2 = G(r) ⊕ m$. Then lets start with $c_2$ where the message is actually "encrypted".

A good PRF will return a stream of bits indistinguishable from random. It should be a different stream each time the seed is different. However, two random streams will still have approximately half the bits identical, purely because of chance.

So lets minimize the size of $m$ to a single bit, and set $m$ to zero. The resulting stream of bits may start with a zero or one for $r=x$ or $r=y$ with $x \neq y$ . Say that they both start with $0$ or $1$ then the result of $c_2 = G(r) ⊕ m$ will be $0$ or $1$ as well.

Of course the chance that $c_2=c_2'$ is reduced by 50% for each bit added to $m$. But $c_2$ can be identical for the right combination of nonces.

The fact that $c$ consists of the permuted nonce as well confuses the matter. The $c_1$ will always be different because $P(k, r)$ will always be different - it is a permutation after all. This has however nothing to do with the message $m$ or the security of the scheme.

However, it does mean that the only answer possible is no given your scheme; if $c_1$ is never the same then $c$ is obviously never the same as well, even though $c_2$ is not affected.

Note that $G(r)$ can only be secure if $r$ behaves as a secret, i.e. has enough entropy. The size of $r$ is maximized by the size of the PRP. Basically this scheme is a stream cipher if and only if $r$ contains enough entropy. In that case $P(k, r)$ will be a form of key wrapping.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So, at a very high-level view, G(r) ⊕ m will always produce different cipher with the same m, right? $\endgroup$
    – ThomasWest
    Commented Dec 14, 2017 at 17:11
  • $\begingroup$ Huh? No I just explained why not. If the stream cipher generated by $G(r)$ creates the same key stream then the ciphertexts will be identical. However, the larger the stream the less likely this becomes. I'm not sure what you mean with "very high-level view". $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 14, 2017 at 17:15
  • $\begingroup$ Oh, sorry I didn't read it properly. I think for simplicity's sake $r$ random n-bit nonce is a large-enough seed that will not cause the stream cipher to generate the same key stream. Correct? $\endgroup$
    – ThomasWest
    Commented Dec 14, 2017 at 17:18
  • $\begingroup$ Well, again, consider a "stream" of a single bit. There is still a 50% chance that two entirely different values of $r$ will generate the same key stream. Random doesn't mean different. It is perfectly possible to toss two sixes in a row with a perfectly balanced dice. But I shall amend my answer for an n-bit sized $r$, because I skipped that. $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 14, 2017 at 17:24

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.