4
$\begingroup$

Assume we have a secure PRF $F$ which takes a key of length $k$, a message of length $l$, and outputs an output of length $o$. The task it to construct a secure PRF $G$ which takes the same input parameters, but outputs an output of length $2 \cdot o$, by using the first PRF.

My basic intuition would be to construct something like this: $$G(k, m) = F(k, m) \| F(k, F(k,m))$$

But there is a dimension issue here, since the length of the output is not the same as the length of the message.

Could anyone give me a hint to push me in the right direction?

$\endgroup$
4
  • 1
    $\begingroup$ See, is-f-kx-h-kx-oplus-h-kxh-kx-a-prf-where-h-is-a-prf $\endgroup$
    – kelalaka
    Oct 29, 2018 at 8:32
  • $\begingroup$ I'd go overkill on it and use a KDF :) Note hat a KDF is a PRF, and PRF's are commonly used instead of full fledged KDF's. $\endgroup$
    – Maarten Bodewes
    Oct 29, 2018 at 11:39
  • $\begingroup$ I think that the adversary should not be able to query $F$ for any secure construction, by the way. $\endgroup$
    – Maarten Bodewes
    Oct 29, 2018 at 11:52
  • $\begingroup$ KDF and then apply F twice? that seems like an interesting idea ! $\endgroup$
    – el-flor
    Oct 29, 2018 at 12:50

2 Answers 2

2
$\begingroup$

The $G$ that you have defined is not a PRF at all. I can distinguish it from random in just two queries. Since I have a feeling that this is homework (correct me if I'm wrong), I'll let you work out how it can be broken.

$\endgroup$
6
  • $\begingroup$ Yep, as additional hint: remember that an adversary can choose its own messages, so you should now allow an adversary to somehow repeat output, even over different calls to $G$ $\endgroup$
    – Maarten Bodewes
    Oct 29, 2018 at 11:56
  • $\begingroup$ Thanks for your help, I have indeed seen why the G I have defined is not a PRF. Is there any hint to push my in the right direction? $\endgroup$
    – el-flor
    Oct 29, 2018 at 12:49
  • $\begingroup$ Think about how you can "stretch" the output. $\endgroup$ Oct 29, 2018 at 14:33
  • $\begingroup$ I'm finding myself incredible stuck here. The basic operations we can use here are quite clearly the XOR, concatenation, and the usage of F. I can't seem to do any operation that isn't completely deterministic and can easily be used to query with. To stretch my output I'll need to somehow concatenate two results (that can be manipulated afterwards) of calls to F, since my length has to be exactly 2*L. Can anyone push me forward here? Thanks a lot. $\endgroup$
    – el-flor
    Oct 30, 2018 at 3:12
  • 2
    $\begingroup$ Hint: You can use the PRF to derive two keys and then use those two keys from then on. $\endgroup$ Oct 30, 2018 at 5:04
0
$\begingroup$

Your construct has a problem. There are only $2^o$ possible values even though the output length is $2\cdot o$. The second half of the output only depends on the first half, not the message itself. There are at least two consequences to this

  1. The likelihood of collisions is the same as if you didn't double the output length.
  2. The security of the PRF used as a MAC is not improved.

The first consequence may not be much of a problem if the output length of the original PRF is already long enough to prevent collisions. You are expected to see two messages with the same output after about $2^{o/2}$ queries, instead of the number you normally expect from a PRF of length $2 \cdot o$, which is $2^o$. If $o$ is already at least $256$ bits then you shouldn't expect collisions.

The second consequence can be exploited to forge messages with the same probability of success as with PRF $F$. You only have $2^o$ possible outputs for a given key. If the forger can observe any one of the valid MAC tags then they can reuse the same tag for a forged message. The probability of success would be $2^{-o}$. You can improve this probability if you can generate a large number of forged messages. (Using different messages with the same tag instead of one message with different tags.)

If you want to double your PRF output length then it probably would be best, from the perspective the mathematical ideal of a PRF, to choose two distinct keys and process the message twice. (Doubling the run time may be unfortunate from a pure performance perspective, though.)

You may be able to reuse the PRF as a key derivation function to choose, say $k_1, k_2$, from a single key $k$, if the output length is large enough and $k$ is already a safe key size. You should not do something like $k_1 = k + 1, k_2 = k + 2$ because a specific algorithm may not resist related key attacks.

Alternatively you can process the message twice using a single key by using two different prefixes added to the message. (Basically the same idea as a salt.) Some algorithm might have an optional salt or "personalization string" parameter that works the same way.

$\endgroup$

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.