Score:2

How do I construct the Fn family of functions of WOTS+ using SHA3?

ca flag

From the WOTS+ paper:

Furthermore, W-OTS+ uses a family of functions Fn : {f_k : {0, 1}^n → {0, 1}^n | k ∈ Kn} with key space Kn. The reader might think of it as a cryptographic hash function family that is non-compressing. Using Fn we define the following chaining function.

I do not understand the meaning of this paragraph. My interpretation of it is that I need a family of n n-bit pseudorandom functions, where n is the security parameter. That is, if the security parameter is 128, then I need 128 different 128-bit pseudo-random functions. If this understanding is correct, and assuming n=128, can I define F(k) as just the sha3 (which resists length extension attacks) of k appended to the message, then sliced to 128-bits? That is, something like:

// Generates the kth pseudo-random function, with n=128
fn kth_random_function(k: uint8) -> (bytes -> uint128):
  return λ(msg: bytes) => uint128(sha3(u8_to_byte(k) ++ msg)[0:16])
Maarten Bodewes avatar
in flag
Binary is not hexadecimals; you should definitely not encode `k` before you use it (and usually not afterwards either, if binary is allowed). Furthermore, if you're going to use a keyed hash you might as well use KMAC. Note that KMAC offers an option to set the output size with 128 and 256 bit output being standardized options.
ca flag
@MaartenBodewes That was just for simplicity, assuming sha3 is operating on hex. I've edited to improve the pseudocode. Isn't KMAC with 128 bit output just what I described? I.e., taking the first 128 bits of `SHA3(k || m)`?
Maarten Bodewes avatar
in flag
It's almost literally a bit different. But in general I would use the algorithms for which they are supposed to operate. Say you have this function in hardware: in that case SHA-3 may not accept a key object, while KMAC would.
ca flag
Makes sense, thank you.
Maarten Bodewes avatar
in flag
KMAC: 1. newX = bytepad(encode_string(K), 168) || X || right_encode(L). 2. return cSHAKE128(newX, L, “KMAC”, S). So yeah, not quite SHA-3, but very similar if you go and look at the actual sponge construction. S is usually empty, but there is an additional encoding of output size L included and a "KMAC" indicator. I don't know W-OTS well enough to answer by the way, I'm afraid that I overlook some requirement w.r.t. the non-compression part.
Score:1
in flag

You actually need a family of second-preimage resistant, undetectable, one-way functions. In general, any secure cryptographic hash function (SHA2, SHA3, ...) should work with a little tweak to make it keyed. You do not need it to be a PRF, and the function is fixed length. Hence, if you also fix the key length, using

SHA3(K || M)

is fine (and then taking the amount of output bits needed). For SHA2 (or any Merkle-Damgard construction) you obtain a nicer security argument, if you first absorb the key into a compression function call and then the message. I.e., you do

SHA2-256( pad(K, 512) || M ),

where pad(K, 512) applies an injective padding to turn K into a 512 bit string. Assuming fixed length for K, appending sufficiently many 0's works just fine. Here I took into account that the block length of SHA2-256 is 512 bits. For different block-lengths you have to adjust the length accordingly. Because of Merkle-Damgard strengthening (which requires the application of the length padding) this does not increase the number of compression function calls. At the same time, you can think about this as first computing a pseudorandom IV from K which is then used to hash M.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.