On Thu, Jul 7, 2022 at 6:29 PM Harald Freudenberger <freude@xxxxxxxxxxxxx> wrote: > > 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(¶ms)), 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@xxxxxxxxxxxxxx> > > Reported-by: kernel test robot <lkp@xxxxxxxxx> > > --- > > 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: Hi Harald, The issue has been reported previously and I've submitted a follow up patch: [1] [1]: https://patchwork.kernel.org/project/linux-crypto/patch/20220704103840.924-1-ignat@xxxxxxxxxxxxxx/ > 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 > > > Regards, Ignat