SIV - Synthetic IV - S2V Construction? Benefits over a MAC or Hash?

Question

Looking at the SIV construction in rfc-5297 - https://www.rfc-editor.org/rfc/rfc5297

With regards to the generation of the SIV, using S2V construction, I am struggling to find the benefits of the chosen method of combining MAC codes together and has some questions I am struggling with:

1. What benefits does the doubling and xor provide over say a modern MAC and/or Hash function? For example, if you used the following, how does the security differ?

$MAC( MAC($x$0), ... MAC($X$i)) $ instead of

dbl_Xor( MAC($x$0), ... MAC($X$i)) Where xi represents of your header inputs for 0 < i < blocksize-1.

2. Looking at the choice of a MAC, the proof works if its a secure-PRF. The authors choose CMAC and list that alternative could be used under different circumstances. There are many discussions on this forum on cipher versus non cipher based MACs and the differences mostly come down reducing the number of components you need to trust. Given this, for a SIV construction could you use a modern hash for the MAC instead of CMAC? say SHA3 or Skein-MAC (which is based off a tweakable cipher as well). ?

Thanks and regards

Answer 1

Rogways's paper on the algorithm goes deeper into detail: http://web.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf and discusses more about design rationale and provides proof (more than the RFC).

I find a lot of benefits in SIV and S2V. For me, the most important is that it can be used without nonce. The second most important is that the mode builds on widely available modes of operation, but on the other hand just using single 128-bit cipher (typically AES, just the forward cipher function). If the implementor has some SW crypto library or FIPS 140-2 validated cryptographic module available, chances are that those have AES-CTR algorithm and AES-CMAC algorithm (if they have AES-CBCMAC or AES-CBC then AES-CMAC can be built easily).

But the question was not about these benefits. So I address the questions:

Answering the first question

The operations doubling and xor in S2V construct are primarily intended to be easy to implement yet sufficiently secure. Thus,

$MAC( MAC($x$0), ... MAC($X$i)) $

instead of

dbl_Xor( MAC($x$0), ... MAC($X$i))

invokes the MAC function one more time. For typical amounts of segments in S2V this is for many implementations a slow down.

The most typical amounts of input strings to S2V include:

1. Plaintext or authenticated data without nonce
2. Plaintext or authenticated data with nonce; or plaintext with additional authenticated data without nonce
3. Plaintext and additional authenticated data with nonce

Because the designers wanted a function that can easily handle any of these cases, they designed S2V, which can handle any of these cases and more. It is common that additional authenticated data is factually combination of multiple separate fields and thus it can be seen as nice convenience that it can be fed to S2V as multiple separate fields rather than needing to specify format that combines the fields.

Answering the second question

The SIV mode generates 128-bit IV for AES-CTR and authentication tag with the S2V algorithm. Therefore, perhaps the most prominent benefit of alternative MAC algorithms, larger tag size, would not be realized with SIV mode. Currently many modes of additional authenticated encryption aim at simplicity to have their design depend on as few underlying ciphers and other components as possible. Using separate algorithm for MAC would go against that goal. Additionally, similar pre-existing algorithms like AES-CCM (not cipher misuse resistant, but otherwise for many of same uses than SIV-AES) already require just one 128-bit block cipher and use only forward function.