Received-SPF: pass (google.com: domain of linux-crypto-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Thu, 07 Jul 2022 19:29:11 +0200
From:   Harald Freudenberger <freude@linux.ibm.com>
To:     Ignat Korchagin <ignat@cloudflare.com>
Cc:     Herbert Xu <herbert@gondor.apana.org.au>,
        "David S . Miller" <davem@davemloft.net>,
        linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org,
        kernel-team@cloudflare.com, kernel test robot <lkp@intel.com>,
        egorenar@linux.ibm.com, jchrist@linux.ibm.com
Subject: Re: [PATCH v2] crypto: rsa - implement Chinese Remainder Theorem for
 faster private key operations
Reply-To: freude@linux.ibm.com
In-Reply-To: <20220617084210.907-1-ignat@cloudflare.com>
References: <20220617084210.907-1-ignat@cloudflare.com>
User-Agent: Roundcube Webmail/1.4.13
Message-ID: <87a675dc70199baf013b417c55275ee1@linux.ibm.com>
Content-Type: text/plain; charset=US-ASCII;
 format=flowed
Content-Transfer-Encoding: 7bit
MIME-Version: 1.0
Precedence: bulk

On 2022-06-17 10:42, Ignat Korchagin wrote:
> Changes from v1:
>   * exported mpi_sub and mpi_mul, otherwise the build fails when RSA is 
> a module
> 
> The kernel RSA ASN.1 private key parser already supports only private 
> keys with
> additional values to be used with the Chinese Remainder Theorem [1], 
> but these
> values are currently not used.
> 
> This rudimentary CRT implementation speeds up RSA private key 
> operations for the
> following Go benchmark up to ~3x.
> 
> This implementation also tries to minimise the allocation of additional 
> MPIs,
> so existing MPIs are reused as much as possible (hence the variable 
> names are a
> bit weird).
> 
> The benchmark used:
> 
> ```
> package keyring_test
> 
> import (
> 	"crypto"
> 	"crypto/rand"
> 	"crypto/rsa"
> 	"crypto/x509"
> 	"io"
> 	"syscall"
> 	"testing"
> 	"unsafe"
> )
> 
> type KeySerial int32
> type Keyring int32
> 
> const (
> 	KEY_SPEC_PROCESS_KEYRING Keyring = -2
> 	KEYCTL_PKEY_SIGN                 = 27
> )
> 
> var (
> 	keyTypeAsym = []byte("asymmetric\x00")
> 	sha256pkcs1 = []byte("enc=pkcs1 hash=sha256\x00")
> )
> 
> func (keyring Keyring) LoadAsym(desc string, payload []byte)
> (KeySerial, error) {
> 	cdesc := []byte(desc + "\x00")
> 	serial, _, errno := syscall.Syscall6(syscall.SYS_ADD_KEY,
> uintptr(unsafe.Pointer(&keyTypeAsym[0])),
> uintptr(unsafe.Pointer(&cdesc[0])),
> uintptr(unsafe.Pointer(&payload[0])), uintptr(len(payload)),
> uintptr(keyring), uintptr(0))
> 	if errno == 0 {
> 		return KeySerial(serial), nil
> 	}
> 
> 	return KeySerial(serial), errno
> }
> 
> type pkeyParams struct {
> 	key_id         KeySerial
> 	in_len         uint32
> 	out_or_in2_len uint32
> 	__spare        [7]uint32
> }
> 
> // the output signature buffer is an input parameter here, because we 
> want to
> // avoid Go buffer allocation leaking into our benchmarks
> func (key KeySerial) Sign(info, digest, out []byte) error {
> 	var params pkeyParams
> 	params.key_id = key
> 	params.in_len = uint32(len(digest))
> 	params.out_or_in2_len = uint32(len(out))
> 
> 	_, _, errno := syscall.Syscall6(syscall.SYS_KEYCTL, KEYCTL_PKEY_SIGN,
> uintptr(unsafe.Pointer(&params)), uintptr(unsafe.Pointer(&info[0])),
> uintptr(unsafe.Pointer(&digest[0])), uintptr(unsafe.Pointer(&out[0])),
> uintptr(0))
> 	if errno == 0 {
> 		return nil
> 	}
> 
> 	return errno
> }
> 
> func BenchmarkSign(b *testing.B) {
> 	priv, err := rsa.GenerateKey(rand.Reader, 2048)
> 	if err != nil {
> 		b.Fatalf("failed to generate private key: %v", err)
> 	}
> 
> 	pkcs8, err := x509.MarshalPKCS8PrivateKey(priv)
> 	if err != nil {
> 		b.Fatalf("failed to serialize the private key to PKCS8 blob: %v", 
> err)
> 	}
> 
> 	serial, err := KEY_SPEC_PROCESS_KEYRING.LoadAsym("test rsa key", 
> pkcs8)
> 	if err != nil {
> 		b.Fatalf("failed to load the private key into the keyring: %v", err)
> 	}
> 
> 	b.Logf("loaded test rsa key: %v", serial)
> 
> 	digest := make([]byte, 32)
> 	_, err = io.ReadFull(rand.Reader, digest)
> 	if err != nil {
> 		b.Fatalf("failed to generate a random digest: %v", err)
> 	}
> 
> 	sig := make([]byte, 256)
> 	for n := 0; n < b.N; n++ {
> 		err = serial.Sign(sha256pkcs1, digest, sig)
> 		if err != nil {
> 			b.Fatalf("failed to sign the digest: %v", err)
> 		}
> 	}
> 
> 	err = rsa.VerifyPKCS1v15(&priv.PublicKey, crypto.SHA256, digest, sig)
> 	if err != nil {
> 		b.Fatalf("failed to verify the signature: %v", err)
> 	}
> }
> ```
> 
> [1]:
> https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm
> 
> Signed-off-by: Ignat Korchagin <ignat@cloudflare.com>
> Reported-by: kernel test robot <lkp@intel.com>
> ---
>  crypto/rsa.c      | 78 ++++++++++++++++++++++++++++++++++++++++++++---
>  lib/mpi/mpi-add.c |  2 +-
>  lib/mpi/mpi-mul.c |  1 +
>  3 files changed, 75 insertions(+), 6 deletions(-)
> 
> diff --git a/crypto/rsa.c b/crypto/rsa.c
> index 39e04176b04b..0e555ee4addb 100644
> --- a/crypto/rsa.c
> +++ b/crypto/rsa.c
> @@ -17,6 +17,11 @@ struct rsa_mpi_key {
>  	MPI n;
>  	MPI e;
>  	MPI d;
> +	MPI p;
> +	MPI q;
> +	MPI dp;
> +	MPI dq;
> +	MPI qinv;
>  };
> 
>  /*
> @@ -35,16 +40,49 @@ static int _rsa_enc(const struct rsa_mpi_key *key,
> MPI c, MPI m)
> 
>  /*
>   * RSADP function [RFC3447 sec 5.1.2]
> - * m = c^d mod n;
> + * m_1 = c^dP mod p;
> + * m_2 = c^dQ mod q;
> + * h = (m_1 - m_2) * qInv mod p;
> + * m = m_2 + q * h;
>   */
> -static int _rsa_dec(const struct rsa_mpi_key *key, MPI m, MPI c)
> +static int _rsa_dec_crt(const struct rsa_mpi_key *key, MPI 
> m_or_m1_or_h, MPI c)
>  {
> +	MPI m2, m12_or_qh;
> +	int ret = -ENOMEM;
> +
>  	/* (1) Validate 0 <= c < n */
>  	if (mpi_cmp_ui(c, 0) < 0 || mpi_cmp(c, key->n) >= 0)
>  		return -EINVAL;
> 
> -	/* (2) m = c^d mod n */
> -	return mpi_powm(m, c, key->d, key->n);
> +	m2 = mpi_alloc(0);
> +	m12_or_qh = mpi_alloc(0);
> +	if (!m2 || !m12_or_qh)
> +		goto err_free_mpi;
> +
> +	/* (2i) m_1 = c^dP mod p */
> +	ret = mpi_powm(m_or_m1_or_h, c, key->dp, key->p);
> +	if (ret)
> +		goto err_free_mpi;
> +
> +	/* (2i) m_2 = c^dQ mod q */
> +	ret = mpi_powm(m2, c, key->dq, key->q);
> +	if (ret)
> +		goto err_free_mpi;
> +
> +	/* (2iii) h = (m_1 - m_2) * qInv mod p */
> +	mpi_sub(m12_or_qh, m_or_m1_or_h, m2);
> +	mpi_mulm(m_or_m1_or_h, m12_or_qh, key->qinv, key->p);
> +
> +	/* (2iv) m = m_2 + q * h */
> +	mpi_mul(m12_or_qh, key->q, m_or_m1_or_h);
> +	mpi_addm(m_or_m1_or_h, m2, m12_or_qh, key->n);
> +
> +	ret = 0;
> +
> +err_free_mpi:
> +	mpi_free(m12_or_qh);
> +	mpi_free(m2);
> +	return ret;
>  }
> 
>  static inline struct rsa_mpi_key *rsa_get_key(struct crypto_akcipher 
> *tfm)
> @@ -112,7 +150,7 @@ static int rsa_dec(struct akcipher_request *req)
>  	if (!c)
>  		goto err_free_m;
> 
> -	ret = _rsa_dec(pkey, m, c);
> +	ret = _rsa_dec_crt(pkey, m, c);
>  	if (ret)
>  		goto err_free_c;
> 
> @@ -134,9 +172,19 @@ static void rsa_free_mpi_key(struct rsa_mpi_key 
> *key)
>  	mpi_free(key->d);
>  	mpi_free(key->e);
>  	mpi_free(key->n);
> +	mpi_free(key->p);
> +	mpi_free(key->q);
> +	mpi_free(key->dp);
> +	mpi_free(key->dq);
> +	mpi_free(key->qinv);
>  	key->d = NULL;
>  	key->e = NULL;
>  	key->n = NULL;
> +	key->p = NULL;
> +	key->q = NULL;
> +	key->dp = NULL;
> +	key->dq = NULL;
> +	key->qinv = NULL;
>  }
> 
>  static int rsa_check_key_length(unsigned int len)
> @@ -217,6 +265,26 @@ static int rsa_set_priv_key(struct
> crypto_akcipher *tfm, const void *key,
>  	if (!mpi_key->n)
>  		goto err;
> 
> +	mpi_key->p = mpi_read_raw_data(raw_key.p, raw_key.p_sz);
> +	if (!mpi_key->p)
> +		goto err;
> +
> +	mpi_key->q = mpi_read_raw_data(raw_key.q, raw_key.q_sz);
> +	if (!mpi_key->q)
> +		goto err;
> +
> +	mpi_key->dp = mpi_read_raw_data(raw_key.dp, raw_key.dp_sz);
> +	if (!mpi_key->dp)
> +		goto err;
> +
> +	mpi_key->dq = mpi_read_raw_data(raw_key.dq, raw_key.dq_sz);
> +	if (!mpi_key->dq)
> +		goto err;
> +
> +	mpi_key->qinv = mpi_read_raw_data(raw_key.qinv, raw_key.qinv_sz);
> +	if (!mpi_key->qinv)
> +		goto err;
> +
>  	if (rsa_check_key_length(mpi_get_size(mpi_key->n) << 3)) {
>  		rsa_free_mpi_key(mpi_key);
>  		return -EINVAL;
> diff --git a/lib/mpi/mpi-add.c b/lib/mpi/mpi-add.c
> index 2cdae54c1bd0..9056fc5167fc 100644
> --- a/lib/mpi/mpi-add.c
> +++ b/lib/mpi/mpi-add.c
> @@ -138,7 +138,7 @@ void mpi_sub(MPI w, MPI u, MPI v)
>  	mpi_add(w, u, vv);
>  	mpi_free(vv);
>  }
> -
> +EXPORT_SYMBOL_GPL(mpi_sub);
> 
>  void mpi_addm(MPI w, MPI u, MPI v, MPI m)
>  {
> diff --git a/lib/mpi/mpi-mul.c b/lib/mpi/mpi-mul.c
> index 8f5fa200f297..7f4eda8560dc 100644
> --- a/lib/mpi/mpi-mul.c
> +++ b/lib/mpi/mpi-mul.c
> @@ -82,6 +82,7 @@ void mpi_mul(MPI w, MPI u, MPI v)
>  	if (tmp_limb)
>  		mpi_free_limb_space(tmp_limb);
>  }
> +EXPORT_SYMBOL_GPL(mpi_mul);
> 
>  void mpi_mulm(MPI w, MPI u, MPI v, MPI m)
>  {
> --
> 2.36.1

Hello Ignat
on s390 the linux-next kernel gives me this during startup:

Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: akcipher: decrypt test 
failed. err -22
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: akcipher: test 1 failed 
for rsa-generic, err=-22
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ------------[ cut here 
]------------
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: self-tests for 
rsa-generic (rsa) failed (rc=-22)
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: WARNING: CPU: 6 PID: 111 at 
crypto/testmgr.c:5773 alg_test+0x348/0x4d0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Modules linked in:
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: CPU: 6 PID: 111 Comm: 
cryptomgr_test Not tainted 5.19.0-rc5-next-20220706 #1
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Hardware name: IBM 8561 T01 
703 (LPAR)
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl PSW : 0704d00180000000 
00000000f8b15ab4 (alg_test+0x34c/0x4d0)
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:            R:0 T:1 IO:1 EX:1 
Key:0 M:1 W:0 P:0 AS:3 CC:1 PM:0 RI:0 EA:3
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl GPRS: c0000000fffeffff 
0000000080000000 0000000000000035 0000000000000000
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:            0000000000000001 
0000000000000001 000000008da15c80 000000000000000d
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:            000000008da15c00 
00000000ffffffff 00000380000000b6 ffffffffffffffea
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:            000000008cd53200 
00000000fb19dfd0 00000000f8b15ab0 0000038004847cf8
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl Code: 00000000f8b15aa4: 
c02000523738        larl        %r2,00000000f955c914
                                                      00000000f8b15aaa: 
c0e5002d52a7        brasl        %r14,00000000f90bfff8
                                                     #00000000f8b15ab0: 
af000000                mc        0,0
                                                     >00000000f8b15ab4: 
b904002b                lgr        %r2,%r11
                                                      00000000f8b15ab8: 
eb6ff1300004        lmg        %r6,%r15,304(%r15)
                                                      00000000f8b15abe: 
07fe                bcr        15,%r14
                                                      00000000f8b15ac0: 
47000700                bc        0,1792
                                                      00000000f8b15ac4: 
1829                lr        %r2,%r9
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Call Trace:
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:  [<00000000f8b15ab4>] 
alg_test+0x34c/0x4d0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ([<00000000f8b15ab0>] 
alg_test+0x348/0x4d0)
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:  [<00000000f8b13b98>] 
cryptomgr_test+0x68/0x70
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:  [<00000000f83b4be8>] 
kthread+0x138/0x150
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:  [<00000000f832f91c>] 
__ret_from_fork+0x3c/0x58
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:  [<00000000f90ecf6a>] 
ret_from_fork+0xa/0x40
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: no locks held by 
cryptomgr_test/111.
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Last Breaking-Event-Address:
Jul 07 11:50:28 t35lp54.lnxne.boe kernel:  [<00000000f90c005e>] 
__warn_printk+0x66/0x70
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: irq event stamp: 729
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: hardirqs last  enabled at 
(737): [<00000000f841f3b4>] __up_console_sem+0x8c/0xc0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: hardirqs last disabled at 
(744): [<00000000f841f396>] __up_console_sem+0x6e/0xc0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: softirqs last  enabled at (0): 
[<00000000f837d6da>] copy_process+0x7fa/0x17d0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: softirqs last disabled at (0): 
[<0000000000000000>] 0x0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ---[ end trace 
0000000000000000 ]---

I tracked this down with git bisect to exactly your patch.
Looks like the testmanager needs an update also ... maybe use CRT 
formated keys instead of ME keys ?!?

regards
Harald Freudenberger