Independent Submission M. Kutylowski, P. Kubiak Internet Draft Wroclaw University of Technology Intended status: Informational M. Tabor, D. Wachnik Expires: May 2012 Trusted Information Consulting November 14, 2011 Mediated RSA cryptography specification for additive private key splitting (mRSAA) draft-kutylowski-mrsa-algorithm-01 Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on May 2, 2012. Kutylowski et al. Expires May 14, 2012 [Page 1] Internet-Draft Mediated RSA cryptography specification November 2011 Copyright Notice Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Abstract This document describes recommendations for the implementation of public key cryptography based on the mediated RSA algorithm. The Mediated RSA algorithm bases on fragmentation of a private key. As a result the signature process consists from multiple stages. The verification process is the same as in the case of RSA algorithm [RFC3447]. Table of Contents 1. Introduction...................................................4 2. Conventions used in this document..............................4 3. Key types......................................................7 3.1. RSA public key............................................7 3.2. Mediated RSAA private key.................................7 3.2.1. User's mRSAA private key.............................8 3.2.2. Finalization service's mRSAA private key.............9 4. Data conversion primitives.....................................9 4.1. I2OSP.....................................................9 4.2. OS2IP....................................................10 5. Cryptographic primitives......................................10 5.1. Key generation primitives................................10 5.1.1. MRSAA_F_GP..........................................11 5.1.2. MRSAA_U_GP..........................................12 5.2. Encryption and decryption primitives.....................13 5.2.1. MRSAA_F_DP..........................................13 5.2.2. MRSAA_U_DP..........................................14 5.2.3. MRSAA_EP............................................15 5.3. Signature and verification primitives....................15 5.3.1. MRSAA_U_SP1.........................................16 5.3.2. MRSAA_F_SP1.........................................16 5.3.3. MRSAA_VP1...........................................17 6. Overview of schemes...........................................18 7. Key generation schemes........................................18 7.1. Key generation operation.................................19 Kutylowski et al. Expires May 14, 2012 [Page 2] Internet-Draft Mediated RSA cryptography specification November 2011 7.1.1. Generation of the private key assigned to identifier Uid of a user..............................................19 MRSAA_U_GS-DRBG-GENERATE (K,df)............................19 7.1.2. Key generation on the finalization service's side...19 8. Encryption schemes............................................20 8.1. MRSAAES-OAEP.............................................21 8.1.1. Encryption operation................................21 8.1.2. Decryption operation................................21 8.2. MRSAAES-PKCS1-v1_5.......................................23 8.2.1. Encryption operation................................23 8.2.2. Decryption operation................................23 9. Signature schemes with appendix...............................25 9.1. MRSAASSA-PSS.............................................25 9.1.1. Signature generation operations.....................26 9.1.2. Signature verification operation....................27 9.2. MRSAASSA-PKCS1-v1_5......................................28 9.2.1. Signature generation operations.....................28 9.2.2. Signature verification operation....................30 10. Encoding method for signatures with appendix.................30 11. Security Considerations......................................30 11.1. Identification of assets and actors.....................31 11.2. Key generation security.................................32 11.2.1. Key generation by a separate yet distributed service. ...........................................................33 11.2.2. Key generation by the a separate, centralized service ...........................................................34 11.2.3. Key generation executed directly by the user's device and the finalization service with a two-party protocol.....37 11.2.4. Key generation on user's device....................37 11.2.5. Key generation directly by the finalization service.38 11.3. Replacement of a finalization service...................39 11.4. Signature creation process security.....................40 11.5. Decryption process security.............................44 11.6. Short summary of possible security techniques...........44 12. IANA Considerations..........................................45 13. Conclusions..................................................46 14. References...................................................46 14.1. Normative References....................................46 14.2. Informative References..................................46 15. Acknowledgments..............................................49 Appendix A. Pseudorandom generator primitives....................50 A.1. CTR_DRBG_Instantiate_algorithm(entropy_input, personalization_string).......................................50 A.2. CTR_DRBG_Generate_algorithm(working_state, requested_number_of_bits, additional_input)...................50 Appendix B. Standard RSA primitives..............................51 A.3. Encryption and decryption primitives.....................51 A.3.1. RSAEP((n,e),m)......................................51 A.3.2. RSADP(K,c)..........................................51 A.4. Signature and verification primitives....................52 A.4.1. RSASP1(K,m).........................................52 Kutylowski et al. Expires May 14, 2012 [Page 3] Internet-Draft Mediated RSA cryptography specification November 2011 A.4.2. RSAVP1((n,e),s).....................................52 Appendix C. ASN.1 Syntax.........................................53 A.5. MRSAA key representation.................................53 A.5.1. MRSAA public key syntax.............................53 A.5.2. MRSAA private key syntax............................53 A.5.3. Scheme identification...............................54 Appendix D. ASN.1 Module.........................................55 Appendix E. Intellectual Property Considerations.................56 1. Introduction This memo is the extension to the RFC 3447. This document describes aspects specific to the mediated RSA signature scheme such as: o Key generation o Signature creation The recommendations are intended for general application within computer and communications systems, and as such include a fair amount of flexibility. It is expected that application standards based on these specifications may include additional constraints. mRSA algorithm may exists in many versions, depending on the way how the private RSA exponent is split between parties. We might distinguish two main cases (cf. sect. 1 of [8]): o mRSAA for additive splitting of the private exponent: d \equiv du + df (mod lcm(p-1,q-1)) for some integers du, df, o and mRSAM if the private exponent is divided multiplicatively: d \equiv du' * df' (mod lcm(p-1,q-1)) for some integers du', df' coprime with lcm(p-1,q-1). Since each of the above possibilities determines different communication content between the user and the finalization service during signature generation (this imposes constraints on interoperability of implementations of mRSA schemes), and since addition gives more flexibility in choice of a key generation procedure, this document covers only the additive scheme. 2. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [1]. Kutylowski et al. Expires May 14, 2012 [Page 4] Internet-Draft Mediated RSA cryptography specification November 2011 (n, e) RSA public key c ciphertext representative, an integer between 0 and n-1 cp ciphertext created using du key, an integer between 0 and n-1 C ciphertext, an octet string Cp ciphertext created using du, an octet string d private exponent of a user, an integer such that df + du \equiv d (mod \lambda(n)) df private component of a finalization service, a positive integer such that df + du \equiv d (mod \lambda(n)) dP p's exponent, a positive integer such that: e(dP)\equiv 1 (mod(p-1)) NOTE: The dP value is not used in the MRSAA algorithm. It has been placed for compliancy with the RSA specification. dQ q's exponent, a positive integer such that: e(dQ)\equiv 1 (mod(q-1)) NOTE: The dQ value is not used in the MRSAA algorithm. It has been placed for compliancy with the RSA specification. e public exponent EM encoded message, an octet string emLen intended length in octets of an encoded message Fm finalization service's master key H hash value, an output of Hash Hash hash function hLen output length in octets of hash function Hash K RSA private key, we assume that that meaningful fields of the K are at least (n,e,d,p,q) Kutylowski et al. Expires May 14, 2012 [Page 5] Internet-Draft Mediated RSA cryptography specification November 2011 Kf RSA private key which consists of (n, df) Ku RSA private key which consists of (n, du) k length in octets of the modulus n l intended length of octet string lcm(.,.) least common multiple of two nonnegative integers m message representative, an integer between 0 and n-1 mp message decrypted using df key, an integer between 0 and n-1 M message, an octet string MGF mask generation function n RSA modulus, n=pq P encoding parameters, an octet string p,q prime factors of the modulus qInv CRT coefficient, a positive integer less than p such: q(qInv)\equiv 1 (mod p) NOTE: This value is not used in the MRSAA algorithm. It has been placed for compliancy with the RSA specification. s signature representative, an integer between 0 and n-1 Sp signature representative, created using du key, an integer between 0 and n-1 S signature, an octet string Sp signature created using du key, an octet string Uid user identifier, an octet string x a nonnegative integer X an octet string corresponding to x \abs(x) absolute value of argument x Kutylowski et al. Expires May 14, 2012 [Page 6] Internet-Draft Mediated RSA cryptography specification November 2011 \eea(a,b) an extended Euclidean algorithm which gives a result that satisfies: result*a\equiv gcd(a,b) mod b, where gcd(a,b) is the greatest common divisor of arguments a and b. \floor(x) the greatest integer not greater than real number x \lambda(n) lcm(p-1, q-1), where n = pq \log_2(x) logarithm in base 2 from positive number x \xor bitwise exclusive-or of two octet strings || concatenation operator ||.|| octet length operator 3. Key types This document employs two types of key: an RSA public and RSA private key. The RSA private key is divided into two fragments, one fragment is stored privately by the user the other is privately recalculated by the finalization service on finalization requests. The public key is not fragmented and thus is independent from private key fragmentation schema. 3.1. RSA public key For the purposes of this document, an RSA public key consists of two components: n, the modulus, an odd, positive integer e, the public exponent, an odd, positive integer In a valid RSA public key, the modulus n is a product of two odd primes p and q, and the public exponent e is an integer between 3 and n-1 satisfying gcd(e, \lambda(n)) = 1, where \lambda(n) = lcm (p-1,q-1). 3.2. Mediated RSAA private key This document defines mediated RSA key as a set of two keys: Kutylowski et al. Expires May 14, 2012 [Page 7] Internet-Draft Mediated RSA cryptography specification November 2011 o User's mRSAA private key o Finalization service's mRSAA private key These keys are created from standard RSA key (the base key) which in particular includes: o p, q, prime factors of the public modulus n, that is pq=n o d, the private exponent, a nonnegative integer In the valid RSA private key, the product pq equals the modulus n from the corresponding public key, and the private exponent d is a positive integer less than \lambda(n) satisfying: ed \equiv 1 (mod \lambda(n)). In mediated RSA variant the private exponent is split between two parties: between the user and the finalization service. In mRSAA the split is done to satisfy the following relation: d \equiv df + du (mod \lambda(n)). NOTE: In this document we require that df is longer than modulus n, hence above we have a congruence modulo \lambda(n) instead of equality of integers. Although, it is possible to use a different key splitting method, this document covers only the method based on the addition (additive scheme). 3.2.1. User's mRSAA private key User's key consists of two components: o n, the modulus, a positive integer, the same one as in the public key o du, user's private exponent, an integer In a valid mRSAA user's private key the user's private component meets the following equation: df + du \equiv d (mod \lambda(n)) The process of key generation is described in section 7. Because some key generation techniques might yield du being a negative integer (cf. sect. 11.2. ), we do not exclude du < 0 in the document Kutylowski et al. Expires May 14, 2012 [Page 8] Internet-Draft Mediated RSA cryptography specification November 2011 3.2.2. Finalization service's mRSAA private key For the purposes of this document the finalization service's private key Kf consists of the pair (n,df) where the components have the following meaning: o n, the modulus, a positive integer, the same one as in the public key o df, the finalization service's private exponent, a positive integer In a valid mRSAA finalization service's private key, the finalization service's private component meets the following equation: df + du \equiv d (mod \lambda(n)) 4. Data conversion primitives In this document are used following data conversion primitives: I2OSP: Integer-to-Octet-String primitive OS2IP: Octet-String-to-Integer primitive This document describes briefly syntax of data conversion primitives. More detailed description can be found in [RFC3447]. For the purposes of this document, and consistent with ASN.1 syntax, an octet string is an ordered sequence of octets (eight-bit bytes). The sequence is indexed from first (conventionally, leftmost) to last rightmost). For purposes of conversion to and from integers, the first octet is considered the most significant in the following conversion primitives. 4.1. I2OSP I2OSP converts a nonnegative integer to an octet string of a specified length. I2OSP (x, l) Input: x nonnegative integer to be converted l intended length of the resulting octet string Kutylowski et al. Expires May 14, 2012 [Page 9] Internet-Draft Mediated RSA cryptography specification November 2011 Output: X corresponding octet string of length l; or "integer too large" 4.2. OS2IP OS2IP converts an octet string to a nonnegative integer. OS2IP (X) Input: X octet string to be converted Output: x corresponding nonnegative integer 5. Cryptographic primitives Cryptographic primitives are basic mathematical operations on which cryptographic schemes can be built. They are intended for implementation in hardware or as software modules, and are not intended to provide security apart from a scheme. Five types of primitive are specified in this document, organized in sections: key generation; encryption and decryption; and signature and verification. The specifications of the primitives assume that certain conditions are met by the inputs, in particular that public and private keys are valid. 5.1. Key generation primitives The purpose of using key generation primitives is to create mRSAA key pair: a public key and pair of private keys: a finalization service's key and a user's key. The finalization service's exponent df is derived from a master service key Fm and a user identifier Uid. The derivation is a multiple stage process. For example, if Fm is chosen as an Kutylowski et al. Expires May 14, 2012 [Page 10] Internet-Draft Mediated RSA cryptography specification November 2011 asymmetric signature key then generation process of exponent df might be as follows: Uid is signed with key Fm, and this signature is a seed for pseudorandom string generation (cf. deterministic seed for generation of pseudorandom bits in paper [16]). The resulting string df (output of the generator) should have bitlength defined as follows: \floor(\log_2(n))+1 + Delta where Delta is a fixed value taken from the set {80,...,128}. That is df should be longer by Delta bits from the length of the modulus n. The aim of taking a longer bitstring df is to equalize chances of each single value modulo \lambda(n) to be chosen as the remainder rem in the relation df \equiv rem mod \lambda(n) Note that the finalization service does not know the value \lambda(n). The greater Delta is the tighten equalization is achieved. Note that in case of asymmetric method there is no need to make public the key complementary to Fm, that is the signature verification key. The complementary key should remain secret to prevent any cryptoanalytic attempts: one option is to use it internally in the system for the purpose of verification of implementation correctness (e.g., of subliminal channel freeness), another possibility is to completely erase the complementary key. Generation of the pseudorandom bit string uses deterministic random bit generator which bases on block ciphers algorithms (CTR_DRBG). CTR_DRBG's primitives are specified in the paper [3]. For the purposes of this document, primitives specified in [3] have been briefly described in Appendix A. The user's private key is created on a basis of the finalization service's private key (n,df) and the RSA base key K. 5.1.1. MRSAA_F_GP MRSAA_F_GP generates pseudorandom key of requested length on a basis of a given bit string. This document describes MRSA_F_GP as a primitive which is based on the CRT_DRBG pseudorandom generator. An implementer may use other pseudorandom generator type conformant to [3]. MRSAA_F_GP(w, len) Input: Kutylowski et al. Expires May 14, 2012 [Page 11] Internet-Draft Mediated RSA cryptography specification November 2011 w the string of bits received from the consuming application len Requested bitlength of the output string Output: returned_bits pseudorandom bit string with length specified in len Assumptions: CRT_DRBG generator conformant to [3] is used. Steps: 1. Let H = Hash(w) 2. Let (V, Key, reseed_counter) = CTR_DRBG_Instantiate_algorithm(null, H) 3. Let (status, returned_bits, Key, V, reseed_counter) = CTR_DRBG_Generate_algoritm(reseed_counter, len, null) 4. If the status is SUCCESS output returned_bits and stop. In a different case return an error 5.1.2. MRSAA_U_GP Creates user's private exponent from finalization service's private exponent and a base RSA key. NOTE: For alternative procedures see sect.11.2. MRSAA_U_GP(K,df) Input: K Base RSA private key which contains values (n, d, p, q) df Private exponent of finalization service's key Output: Kutylowski et al. Expires May 14, 2012 [Page 12] Internet-Draft Mediated RSA cryptography specification November 2011 du Private exponent of user's key Assumptions: The K is a valid RSA private key corresponding to the public key (e,n) for which df has been calculated Steps: 1. Let lambda = (p-1)*(q-1)/gcd(p-1,q-1). 2. Let du = (d - df) mod lambda 5.2. Encryption and decryption primitives An encryption primitive produces a ciphertext from a message representative under a control of public key. The primitive MRSAA_F_DP is used to transform a ciphertext to a form which can be processed by the MRSAA_U_DP primitive. The primitive MRSAA_U_DP recovers a message from MRSAA_F_DP output. The encryption/decryption scheme involves all three primitives described below. Primitives RSAEP and RSADP are briefly described in the Appendix B. MRSAA_EP is identical as a RSAEP primitive and thus they can be used interchangeably. 5.2.1. MRSAA_F_DP MRSAA_F_DP transforms ciphertext to the form which can be decrypted by a MRSAA_U_DP primitive. MRSAA_F_DP(Kf, c) Input: Kf Finalization service's private key in the form of a pair of (n, df) c ciphertext representative, an integer between 0 and n-1 Output: Kutylowski et al. Expires May 14, 2012 [Page 13] Internet-Draft Mediated RSA cryptography specification November 2011 mp message partially decrypted using df key, an integer between 0 and n-1 Assumptions: The Kf key is a valid mRSAA key which corresponds to the user's identifier Uid. Steps: 1. Let mp = RSADP(Kf, c) 5.2.2. MRSAA_U_DP Retrieves message from partially deciphered message (result of an MRSAA_F_DP) MRSAA_U_DP(Ku, mp, c) Input: Ku user's private key in the form of a pair of (n, du) mp message partially decrypted using df key, an integer between 0 and n-1 c ciphertext representative, an integer between 0 and n-1 Output: m message representative, an integer between 0 and n-1 Assumptions: The Ku key is a valid mRSAA key (n, du) Steps: 1. Let Ku' = (n,\abs(du)) 2. Let temp = RSADP(Ku', c) 3. If (du < 0) temp = \eea(temp,n) 4. Let m = mp*temp mod n Kutylowski et al. Expires May 14, 2012 [Page 14] Internet-Draft Mediated RSA cryptography specification November 2011 5.2.3. MRSAA_EP MRSAA_EP encrypts given message MRSAA_EP((n,e),m) Input: (n, e) RSA public key m message representative, an integer between 0 and n-1 Output: c ciphertext representative, an integer between 0 and n-1; or "message representative out of range" Assumptions: The public key (n, e) is valid Steps: 1. Let c = RSAEP((n,e) , m) 5.3. Signature and verification primitives A verification primitive works in similar way like an RSAVP1 primitive. Signature process uses two primitives specified below: an MRSAA_U_SP1 and MRSAA_F_SP1 primitive. MRSAA_U_SP1 primitive creates partial signature, which cannot be verified before execution of the MRSAA_F_SP1 primitive. Signature/verification scheme uses all three primitives specified below. Verification primitive is identical as an RSAVP1 primitive and thus RSAVP1 can be used instead of MRSAA_VP1. Primitives RSAVP1, RSASP1 are briefly described in Appendix B. For the final signature creation step (MRSAA_F_SP1) we strongly recommend to perform signature verification before passing the result to a user (see section 11. Security considerations). We Kutylowski et al. Expires May 14, 2012 [Page 15] Internet-Draft Mediated RSA cryptography specification November 2011 assume that signature verification includes verification of encoding correctness. 5.3.1. MRSAA_U_SP1 MRSAA_U_SP1 creates partial signature from given message. MRSAA_U_SP1(Ku,m) Input: Ku user's private key in the form of a pair of (n, du) m message representative, an integer between 0 and n-1 Output: sp representative of a partial signature, an integer between 0 and n-1, created using Ku key Assumptions: The Ku key is a valid mRSAA key which corresponds to the user's identifier Uid and public key (n,e) Steps: 1. Let Ku' = (n,\abs(du)) 2. Let sp = RSASP1(Ku', m) 3. If (du < 0) then sp = \eea(sp,n) mod n 5.3.2. MRSAA_F_SP1 MRSAA_F_SP1 creates valid RSA signature from given partial signature. MRSAA_F_SP1(Kf, sp, m) Input: Kf Finalization service's private key in the form of a pair (n, df) sp representative of a partial signature, an integer between 0 and n-1, created using Ku key Kutylowski et al. Expires May 14, 2012 [Page 16] Internet-Draft Mediated RSA cryptography specification November 2011 m message representative, an integer between 0 and n-1 Output: s signature representative, an integer between 0 and n-1 Assumptions: The Kf key is a valid mRSAA key which corresponds to the key Ku Steps: 1. Let temp = RSADP1(Kf, m) 2. Let s = temp*sp mod n 5.3.3. MRSAA_VP1 MRSAA_VP1 retrieves a message from a given signature MRSAA_VP1((n, e), s) Input: (n, e) RSA public key s signature representative, an integer between 0 and n-1 Output: c message representative, an integer between 0 and n-1 Assumptions: The public key (n, e) is valid Steps: 1. Let m = RSAVP1((n, e) , s) Kutylowski et al. Expires May 14, 2012 [Page 17] Internet-Draft Mediated RSA cryptography specification November 2011 6. Overview of schemes A scheme combines cryptographic primitives and other techniques to achieve a particular security goal. Two types of scheme are specified in this document: encryption schemes and signature schemes with appendix. The schemes specified in this document are limited in scope in that their operations consist only of steps to process data with an mRSAA public or private key. Additionally steps necessary for private key splitting have been described (see section 7.1. ). Thus, in addition to the scheme operations, an application will typically include key management operations by which parties may select mRSAA public and private keys for a scheme operation. The specific additional operations and other details are outside the scope of this document. As was the case for the cryptographic primitives (Section 5), the specifications of scheme operations assume that certain conditions are met by the inputs, in particular that mRSAA public and private keys are valid. The behavior of an implementation is thus unspecified when a key is invalid. The impact of such unspecified behavior depends on the application. In general possible means of addressing key validation include: o explicit key validation by the application; o key validation within the public-key infrastructure; o assignment of liability for operations performed with an invalid key to the party which generated the key. In case of mRSAA signatures the key validation could be performed by verifying the first finalized signature using the public key. To validate mRSAA decryption keys, decryption of some test message may be performed. 7. Key generation schemes A key generation scheme combines a MRSAA_U_GP and MRSAA_F_GP with a RSASP1 operation to create MRSAA private key pair for user and finalization service. The finalization service's key can be derived from a service key Fm and user identifier Uid. This kind of solution eliminates necessity of key archival on the finalization service's side. To derive private key from service's master key Fm some secure pseudorandom numbers generator is used. Fm is described below as an asymmetric signature key of a deterministic scheme. However, since Fm is used internally in the system, we do not exclude possibility of implementing other secure derivation methods of exponents df. As Kutylowski et al. Expires May 14, 2012 [Page 18] Internet-Draft Mediated RSA cryptography specification November 2011 stated in section 5.1. we recommend the key complementary to asymmetric signature key Fm to remain secret. In key generation schemes described below we do not assume that all input variables are available at the same location, and that all output variables are generated at the same place. 7.1. Key generation operation 7.1.1. Generation of the private key assigned to identifier Uid of a user MRSAA_U_GS-DRBG-GENERATE (K,df) Input: K Base RSA private key which contains values (n, d, p, q) df Finalization services exponent calculated for the user of identifier Uid Output: Ku RSA key (n, du) such that du + df \equiv d \lambda(n), and e*d \equiv 1 \lambda(n), where (n,e) is the public key for which exponent df has been calculated on finalization service side Steps: 1. Apply an MRSAA_U_GP to generate user's MRSAA private exponent du: du = MRSAA_U_GP(K,df) 2. Return (n,du) as Ku 7.1.2. Key generation on the finalization service's side MRSAA_F_GS-DRBG-GENERATE generates finalization service's private key. An implementer may use other deterministic signature algorithms (i.e. RSASSA-PKCS-v1_5-SIGN) or other methods to generate df exponent. MRSAA_F_GS-DRBG-GENERATE (n, Uid, Fm) Input: Kutylowski et al. Expires May 14, 2012 [Page 19] Internet-Draft Mediated RSA cryptography specification November 2011 n public RSA modulus of the user and the identifier Uid Uid User identifier, an octet string Fm Finalization service's master key, a RSA key Output: Kf Finalization service's key, RSA key (n, df) which together with key Ku shall satisfy the congruence: df + du \equiv d mod \lambda(n), where d is the private exponent corresponding to the public key (n,e) of the user of identifier Uid, that is d*e \equiv 1 mod \lambda(n) Assumptions: The finalization service uses a fixed value Delta, an integer from the set {80,...,128} (see remarks in sect. 5.1. ). In the case when Kf is generated anew for each signature finalization or/and for each decryption operation concerning the user of identifier Uid, that is why the process must be deterministic. 1. Steps:Apply the RSASP1 primitive to Fm key and Uid integer representative value to create signature W, with salt of length 0 (cf. [RFC3447], point 4 on page 37), or with salt being a fixed value (cf. [RFC3447], sect. 8.1 page 29): W = RSASSA-PSS-SIGN(Fm, Uid) 2. Convert W octet string to an integer representative w: w = OS2IP(W) 3. Apply an MRSAA_F_GP to generate finalization service's MRSAA private exponent df: df = MRSAA_F_GP(w, \floor(\log_2(n))+1 + Delta) 4. Return (n, df) as Kf 8. Encryption schemes For the purpose of this document, an encryption scheme consists of an encryption operation and decryption operation, where the encryption operation produces a ciphertext from a message with a recipient's RSA public key, and the decryption operation recovers original message in two stages: transformation made by finalization service, and decryption performed by an recipient. The encryption scheme can be employed in variety of applications, especially in systems with different level access to confidential Kutylowski et al. Expires May 14, 2012 [Page 20] Internet-Draft Mediated RSA cryptography specification November 2011 information. The scheme assures additional level of protection because of a usage of a finalization service. The document extends existing RSA encryption and decryption scheme, particularly the decryption scheme, which differs from the RSA scheme. The Encryption scheme combines encryption and decryption primitives with an encoding method for encryption. The encryption operations apply a message encoding operation to a message to produce an encoded message, which is then converted to an integer message representative. An encryption primitive is applied to the message representative to produce the ciphertext. Reversing this, the decryption operations apply a decryption primitive to the ciphertext to recover a message representative, which is then converted to an octet string encoded message. A message decoding operation is applied to the encoded message to recover the message and verify the correctness of the decryption. 8.1. MRSAAES-OAEP MRSAA-OAEP combines RSAEP, MRSAA_U_DP, and MRSAA_F_DP primitives (Sections 5.2.2. 5.2. ) with EME-OAEP encoding method specified in [RFC3447]. 8.1.1. Encryption operation There are no differences in encryption operation (RSAES-OAEP- ENCRYPT) according to [RFC3447]. 8.1.2. Decryption operation MRSAA-F-OAEP-DECRYPT(Kf, C) Options: Hash Hash function (hLen denotes the length in octets of the hash function output) MGF Mask generation function Input: Kf Finalization service's private key (k denotes the length in octets of the RSA modulus n) Kutylowski et al. Expires May 14, 2012 [Page 21] Internet-Draft Mediated RSA cryptography specification November 2011 C Ciphertext to be decrypted, an octet string of length k, where k >= 2hLen + 2 Output: Cp Transformed ciphertext, which can be deciphered using Ku key Assumptions: The Kf key is generated with MRSAA_F_GS-DRBG-GENERATE and corresponds to the public key which has been used to produce the ciphertext C. Steps: 1. Length checking a. If a the length of the ciphertext C is not k octets, output "decryption error" and stop. b. If k < 2hLen + 2, output "decryption error and stop" 2. RSA decryption a. Convert the ciphertext C to an integer ciphertext representative c (see Section 4.2. ): c = OS2IP(C) b. Apply the MRSAA_F_DP decryption primitive (Section 5.2.1. )to the mRSAA private key Kf and ciphertext representative c to produce an integer representative cp: cp = MRSAA_F_DP(Kf,c) c. Convert the transformed ciphertext cp to an encoded transformed ciphertext Cp of length k octets: Cp = I2OSP(cp,k) d. Output the Cp MRSAA-U-OAEP-DECRYPT(Ku, Cp, C, L) Input: Ku User's private key (k denotes the length in octets of the RSA modulus n) Cp Transformed ciphertext, to be decrypted C Ciphertext, an octet string L Optional label whose association with the message is to be verified; the default value for L, if L is not provided, is the empty string Kutylowski et al. Expires May 14, 2012 [Page 22] Internet-Draft Mediated RSA cryptography specification November 2011 Output: M message, an octet string of length mLen, where mLen <= k - 2hLen - 2 Steps: 1. RSA decryption a. Convert the ciphertext Cp to an integer ciphertext representative cp (see Section 4.2. ): cp = OS2IP(Cp) b. Convert the ciphertext C to an integer ciphertext representative c (see Section 4.2. c = OS2IP(C) c. Apply the MRSAA_U_DP decryption primitive (Section 5.2.2. )to the RSA private key Ku and ciphertext representative cp to produce an integer representative m' of an encoded message: m' = MRSAA_U_DP(Ku, cp, c) d. Convert the encoded message representative m' to an encoded message M' of length k octets: M' = I2OSP(m',k) 2. EME-OAEP decoding message M from string M': Process is performed on M' as described in [RFC3447] 3. Output the message M 8.2. MRSAAES-PKCS1-v1_5 MRSAAES-PKCS1-v1_5 combines the RSAEP and MRSAADP primitives with the EME-PKCS1-v1_5 encoding method. RSAES-PKCS1-v1_5 can operate on messages length up to k-11 octets, although care should be taken to avoid certain attacks on low-exponent RSA due to Coppersmith, et al. when long messages are encrypted (see [5]). As general rule, the use of this scheme for encrypting an arbitrary message, as opposed to a randomly generated key, is not recommended. Moreover, one must still avoid encrypting the same random key with relatively short, different randomizers, to some number of recipients sharing the same small public exponent (see section 5 and appendix C of [17]). 8.2.1. Encryption operation There are no differences between MRSAA and RSA encryption process and thus RSAES-PKC1-V1_5-ENCRYPT should be used. Detailed specification can be found in the [RFC3447] 8.2.2. Decryption operation MRSAAES-F-PKCS1-V1_5-DECRYPT (Kf,C) Kutylowski et al. Expires May 14, 2012 [Page 23] Internet-Draft Mediated RSA cryptography specification November 2011 Input: Kf Finalization service's private key (k denotes the length in octets of the RSA modulus n) C Ciphertext to be decrypted, an octet string of length k, where k is the length in octets of the RSA modulus n Output: Cp Transformed ciphertext, which can be deciphered using Ku key Assumptions: The Kf key is generated with MRSAA_F_GS-DRBG-GENERATE and corresponds to the public key which has been used to produce the ciphertext C. Steps: 1. Length checking: If the length of the ciphertext C is not k octets (or if k < 11), output "decryption error" and stop. 2. RSA decryption a. Convert the ciphertext C to an integer ciphertext representative c (see Section 4.2. ): c = OS2IP(C) b. Apply the MRSAA_F_DP decryption primitive (section 5.2.1. )to the mRSAA private key Kf and ciphertext representative c to produce an integer representative cp: cp = MRSAA_F_DP(Kf,c) c. Convert the transformed ciphertext cp to an encoded transformed ciphertext Cp of length k octets: Cp = I2OSP(cp,k) 3. Output Cp MRSAAES-U-PKCS-1-V1_5-DECRYPT (Ku, CP, C) Input: Ku User's private key (k denotes the length in octets of the RSA modulus n) Cp Transformed ciphertext, to be decrypted C Original ciphertext, octet string Output: Kutylowski et al. Expires May 14, 2012 [Page 24] Internet-Draft Mediated RSA cryptography specification November 2011 M message, an octet string of length at most k - 11 Steps: 1. Length checking: If the length of the ciphertext C is not k octets (or if k < 11), output "decryption error" and stop. 2. RSA decryption a. Convert the ciphertext C to an integer ciphertext representative c (see Section 4.2. ): c = OS2IP(C) b. Convert the transformed ciphertext Cp to an integer ciphertext representative cp (see Section 4.2. ): cp = OS2IP(Cp) c. Apply the MRSAA_U_DP decryption primitive (section 5.2.2. )to the RSA private key Ku and transformed ciphertext representative cp and original ciphertext c to produce an integer representative of an encoded message m': m' = MRSAA_U_DP(Ku,cp, c) If MRSAA_U_DP outputs "ciphertext representative out of range" (meaning that cp>=n), output "decryption error" and stop. d. Convert the encoded message representative m' to an encoded message M' of length k octets: M' = I2OSP(m',k) 3. EME-PKCS1-v1_5 decoding message M from string M' Performed on string M' as specified in [RFC3447]. 4. Output M 9. Signature schemes with appendix For the purposes of this document signature schemes with appendix consists of three main operations: signature verification and two complementary operations of signature generation. Signature verification produces a message from signature value using RSA public key, and signature operations creates a signature value from a message value and from the intermediate product, i.e., from a partial signature. The partial signature is created using a user's private key, and final signature value is created using finalization service's private key corresponding to the public key of the user. Two signature schemes are specified in this document: MRSAASA-PSS and MRSAASA-PKCS1-v1_5. Both of them base on an corresponding RSA scheme specified in [RFC3447]. 9.1. MRSAASSA-PSS MRSAASSA-PSS combines MRSAA_U_SP1, MRSAA_F_SP1 and RSAVP1 which is equivalent of MRSAA_VP1 with the EMSA-PSS encoding method. Kutylowski et al. Expires May 14, 2012 [Page 25] Internet-Draft Mediated RSA cryptography specification November 2011 The MRSAA_U_SP1 primitive is identical to the RSASP1 primitive, and thus it is sufficient to implement only RSASP1. The length of messages on which MRSAASSA-PSS can operate is either unrestricted or constrained by a very large number, depending on the hash function underlying the EMSA-PSS encoding method. To make signature verification by the finalization service possible (see remark in Section 5.3. ) we strongly recommend adding at least mHash to the list of arguments passed to the finalization service. Note that according to [RFC3447] (page 37, point 3) the EMSA-PSS encoding is secure even if an adversary can freely choose mHash. Thus to utilize strength of the EMSA-PSS encoding verification must at least comprise verification of encoding correctness. 9.1.1. Signature generation operations MRSAASSA_U_PSS_SIGN (Ku, M) Input: Ku Signer's RSA private key M Message to be signed, an octet string Output: Sp Partial signature, an octet string of length k, where k is the length in octets of the RSA modulus n EM Message encoded using EMSA-PSS-ENCODE primitive (see [RFC3447] paragraph 9.1.1) Errors: "message too long;" "encoding error" Steps: 1. Let EM = EMSA-PSS-ENCODE(M, modBits -1) 2. Convert the encoded message into integer message representative m: m=OS2IP(EM) 3. Apply the RSASP1 signature primitive to the key Ku and Message M: sp = RSASP1(Ku, m) 4. Convert the signature representative sp into partial signature value Sp with the length of k octets. Where k is the length in octets of the RSA modulus n Sp = I2OSP(sp, k) 5. Output Sp, EM Kutylowski et al. Expires May 14, 2012 [Page 26] Internet-Draft Mediated RSA cryptography specification November 2011 MRSASSSA_F_PSS_SIGN (Kf, Sp, EM) Input: Kf Finalization service's RSA private key Sp Partial signature to be transformed into valid signature EM Message encoded using EMSA-PSS-ENCODE primitive (see [RFC3447] paragraph 9.1.1) Output: S signature, an octet string of length k, where k is the length in octets of the RSA modulus n Errors: "message too long;" Assumptions: The Kf key is generated with MRSAA_F_GS-DRBG-GENERATE and corresponds to the public key which will be used to verify the signature S. Steps: 1. RSA signature a. Convert the partial signature Sp to an integer signature representative sp: sp = OS2IP(Sp) b. Convert the pss-encoded message EM to an integer representative m: m = OS2IP(EM) c. Apply the MRSAA_F_SP1 signature primitive (see Section 5.3.2. ) to the RSA private key Kf and the partial signature representative sp to produce a signature representative s: s = MRSAA_F_SP1(Kf, sp, m) d. Convert the signature representative s to a signature S of length k octets (see section 4.1. ): S = I2OSP(s, k) 2. Output the signature S 9.1.2. Signature verification operation There are no differences between MRSASSSA-PSS-VERIFY and RSASSA-PSS- VERIFY operation and thus RSASSA-PSS-VERIFY should be used. The Kutylowski et al. Expires May 14, 2012 [Page 27] Internet-Draft Mediated RSA cryptography specification November 2011 RSASSA-PSS-VERIFY operation has been specified in [RFC3447] section 8.1.2. 9.2. MRSAASSA-PKCS1-v1_5 MRSAASSA-PKCS-v1_5 combines MRSAA_U_SP1, MRSAA_F_SP1 and MRSAA_VP1 with EMSA-PKCS1-v1_5 encoding method. Since MRSAA_U_SP1 is identical to MRSAASP and MRSAA_VP1 is identical to RSAVP1, RSA version of primitives is used in specification. However, as paper [18] indicates, fixed pattern padding method is relatively weak (note that for a fixed hash function PKCS-v1_5 is a fixed pattern encoding). The attack from [18] allows producing valid signatures under a message of attacker's choice (it might be a hash of some meaningful message), if the following conditions are satisfied simultaneously: o hash of the message is longer than one-third of the length of the modulus, o a victim has signed three encoding results without verifying that the values present in the hash-block of encoding are really hashes of some messages. The three values are related with the final signature forged by the adversary. Although the attack seems to be theoretical (the victim must sign three artificial messages to make the adversary able to produce a single meaningful forgery), it exhibits weakness of this encoding method. To mitigate this kind of attacks we recommend to use hashes that are shorter than one-third of the RSA modulus, and to make the finalization service capable of checking that the value present in the hash-block is really a hash of some message. Verification process in the scheme is identical to the RSASSA-PKCS1- v1_5 verification process. The signing process consists of two stages: intermediate signature generation (presignature), which is done in similar way to the RSA scheme, and signature finalization, where MRSAA_F_SP1 primitive is used in combination with EMSA-PKCS1-v1_5 encoding. 9.2.1. Signature generation operations MRSAASSA_U_PKCS1_v1_5_SIGN (Ku, M) Input: Ku Signer's RSA private key Kutylowski et al. Expires May 14, 2012 [Page 28] Internet-Draft Mediated RSA cryptography specification November 2011 M Message to be signed, an octet string Output: Sp Partial signature, an octet string of length k, where k is the length in octets of the RSA modulus n EM Pkcs1-encoded message (see [RFC3447] section 9.2) Errors: "message too long"; "RSA modulus too short" Assumptions: The Kf key is generated with MRSAA_F_GS-DRBG-GENERATE and corresponds to the public key which will be used to verify the signature S. Steps: 1. Let EM = EMSA-PKCS1-V1_5-ENCODE (M, k) 2. Convert EM value into message representative m: m = OS2IP(EM) 3. Apply RSASP1 signature primitive to the key Ku and message m to obtain partial signature value Sp: Sp = RSASP1(Ku,m) 4. Output Sp, EM MRSAA_F_PKCS1_v1_5_SIGN (Kf, Sp, EM) Input: Kf Finalization service's RSA private key Sp Partial signature to be transformed into valid signature EM Pkcs1-encoded message (see [RFC3447] section 9.2) Output: S signature, an octet string of length k, where k is the length in octets of the RSA modulus n Errors: "message too long;" Steps: 1. RSA signature a. Convert the partial signature Sp to an integer signature representative sp: Kutylowski et al. Expires May 14, 2012 [Page 29] Internet-Draft Mediated RSA cryptography specification November 2011 sp = OS2IP(Sp) b. Convert the encoded message EM to an integer representative m: m = OS2IP(EM) c. Apply the MRSAA_F_SP1 signature primitive (see section 5.3.2. ) to the RSA private key Kf, the partial signature representative sp and message representative m to produce a signature representative s: s = MRSAA_F_SP1(Kf, sp, m) d. Convert the signature representative s to a signature S of length k octets (see section 4.1. ): S = I2OSP (s, k) 2. Output the signature S 9.2.2. Signature verification operation There are no differences between MRSAASSA-PKCS1-v1_5-VERIFY and RSASSA- PKCS1-v1_5-VERIFY operation and thus RSA version should be used. RSASSA-PKCS1-v1_5-VERIFY operation has been specified in [RFC3447] section 8.2.2. 10. Encoding method for signatures with appendix The encoding methods specified in [RFC3447] in section 9. should be used. 11. Security Considerations Formal proof of security of two-party RSA signatures in the random oracle model is given in the paper [8]. The proof applies both to multiplicative and to additive private exponent splitting. However, the paper [8] assumes that the key material is securely generated, distributed and stored. It does not investigate for example side channel or fault injection attacks into parts of the system involved in generation, distribution of keys and replacement of old key material. Some issues of designing, implementing and maintaining a secure system that is demonstrably trustworthy are depicted for example in papers [9], [10]. Obviously, building such a system is not a trivial task, and many factors have to be taken into consideration. Kutylowski et al. Expires May 14, 2012 [Page 30] Internet-Draft Mediated RSA cryptography specification November 2011 The following sections contain an analysis of those factors and give recommendations, what kind of controls could be taken into consideration when building such a system. The subsequent sections identify the assets which should be protected and describe security considerations which should be taken into account. Security considerations are identified for particular processes such as: key generation, signature generation etc. 11.1. Identification of assets and actors The main advantage of the MRSAA scheme over the RSA scheme is the private exponent fragmentation. This allows the trusted third party to confirm user's right to perform MRSAA operation. To achieve this functionality neither user nor finalization service knows a base RSA key. This can be achieved using distributed key generation techniques (see for example [11]), or by outsourcing key generation to a trusted third party. Alternatively, to facilitate implementation the base key may exist on one component for a short period of lifecycle of the keys in a secure environment and must be destroyed immediately afterwards. After the introduction of the key generation trusted third party, the MRSAA key generation algorithm actors list is as follows: o User's device - uses user's MRSAA key o Finalization service - uses finalization service's MRSAA key o Key generation service - generates base RSA key In the MRSA algorithm the following assets can be identified: o Fm - master key used in finalization service's exponent (df) derivation o df - finalization service's MRSAA private exponent derived from Fm and Uid o du - user's MRSAA private exponent o d - base RSA private exponent o Uid - user identifier used in derivation of df For the MRSAA algorithm the following threats can be identified: o Fm key's privacy violation - disclosure of the Fm key allows an attacker to generate finalization private exponent df on the basis of the Uid's. The attacker is able to create his own finalization service. Kutylowski et al. Expires May 14, 2012 [Page 31] Internet-Draft Mediated RSA cryptography specification November 2011 o df privacy violation - disclosure of the df exponent allows an attacker to act as an finalizations service in a relation to a specific user that holds a complementary Ku key. o du privacy violation - a disclosure of the du exponent allows an attacker to sign in behalf of the key owner. To produce such a signature, the attacker has to use finalization service to complete a signature. In the case of an encryption scheme the attacker has to obtain a partially deciphered message from finalization service. o d exponent's privacy violation - a disclosure of the base RSA key allows an attacker to make all operations, either signature and decryption, without participation of the user and finalization service o Uid's privacy violation - revealing Uid does not affect the MRSAA algorithm security. 11.2. Key generation security Generation of keys referring to a particular user includes three main steps: o Generation of user's base RSA key; o Generation of finalization service's key Kf (the key is complementary to the user's key Ku); the procedure is usually executed anew for each signature finalization and for each partial decryption operation referring to the user; o Generation of the user's private key Ku MRSAA keys are distributed among parties. The security of the MRSAA algorithm bases on fact that neither user nor finalization service knows user's base RSA key (K). Security of the generation process is critical because on this stage the base key K with private exponent d is generated. In this stage the exponent du, and hence the exponent df needed for this task, are calculated as well. We can distinguish at least five approaches to the key generation process: o Key generation by a separate yet distributed key generation service o Key generation by a separate, centralized key generation service Kutylowski et al. Expires May 14, 2012 [Page 32] Internet-Draft Mediated RSA cryptography specification November 2011 o Generation of the RSA key directly by the user and the finalization service with a two-party protocol o Generation of the RSA keys on user's device o Key generation directly by the finalization service 11.2.1. Key generation by a separate yet distributed service. The key generation model described in addresses the threat of disclosing the base RSA key and finalization exponent df by a single protocol participant. Distributed key generation protocols enjoys the following property: compromise of a single party does not lead to disclosure of the private key. This is achieved by representing some intermediate values of the protocol and the final private key as a set of shares, and each party knows only a single share of each shared value and of the final key. Only having collected some subset of shares of a value an adversary is able to reconstruct the value. The same refers to the private key. The cardinality of the subset must be greater than some threshold. Usually the threshold equals \floor((k-1)/2), where k is the number of parties generating the key, in the two-party schemes the threshold is obviously set to one. However, distributed protocols suffer from some drawback: total communication volume grows rapidly with the number of participants k, thus the protocols do not scale well and are useful only for relatively small values of k. Distributed protocols assume that point-to-point communication lines between parties are secured (i.e., are encrypted and authenticated). To refer to distributed RSA-key generation, many such protocols exist in the literature. Some of them consider two-party setting [24], [25], [26], whereas other use techniques requiring at least three participants of the protocol - see e.g., [27], [28], [11]. Suppose that RSA key-pair (n,e), d was generated by k parties: P_1, P_2, ..., P_k, and the private exponent d (an integer d such that d*e \equiv 1 \lambda(n)) is represented as sum of integers: d = d_1 + d_2 + ... + d_k, where party P_i knows only the component d_i. Let df be split by the finalization service to the following sum of integers: df = df_1 + df_2 + ... + df_k Next, df_i is sent over a secure channel to party P_i. Then P_i calculates integer value d_i - df_i and sends the result over a secure channel to the device of user u. Finally, user u obtains integer Kutylowski et al. Expires May 14, 2012 [Page 33] Internet-Draft Mediated RSA cryptography specification November 2011 du = (d_1 - df_1) + ... + (d_k - df_k) which equals d - df. The distributed key generation is exposed to the eavesdropping. For example, an adversary who is able to get access to all of the df_i fragments is able to recover a df exponent. Access to all fragments of the d exponent gives a possibility to recreate the original d exponent. Therefore, to secure distributed key generation mechanism the following security measures may be taken into account: o Authenticating all parties involved in communication o Encrypting communication channels between parties with session keys that are secret and unique for each communicating pair. 11.2.2. Key generation by the a separate, centralized service In this case a single party, i.e., the key generation service, has a control over the base key K. Moreover, it is necessary to involve this party into generation of the user's private exponent du. On the other hand generation of the finalization service's private exponent df should be performed by a finalization service in order to not disclose finalization service's master key Fm to other parties. Note that key Fm (and thus exponent df) is independent of the values of generated RSA (public (n,e), private d) key-pairs. Exponent df depends only on the length of the RSA modulus. To secure key generation process the following requirements should be fulfilled: o Fm key should be protected by a finalization service, the key must not be disclosed to the other parties o df exponent should be generated in a secure environment by a finalization service; the key should be transferred to a key generation service in encrypted form o du exponent should be generated in a secure manner by a key generation service; the exponent du should be transferred to the user in a encrypted form; o K key should be generated in a secure environment by a key generation service; the key should not be transferred to other parties; private part d of the key should be destroyed immediately after du private exponent generation. Kutylowski et al. Expires May 14, 2012 [Page 34] Internet-Draft Mediated RSA cryptography specification November 2011 A centralized approach to the key generation problem gives an opportunity to use many security techniques to protect privacy and availability of assets. To protect privacy the following controls may be used: o Hardware security modules o Strong authentication and authorization between components o Smart cards for protection of user's key du o Encryption of messages passed between the key generation module and the user's device To achieve high availability of the key generation environment the duplication of the Fm key on multiple devices may be considered as long as full control over usage of Fm is maintained. However, duplication of Fm rises a risk of the key being compromised. In the described model a single party knows the complete RSA key K ((n,e), d). However, one might prevent the party from learning how the private exponent is divided between the finalization service and the user's device. In such case the following method may be used. Let the finalization services express the positive integer df as a sum of two pseudorandom integers df_1+df_2, where both values have roughly the same length. Then df_1 might be encrypted by finalization service with the public key to (a device of) the user. We suppose that at the time of signature key generation there is some public key assigned to the device of the user (e.g., it might be the key used for the device authentication), and that this public key might also be used for encryption purposes. Then the finalization service signs the pair (ciphertext of df_1, Uid) and both the signed pair and df_2 are sent to the key generation service. The key generation service calculates a multiple of \lambda(n) such that the sum of the multiple and d is greater than df_2. Next the service subtracts df_2 from the sum result, and passes this subtraction result (we denote it by df_2') to the user's device. Also the pair (ciphertext of df_1, Uid) and key generation service's signature under it is passed to the user's device. We assume that all messages are sent through a secure and authenticated channel. The user's device checks Uid, the signature of the key generation service, and decrypts df_1. Finally the device calculates the integer du=df_2' - df_1. Below we shall justify some requirements concerning the channel between user's device and the finalization service. Note that pre- signature m^{du} mod n, together with the finalized signature m^d mod n both represent the DLP (discrete logarithm problem) in the multiplicative group of ring Zn: Kutylowski et al. Expires May 14, 2012 [Page 35] Internet-Draft Mediated RSA cryptography specification November 2011 Knowing m^d mod n one might easily obtain m. Consequently, to learn du from m^{du} mod n it suffices to solve the DLP problem in the ring Zn. Knowing factorization of n the (staff of the) key generation service might transform this problem to an equivalent pair of DLP problems: one modulo p, the other modulo q. However, comparing known attacks on factorization problem and on the DLP defined in prime fields it is obvious that these two resulting DLP problems are much easier to solve than factoring n by an external observer (n is about two times longer than each of its factors p, q). Therefore, to prevent the (staff of the) key generation service from learning du by attacking the DLP problem we advise not only authenticate, but also to encrypt the channel between the user's device and the finalization service. If the channel between the device and the finalization service is not authenticated then, having exponent du, the adversary might submit pre-signatures that shall be correctly finalized and assigned to the owner of the public key (e,n). Both in the distributed and the centralized version of the RSA key generation service one should take into account possibility of kleptographic attacks [29]. To prevent them one might verify a fraction of randomly chosen keys being generated regarding randomness used. Some methods of randomness verification are presented in the papers [9], [10]. Another option is to use a deterministic signature scheme as a tool to generate seeds for a pseudo-random number generator [16]. Such seeds are unpredictable, but easily verifiable in respect to correctness. Another issue concerns the finalization service. The issue is possibility of subliminal leakage made by finalization service's manufacturer by utilizing the relation d \equiv df + du mod \lambda(n). Note that d must be odd and \lambda(n) is even, hence manipulating parity bit of df the finalization service chooses parity bit of du. If the channel between the user's device and finalization service is not encrypted, then parity of du might be easily determined by testing values of Jacobi symbol calculated by user's device on a few pre-signatures. Suppose that the finalization service is given master key Fm and the aim of the attack prepared by finalization service's manufacturer is to leak a ciphertext of Fm say AES CFB-mode ciphertext (AES encryption key might be chosen in advance by the producer). Let the infected device divide the AES ciphertext into say 48-bit blocks and let each block be loaded as an initial state of some LFSR (Linear Feedback Shift Register) secretly implemented inside finalization's service HSM. Suppose the upper limit L on the number of ciphertext's blocks is correctly estimated by service's malicious producer. Let hash of Uid indicates both the index of LFSR and the index of the bit on that LFSR's output, and let parity bit of du be value of the bit indicated by hash of Uid. LFSRs might be prepared in such a way that each of them produces Kutylowski et al. Expires May 14, 2012 [Page 36] Internet-Draft Mediated RSA cryptography specification November 2011 pseudorandom sequence of period 2^{48}-1, hence indicated bits are sparsely distributed in LFSR's period and we expect that there would be no bit-repetition. Accordingly, outside the system parity bits of exponents du seem to be not correlated. On the other hand, stealing some number of users' devices the producer collects different bits in the sequence produced by each LFSR, that is the producer collects linear equations with unknowns being the initial state's bits. Having collected 48 independent equations for each LFSR the HSM producer calculates values of initial state of each LFSR. In such a way all blocks of the ciphertext are collected. If output of user's device is encrypted, a powerful adversary might try to bypass encryption (cf. instruction nulling with laser beam [30] in case of smart cards). We do not exclude possibility of mounting such a sophisticated attack against key Fm. Therefore, to prevent such an attack we recommend to fix the parity bit of values df generated in the system, or to generate exponent df in a verifiable manner, for example from seeds being signatures. 11.2.3. Key generation executed directly by the user's device and the finalization service with a two-party protocol This is a special case of distributed RSA key generation limited to two protocol participants [26],[24]. If executed properly (i.e., parties are curious but honest), it prevents each single participant from learning the private key. Such a solution eliminates the need of having a separate key generation service. On the other hand, a distributed protocol imposes heavy communication and computational burden on user's device and (cumulatively) on the central server. Moreover, if a more robust version of the protocol is considered (i.e., one that prevents parties from cheating - cf. e.g., sect. 6 of [25]) the imposed burden is even greater. Designing robust and efficient solution well-tailored to capabilities of constrained parties seems still to be a challenge. 11.2.4. Key generation on user's device In this model functionalities related to the key generation service are implemented by a user device. It should be noticed that to successfully generate user's exponent du, the user's device need to know the df exponent. The df exponent can be transmitted during key generation process or stored securely on the device production phase. In this model the user's exponent du and the base key K are not revealed to the finalization service. The disadvantage of this model is that at some stage of the protocol the user's device knows the df exponent and the base key K, which gives it a possibility to create signatures without participation of the finalization service. This Kutylowski et al. Expires May 14, 2012 [Page 37] Internet-Draft Mediated RSA cryptography specification November 2011 exposes the user to attacks performed by a malicious device producer. To increase security level of this model the following requirements should be taken into consideration: o Securely store encryption of exponent df key on user's device before the key K is generated by the device. Decryption key Kdf for this ciphertext should be sent to the device after revealing the public RSA key by the device. In this way even a malicious device cannot adjust the key generated to the given exponent df. Note that one round of communication after generation of the RSA key is always required in this model in order to obtain a certificate. Note also that the decryption key Kdf does not have to be sent over a secure channel provided that the ciphertext of df is placed on the user's device in a secure environment. o Completely erase df and K from user's device immediately after the key Ku is generated. It should be noticed that all mentioned controls are based on the trust to manufacturer of the user's device. In particular the user must trust that no kleptographic channel is implemented on the device (cf. [12]). Note however that if the RSA key is generated directly on a user's device, then particular attention should be given to quality of randomness. This refers also to signature generation process for non-deterministic signature schemes (cf. RSA-PSS with random salt). 11.2.5. Key generation directly by the finalization service. This model does not employ a third party generating keys. All steps related to the key generation are performed by the finalization service. In such case a finalization service has all necessary information needed to forge user's signatures. All threats specific key generation by a separate centralized service (Section 11.2.1. , but since finalization service should be publicly available for signatures finalization, the risk of interception of the finalization service by an adversary becomes significantly bigger. Moreover, because the key generation procedure is cumulated into the server that permanently is contacted by users' devices and might be heavily loaded with new connections, the process controlling quality of keys generated might be somewhat cumbersome. Further, theoretically, one might develop a malicious implementation, which might generate false signatures of some user on a request of an adversary (we suppose that the malicious implementation knows how to recover user's complete RSA key because this implementation has generated the key). Kutylowski et al. Expires May 14, 2012 [Page 38] Internet-Draft Mediated RSA cryptography specification November 2011 Therefore, the key generation performed directly by the finalization service could be considered only in environments with low security requirements. 11.3. Replacement of a finalization service Probability of a successful attack on the finalization service's key depends on strength of cryptographic algorithm used, strength of the used key, implementation, security policies executed during system lifetime and other issues. Even in implementations that are supposed to be secure there is a danger of extracting the Fm key by utilizing some new attack, which was not taken into account when the system was designed (cf. e.g., [31],[32],[33]). To minimize consequences of such situation and to additionally facilitate load balancing it is possible to use multiple finalizations services with different Fm keys. If a few finalization services operate at the same time, with corresponding master keys Fm_1, Fm_2, ..,Fm_t, then if one of the keys (say Fm_2) becomes compromised it is possible to replace it with a new one, and then gradually change users' public keys (immediate change of all public keys in a large system might be infeasible). Suppose that user's device holds exponents du_1, du_2, ..., du_t referring to the same public key (n,e) or holds some subset of these exponents. Each du_i corresponds to df_i produced from key Fm_i, and the following condition is satisfied: du_i + df_i = d_i, where d_i is some integer such that d_i*e \equiv 1 mod \lambda(n), that is, d_i \equiv d mod \lambda(n). If say Fm_2 becomes compromised, exponent du_2 should be erased from the user's device. To introduce a new finalization server with a new master key Fm_2' the following, exemplary procedure might be applied: Generate df_j (for some j\neq 2) on the server holding Fm_j and split df_j pseudorandomly to the sum of two integers of roughly the same length: df_j = df_j1+df_j2. Next the server holding Fm_j sends df_j2 to the server holding Fm_2'. The latter server generates df_2' from user's Uid and key Fm_2' and subtracts the value generated from the value received: df_j2-df_2'. The resulting value is encrypted with the public encryption key corresponding to Uid (see remarks in Sect. 11.2.2. on preventing the key generation service from learning df). Next the pair (the ciphertext, Uid) is signed by the server holding Fm_2', and this pair and the signature is sent to the server holding Fm_j. The latter server sends df_j1 and the data received from the server holding Fm_2' to the user's device over a secure channel. Kutylowski et al. Expires May 14, 2012 [Page 39] Internet-Draft Mediated RSA cryptography specification November 2011 The user's device checks the signature, decrypts the ciphertext and adds du_j to the sum of values: df_j1+(df_j2-df_2') = df_j-df_2'. As a result value d_j - df_2' \equiv d - df_2' mod \lambda(n) is obtained. User's device defines du_2' as d_j - df_2'. When du_2' is calculated all intermediate data should be immediately erased from the user's device. The procedure above might be initialized at the time of finalization of some signature - this should reduce communication overhead from user's point of view. Apart from key Fm the finalization server should also hold some authentication key pair and its short-term certificate. Thus in case of detection that Fm could be compromised such an additional security mechanisms should prevent signature finalization outside the legitimate finalization service. There is some limitation of the technique described above. If Fm_j becomes compromised later, then security of df_2' depends on inaccessibility of df_j - df_2' outside the user's device. If such inaccessibility might be questionable, then we recommend to gradually replace users' public keys. 11.4. Signature creation process security The signing process consists of two parts: o Creating a partial signature o Finalizing a signature The partial signature creation is performed by a user. The final signature is created by a finalization service. The user key Ku is stored by the user. The key Kf is derived by a finalization service on a basis of the user specific identifier Uid and finalization service's master key Fm. To create a final signature there is a need to establish a communication channel between the user and the finalization service. It should be noticed that in the case of the interception of a user's private exponent du it is easy to make the exponent useless. The adversary has to access to the finalization service to create a valid signature. The access to the finalization service can be blocked for a specific exponent. The mediated signature scheme has another advantage: in the case of dispute, the finalization service is able to present the evidence of the signature creation. The finalization service's logs might even have a public form of undeniable timestamps [19] made automatically by the finalization service. Kutylowski et al. Expires May 14, 2012 [Page 40] Internet-Draft Mediated RSA cryptography specification November 2011 Note that the not-mediated RSA variant usually does not satisfy this property: user's certificate revocation does not prevent the adversary from making signatures with the stolen key. It is possible to achieve comparable level of functionality with timestamped signature with a mandatory signature policy. However, it should be noticed that signature verification applications must be adjusted accordingly. Since in MRSAA scheme user's device does not know the factorization of the modulus, the Bellcore attack [20] aimed to injecting faults modulo one of the factors of n, does not apply. Even more general attacks [21], [22] on implementation not utilizing knowledge about modulus factorization (i.e., CRT) do not apply directly because nobody knows public exponent eu such that eu * du \equiv 1 mod \lambda(n). Even user's device should not know such eu (note that knowledge of both eu and du, provided eu*du < n^2, is polynomially equivalent to the knowledge of factors of n - cf. [23]). Moreover, there is a very efficient probabilistic algorithm that, given eu and du, factors n. The algorithm does not impose constraints on eu*du. However, in MRSAA scheme the device of the user is not the only component involved in signature generation. Suppose that the channel between user's device and the finalization service is not encrypted, and that the finalization service does not verify the final signature. Let m, sp' be integers representing some encoded message and its faulty partial signature correspondingly. Let sp' be faulty because of a single-bit fault that occurred during this partial signature generation (cf. assumptions in [21], [22], concerning faults generated). Since m and sp' are sent to the finalization service, and m^{df} * sp' mod n is returned to the device of the user, it is easy for the adversary to obtain m^{df} mod n from the data eavesdropped. If exponentiation method used on the side of the device is the method attacked in [21] or the method attacked in [22], then having m and m^{df} mod n the adversary might modify the original attack from [21] or [22] to obtain exponent du. Hence to prevent an adversary from learning du by utilizing some fault injection attack we recommend to verify the final signature by the finalization service. Verification should include verification of encoding correctness. The signature creation in MRSAA scheme gives also a possibility to perform the following attack: suppose that the finalization service does not check if given modulus n corresponds to the argument Uid Kutylowski et al. Expires May 14, 2012 [Page 41] Internet-Draft Mediated RSA cryptography specification November 2011 (e.g., Uid is not included in the certificate of the key (n,e) nor Uid includes hash of (n,e)). Suppose that public keys are not stored by the finalization service's device (e.g., a HSM). Let the adversary might input all necessary data to the finalization service's device and let the device does not verify the finalized signature nor check message encoding correctness. Instead of modulus n the adversary will use modulus n' such that n'> n, let factorization of n' is known to the adversary, and for each prime factor p of n' number p-1 is smooth. In such a case having m^{df} mod n' the adversary is able to compute df mod \lambda(n') using Pohling-Hellman method modulo each prime factor of n'. Details of the attack are as follows: Let the adversary input to the finalization service some tuple (m,sp,n'), where m, sp are some integers. The finalization service outputs sp*m^{df} mod n'. Knowing sp the adversary calculates m^{df} mod n' and then df mod \lambda(n'). If \lambda(n') is too short to recover df completely, the adversary might repeat the procedure for another, appropriately chosen n''. As a result df mod lcm(\lambda(n'),\lambda(n'')) is found by the adversary. The attack above might be modified in such a way that df leaks even if the finalization service verifies the signature (but does not check encoding correctness) - in this case we assume that if signature verification fails finalization service does not return any value modulo n'. The modification proceeds as follows: modulus n' will again be chosen in a way that the multiplicative group of Z_{n'} will have smooth order and that some other conditions are satisfied, namely: let prime p be divisor of n' and let p' be a prime factor of p-1 such that df is not divisible by p'. Let (p')^t be the greatest power of p' dividing p-1, and let for each prime factor q of n' either (p')^t be the greatest power of p' dividing q-1 or p' do not divide q-1. Let sp, m belong to the multiplicative group Z_{n'}^{*} of the ring Z_{n'} and are chosen in such a way that: sp is the neutral element in each cyclic subgroup of the order (p')^t, and in other subgroups of Z_{n'}^{*} it might be any element. Kutylowski et al. Expires May 14, 2012 [Page 42] Internet-Draft Mediated RSA cryptography specification November 2011 m is the neutral element of each cyclic subgroup of the order not divisible by p', and it is a generator of each subgroup of the order (p')^t. Such m modulo Z_{n'} might be easily found using generators of the multiplicative groups Z_{p}^{*}, Z_{q}^{*} and then utilizing the Chinese Remainder Theorem. Then the adversary will test some set of exponents e being co-prime with p', such that the set of tested exponents is not greater than the complete set of elements of the multiplicative group Z_{(p')^t}^{*}. Let each tested exponent e fulfill the following condition: for each prime factor q of n' and for each prime factor q' of q-1, if q' is different from p', then e is divisible by the greatest power of q' dividing q-1. During each test the adversary inputs tuple (m, sp, (n', e)) to the finalization service. If no value modulo n' is returned by the finalization service, then the adversary tries the next exponent e giving not tested yet element of Z_{(p')^t}^{*}. Values m, sp do not have to be changed for the next trial. If df is indeed not divisible by p', then for some e the condition (sp * m^{df})^e \equiv m mod n' is satisfied, and the finalization service returns sp*m^{df} mod n'. The adversary knows that for this e the congruence df * e \equiv 1 mod (p')^t holds, hence df mod (p')^t is found. If no value is returned and all residues from Z_{(p')^t}^{*} were tested as exponents e, then df \equiv 0 mod p'. Executing the attack for different primes p' the adversary finally finds complete exponent df. We have assumed that m does not represent correct message encoding, because finding m, n' fulfilling the conditions above and m representing correct encoding might be computationally hard for appropriate encoding. If (m, sp, (n',e)) must be delivered over user's device, then security of df depends on security of the authentication key. Therefore, to provide some security margin we recommend checking during finalization all the following conditions: o Does m represent correct encoding? o Do (n,e) and Uid correspond to each other? o Does Uid correspond the authentication key of the user's device? Kutylowski et al. Expires May 14, 2012 [Page 43] Internet-Draft Mediated RSA cryptography specification November 2011 o Is the finalized value a correct signature? Additionally, to protect a signature process the following requirements should be fulfilled: o du exponent should be stored securely by the user; the exponent shouldn't be revealed to other parties; o df exponent should be derived from the key Fm in a secure environment by the finalization service; the df exponent should be destroyed immediately after the completion of the signature process; o the channel between the user's device and the finalization service should be encrypted. 11.5. Decryption process security The decryption process in MRSAA algorithm consists of the following stages: o transformation of the ciphertext by the finalization service, o decryption of the ciphertext by the user. To perform a decryption it is necessary to transfer a transformed ciphertext to the user's device. The device must check correctness of encoding of the encrypted value. To protect a decryption process the following requirements should be fulfilled: o df exponent should be derived in a secure environment by the finalization service; the exponent should be destroyed immediately after the completion of the transformation process; o (n, e) and df must correspond to the same Uid; o du exponent should be stored securely by the user; the exponent must not be relayed to other parties. To provide some security margin we recommend encrypting the channel between the user's device and the finalization service. 11.6. Short summary of possible security techniques To sum up this section we can briefly enumerate exemplary countermeasures to the threats listed in subsection 11.1. (in the Kutylowski et al. Expires May 14, 2012 [Page 44] Internet-Draft Mediated RSA cryptography specification November 2011 previous subsections we have analyzed need of some of the countermeasures in more detail): o log service, which works in an append-only way, and which is audited by a third party, o mutual authentication protocol such like chip authentication and terminal authentication protocols (cf. e.g., [4])resulting in secure and authenticated connection between the finalization service and user's device (in particular, such a connection must be inaccessible for operators of the RSA key generation server). o internal (nested) signature carried by salt in EMSA-PSS encoding, o external timestamp and signature applied automatically by the finalization service, o evolution of unique secrets shared between users and the finalization service as a simple clone-detection mechanism, o hiding exponent df from the RSA key generation service which can be realized by the finalization service in the following way: the finalization service expresses df as a sum of two integers df_1 + df_2 and then encrypts df_1 to the user, and next sends df_2 instead of df to the key generation service; getting du from the key generation service the user must only subtract df_1 from du to obtain the correct value. Most of the techniques listed above are described in [15]. The general goal is system decomposition by utilizing existing or introducing additional security layers (cf. chip and terminal authentication procedures), and by assigning to separate parties the task of generating key material used in separate layers. Moreover, a prudent approach is to require that the parties generating key material have only "local" knowledge on the system that is to require that they are provided with minimum data necessary to accomplish their task. Accordingly, we advise to separate information flow by utilizing encryption. 12. IANA Considerations Kutylowski et al. Expires May 14, 2012 [Page 45] Internet-Draft Mediated RSA cryptography specification November 2011 13. Conclusions The main difference between a MRSAA and a RSA algorithm is related to the signing key. In the MRSAA algorithm the key is divided into two fragments. This fact gives a possibility to transfer a final step of signature creation to a finalization service [6]. Incorporating a third party into the signature process allows confirming the signature at the creation time. In such a case the signature which can be successfully verified using a public key can be considered as a confirmed one. The confirmation process can consist of verification of multiple signature attributes (see [7]), particularly a signer's certificate validity check (cf. [13]). The signature with certificate validity verified on the signature creation stage can be considered as a trusted one without additional verification of certificate validity. In conclusion, MRSAA protects relying party from rogue signer. 14. References 14.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax Specifications: ABNF", RFC 5234, January 2008. [3] E. Barkley, J. Kelsey, "NIST SP800-90 Recommendation for Random Number Generation using Deterministic Random Bit Generators", NIST, March 2007 [4] Bundesamt fur Sicherheit in der Informationstechnik: Technical Guideline TR-03110, Advanced Security Mechanisms for Machine Readable Travel Documents Version 2.05 14.2. Informative References [5] D. Coppersmith, M. Franklin, J. Patarin and M. Reiter. Low- Exponent RSA with Related Messages. In Advances in Cryptology- Eurocrypt '96, pp. 1-9, Springer-Verlag, 1996 Kutylowski et al. Expires May 14, 2012 [Page 46] Internet-Draft Mediated RSA cryptography specification November 2011 [RFC3447] J. Jonsson, B. Kaliski, "Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1 [6] D. Boneh X. Ding, G. Tsudik and Ch. M. Wong, "A method for Fast Revocation of Public Key Certificates and Security Capabilities", USENIX Association, 2001 [7] M. Tabor, "Electronic signature - easy as card transactions", Polskie Karty 2011 almanach. Medien Service Slawomir Cieslinski,2010 [8] M. Bellare, R. Sandhu, "The Security of Practical Two-Party RSA Signature Schemes", Cryptology ePrint Archive, Report 2001/060 [9] E. Konstantinou, V. Liagkou, P. G. Spirakis, Y. C. Stamatiou, M. Yung, "Trust Engineering: " From Requirements to System Design and Maintenance - A Working National Lottery System Experience", ISC, 2005 [10] E. Konstantinou, V. Liagkou, P. G. Spirakis, Y. C. Stamatiou, M. Yung, "Electronic National Lotteries.", Financial Cryptography, 2004 [11] I. Damgard, G. L. Mikkelsen, "Efficient, Robust and Constant- Round Distributed RSA Key Generation", TCC, 2010 [12] A. Young, M. Young, "A Space Efficient Backdoor in RSA and Its Applications", Selected Areas in Cryptography, 2005 [13] D. Boneh, X. Ding, G. Tsudik, "Fine-grained control of security capabilities", ACM Trans. Internet Techn.,4(1) 2004 [14] P. Paillier, "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes", EUROCRYPT, 1999 [15] P. Blaskiewicz, P. Kubiak, M Kutylowski, "Digital signatures for e-government - a long-term security architecture", China Communications 7(6),December 2010 [16] D. Chaum: Secret-Ballot Receipts: True Voter-Verifiable Elections. IEEE Security & Privacy 2(1): 38-47 (2004) [17] A. Bauer, J.-S. Coron, D. Naccache, M. Tibouchi, D. Vergnaud, "On the Broadcast and Validity-Checking Security of pkcs#1 v1.5 Encryption", ACNS, 2010 [18] A. K. Lenstra, I. Shparlinski, "Selective Forgery of RSA Signatures with Fixed-Pattern Padding", Public Key Cryptography, 2002 Kutylowski et al. Expires May 14, 2012 [Page 47] Internet-Draft Mediated RSA cryptography specification November 2011 [19] S. Haber, W. S. Stornetta, "How to Time-Stamp a Digital Document", J. Cryptology, 1991 [20] D. Boneh, R. A. DeMillo, R. J. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract)", EUROCRYPT, 1997 [21] A. Pellegrini, V. Bertacco, T. M. Austin, "Fault-based attack of RSA authentication", DATE 2010, 2010 [22] D. Boneh, R. A. DeMillo, R. J. Lipton, "On the Importance of Eliminating Errors in Cryptographic Computations", J. Cryptology 14, 2001 [23] J. Coron, A. May, "Deterministic Polynomial-Time Equivalence of Computing the RSA Secret Key and Factoring", J. Cryptology 20, 2007 [24] C. Cocks, "Split Knowledge Generation of RSA Parameters", IMA Int. Conf., 1997 [25] M. Joye, R. Pinch, "Cheating in split-knowledge RSA parameter generation", Workshop on Coding and Cryptography, January 1999 [26] N. Gilboa, "Two Party RSA Key Generation", CRYPTO, 1999 [27] J. Algesheimer, J. Camenisch, V. Shoup, "Efficient Computation Modulo a Shared Secret with Application to the Generation of Shared Safe-Prime Products", CRYPTO, 2002 [28] E. Ong, J. Kubiatowicz, "Optimizing Robustness While Generating Shared Secret Safe Primes", Public Key Cryptography, 2005 [29] A. Young, M. Yung, "A Space Efficient Backdoor in RSA and Its Applications", Selected Areas in Cryptography, 2005 [30] G. Barbu, H. Thiebeauld, V. Guerin, "Attacks on Java Card 3.0 Combining Fault and Logical Attacks", CARDIS, 2010 [31] O. Aciicmez, C. K. Koc, J.-P. Seifert, "On the Power of Simple Branch Prediction Analysis",Cryptology ePrint Archive: Report 2006/351 [32] D. Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. CRYPTO 1998: 1- 12 [33] E. Biham, Y. Carmeli, A. Shamir: Bug Attacks. CRYPTO 2008: 221-240 Kutylowski et al. Expires May 14, 2012 [Page 48] Internet-Draft Mediated RSA cryptography specification November 2011 15. Acknowledgments This document was prepared using 2-Word-v2.0.template.dot. Kutylowski et al. Expires May 14, 2012 [Page 49] Internet-Draft Mediated RSA cryptography specification November 2011 Appendix A. Pseudorandom generator primitives Primitives described below are described in details in [3]. This annex describes only inputs and outputs for these primitives. A.1. CTR_DRBG_Instantiate_algorithm(entropy_input, personalization_string) Input: entropy_input the string of bits obtained from the source of entropy input personalization_ the personalization string received from the string consuming application Output: initial_working_ The initial values for V, Key, and state reseed_counter A.2. CTR_DRBG_Generate_algorithm(working_state, requested_number_of_bits, additional_input) Input: working_state The current values for V, Key and reseed_counter requested_numbe The number of pseudorandom bits to be returned r_of_bits to the generate function additional_inpu The additional input string received from the t consuming application. If additional_input is not supported by an implementation, then step 2 becomes: additional_input = 0^seedlen Output: status The status returned from the function. The status will indicate SUCCESS, or indicate that a reseed is required before the requested pseudorandom bits can be generated. returned_bits The pseudorandom bits returned to the generate function working_state The new values for V, Key and reseed_counter Kutylowski et al. Expires May 14, 2012 [Page 50] Internet-Draft Mediated RSA cryptography specification November 2011 Appendix B. Standard RSA primitives Appendix contains a list of primitives with short description. Detailed specification of primitives can be found in [RFC3447] document. A.3. Encryption and decryption primitives RSAEP transforms cleartext into ciphertext. RSADP performs a reverse operation. A.3.1. RSAEP((n,e),m) Input: (n,e) RSA public key m message representative, an integer between 0, and n-1 Output: c Ciphertext representative, an integer between 0 and n-1 or message "message representative out of range" A.3.2. RSADP(K,c) Input: K RSA private key, where K has one of the following forms - A pair (n,d) - A quintuple(p,q,dP,dQ,qInv) c Ciphertext representative, an integer between 0 and n-1 Output: m message representative, an integer between 0, and n-1 or message "ciphertext representative out of range" In the present document RSADP was used for key K=Kf and key K=Ku', thus the first form of a private key representation has been utilized. Kutylowski et al. Expires May 14, 2012 [Page 51] Internet-Draft Mediated RSA cryptography specification November 2011 A.4. Signature and verification primitives RSASP1 produces signature value from message. RSAVP1 retrieves a message value from signature value. A.4.1. RSASP1(K,m) Input: K RSA private key, where K has one of the following forms - A pair (n,d) - A quintuple(p,q,dP,dQ,qInv) c message representative, an integer between 0 and n-1 Output: m signature representative, an integer between 0, and n-1 or message "message representative out of range" In the present document RSASP1 was used for key K=Ku and key K=Fm. In the first case the first form of a private key representation has been utilized. A.4.2. RSAVP1((n,e),s) Input: (n,e) RSA public key s signature representative, an integer between 0 and n-1 Output: m message representative, an integer between 0, and n-1 or message "invalid" Kutylowski et al. Expires May 14, 2012 [Page 52] Internet-Draft Mediated RSA cryptography specification November 2011 Appendix C. ASN.1 Syntax A.5. MRSAA key representation This section defines ASN.1 object identifiers for MRSA public and private keys. It does not define new types, but shows how to use RSA data types with MRSA scheme. A.5.1. MRSAA public key syntax The RSA public key syntax is identical to a RSA public key syntax. The RSAPublicKey type should be used to represent MRSAA public key. A.5.2. MRSAA private key syntax MRSAA private key should be represented with ASN.1 type RSAPrivateKey according to [RFC3447] section A.1.2: RSAPrivateKey ::= SEQUENCE { version Version, modulus INTEGER, -- n publicExponent INTEGER, -- e privateExponent INTEGER, -- d prime1 INTEGER, -- p prime2 INTEGER, -- q exponent1 INTEGER, -- d mod (p-1) exponent2 INTEGER, -- d mod (q-1) coefficient INTEGER, -- (inverse of q) mod p otherPrimeInfos OtherPrimeInfos OPTIONAL } MRSAA private key, either Ku or Kf, should not contain information which give a possibility to recover d private exponent which corresponds to the public exponent. This implies that the key cannot contain original p and q, d mod (p-1), d mod (q-1), qInv values. For the purposes of storing finalization service's key Kf or user's key Ku, RSAPrivateKey structure's fields have the following meaning: o version is the version number, for compatibility with future revisions of this document. It shall be 0 for this version of the document, unless multi-prime is used, in which case it shall be 1. In the case of MRSAA version number 2 should be used Version ::= INTEGER { two-prime(0), multi(1) } (CONSTRAINED BY {-- version must be multi if otherPrimeInfos present --}) o modulus is the RSA modulus n o publicExponent is the MRSAA public exponent e Kutylowski et al. Expires May 14, 2012 [Page 53] Internet-Draft Mediated RSA cryptography specification November 2011 o privateExponent is the MRSAA private exponent (df or du respectively) Other fields should be set to value 0 A.5.3. Scheme identification The section defines object identifiers for the MRSAA encryption schemes. For signature schemes RSA object identifiers should be used as defined in [RFC3447] section A.2. Here are the type identifier definitions for the MRSAA OIDs: mrsa OBJECT-IDENTIFIER ::= { iso(1) identified-organization(3) dod(6) internet(1) private(4) enterprise(1) 37722 applications(1) 1} } mrsaEncryption OBJECT-IDENTIFIER ::= { applications(1) mrsa(1) algorithms(1) 1} Id-MRSAES-OAEP OBJECT-IDENTIFIER ::= { applications(1) mrsa(1) algorithms(1) 2} Kutylowski et al. Expires May 14, 2012 [Page 54] Internet-Draft Mediated RSA cryptography specification November 2011 Appendix D. ASN.1 Module MRSAA { iso(1) identified-organization(3) dod(6) internet(1) private(4) enterprise(1) 37722 applications(1) 1 } DEFINITIONS EXPLICIT TAGS ::= BEGIN EXPORTS ALL; IMPORTS ALGORITHM-IDENTIFIER, PKCS1Algorithms FROM PKCS-1 { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) 1 } ; MRSAAAlgorithms ALGORITHM-IDENTIFIER ::= { { OID mrsaaEncryption PARAMETERS NULL } | { OID id-MRSAAES-OAEP PARAMETERS RSA-OAEP-params } | PKCS1Algorithms, ... } mrsaa OBJECT IDENTIFIER ::= { iso(1) identified-organization(3) dod(6) internet(1) private(4) enterprise(1) 37722 applications(1) 1 } -- -- When rsaEncryption is used in an AlgorithmIdentifier the -- parameters MUST be present and MUST be NULL. -- mrsaaEncryption OBJECT IDENTIFIER ::= { mrsaa algorithms(1) 1} -- -- When id-MRSAAES-OAEP is used in an AlgorithmIdentifier the -- parameters MUST be present and MUST be RSAES-OAEP-params. -- id-MRSAAES-OAEP OBJECT IDENTIFIER ::= { mrsa algorithms(1) 2} END Kutylowski et al. Expires May 14, 2012 [Page 55] Internet-Draft Mediated RSA cryptography specification November 2011 Appendix E. Intellectual Property Considerations The RSA public-key cryptosystem is described in U.S. Patent 4,405,829, which expired on September 20, 2000. RSA Security Inc. For this moment there are no active patents related to the RSA algorithm. The Mediated RSA cryptographic method and system is described in U.S.patent 20,040,252,830, which will expire on June 2024. The patent describes a mediated RSA cryptosystem with the key fragmented using additive scheme. Additionally the messages passed between a finalization service (Trusted Authority) and message receiver are blinded using random number. However the schema described in this document differs from the one described in the patent, some similarities such like user exponent du can be found. A U.S. patent 20 050 002 528 describes mediated signature system with identifier based key generation. The concept described in the patent is similar to the one described in this document, but the key generation method is different than presented in this document. Additionally, during a message transmission a random blinding is incorporated. Authors' Addresses Miroslaw Kutylowski Wroclaw University of Technology Wybrzeze Wyspianskiego 27 PL-50-370 Wroclaw Email: miroslaw.kutylowski@pwr.wroc.pl Kutylowski et al. Expires May 14, 2012 [Page 56] Internet-Draft Mediated RSA cryptography specification November 2011 Przemyslaw Kubiak Wroclaw University of Technology Wybrzeze Wyspianskiego 27 PL-50-370 Wroclaw Email: przemyslaw.kubiak@pwr.wroc.pl Michal Tabor Trusted Information Consulting Domaniewska 41A PL-02-672 Warszawa Email: michal.tabor@ticons.pl Daniel Wachnik Trusted Information Consulting Domaniewska 41A PL-02-672 Warszwawa Email: daniel.wachnik@ticons.pl Kutylowski et al. Expires May 14, 2012 [Page 57] Internet-Draft Mediated RSA cryptography specification November 2011 Full copyright statement Copyright (c) 2011 IETF Trust and the persons identified as authors of the code. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: o Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. o Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. o Neither the name of Internet Society, IETF or IETF Trust, nor the names of specific contributors, may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Kutylowski et al. Expires May 14, 2012 [Page 58]