9. Encoding Methods for Signatures with Appendix
Encoding methods consist of operations that map between octet string
messages and octet-string-encoded messages, which are converted to
and from integer message representatives in the schemes. The integer
message representatives are processed via the primitives. The
encoding methods thus provide the connection between the schemes,
which process messages, and the primitives.
An encoding method for signatures with appendix, for the purposes of
this document, consists of an encoding operation and optionally a
verification operation. An encoding operation maps a message M to an
encoded message EM of a specified length. A verification operation
determines whether a message M and an encoded message EM are
consistent, i.e., whether the encoded message EM is a valid encoding
of the message M.
The encoding operation may introduce some randomness, so that
different applications of the encoding operation to the same message
will produce different encoded messages, which has benefits for
provable security. For such an encoding method, both an encoding and
a verification operation are needed unless the verifier can reproduce
the randomness (e.g., by obtaining the salt value from the signer).
For a deterministic encoding method, only an encoding operation is
needed.
Two encoding methods for signatures with appendix are employed in the
signature schemes and are specified here: EMSA-PSS and
EMSA-PKCS1-v1_5.
9.1. EMSA-PSS
This encoding method is parameterized by the choice of hash function,
mask generation function, and salt length. These options should be
fixed for a given RSA key, except that the salt length can be
variable (see [JONSSON] for discussion). Suggested hash and mask
generation functions are given in Appendix B. The encoding method is
based on Bellare and Rogaway's Probabilistic Signature Scheme (PSS)
[RSARABIN][PSS]. It is randomized and has an encoding operation and
a verification operation.
Figure 2 illustrates the encoding operation.
__________________________________________________________________
+-----------+
| M |
+-----------+
|
V
Hash
|
V
+--------+----------+----------+
M' = |Padding1| mHash | salt |
+--------+----------+----------+
|
+--------+----------+ V
DB = |Padding2| salt | Hash
+--------+----------+ |
| |
V |
xor <--- MGF <---|
| |
| |
V V
+-------------------+----------+--+
EM = | maskedDB | H |bc|
+-------------------+----------+--+
__________________________________________________________________
Figure 2: EMSA-PSS Encoding Operation
Note that the verification operation follows reverse steps to recover
salt and then forward steps to recompute and compare H.
Notes:
1. The encoding method defined here differs from the one in Bellare
and Rogaway's submission to IEEE 1363a [PSS] in three respects:
* It applies a hash function rather than a mask generation
function to the message. Even though the mask generation
function is based on a hash function, it seems more natural to
apply a hash function directly.
* The value that is hashed together with the salt value is the
string (0x)00 00 00 00 00 00 00 00 || mHash rather than the
message M itself. Here, mHash is the hash of M. Note that
the hash function is the same in both steps. See Note 3 below
for further discussion. (Also, the name "salt" is used
instead of "seed", as it is more reflective of the value's
role.)
* The encoded message in EMSA-PSS has nine fixed bits; the first
bit is 0 and the last eight bits form a "trailer field", the
octet 0xbc. In the original scheme, only the first bit is
fixed. The rationale for the trailer field is for
compatibility with the Integer Factorization Signature
Primitive using Rabin-Williams (IFSP-RW) in IEEE 1363
[IEEE1363] and the corresponding primitive in ISO/IEC
9796-2:2010 [ISO9796].
2. Assuming that the mask generation function is based on a hash
function, it is RECOMMENDED that the hash function be the same as
the one that is applied to the message; see Section 8.1 for
further discussion.
3. Without compromising the security proof for RSASSA-PSS, one may
perform Steps 1 and 2 of EMSA-PSS-ENCODE and EMSA-PSS-VERIFY (the
application of the hash function to the message) outside the
module that computes the rest of the signature operation, so that
mHash rather than the message M itself is input to the module.
In other words, the security proof for RSASSA-PSS still holds
even if an opponent can control the value of mHash. This is
convenient if the module has limited I/O bandwidth, e.g., a smart
card. Note that previous versions of PSS [RSARABIN][PSS] did not
have this property. Of course, it may be desirable for other
security reasons to have the module process the full message.
For instance, the module may need to "see" what it is signing if
it does not trust the component that computes the hash value.
4. Typical salt lengths in octets are hLen (the length of the output
of the hash function Hash) and 0. In both cases, the security of
RSASSA-PSS can be closely related to the hardness of inverting
RSAVP1. Bellare and Rogaway [RSARABIN] give a tight lower bound
for the security of the original RSA-PSS scheme, which
corresponds roughly to the former case, while Coron [FDH] gives a
lower bound for the related Full Domain Hashing scheme, which
corresponds roughly to the latter case. In [PSSPROOF], Coron
provides a general treatment with various salt lengths ranging
from 0 to hLen; see [IEEE1363A] for discussion. See also
[JONSSON], which adapts the security proofs in [RSARABIN]
[PSSPROOF] to address the differences between the original and
the present version of RSA-PSS as listed in Note 1 above.
5. As noted in IEEE 1363a [IEEE1363A], the use of randomization in
signature schemes -- such as the salt value in EMSA-PSS -- may
provide a "covert channel" for transmitting information other
than the message being signed. For more on covert channels, see
[SIMMONS].
9.1.1. Encoding Operation
EMSA-PSS-ENCODE (M, emBits)
Options:
Hash hash function (hLen denotes the length in octets of
the hash function output)
MGF mask generation function
sLen intended length in octets of the salt
Input:
M message to be encoded, an octet string
emBits maximal bit length of the integer OS2IP (EM) (see Section
4.2), at least 8hLen + 8sLen + 9
Output:
EM encoded message, an octet string of length emLen = \ceil
(emBits/8)
Errors: "Encoding error"; "message too long"
Steps:
1. If the length of M is greater than the input limitation for
the hash function (2^61 - 1 octets for SHA-1), output
"message too long" and stop.
2. Let mHash = Hash(M), an octet string of length hLen.
3. If emLen < hLen + sLen + 2, output "encoding error" and stop.
4. Generate a random octet string salt of length sLen; if sLen =
0, then salt is the empty string.
5. Let
M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt;
M' is an octet string of length 8 + hLen + sLen with eight
initial zero octets.
6. Let H = Hash(M'), an octet string of length hLen.
7. Generate an octet string PS consisting of emLen - sLen - hLen
- 2 zero octets. The length of PS may be 0.
8. Let DB = PS || 0x01 || salt; DB is an octet string of length
emLen - hLen - 1.
9. Let dbMask = MGF(H, emLen - hLen - 1).
10. Let maskedDB = DB \xor dbMask.
11. Set the leftmost 8emLen - emBits bits of the leftmost octet
in maskedDB to zero.
12. Let EM = maskedDB || H || 0xbc.
13. Output EM.
9.1.2. Verification Operation
EMSA-PSS-VERIFY (M, EM, emBits)
Options:
Hash hash function (hLen denotes the length in octets of
the hash function output)
MGF mask generation function
sLen intended length in octets of the salt
Input:
M message to be verified, an octet string
EM encoded message, an octet string of length emLen = \ceil
(emBits/8)
emBits maximal bit length of the integer OS2IP (EM) (see Section
4.2), at least 8hLen + 8sLen + 9
Output: "consistent" or "inconsistent"
Steps:
1. If the length of M is greater than the input limitation for
the hash function (2^61 - 1 octets for SHA-1), output
"inconsistent" and stop.
2. Let mHash = Hash(M), an octet string of length hLen.
3. If emLen < hLen + sLen + 2, output "inconsistent" and stop.
4. If the rightmost octet of EM does not have hexadecimal value
0xbc, output "inconsistent" and stop.
5. Let maskedDB be the leftmost emLen - hLen - 1 octets of EM,
and let H be the next hLen octets.
6. If the leftmost 8emLen - emBits bits of the leftmost octet in
maskedDB are not all equal to zero, output "inconsistent" and
stop.
7. Let dbMask = MGF(H, emLen - hLen - 1).
8. Let DB = maskedDB \xor dbMask.
9. Set the leftmost 8emLen - emBits bits of the leftmost octet
in DB to zero.
10. If the emLen - hLen - sLen - 2 leftmost octets of DB are not
zero or if the octet at position emLen - hLen - sLen - 1 (the
leftmost position is "position 1") does not have hexadecimal
value 0x01, output "inconsistent" and stop.
11. Let salt be the last sLen octets of DB.
12. Let
M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt ;
M' is an octet string of length 8 + hLen + sLen with eight
initial zero octets.
13. Let H' = Hash(M'), an octet string of length hLen.
14. If H = H', output "consistent". Otherwise, output
"inconsistent".
9.2. EMSA-PKCS1-v1_5
This encoding method is deterministic and only has an encoding
operation.
EMSA-PKCS1-v1_5-ENCODE (M, emLen)
Option:
Hash hash function (hLen denotes the length in octets of
the hash function output)
Input:
M message to be encoded
emLen intended length in octets of the encoded message, at
least tLen + 11, where tLen is the octet length of the
Distinguished Encoding Rules (DER) encoding T of
a certain value computed during the encoding operation
Output:
EM encoded message, an octet string of length emLen
Errors: "message too long"; "intended encoded message length too
short"
Steps:
1. Apply the hash function to the message M to produce a hash
value H:
H = Hash(M).
If the hash function outputs "message too long", output
"message too long" and stop.
2. Encode the algorithm ID for the hash function and the hash
value into an ASN.1 value of type DigestInfo (see
Appendix A.2.4) with the DER, where the type DigestInfo has
the syntax
DigestInfo ::= SEQUENCE {
digestAlgorithm AlgorithmIdentifier,
digest OCTET STRING
}
The first field identifies the hash function and the second
contains the hash value. Let T be the DER encoding of the
DigestInfo value (see the notes below), and let tLen be the
length in octets of T.
3. If emLen < tLen + 11, output "intended encoded message length
too short" and stop.
4. Generate an octet string PS consisting of emLen - tLen - 3
octets with hexadecimal value 0xff. The length of PS will be
at least 8 octets.
5. Concatenate PS, the DER encoding T, and other padding to form
the encoded message EM as
EM = 0x00 || 0x01 || PS || 0x00 || T.
6. Output EM.
Notes:
1. For the nine hash functions mentioned in Appendix B.1, the DER
encoding T of the DigestInfo value is equal to the following:
MD2: (0x)30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04
10 || H.
MD5: (0x)30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04
10 || H.
SHA-1: (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H.
SHA-224: (0x)30 2d 30 0d 06 09 60 86 48 01 65 03 04 02 04
05 00 04 1c || H.
SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00
04 20 || H.
SHA-384: (0x)30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00
04 30 || H.
SHA-512: (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00
04 40 || H.
SHA-512/224: (0x)30 2d 30 0d 06 09 60 86 48 01 65 03 04 02 05
05 00 04 1c || H.
SHA-512/256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 06
05 00 04 20 || H.
2. In version 1.5 of this document, T was defined as the BER
encoding, rather than the DER encoding, of the DigestInfo value.
In particular, it is possible -- at least in theory -- that the
verification operation defined in this document (as well as in
version 2.0) rejects a signature that is valid with respect to
the specification given in PKCS #1 v1.5. This occurs if other
rules than DER are applied to DigestInfo (e.g., an indefinite
length encoding of the underlying SEQUENCE type). While this is
unlikely to be a concern in practice, a cautious implementor may
choose to employ a verification operation based on a BER decoding
operation as specified in PKCS #1 v1.5. In this manner,
compatibility with any valid implementation based on PKCS #1 v1.5
is obtained. Such a verification operation should indicate
whether the underlying BER encoding is a DER encoding and hence
whether the signature is valid with respect to the specification
given in this document.
10. Security Considerations
Security considerations are discussed throughout this memo.
11. References
11.1. Normative References
[GARNER] Garner, H., "The Residue Number System", IRE Transactions
on Electronic Computers, Volume EC-8, Issue 2, pp.
140-147, DOI 10.1109/TEC.1959.5219515, June 1959.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.
[RSA] Rivest, R., Shamir, A., and L. Adleman, "A Method for
Obtaining Digital Signatures and Public-Key
Cryptosystems", Communications of the ACM, Volume 21,
Issue 2, pp. 120-126, DOI 10.1145/359340.359342, February
1978.
11.2. Informative References
[ANSIX944] ANSI, "Key Establishment Using Integer Factorization
Cryptography", ANSI X9.44-2007, August 2007.
[BKS] Bleichenbacher, D., Kaliski, B., and J. Staddon, "Recent
Results on PKCS #1: RSA Encryption Standard", RSA
Laboratories, Bulletin No. 7, June 1998.
[BLEICHENBACHER]
Bleichenbacher, D., "Chosen Ciphertext Attacks Against
Protocols Based on the RSA Encryption Standard PKCS #1",
Lecture Notes in Computer Science, Volume 1462, pp. 1-12,
1998.
[CHOSEN] Desmedt, Y. and A. Odlyzko, "A Chosen Text Attack on the
RSA Cryptosystem and Some Discrete Logarithm Schemes",
Lecture Notes in Computer Science, Volume 218, pp.
516-522, 1985.
[COCHRAN] Cochran, M., "Notes on the Wang et al. 2^63 SHA-1
Differential Path", Cryptology ePrint Archive: Report
2007/474, August 2008, <http://eprint.iacr.org/2007/474>.
[FASTDEC] Quisquater, J. and C. Couvreur, "Fast Decipherment
Algorithm for RSA Public-Key Cryptosystem", Electronic
Letters, Volume 18, Issue 21, pp. 905-907,
DOI 10.1049/el:19820617, October 1982.
[FDH] Coron, J., "On the Exact Security of Full Domain Hash",
Lecture Notes in Computer Science, Volume 1880, pp.
229-235, 2000.
[FOPS] Fujisaki, E., Okamoto, T., Pointcheval, D., and J. Stern,
"RSA-OAEP is Secure under the RSA Assumption", Lecture
Notes in Computer Science, Volume 2139, pp. 260-274,
August 2001.
[FORGERY] Coppersmith, D., Halevi, S., and C. Jutla, "ISO 9796-1 and
the new forgery strategy", rump session of Crypto, August
1999.
[HAASTAD] Haastad, J., "Solving Simultaneous Modular Equations of
Low Degree", SIAM Journal on Computing, Volume 17,
Issue 2, pp. 336-341, DOI 10.1137/0217019, April 1988.
[HANDBOOK] Menezes, A., van Oorschot, P., and S. Vanstone, "Handbook
of Applied Cryptography", CRC Press, ISBN: 0849385237,
1996.
[HASHID] Kaliski, B., "On Hash Function Firewalls in Signature
Schemes", Lecture Notes in Computer Science, Volume 2271,
pp. 1-16, DOI 10.1007/3-540-45760-7_1, February 2002.
[IEEE1363] IEEE, "Standard Specifications for Public Key
Cryptography", IEEE Std 1363-2000,
DOI 10.1109/IEEESTD.2000.92292, August 2000,
<http://ieeexplore.ieee.org/document/891000/>.
[IEEE1363A]
IEEE, "Standard Specifications for Public Key Cryptography
- Amendment 1: Additional Techniques", IEEE Std 1363a-
2004, DOI 10.1109/IEEESTD.2004.94612, September 2004,
<http://ieeexplore.ieee.org/document/1335427/>.
[ISO18033] International Organization for Standardization,
"Information technology -- Security techniques --
Encryption algorithms - Part 2: Asymmetric ciphers", ISO/
IEC 18033-2:2006, May 2006.
[ISO9594] International Organization for Standardization,
"Information technology - Open Systems Interconnection -
The Directory: Public-key and attribute certificate
frameworks", ISO/IEC 9594-8:2008, December 2008.
[ISO9796] International Organization for Standardization,
"Information technology - Security techniques - Digital
signature schemes giving message recovery - Part 2:
Integer factorization based mechanisms",
ISO/IEC 9796-2:2010, December 2010.
[JONSSON] Jonsson, J., "Security Proofs for the RSA-PSS Signature
Scheme and Its Variants", Cryptology ePrint
Archive: Report 2001/053, March 2002,
<http://eprint.iacr.org/2001/053>.
[LOWEXP] Coppersmith, D., Franklin, M., Patarin, J., and M. Reiter,
"Low-Exponent RSA with Related Messages", Lecture Notes in
Computer Science, Volume 1070, pp. 1-9, 1996.
[MANGER] Manger, J., "A Chosen Ciphertext Attack on RSA Optimal
Asymmetric Encryption Padding (OAEP) as Standardized in
PKCS #1 v2.0", Lecture Notes in Computer Science, Volume
2139, pp. 230-238, DOI 10.1007/3-540-44647-8_14, 2001.
[MD4] Dobbertin, H., "Cryptanalysis of MD4", Lecture Notes in
Computer Science, Volume 1039, pp. 53-69,
DOI 10.1007/3-540-60865-6_43, 1996.
[MD4FIRST] Dobbertin, H., "The First Two Rounds of MD4 are Not One-
Way", Lecture Notes in Computer Science, Volume 1372, pp.
284-292, DOI 10.1007/3-540-69710-1_19, March 1998.
[MD4LAST] den Boer, B. and A. Bosselaers, "An Attack on the Last Two
Rounds of MD4", Lecture Notes in Computer Science, Volume
576, pp. 194-203, DOI 10.1007/3-540-46766-1_14, 1992.
[NEWATTACK]
Coron, J., Joye, M., Naccache, D., and P. Paillier, "New
Attacks on PKCS #1 v1.5 Encryption", Lecture Notes in
Computer Science, Volume 1807, pp. 369-381,
DOI 10.1007/3-540-45539-6_25, May 2000.
[OAEP] Bellare, M. and P. Rogaway, "Optimal Asymmetric Encryption
- How to Encrypt with RSA", Lecture Notes in Computer
Science, Volume 950, pp. 92-111, November 1995.
[PA98] Bellare, M., Desai, A., Pointcheval, D., and P. Rogaway,
"Relations Among Notions of Security for Public-Key
Encryption Schemes", Lecture Notes in Computer
Science, Volume 1462, pp. 26-45, DOI 10.1007/BFb0055718,
1998.
[PADDING] Coron, J., Naccache, D., and J. Stern, "On the Security of
RSA Padding", Lecture Notes in Computer Science, Volume
1666, pp. 1-18, DOI 10.1007/3-540-48405-1_1, December
1999.
[PKCS1_22] RSA Laboratories, "PKCS #1: RSA Cryptography Standard
Version 2.2", October 2012.
[PREFIX] Stevens, M., Lenstra, A., and B. de Weger, "Chosen-prefix
collisions for MD5 and applications", International
Journal of Applied Cryptography, Volume 2, No. 4, pp.
322-359, July 2012.
[PSS] Bellare, M. and P. Rogaway, "PSS: Provably Secure Encoding
Method for Digital Signatures", Submission to IEEE P1363a,
August 1998, <http://grouper.ieee.org/groups/1363/
P1363a/contributions/pss-submission.pdf>.
[PSSPROOF] Coron, J., "Optimal Security Proofs for PSS and Other
Signature Schemes", Lecture Notes in Computer
Science, Volume 2332, pp. 272-287,
DOI 10.1007/3-540-46035-7_18, 2002.
[RFC1319] Kaliski, B., "The MD2 Message-Digest Algorithm", RFC 1319,
DOI 10.17487/RFC1319, April 1992,
<http://www.rfc-editor.org/info/rfc1319>.
[RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
DOI 10.17487/RFC1321, April 1992,
<http://www.rfc-editor.org/info/rfc1321>.
[RFC2313] Kaliski, B., "PKCS #1: RSA Encryption Version 1.5",
RFC 2313, DOI 10.17487/RFC2313, March 1998,
<http://www.rfc-editor.org/info/rfc2313>.
[RFC2315] Kaliski, B., "PKCS #7: Cryptographic Message Syntax
Version 1.5", RFC 2315, DOI 10.17487/RFC2315, March 1998,
<http://www.rfc-editor.org/info/rfc2315>.
[RFC2437] Kaliski, B. and J. Staddon, "PKCS #1: RSA Cryptography
Specifications Version 2.0", RFC 2437,
DOI 10.17487/RFC2437, October 1998,
<http://www.rfc-editor.org/info/rfc2437>.
[RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography
Standards (PKCS) #1: RSA Cryptography Specifications
Version 2.1", RFC 3447, DOI 10.17487/RFC3447, February
2003, <http://www.rfc-editor.org/info/rfc3447>.
[RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security
(TLS) Protocol Version 1.2", RFC 5246,
DOI 10.17487/RFC5246, August 2008,
<http://www.rfc-editor.org/info/rfc5246>.
[RFC5652] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70,
RFC 5652, DOI 10.17487/RFC5652, September 2009,
<http://www.rfc-editor.org/info/rfc5652>.
[RFC5958] Turner, S., "Asymmetric Key Packages", RFC 5958,
DOI 10.17487/RFC5958, August 2010,
<http://www.rfc-editor.org/info/rfc5958>.
[RFC6149] Turner, S. and L. Chen, "MD2 to Historic Status",
RFC 6149, DOI 10.17487/RFC6149, March 2011,
<http://www.rfc-editor.org/info/rfc6149>.
[RFC7292] Moriarty, K., Ed., Nystrom, M., Parkinson, S., Rusch, A.,
and M. Scott, "PKCS #12: Personal Information Exchange
Syntax v1.1", RFC 7292, DOI 10.17487/RFC7292, July 2014,
<http://www.rfc-editor.org/info/rfc7292>.
[RSARABIN] Bellare, M. and P. Rogaway, "The Exact Security of Digital
Signatures - How to Sign with RSA and Rabin", Lecture
Notes in Computer Science, Volume 1070, pp. 399-416,
DOI 10.1007/3-540-68339-9_34, 1996.
[RSATLS] Jonsson, J. and B. Kaliski, "On the Security of RSA
Encryption in TLS", Lecture Notes in Computer
Science, Volume 2442, pp. 127-142,
DOI 10.1007/3-540-45708-9_9, 2002.
[SHA1CRYPT]
Wang, X., Yao, A., and F. Yao, "Cryptanalysis on SHA-1",
Lecture Notes in Computer Science, Volume 2442, pp.
127-142, February 2005,
<http://csrc.nist.gov/groups/ST/hash/documents/
Wang_SHA1-New-Result.pdf>.
[SHOUP] Shoup, V., "OAEP Reconsidered (Extended Abstract)",
Lecture Notes in Computer Science, Volume 2139, pp.
239-259, DOI 10.1007/3-540-44647-8_15, 2001.
[SHS] National Institute of Standards and Technology, "Secure
Hash Standard (SHS)", FIPS PUB 180-4, August 2015,
<http://dx.doi.org/10.6028/NIST.FIPS.180-4>.
[SILVERMAN]
Silverman, R., "A Cost-Based Security Analysis of
Symmetric and Asymmetric Key Lengths", RSA
Laboratories, Bulletin No. 13, 2000.
[SIMMONS] Simmons, G., "Subliminal Communication is Easy Using the
DSA", Lecture Notes in Computer Science, Volume 765, pp.
218-232, DOI 10.1007/3-540-48285-7_18, 1994.
