Score:2

May RSA-PSS DB MSB be 1?

fi flag

I've used OpenSSL to generate an RSA-PSS keypair.

-----BEGIN PRIVATE KEY-----
MIIBUgIBADALBgkqhkiG9w0BAQoEggE+MIIBOgIBAAJBAKjJmhflBebbRJt0JNWe
elk9w32jGxvZrvxO7kdpvNFWCgXIXSU0zC26R2Rca1w81sY4MpKfKl0baIK06Dbp
F6cCAwEAAQJANfamrocJeQKXj7/1WtrdMRT/IHb6XtAdEwvFQM28kYyUU4QuIxGO
cJ90rX99FdhOouUtbeYVXfnR7+I4NL6C+QIhAN6GukudUZqsor+AH/fuVg1Z4cUo
8slDhv5hoHJq1HizAiEAwi1yKT4YeBWc7vxwBwQ5i2DtrhfOxOs1+Mzij7xu1z0C
IQCqekz+4OdDuD52t5HGP7FtSQ7OHTDjP/iLqf9hqLZeQQIgf7DVBuwPuUA1QC9/
GA4eLVrjUf3T+kjW6DMLtgvrM90CIGAwntt2VAvNb2rCNMsLqtkM0iLGGopRkXqW
hkb6wXFX
-----END PRIVATE KEY-----

I'm signing a short message (the text "RSA-PSS") using OpenSSL with SHA256 and validating that signature by hand:

$ cat hash_value | openssl pkeyutl -sign -inkey rsapsskey.pem -pkeyopt digest:sha256 -pkeyopt rsa_padding_mode:pss -pkeyopt rsa_pss_saltlen:30 >signature

In some instances the MSB of the DB is set to 1, i.e., the block begins with 0x80 instead of 0x00. If the seed fills the whole DB, the separating byte 0x01 becomes 0x81. For example:

$s$ = 3193b488a362a71b7b1fb4328a3f2eea2423f762a87ad9823b01c21e1fe7296a3d4530513945c8b59f30427fa9c9c60340d20320d10a0f21290669060b833b83

$s^e \mod n$ = 64f252e4a9dc625f881b87010ab54c5dc557fac18ff11573621e92aa68415067c12e5a3c85aafe33c90a7fd352ddb5c0dcada72268c55d74cc034fe9ff54b9bc

mDB = 64f252e4a9dc625f881b87010ab54c5dc557fac18ff11573621e92aa684150

mask = e58271cfa607b848676d08342483e8e57aee64c76853f2a09944f6a731d2a7

DB = 8170232b0fdbda17ef768f352e36a4b8bfb99e06e7a2e7d3fb5a640d5993f7

seed = 70232b0fdbda17ef768f352e36a4b8bfb99e06e7a2e7d3fb5a640d5993f7

$m'$ = 000000000000000068c8e017fdb4880b0b276605be9003f9cb6a9504b8b83edac2ccf9d0de420ca170232b0fdbda17ef768f352e36a4b8bfb99e06e7a2e7d3fb5a640d5993f7

$H(m')$ = 67c12e5a3c85aafe33c90a7fd352ddb5c0dcada72268c55d74cc034fe9ff54b9

I.e., signature verification works, but why is the first byte of DB 0x81 instead of 0x01? I cannot find a reference to that behavior in RFC8017.

Score:0
ng flag

I'll use PKCS#1v2.2 (RSA Laboratories edition) as a reference.

Looking a the private key with an ASN.1 decoder, the public modulus $n$ is 512-bit, thus in RSASSA-PSS-VERIFY we have $modBits\,=\,512$, $k=64$.

Thus in EMSA-PSS-VERIFY we have $emBits\,=\,modBits\;-\,1\,=\,511$.  $EM$ is the question's 64-octet string following $s^e\,\bmod n$.  $emLen\,=\,\lceil\,emBits\,/\,8\,\rceil\,=\,64$.  The hash is SHA-256, thus $hLen\,=\,32$.  The question's salt is 30 octets, thus $sLen\,=\,30$.  The constraint $emBits\,\ge\,8\,hLen\,+\,8\,sLen\,+\,9$ is met (with an extra $7$ bits).

At EMSA-PSS-VERIFY step 3, $emLen\,\ge\,hLen+\,sLen\,+\,2$, the check passes.

At step 4, the rightmost octet of $EM$ has hexadecimal value $\text{0xbc}$, the check passes.

At step 5, $maskedDB$ is the leftmost $emLen\;-\,hLen\;-\,1\,=\,31$ octets, as "mDB" in the question.

At step 6, it is considered the $8\,emLen\;-\,emBits\,=\,1$ leftmost bit(s) of the leftmost octet of $maskedDB$. That octet is $\text{0x64}$, that bit is $0$, the check passes.

At step 7, $dbMask$ is the 31 octets of the question's "mask".

At step 8, $DB$ is the 31 octets of the question's "DB".

At step 9, it is set the leftmost $8\,emLen\;-\,emBits\,=\,1$ bit(s) of the leftmost octet in $DB$ to zero. That leftmost octet goes from $\text{0x81}$ to $\text{0x01}$.


Why is the first byte of DB $\text{0x81}$ instead of $\text{0x01}$?

That first byte/leftmost octet is $\text{0x81}$ after step 8 because $dbMask$ is computed over an integer number of octets wide enough to perform the XOR of step 8, with $k\,+1\,\bmod\,8\,=\,1$ extra bit(s) if the left octet, which take pseudorandom value(s) in $dbMask$, thus in $DB$ after the XOR (which happens to be with zero bits, as checked at step 6). But these extra bit(s) in $DB$ get masked out to zero at step 9.

After that masking, the byte is $\text{0x01}$ because the signature is valid and the salt has been set to the maximum possible size $k\;-\,hLen\;-\,1$. It would be $\text{0x00}$ for any smaller salt size.


We can now answer the question in title:

May RSA-PSS $DB$ Most Significant Bit be 1?

No for $DB$ as computed

  • during signature generation, in EMSA-PSS-ENCODE at step 8
  • during signature verification, in EMSA-PSS-VERIFY at step 9, if $k\,\bmod8\,\ne\,1$ (because then step 9 masks this Most Significant Bit) or if the signature is valid (because then this Most Significant Bit must be zero, which will be checked at step 10);

but possibly so for $DB$ as computed during signature verification in EMSA-PSS-VERIFY

  • at step 8 (irrespective of signature validity and value of $k$); this is what occurs in the question
  • at step 9, though only for invalid signature and $k\,\bmod8\,=\,1$ (e.g. 2049-bit $n$). Notice that for such $k$, step 9 performs no masking, and step 10 will catch the signature as invalid if the Most Significant Bit of $DB$ happens to be 1.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.