Provable Secure Signatures with RSA

Provable Secure Signatures with RSA

PSS: Probabilistic Signature Scheme

After 45 years, RSA is still going strong and basically secures the Internet. Every time you connect to a Web site, there is a signature method there that proves the identity of the Web site you are connecting to. While some — such as Cloudflare use ECC — the majority still use RSA. Here is the Edinburgh Napier University public key, and which uses a 2,048-bit RSA modulus:

At the core of this, is the RSA signature. Basically, the site shows a trusted public key to the client, and will digitally sign some data with its private key. If the signature proves to be valid with the public key, the site can be trusted. In this case, Alice signs the hash of a message with her private key, and Bob checks with her public key:

But which one should you use? RSA-PKCS#1.5, RSA-OAEP or RSA-PSS?

First, let’s get the acronyms out of the way. With PKCS, we have Public-Key Cryptography Standards, and which are standards that were defined by RSA Labs. With PSS, we have Probabilistic Signature Scheme, and OAEP is Optimal Asymmetric Encryption Padding.

The PKCS standards are one of the foundation elements of the Internet and were drafted by RSA Labs. In one of the original specifications for RSA, we saw it defined in PKCS#1:

It contained the methods of PKCS#1.5 and OAEP:

Basically, we have since found that PKCS#1.5 is open to a range of attacks [2] and that the OAEP method was more secure. No one should ever code with PKCS#1.5 in a production environment these days. Then, in 2003, the PKCS#1 standard was upgraded with Version 2.1:

Its main addition was RSA-PSS, and which is based on a paper by Bellare & Rogaway [3]:

It should be noted that OAEP is based on other work by Bellare and Rogaway [1].

RSA — The Rock of Trust

The RSA method is still around and is still used fairly extensively in digital signing — in fact it is the default signing method used with JSON Web Tokens. Also, most of the digital certificates that are used on the Internet still use RSA as their signing method. So while Bitcoin and Ethereum have dumped RSA in favour of ECDSA (and based on ECC — Elliptic Curve Cryptography), RSA is often used in many applications, including with OpenSSL authentication.

RSA signing can be seen as the opposite of the encryption process, and where we operate on a hash of the message. In RSA, we have a modulus (N) which is based on two prime numbers (p and q):

N=p.q

We then have a public exponent (e- the verifier) and a private exponent (d — the signer). Initially, we hash the message (msg):

h=hash(msg)

Then, we use the private exponent to determine the signature:

s=h^d (mod N))

To verify we take the public exponent and make sure that:

hash(msg)==s^e (mod N)

Unfortunately, pure RSA signing is open to a number of attacks, and which can be overcome using either RSA-OEAP or RSA-PSS.

PKCS#v1.5 Should Never Been Seen!

The simplest way to pad the input data to RSA is to use PKCS#v1.5. With this, we pad to the start of the message bytes, and where the first two bytes are 0x00 and 0x02, and followed by a number of non-zero bytes. We then add a 0x00 byte to identify the end of the padding and then followed by the message bytes:

0x00 0x02 [some non-zero bytes ] 0x00 [message bytes]

When unpadding, the 0x00, 0x02 sequence is detected, and then we search for the 0x00 byte and take remove all of the preceding bytes. Unfortunately, Daniel Bleichenbacher published a paper [2] that showed how the PKCS#v1.5 padding method could be cracked with a chosen cipher attack: [2]:

The Bleichenbacker’s attack has been continually compromising some systems for decades, but TLS 1.3 now overcomes it by dropping support for PKCS#v1.5. To overcome the weaknesses of PKCS#v1.5, we can either use OAEP (Optimal Asymmetric Encryption Padding) or PSS (Probabilistic Signature Scheme) methods to add padding which can be removed later.

Optimal Asymmetric Encryption Padding (OAEP)

So, our solution is to use padding, and one of the most popular methods is Optimal Asymmetric Encryption Padding (OAEP). The method was first published by Bellare and Rogaway as [here][1]:

It has since been standardized in PKCS#1 v2 and RFC 2437 [here]:

Overall we operate on n bits at a time, and where n is the number of bits in the modulus (Figure 1). This is based on a Feistel network, and where if we EX-OR sometime with the same value twice, we end up with the original value.

With this - as illustrated in Figure 1 - we have two fixed values of k0 and k1. k1 defines the number of zeros to pad onto the message, and k0 defines the number of bits in a random number (r). The number of bits we are processing in the message is thus n−k0−k1 bits. We then have two hashing functions of G and H. The G function expands the k0 bits of r into n−k0 bits, and which is EX-OR with the padded message. This produces X. Next, we take the value and feed it into H, and which hashes the bits to produce k0 bits. This is then EX-OR (⊕) with r to produce Y (and which has k0 bits).

We now have X and Y for our padding (Mp=X||Y), and where the total number of bits will be n. This can then be operated on with a (mod N) operation. The values of X and Y can now go into our cipher for:

C=Mp^e (mod N)

and then decrypted with:

P=C^d (mod N)

We can now strip off the padding. To recover the message we first recover the random value (r) from:

r=Y⊕H(X)

and then with r we recover the padded message:

m00…0=X⊕G(r)

We then strip off k1 zeros from the end of this message and recover M.

PSS (Probabilistic Signature Scheme)

Four years after the OEAP paper, Bellare and Rogaway produced their PSS paper [3]:

As we have seen PKCS#v1.5 is weak in its padding, and suffers from many weaknesses:

• It is deterministic. With this, we do not have a random element that changes the signature when we sign for the same data.
• The hashed value can be extracted from the signature. An intruder can extract the hash from the signature and reveal the hashed value. While this does not reveal the original message, an intruder could eventually match it to a given message.
• It has no formal security proof.

RSA-PSS overcomes these weaknesses. It uses randomized signatures for the same message — and is thus probabilistic rather than deterministic. For this, we have a random salt value which is added to the signature process. It also stops the message hash from being extracted from the signature. Along with this, it has a formal security proof of its security.

As with OAEP, it uses a mask generation function (MGF) and which is pseudorandom. This produces a non-deterministic output signature. With this, we use a salt value to produce the random signature, and where this salt value can be extracted from the signature (or contained in the signature).

The padding method is fully defined in RFC 2447:

Notice that the end part of the encoding is “0xbc”. This hex value defines the trailer to the encoded data.

Coding

The outline code is [here]:

package main
import (
 "crypto/rsa"
 "crypto/rand"
 "crypto"
 "crypto/sha256"
 "fmt"
 "os"
 "strconv"

)

func main() {
 input_string := "This is a test"
 size:=1024
 argCount := len(os.Args[1:])
 if argCount > 0 {
  input_string = string(os.Args[1])
 }
 if argCount > 1 {
  size,_ = strconv.Atoi(os.Args[2])
 }
 private_key, _ := rsa.GenerateKey(rand.Reader, size)
 public_key := &private_key.PublicKey

 message := []byte(input_string)

 hashed := sha256.Sum256(message)
 signature, _ := rsa.SignPSS(rand.Reader, private_key, crypto.SHA256, hashed[:],nil)
 verify:=  rsa.VerifyPSS(public_key, crypto.SHA256, hashed[:], signature,nil)
 fmt.Printf("\nInput message: [%s]", input_string)
 fmt.Printf("\nMessage hash (SHA-256): [%x]", hashed[:])
 fmt.Printf("\nKey size: [%d]",size)
 fmt.Printf("\n\nPrivate key:\nd=%x\nN=%x\n", private_key.D,private_key.N)
 fmt.Printf("\nPublic key:\ne=%x\nN=%x\n", public_key.E,public_key.N)
  fmt.Printf("\n\nSignature: %x\n",signature)
 if (verify==nil) {
  fmt.Printf("\nRSA signature verified")
 }
}

A sample run for a 1,024 bit modulus:

Input message: [Test]
Message hash (SHA-256): [532eaabd9574880dbf76b9b8cc00832c20a6ec113d682299550d7a6e0f345e25]
Key size: [1024]
Private key:
d=a2efc66b10b433ab1f77e6a4e5b28d0fafbc990550f60c775c4236c247609d3b1c4fc8bd435da38ad58a68aabb0813367a07b549de3d62fc567cc2fea404ae6f1e59e1480de932f6e519070138b4b5774627831446eed808bbf9287f6d9132e6f14df10191cba49599992572667803dd78c6424531c02f6e1330b4b4e951db61
N=a73bd7c664654a46a17a9f41c9d973536a2f5e29f7e40db37bafb735f5e263f2ced08a088209cd597c61f63ae8fc824b2129311f85c3a67927faf0349095dba874981e44cfa63aa96264c3b14a03a4a0201a46ca422623a0a497b41d1a5d0f0535ae1814de3d2c464f58c42218f61180a8132260a6739fb72e0e3acdc464398b
Public key:
e=10001
N=a73bd7c664654a46a17a9f41c9d973536a2f5e29f7e40db37bafb735f5e263f2ced08a088209cd597c61f63ae8fc824b2129311f85c3a67927faf0349095dba874981e44cfa63aa96264c3b14a03a4a0201a46ca422623a0a497b41d1a5d0f0535ae1814de3d2c464f58c42218f61180a8132260a6739fb72e0e3acdc464398b

Signature: 0449096ac1871dcd322effa068360e972960b0ce37339b21c181d4ed60a4c3cfe4fb871655d379bfcf7c4c7727899272c1a4bc0af8a2962a469827b21d382cdab7df518537c502203fad30532be53d4c46d2712b27f1bb4af206f3291f1250560b8e51229d70c784f2c5af019de7b1e903572d1f2d430979f47def19066b7b03
RSA signature verified

If you count the number of hex characters in the modulus (N), you see that we have 256 characters. Two hex characters make one byte, thus we have 128 bytes, and which is 1,024 bits. This will be created from two 512-bit prime numbers. For a 2,048-bit modulus:

Input message: [Test]
Message hash (SHA-256): [532eaabd9574880dbf76b9b8cc00832c20a6ec113d682299550d7a6e0f345e25]
Key size: [2048]
Private key:
d=8c6c07d4a2bef77fd588b632acab992fdef7a134eb1c0861c64d832e7308e073cac66fbc9e91830fd4add9c52c1351abe41c801fc834315b9fa2f597da9076216f17b2b44dc0d4118adb3da4cf510cf6ed50438202c30372e79942c57b581f39c017b6037c2761d9d5a5b1681195b2f4ca097fcb68f026cf7b0e0cd5a7e398c474aae6695c67d11a81c9f35236dd40467e3beb16a9aaceda4e682b71228b5cd3a0c7802b8d4c28a65bbca81b304f0e7d03ee38374331f365d2ef647a2e1925e97deb907be0d347a43f266c59d37c745f110312efd43d87d76cfb63499ed2fce6f37f6c0441daa7664037e5c12beca1420b07db159ac7559ca380bf53039ea1c9
N=d42dcda2405e36bb12c13a42042e30c2f7203bc20d2aefa7c9d61d43694c7c17fb7aee14bb0b59114c4f0ed3a1af2f32298ae969e21343324c9d7af79a1acff2e77584eff14c55505a7388cc3386b2a378b0ee8f7369dbda98f3f19d5687f7efccd2efc81b36f4cc79d81548417a8760b702121a0e99845e5460592b889daa75aaf2b083c8e0d40b22ed2e09a6f099566b2b8793d2b5e9bfa8aa2d89ed8c587ab381569c0109f216a9692cf1d307ba7d2c03cd5e862734687436557554188d46147563178af05871225224a57ea40dadca488672556620507e441fcc59f0da6976298fd4cf76f37db85e1bf289dfc9ef36cb7e887a0c54b6715dd17f03b2e47b
Public key:
e=10001
N=d42dcda2405e36bb12c13a42042e30c2f7203bc20d2aefa7c9d61d43694c7c17fb7aee14bb0b59114c4f0ed3a1af2f32298ae969e21343324c9d7af79a1acff2e77584eff14c55505a7388cc3386b2a378b0ee8f7369dbda98f3f19d5687f7efccd2efc81b36f4cc79d81548417a8760b702121a0e99845e5460592b889daa75aaf2b083c8e0d40b22ed2e09a6f099566b2b8793d2b5e9bfa8aa2d89ed8c587ab381569c0109f216a9692cf1d307ba7d2c03cd5e862734687436557554188d46147563178af05871225224a57ea40dadca488672556620507e441fcc59f0da6976298fd4cf76f37db85e1bf289dfc9ef36cb7e887a0c54b6715dd17f03b2e47b

Signature: 78a7675e7032ca93ab5acbe689cf9d1c963bce18514f28401c61a2c15dd909c43e5c1d376c918ab76fa8a403ed4f5097030cbe8e4bf73445f46f1febe7a7577a8e62a9ed347fc39304091ea4a3468cbff725b081b9a3190694fa4295cfdf655803f68e618018c8b46258b57217285fde22be5bc2fe696d785212ded7d3a96af5793aa4ace962f46851b1140e698e5f1314d6c5fa637163df39b024c780047fdba59b512a66d035807cddb0dceb85e0fa7fb94ef39c7ca0a4dfe27f96dfef746402edab909d493a9c0ad88dbbeeb34ce005d4247a6265f471539f084f45d00241d092ad180a620f42fc97a4a32e934e54d1c7b3d19396ce9c8f5299dadc7629d5
RSA signature verified

If you count the number of hex characters in the modulus (N) you see that we have 512 characters. Two hex characters make one byte, thus we have 256 bytes, and which is 2,048 bytes. This will be created from two 1,024-bit prime numbers.

References

[1] Bellare, M., & Rogaway, P. (1994, May). Optimal asymmetric encryption. In Workshop on the Theory and Application of Cryptographic Techniques (pp. 92–111). Springer, Berlin, Heidelberg.

[2] Bleichenbacher, D. (1998, August). Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS# 1. In Annual International Cryptology Conference (pp. 1–12). Springer, Berlin, Heidelberg.

[3] Bellare, M., & Rogaway, P. (1998). PSS: Provably secure encoding method for digital signatures. IEEE P1363a: Provably secure signatures.

Subscribe: https://billatnapier.medium.com/membership