1

I am wrapping the RSACng class from the .Net API. Whilst unit testing, I run checks against an array of possibilities:

  • Key Size = 1024, 2048, or 3072 bits
  • Padding Mode = PKCS v1, or PSS (=PKCS v2?)
  • Hash Algorithm = SHA-1, SHA256, SHA512

I test for all 3*2*3=18 possible configurations. All tests pass except one combination:

  • Key size = 1024 bits
  • Padding Mode = PSS
  • Hash Algorithm = SHA512

Should this be expected, and how could have I anticipated it? So far, Google has not been my friend.

I also ran a similar batch of unit tests for RSA encryption, and noted a 1024 bits key is incompatible with OAEP-SHA1 and OAEP-SHA256 padding modes. I suspect the key is not large enought, but I was again unable to read some info as to why this was happening.

Ama
  • 113
  • 4
  • 1
    Having about 80 bits of security, using 1024 bit RSA is also incompatible with most key size requirements, and mixing it with a hash function that supplies close to 512 bits of security in this setting makes little to no sense. – Maarten Bodewes Feb 07 '20 at 21:52

1 Answers1

4

Yes, this is expected, if the RSASSA-PSS signing code/test uses salt the width of the hash, which is customary. In that case, a $h$-bit hash (with $h$ multiple of 8) requires an RSA public modulus at least $2h+10$ bits (see justification in comment). That's semi-clearly stated in PKCS#1 v2.2, section 9.1.1, condition on enBits, with actual test in step 3.

That's because the message representative needs to convey $h$ bits for the message hash, $h$ bits for the salt, $8$ bits for a one-byte identifier¹, so we are at $2h+8$. Then there is a 01h byte stuffed on the left, which requires one additional bit. And the public modulus needs to be at least one bit larger so that the value obtained is always less than the public modulus.

In PSS, the salt length can be made a parameter, rather than fixed to the hash width as usual. Also, it can optionally be deterministic or fixed, rather than random as usual. But far from all APIs allow that.

There are similar limitations for RSAES-OAEP (without flexibility: the tag's hash always is as wide as the hash, even when the tag is empty/absent, as it often is).

¹ That identifier BCh plays a role when using PSS padding for Rabin signatures or when it is used $r\to\min(r^d\bmod N,N-(r^d\bmod N))$ instead of the textbook RSA private key operation, in order to allow immediate textbook-RSA encryption of the signature with any public key with public modulus of the same size as the one used for signature.

fgrieu
  • 140,762
  • 12
  • 307
  • 587
  • I've got the OAEP calculations for size in handy bytes over here. Note the N/A for RSA-1024 with OAEP using SHA-512. – Maarten Bodewes Feb 08 '20 at 04:32
  • @MaartenBodewes that's interesting because .Net allows me to combine RSA1024 & OAEP-SHA512, but not to combine RSA1024 & OAEP-SHA1 or SHA256 (allow = does not throw an error). I understand some combinations might make little sense, which is partly why I am testing all possible scenarios: I wanted to know if my wrapper requires to "validate" the configuration (key length & hash length) another programmer would set up whilst using the wrapper. (sort of a last resort layer of security) – Ama Feb 10 '20 at 16:54
  • I'll be short: If you want to make sense of anything, the .NET crypto API is not a good starting point. It does some things correctly, many other things are unspecified or just badly designed. – Maarten Bodewes Feb 10 '20 at 16:56
  • About the salt length: "rather than fixed to the hash width as usual". Is the hash width recommended or optimal in some way? If not, why has it become the "usual" choice? OpenSSL by default seems to choose the maximum salt length when signing. – Reinier Torenbeek Jul 27 '21 at 17:30
  • The $2h+9$ bits calculation isn't quite right.

    In s9.1.1 the restriction is $emBits \ge 8hLen + 8sLen + 9$. But in s8.1.1, $emBits=modBits-1$, where $modBits$ is the bit size of the public modulus.

    So the correct restriction is $|n| \ge 8hLen + 8sLen + 10$. For example if the hash is SHA-512 and the salt matches the hash length at 512 bits, you need at least a 1034-bit key.

     – Richard Kettlewell Apr 06 '23 at 08:10
  • @Richard Kettlewell: I agree that follows from the letter of the standard, and I fixed the answer accordingly. I wonder why there is this extra bit, which as far as I can tell is not necessary mathematically. – fgrieu Apr 06 '23 at 08:53
  • If $EM$ was allowed to be the same length as $n$ (i.e. the extra bit wasn't included) then it could convert to an integer greater than $n$, contradicting the requirements on $m$ in s5.2.1. AFAICS this can only happen if $emBits$ is a multiple of 8 since otherwise step 11 will set (at least) the leftmost bit of $EM$ to 0. So it deals with the special case where $|n|\equiv 1 \pmod 8$, which I suspect to be vanishingly rare. – Richard Kettlewell Apr 06 '23 at 10:26
  • Actually I'm losing faith in that logic (but don't have time to revisit it right now). – Richard Kettlewell Apr 06 '23 at 10:41
  • 1
    @Richard Kettlewell: ah, I got it: there's this 0x01 byte that I did not account for, which requires an extra bit. – fgrieu Apr 06 '23 at 10:47