RSA CRT decryption occasional failure
Closed, InvalidPublic

Description

In some cases, the same cipher message encrypted by gpg cannot be decrypted by gpg.
The output error messages:

gpg: public key decryption failed: Wrong secret key used
gpg: decryption failed: No secret key

This can be reproduced with this private key (password: test).

-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: IPWorks! OpenPGP 2020

xcFGBFKzRJkBBAC8VHK3AT0H6wm76SGOLDBNMnJsY0Rdg9haaHjEetDCxe6bIRZj1JcUx7xYrhDJ
sLWEmGIawrAGLhmuybE9V7aB7r9HHdKpwlcROypcXXkcTDMFuq1TpRtImghCPMo8dOu3DIevlE0F
Lb4/DBB8xZ+0ikxAyZXz6rtJ4eJ9h/VPRwARAQAB/gcDAps6qO0ePvp7xWCkz0iF7tSUVTB5/eUs
zfaRV8HZZoOoBc38ygjM/bChiOtJBtM1LwAne9AzMT2zFiutF1tbOJY1iDlnBRGfKcDu08lYkjK7
9ZcQtnQrkekxTowuJqma/V0KuWoWxDP61fxEQGUsGFFLIYuR0l7cpDsjO3rU23ZXTz0Cs9YDujuD
YdNICzaEIv9cO4l+pT9dv/2ULRrq7DnPuyehBZIzInNwqRf2XSbr+z+OSSo8u9Mk//WHYX9CGODm
6+mQEwbbiYCoL9a1MD+2j2xAaGq3HVZ6HdVKKV67W8jP6ObAy6XAmWHnb4O4YoA+rf4/HFdwqLe7
NmrFHqnyHhBAP2oMbrmE3rVenXYQf7zpYfSglNx1dp2ONSlNHRi9iaQ17tX+eHlogAL1Y3ebCAmS
pHpKXddQ2Ltb9JiT8fdlGyzZ0kwfPHUC7t7uhadK+8ZFlEGZpk20C70Zn/r6ILy1pTdW866CtK1k
O8t+Q+zb9NbNH25zb2Z0d2FyZSA8bnNvZnR3YXJlQGdtYWlsLmNvbT7CwBUEEwECAD8JCwMCCQgH
BAoBCBUCCAkKCwEDBRYBAgMAAh4BAheAAhsPFiEEsjx6kG46XJo5wp1OaYeUvG5zfw0FAl0CGtYA
CgkQaYeUvG5zfw3iPQP+Jzzy4/hUj3/9Xxo7Q91NP5wP6QdVYih5e5vG0QgGWWcOfZz5M5tOFNXJ
gBYDEdSL088+DBThjUipeJ+0Ljx33UDdPfFk3FTStuOytwEWJQkxDqpm9FD5zaPh2M0VfQQNGUi/
Dkv5N9U7YJNmA2KOsQQDvoksAE0EMSX5pZdm3tXHwT4EXQyXbgIEAIOyA+/eDypAqaRbIV4udJ9k
+DrzFBObnrjTd3MkSVRlTj/I93Gyq6oPv2MVgp5IaGfyVEyLRvgrkgFznEmTari/nfG2qxTEjVTT
mTSAMCly2TSHMdDMNmWJcOjqLvTvsVl+FeSxvzeZQtOq9oHU18/tX0Vwne9yHNpZgUPt4OP/ABEB
AAH+AwMCf1jNYpZ8lXpg539fyblG6uRo8eCkcs3Xe8+o+NKrPeAbJCJq97edlEgLiIXOmsjJy3f/
UrktX+IrWXhlvfVDvJ9/zTYgJcDit47TnO4BYqhWf/xYQjjd+ezcWOCy6Iv1AueSQmy/d9F6C0Xe
6JM5qPm7g+YbwxTmUPsrhMT8Jh0G9/WthujRJWbkMO5uqzsRKp/x7qNz70+PL3JysBuJQW/snpS5
oLhl9aGlNTBAeWkuc56MRkWt9z50OJRi4f7yn+QYhe2Gk2dOKs4/274cByZEhcGEpUoeFzkaCSdy
Mbh77lpBF8M8tBctwL41rsjQByLQd4S0dZXrm3Rr7ZRw+KclQHgtrvlOf9cC7PCOcL+EyVtMtXYM
P81KBmFdOtI4l5290pOx76uEXha1o+KtsaA6ii3drO+UgUpqCYrr9N/l0FUXFmxynJvXMx76IOgH
EhnIW31522q8JMCspP34twWvZ29fmAvG+rUlA8/CnwQYAQgACQUCXQyXbgIbDAAKCRBph5S8bnN/
DSXqA/9+wf1UxDdu5L09x+JSWcEw3GXSxj8ZI1z9yU1b7Im6si+IC5d1d3hXDv9Tw1rYdX263JfD
7qkgcagH1r/zlbg9TsJIg35ForFm6WH9dsbivA2dD06LZHGI/IjBKBAhfovuDDech97XywfD9lII
BegZQpCt1gCJ+LFddTvMUUZf+Q==
=pVtt
-----END PGP PRIVATE KEY BLOCK-----

Here is the gpg-agent debug log for both success decryption and failed decryption. The RSA key parameters and input data are the same. But the RSA decrypted results are different.

  • Success log

2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt data:+5229acc197af135d1a538e553dda54ecbaa2f37885ed3bb52ce39f237c68a803 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: 53795232070f7a426a57dc3e539a7b0e9b9c3d04739612370a5e40a1974979a4 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: aacd3b68e198fce377b91365930d358371b2240818f961be48ee5d568b593768 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: da311059f96380bdadd49fc5278bf56a641a7fcebd6cef310f4908de1eeeb918
2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt n:+83b203efde0f2a40a9a45b215e2e749f64f83af314139b9eb8d3777324495465 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: 4e3fc8f771b2abaa0fbf6315829e486867f2544c8b46f82b9201739c49936ab8 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: bf9df1b6ab14c48d54d3993480302972d9348731d0cc36658970e8ea2ef4efb1 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: 597e15e4b1bf379942d3aaf681d4d7cfed5f45709def721cda598143ede0e3ff
2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt e:+010001
2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt d:+25c299fc61d8494e2715f8073640edb1723af67412129931465f63c580e701aa \
2019-06-21 16:39:47 gpg-agent[14676] DBG: d667d590956a1c6c737d75c48a222632c1732b16936cb2e5934495487f94242a \
2019-06-21 16:39:47 gpg-agent[14676] DBG: 0eef9b05d9bb5156b5bb4930b756a0b56facb2196c5b14b134a11474fa3316a8 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: 846fc9733aa5e865fe21284ec1e8f81ff56b61199db52fbfcd117218d3400479
2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt p:+e4fe694a1642c147cc6345d1a20351894b43ab80b4a2725dfa31b5ed965ca022 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: a9754f26c98f4ad610227fd6f340ddccc369bdf124db5a9623aaf5ce34edeb33
2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt q:+933a0d3bddec0864c8cf60d52608e0699c4c5b6239371dbc95b6d38a14ccc6e7 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: ace212c9c90e3836060f2db680ba0358709b2f3b274c8e2586965c5890378405
2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt u:+597e14279288b594bcecb7b3a3f3db873b39c0eb4b22a6bcd9c916d1d8e74971 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: 5bf6281d754316572a6ed4a92326ed5d87f0f1e25598bd86ce45e4eaeb220b60
2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt res:+02782fc3d86ce02599322563e5985b59fded066fae86dad323a4fbede154c7b7 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: 51c768db26ff7b9586686a586ea562635f3bfb9a877eae6e7431018f61b76a61 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: 3e369ef6abce75dcba7717a88a247534b9dc2e93dcb7a4f671e20c1880a77634 \
2019-06-21 16:39:47 gpg-agent[14676] DBG: b1440ea95c45ee8caf5c470003450e475d9a873b2d79f5b3cf401cd62706c9
2019-06-21 16:39:47 gpg-agent[14676] DBG: rsa_decrypt => Success

  • Failed log

2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt data:+5229acc197af135d1a538e553dda54ecbaa2f37885ed3bb52ce39f237c68a803 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 53795232070f7a426a57dc3e539a7b0e9b9c3d04739612370a5e40a1974979a4 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: aacd3b68e198fce377b91365930d358371b2240818f961be48ee5d568b593768 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: da311059f96380bdadd49fc5278bf56a641a7fcebd6cef310f4908de1eeeb918
2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt n:+83b203efde0f2a40a9a45b215e2e749f64f83af314139b9eb8d3777324495465 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 4e3fc8f771b2abaa0fbf6315829e486867f2544c8b46f82b9201739c49936ab8 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: bf9df1b6ab14c48d54d3993480302972d9348731d0cc36658970e8ea2ef4efb1 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 597e15e4b1bf379942d3aaf681d4d7cfed5f45709def721cda598143ede0e3ff
2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt e:+010001
2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt d:+25c299fc61d8494e2715f8073640edb1723af67412129931465f63c580e701aa \
2019-06-21 16:39:49 gpg-agent[14676] DBG: d667d590956a1c6c737d75c48a222632c1732b16936cb2e5934495487f94242a \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 0eef9b05d9bb5156b5bb4930b756a0b56facb2196c5b14b134a11474fa3316a8 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 846fc9733aa5e865fe21284ec1e8f81ff56b61199db52fbfcd117218d3400479
2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt p:+e4fe694a1642c147cc6345d1a20351894b43ab80b4a2725dfa31b5ed965ca022 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: a9754f26c98f4ad610227fd6f340ddccc369bdf124db5a9623aaf5ce34edeb33
2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt q:+933a0d3bddec0864c8cf60d52608e0699c4c5b6239371dbc95b6d38a14ccc6e7 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: ace212c9c90e3836060f2db680ba0358709b2f3b274c8e2586965c5890378405
2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt u:+597e14279288b594bcecb7b3a3f3db873b39c0eb4b22a6bcd9c916d1d8e74971 \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 5bf6281d754316572a6ed4a92326ed5d87f0f1e25598bd86ce45e4eaeb220b60
2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt res:-83af8bc01a36bd60840b28fbfa48dc440afa4deca46514c3e5afd2773667ff9d \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 96ee018e968bac2e7a38faab2a2fa30604931850f0bf797d238d429aba31b34e \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 5e5fbb17b468f6177819221cd7a604fda47aab033cef7ec092ff06de1674483b \
2019-06-21 16:39:49 gpg-agent[14676] DBG: 24ccd1d60862f1aab6244eaf81d192c1a601aae962c1f827268a412717b9dd36
2019-06-21 16:39:49 gpg-agent[14676] DBG: rsa_decrypt => Success

This only happens for the RSA CRT decryption. If I modify the code in cipher/rsa.c to always use secret_core_std, then the decryption never failed. It seems the gpg assumes the RSA key parameter P should always smaller than Q. The P is bigger than Q in the above private key.

This issue exists in both Windows and Unix.

Details

Version
2.2.10
Anthony created this task.Jun 21 2019, 11:50 AM
werner added a subscriber: werner.Jun 23 2019, 12:09 PM

Which Libgcrypt version is used (gpg --version shows it).

Why do we see a "IPWorks! OpenPGP 2020" and what is this?

The gpg --version shows:

gpg (GnuPG) 2.2.10
libgcrypt 1.8.3

As for the "IPWorks! OpenPGP 2020", it's another pgp tool, IPWorksOpenPGP (https://www.nsoftware.com/ipworks/pgp/). This key is created by IPWorksOpenPGP.

werner edited projects, added Not A Bug, OpenPGP; removed Bug Report.Jun 24 2019, 2:37 PM

I see. Thus the problem is that IPWorksOpenPGP does not create proper OpenPGP private keys. I guess they use OpenSSL with their different CRT parameter style and do not convert them correctly. RFC-4880 says this in 5.5.3:

The secret key is this series of multiprecision integers:
o  MPI of RSA secret exponent d;
o  MPI of RSA secret prime value p;
o  MPI of RSA secret prime value q (p < q);
o  MPI of u, the multiplicative inverse of p, mod q.

Note the requirement of P < Q.

I see. Thanks for your explanation.

werner closed this task as Invalid.Jun 25 2019, 1:28 PM