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

[Martin Rex]

Tony Arcieri wrote:
>
> 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/

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

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Tony Arcieri]

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/

On Tue, Aug 9, 2016 at 2:13 PM, Tony Arcieri  wrote:

> On Tue, Aug 9, 2016 at 7:16 AM, Martin Rex  wrote:
>
>> 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
>



-- 
Tony Arcieri
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Tony Arcieri]

On Tue, Aug 9, 2016 at 7:16 AM, Martin Rex  wrote:

> 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
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Martin Rex]

Tony Arcieri wrote:
[ Charset UTF-8 unsupported, converting... ]
> On Monday, August 8, 2016, Martin Rex  wrote:
> >
> > The urban myth about the advantages of the RSA-PSS signature scheme
> > 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?

BERserk is an implementation defect, not a crypto weakness.

-Martin

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Tony Arcieri]

On Monday, August 8, 2016, Martin Rex  wrote:
>
> The urban myth about the advantages of the RSA-PSS signature scheme
> 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?
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Brian Smith]

Martin Rex  wrote:
> The urban myth about the advantages of the RSA-PSS signature scheme
> 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.

> 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).

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/

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Salz, Rich]

 
> 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.

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Nikos Mavrogiannopoulos]

On Mon, 2016-08-08 at 14:55 +0200, Martin Rex wrote:

> > 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).

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

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Martin Rex]

Hanno Böck wrote:
> 
> 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.

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

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Brian Smith]

Rene Struik  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
> 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

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/

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Rene Struik]

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:

Hi,

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


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.

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



___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls



--
email: rstruik@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Hanno Böck]

Hi,

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

> 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.

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: ha...@hboeck.de
GPG: BBB51E42


pgpOIJowXJU0B.pgp
Description: OpenPGP digital signature
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls