Subject: [saag] pkcs#1 -> IETF change control

From: Stephen Farrell <[email-masked]>
Date: Fri, 5 Aug 2016 18:07:21 +0100

Folks,

I've just asked to start IETF last call for drafts that
document pkcs#5 [1] and pkcs#1. [2] The main purpose
of these drafts is to hand change control to the IETF,
as we've recently done with other pkcs series documents.
(That's a good thing, and thanks to those who've made
the not-inconsiderable effort to make it happen.)

For pkcs#5 I think there are only nits to consider but
I do have a question to ask wrt the pkcs#1 draft. [2]

Please send responses here or in response to the last
call on [email-masked], which should pop out shortly.

If you look at the diff [3] between this draft and RFC
2437, there are substantial differences, including to
some data structures, the older versions of which may be
in widespread use, e.g., RSAPrivateKey is extended in a
way that I think could lead to interop issues in [2].

So my question is: what's the right way to handle getting
pkcs#1 under IETF change control without breaking anything?

Should we for example, not formally OBSOLETE RFC2347 perhaps,
or should we ask to add some statement to [2] that explains
that even though this is newer, it's the older version that's
widely implemented.

Bear in mind that we are in any case trying to move entirely
away from pkcs#1v1.5 so this shouldn't be too much of an issue
for future RFCs, which are likely to just use pkcs#1v.5 as-is
(if that's needed due to legacy h/w) or to use something else
entirely, e.g. based on the cfrg curves.

So, that's a bit long winded, but please take a look, in
particular at [2] and [3] and say what you think we should
be doing here.

Thanks,
S.

PS: Please note that it's taken the folks doing this
work quite a bit of effort, e.g. dealing with their
legal folks to get permission to move change control to
the IETF, so we should really try to avoid imposing
more work (and delay) on those folks if we can. IOW,
minimal change here is really good, and if the IETF
wants to and has the energy, we can modify whatever we
like after this transition has happened.

[1] https://datatracker.ietf.org/doc/draft-moriarty-pkcs5-v2dot1/
[2] https://datatracker.ietf.org/doc/draft-moriarty-pkcs1/
[3]
https://tools.ietf.org/rfcdiff?url1=rfc2437&url2=draft-moriarty-pkcs1-01.txt

---

From: Russ Housley <[email-masked]>
Date: Fri, 5 Aug 2016 13:58:04 -0400

PKCS#1 v2.2 supports multi-prime RSA, where the modulus may have more than two prime factors. Multi-prime RSA can provide lower computational cost for the decryption and signature primitives when the CRT (Chinese Remainder Theorem) is used. Further, one can get better performance in a multiprocessor environment where the modular exponentiations can be done in parallel.

The big changes in the PKCS#1 v2.2 data structures are to support multi-prime RSA.  I believe that the changes were done in a way that is backward compatible with the non-multi-prime RSA.

Russ

On Aug 5, 2016, at 1:07 PM, Stephen Farrell <[email-masked]> wrote:

> [3] https://tools.ietf.org/rfcdiff?url1=rfc2437&url2=draft-moriarty-pkcs1-01.txt

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 5 Aug 2016 19:21:19 +0100

On 05/08/16 18:58, Russ Housley wrote:
> PKCS#1 v2.2 supports multi-prime RSA, where the modulus may have more
> than two prime factors. Multi-prime RSA can provide lower
> computational cost for the decryption and signature primitives when
> the CRT (Chinese Remainder Theorem) is used. Further, one can get
> better performance in a multiprocessor environment where the modular
> exponentiations can be done in parallel.
> 
> The big changes in the PKCS#1 v2.2 data structures are to support
> multi-prime RSA.  I believe that the changes were done in a way that
> is backward compatible with the non-multi-prime RSA.
> 

I agree with the above, except I think for the changes to RSAPrivateKey
(at least that's the one I noted). Now that's not a huge deal for
interop, but would bite for private key import/export, I don't think
old code could ever usefully accept the multi-prime structure, so I
think it is an issue there at least. So if we OBSOLETE 2347 then new
code is likely to be less interoperable with current code.

I think maybe best might be to just not OBSOLETE 2347 for now and then
if/when multi-prime is desired (for pkcs#1) we can figure that out then.

Cheers,
S.

>> I've just asked to start IETF last call for drafts that document
>> pkcs#5 [1] and pkcs#1. [2] The main purpose of these drafts is to
>> hand change control to the IETF, as we've recently done with other
>> pkcs series documents. (That's a good thing, and thanks to those
>> who've made the not-inconsiderable effort to make it happen.)
>> 
>> For pkcs#5 I think there are only nits to consider but I do have a
>> question to ask wrt the pkcs#1 draft. [2]
>> 
>> Please send responses here or in response to the last call on
>> [email-masked], which should pop out shortly.
>> 
>> If you look at the diff [3] between this draft and RFC 2437, there
>> are substantial differences, including to some data structures, the
>> older versions of which may be in widespread use, e.g.,
>> RSAPrivateKey is extended in a way that I think could lead to
>> interop issues in [2].
>> 
>> So my question is: what's the right way to handle getting pkcs#1
>> under IETF change control without breaking anything?
>> 
>> Should we for example, not formally OBSOLETE RFC2347 perhaps, or
>> should we ask to add some statement to [2] that explains that even
>> though this is newer, it's the older version that's widely
>> implemented.
>> 
>> Bear in mind that we are in any case trying to move entirely away
>> from pkcs#1v1.5 so this shouldn't be too much of an issue for
>> future RFCs, which are likely to just use pkcs#1v.5 as-is (if
>> that's needed due to legacy h/w) or to use something else entirely,
>> e.g. based on the cfrg curves.
>> 
>> So, that's a bit long winded, but please take a look, in particular
>> at [2] and [3] and say what you think we should be doing here.
>> 
>> Thanks, S.
>> 
>> PS: Please note that it's taken the folks doing this work quite a
>> bit of effort, e.g. dealing with their legal folks to get
>> permission to move change control to the IETF, so we should really
>> try to avoid imposing more work (and delay) on those folks if we
>> can. IOW, minimal change here is really good, and if the IETF wants
>> to and has the energy, we can modify whatever we like after this
>> transition has happened.
>> 
>> [2] https://datatracker.ietf.org/doc/draft-moriarty-pkcs1/ [3]

---

From: Russ Housley <[email-masked]>
Date: Sat, 6 Aug 2016 10:18:29 -0400

> if/when multi-prime is desired (for pkcs#1) we can figure that out then.

The RSAPrivateKey structure is:

         RSAPrivateKey ::= SEQUENCE {
             version           Version,
             modulus           INTEGER,  -- n
             publicExponent    INTEGER,  -- e
             privateExponent   INTEGER,  -- d
             prime1            INTEGER,  -- p
             prime2            INTEGER,  -- q
             exponent1         INTEGER,  -- d mod (p-1)
             exponent2         INTEGER,  -- d mod (q-1)
             coefficient       INTEGER,  -- (inverse of q) mod p
             otherPrimeInfos   OtherPrimeInfos OPTIONAL
         }

If multi-prime RSA is used, then the OPTIONAL otherPrimeInfos is present.

If multi-prime RSA is not used, then the OPTIONAL otherPrimeInfos is absent.

In this way, a private key with two primes can be used by older software that does not support multi-prime RSA.  The text on version warns about this; version must be 1 if otherPrimeInfos present.  

Russ

---

From: Jim Schaad <[email-masked]>
Date: Sat, 6 Aug 2016 09:02:06 -0700

> -----Original Message-----
> From: saag [mailto:[email-masked]] On Behalf Of Stephen Farrell
> Sent: Friday, August 05, 2016 11:21 AM
> To: Russ Housley <[email-masked]>
> Cc: IETF SAAG <[email-masked]>
> Subject: Re: [saag] pkcs#1 -> IETF change control
> 
> 
> 
> I agree with the above, except I think for the changes to RSAPrivateKey (at least
> that's the one I noted). Now that's not a huge deal for interop, but would bite
> for private key import/export, I don't think old code could ever usefully accept
> the multi-prime structure, so I think it is an issue there at least. So if we
> OBSOLETE 2347 then new code is likely to be less interoperable with current
> code.
> 

I am not sure that I am following your logic.

If the old code only supports using two primes, then it will import the new structure just fine if the new structure only has two primes.

If the old code only supports using two primes, then it will fail to import the new structure if it has three primes.  However, even if the code is fixed to allow for having three primes in the parsed structure it would fail to import the key because it does not support having three primes in the code.

I don't think that I am worried that old code would fail when trying to import a three prime RSA private key beause it is going to fail either doing the ASN.1 parsing of the RSAPrivateKey structure or it is going to reject it because it does not support doing multiprime RSA.  Either way it has to fail.

If we obsolete 2347, then new code will correctly parse the multiprime structure.  But it will possibly still reject the private key because it does not support multiprime RSA.  I don't know how many places implement multiprime RSA today.  And many of those places are probably moving towards ECDSA or EdDSA anyway.  

I would say go ahead and obsolete 2347.

Jim
> >> older versions of which may be in widespread use, e.g., RSAPrivateKey
> >> is extended in a way that I think could lead to interop issues in
> >> [2].
> >>
> >> from pkcs#1v1.5 so this shouldn't be too much of an issue for future
> >> RFCs, which are likely to just use pkcs#1v.5 as-is (if that's needed
> >> due to legacy h/w) or to use something else entirely, e.g. based on
> >> the cfrg curves.
> >>
> >> PS: Please note that it's taken the folks doing this work quite a bit
> >> of effort, e.g. dealing with their legal folks to get permission to
> >> move change control to the IETF, so we should really try to avoid
> >> imposing more work (and delay) on those folks if we can. IOW, minimal
> >> change here is really good, and if the IETF wants to and has the
> >> energy, we can modify whatever we like after this transition has
> >> happened.
> >>

---

From: Watson Ladd <[email-masked]>
Date: Sat, 6 Aug 2016 09:38:46 -0700

> The big changes in the PKCS#1 v2.2 data structures are to support multi-prime RSA.  I believe that the changes were done in a way that is backward compatible with the non-multi-prime RSA.

And the changes that weren't made were taking the PKCS 1.5 padding out
back, merely NOT RECOMMENDING it. The text is woefully optimistic in
its description of Bleichenbacher's result. There are no key size
recommendations.

> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 7 Aug 2016 09:25:48 +0000

Watson Ladd <[email-masked]> writes:

>And the changes that weren't made were taking the PKCS 1.5 padding out back,
>merely NOT RECOMMENDING it. 

The current text is fine, using encode-then-compare with PKCS 1.5 signature
padding solves all (known) attacks, and while the crypto padding is still
problematic, the fact that neither SSH nor TLS nor IPsec use it any more
(apart from some old legacy stuff) means it's not such a big deal.  In any
case the alternative, OAEP, is pretty much impossible to implement without
side-channels, so it's probably worse than PKCS 1.5 no matter how
theoretically perfect it is.

>There are no key size recommendations.

That's a matter of policy for each application domain.  The problem with
keysize recommendations is that they're often driven by numerologists who, in
splendid isolation from reality, decide everyone has to use ludicrous-length
keys, even if it's securing a printer on an isolated LAN.

Peter.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 7 Aug 2016 07:18:57 -0700

> theoretically perfect it is.

The alternative for signatures (where there is no problem) is PSS.
PKCS 1.5 encryption has a problem.

OAEP without side-channels is very possible: you have to carry out the
operations unconditionally, and then mask based on the high byte. Of
course, if you really cared about simplifying standards and
eliminating this problem we would simply apply the private key
operation and hash the output with the input to obtain a symmetric
key.
> keys, even if it's securing a printer on an isolated LAN.

We can't kill RSA-1024 in libraries, thus ensuring no one uses it,
because of the need to support these applications. Until we remove the
code, it's only a flag away.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 8 Aug 2016 03:58:50 +0000

Watson Ladd <[email-masked]> writes:

>operations unconditionally, and then mask based on the high byte.

That's a generic answer that you can throw at any algorithm.  Can you provide
actual real code (or pseudocode) for doing OAEP in constant-time, branchless
manner?  You can do it with 1.5 because it's just a simple scan of a string
for which the above strategy works (I don't know what you mean by "mask based
on the high byte" but I assume it's that you accumulate all the compares into
a single byte and check for zero/nonzero at the end).  You can't do that with
OAEP.

Peter.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 7 Aug 2016 21:56:25 -0700

> a single byte and check for zero/nonzero at the end).  You can't do that with

http://www.inf.pucrs.br/~calazans/graduate/TPVLSI_I/RSA-oaep_spec.pdf Page 14.

Your "solution" to RSA 1.5 doesn't actually solve the problem. TLS
implementations have had to carefully handle parsing errors in the
data encrypted with RSA 1.5. That doesn't work for encrypting
arbitrary data without carefully designing the entire program around
the need for uniform errors, which is sort of the point of encryption.

Bleichenbacher oracles are regularly exploited in TLS implementations.
How about we follow Bernstein's advice and instead of blaming the
implementor, blame those who made their task hard.

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 8 Aug 2016 06:04:50 +0000

>http://www.inf.pucrs.br/~calazans/graduate/TPVLSI_I/RSA-oaep_spec.pdf Page 14.

That's an abstract description of OAEP, not a constant-time implementation.
I'll repeat my question:

  Can you provide actual real code (or pseudocode) for doing OAEP in constant-
  time, branchless manner?

In fact lets make it a requirement for real code, because in pseudocode you
can always just say "perform the padding check in constant time; // magic
happens here".

>implementations have had to carefully handle parsing errors in the data
>encrypted with RSA 1.5. 

Right, and if you know that you need to do that, it's quite possible with 1.5.
For example my TLS code has never provided anything other than a single error
type for a decrypt issue (or any crypto problem in general, it just says
"failed" and disconnects).  However this isn't possible with OAEP, because you
can't do the checking in constant time.

Peter.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 7 Aug 2016 23:15:53 -0700

>   Can you provide actual real code (or pseudocode) for doing OAEP in constant-

https://golang.org/src/crypto/rsa/rsa.go?s=16896:17021#L558

There is still a leak, but it's clear that this can be fixed by a
small modification to the bignum library.

> can't do the checking in constant time.

No, it's not possible for a library that provides a 1.5 PKCS
decryption primitive to ensure that application code treats the error
uniformly. That your TLS implementation can handle this problem
doesn't say anything about the scheme in any other protocol that
assumed it had an encryption primitive.

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 8 Aug 2016 11:38:26 +0000

>https://golang.org/src/crypto/rsa/rsa.go?s=16896:17021#L558

Ah OK.  I assume go has built-in range/bounds checks, since the problems I had
with constant-time eval were due to performing strict bounds-checking on
operations.

>No, it's not possible for a library that provides a 1.5 PKCS decryption
>primitive to ensure that application code treats the error uniformly.

But the same applies for OAEP, or any other scheme.  What I was saying was
that the simplicity of 1.5 makes it easier to get right than the complex OAEP
or other padding schemes.

Peter.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 8 Aug 2016 06:29:23 -0700

> or other padding schemes.

Except that an application using OAEP doesn't need to be carefully
written to ensure errors are uniform. The library author can take care
of all the tricky work themselves, once, and then everyone else enjoys
the fruits of their labor.

Bleichenbacher oracles are a real problem, routinely exploited. Manger
oracles less so, but I'm sure it still happens. PKCS should have used
a better RSA scheme that would avoid this whole mess: hopefully we
will be able to do this now that we have change control.

Sincerely,
Watson

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 8 Aug 2016 17:32:24 +0100

So looks like the "OBSOLETED" thing turns out to be a non-issue,
at least for this draft.

In an offlist mail, Burt Kaliski pointed out that:

"The "obsoletes" needs to be updated to refer to RFC3447 rather
than RFC2437."

And yes 3447 has indeed already obsoleted 2347, so this draft
creates no new problems, once the header's fixed:-) The reason
being that 3447 already has the multi-prime support, so if
there's any issues with RSAPrivateKey, then we already have
those, and they've not caused breakage that I've noticed.

Sorry - I should've spotted that when doing my AD review. I'll
make sure the draft is updated to obsolete 3447. (And the diff
vs. 3447 [1] also looks much cleaner at first sight, as it
ought.)

Cheers,
S.

[1]
https://tools.ietf.org/rfcdiff?url1=rfc3447&url2=draft-moriarty-pkcs1-01.txt

---

From: Kathleen Moriarty <[email-masked]>
Date: Mon, 8 Aug 2016 13:28:51 -0400

> vs. 3447 [1] also looks much cleaner at first sight, as it

Sorry we didn't catch that prior to your review.

Thanks,
Kathleen

-- 

Best regards,
Kathleen