4
$\begingroup$

ECDSA works by computing the hash of a message and then computing the signature for it. ECDSA uses the signature:

$$s = k^{-1}(h + rp_{pr})\,\textrm{mod } n,$$

where $n$ is the order of the group, $k$ is a randomly sampled nonce, $r$ is the projection onto the $x$ axis of $kg$, where $g$ is a group generator.

If you are only provided $r,s$, then I don't see any obvious way this would leak any bits of $h$. Has anyone managed to see any papers about it? I couldn't find any. I also couldn't come up with a reduction to another hard problem if I had an oracle that could figure out $h$.

The somewhat strange use case of this is that we have an HSM that supports signature generation and verification. By storing signatures in a DB we could use the signature verification algorithm for password verification. Preventing any form of offline password cracking in case of a data leak or unauthorized access to the data.

$\endgroup$
3
  • 1
    $\begingroup$ The aim of signature schemes is not about securing the hash or the message, it is about creating an unforgeable signature and not leaking about the key ( very short of the huge subject). To verify the signature one needs the message itself and the hash is not a keyed hash then. You should have already applied the password hashing to your hash before the ECDSA signature. By the way, be careful about the nonce of the ECDSA, it is very fragile on tiny biases. Prefer to use deterministic ECDSA $\endgroup$
    – kelalaka
    Oct 27, 2022 at 10:29
  • $\begingroup$ I'm well aware. I have a Ph.D. in crypto... and we do first apply bcrypt with salt, so that's the input to ECDSA to generate the signature. To verify a password, we compute bcrypt of the password and the salt and ask the HSM to verify that what's in the DB is a valid signature. I would not want to do this, but this is our only available way to protect against insider attacks. $\endgroup$
    – eof
    Oct 27, 2022 at 10:33
  • 1
    $\begingroup$ On the internet, everyone has a Ph. D. Anyway: I think you can reduce the problem to the discrete logarithm assumption if you assume $h$ is uniform random (ROM) and the scheme is secure. $\endgroup$
    – Titanlord
    Oct 27, 2022 at 11:00

1 Answer 1

1
$\begingroup$

Does ECDSA leak information about the message hash?

At least if the public key is public (as implied by the name, and the standard hypothesis in cryptography), yes it does. Proof: it allows anyone with the signature to check a guess of the message or even of the message hash, merely by using the ECDSA signature verification procedure. And if we "use signature verification algorithm for password verification" by way of signing the password or a hash thereof and storing it in the password file, that's a disaster.

If we use a memory-hard KDF like Argon2 before signature, there's no disaster, but the signature step adds little security.

Thus I think the question makes more sense if we specify that the public key is somewhat made secret. But even then, there's a another issue: with one (or few) known passwords and their ECDSA signature, it becomes possible to rebuild the public key, using public-key recovery.

I conclude the proposed technique does not work, as is.


In the following I explore ideas on using a HSM's signature function for secure password handling.

If we try to hash the ECDSA signature before storing it, we solve the problem that the public key can be found, but we loose the ability to use signature verification to verify a password. And, devastatingly, can't verify a password at all: recomputing the password-hash-token as in enrollment and comparing it to the stored password hash token would fail, because ECDSA is a randomized signature scheme.

On the other hand, that variant works with any deterministic signature scheme supported by the HSM, such as RSA-SSA-PKCS1-v1_5 (which is ubiquitous), or EdDSA (which is increasingly common). Basically, we include in a password hash token: $$\operatorname{HSMPBKDF}_\text{priv}(\text{salt},\text{password})\gets H(\operatorname{Sign}_\text{priv}(\text{salt}\mathbin\|H(\text{password})))$$ where $H$ is a standard (fast) hash such as SHA-256, which needs not be in the HSM. Or if we want to additionally use a memory-hard key-streching hash like Argon2, we include in a password hash token: $$\operatorname{HSMPBKDF}_\text{priv}(\text{salt},\text{password})\gets H(\operatorname{Sign}_\text{priv}(\operatorname{Argon2}(\text{salt},\text{password},\ldots))$$

That password hash can be safely truncated, e.g. to 128 bits. As usual it should be stored in the password hash token along with extra stuff: at least a version for the password hash token format and algorithm, the salt, here probably the private key id, perhaps some parameter(s) as as workfactor…

The signature parameters (e.g. size of the public modulus for RSA) can be used as a workfactor parameters in case we want to resist the HSM being used by an attacker together with it's private key $\text{priv}$ (a reasonable scenario).

It's important that:

  • The signing key is kept secret (the public key can be left public; both are universal practice in HSM)
  • The input and output of the signature both are kept secret (possible though not always the case; in particular these values must not be logged, or leak as a side channel thru a Smart Card reader interface)
  • The password is hashed before signing†, or another measure insures that it's impossible to exhibit two ($\text{salt}$$\text{password}$) that must have the same signature. Contrast with $H(\operatorname{Sign}_\text{priv}(\text{salt}\mathbin\|\text{password}))$ which could be attacked by an adversary with free read access to the hashed passwords‡.

† As a general rule the earlier the password gets hashed, the better, as long as bytes 00 in the hash are not considered the end of the hash.

‡ Such adversary can find any lowercase 4-letter password for targeted user john.doe used as salt, by remotely registering 26 phony users john.doea, john.doeb, …; then iteratively: changing the passwords for each of these to one of 263=17576 three-character passwords, reading the password file, and checking if one of the password hash fields in the password hash tokens for the phony users matches the passwords hash field in the password hash token for john.doe.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.