Re: [lamps] [EXTERNAL] pre-hashing the OID in draft-ounsworth-pq-composite-sigs-10

["Markku-Juhani O. Saarinen" <[e-mail]>]

Falko,

Perhaps it is better to just replace M with mu. That way there is no need
to change any of the internals -- public key would be hashed twice in
digest, but that's a minor loss if there is unwillingness to move those
variables to mu.

It's necessarily not so much a hardware issue albeit engineering the option
into a secure element to take in M itself or pass hash contexts is hard --
hence the requirement for computing mu externally, as in Dilithium.

It just seems that also it is easier to have an consistent interface with 1
input (mu) than with several inputs and flags. Anyway, I'll throw in that
proposal, you can send in an another proposal. I'm fine with either one.

Cheers,
-markku

Dr. Markku-Juhani O. Saarinen
Staff Cryptography Architect
PQShield Ltd



M:             [phone]

E:              [e-mail]
W:             www.pqshield.com


On Tue, Nov 21, 2023 at 1:11 PM Falko Strenzke <[e-mail]>
wrote:

> Hi Markkhu,
>
> I understand the hardware perspective, but I don't think that it is
> necessary or even possible that NIST opens up the algorithm interface like
> you propose.
>
> First of all, a hardware implementation is not bound to provide a module
> that has the interface that NIST defines. For instance hardware support for
> ECC and RSA for embedded applications that I know works on the arithmetic
> level. So whatever NIST will specifies as the algorithm interface, this
> does not affect the hardware design.
>
> Second, it will most likely matter for FIPS certifications how NIST
> specifies the algorithm and its interface. Namely, as I understand from
> previous conversations on one of our lists, FIPS conformance will require
> the implementation of the FIPS-algorithm *within the secure module*. And
> that should most likely have be the "closed" algorithm interface that I
> proposed, as otherwise there are too many critical operations left to the
> application using the module. This is why I think NIST will not open up the
> algorithm interface like you propose.
>
> Does that make sense to you?
>
> - Falko
> Am 21.11.23 um 13:46 schrieb Markku-Juhani O. Saarinen:
>
> Falko,
>
> That seems workable, albeit slightly non-ideal from hardware perspective.
> One alternative is to align the interface and signature logic with ML-DSA /
> Dilithium. The module would always be passed "mu" to represent the message
> to be signed/verified:
>
> mu = H( PK || M )
>
> Where PK = (PK.seed, PK.root) in the case of SPHINCS+, and maps to "tr" in
> Dilithium, albeit without the hash (in Dilithium tr=H(PK)). In both cases
> mu has at least "double" (collision-resistant) length -- perhaps always 512
> bits as in Dilithium.
>
> Changes in Alg. 18, slh_sign():
> Line 7: R <- PRF_msg(SK.prf, opt_rand, mu)
> Line 10: digest <- H_msg(R, mu)
>
> Changes in Alg. 19, slh_verify():
> Line 9: digest <- H_msg(R, mu)
>
> This corresponds to the BUFF transform (See Fig 6 https://ia.cr/2020/1525
> ), which Dilithium already implements.
>
> Note the mapping; R = rho' in Dilithium: SK.prf = "K" in Dilithium,
> opt_rand = "rnd" in Dilithium.
>
> Cheers,
> -markku
>
> On Tue, Nov 21, 2023 at 12:25 PM Falko Strenzke <[e-mail]>
> wrote:
>
>> What I would propose is just to request the features of
>> Ed25519ctx/Ed25519ph in RFC 8032 for the PQC signature algorithms, i.e. at
>> the moment for ML-DSA. The comment to NIST could be as follows:
>>
>> ===>
>>
>> *We propose to in build the following two features into ML-DSA:*
>>
>>
>> *1. Introduction of a flag in the algorithm's interface that gives domain
>> separation between the two uses direct-signing and sign-pre-hashed-message.
>> 2. Introduction of a context string into the algorithm's interface of a
>> length of 0 between 255 octets that allows the protocol or application to
>> define a custom domain separation string.*
>>
>> *This proposal is meant to follow the construction of
>> Ed25519ctx/Ed25519ph in RFC 8032. *
>>
>> *The reason for the first point is the need to avoid any ambiguity with
>> respect to what is the signed message given the alternate options of **direct-signing
>> and sign-pre-hashed-message. When lacking this domain separation feature in
>> ML-DSA, protocols that allow both variants and cannot provide authentic
>> information about the variant during signature verification will be
>> subjected to signature forgery attacks.*
>>
>>
>> *The reason for the second point is that currently there are plans to
>> design composite signature schemes that fulfil non-separability notions,
>> i.e. make it impossible that a signature is stripped from the set of
>> signatures in a composite signature and the remaining signature(s) appear
>> as (a) valid signature(s) of the message. Existing proposals for protocols
>> that cannot provide for authentic information about the nature
>> (composite/standalone) of the signature algorithm during verification can
>> achieve non-separability with a means of domain separation in the signature
>> algorithm. The protocol can thus use the context string to ensure domain
>> separation between composite and standalone use and possibly further
>> aspects such as domain separation between applications. *
>>
>>
>> *<=== *
>>
>> Actually then, at least with Ed25519ctx/Ed25519ph, we can achieve secure
>> non-separable composite signatures with ML-DSA, as both support a context
>> string for domain separation. Whether that will happen in the LAMPS
>> solution I cannot predict, but in any case, it might serve other protocols
>> as well. It seems RFC 8032 has been written with a lot of foresight and is
>> a good template.
>>
>> - Falko
>> Am 21.11.23 um 12:47 schrieb Markku-Juhani O. Saarinen:
>>
>> Hi All,
>>
>> I'd also encourage sending out a public comment, perhaps on behalf of
>> "LAMPS WG". The public comment period on FIPS 205 will actually close
>> November 22, 2023 (Weds.) The date and the e-mail address for comments can
>> be found at https://csrc.nist.gov/pubs/fips/205/ipd
>>
>> I agree that the discussion in Section 9.4 ("Prehash SLH-DSA") seems to
>> leave it to the application whether M is the message itself, or generated
>> via on of the approved functions. There is no built-in domain separation,
>> which is a potential issue. So if someone is sending a public comment, feel
>> free to add my name to it.
>>
>> *Quote: "For some use cases, these issues may be addressed by signing a
>> digest of the message rather than signing the message directly. In order to
>> maintain the same level of security strength, the digest that is signed
>> needs to be generated using an approved hash function or extendable-output
>> function (XOF) (e.g., from FIPS 180-4 [12] or FIPS 202 [10]) that provides
>> at least 8n bits of classical security strength against both collision and
>> second preimage attacks [10, Table 4]."*
>>
>> Hence, an adversary can seemingly just state to the verification function
>> whether a (say) 512-bit blob is a message M itself, or hash from
>> SHAKE256(M1), SHA2-512(M2), or SHA3-512(M3) -- all are authenticated by the
>> same signature. EUF-CMA -- the stated security goal of FIPS signature
>> standards -- is indeed violated if the same signature that was queried for
>> M1/M2/M3 is also a signature for M itself (different message).
>>
>> Apart from existential forgery technicalities, here's a little scenario
>> where this matters: Imagine a remote firmware update that is authenticated
>> with a signature of M = SHA3-512(firmware). An adversary modifies the
>> metadata to state that, oh, here actually M=firmware itself (the update
>> just happens to be only 512 bits long.) Since the metadata is not
>> authenticated, the device replaces its firmware with that garbage. As a
>> result, the device is permanently bricked (perhaps by remote control.)
>>
>> Cheers,
>> -markku
>>
>> Dr. Markku-Juhani O. Saarinen
>> Staff Cryptography Architect
>> PQShield Ltd
>>
>>
>>
>> M:             [phone]
>>
>> E:              [e-mail]
>> W:             www.pqshield.com
>>
>>
>> On Tue, Nov 21, 2023 at 10:43 AM JOHNSON Darren <darren.johnson=
>> [e-mail]> wrote:
>>
>>> THALES GROUP LIMITED DISTRIBUTION to email recipients
>>>
>>>
>>>
>>> Hi,
>>>
>>> Did you pushed this concern to NIST?  They were accepting public
>>> comments on their drafts of ML-DSA up until November 20’th.  I’m sure they
>>> will accept a comment one day late.
>>>
>>>
>>>
>>> Given that they loosely defined pre-hashing in FIPS 204, it sounds like
>>> something that should be addressed by the base signature algorithm,
>>> addressed or justified as not required..
>>>
>>>
>>>
>>> In fact, this should be a base requirement that should be addressed by
>>> any new signature algorithm considered; either addressed, or justified as
>>> not required.
>>>
>>>
>>>
>>> -Darren
>>>
>>>
>>>
>>> *From:* Spasm <[e-mail]> *On Behalf Of * Falko Strenzke
>>> *Sent:* Tuesday, November 21, 2023 4:29 AM
>>> *To:* Seo Suchan <[e-mail]>; LAMPS WG <[e-mail]>
>>> *Subject:* Re: [lamps] [EXTERNAL] pre-hashing the OID in
>>> draft-ounsworth-pq-composite-sigs-10
>>>
>>>
>>>
>>> This is why using raw RSA is insecure and isn't used in any protocol.
>>>
>>> - Falko
>>>
>>> Am 21.11.23 um 10:26 schrieb Seo Suchan:
>>>
>>> not sure we care about existential forgery: RSA have one natively( sign
>>> for product of two message is product of sign of those two message) and
>>>
>>>
>>>
>>> On 2023년 11월 21일 오후 6시 12분 54초 GMT+09:00, Falko Strenzke
>>> <[e-mail]> <[e-mail]> 작성함:
>>>
>>> Hi David,
>>>
>>> Am 21.11.23 um 01:33 schrieb David A. Cooper:
>>>
>>> Hello Falko,
>>>
>>>
>>>
>>> I am unclear about the concern you are raising and the proposed
>>> solution. Is the concern specific to the proposed composite signature
>>> scheme or would it apply whenever a message could be signed using either a
>>> "pure" or "prehash" option?
>>>
>>>
>>>
>>> If I understand correctly, you're concern is that if message M could be
>>> signed as either:
>>>
>>>
>>>
>>>      -- sig = sigalg(K, M); or
>>>
>>>
>>>
>>>      -- sig = sigalg(K, OID || Hash(M)); or
>>>
>>>
>>>
>>> then an attacker could obtain a "pure" signature for "OID || Hash(M)" by
>>> requesting a "prehash" signature for "M," and that this is a concern
>>> regardless of how the "prehash" input to the signing function is
>>> constructed, e.g., "OID || Hash(M)", " 'prehash sig' || OID || Hash(M) ",
>>> etc. Is this correct?
>>>
>>> Yes, it applies whenever there is an ambiguity with respect to what is
>>> signed in the sense that anyone can come up with one or more further
>>> validly signed messages given a validly signed message from the signer.
>>> This is called an existential signature forgery vulnerability (signing M
>>> yields M' ≠ M which can be verified with the same signature (in a different
>>> context)). That this is referred to as an existential signature forgery is
>>> a fact, not my opinion or interpretation. And I think also that a protocol
>>> being vulnerable to such forgeries is considered flawed is common sense.
>>>
>>>
>>>
>>> If so, isn't this already an issue with CMS? Content can be signed using
>>> CMS by either signing the content itself or by signing a set of signed
>>> attributes, one of which is the hash of the content. An attacker could
>>> present some content to the signed using CMS, with the CMS message
>>> containing signedAttrs. The attacker could then construct a new CMS message
>>> with no signed attributes for which the signedAttrs from the original
>>> message was the content.
>>>
>>> Yes, true! I discovered that last week, too, and wrote the attached
>>> paper about it, which I was even planning to make subject to responsible
>>> disclosure to give library maintainers some time to implement the
>>> countermeasures. Now that you are pointing out the vulnerability yourself I
>>> publish it right away. (I hope you believe me and don't assume I wrote it
>>> now after your revelation ;-) Actually I sent it to Russ already yesterday
>>> before your message to hear his opinion.)
>>>
>>> I think this kind of principal weakness is a concern and so far I met no
>>> one who was aware of that problem. And I can well imagine that some vendors
>>> are now going to review or test their systems to preclude that they are
>>> vulnerable – no matter how unlikely a harmful result may be assumed.
>>>
>>>
>>>
>>> This also seems related to general concerns about cross-application
>>> attacks, where an attacker attempts to obtain a signature in one context to
>>> exploit in another context. (For example, if an attacker could obtain a
>>> signature generated for TLS server authentication and somehow use that
>>> signature to perform TLS client authentication, and thus impersonate the
>>> server.)
>>>
>>> Yes, very related. And this should show how serious the concerns about
>>> signature forgery vulnerabilities should be taken. Who had thought that TLS
>>> application layer confusion attacks would be possible until
>>> https://alpaca-attack.com/ ? I don't think it is good idea to design
>>> something with unsound crypto and then wait until a team from Ruhr-Uni
>>> Bochum (it's just a fact, most of the real world vulnerable broken crypto
>>> research comes from there) takes a closer look at real world applications
>>> using the flawed protocol. Efail is of course another perfect example –
>>> until then, no one saw a reason for updating the long known vulnerable CBC
>>> and CFB encryption in S/MIME and OpenPGP.
>>>
>>>
>>>
>>> Could you explain more about how using a different hash function
>>> addresses the problem? Are you envisioning that the signature algorithm
>>> could be used as a black box and one would preform the pre-hashing using a
>>> different hash algorithm or are you suggesting the use of a different hash
>>> algorithm inside the signing algorithm? Unless I am misunderstanding your
>>> concern, it seems that it can not be addressed if the signing algorithm is
>>> treated as a black box.
>>>
>>> I wouldn't really say that I am envisioning one or the other, because I
>>> am not convinced those separability defences are ultimately necessary. But
>>> my initial proposal (when I first mentioned it in a reply to John Gray) was
>>> indeed to treat the signature algorithm as a black box with the implication
>>> that one then is committed to hash-and-sign. That means a composite
>>> signature would be computed as
>>>
>>> S_i = Sign_i(pubKey_i, comp_hash(M))
>>>
>>> where comp_hash(M) = cSHAKE(M,
>>> "pkix-composite-signature-hash-domain-separation-label) *// whatever
>>> order of the arguments to cSHAKE makes sense here, I haven't given that any
>>> attention here*
>>>
>>> Then S_i brought into the standalone scheme context would not be
>>> verifiable, because in the standalone context comp_hash() does not exist
>>> and thus no preimage can be found for the hash.
>>>
>>> Surely, it might be worth exploring what is possible when opening up the
>>> black box of the signature scheme. Then we wouldn't have to commit to
>>> hash-and-sign. But then the traditional algorithm would have to be
>>> redesigned, too, because non-separability would require both algorithms to
>>> be "protected". This topic comes up again under 1. below.
>>>
>>> Two further notes:
>>>
>>> 1. There is also generally a problem if a protocol that doesn't fulfil
>>> what I describe under 2. wants to enable for instance SLH-DSA in two the
>>> variants direct-signing and with pre-hashing. Then again the signature of
>>> the pre-hash scheme would be valid for the message that amounts to the
>>> value of the pre-hash in the direct-signing scheme. This can be solved in
>>> two ways:
>>>
>>>     1a) by a protocol with the features described under 2.
>>>     1b) by ensuring domain separation for the two variants
>>> direct-signing/pre-hash in the signature algorithm like it is done in RFC
>>> 8032 <https://datatracker.ietf.org/doc/html/rfc8032#section-5.1>. This
>>> is what we mean by "opening up the black box". Thus, to facilitate the
>>> support of the variants direct-signing/pre-hash, NIST could consider to
>>> include a domain separation flag like in RFC 8032. (However, this cannot be
>>> so easily used to address the non-separability concerns since for that we
>>> would need to open up the black box of the existing traditional schemes,
>>> which is probably undesired, as mentioned above already.)
>>>
>>> 2. A protocol that *already* feeds the signature algorithm (and ideally,
>>> further context information) in a non-ambiguous way to the message digest
>>> computation as context information doesn't face any of these problems
>>> (neither separability nor direct-signing/pre-hashing), because it can
>>> simply assign different algorithm identifiers in each case and thus
>>> automatically achieves domain separation. This is for instance the case for OpenPGP
>>> signatures
>>> <https://www.ietf.org/archive/id/draft-ietf-openpgp-crypto-refresh-12.html#name-computing-signatures>.
>>> But introducing the context into a protocol that as of yet doesn't feed any
>>> context information would again require some "cut-off" measure like domain
>>> separation through the hash in order to prevent the downgrade and thus
>>> signature forgery.
>>>
>>> - Falko
>>>
>>>
>>>
>>> Thanks,
>>>
>>>
>>>
>>> David
>>>
>>>
>>>
>>> On 11/19/23 9:53 PM, Falko Strenzke wrote:
>>>
>>> The point I was making is that for instance with a feasible
>>> computational effort of 2⁶³ hash evaluations on average, the attacker can
>>> control 8 bytes in the digest, if he can control a large enough portion of
>>> the signed message and predict the whole message.
>>>
>>> Anyway, this is an irrelevant and misleading discussion, a signature
>>> forgery is a signature forgery and the protocol is broken.
>>>
>>> - Falko
>>>
>>> Am 19.11.23 um 01:04 schrieb Scott Fluhrer (sfluhrer):
>>>
>>> (Falko argued that it could be under total control if the attacker had
>>> sufficient computational power; however if the attacker had sufficient
>>> computational power, he could just break the public keys).
>>>
>>> --
>>>
>>> *MTG AG*
>>> Dr. Falko Strenzke
>>> Executive System Architect
>>>
>>> --
>>>
>>> *MTG AG*
>>> Dr. Falko Strenzke
>>> Executive System Architect
>>>
>>> Phone: [phone]
>>> E-Mail: [e-mail]
>>> Web: mtg.de <https://www.mtg.de>
>>>
>>>
>>> <https://www.linkedin.com/search/results/all/?fetchDeterministicClustersOnly=true&heroEntityKey=urn%3Ali%3Aorganization%3A13983133&keywords=mtg%20ag&origin=RICH_QUERY_SUGGESTION&position=0&searchId=d5bc71c3-97f7-4cae-83e7-e9e16d497dc2&sid=3S5&spellCorrectionEnabled=false>
>>> Follow us
>>> ------------------------------
>>>
>>>
>>> <https://www.mtg.de/de/aktuelles/MTG-AG-erhaelt-Innovationspreis-des-Bundesverbands-IT-Sicherheit-e.V-00001.-TeleTrust/>
>>> <https://www.itsa365.de/de-de/companies/m/mtg-ag>
>>>
>>> MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
>>> Commercial register: HRB 8901
>>> Register Court: Amtsgericht Darmstadt
>>> Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
>>> Chairman of the Supervisory Board: Dr. Thomas Milde
>>>
>>> This email may contain confidential and/or privileged information. If
>>> you are not the correct recipient or have received this email in error,
>>> please inform the sender immediately and delete this email.Unauthorised
>>> copying or distribution of this email is not permitted.
>>>
>>> Data protection information: Privacy policy
>>> <https://www.mtg.de/en/privacy-policy>
>>> _______________________________________________
>>> Spasm mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/spasm
>>>
>> --
>>
>> *MTG AG*
>> Dr. Falko Strenzke
>> Executive System Architect
>>
>> Phone: [phone]
>> E-Mail: [e-mail]
>> Web: mtg.de <https://www.mtg.de>
>>
>> <https://www.linkedin.com/search/results/all/?fetchDeterministicClustersOnly=true&heroEntityKey=urn%3Ali%3Aorganization%3A13983133&keywords=mtg%20ag&origin=RICH_QUERY_SUGGESTION&position=0&searchId=d5bc71c3-97f7-4cae-83e7-e9e16d497dc2&sid=3S5&spellCorrectionEnabled=false>
>> Follow us
>> ------------------------------
>>
>> <https://www.mtg.de/de/aktuelles/MTG-AG-erhaelt-Innovationspreis-des-Bundesverbands-IT-Sicherheit-e.V-00001.-TeleTrust/>
>> <https://www.itsa365.de/de-de/companies/m/mtg-ag>
>>
>> MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
>> Commercial register: HRB 8901
>> Register Court: Amtsgericht Darmstadt
>> Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
>> Chairman of the Supervisory Board: Dr. Thomas Milde
>>
>> This email may contain confidential and/or privileged information. If you
>> are not the correct recipient or have received this email in error,
>> please inform the sender immediately and delete this email.Unauthorised
>> copying or distribution of this email is not permitted.
>>
>> Data protection information: Privacy policy
>> <https://www.mtg.de/en/privacy-policy>
>>
> --
>
> *MTG AG*
> Dr. Falko Strenzke
> Executive System Architect
>
> Phone: [phone]
> E-Mail: [e-mail]
> Web: mtg.de <https://www.mtg.de>
>
> <https://www.linkedin.com/search/results/all/?fetchDeterministicClustersOnly=true&heroEntityKey=urn%3Ali%3Aorganization%3A13983133&keywords=mtg%20ag&origin=RICH_QUERY_SUGGESTION&position=0&searchId=d5bc71c3-97f7-4cae-83e7-e9e16d497dc2&sid=3S5&spellCorrectionEnabled=false>
> Follow us
> ------------------------------
>
> <https://www.mtg.de/de/aktuelles/MTG-AG-erhaelt-Innovationspreis-des-Bundesverbands-IT-Sicherheit-e.V-00001.-TeleTrust/>
> <https://www.itsa365.de/de-de/companies/m/mtg-ag>
>
> MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
> Commercial register: HRB 8901
> Register Court: Amtsgericht Darmstadt
> Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
> Chairman of the Supervisory Board: Dr. Thomas Milde
>
> This email may contain confidential and/or privileged information. If you
> are not the correct recipient or have received this email in error,
> please inform the sender immediately and delete this email.Unauthorised
> copying or distribution of this email is not permitted.
>
> Data protection information: Privacy policy
> <https://www.mtg.de/en/privacy-policy>
>