lkml.org 
[lkml]   [2022]   [Jul]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v2] crypto: rsa - implement Chinese Remainder Theorem for faster private key operations
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



\
 
 \ /
  Last update: 2022-07-07 19:31    [W:0.126 / U:0.020 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site