Subject: [Cfrg] Extending SIV to other ciphers and MAC algorithms

From: Neil Madden <[email-masked]>
Date: Thu, 4 Oct 2018 11:12:15 +0100

Hi,

I am interested in adapting the SIV construction to other ciphers and MAC algorithms. As currently specified in RFC 5297, the mode is only defined for a MAC (AES-CMAC) that produces a 128-bit tag length. Furthermore, it assumes that the tag length is exactly the same as the nonce/IV required by the cipher (i.e., also 128-bits for AES-CTR). This restriction to limit the authentication strength of the AEAD based on the length of the required nonce for confidentiality seems somewhat artificial to me.

As a concrete example, I am interested in SIV constructions based on XSalsa20 (or XChaCha20 as recently proposed on this list) together with some keyed hash MAC, such as HMAC-SHA256 or Blake2. XSalsa20 requires a nonce of 192-bits, while HMAC-SHA256 produces a MAC tag of 256 bits. I have a draft recommending MRAE modes for JOSE, and would like to include one non-AES algorithm that can be implemented well in software on platforms without AES hardware acceleration.

I believe that there are just two adaptions needed to make this work:

1. Adjusting the conditional XOR constant used in the doubling operation in s2v (https://tools.ietf.org/html/rfc5297#section-2.3) to account for other field sizes.
2. Defining the nonce used as input to the cipher as the left-most n bits of the authentication tag returned from s2v, where n is the size of the nonce required by the cipher (i.e., the full tag is output, but a truncation of it is used as the nonce).

For step 1, based on the comments in [1] and the table of primitive polynomials from [2], I think the polynomials and corresponding constants to use for different values of n (bit length of MAC output) are:

n = 128 gives x^128 + x^7 + x^2 + x + 1 and constant = 0^{120}10000111 (= 0x87 with leading 0s)
n = 192 gives x^192 + x^7 + x^2 + x + 1 and constant = 0^{184}10000111 (= 0x87 with more leading 0s)
n = 256 gives x^256 + x^10 + x^5 + x^2 + 1 and constant = 0^{245}10000100101 (= 0x00..0425)

Is this something that CFRG might support if I submitted a draft?

Regards,

Neil

[1]: http://web.cs.ucdavis.edu/~rogaway/papers/siv.pdf
[2]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.365.1806&rep=rep1&type=pdf

---

From: John Mattsson <[email-masked]>
Date: Thu, 4 Oct 2018 12:00:07 +0000

Hi,

I think it is hard to recommend encryption algorithms without nonce (e.g. Section 2.6 of RFC 5297) except in specific use cases. While such an algorithm does not fail by allowing an attacker to recover some secret parameter (plaintext, authentication key) if a nonce is repeated, it fails by allowing an attacker to always determine that two messages were equal or that they were not equal. This is not a nice property and should also be mitigated.

If you make a SIV mode for XChaCha20, I recommend a construction that still uses a nonce (like e.g. draft-irtf-cfrg-gcmsiv). Such a mode gives the expected properties unless both the nonce and message are reused.

Cheers,
John

On 2018-10-04, 12:12, "Cfrg on behalf of Neil Madden" <[email-masked] on behalf of [email-masked]> wrote:

Hi,

Regards,

Neil

[1]: http://web.cs.ucdavis.edu/~rogaway/papers/siv.pdf
[2]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.365.1806&rep=rep1&type=pdf
_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 4 Oct 2018 12:05:33 +0000

Dear Neil,

Speaking without my co-chair hat on: I think this could be interesting and useful. Have you by any chance looked at the portfolio of AEADs that has come out of the CAESAR competition to see if any of them would meet your needs?

https://competitions.cr.yp.to/caesar-submissions.html

Best wishes,

Kenny

-----Original Message-----
From: Cfrg <[email-masked]> on behalf of Neil Madden <[email-masked]>
Date: Thursday, 4 October 2018 at 11:12
To: "[email-masked]" <[email-masked]>
Subject: [Cfrg] Extending SIV to other ciphers and MAC algorithms

    Hi,

    

    

    Regards,
    
    Neil

---

From: Alexandre Anzala-Yamajako <[email-masked]>
Date: Thu, 4 Oct 2018 14:07:05 +0200

In this case I think you mean "unless the nonce, the message *and the key*
are reused" don't you ?

Best regards
Alexandre

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 4 Oct 2018 06:25:25 -0700

I am also interested in alternative SIV modes...

On Thu, Oct 4, 2018 at 3:12 AM Neil Madden <[email-masked]> wrote:

> As currently specified in RFC 5297, the mode is only defined for a MAC
> (AES-CMAC) that produces a 128-bit tag length.

...specifically I have considered writing an I-D for PMAC, and specifying
an RFC 5297-alike construction which swaps in PMAC in lieu of CMAC. I have
already implemented this construction in the https://miscreant.io library.

That said...

> As a concrete example, I am interested in SIV constructions based on
> XSalsa20 (or XChaCha20 as recently proposed on this list) together with
> some keyed hash MAC, such as HMAC-SHA256 or Blake2.

I think for IETF protocols you'll almost certainly want to use XChaCha20
over XSalsa20, as the latter has not been specified for IETF work, and is
redundant with XChaCha20.

If you're curious, here is some discussion about instantiating a SIV mode
using ChaCha20 and Poly1305 as primitives. This is of course a bit tricky,
as in the typical ChaCha20Poly1305 construction the Poly1305 key is derived
from the beginning of the ChaCha20 keystream (hence why I assume you're
proposing swapping in a PRF like HMAC as the basis of S2V):

https://github.com/briansmith/ring/issues/413

-- 
Tony Arcieri

---

From: Neil Madden <[email-masked]>
Date: Thu, 4 Oct 2018 14:53:02 +0100

> If you make a SIV mode for XChaCha20, I recommend a construction that still uses a nonce (like e.g. draft-irtf-cfrg-gcmsiv). Such a mode gives the expected properties unless both the nonce and mess…

Section 3 of RFC 5297 explicitly discusses using a nonce with SIV as the last associated data input. In this mode of operation SIV achieves normal nonce-based authenticated encryption security goals, with the added benefit of being misuse-resistant if you do accidentally reuse a nonce. The concrete instantiations in sections 6.1, 6.2 and 6.3 all require a nonce of at least 1 octet.

Kind regards,

Neil

---

From: Neil Madden <[email-masked]>
Date: Thu, 4 Oct 2018 15:15:01 +0100

I have had a look. As I understand it the only MRAE design still in the finalists is Deoxys-II, which is itself based on the AES round function.

— Neil

> On 4 Oct 2018, at 13:05, Paterson, Kenny <[email-masked]> wrote:
> 
> Dear Neil,
>

---

From: Neil Madden <[email-masked]>
Date: Thu, 4 Oct 2018 15:38:31 +0100

Hi Tony,

On 4 Oct 2018, at 14:25, Tony Arcieri <[email-masked]> wrote:
> As currently specified in RFC 5297, the mode is only defined for a MAC (AES-CMAC) that produces a 128-bit tag length.
> 
> ...specifically I have considered writing an I-D for PMAC, and specifying an RFC 5297-alike construction which swaps in PMAC in lieu of CMAC. I have already implemented this construction in the https://miscreant.io library.

Yes, I remember looking at miscreant. It’s a nice design.

> 
> That said...
>  
> As a concrete example, I am interested in SIV constructions based on XSalsa20 (or XChaCha20 as recently proposed on this list) together with some keyed hash MAC, such as HMAC-SHA256 or Blake2.
> 
> I think for IETF protocols you'll almost certainly want to use XChaCha20 over XSalsa20, as the latter has not been specified for IETF work, and is redundant with XChaCha20.

Thanks. I started writing some notes on this some time ago, at which point XSalsa20 was published while XChaCha20 was the “obvious” translation of the technique to ChaCha20, but didn’t seem to have a published reference document I could cite. Hopefully that will change if CFRG publish the XChaCha draft that was proposed.

> 
> If you're curious, here is some discussion about instantiating a SIV mode using ChaCha20 and Poly1305 as primitives. This is of course a bit tricky, as in the typical ChaCha20Poly1305 construction the Poly1305 key is derived from the beginning of the ChaCha20 keystream (hence why I assume you're proposing swapping in a PRF like HMAC as the basis of S2V):
> 

Yes, pretty much. The other reason was that if I found myself having to implement the mode from scratch, I would be more comfortable implementing SHA-256 or Blake2 than Poly1305, but that is more about my own experience and competence than about the security of the design. If you pair XChaCha20 with Blake2s then you can save some time by just copying + pasting the ChaCha round function, changing the direction of the rotations and you’re 90% done! :-)

— Neil

---

From: John Mattsson <[email-masked]>
Date: Thu, 4 Oct 2018 14:45:06 +0000

Thanks, I missed that extension to the SIV Encrypt algorithm. I think that is also a good input to the RFC5116bis discussion. An update should not only include discussion about algorithms without Nonce input but also the option to use all the possible nonce formats in the ADD input.

/John

On 2018-10-04, 15:53, "Neil Madden" <[email-masked]> wrote:

Kind regards,

Neil