[1]https://hardenedvault.net/2021/07/07/vaulthsm_ecdsa-rfc6979.html
VaultHSM report: The way to confirm whether the Smart Card (J3H145) supports
RFC-6979 ECDSA implementation
Vault Labs, HardenedVault Limited
Background
The original implementation of DSA-type signature algorithm (including
ECDSA) needs a random number which belongs to the same mathematical
object of the private key (an element of GF(p), in which p is a prime
number). This random number should also have these three property
below:
1. Randomness: It should be unable to calculate from the data being signed (call
ed "payload" below) and the resulted signature.
2. Confidentiality: It should not be leaked outside the signing process.
3. Uniqueness: It should be different for different payloads.
Otherwise, an attacker may calculate the private key from payloads and
signatures.
If the random number comes from a flawed RNG, its randomness and
uniqueness will become difficult to guarantee, for the attacker may
find the pattern of the flawed RNG by collecting enough
payload-signature pairs, and then calculate the private key. The
industry think “we can take bear of this” until [2]LadderLeak was being
made public. The biggest problem here is: 1) Neither can’t keep the
k-value secret nor “maliciously” repeat it 2) In worst-case, the
attacker only cost 300k USD for P-224:
It doesn’t make sense to ignore this issue especially in
post-LadderLeak era. One of the methods to solve this problem is to
derive the “random number” deterministically from the hash value of
private key and payload with irreversible algorithm (such as hash or
message authentication code algorithm): The participation of private
key in the derivation process guarantees property 1 and 3, if only the
private key is not leaked. This method has been standardized as [3]RFC
6979, and applied to the (EC)DSA implementation of libgcrypt by
default. In addition, EdDSA does not use RNG anymore. The “random
number” used internally is completely and deterministically derived
from the hash value of private key and payload.
GnuPG 2 makes use of libgcrypt, so its implementation of (EC)DSA should
conform to RFC 6979, but GnuPG completely uses the implementation
within libgcrypt only when using private key stored on disk; if the
private key is stored in an OpenPGP Card, operations related to private
key are done inside the card, unrelated to libgcrypt.
If the RNG can not be guaranteed to be flawless, any (EC)DSA
implementation not conforming to RFC 6979 may leak private keys via the
issue mentioned above. Thus, we should use an (EC)DSA implementation
provided by a smartcard only when it certainly conforms to RFC 6979.
Testing process and result
gpg has an option –faked-system-time to assign the timestamp of
signature. (${TIMESTAMP} should not exceed the life time of the sub key
to use)
$ gpg -u ${SUBKEY_ID}! -bo payload.sig --faked-system-time ${TIMESTAMP} payload
If an algorithm is completely deterministic (all of its input is
user-controllable, and the output is uniquely determined by inputs) ,
the resulted signature should be identical when timestamp, payload and
private key are all unchanged. Thus, if an (EC)DSA implementation
outputs different signature even if timestamp, payload and private key
are unchanged, such implementation could not conform to RFC 6979.
The target to test is an [4]NXP JCOP3 J3H145 running [5]SmartPGP. Due
to some limits, switching the type of private key slots may need a
method similar to what is done by [6]this script.
Private keys with type brainpoolP512r1 and rsa2048 (as control group)
are imported to the signing key slot in succession, paired with private
keys stored on disk. Two signatures are generated against each one type
of private key, with fixed timestamp. Generated signatures are examined
with hash. The results are shown below:
$ sha256sum payload*
94d89559a996659d5220e630d7af057db8cd7e5dd61d7959139a68fc72fa80c8 payload
54885e606a52f6e80af21766568ab840ee1b5e4a8c84898a6ee551c98f31f36e payload.ecdsa.
c0.sig
f36c492c25ec794a30e68d0c08687b6afc14b28ec19bbd4b52bc57930b1c3eaf payload.ecdsa.
c1.sig
b6e0a45b5da47171472f970fcf4decdb92ec8050fcd094f05ddf0a3af8d65e90 payload.ecdsa.
d0.sig
b6e0a45b5da47171472f970fcf4decdb92ec8050fcd094f05ddf0a3af8d65e90 payload.ecdsa.
d1.sig
31b83302f6397a8ae9676b484507ee4585e65999e24e9d9e0f1e25a0a3149e4e payload.rsa.c0
.sig
31b83302f6397a8ae9676b484507ee4585e65999e24e9d9e0f1e25a0a3149e4e payload.rsa.c1
.sig
fd31c92c884ae26cc5efbd58c6ebbb080ee3755ea3de6b6b3474bf3f9b713f76 payload.rsa.d0
.sig
fd31c92c884ae26cc5efbd58c6ebbb080ee3755ea3de6b6b3474bf3f9b713f76 payload.rsa.d1
.sig
payload is randomly generated data; Signature labeled with letter c are
signed with keys in card; Signature labeled with letter d are signed
with keys stored on disk.
It can be seen that, with timestamp fixed, no matter rsa keys in card
or on disk are used, identical signature are generated with the same
timestamp, payload and private key, confirming the validity of this
method of judgment from the side.
Identical signatures could also be generated with the ecdsa private key
on disk, but different signatures come out when using the ecdsa private
key on card with the same timestamp, payload and private key, which
means when using the ecdsa private key on disk, the ECDSA
implementation used by gpg is deterministic, while the implementation
on card is not.
Prospect
If the on-card (EC)DSA implementation is confirmed to be deterministic,
whether it conforms to RFC 6979 should be further checked. The method
may be to sign the same payload with same timestamp and same key, once
on disk while once on card. If the implementation on card conforms to
RFC 6979, the resulted signature in these two process should be
identical. It is omitted in this article, though.
Conclusion
Because at present EdDSA has not been popularized among smart cards, we
had better use (EC)DSA for signature only on smartcards whose
implementation is confirmed to conform to RFC 6979, otherwise, the RSA
algorithm should be used for signature, for it does not have the issue
like what presents in indeterministic (EC)DSA algorithm.
The conclusion above only applies to signature. If your smart card
supports ECC, Using EC key pairs for encryption is okay. In such
situation, the assymmetric part of the algorithm will be performed in
the manner of [7]ECIES, and comparing to RSA, it will be enhanced with
the [8]probabilisity of DH, making chosen-plaintext attack much less
effective.
In systems with DH applied, probabilisity is a problem for signature
algorithm, and if it is not handled well, private key may be leaked,
but for encryption, probabilisity can provide extra advantage.
Proposed approach for defense
The long-term solution is waiting for the standardization of EdDSA in
FIPS-186-5. One the practical side, the deterministic ECDSA
implementation didn’t go well in open source project like OpenSSL:
The current situation doesn’t leave us much options but go through the
short-term solution:
* Make sure all of your certificates are using >= P-256 or RSA(
another problematic component)
* Don’t miss the spots without internet connection
Appendix
In order to avoid the interference of testing process with local
~/.gnupg/ directory, it is suggested that a tmpfs dedicated for test be
mounted here:
$ killall gpg-agent
$ su root
# mount tmpfs ${YOUR_HOME}/.gnupg/ -t tmpfs -o nodev,nosuid,noexec,mode=0700
# chown ${YOUR_USERNAME}:${YOUR_GROUP} ${YOUR_HOME}/.gnupg/
After that, keys could be generated according to standard GnuPG usage
and used for test. After test is complete, the tmpfs could be unmounted
after its contents being shredded.
$ killall gpg-agent
$ find ~/.gnupg -type f -exec shred -v {} \;
$ su root
# umount ${YOUR_HOME}/.gnupg/
References
1. https://hardenedvault.net/2021/07/07/vaulthsm_ecdsa-rfc6979.html
2. https://eprint.iacr.org/2020/615
3. https://tools.ietf.org/html/rfc6979
4. https://www.javacardos.com/store/products/10029
5. https://github.com/ANSSI-FR/SmartPGP
6. https://github.com/ANSSI-FR/SmartPGP/blob/master/bin/example-set-mixed-crypto.py
7. https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme
8. https://en.wikipedia.org/wiki/Probabilistic_encryption