Subject: [Cfrg] Farfalle-SANSE

From: Gilles Van Assche <[email-masked]>
Date: Fri, 2 Nov 2018 13:35:41 +0100

Dear all,

On a related note, we published at ToSC last year (and presented at FSE
2018) the Kravatte pseudo-random function [1], to which an SIV mode can
be attached. More specifically, we recently specified the SIV-based
authenticated encryption scheme Kravatte-SANSE [2]. As a feature, it
also supports sessions, for use cases where multiple messages are
exchanged and where each tag authenticates all messages already sent so
far in the session.

This function is based on the 6-round Keccak-p permutation and performs
well in software without AES hardware acceleration. For instance,
Kravatte-SANSE processes plaintext and metadata at 1.32 cycles/byte on
Skylake and at 0.84 c/b on SkylakeX processors.

Would this be of interest to CFRG?

Kind regards,
Guido, Joan, Seth, Michaël, Gilles and Ronny

[1] https://tosc.iacr.org/index.php/ToSC/article/view/855
[2] https://keccak.team/2018/kravatte_sane_sanse.html

On 4/10/18 12:12, Neil Madden wrote:
> 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
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Gilles Van Assche <[email-masked]>
Date: Fri, 2 Nov 2018 13:52:21 +0100

(sorry, with the correct subject this time…)

Dear all,

Kind regards,

---

From: Russ Housley <[email-masked]>
Date: Sat, 3 Nov 2018 20:57:47 -0400

Gilles:

I am interesting in the property that "each tag authenticates all messages already sent so far in the session".  I have not had an opportunity to review the references provided.  Does this mechanism work even if some of the messages are not delivered?

Russ

> From: Gilles Van Assche <[email-masked]>
> Subject: [Cfrg] Kravatte-SANSE
> Date: November 2, 2018 at 8:52:21 AM EDT
> To: <[email-masked]>
>

---

From: Gilles Van Assche <[email-masked]>
Date: Tue, 6 Nov 2018 18:17:10 +0100

Hi Russ,

The tag authenticates the exact sequence, so any missing or reordered
message will cause a mismatch. I guess the best is to use sessions on
top of a layer that handles the delivery of messages.

A possible way to use sessions is to authenticate the exchange between a
client and a server, where they take turns as sender/receiver. If the
client sends a request to the server, the tag on the server's reply
automatically binds it to the client's request. Then, even a simple
confirmation from the server cannot be replayed on another request.

Kind regards,
Gilles

On 4/11/18 01:57, Russ Housley wrote:
> Gilles:
>
> I am interesting in the property that "each tag authenticates all
> messages already sent so far in the session".  I have not had an
> opportunity to review the references provided.  Does this mechanism
> work even if some of the messages are not delivered?
>
> Russ
>
>
>> *From: *Gilles Van Assche <[email-masked]
>> <mailto:[email-masked]>>
>> *Subject: **[Cfrg] Kravatte-SANSE*
>> *Date: *November 2, 2018 at 8:52:21 AM EDT
>> *To: *<[email-masked] <mailto:[email-masked]>>
>>
>>> 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.
>>>
>>> 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 = 192 gives x^192 + x^7 + x^2 + x + 1 and constant =
>>> 0^{184}10000111 (= 0x87 with more leading 0s)
>>> [2]:
>>> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.365.1806&rep=rep1&type=pdf
>>> [email-masked] <mailto:[email-masked]>
>> [email-masked] <mailto:[email-masked]>

---

From: Nick Sullivan <[email-masked]>
Date: Thu, 29 Nov 2018 14:48:55 -0800

Hi Gilles,

I'm interested in this construction but I'd like to know more. What sort of
applications do you think this function would have within the IETF? Would
it be useful as a general replacement for PRFs in, for example, TLS? Can it
leverage hardware-specific instructions?

Best,
Nick

On Fri, Nov 2, 2018 at 5:34 AM Gilles Van Assche <[email-masked]>
wrote:

> > 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.
> >
> 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.
> >
> > 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.
> 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).
> >
> polynomials from [2], I think the polynomials and corresponding constants
> to use for different values of n (bit length of MAC output) are:
> >