# Which functions can be used as Pseudo Random functions? Can block Ciphers be used for this purpose with our own encryption function?

Since the cloud security algorithm I am trying to implement says that for a PRF, any secure encryption algorithm or a keyed hash function can be used. The security parameter I have chosen is 15 bits while AES and SHA use a large key size than this. So which block cipher and encyption function should I use for a PRF?

• if your security parameter / key size is 15 bit long, your scheme is completely broken whatever the underlying cipher. – Geoffroy Couteau Apr 20 '19 at 12:33
• Increasing key size would affect the computation overhead. What should be the least value of security parameter then? – Syeda Apr 20 '19 at 12:49
• bruteforcing a 15 bit key takes perhaps milliseconds on a standard computer. Anything below 60 bits can be bruteforced in a small amount of time without investing enormous resources. 80 bits seems the bare minimum, you can perhaps go for 64 bits if you have very strong efficiency constraints, and if adversaries are very unlikely to want badly to break your scheme. But remember that even if you go for 64 bits, it can still clearly be broken by a real world adversary who is motivated to invest some time and resources in it. – Geoffroy Couteau Apr 20 '19 at 12:53
• As a businessman, I would find it extremely difficult to promote and sell a new cloud service secured by 80 bit keys. Perception is everything in marketing. AES is not 80 bits and that will become a promotional nightmare. Your marketing 'adversary' will simply ask "Why are the keys so small?" And you'll have no crypto credible reply. You won't convincingly justify it by saying your kit is too small. AES is almost de rigueur and can squeeze into surprisingly small spaces. – Paul Uszak Apr 20 '19 at 13:54
• I will try to write a more detailed and useful response later this weekend, but to add to the remark of Paul Uszak: key size is also not everything that matters regarding efficiency. The underlying design, and the hardware on which the block cipher is run, is of core importance - and in this respect, it is often the case that AES is more efficient than existing alternatives even when they have smaller key size. – Geoffroy Couteau Apr 20 '19 at 14:16

I would recommend against using ONLY 15-bits as a key for your encryption algorithm. A key size that small can be broken via brute force by any standard machine. There's a reason that AES (where the key can be 128 bits, 192 bits, or 256 bits) or SHA-256 are so widely used. The extended key lengths of those algorithms add security against brute force attacks from adversaries.

First, a security level of ‘15 bits’ has essentially no security. So you're going to have to rethink that, and maybe schedule some quality time with a good book on cryptography engineering to get some bearings on the field—the 15-bit security parameter tells us that you're not presently in a position to be making security engineering decisions.

Now, once you've spent that quality time—don't come back to this for at least a few weeks of studying!—here's a specific answer to the question you asked:

Let $$f\colon \{0,1\}^b \to \{0,1\}^b$$ be a uniform random function, and $$\pi\colon \{0,1\}^b \to \{0,1\}^b$$ be a uniform random permutation. If $$A(\mathcal O)$$ is a random decision algorithm making $$q$$ queries to the oracle $$\mathcal O$$, then $$\Pr[A(\pi)] \leq \delta \cdot \Pr[A(f)], \quad \text{where} \quad \delta = (1 - (q - 1)/2^b)^{-q/2};$$ or, as more commonly but less tightly stated, $$\Pr[A(\pi)] \leq \Pr[A(f)] + \binom q 2 2^{-b}.$$ Consequently, if $$A$$ is a random decision algorithm with advantage $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}}(A)$$ at distinguishing AES from a uniform random permutation, then $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{AES}}(A) \leq \delta \cdot \operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}}(A),$$ or $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{AES}}(A) \leq \operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}}(A) + \binom q 2 2^{-b}.$$ This is the PRF/PRP-switching lemma, and it shows that any good pseudorandom permutation is a nearly-as-good pseudorandom function, up to the birthday bound.

• Yes, I now intend to use the key size of 128 bits. To use AES as the PRF, can AES algorithm be used as it is or does it require some initial changes/ parameter values to be set? – Syeda Apr 30 '19 at 11:36
• @Syeda If you're not clear on the answer to that question, I recommend you study up more on cryptographic building blocks. I am deliberately leaving this phrased in jargon so that you're not tempted to run with these scissors until you understand all the terminology of scissor safety, including which parts of the scissors are the handle and which parts are the blades. – Squeamish Ossifrage May 7 '19 at 4:47