[noise] PSK-based resumption, postquantum, and XOFs

[Trevor Perrin]

On Mon, Nov 27, 2017 at 11:17 PM, David Wong <davidwong.crypto at gmail.com> wrote:
>> If an XOF is chosen, these functions are constructed:
>>  - HASH(message) = XOF(message)
>>  - PRF(key, message) = XOF(pad_to_block(key) || message)
>>  - KDF(key, message) = XOF(pad_to_block(key) || input)
>
> If you look at KMAC, it is really just SHAKE (or rather cSHAKE) with
> optimizations for precomputing a key.

KMAC is more complicated than the above SHAKE-based "PRF" in a few ways:

 (1) The first block of KMAC absorbs the string "KMAC" and an optional
user-specified customization string.

 (2) The second block of KMAC absorbs the key, with a length prefix
(this is similar to the first block of "PRF", except for the added
length prefix).

 (3) At the end, KMAC contains the desired output length (or 2-bytes
of zeros if you want a SHAKE-style arbitrary-length output stream).


> Knowing that:
>
> 1. using cSHAKE sounds like the way to go (with custom strings for
> Noise and the operation name)

I'm not sure the above complications add value over the simpler
SHAKE-based "PRF":

 (1) Noise hashes the protocol name into ck and h at the beginning, so
we don't need to repeat names or customization strings in every
operation.

 (2) Noise uses fixed-length keys determined by the protocol name, so
I don't think we need to repeat key length fields in each operation
(also, we already use HMAC, which doesn't explicitly include the
key-length; if this was a problem we'd already be affected).

 (3) Instead of using the output-length field, it seems easier to use
SHAKE-style arbitrary-length output, and just take however many bytes
we need.


> 2. do you need the optimization? It sounds like the key is going to
> change so you would not need to pad the key to the block


So:

XOF(key || message)
vs
XOF(key || padding_to_block || message)

I thought the padding helped security, or at least made the assumptions simpler?

Padding the key to a full block is done in HMAC, KMAC, and keyed
BLAKE2, so it might be worth doing just so people don't worry we've
cut some corner and reduced security.

We should probably get some cryptographer opinions here, though...

Trevor