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.
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?
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
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.
Which, for a particular real-world use case; I built a PoC for the four biggest insurance companies in my country that allowed them to query each others claims data to see if a claim has been made with another insurance company for the same car/accident/etc (apparently it’s pretty common, with a dodgy repairer involved to do this), without ever revealing the actual data and who was answering it. This would allow the companies to reduce fraud without falling afoul of data sharing prohibitions (which rightfully exist) or needing to necessarily trust one another.
We used a partial homomorphic encryption system for it, but I’m sure we could’ve used a Pederson commitment if we tweaked how we approached it.
One factor though that the PoC never truly got rid of was a semi-trusted central system. We didn’t need to though, at the time. Would’ve been neat however!
Another use is for password authenticated key exchange. The CPace protocol picks its generator using a hash to group operation. See page 13 of https://eprint.iacr.org/2018/286
Its OK it was just like reading ‘car’ and ‘automobile’ in the same sentence and not being quite sure if that was what was actually meant. Otherwise it was a very clear explanation!
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?
This is a great question. To rephrase: is it possible to come up with an RSA modulus that even you don't know the factorization of?
The answer, I believe, is we have no way of doing that so far. The closest thing that exists is "multiparty" or "distributed" generation of an RSA modulus. Roughly, in the two party case of Alice and Bob, this means Alice picks some pair of numbers (P1, Q1) and Bob similarly picks some (P2, Q2). Then, Alice and Bob engage in some secure multiparty computation protocol whereby they obliviously a) check P1+P2 and Q1+Q2 are prime, and b) if so, output N=(P1+P2)(Q1+Q2) to both Alice and Bob.
At the end of the protocol (after repeating enough times that it succeeds), both parties have derived an N whose factorization they don't know.
I don't know much about this area of study, but searching multiparty RSA modulus generation should bring up relevant papers.
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.
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.
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.
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.
Oh 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.
Ristretto 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.
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.
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.
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.
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.
It's still a point on a curve here. It's just on a twisted Edwards curve (or in the case of Ristretto, on a Jacobi quartic curve), not on a Weierstrass curve, but it's the same idea.
When encoding the public key, you give only one coordinate and possibly also a sign bit, and the other person uses the curve equation to solve for the other coordinate. Just like with a Weierstrass curve y^2 = x^3 + ax + b, you can solve for y using only x, plus one bit to say whether to take the positive or negative square root.
Technically, the zero-string encodes the identity element (0,1) for Ristretto, but not for Ed25519 where it's the point (i,0) where i = sqrt(-1). (Not (1,0) as the StackExchange claims, unless I'm very much mistaken. For Ed448 instead I believe it encodes (-1,0).) However the points (i,0) or (-1,0) are basically a rotation of (0,1). So for some protocols it works out that you can use 0 as the private key and it will work anyway.
Part of the point of Ristretto is to eliminate this sort of "gotcha" where certain public keys are equivalent. The way around it is that you pick a certain one of the equivalent points to encode, in a canonical way, and the other options are not valid encodings. This also means you don't need a sign bit: one of the criteria for choosing which rotation is that the sign bit would be zero.
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.
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.
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.
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.
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.
It 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.
Math 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.
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.
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!
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.
Abstract algebra is more relevant to the general practice of cryptography engineering than semiconductor engineering is to the general practice of writing software.
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.
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.
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.
The 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.
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
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.