2
$\begingroup$

From draft-madden-generalised-siv:

SIV defines a particularly efficient encoding provided by the function S2V (for "string to vector") that converts a single-string PRF to a vector input PRF. S2V is defined using bitwise exclusive OR (XOR) and a doubling operation in the finite field GF(2^n) where n is the bit length of the output of the PRF.

Here's a diagram from the Deterministic Authenticated-Encryption paper:

S2V diagram

Further information and diagrams can also be found in RFC 5297.

My question is if the PRF is a keyed collision-resistant hash function (e.g., like here), does S2V have the same collision resistance as concatenation (with length encoding for variable-length inputs)?

Improve this question
$\endgroup$
1
  • $\begingroup$ The other approach to concatenation that definitely maintains collision resistance is an NMAC-style construction. $\endgroup$ Commented Apr 15 at 7:52

1 Answer 1

Reset to default
5
$\begingroup$

My question is if the PRF is a collision-resistant hash function, does S2V have the same collision resistance as concatenation (with length encoding for variable-length inputs)?

No, with a public PRF (such as a collision-resistant hash function), the construction does not achieve second preimage resistance (and hence not collision resistance either).

The method for finding second preimages is straight-forward; the construction can be simplified as:

$$Z = f(T( X_n \oplus \text{Other Stuff} ))$$

Where 'Other Stuff' is a public function of the previous parts of the message.

Hence, to find a second preimage to an arbitrary message (with a specific $X_n, \text{Other Stuff}$), you pick an arbitrary second preliminary part of the message, compute the corresponding $\text{Other Stuff'}$ and then set the last full block as:

$$X'_n = X_n \oplus \text{Other Stuff} \oplus \text{Other Stuff'}$$

Now, this observation does not apply either to GCM-SIV or the generalized version in draft-madden-generalised-siv, because those use a keyed PRF that cannot be computed by the adversary who does not know the key. This observation shows that such a keyed PRF is mandatory in this construction.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. That's what I thought. Please could you also comment on the collision resistance if the key is known/chosen by the adversary. Is that equivalent to the public case? I'll edit my question to mention keyed hash functions as well. $\endgroup$ Commented Apr 15 at 16:27
  • 1
    $\begingroup$ @samuel-lucas6: having the key known by the adversary is the public case (as far as the adversary is concerned). Having the key chosen by the adversary is even more so. Both means that you have essentially no collision resistance. $\endgroup$ Commented Apr 15 at 17:06

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.