# Construct PRF with longer output from existing PRF

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?

• – kelalaka Oct 29 '18 at 8:32
• 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. – Maarten Bodewes Oct 29 '18 at 11:39
• I think that the adversary should not be able to query $F$ for any secure construction, by the way. – Maarten Bodewes Oct 29 '18 at 11:52
• KDF and then apply F twice? that seems like an interesting idea ! – el-flor Oct 29 '18 at 12:50

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.

• 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$ – Maarten Bodewes Oct 29 '18 at 11:56
• 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? – el-flor Oct 29 '18 at 12:49
• Think about how you can "stretch" the output. – Yehuda Lindell Oct 29 '18 at 14:33
• 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. – el-flor Oct 30 '18 at 3:12
• Hint: You can use the PRF to derive two keys and then use those two keys from then on. – Yehuda Lindell Oct 30 '18 at 5:04

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.