3
$\begingroup$

The description of the sponge function on Crypto.Stackexchange contains the following text

The cryptographic sponge is a construction scheme for hash functions (and other symmetric primitives) based on an unkeyed permutation.

But is it possible to make use of a keyed permutation $f_k(x)$ to construct the sponge function? All constructions described in the “One-way compression function” article are based on the keyed permutation function. And section “Sponge construction” of this article contains the following information:

The sponge construction can be used to build one-way compression functions.

But the article “Sponge function” does not mention any presence of the key in the used permutation function $f(x)$. Does this imply that we can fix any public key $K$ and always use $f_K(x)$ as $f(x)$?

If yes, then how does the length of $K$ impact the security of the $n$-bit output, assuming that $n$ will be equal to the capacity divided by 2, as in SHA-3 (but if $K$ is public, then it seems that its length should not impact the security at all!)?

If no, then how to apply a pseudo-random permutation (that is, a keyed permutation function) $f_k(x)$ to construct a sponge function, and how will the length of $k$ impact the security of the $n$-bit output?

$\endgroup$
2
  • 1
    $\begingroup$ The value of the key shouldn't matter (so public fixed key should be fine). But the problem with most (practical) keyed permutations is rather that they only operate on eg 128 bit (with the largest non-composite one I know being Threefish-1024) and for comparison: Keccak / SHA3 uses a 1600 bit permutation. $\endgroup$
    – SEJPM
    Nov 10, 2018 at 18:03
  • $\begingroup$ @SEJPM: There exists XXTEA, which supports variable block length. Although there are attacks against XXTEA, it is possible to increase the number of rounds, thus increasing the difficulty of these attacks. $\endgroup$ Nov 12, 2018 at 6:12

1 Answer 1

2
$\begingroup$

Is it possible to apply a pseudo-random permutation (a keyed permutation) to construct a sponge function?

Yes, it is possible to construct a keyed-sponge function $\mathcal{F}_k(x, n)$ using a pseudo-random permutation $\pi$ and a secret key $k$. Here, $x$ refers to the input message, and $n$ to the number of output bits.

The sponge construction consists of $\pi$, and a state $S$, which is $s$-bits (sometimes also denoted $b$-bits). $S$ is conceptually divided into two parts: the leading section, called the rate $R$, which is $r$-bits; and, the trailing section, called the capacity $C$, which is $c$-bits. The following equation holds: $b = s = r + c$. For how $x$ is absorbed into $R$, see this.

I'll use $k_{enc}$ here as shorthand to refer to $k_{enc} = \textrm{encode_key(}k, \mathcal{F}\textrm{)}$ to abstract away some of the complexity involved in domain-separation and how $k$ is preprocessed to fit within a certain portion of $S$. The function $\textrm{encode_key(}k, \mathcal{F}\textrm{)}$ may encode $k$ with concatenated metadata, like its length, and pad it with a function-specific value to the appropriate size. The exact metadata, value, size and portion of $S$ may be defined in different ways by the designer of $\mathcal{F}$ and the specific approach used in the construction.

There are several approaches for how to construct a keyed-sponge mentioned in the literature. There's the Outer-Keyed Sponge (OKS), which absorbs $k_{enc}$ into $R$ prior to absorbing $x$ into $R$. Also, the Inner-Keyed Sponge (IKS), which sets $C = k_{enc}$ prior to absorbing $x$ into $R$. And, there's the Full-Keyed Sponge (FKS), which sets $S = k_{enc}$ prior to absorbing $x$ into the full $S$. The KMAC construction, for instance, uses OKS to initialize its internal keyed-permutation. At a minimum, they all assume $k$ and $C$ will be kept secret, as well as all of the initial $S$ before the first call to $\pi(S)$ after $k_{enc}$ has been incorporated.

But the article “Sponge function” does not mention any presence of the key in the used permutation function $f(x)$. Does this imply that we can fix any public key $K$ and always use $f_K(x)$ as $f(x)$?

No, $k$ is expected to be kept secret to the communicating parties. Using a public key(1), or parameter, $K$ as the key for a keyed-sponge permutation is not going to give you the security properties you may be looking for.(2)(3)(4) Though, there is utility to including a public parameter $K$ in the input as something other than a key, like as a nonce, or for domain separation. In these cases, the length of $K$ may only incidentally affect the security provided by the nonce or domain-separator, insofar as they both need to be canonically unique to each usage context.

If no, then [...] how will the length of $k$ impact the security of the $n$-bit output?

In the paper Key Prediction Security of Keyed Sponges(5), the simplified PRF security bounds of the different approaches is defined by a notion called key-prediction security (key-pre). FKS is considered a generalization of IKS in this paper, so the same bounds apply to both. The output size $n$ is not directly considered in these bounds. In general, for sponges, the expected resistance against output collisions is ~$\min{ \left\{2^{n/2}, 2^{c/2}\right\} }$, and the expected resistance against inner collisions is ~$2^{c/2}$.(6 §6.2) The provided equations to estimate aversarial advantage refer to: $M$, the number of queries an adversary makes to $\mathcal{F}_{\bar k}(\bar{x}, n)$; $N$, the number of queries an adversary makes to $\pi{(\bar{S})}$; and, $\lambda$, which applies to OKS, and is the number of rounds of $\pi(S)$ that are performed when absorbing $k_{enc}$ into $R$. $\bar{k}$, $\bar{x}$ and $\bar{S}$ are guesses the adversary makes for the values $k$, $x$ and $S$, respectively.

$\boldsymbol{ \mathrm{Adv}_{\mathcal{F}}^{ \mathrm{key-pre} } }(N)$ is the probability that the adversary made queries to the underlying permutation that match the key input to $\mathcal{F} \in$ $\{$OKS, IKS, FKS$\}$ $-§1.1$

\begin{equation} \label{eq:key-prediction-security-oks} \boldsymbol{ \mathrm{Adv}_{\boldsymbol{ \mathrm{OKS} }}^{ \mathrm{key-pre} } }(N) \lesssim c^{\lambda - 1} \frac{N}{2^{|k|}} \tag{Ref. a} \end{equation}

\ref{eq:key-prediction-security-oks}: §1.2, Equation 4

\begin{equation} \label{eq:key-prediction-security-fks} \boldsymbol{ \mathrm{Adv}_{\boldsymbol{ \mathrm{FKS} }}^{ \mathrm{key-pre} } }(N) \le \frac{N}{2^{|k|}} \tag{Ref. b} \end{equation}

\ref{eq:key-prediction-security-fks}: §1.2, Equation 2

\begin{equation} \label{eq:prf-security} \boldsymbol{ \mathrm{Adv}_{\mathcal{F}}^{ \mathrm{prf} } }(M, N) \approx \frac{M^2}{2^c} + \frac{MN}{2^c} + \boldsymbol{ \mathrm{Adv}_{\mathcal{F}}^{ \mathrm{key-pre} } }(N) \tag{Ref. c} \end{equation}

\ref{eq:prf-security}: §1.1, Equation 1

And, when one also considers absorbing a nonce (which is used only once for a given $k$) into $R$ (or into all of $S$ for FKS) prior to absorbing $x$, the security bounds are shown to get a bit better:

\begin{equation} \label{eq:prf-security-nonce-respecting} \boldsymbol{ \mathrm{Adv}_{\mathcal{F}_{_{nonce}}}^{ \mathrm{prf} } }(M, N) \approx \frac{M^2}{2^s} + \frac{MN}{2^c} + \boldsymbol{ \mathrm{Adv}_{\mathcal{F}}^{ \mathrm{key-pre} } }(N) \tag{Ref. d} \end{equation}

\ref{eq:prf-security-nonce-respecting}: §1.3, Equation 5

$\endgroup$
4
  • $\begingroup$ KMAC is a PRF, not a PRP. I think you've misunderstood what OP's asking. $\endgroup$
    – DannyNiu
    Aug 5, 2023 at 7:48
  • $\begingroup$ Oh yes, that's true. Would it not be helpful for OP to investigate how KMAC answers the question > "how to apply a pseudo-random permutation (that is, a keyed permutation function) $f_k(x)$ to construct a sponge function, and how will the length of $k$ impact the security of the $n$-bit output." since it has a vetted security analysis, it uses a permutation, & it keys the permutation by xoring a metadata encoded, and padded, key into the initial state of the sponge? Am I off-base here? If not, I can try to elaborate. Maybe include other options like replacing the initial capacity bits with $k$ $\endgroup$
    – aiootp
    Aug 5, 2023 at 8:21
  • 1
    $\begingroup$ You missed several sub-points in the "If yes" and "If not" question cases. If those can be filled, I think It'll be better. $\endgroup$
    – DannyNiu
    Aug 5, 2023 at 10:37
  • $\begingroup$ @DannyNiu Ok, I gave it a shot. Thanks for your feedback! $\endgroup$
    – aiootp
    Aug 6, 2023 at 2:33

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.