Subject: RSA Signature Padding

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 3 Jun 2009 12:58:45 -0400

I do not know if this is the right forum.

Should we encourage vendors to use RSA PSS as we transition to SHA-256
given the weakness in PKCS 1.5 padding?

Santosh Chokhani
CygnaCom Solutions

"Questioning conventional wisdom is key to innovation"

---

From: Tom Gindin <[email-masked]>
Date: Sun, 7 Jun 2009 20:54:27 -0400

Is "we" the right term?  The latest TLS (RFC 5246 section 4.7) 
specifies RSA signatures but does not seem to permit PSS ones.  PKIX at 
least has PSS in RFC 4055.  We could encourage vendors by producing a 
consolidated "algorithms" RFC which deprecates the use of MD2 and MD5 for 
new certificates, while suggesting that any RP vendor supporting 
sha1WithRSAEncryption as a signatureAlgorithm SHOULD also support 
id-RSASSA-PSS.  Are you suggesting that we should also tell people not to 
use sha256WithRSAEncryption, sha384WithRSAEncryption, or 
sha512WithRSAEncryption as signatureAlgorithm values but to use those hash 
algorithms as PSS parameters instead?
        Should such an RFC be targeted for New Year's 2011?

                Tom Gindin

"Santosh Chokhani" <[email-masked]> 
Sent by: [email-masked]
06/03/2009 12:58 PM

To
"IETF-pkix" <[email-masked]>
cc

Subject
RSA Signature Padding

Santosh Chokhani
CygnaCom Solutions

---

From: "Santosh Chokhani" <[email-masked]>
Date: Mon, 8 Jun 2009 06:43:11 -0400

Tom,

I am asking because of the paper in the link below.

http://eprint.iacr.org/2009/203 

> -----Original Message-----
> From: Tom Gindin [mailto:[email-masked]] 
> Sent: Sunday, June 07, 2009 8:54 PM
> To: Santosh Chokhani
> Cc: IETF-pkix
> Subject: Re: RSA Signature Padding
> 
>         Is "we" the right term?  The latest TLS (RFC 5246 
> section 4.7) specifies RSA signatures but does not seem to 
> permit PSS ones.  PKIX at least has PSS in RFC 4055.  We 
> could encourage vendors by producing a consolidated 
> "algorithms" RFC which deprecates the use of MD2 and MD5 for 
> new certificates, while suggesting that any RP vendor 
> supporting sha1WithRSAEncryption as a signatureAlgorithm 
> SHOULD also support id-RSASSA-PSS.  Are you suggesting that 
> we should also tell people not to use 
> sha256WithRSAEncryption, sha384WithRSAEncryption, or 
> sha512WithRSAEncryption as signatureAlgorithm values but to 
> use those hash algorithms as PSS parameters instead?
> "Santosh Chokhani" <[email-masked]> Sent by: 
> [email-masked]
> 06/03/2009 12:58 PM
> 
> To
> Should we encourage vendors to use RSA PSS as we transition 
> to SHA-256 given the weakness in PKCS 1.5 padding?
> 
> Santosh Chokhani
> CygnaCom Solutions
>

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 08 Jun 2009 13:28:03 +0200

> http://eprint.iacr.org/2009/203 

Interesting.  What does that mean for PKCS#1 v1.5?

/Simon

---

From: "Santosh Chokhani" <[email-masked]>
Date: Mon, 8 Jun 2009 09:21:58 -0400

The thesis of the paper is that ad hoc encodings should be replaced with
Provably secure encodings, albeit the attack it describes may not apply
to PKCS 1 1.5.

One would think that we would want to use provable secure padding
specially as we use new OID.

> From: Simon Josefsson [mailto:[email-masked]] 
> Sent: Monday, June 08, 2009 7:28 AM
> To: Santosh Chokhani
> Cc: Tom Gindin; IETF-pkix
> >>         Is "we" the right term?  The latest TLS (RFC 5246 section 
> >> 4.7) specifies RSA signatures but does not seem to permit 
> PSS ones.  
> >> PKIX at least has PSS in RFC 4055.  We could encourage vendors by 
> >> producing a consolidated "algorithms" RFC which deprecates 
> the use of 
> >> MD2 and MD5 for new certificates, while suggesting that 
> any RP vendor 
> SHOULD also 
> >> support id-RSASSA-PSS.  Are you suggesting that we should 
> also tell 
> >> people not to use sha256WithRSAEncryption, 
> sha384WithRSAEncryption, 
> >> or sha512WithRSAEncryption as signatureAlgorithm values but to use 
> >> those hash algorithms as PSS parameters instead?
> >> Should we encourage vendors to use RSA PSS as we transition to 
> >> SHA-256 given the weakness in PKCS 1.5 padding?
> >> 
> >> Santosh Chokhani
> >> CygnaCom Solutions
> >>

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 11 Jun 2009 22:32:55 +1200

"Santosh Chokhani" <[email-masked]> writes:

>Should we encourage vendors to use RSA PSS as we transition to SHA-256 given
>the weakness in PKCS 1.5 padding?

[Click]

[Revind about five years to the thread discussing "Should we encourage vendors
 to use RSA OEAP as we transition to AES given the weakness in PKCS 1.5
 padding"]

[Play]

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 11 Jun 2009 22:36:45 +1200

>Interesting.  What does that mean for PKCS#1 v1.5?

Nothing whatsoever.

Rob Stradling <[email-masked]> writes:

>Should implementors wait until support for RSA-PSS is sufficiently widespread
>for their needs before migrating from PKCS#1.5/SHA-1 to PKCS#2.1/SHA-2?

Yes.  I'd recommend waiting until January 2038, on the basis that (a) there
may be support for it in implementations by then and (b) people will be so
busy fixing another problem that'll crop up around then that they won't notice
this particular change.

Peter.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 11 Jun 2009 17:23:49 -0400

Peter,

You may be right about the implementers.

There is benefit to PSS over 1.5.  The paper points that out.  

> From: pgut001 [mailto:[email-masked]] 
> Sent: Thursday, June 11, 2009 6:37 AM
> To: Santosh Chokhani; [email-masked]
> Cc: [email-masked]; [email-masked]
> >Should implementors wait until support for RSA-PSS is sufficiently 
> >widespread for their needs before migrating from 
> PKCS#1.5/SHA-1 to PKCS#2.1/SHA-2?
> 
> Yes.  I'd recommend waiting until January 2038, on the basis 
> that (a) there may be support for it in implementations by 
> then and (b) people will be so busy fixing another problem 
> that'll crop up around then that they won't notice this 
> particular change.
> 
> Peter.
>

---

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 11 Jun 2009 17:20:37 -0400

Any how did that go?

I suspect fell on deaf ears? 

> Sent: Thursday, June 11, 2009 6:33 AM
> To: [email-masked]; Santosh Chokhani
> [Revind about five years to the thread discussing "Should we 
> encourage vendors  to use RSA OEAP as we transition to AES 
> given the weakness in PKCS 1.5  padding"]
> 
> [Play]
> 
> Peter.
>

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 12 Jun 2009 14:57:50 +1200

>I suspect fell on deaf ears?

Well, if you mean "after careful analysis the conclusion was that it was, at
best, going to be a pointless gesture", then I guess, yes.  My summary was:

-- Snip --

No matter how cool/interesting/useful/mandated in standards a new design is,
it won't be used if it requires redeployment of all existing hardware and
software for little apparent gain.  Two illustrative examples of this are
X9.42 DH and OAEP with AES.

An Internet standard RFC required that implementors support X9.42 DH key
agreement, and provided RSA as an option (in IETF terms, "MUST X9.42, MAY
RSA").  However, no existing software supported X9.42, no CAs would issue
certificates for it, even if they did no-one wanted to renew all of their
certificates ($$$) for an algorithm that provided no advantages over RSA, and
no hardware (either crypto accelerators or smart cards) supported it (there
was some token support after a few years, although even now there are problems
being found with the X9.42 test vectors which indicate that no-one has really
looked at them).  As a result, even though the standard mandated use of X9.42,
everyone treated it as if it said "MUST RSA, SHOULD NOT X9.42", pretending to
do X9.42 while running business as usual with RSA.

OAEP is in a similar situation.  In order to get it usefully deployed, it
would be necessary to issue certificates that would only work with OAEP
otherwise everyone would just keep using them with PKCS #1 v1.5.  This would
have exactly the same effect as X9.42.

An attempt was made to force OAEP through by tying it to AES.  In other words,
in order to use AES you also had to use OAEP.  Apart from the list of issues
already mentioned with X9.42 above, this was also going to be deployed in an
area where it was necessary to use crypto hardware for performance reasons
(this area is almost always glossed over in crypto designs).  Most crypto
hardware does RSA in hardware and either leaves the symmetric crypto for
software to do (cheaper hardware) or leaves further key management to software
and provides hardware acceleration for bulk data encryption once all further
key processing has been performed (more expensive hardware).  In addition a
few rather specialised crypto engines do everything in hardware.

In all cases except the most primitive accelerators that consist of nothing
but a bignum engine, moving to OAEP would require replacing the crypto
hardware.  Crypto hardware boxes typically cost $10,000-$20,000 each, assuming
you can find one that supports OAEP.  A server farm needs a great many of
these $20,000 boxes.  Smaller devices like smart cards may only cost $10-$20
each, but then you've got 100,000 of them to replace.  Some devices can upload
new firmware, but will zeroise their keys when this occurs for security
reasons, requiring a complete redeployment from scratch of all keys and
certificates ($$$).

As a result, a vendor would have two options: Supply a non-compliant solution
that uses AES with PKCS #1 v1.5, or supply a compliant solution that uses AES
with OAEP and requires rebuilding the entire infrastructure (hardware,
software, and certificates) from the ground up.

The standards group abandoned the idea of tying OAEP to AES ("It's X9.42 all
over again").

-- Snip --

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 14 Jun 2009 00:10:22 +1200

>There is benefit to PSS over 1.5.  The paper points that out.

There is a purely theoretical benefit, but weighed against the *massive*
practical downside of going to PSS I doubt it'll carry much weight...

Peter.

---

From: Stefan Santesson <[email-masked]>
Date: Sat, 13 Jun 2009 14:42:38 +0200

The way I read this is that 1.5 is handcrafted to mitigate known attacks
while PSS use a more generic and provable secure approach. But neither of
them are broken.

Would that be a correct assessment?

/Stefan

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 14 Jun 2009 01:16:45 +1200

>Would that be a correct assessment?

Yes.  So 1.5 makes some cryptographers uneasy because it's not as rigorous as
PSS, but (barring buggy implementations, which affects PSS as much as 1.5)
there's currently no known attack against it that makes 1.5 worse than PSS.
9796-2, on the other hand, is a long series of patches to fix up weaknesses,
and there's no sign it's getting much better over time.

Peter.