I'm implementing a hobby cryptosystem for fun and to increase my knowledge on the subject, and I was wondering if the OAEP construct was still sufficient as an all-or-nothing-transform if variable length hash functions (specifically SHAKE256) are used for the $G$ and $H$ random oracles.

I already found a paper showing that OAEP was functional as an all-or-nothing-transform, but I'd like to use SHAKE256 as a hash function because it allows for arbitrary-length messages.

My current implementation is here. I pad the message to a minimum of 32 bytes, and then then my $k0$ length, or the length of the additional information added, is another 32 bytes.

I'm wondering if this use of SHAKE256 is theoretically secure, or if there is a problem with using a variable output hash function with OAEP. I'm not concerned with side channel attacks, this is a purely educational implementation.

  • $\begingroup$ Why not just use RSA-KEM? Much simpler! Pick $0 \leq x < n$ uniformly at random; use the key $k = H(x)$ (say, SHA-256 on the little-endian encoding of $x$); send the encapsulation $y = x^3 \bmod n$. $\endgroup$ – Squeamish Ossifrage Feb 27 '19 at 18:47
  • $\begingroup$ This would be before a symmetric cipher as an AONT, does RSA-KEM serve this purpose as well? $\endgroup$ – ThePlasmaRailgun Feb 27 '19 at 21:00
  • $\begingroup$ You then use $k$ as a key for an authenticated cipher (actually, a DEM, or ‘data encapsulation method’, which need merely serve as a one-time authenticated cipher). No need for an AONT—just a hash mapping integers mod $n$ into 256-bit keys. $\endgroup$ – Squeamish Ossifrage Feb 27 '19 at 21:22
  • $\begingroup$ I don't think that's what I'm looking for, I'm implementing a AONT for the actual cipher data, not a key. $\endgroup$ – ThePlasmaRailgun Feb 27 '19 at 21:36
  • $\begingroup$ Got it—you're just looking for the AONT, not for anything involving, e.g., RSAES-OAEP. $\endgroup$ – Squeamish Ossifrage Feb 27 '19 at 21:50

Beware that if $n < m$, then $\operatorname{SHAKE256-}\!n(x)$ is a prefix of $\operatorname{SHAKE256-}\!m(x)$, so the two functions are not really independent random oracles as the usual OAEP theorems posit.

If you set $G(x) = \operatorname{SHAKE256}(0 \mathbin\| x)$ and $H(s) = \operatorname{SHAKE256}(1 \mathbin\| s)$, that should be adequate to (conjecturally) satisfy the hypotheses of the theorems without requiring additional analysis to study the possibility of collisions between the inputs to $G$ and $H$.

Alternatively, if the inputs to $G$ and $H$ are guaranteed to have distinct lengths in your application, then $G(x) = \operatorname{SHAKE256}(x)$ and $H(s) = \operatorname{SHAKE256}(s)$ should work too. But it won't hurt, and might be safer to avoid mistakes, if you always use a unique prefix, whether it be a 0 bit vs. a 1 bit, or the string G oracle vs. H oracle, etc.

| improve this answer | |
  • $\begingroup$ Thank you! Is this prefix behavior specific to the squeezing of the sponge function, or is it common to all XOF hash functions? $\endgroup$ – ThePlasmaRailgun Feb 28 '19 at 5:36
  • $\begingroup$ @ThePlasmaRailgun Nothing to do with sponges in particular (or even XOFs), everything to do with using one (conjectured) uniform random function to make two independent uniform random functions (of slightly shorter inputs). See crypto.stackexchange.com/a/67350 for what can happen if you try to use the same random oracle twice for what should be independent purposes, in a somewhat different context. $\endgroup$ – Squeamish Ossifrage Feb 28 '19 at 6:53
  • $\begingroup$ This is not to say that $G = H$ is necessarily broken—just that it takes more analysis, and you can save yourself the trouble of that analysis by using a unique prefix. This is a general design principle in an application that uses the same hash function or signature scheme and signing key for many purposes. $\endgroup$ – Squeamish Ossifrage Feb 28 '19 at 6:59
  • $\begingroup$ Ok, will do! Thank you so much for your help. $\endgroup$ – ThePlasmaRailgun Feb 28 '19 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.