Topic: Bounty offered to crack the seeds for NIST curves! (Read 561 times)

https://crypto.stackexchange.com/questions/41920/what-is-the-g-function-of-fips-186-2

I wonder, what is c-value for all of those four curves: secp160k1, secp192k1, secp224k1 and secp256k1. Because in the generation procedure from FIPS https://csrc.nist.gov/files/pubs/fips/186-2/upd1/final/docs/fips186-2-change1.pdf we can read:

Which means, that c=(-27/b^2). Assuming that b={3,5,7} for those curves, we would get:

https://neuromancer.sk/std/secg/secp160k1

https://neuromancer.sk/std/secg/secp192k1

https://neuromancer.sk/std/secg/secp224k1

https://neuromancer.sk/std/secg/secp256k1

And as we can see, there are similar patterns in those c-values, even though they use different p-values (especially between secp160k1 and secp256k1). The same hex digits are repeated, because if you apply the same operations on some small numbers, like "-27" or "49", then similar patterns will appear. And I wonder, if this is the case, when it comes to the x-value of the base point.

When it comes to the value used in Bitcoin, I currently think that it may be related mainly to secp192k1, because it contains the most digits of all of those cases, and because there is a point (x=1,y=2) existing on all y^2=x^3+3 curves, so the generator may be just a multiplication of that point, and for example some 160-bit value of SHA-1. Also, it could be some special root, like square root, cube root, or n-th root of factors, used in (p-1) and (n-1).
Some example:
Code for checking values:
Of course, the hash of empty string is not a solution, but I think it may be similar to this one. So, I wonder if applying Kangaroo or BSGS on that curve, and trying to find a distance between (1,2), and the true generator of secp192k1, will show for example some 160-bit number (or maybe even 128-bit number), instead of some 192-bit number.

There are more MinghuaQu seeds, for example here: https://www.certicom.com/content/certicom/en/curves-list.html
If you remove "MinghuaQu", you will see that:
I wonder, what is the exact pattern, so that it would be possible to start with "MinghuaQu", concatenated with some bytes, and jump from one seed to another.

My current assumption is that someone simply started with "srand(time(NULL))", and used "rand()" when needed. I guess that kind of code could end up in production. Which means, exploring old (s)rand implementation may be useful: https://stackoverflow.com/questions/4768180/rand-implementation
I guess it could be also "srand(0)" or something like "srand(1337)", but it could be the current time as well. Which means, we can assume the system clock was set correctly, and then do some bruteforcing, and guessing, to get the correct date and time.

Hint: it is useful to rename (s)rand functions above, to not produce conflicts with the standard library.

I code a quick and dirty CUDA program  for sha1 mining.
The speed i observe is around 5 Giga hash (tries) / second on a RTX3090.
The big problem would be the way to generate the password candidate. (probably slower than the hash)
Have anyone think about it?
the solution with the linux pipe "|"
would be the more convenient but i don't think than it can support such a speed

1. People used nothing-up-my-sleeve numbers to generate elliptic curves.
2. There was some FUD, that those curves are unsafe, because they are "not random enough".
3. People created some random curves, to address this FUD.
4. Then, people started questioning that "randomness" being not explained enough, creating another FUD.

This challenge was made to clean up the FUD. But because the whole process is not fully documented, the task is to recover the full algorithm, to clear all of that FUD. Why it was not fully documented in the first place? Because people are lazy, and they focus on writing code, rather than documentation, then some of that is lost in the history, and then you have things that are officially used in production, but are not fully explained.

Not really, because it is very unlikely that creators of those curves had any special knowledge, that was not publicly revealed by independent researchers. You can read A riddle wrapped in an enigma if you want to know, why elliptic curves are safe, even if they are generated from simple phrases like "Hello world".

Here you have some bytes that looks randomly. Guess what: now people ask about that randomness, and they want to know, how exactly that "randomness" was created in the first place.

Who knows, maybe that was the case. Maybe one of those seeds is just a result of something like SHA-1("Hello world 123456"). But the problem is, that nobody exactly knows, how those bytes were generated, so the whole challenge is about finding that out.

Edit:I found a pattern, but I don't know, how to continue that.
Subtract u1 from all other values, to make it more clear:
And then, split it:
Then, treat the last byte as your counter, and observe values going beyond 160-bit value:
But then, the big question is: why the first value does not begin with "30"? I don't know, maybe the counter also increments some bits at the beginning? I will try to check some other valid points around that, to confirm, why they could be skipped.

Edit: Do you know any other magic value than 76439, that was used to produce "random, but not quite" numbers? I know how it was used in secp112r1, and I can even expand it, but still, I cannot find anything useful:
You can concatenate all of that, and multiply again by 76439, then you will see just a huge number, close to 2^N.

Edit: In sect113r1, when we calculate half of the base point, then we can find very small x-value:
This Sage code can give us this point:
Which means, my idea of starting from x=1, and incrementing that, is closer to the reality, than I thought.

Edit: I found a new hint: each of those hashes is a valid x-value on a curve, where p=0xfffffffffffffffffffffffffffffffeffffac73, that is used in secp160k1. I reached those points:

Edit: There is a better pattern: all values can be taken modulo p=0xfffffffffffffffffffffffffffffffeffffac73 (used in secp160k1), and then, it is a valid x-value on that curve:
Which means, the only values that we can pick from, is when p-value from secp160k1 can be intersected with p-value from another curve, and form a valid x-value on both.

Why would a person generating seeds to be used in standardized elliptic curves derive it from such a simple sentence or phrase? Considering how brainwallets have been broken into (and those used SHA256), isn't that a bit unsafe?

It would be far more secure to generate them from a sequence of - given enough entropy - random bytes. In 1970s - 80s it would not be so difficult to calculate SHA1 of any bytes input given suitable hardware.

It seems that person generated a lot of seeds (I found 13), but I cannot see the pattern in other values. Maybe I should list all seeds from https://secg.org/SEC2-Ver-1.0.pdf to get all of them in a single place:

Edit: Interestingly, the movement between sect131r1 and sect131r2 sounds like a single call to some "seed transformation function":
First, let's remove "MinghuaQu":
And then, note that going from "seed for sect131r1" to "seed for sect131r2" is all about shifting bits, and incrementing the result:
See? I will try to write some code, maybe similar operation was simply done in a loop, and after some iterations, those seeds look like some hash, but maybe there was no hashing at all?

Edit: In other curves, half of the base point also has surprisingly low x-coordinate. For example, sect163k1 has something like that:
And then, after checking different private keys, we can see something like that:

Edit: Another interesting thing is all of those "object identifiers". Some of them are missing, but I think this is just the order in which those curves were created.

ChatGPT used with GPT-4 has a plugin for calculating math equations that connects it directly to Wolfram | Alpha, so that should improve the accuracy of these things dramatically. Though I doubt it can do cryptographic stuff like SHA-1. Or anything that Sage can do.

I have never used it myself, because it is a feature for paid ChatGPT users. Although I do use ChatGPT almost every day, for other use cases, $20/month is a bit large for a subscription.

I told you to avoid AI. Here, you have a loop, that repeats things 20,000,000 times, for absolutely no reason. You have 8 examples. So, that means your code is 2,500,000 times slower than it should be, because that loop is not used at all to modify anything!

https://words.filippo.io/dispatches/seeds-bounty/
Also, I told you there is not more than thousands of hashes, so if you use brute force on anything bigger than 16-bit, it is probably wrong.

Currently, that "overlord" can only repeat things, that were put there by other humans. Which means, if the plaintext for those hashes was never in the training set, it is very unlikely that AI will deduce it. You could get a better result by feeding a model with some data from 1990-2000, or by teaching it first, how to break things with already known solutions. You could be surprised, how hard it is to teach any model to compute simple things, like counting points on some elliptic curve with p<1000. It will probably tell you "this is a complicated process", because that's what people said about it, and that's what was present in some training data.

Also, you can read what gmaxwell wrote about AI: https://nt4tn.net/articles/aixy.html

Yes. I guess they incremented the hash, instead of incrementing the data and rehashing it. But still, I don't know, what is the value after hashing. I can guess it is around "0554123b78ce563f89a0ed9414f5aa28ad0d96d6795f9c66", and it has at least 192 bits (who knows, maybe even 256 bits?), but then is mixed in some way, and cut at the beginning and in the end, by applying modulo (dropping the first bits with modulo is easy, but the last bits may be a little bit different, if you have "ffff" or "fffe" in the end of your q-value, but still, I don't know the exact q-value in this case).

And then, if "e=H", that means the hash is left unchanged, and simply converted into N-bit number. Then, we have t-value as modulo "2*q". Then, u-value is just modulo "q", which means that I don't understand it, because you can use modulo "q" from the start, and get the same result. So, what is q-value?

Edit: Also, I noticed some values look randomly, but if you multiply them by some magic number, then they are quite simple. For example:
This is officially used in secp112r1, as well as in some other curves. Which means, maybe multiplying a seed by some number will give us some hints?

Right, that's why I think it's likely that the solution to this 'random curve'  question is likely to give hits for the secp256k1 G question-- I bet their seeds are similar.  But checking that procedure, it tells you to increment C when it doesn't land on the curve which doesn't explain the values we're seeing in the varrious k-curves.  If they used that procedure the different curves G wouldn't share so many bits in common.

As far as the hash function. SHA-1 makes sense because it's used for the 'random curve' stuff. Ripemd160 would be very surprising.

I see in the prior thread people wondering why the mystery point with the small x was doubled. This isn't a huge mystery to me. 

Many of the curves generated at the same time were generated 'randomly', and they involved taking the output from sha1.  When you have a candidate point created from a hash you're supposed to multiply it by the curve's cofactor to extinguish the subgroup. In the case of the characteristic-2 curves that means doubling it.  I think it's completely credible that someone just reused some code that doubled it even though it wasn't needed in secp256k1.   It also make the value look 'random-ish' which might have been perceived to have some value against sidechannel attacks.

As far as other operations that could have been performed,  all the obvious ones would be operations in the field P.  But since P is different for the different curves, the values wouldn't be the same.  It seems possible to me that some natural operation (like a sqrt of a simple constant) was done in the 160-bit field then the result lifted to the other field... but since they were using sha1 for the 'random' curves using a hash seems more likely to me.


ha. I never looked at them laid out that way before.

I believe the reason they're not all the same is that the magic value the author intended to use wasn't on the curve and required modification.  A randomly selected field element has a 50% chance of being on the curve.   Though from looking at those values it's far from clear to me what process was used (as you should only need to try a very small number).

That is the problem: nobody knows the algorithm! Which means, I can give you some hint, but it could be totally wrong. But if you want to get some random hint, here it is: https://en.bitcoin.it/wiki/Proof_of_work#Example

Also, it is not that random, as you could expect, because Steve Weis gave us those hints on his page: https://saweis.net/posts/nist-curve-seed-origins.html
Which means, people believe it is just SHA-1, executed on a similar string than "Hello, world!" in this SHA-256 example, but for SHA-1 instead.

You mean ChatGPT? Good luck, I tried basic calculations, and it failed many times. For example:

Let me know, if you successfully force any AI to compute things like "0x5a827999^2=0x1fffffff4d25fd71" correctly. And not only for this example, but for all of them, for example if you ask for the first five rounds of SHA-1, it should calculate all of them correctly, without hallucinations like that one above.

I don't know. This is the whole problem, that the algorithm is missing. Also, you probably shouldn't get too deep in your algorithm, because if it was some kind of hashing, it is believed that there were no more than thousands of hashes, so you shouldn't try to check for example 2^32 hashes or more (of course you can, nobody will stop you, but it is very unlikely that the solution is there).

Edit: If you need more hints for seeding without hashing, I can give you another one: pick some Solinas prime, and try to form a valid curve. Then, based on p-value, you can get some n-value that looks randomly, but is fully deterministic. For example:
Of course, all of those examples use y^2=x^3+7, but you can try different a-values or b-values if you want.

🖤

So, what changed since then? Well, I learned, how to use Sage, to calculate n-value, based on p-value, and started exploring point counting algorithms. But I am not there yet, to roll my own implementation from scratch. However, based on some revealed seeds, for example those containing "MinghuaQu", I am more confident, that no hashing was there, and all numbers were produced just from simple operations. For example, someone could start with some simple string like "Alice and Bob", and then it was mixed by the algorithm, used to generate elliptic curves, without any hashing: https://saweis.net/posts/nist-curve-seed-origins.html

Found this today, thought it might be useful for some of you to know about this challenge.
https://www.bleepingcomputer.com/news/security/bounty-offered-for-secret-nsa-seeds-behind-nist-elliptic-curves-algo/
Share the results of your research please.