Subject: [Curdle] Confirming a change to draft-ietf-curdle-rsa-sha2-12

From: "Salz, Rich" <[email-masked]>
Date: Sun, 11 Mar 2018 17:59:00 +0000

Eric rightly pounts out that this is a tech change made during the final stage of RFC editing and that it should be confirmed by the WG.  It's about MAY accepting fewer leading zero's.

Does anyone object?

    > > The value for 'rsa_signature_blob' is encoded as a string that
    > > contains an octet string S (which is the output of RSASSA-PKCS1-v1_5)
    > > and that has the same length (in octets) as the RSA modulus.  When S
    > > contains leading zeros, there exist signers that will send a shorter
    > > encoding of S that omits them.  A verifier MAY accept shorter
    > > encodings of S with one or more leading zeros omitted.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sun, 11 Mar 2018 17:56:27 -0700

Salz, Rich <[email-masked]> writes:

> Eric rightly pounts out that this is a tech change made during the
> final stage of RFC editing and that it should be confirmed by the WG.
> It's about MAY accepting fewer leading zero's.
> 
> Does anyone object?
> 

Question:

If the octet string S begins with the most significant bit set, is it a
MUST or a SHOULD or a MAY to prepend a zero octet so that the number is
not considered to be negative?

Consideration:

RFC 8017 section 4.1 specifies x as a nonnegative integer to be
converted to an Octet String primitive. It is not clear if the octet
string S is to always be considered unsigned or not.

RFC4251 provides that an mpint is a multiple precision integer in two's
complement format, stored as a string, 8 bits per byte, MSB first.
Negative numbers have the value 1 as the most significant bit of the
first byte of the data partition. If the most significant bit would be
set for a positive number, the number MUST be preceded by a zero byte
[RFC4251, sectio 5, page 8.]. RFC4251 provides that a 'string'

If draft-ietf-curdle-rsa-sha2-12 would like to see the
rsa_signature_blob be treated as an mpint with a leading zero-byte for
strings that otherwise would look negative, why not just change the type
in section 3 to read:

The resulting signature is encoded as follows:

    string    "rsa-sha2-256" / "rsa-sha2-512"
    mpint      rsa_signature_blob

  The value for 'rsa_signature_blob' is encoded as a string containing
  S   - an octet string which is the output of RSASSA-PKCS1-v1_5, of
  length equal to the length in octets of the RSA modulus. As with any
  mpint, there may be a leading zero octet to ensure that S is considered
  a nonnegative number.

If I have misunderstood the rationale for the change, please let me
know.

	Thank you,
	-- Mark

---

From: denis bider <[email-masked]>
Date: Sun, 11 Mar 2018 21:21:36 -0500

Mark:

> If the octet string S begins with the most significant bit set,
> is it a MUST or a SHOULD or a MAY to prepend a zero octet
> so that the number is not considered to be negative?

In historic and current practice, for "ssh-rsa", as per RFC 4253, the
signature encoding is specified as follows:

      string    "ssh-rsa"
      string    rsa_signature_blob

   The value for 'rsa_signature_blob' is encoded as a string containing
   s (which is an integer, without lengths or padding, unsigned, and in
   network byte order).

In my opinion, this is underspecified, and has led to discrepancies in
actual implementations.

The treatment of leading zeros is not clarified here. This RFC could have
specified to encode S, i.e. a concrete, well-specified RSA signature
encoding described in RFC 8017. Perhaps it meant to specify S but someone
went with "s" instead. We can't tell at this point.

"s" is the abstract equivalent to "S", i.e. it's the RSA signature with no
specified encoding. So the encoding is defined entirely in the above
language, and we know the following:

- It is an integer encoded as a string.
- It's not encoded as a mpint.
- No lengths or padding.
*- Unsigned, therefore no zero prefix if high bit is on.* (I believe this
answers the above question.)
- Network byte order.

This is ALMOST identical to "S". Except it does not clearly specify what to
do if the signature has a naturally occurring leading 0 which occurs in
1/256 of all signatures.

Therefore, implementations diverge in whether the leading 0 is sent or not.
Some implementations send it. Some do not.

My intent with "rsa-sha2-256" and "rsa-sha2-512" is not to change how the
rsa_signature_blob is encoded, it's to document it better.

I don't think it's realistic to change it. The new public key algorithms
are already implemented and widely deployed, and the practical
implementations already diverge in the choice they make about the leading
0, in the same way as "ssh-rsa" implementations diverged.

The fact that implementations diverge on this detail is not a big deal, but
there's good reason to document it. Otherwise people are prone to implement
and release software that's going to fail to validate 1/256 of signatures
sent by other SSH implementations.

> mpint     rsa_signature_blob

No no no no no no no! Wrong! Error! Please do not even mention this. :)

I marked it in red to emphasize that this is very wrong.

This is already implemented. It's already deployed. It's too late to
change. It's clear this is not an mpint, and has never been in "ssh-rsa"
either. Changing this to "mpint" now would completely divorce the spec from
actual implementations.

My intent with this late improvement to the text is to clarify actual
practice for the benefit of future implementations. Changing existing
implementations is a no-go.

On Sun, Mar 11, 2018 at 7:56 PM, Mark D. Baushke <[email-masked]> wrote:

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

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sun, 11 Mar 2018 21:43:44 -0700

Hi denis,

My question is answered.

>     > > encodings of S with one or more leading zeros omitted.

I do not object.

Given at approximately 1/256 signatures will have a naturally occurring
leading zero for which some implementations do not send it and some do,
I have no objection with the change in text.

I do wonder if the text would better read:

 A verifier SHOULD accept shorter encodings of S with one or more
 leading zeros omitted.

to encourage a stronger likelyhood that a valid, but short signature
would still be accepted. However, I will leave that to others to
determine.

	-- Mark

---

From: denis bider <[email-masked]>
Date: Mon, 12 Mar 2018 04:41:43 -0500

I agree with either MAY or SHOULD.

I suggested MAY on the following grounds:

1. I was speculating it could help this new text, which I knew was too
late, be accepted more easily. This hasn't panned out, but that seems for
the best. :)

2. Years in the future, there may be a time when deployed implementations
all encode "S" correctly. At that point, we may no longer want to SHOULD a
special case that's no longer relevant.

3. It weakens the claim of implementations that don't send the zeros that
they follow the spec. They can more easily make this claim if there is a
"SHOULD" to accommodate them.

However, I also see the following arguments for SHOULD:

4. It's unavoidable current practice, so it may convey the more accurate
idea to a new implementer.

5. Quantum computing will likely make RSA irrelevant much before all
implementations encode "S" correctly.

All things considered, I prefer MAY, and the main reason is 3 - not letting
implementations who don't send the zeros to claim that they're doing it
right. I'm also okay with SHOULD, but it enables the implementations that
created the problem to begin with. :)

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 12 Mar 2018 02:59:46 -0700

Hi denis,

Argument #3 works for me.

MAY is best. SHOULD lets broken implementations continue to be broken.

Thank you for your responses.

	Enjoy!
	-- Mark

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 12 Mar 2018 11:14:34 +0000

Does anyone else in the group have a view AGAINST the current wording?

Thank you to Denis for the detailed explanations, and Mark for helping trigger them. :)

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 12 Mar 2018 17:01:12 +0000

Please respond by Friday if you are AGAINST the proposed change about ignoring leading zero’s.

From: Rich Salz <[email-masked]>
Date: Monday, March 12, 2018 at 7:14 AM
To: denis bider <[email-masked]>, Mark Baushke <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: [Curdle] Confirming a change to draft-ietf-curdle-rsa-sha2-12

---

From: Ron Frederick <[email-masked]>
Date: Mon, 12 Mar 2018 18:01:10 -0700

Agreed on MAY here instead of SHOULD.

One of the original e-mails on this thread also mentioned prepending a leading 0x00 byte in cases where the high-bit of the first octet is set. I’m not sure we want to ever allow that. is anyone aware of any existing implementations that do that today, incorrectly thinking this value was supposed to follow the rules for encoding an “mpint” instead of a fixed-length octet string?

-- 
Ron Frederick
[email-masked]

---

From: denis bider <[email-masked]>
Date: Mon, 12 Mar 2018 23:28:20 -0500

Yes - this was the "mpint" idea that Mark broached. In SSH, the "mpint"
type is used to encode a signed integer, and prepends the \0 byte if the
value is positive and its high bit is on. This is necessary to distinguish
the positive value from a negative one.

As far as I know, there does NOT exist any SSH implementation that would
require such an erroneous encoding for an RSA signature.

If such an implementation did exist, it would fail to validate a very large
proportion of valid signatures as currently generated by most SSH servers
and clients. Unless my assumptions about RSA are incorrect, a very large
proportion of signatures, e.g. 1/3 - or up to 1/2 depending on the modulus
- will have the high bit set.

An implementation that would incorrectly require a signed encoding (like
"mpint") would be immediately discovered in development. I have not seen it
in practice.

What I cannot say is how many implementations might ACCEPT a signed
encoding if it is sent. If they do, I have no idea how many extra zeros
such implementations might accept. It might be that there exist
implementations (perhaps including ours!) that will accept an arbitrary
number of leading zeros. Perhaps there may be so many zeros as to fill up
to the maximum size of the SSH packet the implementation accepts.

If they do, though, I'm not aware of an attack that could be mounted based
on that, and it won't arise as a compatibility issue. So I think it's not
worthwhile to mention.

On Mon, Mar 12, 2018 at 8:01 PM, Ron Frederick <[email-masked]> wrote:

> One of the original e-mails on this thread also mentioned prepending a
> leading 0x00 byte in cases where the high-bit of the first octet is set.
> I’m not sure we want to ever allow that. is anyone aware of any existing
> implementations that do that today, incorrectly thinking this value was
> supposed to follow the rules for encoding an “mpint” instead of a
> fixed-length octet string?
>

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 13 Mar 2018 07:01:41 +0000

denis bider <[email-masked]> writes:

>What I cannot say is how many implementations might ACCEPT a signed encoding
>if it is sent. If they do, I have no idea how many extra zeros such
>implementations might accept. It might be that there exist implementations
>(perhaps including ours!) that will accept an arbitrary number of leading
>zeros.

My read-integer code accepts leading zeroes and strips them, based on
implementations that assume e.g. a 1024-bit RSA key always produces 128 bytes
of output and memcpy() the result into a zero-filled 128-byte field.  I've
seen stuff like this in the past, in PGP code I think (the read-integer code
is shared across a range of different crypto protocols).

I also reject anything that's supposed to be signed where the sign bit is set:

	/* If we're reading a signed integer then the sign bit can't be set 
	   since this would produce a negative value.  This differs from the 
	   ASN.1 code, where the incorrect setting of the sign bit is so common 
	   that we always treat integers as unsigned */

Peter.

---

From: denis bider <[email-masked]>
Date: Tue, 13 Mar 2018 02:19:11 -0500

> My read-integer code accepts leading zeroes and strips them,
> based on implementations that assume e.g. a 1024-bit RSA key
> always produces 128 bytes of output

It does. :)

> and memcpy() the result into a zero-filled 128-byte field.

That's actually the correct encoding according to RFC 8017.

>  I also reject anything that's supposed to be signed where

That's OK, it relates to mpint fields that aren't the RSA signature though.
The RSA signature is a string, not an mpint, and is unsigned.

On Tue, Mar 13, 2018 at 2:01 AM, Peter Gutmann <[email-masked]>
wrote:

> encoding

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 13 Mar 2018 07:49:35 +0000

>> always produces 128 bytes of output

No it doesn't, it can produce shorter lengths with increasingly smaller
probabilities.

>That's actually the correct encoding according to RFC 8017.

D'you mean I2OSP?  That takes a variable length as a parameter, it's not fixed
at any particular size.

The only format I know of that requires a fixed-length field, for no known
reason, is X9.62 and everything derived from it, which in practice means
everything that does ECC except for Curve25519/X25519/Ed25519/etc, which does
whatever it was djb felt like doing at the time.

Peter.

---

From: denis bider <[email-masked]>
Date: Tue, 13 Mar 2018 03:15:51 -0500

RFC 8017:

8.2 <https://tools.ietf.org/html/rfc8017#section-8.2>.  RSASSA-PKCS1-v1_5 [...]

8.2.1 <https://tools.ietf.org/html/rfc8017#section-8.2.1>.  Signature
Generation Operation [...]

  Output:

  S   signature, an octet string of length k, where k is the
      length in octets of the RSA modulus n

  [...]

  c.  Convert the signature representative s to a signature S of
      length k octets (see Section 4.1
<https://tools.ietf.org/html/rfc8017#section-4.1>):

      S = I2OSP (s, k).

S is fixed size. It is exactly the size of the modulus.

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 13 Mar 2018 08:39:25 +0000

>S is fixed size. It is exactly the size of the modulus.

Ah, I'd never noticed that (the original PKCS #1 hides that detail a lot
better).  However for the most common use, certificates and similar, this
would conflict with the ASN.1 DER requirements, which trump the PKCS #1 ones.

Does anything non-ASN.1 do the fixed-length encoding?  My test code includes
special-case tests for RSA data blocks shorter than the modulus to make sure
it can handle these cases, I know that there are at least some implementations
out there that do this because when I accidentally broke the variable-length
handling I got complaints and included the self-test checks to make sure it
wouldn't happen again.

Peter.

---

From: denis bider <[email-masked]>
Date: Tue, 13 Mar 2018 04:07:54 -0500

>  Does anything non-ASN.1 do the fixed-length encoding?

Yes, SSH. :)

RFC 4253:

6.6 <https://tools.ietf.org/html/rfc4253#section-6.6>.  Public Key Algorithms

   Signing and verifying using this key format is performed according to
   the RSASSA-PKCS1-v1_5 scheme in [RFC3447
<https://tools.ietf.org/html/rfc3447>] using the SHA-1 hash.

      string    "ssh-rsa"

The problem with this phrasing is that it doesn't say:

encode "S" as specified in RSASSA-PKCS1-v1_5

It instead says:

- "according to the RSASSA-PKCS1-v1_5 scheme" (which produces "S" as output)

- "a string containing s (which is an integer, without lengths or padding,
unsigned, and in network byte order)"

... which sure seems to be strongly hinting that we're encoding "S", but it
is *just* shy of saying that. It specifies the exact same encoding as "S" -
but it does not say what to do with the occasional naturally occurring
leading 0.

Because of this ambiguity, the spec for "rsa-sha2-256" and "rsa-sha2-512" -
which is the subject of present discussion - comes out and says explicitly:
though shalt encode "S". Which is fixed-length.

It has been like that since the first version if the draft, in November
2015, which you reviewed. :)

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 13 Mar 2018 09:18:39 +0000

>unsigned, and in network byte order)"

By saying "without lengths or padding" it seems to be saying that you
shouldn't zero-pad.  Or at least that's how I interpreted it.

>though shalt encode "S". Which is fixed-length.

Given that this has been ambiguous for untold years, it might be a good idea
to mention that you shouldn't expect to find this fixed-length zero-padded
encoding but may get a form, uh "without lengths or padding".  I don't care
either way since my code will handle both forms, but there are I-don't-know-
how-many different SSH implementations out there where we can't easily tell
what they do.

>It has been like that since the first version if the draft, in November 2015,
>which you reviewed. :)

Well, yeah, but that text says different things to different people :-).

Peter.

---

From: denis bider <[email-masked]>
Date: Tue, 13 Mar 2018 05:20:56 -0500

Well, to me, "without padding" means "don't add ornamentation to S". It
does not mean "trim leading zeros from S", since the spec says we're using
RSASSA-PKCS1-v1_5, and the output of that is S with a fixed-length
encoding. :)

But yes:

> Given that this has been ambiguous for untold years,
> it might be a good idea to mention that you shouldn't
> expect to find this fixed-length zero-padded encoding
> but may get a form, uh "without lengths or padding".

That is what we're doing. :) The reason for this discussion is that I
requested a sentence added (to draft-ietf-curdle-rsa-sha2) to clarify that
both S and leading-zero-trimmed-S are acceptable.

denis

---

From: Ron Frederick <[email-masked]>
Date: Tue, 13 Mar 2018 08:17:04 -0700

On Mar 12, 2018, at 9:28 PM, denis bider <[email-masked]> wrote:
> Yes - this was the "mpint" idea that Mark broached. In SSH, the "mpint" type is used to encode a signed integer, and prepends the \0 byte if the value is positive and its high bit is on. This is necessary to distinguish the positive value from a negative one.
> 
> As far as I know, there does NOT exist any SSH implementation that would require such an erroneous encoding for an RSA signature.
> 
> If such an implementation did exist, it would fail to validate a very large proportion of valid signatures as currently generated by most SSH servers and clients. Unless my assumptions about RSA are incorrect, a very large proportion of signatures, e.g. 1/3 - or up to 1/2 depending on the modulus - will have the high bit set.
> 
> An implementation that would incorrectly require a signed encoding (like "mpint") would be immediately discovered in development. I have not seen it in practice.

If an implementation did a byte-wise compare of the signature, I agree that this would be discovered very quickly. However, a byte-wise compare would also trigger interoperability failures with implementations which strip leading zeroes. If there are implementations stripping leading zeroes in some cases without triggering interoperability failures, I don’t see why adding zeroes would would be any less likely, especially if code such as the “mpint” conversion was improperly reused. If the bytes are converted back to an integer before being compared, the comparison would succeed in either of these cases, while if they were compared as byte strings, both would fail.

> What I cannot say is how many implementations might ACCEPT a signed encoding if it is sent. If they do, I have no idea how many extra zeros such implementations might accept. It might be that there exist implementations (perhaps including ours!) that will accept an arbitrary number of leading zeros. Perhaps there may be so many zeros as to fill up to the maximum size of the SSH packet the implementation accepts.
> 
> If they do, though, I'm not aware of an attack that could be mounted based on that, and it won't arise as a compatibility issue. So I think it's not worthwhile to mention.

I think the important thing here is to make sure the text is very clear that the _correct_ encoding is an unsigned fixed-length byte string with a length matching that of the RSA modulus n, as described in RFC 3447 section 8.2. On the verification side, I would actually be ok with removing the “MAY” (and the sentence prior to it) entirely, but if we do keep it I’m not sure why the text should limit things to only shorter encodings.
-- 
Ron Frederick
[email-masked]

---

From: denis bider <[email-masked]>
Date: Wed, 14 Mar 2018 05:55:55 -0500

> If there are implementations stripping leading zeroes in some cases
> without triggering interoperability failures, I don’t see why adding
> zeroes would would be any less likely

I have a high degree of confidence that no such implementations exist.

The reason for this high degree of confidence is that certain older
versions of our software - some of which are still in use, despite our
attempts to get people to upgrade - had a bug which would be triggered by
overlong signatures. The bug is such that if it was ever triggered, it
would certainly be brought to us.

We have never received news of this bug being triggered.

> I’m not sure why the text should limit things to only shorter encodings.

Because the text is to warn implementers of existing practice, not
non-existent practice. :) As explained above, I have a high degree of
confidence that there are no implementations that send overlong signatures.

On Tue, Mar 13, 2018 at 10:17 AM, Ron Frederick <[email-masked]> wrote:

> > If such an implementation did exist, it would fail to validate a very
> large proportion of valid signatures as currently generated by most SSH
> servers and clients. Unless my assumptions about RSA are incorrect, a very
> large proportion of signatures, e.g. 1/3 - or up to 1/2 depending on the
> modulus - will have the high bit set.
> >
> If an implementation did a byte-wise compare of the signature, I agree
> that this would be discovered very quickly. However, a byte-wise compare
> would also trigger interoperability failures with implementations which
> strip leading zeroes. If there are implementations stripping leading zeroes
> in some cases without triggering interoperability failures, I don’t see why
> adding zeroes would would be any less likely, especially if code such as
> the “mpint” conversion was improperly reused. If the bytes are converted
> back to an integer before being compared, the comparison would succeed in
> either of these cases, while if they were compared as byte strings, both
> would fail.
>
> > If they do, though, I'm not aware of an attack that could be mounted
> based on that, and it won't arise as a compatibility issue. So I think it's
> not worthwhile to mention.
>
> I think the important thing here is to make sure the text is very clear
> that the _correct_ encoding is an unsigned fixed-length byte string with a
> length matching that of the RSA modulus n, as described in RFC 3447 section
> 8.2. On the verification side, I would actually be ok with removing the
> “MAY” (and the sentence prior to it) entirely, but if we do keep it I’m not
> sure why the text should limit things to only shorter encodings.
> --
> Ron Frederick
> [email-masked]
>
>
>
>