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

[Ron Frederick <[e-mail]>]

On Mar 12, 2018, at 9:28 PM, denis bider <[e-mail]> 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
[e-mail]