Let's assume we have an $\epsilon$-bounded Universal Hash Function Family $H = \{H_K:\mathcal{X}^{\leq m}\rightarrow \mathcal{X}\mid \forall K\in \mathcal{K}\}$ with $\mathcal{X} = \mathcal{K} = \{0,1\}^{128}$. $H_K$ only takes messages $M$ as input, that are a multiple of the blocksize ($M\in\mathcal{X}^{\leq m}$) and are at most $m$ blocks long. Is it sufficient to apply an injective encoding $enc(\cdot)$ on the message, so that we get a bit-wise Universal Hash Function Family $H^* = \{H^*_K:\{0,1\}^*\rightarrow \mathcal{X}\mid \forall K\in \mathcal{K}\}$ with $H^*_K(M) = H_K(enc(M))$, $M\in\{0,1\}^*$ ?

Intuitively I would say yes, but the reason why I ask is the following:

(Section 7.2.2) states, that the rawCBC construction and any other prefix-free PRF $F_K$ with the following extension property yields an UHF:

if $F_K(x) = F_K(y) \Rightarrow F_K(x \| a) = F_K(y\|a)$

Furthermore, (Section 6.8.) states, that a block-wise PRF can be turned into a bit-wise PRF by applying an injective encoding on the input.

Now consider the following injective encoding function:

  1. pad with $n$ zeros until message is a multiple of the block size
  2. Append a length block $L$ that contains the bit-length of the original message

enter image description here

This bit-wise PRF has lost its extension property, so we cannot simply turn it into an UHF. But we can view it as an UHF with injective encoding on its input. So I am not sure, if the extension property is a sufficient or a necessary condition. This is the motivation for my question.

  • $\begingroup$ I'm not quite sure what you're asking. Are you asking whether a block cipher in a modified CBC-MAC mode is a universal hash function? Or, are you asking whether a fixed-length universal hash can be used with a CBC-MAC setting, and the resulting mode would be universal? $\endgroup$ – poncho Aug 9 '17 at 14:18
  • $\begingroup$ I want to build a provably secure bit-wise UHF based on CBC. I just struggle with the order to get there. Either I start with a bit-wise PRF based on CBC (then I can't prove it as a UHF due to missing extentability) or I start with a block-wise UHF based on CBC and append a length block to get a bit-wise UHF (injective encoding). But I dont't know, if this is a valid way to go. (By the way I consider multiple messages with variable but polynomial message lengths and only PPT adversaries. The term 'block-wise' denotes messages with a length that is a multiple of the block size.) $\endgroup$ – Patrick K Aug 10 '17 at 7:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.