27
$\begingroup$

I am studying about blockchain and have been focusing on encryption protocols that allow authentication. The digital signature of public and private key seems solid, I have focused on the algorithm ED25519.

But in some places, some people say about not exposing the public key because through the public key and signature it would be possible to derive the private key. Some say that quantum computers will easily accomplish this task.

At first, I thought the reason for the bitcoin addresses was to make the public key "human-readable." But I see that there are some security points having a public key hash.

So I have some doubts:

  • Is it really a risk of exposing the public key without any treatment?
  • If so, what are the alternatives?
  • How does bitcoin, for example, validate the transaction signature with a public key hash and not the public key itself? (After all, it would be "impossible" to reverse a sha256 hash to its origin)
$\endgroup$
  • 4
    $\begingroup$ I suppose that BitCoin will not survive in its current form if Quantum Computing comes entirely off age. Exposing the public key is of course fine without QC. And no, you cannot verify without the public key. $\endgroup$ – Maarten - reinstate Monica Jun 18 '17 at 12:06
  • $\begingroup$ And do we have alternatives to implement secure protocols that are resistant to quantum computing? Or is it simply the case of "not worth thinking about for now"? $\endgroup$ – Victor França Jun 18 '17 at 12:34
  • 5
    $\begingroup$ In December of last year NIST issued a call for proposals for criteria to evaluate post quantum algorithms. We're years away from having widely accepted algorithms. csrc.nist.gov/groups/ST/post-quantum-crypto/documents/… $\endgroup$ – Swashbuckler Jun 18 '17 at 14:03
  • $\begingroup$ On bullet 3: ECDSA can recover publickey from signature to within a small number of candidates, and Bitcoin adds a few bits to select among these candidates, then it's trivial to verify address; see crypto.stackexchange.com/questions/18105/… $\endgroup$ – dave_thompson_085 Jun 19 '17 at 1:50
  • 1
    $\begingroup$ You seem to know very little about cryptography in general, i would advise you to not worry about post quantum cryptography . Focus on the basics of modern cryptography $\endgroup$ – Souza Feb 9 '18 at 18:16
50
$\begingroup$

From a cryptographic standpoint it is OK to expose a public key in the sense of revealing its value. The most basic assumption in cryptography involving public/private key pairs is that the value of a public key is public; hence its name.

It is extremely important that an adversary can not alter a public key. Any exposition that would allow alteration must be avoided !

Also, a public key is highly characteristic; so one might not want to reveal one's public key, in order to remain untraceable (and anonymous). However, that might not be enough: unless the signature scheme is designed to prevent this, revealing one's signatures might allow traceability (for some systems it is even possible to reconstruct the public key from signatures).

It is correct that not revealing a public key deprives adversaries from information that a sufficiently powerful adversary can use to find (an equivalent of) the private key and break the system. But we need a public key to be public so that signatures made with the owner's private key can be publicly checked. Concluding that one should not reveal a public key is like saying one should keep the location of a bank's safe room secret: that's an assumption ruled out by design, because it would make the design unfit for the intended purpose.

Yes, hypothetical quantum computers usable for cryptanalysis would allow an adversary to attack a known public key of the kind we use now (and in the blockchain). On the other hand

  • Currently, available quantum computers are less useful for cryptanalysis than available lightsabers are to break into a bank's safe room.
  • There is plausible reason to fear that in the signature systems that we use, a few signatures are as good as the public key to an attacker with such hypothetical quantum computer usable for cryptanalysis.

Update: regarding

How does bitcoin for example validate the transaction signature with a public key hash and not public key itself?

It obtains the public key, validate (or reject) it by hashing it and comparing to the trusted public key hash, then validates the transaction signature against the validated public key. For more, see indiscreteLogarithm's answer.

$\endgroup$
  • $\begingroup$ Great answer! I'm trying to understand about hash-based signatures, there are some interesting points, it seems to be efficient against a "hypothetical quantum attack" but inefficient for processing classical computing we have today (and in space). I am looking for a way to ensure that assuming a user has good practices in keeping "the secrets that generate his identity," no one can clone his identity. In this case, it seems that the public key protocol is perfect in this case for current times. $\endgroup$ – Victor França Jun 18 '17 at 15:42
  • $\begingroup$ @fgrieu Already integrated into the other answer. Order changed because of an edit by Anthony so I clicked the wrong one. Either that or the system messed it up :) $\endgroup$ – Maarten - reinstate Monica Jun 18 '17 at 17:15
  • $\begingroup$ For some reason the most interesting part of the question was ignored: "How does bitcoin validate the transaction signature with a public key hash and not public key itself?" $\endgroup$ – shal Dec 31 '17 at 9:30
  • $\begingroup$ @shal: I tried to plug that hole $\endgroup$ – fgrieu Dec 31 '17 at 10:27
  • 1
    $\begingroup$ @fgrieu I'd suggest changing your last edit regarding the bitcoin validation process of signatures. What you describe would be feasible in theory, but it's not how the Bitcoin protocol is implemented. See my answer for more details. $\endgroup$ – indiscreteLogarithm Jan 1 '18 at 20:47
13
$\begingroup$

The advent of quantum computing, real usable out of the lab QC, will pretty much be the end of any encryption that relies on the difficulty of the discrete log problem via Shor's Algorithm et al. That is not to say it is the death of all modulus based encryption schemes, probably just asymmetric public/private key based schemes.

That said, QC's aren't magic, even they have theoretical limits to their computing power, and its far easier to simply use a QC to discover Sophie Germain primes so large as to make even QC impractical. Even if that proves not to be the case, there are other types of algorithms, e.g. supersingular elliptic curves isogeny, that can step up.

Coming from a military background I will say that any time you can deprive the enemy of information then you should, If for no other reason than to force them to make the effort (read "spend money") to discover that secret, no matter how mundane or useless that knowledge ultimately is. Money spent to discover the public key (if kept secret) is money they don't have to break that key, or to break the next key.

So keep the public key secret as much as feasible.

$\endgroup$
  • 1
    $\begingroup$ Double space will do nothing for formatting, double space with enter is a line break. Double enter will however nicely split your answer in sections and your answer did require a few - just so that you know for any next posts - and welcome to crypto of course :) $\endgroup$ – Maarten - reinstate Monica Jun 18 '17 at 17:00
  • $\begingroup$ The problem is: in the public key protocol we use the signature as a proof of identity (authenticity), who wants to validate this proof of the public key. In a closed and controlled scenario, it is possible to guarantee that only the "validator" has the public key. But in a system where only one can sign, but can everyone optionally validate signature, how to keep the public key secret? I see no practical form. $\endgroup$ – Victor França Jun 18 '17 at 17:26
5
$\begingroup$

In general revealing the public key is fine it is designed to be public. However there are some scenarios where knowing the public key would open up further attack vectors. For example if two parties communicate they will typically first do some key exchange and only authenticate on the encrypted channel. If there is some weakness in the public key system for example poor randomness in key generation a magical(quantom?) Factorization algorithm or such revealing the public key would allow mounting an offline attack. If we have a plain text/ cipher text pair or a plain text and signature we may be able to mount an offline attack regardless but there are scenarios where getting such a pair would be difficult in itself for example the above scenario you get nothing in a paasive attack without breaking first ge key exchange. All of these are protection against hypothetical attacks(except perhaps the randomness one which might be plausible) but there isn't need to give your attacker anything if you don't have to.

On the otherhand publishing your public key widely can protect against other attacks. Such as convincing someone to use the wrong public key. We see a move in https in this direction. Certificate transparency is likely going to improve security substantially.

$\endgroup$
5
$\begingroup$

Most of your questions have been covered in the other answers, so I will focus on the remaining one:

How does bitcoin for example validate the transaction signature with a public key hash and not public key itself? (After all, it would be "impossible" to reverse a sha256 hash to its origin)

This is briefly described in the Bitcoin Wiki. Basically, every bitcoin transaction has one or several inputs which are the origins of the coins being spent, hence every input corresponds to a previous transaction's output where the current spender received coins.

For each input, certain criteria must be fulfilled (defined in a so-called script) which prove the spender's ownership of these coins (i.e. proof that they own the destination addresses of said past transactions). Normally, this is done by providing

  1. a public key that, when hashed, yields destination address (...) embedded in the script, and
  2. a signature to show evidence of the private key corresponding to the public key just provided.

As you see, when spending coins, the involved public keys (which are basically the user addresses) must be made public, and are from this point onwards vulnerable against attacks directed at the elliptic curve discrete logarithm problem (e.g. by quantum computers). This is one of the reasons why it is strongly recommended (and often automatically implemented in wallets) to not re-use addresses for multiple transactions.

$\endgroup$
3
$\begingroup$

Suppose the adversary has a quantum computer. If the adversary has time to run it on the public key before it becomes irrelevant, then every pre-quantum public-key signature scheme is broken. What if the adversary doesn't have time to run it on the public key before it becomes irrelevant? For example, in Bitcoin, a transaction is (very approximately) a signed statement saying

Please send 0.042 BTC to pubkey whose SHA-256 hash is 0x2ef20003e34f7113dfbb26b37e7544a657208aa4f11ffda8781d75e1bda23a09. Sincerely, pubkey 0x40e0cb242a51f749b028a4a3c0895000dc5c3bea58ab7d344e5d0a611529ef04.

As long as you use each public key only once, the adversary has only the time before the network has accepted the transaction to attempt to forge an alternative transaction before any future forgery of signatures by the sender of the transaction is inconsequential. If the adversary wants to forge signatures by the recipient of the transaction, they must also reverse SHA-256—a considerably harder problem. The adversary can try to parallelize the computation, but if theft is all that is at issue (which it may not be; false attribution or all manner of other things might be valuable to the adversary), then the parallelized computation can't cost more than 0.042 BTC before it's a waste of money.

However, this is not a proof of security against quantum computers, of course—it is at best an amusing thought in the attacker economist philosophy. It is also only the story for a single key. What happens if the adversary can break many keys simultaneously? As it happens, Pollard's $\rho$ algorithm breaks many keys simultaneously faster than many keys independently. (I'm not sure what the multi-target Shor story is.)

Now consider a hypothetical application beyond Bitcoin, where only select verifiers learn the public key at all, the verifiers whom the legitimate parties want to enable to verify signatures. What if the adversary doesn't even see the public key? Can the adversary recover the public key—and thereby break the cryptosystem with a quantum computer—from a signature, or a collection of signatures? (Even if the answer is no, of course, this doesn't rule out a quantum adversary's ability to forge signatures without recovering the public key, but while intuitively it seems unlikely, I won't address that extended question for now.)

In ECDSA over a curve $E/\mathbb F_p$, a signature under a public key $A \in E(\mathbb F_p)$ on a message $m \in \{0,1\}^*$ is a pair of $r \in \mathbb F_p$ and $s \in \mathbb Z/\ell\mathbb Z$, where $\ell = \#E(\mathbb F_p)$, satisfying the equation $$r = x([H(m)\,s^{-1}] B + [r s^{-1}] A),$$ where $B \in E(\mathbb F_p)$ is the standard base point. Knowledge of $a \in \mathbb Z/\ell\mathbb Z$ such that $A = [a]B$ makes it easy to solve for $s$ given uniform random $r$. However, we can also solve for public keys—not uniquely, but close enough to forge signatures with nonnegligible probability: by finding the points $R \in x^{-1}(r)$ with $x(R) = r$, so that $R \in \pm [H(m)\,s^{-1}] B + [r s^{-1}] A$, we can compute $$A \in [r^{-1} s] (R \pm [H(m)\,s^{-1}] B),$$ and so from a single signature it is easy to recover one of two public keys verifying the signature. Then an adversary with a quantum computer can solve the elliptic-curve discrete log problem with Shor's algorithm. Thus ECDSA does not provide security against this threat model.

What about Ed25519? An Ed25519 signature under a public key $A \in E(\mathbb F_p)$ on a message $m \in \{0,1\}^*$ is a pair $R \in E(\mathbb F_p)$ and $s \in \mathbb Z/\ell\mathbb Z$ such that $$[s] B = R + [H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)] A.$$ If we had $\underline A$ (the encoding of the point $A$), then we could recover $$A = [H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)^{-1}] ([s] B - R),$$ but this is begging the question. Does this mean Ed25519 provides security against this threat model? I don't know! This requires further analysis.

What about RSA signatures, say RSA-FDH? An RSA-FDH signature under a public key $n$ on a message $m$ is an element $s \in \mathbb Z/n\mathbb Z$ such that $s^3 \equiv H(m) \pmod n$, where $H\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$ is a uniform random function. If an adversary with a quantum computer learned $n$ they could use Shor's algorithm to factor it.

Now, a single signature doesn't reveal $n$. With a corpus of signatures, the adversary can solve the German tank problem to distinguish signatures under $n_0$ from signatures under $n_1$ and deanonymize signers—which doesn't guarantee the adversary can learn $n$ with enough precision to apply Shor's algorithm or hire Don Coppersmith to figure out a brilliant variant of it, but doesn't rule it out either.

What if we chose the first $s_i = H(m, i)^d \bmod n$ for $i = 0, 1, 2, \dots$ such that $s_i \bmod n < 2^{\lfloor\lg n\rfloor}$ by rejection sampling? This shouldn't reduce the security of the underlying signature scheme much: if an adversary could compute cube roots with nonnegligible probability given a signature scheme covering all elements of $\mathbb Z/n\mathbb Z$, then they could probably compute cube roots with at worst about half the probability given a signature scheme covering only elements below $2^{\lfloor\lg n\rfloor}$. (Caveat developer: I am just a pseudonymous bone-eating vulture on the internet, and I'm definitely not your cryptographer…and the first draft of this was completely wrong.)

$\endgroup$
  • 1
    $\begingroup$ Nitpick: Bitcoin address is RIPEMD160(SHA256(pubkey_encoding)) not just SHA256. And a txn (usually? almost always?) has multiple outputs, with at least one to an address owned by the same owner as the input(s) -- but recommended not to be the same address, as noted by Indiscrete. These don't affect the substance of your argument, of course. $\endgroup$ – dave_thompson_085 Jan 1 '18 at 0:41
  • $\begingroup$ @dave_thompson_085 Yes indeed—that's why I said ‘very approximately’! $\endgroup$ – Squeamish Ossifrage Jan 1 '18 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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