Subject: [TLS] TLS 1.3: Deterministic RSA-PSS and ECDSA

From: Brian Smith <[email-masked]>
Date: Sat, 6 Aug 2016 18:54:56 -1000

The current draft says "It is RECOMMENDED that implementations
implement 'deterministic ECDSA' as specified in [RFC6979]." The
current draft also says, regarding RSA-PSS signatures: "When used in
signed TLS handshake messages, the length of the salt MUST be equal to
the length of the digest output."

I think it would be ideal if we could find a way to specify the
RSA-PSS salt requirement in a way that meets the requirements for
provable security that motivated the switch to RSA-PSS and also
recommends a deterministic method of salt generation analogous to what
RFC6979 does for ECDSA. However, I don't know of any such method.
Perhaps other people do; if so, the spec to include a recommendation
to use such a method be used.

Also, I think it would be great if people working on proofs of
security for TLS could take into consideration the fact that
some--perhaps many--implementations will intentionally or accidentally
use some form of deterministic or less-than-random salt generation for
RSA-PSS. For example, it would be great to see a "What if the salt(s)
in the RSA PSS signature(s) were generated deterministically?" section
of papers describing such proofs.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Hanno Böck <[email-masked]>
Date: Sat, 6 Aug 2016 23:57:16 -0700

Hi,

On Sat, 6 Aug 2016 18:54:56 -1000

> of papers describing such proofs.

Actually there is some info on that in the PSS spec [1]. What I write
here is my limited understanding, but roughly I'd interpret it as this:
It says that if you use a non-random salt the security gets reduced to
the security of full domain hashing, which was kinda the predecessor of
PSS.
I'd conclude from that that even in a situation where the salt
generation is a non-random value nothing really bad happens. The
security of a PSS scheme without randomness is still better than that
of a PKCS #1 1.5 signature.

Maybe some more knowledgable people want to add something, but the
bottom line is I think that we don't need to worry too much about the
randomness part here. Unlike with other situations (e.g. ecdsa/dsa) the
randomness is not a piece that once you take it away everything blows
up.

[1] https://tools.ietf.org/html/rfc3447

-- 
Hanno Böck
https://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

From: Rene Struik <[email-masked]>
Date: Sun, 7 Aug 2016 11:41:40 -0400

Hi Hanno:

The papers [1] and [2] may be of interest here. In [2], Section 3.3, 
Alfred Menezes and Neil Koblitz compare FDH-hash RSA signatures, PSS 
(lots of randomness in the salt), and a scheme by Wang and Katz that 
only contains one bit of randomness with signing and is claimed to have 
tight reductions (see also [1]) and argue a "Pass on PSS".

[1] Signature Schemes - Efficient, with Tight Security Reductions 
(Jonathan Katz, Nan Wang, CCCS 2003). Available from 
https://www.cs.umd.edu/~jkatz/papers/CCCS03_sigs.pdf
[2] Provable Security, Another Look at (Alfred Menezes, Neal Koblitz, 
IACR ePrint 2004-152). Available from https://eprint.iacr.org/2004/152

On 8/7/2016 2:57 AM, Hanno Böck wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Brian Smith <[email-masked]>
Date: Sun, 7 Aug 2016 12:44:32 -1000

Rene Struik <[email-masked]> wrote:
> The papers [1] and [2] may be of interest here. In [2], Section 3.3, Alfred
> Menezes and Neil Koblitz compare FDH-hash RSA signatures, PSS (lots of
> randomness in the salt), and a scheme by Wang and Katz that only contains
> one bit of randomness with signing and is claimed to have tight reductions
> (see also [1]) and argue a "Pass on PSS".
>
> [1] Signature Schemes - Efficient, with Tight Security Reductions (Jonathan
> Katz, Nan Wang, CCCS 2003). Available from
> [2] Provable Security, Another Look at (Alfred Menezes, Neal Koblitz, IACR
> ePrint 2004-152). Available from https://eprint.iacr.org/2004/152

Right, these are the papers I read that made me start to think it
might actually be dumb to randomize the salt when generating a PSS
signature. It seems like the randomization is purely needed purely as
an artifact of the method used in the security reduction, and seems
unlikely to actually improve security. In fact, it would hurt security
because it adds significant complexity to PSS signature generation and
provides a means to efficiently smuggle secrets out of the security
module containing the RSA private key. Thus, an implementer of RSA-PSS
signature generation who wants to maximize security likely won't want
to randomize the salt.

Another interesting paper is [3], which says "However, since PSS (with
random salt of arbitrary length) is at least as secure as FDH, we
obtain as a corollary from Section 3 a tight security proof from
lossiness to the security of PSS, with random salt of arbitrary
(possibly zero) length."

At the time I suggested [4] that the salt length be fixed to the
length of the digest function for RSA PSS signatures in TLS, I wasn't
aware of all the research that had been done. Unfortunately, my
under-informed suggestion is what is currently prescribed in the
current draft. I'd like to make sure that whatever the spec ultimately
prescribes is actually motivated by a current scientific argument,
even if it means I have to admit I was wrong.

[3] Optimal Security Proofs for Full Domain Hash, Revisited (Saqib A.
Kakvi and Eike Kiltz). Available from
https://www.iacr.org/archive/eurocrypt2012/72370533/72370533.pdf.
[4] https://www.ietf.org/mail-archive/web/tls/current/msg15601.html

Cheers,
Brian
--
https://briansmith.org/

---

From: [email-masked] (Martin Rex)
Date: Mon, 8 Aug 2016 14:55:14 +0200 (CEST)

> of a PKCS #1 1.5 signature.

The urban myth about the advantages of the RSA-PSS signature scheme
over PKCS#1 v1.5 keep coming up.

It has been mentioned here before:

Fedor Brunner wrote on 4 Mar 2016 17:45:19:
> 
> Please see the paper "Another Look at ``Provable Security''" from Neal
> Koblitz and Alfred Menezes.
> 
> https://eprint.iacr.org/2004/152
> 
> Section 7: Conclusion
> 
> "There is no need for the PSS or Katz-Wang versions of RSA;
> one might as well use just the basic ?hash and exponentiate? signature
> scheme (with a full-domain hash function)."

The advantages of the RSA-PSS signature scheme are limited to situations
where the rightful owner of the private signing key is not supposed
to have access to the bits of the private key (i.e. key kept in hardware).

-Martin

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Mon, 08 Aug 2016 16:41:36 +0200

> to have access to the bits of the private key (i.e. key kept in

Is that limited, so limited today? Aren't we at a time where the
majority of servers will use an HSM (either real hardware or
virtualized)?

regards,
Nikos

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 8 Aug 2016 14:53:09 +0000

> Is that limited, so limited today? Aren't we at a time where the majority of
> servers will use an HSM (either real hardware or virtualized)?

Without even defining "virtualized HSM" the answer is no.

---

From: Brian Smith <[email-masked]>
Date: Mon, 8 Aug 2016 09:54:30 -1000

> over PKCS#1 v1.5 keep coming up.

PKCS#1 v1.5 is a partial-domain scheme, not a full-domain scheme. So,
RSA-PSS (without a salt, or with a fixed salt) might still have an
advantage over PKCS#1 v1.5 because it is a full-domain scheme.

> to have access to the bits of the private key (i.e. key kept in hardware).

RSA-PSS is the only (IETF) (proposed) standard for full-domain hashing
we have for RSA, AFAIK. This is why I think it might still make sense
to use it, in a deterministic fashion.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 8 Aug 2016 13:21:13 -0700

> over PKCS#1 v1.5 keep coming up.

Do you think we'll see real-world MitM attacks against RSA-PSS in TLS
similar to those we've seen with PKCS#1v1.5 signature forgery, such as
BERserk?

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 9 Aug 2016 08:55:30 +0000

Tony Arcieri <[email-masked]> writes:

>Do you think we'll see real-world MitM attacks against RSA-PSS in TLS similar
>to those we've seen with PKCS#1v1.5 signature forgery, such as BERserk?

Not BERserk specifically because that was an attack on the ASN.1, not the
signature format.  OTOH PSS doesn't encode the hash algorithm as 1.5 does, so
here's a much simpler attack: Take a breakable hash function with an output
the same size as the one used in the sig, generate your collision, and paste
the sig onto colliding data, indicating the use of the breakable function not
the one used to generate the original sig.  Done.  Couldn't happen with 1.5
because that encodes the details of the hash function used as part of the
signature.

Peter.

---

From: [email-masked] (Martin Rex)
Date: Tue, 9 Aug 2016 16:16:15 +0200 (CEST)

Tony Arcieri wrote:
[ Charset UTF-8 unsupported, converting... ]
> similar to those we've seen with PKCS#1v1.5 signature forgery, such as

BERserk is an implementation defect, not a crypto weakness.

-Martin

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 9 Aug 2016 14:13:25 -0700

> BERserk is an implementation defect, not a crypto weakness.

Hence why I phrased the question the way I did. Per Izu, Shimoyama, and
Takenaka 2006, PKCS#1 v1.5 has sharp edges which implementers must avoid
(of course, the same can be said of BER in BERserk, and it was clearly the
bigger of the two problems).

Peter Gutmann's response was the sort of thing I was looking for when I
originally asked the question.

-- 
Tony Arcieri

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 9 Aug 2016 16:10:28 -0700

It's also worth noting that BERserk is one of many such incidents of this
coming up in practice:
https://cryptosense.com/why-pkcs1v1-5-signature-should-also-be-put-out-of-our-misery/

-- 
Tony Arcieri

---

From: [email-masked] (Martin Rex)
Date: Wed, 10 Aug 2016 19:57:06 +0200 (CEST)

> https://cryptosense.com/why-pkcs1v1-5-signature-should-also-be-put-out-of-our-misery/

With the PKCS#1 v1.5 signature verification operation,
as described in PKCS#1 v2.0 (rfc2437, Oct-1998, Section 8.1.2)

https://tools.ietf.org/html/rfc2437#section-8.1.2

it is *IMPOSSIBLE* to create an implementation with a bug such
as BERserk, because there is (on purpose) *NO* ASN.1 decoding step
defined for this signature verification.

A useful specification that is almost 2 decades old does not
protect from clueless implementors, however.

Heartbleed is also not part of the underlying specification.
Anyhow some very seriously broken code, for a completely useless
feature (within TLS, not DTLS), was created and shipped into
large parts of the installed base...

-Martin