Subject: Re: [lamps] Call for Presentations at the LAMPS Interim Meeting on 28

From: Tadahiko Ito <[email-masked]>
Date: Tue, 12 Jan 2021 15:26:26 +0900

Hi Russ

I also want to talk a bit about separation of hash and asymmetric function.

It seems we cannot separate those functions in some PQC algorithms.

In current RSA or ECC, we use data control service to calculate hash
function part, and use key management service to calculate asymmetric
function part for large file.

For instance, we (our company) currently have a usecase of signing 10GB PDF
file (with HSM). Separation of those functions is necessary for such a
usecases according to limitation in HSM resource.

It would be OK if we introduce one more hash function to signing data, but
I believe it may damage interoperability. I would like to ask what we
should do in such a usecase.

My draft paper is following (it is a draft, we are not sure if we can
revise before the meeting)

<https://eprint.iacr.org/2020/990>

Regards Tadahiko Ito

---

From: Mike Ounsworth <[email-masked]>
Date: Tue, 12 Jan 2021 15:23:02 +0000

Hello,

I want to highlight two excellent points that you make in your paper:

1. Using a fixed-length hash value in place of the message may affect the security proof of the asymmetric algorithm, so this probably needs to be validated by cryptographers for each PQC algorithm. It seems from your paper that qTESLA is already compatible with this mode. I imagine hash-based signatures would also be ok with pre-hashing. Do any other PQC signature candidates have proofs that pre-hashing does not affect security? I imagine that different parameter sets / security levels of a given PQC algorithm may need different lengths of pre-hash in order to preserve security level.

2. "In addition, it is hard to say that there is no possibility that a new patent risk will occur due to changes on the use of hashes."

I would support LAMPS looking at this, though it probably needs involvement from other groups, especially on the security proof side.

---
Mike Ounsworth

From: Spasm <[email-masked]> On Behalf Of Tadahiko Ito
Sent: January 12, 2021 12:26 AM
To: Russ Housley <[email-masked]>
Cc: LAMPS WG <[email-masked]>
Subject: [EXTERNAL]Re: [lamps] Call for Presentations at the LAMPS Interim Meeting on 28

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.
________________________________________
Hi Russ
 
I also want to talk a bit about separation of hash and asymmetric function.
It seems we cannot separate those functions in some PQC algorithms.
In current RSA or ECC, we use data control service to calculate hash function part, and use key management service to calculate asymmetric function part for large file.

For instance, we (our company) currently have a usecase of signing 10GB PDF file (with HSM). Separation of those functions is necessary for such a usecases according to limitation in HSM resource.
 
It would be OK if we introduce one more hash function to signing data, but I believe it may damage interoperability. I would like to ask what we should do in such a usecase.
 
My draft paper is following (it is a draft, we are not sure if we can revise before the meeting)
<https://eprint.iacr.org/2020/990>
 
Regards Tadahiko Ito

---

From: Russ Housley <[email-masked]>
Date: Tue, 12 Jan 2021 10:48:34 -0500

Tadahiko:

It seems you are talking about PQC signatures in CMS.  PDF signatures employ an early version on CMS.  Would you be able to make a presentation at the interim meeting?  

Russ

> On Jan 12, 2021, at 1:26 AM, Tadahiko Ito <[email-masked]> wrote:
> 
> Hi Russ
>  
> <https://eprint.iacr.org/2020/990 <https://eprint.iacr.org/2020/990>>
>  
> Regards Tadahiko Ito

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Wed, 13 Jan 2021 04:36:33 +0000

Hi Tadahiko-san,

We dealt with a similar issue when trying to introduce HBS signatures in CMS 
implementations with an API which demanded the message digest function.

I think for such usecases someone could do the same as in Ed25519ph and 
Ed448ph. You pre-hash/digest the message and pass that to the PQ signature 
API. Not ideal because of collisions, but as long as the hash/digest function 
is collision resistant and offers at least as many classical and PQ bits of 
security as the PQ signature scheme, you are OK.

For example you could define a DilithiumIII identifier and a DilithiumIIIph 
identifier. The latter can hardcode SHA2-512(M) as the digest, or 
SHAKE256(M,64) similar to what RFC8032 does.

Rgs,

Panos

From: Spasm <[email-masked]> On Behalf Of Tadahiko Ito
Sent: Tuesday, January 12, 2021 1:26 AM
To: Russ Housley <[email-masked]>
Cc: LAMPS WG <[email-masked]>
Subject: Re: [lamps] Call for Presentations at the LAMPS Interim Meeting on 28

Hi Russ

In current RSA or ECC, we use data control service to calculate hash function 
part, and use key management service to calculate asymmetric function part for 
large file.

It would be OK if we introduce one more hash function to signing data, but I 
believe it may damage interoperability. I would like to ask what we should do 
in such a usecase.

My draft paper is following (it is a draft, we are not sure if we can revise 
before the meeting)

Regards Tadahiko Ito

---

From: "Dang, Quynh H. (Fed)" <[email-masked]>
Date: Wed, 13 Jan 2021 14:52:33 +0000

Hi Tadahiko and Panos,

If we have pre-hash and non-prehash versions, then the asymmetric operation must be domain-separated between the 2.  Otherwise, obtaining a signature from a pre-hash version is an attack on the non-prehash version.

For example, step 10 in Dilithium's signing operation:
hash(tr || M) would become hash(0|| tr || M) and
hash(1|| tr || M) for the pre-hash and non-prehash options, for example.

Regards,
Quynh.

________________________________
From: Spasm <[email-masked]> on behalf of Panos Kampanakis (pkampana) <pkampana=[email-masked]>
Sent: Tuesday, January 12, 2021 11:36 PM
To: Tadahiko Ito <[email-masked]>
Cc: LAMPS WG <[email-masked]>
Subject: Re: [lamps] Call for Presentations at the LAMPS Interim Meeting on 28

Hi Tadahiko-san,

We dealt with a similar issue when trying to introduce HBS signatures in CMS implementations with an API which demanded the message digest function.

I think for such usecases someone could do the same as in Ed25519ph and Ed448ph. You pre-hash/digest the message and pass that to the PQ signature API. Not ideal because of collisions, but as long as the hash/digest function is collision resistant and offers at least as many classical and PQ bits of security as the PQ signature scheme, you are OK.

For example you could define a DilithiumIII identifier and a DilithiumIIIph identifier. The latter can hardcode SHA2-512(M) as the digest, or SHAKE256(M,64) similar to what RFC8032 does.

Rgs,

Panos

Hi Russ

<https://eprint.iacr.org/2020/990<https://gcc02.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F2020%2F990&data=04%7C01%7Cquynh.dang%40nist.gov%7Ca5a2bf18b7a64ce675c808d8b77cdd6d%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C637461094229173904%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=4b2EJXVMkBxHH0MYOzjn7bpHzP4CkBFY9BxBKi2yuZE%3D&reserved=0>>

Regards Tadahiko Ito

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 14 Jan 2021 14:10:16 +0200

On Tue, Jan 12, 2021 at 03:23:02PM +0000, Mike Ounsworth wrote:
> 1. Using a fixed-length hash value in place of the message may affect
> the security proof of the asymmetric algorithm, so this probably
> needs to be validated by cryptographers for each PQC algorithm. It
> seems from your paper that qTESLA is already compatible with this
> mode. I imagine hash-based signatures would also be ok with
> pre-hashing. Do any other PQC signature candidates have proofs that
> pre-hashing does not affect security? 

There are at least two ways pre-hashing can cause security proofs
to break, with concrete attacks:

Firstly (this was already brought up), if signature fails to
contextualize on presence of prehash, then pre-hashed message would
validate as signature of another plain message.

And without support from the signature algorithm itself, this impiles
pre-encoding even in the plain message case.

Secondly, if signature is salted, using unsalted prehash will weaken
the signature.

FALCON, SPHINCS+ and Dilithium all seem to be salted. Thus to not weaken
security, one needs to first hash random nonce or public key _before_
the message (random nonce is stronger). 

Note that the tr in Dilithium that is a part of the private key is
actually just hash of the public key (it is part of secret key, as it
is needed for signing).

-Ilari