7 ms·
Why does the all 0 public key have a known private key in SR25519 and ED25519?
- codeflo 4y ago[flagged]
- deleted 4y ago[deleted]
- Jabrov 4y agoWell that made zero sense to me. Can someone ELI16?
- reportgunner 4y agoIt uses math and it uses 0. When you use 0 in math everything becomes 0 after you multiply it. The more you multiply the more 0 it becomes. I bet you have to multiply a lot in cryptography.
- oleganza 4y agoMath is about precision, so it's generally not a good idea to have something become "more 0" than actually needed. Especially in cryptography. So here's my advice. If you multiplied too much by zero, you can make it less 0 by dividing a few times by zero. Then maths would be closer to the precise 0 that you were looking for in the first place.
- detrites 4y agoAs someone quite familiar with cryptography, or so I thought, may I humbly ask for the ELI5?
- bawolff 4y agoI 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 4y agoYou can ask questions about crypto to real cryptographers on https://crypto.stackexchange.com 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 https://wiki.polkadot.network/docs/learn-cryptography or https://ristretto.group/ 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 4y agoThe 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.
- xurukefi 4y agoVery 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 4y agoAn 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 4y agoWould that be a way to leverage fees in trades?
- hdevalence 4y agoIt’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.
- 9dev 4y agoWow. 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 4y agoThe 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_ 4y ago1. I have negligible chance of understanding your abstract algebra and 2. I'll never, ever, get to use it in the real world.
- Salgat 4y agoMight 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 4y agoAbstract algebra is more relevant to the general practice of cryptography engineering than semiconductor engineering is to the general practice of writing software.
- Salgat 4y agoI'm talking specifically about the requirements for your average software developer, not a developer trying to specifically study cryptography.
- _a_a_a_ 4y agoI'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.
- steponlego 4y ago[flagged]
- mlindner 4y ago"It's never Aliens" applies.
- franky47 4y agoAnother 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-clamping-all-about/ https://neilmadden.blog/2020/05/28/whats-the-curve25519-clam...
- oleganza 4y agoRistretto is not a curve, it's a group. Curve25519 is a _curve_ that implements a non-prime order _group_. Ristretto255 is a prime-order _group_ that uses Curve25519 as an underlying _curve_. In other words, Ristretto is a pair of encode/decode functions that map points on _curve25519_ to _ristretto group elements_ and vice versa. It's called "ristretto" because it's a restricted (specific to curve25519) version of Mike Hamburg's Decaf format that "reduces amount of coffee/cofactor by 4" for Edwards curves.
- less_less 4y agoOh huh, I was thinking the origin of the name "ristretto" was that espresso concentrates a certain amount of coffee in a small cup, whereas ristretto concentrates it even more: in this case it removes a cofactor of 8 and not just 4.
- oleganza 4y agoRistretto is a restricted form of Decaf, that is, specific to curve25519 and deals with a sign choice, while Decaf is generic for all cofactor-4 Edwards curves. In other words, the joke around coffee takes a 90º turn with Ristretto because our first application was Bulletproofs where you need (among other things) a lot of orthogonal generator points.
- bawolff 4y agoDES also has a weak all 0 key (ignoring parity bits)
- lucb1e 4y agoWhy is it weak?
- bawolff 4y agohttps://en.wikipedia.org/wiki/Weak_key#Weak_keys_in_DES https://en.wikipedia.org/wiki/Weak_key#Weak_keys_in_DES
- lucb1e 4y agoAh, 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
- hdevalence 4y agoI’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.
- bondarchuk 4y agoPractical solution: just use all ones instead.
- patrakov 4y agoJust 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 4y agoThat 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.
- deleted 4y ago[deleted]
- 3np 4y agoThis 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)
- jongjong 4y agoI 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.
- nullc 4y agoThe choice of the identity element, if one can be encoded at all, gives you one point with known key by design. Choice of the generator, if it isn't NUMS, can give you a second arbitrary value with a known key-- this latter one could even be a no-one-but-us backdoor but a somewhat contrived one. Like if you want to secretly know the private key of 0xDEADBEEF, set your generator to lift(0xDEADBEEF) x (1/$secret). Now the deadbeef pubkey has a DL relative to your generator of $secret.