Vault Labs, HardenedVault Limited
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.
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.
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.
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.
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:
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/