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 (called "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 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 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 NXP JCOP3 J3H145 running SmartPGP. Due to some limits, switching the type of private key slots may need a method similar to what is done by 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 ECIES, and comparing to RSA, it will be enhanced with the 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/