PKCS 1

Last updated

In cryptography, PKCS #1 is the first of a family of standards called Public-Key Cryptography Standards (PKCS), published by RSA Laboratories. It provides the basic definitions of and recommendations for implementing the RSA algorithm for public-key cryptography. It defines the mathematical properties of public and private keys, primitive operations for encryption and signatures, secure cryptographic schemes, and related ASN.1 syntax representations.

Contents

The current version is 2.2 (2012-10-27). Compared to 2.1 (2002-06-14), which was republished as RFC 3447, version 2.2 updates the list of allowed hashing algorithms to align them with FIPS 180-4, therefore adding SHA-224, SHA-512/224 and SHA-512/256.

Keys

The PKCS #1 standard defines the mathematical definitions and properties that RSA public and private keys must have. The traditional key pair is based on a modulus, n, that is the product of two distinct large prime numbers, p and q, such that .

Starting with version 2.1, this definition was generalized to allow for multi-prime keys, where the number of distinct primes may be two or more. When dealing with multi-prime keys, the prime factors are all generally labeled as for some i, such that:

for

As a notational convenience, and .

The RSA public key is represented as the tuple , where the integer e is the public exponent.

The RSA private key may have two representations. The first compact form is the tuple , where d is the private exponent. The second form has at least five terms , or more for multi-prime keys. Although mathematically redundant to the compact form, the additional terms allow for certain computational optimizations when using the key. In particular, the second format allows to derive the public key. [1]

Primitives

The standard defines several basic primitives. The primitive operations provide the fundamental instructions for turning the raw mathematical formulas into computable algorithms.

Schemes

By themselves the primitive operations do not necessarily provide any security. The concept of a cryptographic scheme is to define higher level algorithms or uses of the primitives so they achieve certain security goals.

There are two schemes for encryption and decryption:

There are also two schemes for dealing with signatures:

The two signature schemes make use of separately defined encoding methods:

The signature schemes are actually signatures with appendix, which means that rather than signing some input data directly, a hash function is used first to produce an intermediary representation of the data, and then the result of the hash is signed. This technique is almost always used with RSA because the amount of data that can be directly signed is proportional to the size of the keys; which is almost always much smaller than the amount of data an application may wish to sign.

  1. Note: A small change was made to RSAES-OAEP in PKCS #1 version 2.1, causing RSAES-OAEP in PKCS #1 version 2.0 to be totally incompatible with RSA-OAEP in PKCS #1 version 2.1 and version 2.2.

Version history

Implementations

Below is a list of cryptography libraries that provide support for PKCS#1:

Attacks

Multiple attacks were discovered against PKCS #1 v1.5, specifically its padding scheme. [3] [4]

In 1998, Daniel Bleichenbacher published a seminal paper on what became known as Bleichenbacher's attack (also known as "million message attack"). The attack uses the padding as an oracle. [4] [5] PKCS #1 was subsequently updated in the release 2.0 and patches were issued to users wishing to continue using the old version of the standard. [3] However, the vulnerable padding scheme remains in use and has resulted in subsequent attacks:

In 2006, Bleichenbacher presented a new forgery attack against the signature scheme RSASSA-PKCS1-v1_5. [8] Variants of this attack are reported in 2008 [9] and 2014. [10] This class of attack exploits a flawed implementation of the signature verification; a proper implementation would not be vulnerable. [2]

See also

Related Research Articles

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography to provide equivalent security.

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.

In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm (DSA) is a variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption.

A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption.

Articles related to cryptography include:

An adaptive chosen-ciphertext attack is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a target ciphertext without consulting the oracle on the challenge ciphertext. In an adaptive attack, the attacker is further allowed adaptive queries to be asked after the target is revealed. It is extending the indifferent (non-adaptive) chosen-ciphertext attack (CCA1) where the second stage of adaptive queries is not allowed. Charles Rackoff and Dan Simon defined CCA2 and suggested a system building on the non-adaptive CCA1 definition and system of Moni Naor and Moti Yung.

<span class="mw-page-title-main">Blind signature</span> Form of digital signature

In cryptography a blind signature, as introduced by David Chaum, is a form of digital signature in which the content of a message is disguised (blinded) before it is signed. The resulting blind signature can be publicly verified against the original, unblinded message in the manner of a regular digital signature. Blind signatures are typically employed in privacy-related protocols where the signer and message author are different parties. Examples include cryptographic election systems and digital cash schemes.

In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.

The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.

CRYPTREC is the Cryptography Research and Evaluation Committees set up by the Japanese Government to evaluate and recommend cryptographic techniques for government and industrial use. It is comparable in many respects to the European Union's NESSIE project and to the Advanced Encryption Standard process run by National Institute of Standards and Technology in the U.S.

In cryptography, padding is any of a number of distinct practices which all include adding data to the beginning, middle, or end of a message prior to encryption. In classical cryptography, padding may include adding nonsense phrases to a message to obscure the fact that many messages end in predictable ways, e.g. sincerely yours.

In cryptography, PKCS are a group of public key cryptography standards devised and published by RSA Security LLC, starting in the early 1990s. The company published the standards to promote the use of the cryptography techniques to which they had patents, such as the RSA algorithm, the Schnorr signature algorithm and several others. Though not industry standards, some of the standards have begun to move into the "standards track" processes of relevant standards organizations in recent years, such as the IETF and the PKIX working group.

The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the computational intractability of the Decisional Diffie–Hellman assumption. Developed by Ronald Cramer and Victor Shoup in 1998, it is an extension of the ElGamal cryptosystem. In contrast to ElGamal, which is extremely malleable, Cramer–Shoup adds other elements to ensure non-malleability even against a resourceful attacker. This non-malleability is achieved through the use of a universal one-way hash function and additional computations, resulting in a ciphertext which is twice as large as in ElGamal.

In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway, and subsequently standardized in PKCS#1 v2 and RFC 2437.

IEEE P1363 is an Institute of Electrical and Electronics Engineers (IEEE) standardization project for public-key cryptography. It includes specifications for:

In cryptographic protocols, a key encapsulation mechanism (KEM) or key encapsulation method is used to secure symmetric key material for transmission using asymmetric (public-key) algorithms. It is commonly used in hybrid cryptosystems. In practice, public key systems are clumsy to use in transmitting long messages. Instead they are often used to exchange symmetric keys, which are relatively short. The symmetric key is then used to encrypt the longer message. The traditional approach to sending a symmetric key with public key systems is to first generate a random symmetric key and then encrypt it using the chosen public key algorithm. The recipient then decrypts the public key message to recover the symmetric key. As the symmetric key is generally short, padding is required for full security and proofs of security for padding schemes are often less than complete. KEMs simplify the process by generating a random element in the finite group underlying the public key system and deriving the symmetric key by hashing that element, eliminating the need for padding.

A BLS digital signature—also known as Boneh–Lynn–Shacham (BLS)—is a cryptographic signature scheme which allows a user to verify that a signer is authentic.

In cryptography, a padding oracle attack is an attack which uses the padding validation of a cryptographic message to decrypt the ciphertext. In cryptography, variable-length plaintext messages often have to be padded (expanded) to be compatible with the underlying cryptographic primitive. The attack relies on having a "padding oracle" who freely responds to queries about whether a message is correctly padded or not. The information could be directly given, or leaked through a side-channel.

Coppersmith's attack describes a class of cryptographic attacks on the public-key cryptosystem RSA based on the Coppersmith method. Particular applications of the Coppersmith method for attacking RSA include cases when the public exponent e is small or when partial knowledge of a prime factor of the secret key is available.

Probabilistic Signature Scheme (PSS) is a cryptographic signature scheme designed by Mihir Bellare and Phillip Rogaway.

References

  1. Ilmari Karonen (27 October 2017). "Can I get a public key from an RSA private key?". Stack Exchange .
  2. 1 2 Jager, Tibor; Kakvi, Saqib A.; May, Alexander (15 October 2018). On the Security of the PKCS#1 v1.5 Signature Scheme (PDF). The Second International Conference on Availability, Reliability and Security (ARES'07). pp. 1195–1208. doi:10.1145/3243734.3243798.
  3. 1 2 Jean-Sébastien Coron, Marc Joye, David Naccache, and Pascal Paillier (2000). Advances in Cryptology — EUROCRYPT 2000 (PDF). Lecture Notes in Computer Science. Vol. 1807. EUROCRYPT. pp. 369–381. doi:10.1007/3-540-45539-6. ISBN   978-3-540-67517-4. S2CID   8447520.{{cite book}}: CS1 maint: multiple names: authors list (link)
  4. 1 2 3 Romain Bardou; Riccardo Focardi; Yusuke Kawamoto; Lorenzo Simionato; Graham Steel; Joe-Kai Tsay (2012). Efficient Padding Oracle Attacks on Cryptographic Hardware. Rr-7944 (report). INRIA. p. 19.
  5. RFC   3218 – Preventing the Million Message Attack on Cryptographic Message Syntax
  6. Green, Matthew (21 June 2012). "A bad couple of years for the cryptographic token industry". A Few Thoughts on Cryptographic Engineering.
  7. Hanno Böck; Juraj Somorovsky; Craig Young. "ROBOT attack: Return Of Bleichenbacher's Oracle Threat" . Retrieved February 27, 2018.
  8. Tetsuya Izu; Masahiko Takenaka; Takeshi Shimoyama (April 2007). "Analysis on Bleichenbacher's Forgery Attack". The Second International Conference on Availability, Reliability and Security (ARES'07). IEEE. pp. 1167–1174. doi:10.1109/ARES.2007.38. ISBN   978-0-7695-2775-8. S2CID   2459509.
  9. Kühn, Ulrich; Pyshkin, Andrei; Tews, Erik; Weinmann, Ralf-Philipp (2008): Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures. SICHERHEIT 2008 – Sicherheit, Schutz und Zuverlässigkeit. Beiträge der 4. Jahrestagung des Fachbereichs Sicherheit der Gesellschaft für Informatik e.V. (GI). Bonn: Gesellschaft für Informatik e. V.. PISSN: 1617-5468. ISBN: 978-3-88579-222-2. pp. 97-109. Regular Research Papers. Saarbrücken. 2.- 4. April 2008
  10. "Advanced Threat Research | Intel Security". 1 April 2015. Archived from the original on 2015-04-01.