[HN Gopher] Why does the all 0 public key have a known private k...
___________________________________________________________________
Why does the all 0 public key have a known private key in SR25519
and ED25519?
Author : navigaid
Score : 130 points
Date : 2023-03-05 16:58 UTC (6 hours ago)
(HTM) web link (substrate.stackexchange.com)
(TXT) w3m dump (substrate.stackexchange.com)
| Jabrov wrote:
| Well that made zero sense to me. Can someone ELI16?
| xurukefi wrote:
| Very generally speaking: with ECC using Weierstrasser curves
| the secret key is a x-bit integer (say x=128 for example) that
| is usually generated randomly and the public key is a point on
| the curve that you get by multiplying a "generator point" with
| that secret key using elliptic curve point multiplication.
| Actually, it is only the x-coordinate of that point but that
| doesn't really matter. This all has to satisfy certain
| mathematical properties. Most importanly given a public key
| (remember, this is a point on the curve) it should not be
| possible to undo the multiplication to retrieve the secret key.
|
| If you understand this it becomes obvious why it is strange
| that people seem to be able to know the private key of the all
| 0 public key. Getting to that point on the curve would either
| require undoing the multiplication or brute force, both of
| which are not feasible assuming that ECC is not broken.
|
| Without going to deep: the explanation of this penomenon is
| that ed25519 uses a different curve model (not Weierstrasser
| curves) where this logic does not completely apply due to
| special cases.
| xurukefi wrote:
| An extra titbit for anybody who is interested in this: The
| Weierstrasser curve used by Bitcoin (secp256k1) has an
| interesting public key where the secret key is 1/2. What's so
| special about this (apart from the fact that the key is a
| nothing-up-my-sleeve number) is the x-coordinate of that
| public key has 162 leading 0-bits (out of 256). This can be
| used for saving Bitcoin transaction fees as they use the DER
| encoding to compress these leading 0 bits.*
|
| Considering that it is highly unlikely that this is a
| coincidence it is believed that the designers of the
| secp256k1 curve chose the generator point based on that
| value. They looked at that point (1/2, P) and then they
| defined the generator point G as 2*P.
|
| * NOTE: don't try this at home. If you're not clever about
| this you will lose all your Bitcoins.
| kebman wrote:
| Would that be a way to leverage fees in trades?
| hdevalence wrote:
| It's not strange at all. The "all zero public key" is the
| encoding of the zero element (identity element) of the group.
| Finding the private key corresponding to a public key A is
| finding the number a so that A = a*B. When A = 0, this is
| really easy: a = 0.
| xurukefi wrote:
| It's strange if you come from Weierstrasser curves and
| think of public keys as points on the curve, which I think
| is what most people start with. I was obviously
| oversimplifying heavily.
| tptacek wrote:
| It's "Weierstrass". I don't believe they're describing a
| different model of public keys. The private key in all of
| these schemes is a scalar.
| cvs268 wrote:
| Thanks for putting in the effort to compose this explanation
| (assuming U did, and not simply asked GPT). But FYI, I did
| not find it helpful at all. Even after re-reading it twice.
|
| Bawolff's concise ELI5 comment helped though.
| xurukefi wrote:
| Thanks for the feedback. It's certainly interesting to see
| that you did not find it helpful at all. I was
| oversimplifying so much that I felt uncomfortable about it
| because I feel like some aspects of my answer are just
| borderline wrong. I don't think I can make it even simpler.
| Explaining highly technical issues to people without any
| background in that field really is a tough skill that I
| apparently don't possess.
|
| Also: I did not use ChatGPT. Proof: Any native english
| speaker can tell you that my answers do not come from a
| native speaker. I don't think ChatGPT can mimic that (yet).
| English not being your first language can have its virtues.
| detrites wrote:
| As someone quite familiar with cryptography, or so I thought,
| may I humbly ask for the ELI5?
| bawolff wrote:
| I think the ELI5 version is - if you are doing complex things
| with math, 0 and 1 probably have weird properties so you
| should avoid those numbers. If you're picking a key you
| should generally do it randomly as certain numbers may have
| special properties that are exploitable, but the chance of
| getting such a number by chance is basically zero.
| nailer wrote:
| You can ask questions about crypto to real cryptographers on
| https://crypto.stackexchange.com. My layperson, 30 second
| understanding is:
|
| - If you remember RSA, ECC replaces RSA because it has better
| performance.
|
| - In ECC, public keys are points on a curve. There's two main
| types of EC curves:
|
| - A Weierstrass curve looks like a pimple (classical ECC) -
| you'll see this in older crypto systems.
|
| - An Edwards curve looks like a butthole - more popular these
| days, as it has less 'exceptional cases' on the curve which
| don't confirm to normal 'add two points together to get a third
| point' maths.
|
| - 'Ristretto' turns out to be the ECC-based key derivation
| algorithm used by Polkadot cryptocurrency:
| https://wiki.polkadot.network/docs/learn-cryptography or
| https://ristretto.group/ and is based on Edwards curves.
|
| The second answer (typical for Stack Exchange sites) summarizes
| it well):
|
| > In the Ristretto group, 0 is a member of the group, while in
| Secp256k1 it is not.
| KennyFromIT wrote:
| The question asks why the all 0 public key in SR25519 and
| ED25519 has a known private key and what users should be aware
| of when using these curves. The answer explains that this is
| due to the mathematical properties of the Edwards curve models
| used in these curves and suggests using hash-to-curve to
| generate unspendable funds instead of the all zero public key.
| hdevalence wrote:
| I'm a coauthor of Ristretto.
|
| There is a much more concise explanation than in the linked post:
| in Ristretto, the encoding of group elements was constructed so
| that the encoding of the identity (zero) element of the group is
| the all-zero byte string. So it's not surprising that the all-
| zero byte string has a known private key: it's the all-zero
| secret key.
|
| This aspect of the encoding makes it very easy to check whether a
| provided group element is the identity element, because "zero
| means zero".
|
| What the questioner seems to be looking for is a way to generate
| "burn addresses", public keys with the property that everyone can
| be sure that no one else knows the secret key to. This is
| actually kind of hard: if I just give you a public key, how do
| you know I didn't generate it from a secret key I know?
|
| The correct answer to this "nothing-up-my-sleeve" problem is to
| have a group-valued hash function, which Ristretto provides. Then
| public keys can be specified as the outputs of the hash function.
| etna_ramequin wrote:
| Thanks for the layman's explanation, I didn't realise something
| like that was even possible! What are some use cases for using
| it? Are they all crypto-currency related?
| hdevalence wrote:
| One use case for generating group elements with verifiably
| unknown discrete logs is for a commitment scheme, like a
| Pedersen commitment.
|
| In a Pedersen commitment, you have two generators, let's call
| them G_value and G_blinding. To commit to a value v, you
| choose a random blinding factor v_blinding and form the
| commitment C_v as
|
| C_v = v * G_value + v_blinding * G_blinding
|
| Later, you can publish (v, v_blinding) to open the
| commitment.
|
| Pedersen commitments are really useful because they're
| homomorphic: adding commitments produces a commitment to the
| sum of the values. So you can use them to do a limited form
| of computation on hidden data.
|
| Where does the verifiable generation come in? Since G_value
| and G_blinding are both in the same prime-order group, there
| exists _some_ value r so that G_value = r * G_blinding. If
| someone knew this relation r, they could forge commitments,
| for instance
|
| C_v = (v+1) * G_value + (v_blinding - r) * G_blinding
|
| and claim that C_v is a commitment to the value v+1 instead,
| because knowledge of the relation r lets them "slide value"
| between the "basis vectors".
|
| So Pedersen commitments are only _computationally_ binding:
| finding r requires solving the discrete logarithm problem,
| which we assume is hard, as long as the generators G_value
| and G_blinding were generated through some verifiable
| procedure.
|
| On the other hand, though, they're perfectly hiding, since
| knowing r lets you find a valid blinding factor for _any_
| value, so even an infinitely computationally powerful
| adversary can't determine which value was used after the
| fact.
| patrakov wrote:
| Just out of curiosity: is a similar problem (generate a valid
| public key that surely nobody including myself can know the
| private key of) solvable for RSA?
| thaumasiotes wrote:
| That problem can't be solvable in any context. There's no way
| to rule out the possibility that someone else in the world
| knows your mathematical secret.
| 3np wrote:
| This reasoning doesn't hold if we're still operating within
| the base assumptions of RSA (and if we're not, no private
| key is secure)
| jagged-chisel wrote:
| Let's try it this way: what if two people, unlikely as it
| may be, generate the same key pair? Two people know the
| private key, and factoring is still hard.
| jongjong wrote:
| I wasn't aware of this issue and it's kind of interesting because
| two of my blockchain projects use address 0 as the token burn
| address (which would basically appear to mean that a hacker could
| steal all the tokens ever burned). I'm now thinking that this may
| have scared away some potential investors. But luckily, only one
| of my projects is based on elliptic curves and address 0 is
| locked explicitly in the code (no funds can ever be moved from
| that address, even if the private key is known) - I guess years
| of coding experience taught me to always be extra careful with
| such edge cases. My other project is based on Lamport OTS and
| Merkle Signature Trees so is not affected either. Still, the PR
| implications are a concern.
| 9dev wrote:
| Wow. I'm not a cryptographer by any means, but have come into
| contact with asymmetric cryptography often enough to not do
| totally stupid things... But this response is really just
| complete and utter gibberish to me.
| beebmam wrote:
| The gibberishness comes from the math needed to understand it
| and not from the knowledge of asymmetric cryptographic
| patterns. I highly recommend that all CS students take some
| abstract algebra courses for an introduction to the ideas
| behind this!
| _a_a_a_ wrote:
| 1. I have negligible chance of understanding your abstract
| algebra and 2. I'll never, ever, get to use it in the real
| world.
| Salgat wrote:
| Might as well take an Introduction to Semiconductor Devices
| engineering course while you're at it. Just as relevant
| when it comes to software development.
| tptacek wrote:
| Abstract algebra is more relevant to the general practice
| of cryptography engineering than semiconductor
| engineering is to the general practice of writing
| software.
| _a_a_a_ wrote:
| I'm sure it is but it also has negligible application to
| quotidian grunt-programming which is regrettably what
| 99.9% of people on HN do. Learning a skill that seems
| never to get used seems completely pointless to me.
| That's a critique of industry, not of linear algebra by
| the way.
| tptacek wrote:
| I agree that abstract algebra has only marginal important
| to the general practice of programming. I only dispute
| that it's marginal for cryptography engineering.
| izacus wrote:
| It also comes from silly names of libraries and tools used in
| the example as well.
| steponlego wrote:
| Something to do with the NSA I'm sure, is the real answer.
| mlindner wrote:
| "It's never Aliens" applies.
| codeflo wrote:
| [flagged]
| [deleted]
| franky47 wrote:
| Another footgun is that Curve25519 has a cofactor of 8, which may
| reveal some information about your private key if some high-order
| points are used [1].
|
| Some curves (eg: Ristretto) were designed to alleviate this
| problem.
|
| [1] https://neilmadden.blog/2020/05/28/whats-the-
| curve25519-clam...
| bawolff wrote:
| DES also has a weak all 0 key (ignoring parity bits)
| lucb1e wrote:
| Why is it weak?
| bawolff wrote:
| https://en.wikipedia.org/wiki/Weak_key#Weak_keys_in_DES
| lucb1e wrote:
| Ah, I had looked for zero, null, and 000 in the DES
| Wikipedia article but it wasn't mentioned. Didn't think to
| search for a dedicated article. Thanks!
|
| Saving others a click:
|
| > DES has a few specific keys termed "weak keys" and "semi-
| weak keys". These are keys that cause the encryption mode
| of DES to act identically to the decryption mode of DES
___________________________________________________________________
(page generated 2023-03-05 23:00 UTC)