Bounty offered to crack the seeds for NIST curves!

[digaran]

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.

[1714254265]

1714254265

[1714254265]

1714254265

[1714254265]

1714254265

[1714254265]

1714254265

[garlonicon]

Share the results of your research please.

I already did, for example here:

Is it just because this is the case for secp256k1

Yes, but by doing it in this way, it can also reveal the procedure for smaller elliptic curves, for example secp160k1, secp192k1, and secp224k1. It is also about solving the mystery behind the half of the base point:

Code:

u1=        48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (160-bit)
u2=0554123b78ce563f89a0ed9414f5aa28ad0d96d6795f9c66 (192-bit)
u3=      3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (224-bit)
u4=      3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (256-bit)

Few months ago, I thought x-value is some kind of hash, potentially having more than 160 bits (for example 192 bits). However, when I tried to implement everything by myself from scratch, I discovered more interesting things. For smaller values, the whole procedure of generating a curve does not involve hashing at all! It is not needed. It is described in PDFs, but if you want to generate any curve with certain properties, you don't have to implement any hash function. So, I wonder if that was the case in secp256k1. Maybe the creator didn't implement any hashing, and all values we can see, are just produced by taking modulo square roots, modulo cube roots, counting "n" based on "p", and things like that?

Some example: you pick some "p", as in secp256k1. Then you calculate the only valid "n" for that "p". And then, if you observe the last 128 bits of "n", and take only that, then you cannot see, if it was some result of some 128-bit hash function or not.

Code:

p=ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
n=ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
                              n%2^128=baaedce6 af48a03b bfd25e8c d0364141

Then, by seeing only "baaedce6 af48a03b bfd25e8c d0364141" you could think "hey, someone just used 128-bit hash function here". But what if this was not the case? Another interesting thing is that according to PDFs, the base point is picked after calculating "n". However, in my code, it is now done the other way around: first I pick some base point, and then I can reach "n". So, I still have to learn, how it is possible to calculate "n" without touching any points (because if you touch some of them, then why not make it a base point? Unless the creator thought that picking x=1 was unsafe, and getting temporary points, and then discarding them, is needed anyway).

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

[digaran]

🖤

[garlonicon]

any suggestions on how to get started to find the seeds, such as any script etc?

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

Code:

SEED = SHA1("Jerry deserves a raise.")
SEED = SHA1("Jerry and Bob need raises123")

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.

I will try a world dominating AI to derive a script out of it.

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

garlonicon: 0x5a827999^2=
chatgpt: The result of the calculation (0x5a827999)^2 is 0x24d51b25d6818281. The value "0x" means that the number is written in hexadecimal format.

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.

didn't MinghuaQu generate secp256k1 seeds?

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:

Code:

solinas=2^320
p=ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffbba5
n=ffffffff ffffffff ffffffff ffffffff ffffffff 45a1c45c 1aa3030e 97fde313 13520aba 558cb47f
seed=45a1c45c 1aa3030e 97fde313 13520aba 558cb47f

solinas=2^320-2^32
p=ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffe4f5f
n=ffffffff ffffffff ffffffff ffffffff ffffffff a53570ca 38253ef0 ec60cabe 11c55bee 7ddd8087
seed=a53570ca 38253ef0 ec60cabe 11c55bee 7ddd8087

solinas=2^320-2^64
p=ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff fffa3685
n=ffffffff ffffffff ffffffff ffffffff fffffffe 9556a9d8 65ad4ef3 00c2bcea 45b86ce1 457089bd
seed=9556a9d8 65ad4ef3 00c2bcea 45b86ce1 457089bd

solinas=2^320-2^96
p=  ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff fffffd31
n=1 00000000 00000000 00000000 00000000 00000001 f6466e59 2434ac3d e48b5582 e4530277 dc65aa85
seed=f6466e59 2434ac3d e48b5582 e4530277 dc65aa85

solinas=2^320-2^128
p=ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff ffffffff ffff57e9
n=ffffffff ffffffff ffffffff ffffffff fffffffe caf64985 4e6562db 1a348096 746f91fc 85750ab7
seed=caf64985 4e6562db 1a348096 746f91fc 85750ab7

solinas=2^320-2^160
p=ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff ffffffff ffffffff ffffb927
n=ffffffff ffffffff ffffffff ffffffff fffffffd 5ca0d67b 8ba9146c 6c6d3c3c 44156239 1744ce41
seed=5ca0d67b 8ba9146c 6c6d3c3c 44156239 1744ce41

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.

[gmaxwell]

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.

Share the results of your research please.

I already did, for example here:

Code:

u1=        48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (160-bit)
u2= 0554123b78ce563f89a0ed9414f5aa28ad0d96d6795f9c66 (192-bit)
u3=             3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (224-bit)
u4=             3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (256-bit)

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).

[garlonicon]

it's far from clear to me what process was used

My best guess is this one, but I don't know the seed:

First, start with some drafts, like this one: https://secg.org/sec1-v1.99.dif.pdf
Then, go to "3.1.3.2 Point Selection". You can CTRL+F the word "seed", and try to find places, where that seed is hashed.

Code:

A="Base point"
A=4261736520706f696e74
B=01
C=01
H=Hash(A||B||C||S)=Hash(4261736520706f696e740101||S)
e=H
t=e%(2*q)
u=t%q
z=t/q
u=00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
x=00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63
y=C0C686408D517DFD67C2367651380D00D126E4229631FD03F8FF35EEF1A61E3C
G=hR
h=2
G=2*(0400000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63C0C686408D517DFD67C2367651380D00D126E4229631FD03F8FF35EEF1A61E3C)
G=0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

We can guess that there was another elliptic curve, with h=2 (and for that reason the point is doubled), and there was probably some 160-bit seed S, used to derive it. Guessing the seed is extremely hard, but it is possible to be lucky, and to check seeds for existing curves, trying to find some match.

Also, because many times errors are grouped, you can try to look at places, where something was generated in another way than it should be. For example, open: https://secg.org/SEC2-Ver-1.0.pdf

There, you can find "3.4.2 Recommended Parameters sect163r1", where you have an information, that something was generated in a slightly different way.

However for historical reasons the method used to generate E from S differs slightly from the method described in ANSI X9.62 [1]. Specifically the coefficient b produced from S is the reverse of the coefficient that would have been produced by the method described in ANSI X9.62.

So, you can try seed "S=24B7B137 C8A14D69 6E676875 6151756F D0DA2E5C" and generate some hashes. Another thing is that we can guess SHA-1 was used, but it could be RIPEMD-160 or any other 160-bit hash function as well. Or, the endianness could be swapped, or things like that could happen in the middle.

[gmaxwell]

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.

[garlonicon]

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

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).

Code:

H=Hash(A||B||C||S)=Hash(4261736520706f696e740101||S)
e=H
t=e%(2*q) //what is q-value?
u=t%q
z=t/q
u=00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

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:

Code:

p=0xDB7C2ABF62E35E668076BEAD208B
p=(2^128-3)/76439
p*76439=p*0x12a97=0xfffffffffffffffffffffffffffffffd

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?

[garlonicon]

Code:

for i in range(20000000):

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/

The counter has to be there because only one in every 192 to 521 hashes is actually good to make a curve out of, depending the bit size of the curve. (This is because one in every ln(N) numbers less than N is prime, for large enough N.) There’s a 99% chance the counter is less than 2400 for the largest curve, and less than 1175 for P-256.

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.

our future overlord(lol)

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

[NotATether]

I will try a world dominating AI to derive a script out of it.

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

garlonicon: 0x5a827999^2=
chatgpt: The result of the calculation (0x5a827999)^2 is 0x24d51b25d6818281. The value "0x" means that the number is written in hexadecimal format.

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.

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.

[garlonicon]

didn't MinghuaQu generate secp256k1 seeds?

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:

Code:

00F50B02 8E4D696E 67687561 51752904 72783FB1   secp112r1 (MinghuaQu)
002757A1 114D696E 67687561 51755316 C05E0BD4   secp112r2 (MinghuaQu)
000E0D4D 696E6768 75615175 0CC03A44 73D03679   secp128r1 (MinghuaQu)
004D696E 67687561 517512D8 F03431FC E63B88F4   secp128r2 (MinghuaQu)
1053CDE4 2C14D696 E6768756 1517533B F3F83345   secp160r1 (MinghuaQu)
B99B99B0 99B323E0 2709A4D6 96E67687 56151751   secp160r2 (MinghuaQu)
3045AE6F C8422F64 ED579528 D38120EA E12196D5   secp192r1, P-192 (challenge)
BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5   secp224r1, P-224 (challenge)
C49D3608 86E70493 6A6678E1 139D26B7 819F7E90   secp256r1, P-256 (challenge)
A335926A A319A27A 1D00896A 6773A482 7ACDAC73   secp384r1, P-384 (challenge)
D09E8800 291CB853 96CC6717 393284AA A0DA64BA   secp521r1, P-521 (challenge)
10E723AB 14D696E6 76875615 1756FEBF 8FCB49A9   sect113r1 (MinghuaQu)
10C0FB15 760860DE F1EEF4D6 96E67687 5615175D   sect113r2 (MinghuaQu)
4D696E67 68756151 75985BD3 ADBADA21 B43A97E2   sect131r1 (MinghuaQu)
985BD3AD BAD4D696 E6768756 15175A21 B43A97E3   sect131r2 (MinghuaQu)
24B7B137 C8A14D69 6E676875 6151756F D0DA2E5C   sect163r1 (MinghuaQu)
85E25BFE 5C86226C DB12016F 7553F9D0 E693A268   sect163r2 (?)
103FAEC7 4D696E67 68756151 75777FC5 B191EF30   sect193r1 (MinghuaQu)
10B7B4D6 96E67687 56151751 37C8A16F D0DA2211   sect193r2 (MinghuaQu)
74D59FF0 7F6B413D 0EA14B34 4B20A2DB 049B50C3   sect233r1 (?)
77E2B073 70EB0F83 2A6DD5B6 2DFC88CD 06BB84BE   sect283r1 (?)
4099B5A4 57F9D69F 79213D09 4C4BCD4D 4262210B   sect409r1 (?)
2AA058F7 3A0E33AB 486B0F61 0410C53A 7F132310   sect571r1 (?)

Edit: Interestingly, the movement between sect131r1 and sect131r2 sounds like a single call to some "seed transformation function":

Code:

4D696E67 68756151 75985BD3 ADBADA21 B43A97E2   sect131r1 (MinghuaQu)
985BD3AD BAD4D696 E6768756 15175A21 B43A97E3   sect131r2 (MinghuaQu)

First, let's remove "MinghuaQu":

Code:

________ ________ __985BD3 ADBADA21 B43A97E2   sect131r1 (MinghuaQu)
985BD3AD BAD_____ ________ _____A21 B43A97E3   sect131r2 (MinghuaQu)

And then, note that going from "seed for sect131r1" to "seed for sect131r2" is all about shifting bits, and incrementing the result:

Code:

________ ________ __985BD3 ADBADA21 B43A97E2 //seed for sect131r1
985BD3ADBADA21B43A97E2                       //tail of the seed for sect131r1
985BD3ADBAD A21B43A97E2                      //split in half
985BD3ADBAD __________________ A21B43A97E2   //insert "MinghuaQu" in the middle
985BD3ADBAD __________________ A21B43A97E3   //increment it
985BD3AD BAD_____ ________ _____A21 B43A97E3 //seed for sect131r2

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:

Code:

F.<x> = GF(2)[]
K = GF(2^163, name="x", modulus= x^163 +  x^7 +  x^6 +  x^3 + 1)
E = EllipticCurve(K, (1, K.from_integer(0x000000000000000000000000000000000000000001), 0, 0, K.from_integer(0x000000000000000000000000000000000000000001)))
E.set_order(0x04000000000000000000020108a2e0cc0d99f8a5ef * 0x2)
G = E(K.from_integer(0x02fe13c0537bbc11acaa07d793de4e6d5e5c94eee8), K.from_integer(0x0289070fb05d38ff58321f2e800536d538ccdaa3d9))
private_key = 0x200000000000000000001008451706606ccfc52f7
P = private_key*G
print(hex(P[0].to_integer()),hex(P[1].to_integer()))

And then, after checking different private keys, we can see something like that:

Code:

+-------------------------------------------------------------------------------------------+---------------------------------------------+
|                                         public key                                        | private key                                 |
+---------------------------------------------+---------------------------------------------+                                             |
|                                     x-value |                                     y-value |                                             |
+---------------------------------------------+---------------------------------------------+---------------------------------------------+
| 0x2fe13c0537bbc11acaa07d793de4e6d5e5c94eee8 | 0x289070fb05d38ff58321f2e800536d538ccdaa3d9 | 0x1                                         |
|  0xcb5ca2738fe300aacfb00b42a77b828d8a5c41eb | 0x229c79e9ab85f90acd3d5fa3a696664515efefa6b | 0x2                                         |
+---------------------------------------------+---------------------------------------------+---------------------------------------------+
| 0x5642ec3580430b71c51a33ea17b6fd6d8d5971338 | 0x16cb2d0f9d2e66aacdf0379157fc79e4bf4ac2e44 | 0x200000000000000000001008451706606ccfc52f6 |
|          0x23e21d6019e1211f6bd47ec180256e97 | 0x1055096ab0cce03fdb8ba9bf2d02e94a1205eee5e | 0x200000000000000000001008451706606ccfc52f7 |
|          0x23e21d6019e1211f6bd47ec180256e97 | 0x1055096ab2f2c1e9da15bbaedbbfaea60a07b80c9 | 0x200000000000000000001008451706606ccfc52f8 |
| 0x5642ec3580430b71c51a33ea17b6fd6d8d5971338 | 0x4089c13a1d6d6ddb08ea047b404a84893213b3d7c | 0x200000000000000000001008451706606ccfc52f9 |
+---------------------------------------------+---------------------------------------------+---------------------------------------------+
| 0x2fe13c0537bbc11acaa07d793de4e6d5e5c94eee8 |  0x7714cfe32684eef49818f913db78b866904e4d31 | 0x4000000000000000000020108a2e0cc0d99f8a5ee |
|                                         0x0 |                                         0x1 | 0x4000000000000000000020108a2e0cc0d99f8a5ef |
| 0x2fe13c0537bbc11acaa07d793de4e6d5e5c94eee8 | 0x289070fb05d38ff58321f2e800536d538ccdaa3d9 | 0x4000000000000000000020108a2e0cc0d99f8a5f0 |
+---------------------------------------------+---------------------------------------------+---------------------------------------------+

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.

Code:

sect163k1 OBJECT IDENTIFIER ::= { ellipticCurve 1 }
sect163r1 OBJECT IDENTIFIER ::= { ellipticCurve 2 }
sect239k1 OBJECT IDENTIFIER ::= { ellipticCurve 3 }
sect113r1 OBJECT IDENTIFIER ::= { ellipticCurve 4 }
sect113r2 OBJECT IDENTIFIER ::= { ellipticCurve 5 }
secp112r1 OBJECT IDENTIFIER ::= { ellipticCurve 6 }
secp112r2 OBJECT IDENTIFIER ::= { ellipticCurve 7 }
secp160r1 OBJECT IDENTIFIER ::= { ellipticCurve 8 }
secp160k1 OBJECT IDENTIFIER ::= { ellipticCurve 9 }
secp256k1 OBJECT IDENTIFIER ::= { ellipticCurve 10 }

sect163r2 OBJECT IDENTIFIER ::= { ellipticCurve 15 }
sect283k1 OBJECT IDENTIFIER ::= { ellipticCurve 16 }
sect283r1 OBJECT IDENTIFIER ::= { ellipticCurve 17 }

sect131r1 OBJECT IDENTIFIER ::= { ellipticCurve 22 }
sect131r2 OBJECT IDENTIFIER ::= { ellipticCurve 23 }
sect193r1 OBJECT IDENTIFIER ::= { ellipticCurve 24 }
sect193r2 OBJECT IDENTIFIER ::= { ellipticCurve 25 }
sect233k1 OBJECT IDENTIFIER ::= { ellipticCurve 26 }
sect233r1 OBJECT IDENTIFIER ::= { ellipticCurve 27 }
secp128r1 OBJECT IDENTIFIER ::= { ellipticCurve 28 }
secp128r2 OBJECT IDENTIFIER ::= { ellipticCurve 29 }
secp160r2 OBJECT IDENTIFIER ::= { ellipticCurve 30 }
secp192k1 OBJECT IDENTIFIER ::= { ellipticCurve 31 }
secp224k1 OBJECT IDENTIFIER ::= { ellipticCurve 32 }
secp224r1 OBJECT IDENTIFIER ::= { ellipticCurve 33 }
secp384r1 OBJECT IDENTIFIER ::= { ellipticCurve 34 }
secp521r1 OBJECT IDENTIFIER ::= { ellipticCurve 35 }
sect409k1 OBJECT IDENTIFIER ::= { ellipticCurve 36 }
sect409r1 OBJECT IDENTIFIER ::= { ellipticCurve 37 }
sect571k1 OBJECT IDENTIFIER ::= { ellipticCurve 38 }
sect571r1 OBJECT IDENTIFIER ::= { ellipticCurve 39 }

secp192r1 OBJECT IDENTIFIER ::= { ansi-X9-62 curves(3) prime(1) 1 }
secp256r1 OBJECT IDENTIFIER ::= { ansi-X9-62 curves(3) prime(1) 7 }

[NotATether]

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.

[garlonicon]

Why would a person generating seeds to be used in standardized elliptic curves derive it from such a simple sentence or phrase?

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.

Considering how brainwallets have been broken into (and those used SHA256), isn't that a bit unsafe?

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".

It would be far more secure to generate them from a sequence of - given enough entropy - random bytes.

Code:

3045AE6F C8422F64 ED579528 D38120EA E12196D5   secp192r1, P-192 (challenge)
BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5   secp224r1, P-224 (challenge)
C49D3608 86E70493 6A6678E1 139D26B7 819F7E90   secp256r1, P-256 (challenge)
A335926A A319A27A 1D00896A 6773A482 7ACDAC73   secp384r1, P-384 (challenge)
D09E8800 291CB853 96CC6717 393284AA A0DA64BA   secp521r1, P-521 (challenge)

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.

In 1970s - 80s it would not be so difficult to calculate SHA1 of any bytes input given suitable hardware.

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:

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

I found a pattern, but I don't know, how to continue that.

Code:

u1=        48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (160-bit)
u2=0554123b78ce563f89a0ed9414f5aa28ad0d96d6795f9c66 (192-bit)
u3=      3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (224-bit)
u4=      3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (256-bit)

Subtract u1 from all other values, to make it more clear:

Code:

u1=        48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (160-bit)
u2=0554123b3000000000000000000000000000000000000004 (192-bit)
u3=      3b3000000000000000000000000000000000000001 (224-bit)
u4=      3b3000000000000000000000000000000000000001 (256-bit)

And then, split it:

Code:

u2=05 54 12 3b 30000000000000000000000000000000000000 04 (192-bit)
u3=         3b 30000000000000000000000000000000000000 01 (224-bit)
u4=         3b 30000000000000000000000000000000000000 01 (256-bit)

Then, treat the last byte as your counter, and observe values going beyond 160-bit value:

Code:

+---------+-------------------------------------------+
| counter | values                                    |
+---------+-------------------------------------------+
| 00      | nothing (or truncated, because of modulo) |
| 01      | 3b                                        |
| 02      | 3b 12                                     |
| 03      | 3b 12 54                                  |
| 04      | 3b 12 54 05                               |
+---------+-------------------------------------------+

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:

Code:

db7c2abf 62e35e66 8076bead 208b
00029274 803e28aa 1b338164 3c07
61a10007 b75d80ba 79fe519a 842c
b41624e3 00172618 822f6dfa f4cf
8c861c42 6ea90045 7249868e 49f0
de6ea592 54c74bfb 00d056dc 93aa
ddd29b4b f0b6fe55 e3f10271 0495
bb009977 d1e3d224 fb01abd3 0753

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:

Code:

F.<x> = GF(2)[]
K = GF(2^113, name="x", modulus= x^113 +  x^9 + 1)
E = EllipticCurve(K, (1, K.from_integer(0x003088250ca6e7c7fe649ce85820f7), 0, 0, K.from_integer(0x00e8bee4d3e2260744188be0e9c723)))
E.set_order(0x0100000000000000d9ccec8a39e56f * 0x2)
G = E(K.from_integer(0x009d73616f35f4ab1407d73562c10f), K.from_integer(0x00a52830277958ee84d1315ed31886))
private_key = 0x800000000000006ce676451cf2b8
P = private_key*G
print(hex(P[0].to_integer()),hex(P[1].to_integer()))

This Sage code can give us this point:

Code:

0x3 0x1a7078c5d29ee7ea6e8ff326518f5

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:

Code:

02 3045ae6fc8422f64ed579528d38120eae12196d5 33f505091031a9f3fedf0de27523b755af69cd72
03 3045ae6fc8422f64ed579528d38120eae12196d5 cc0afaf6efce560c0120f21d8adc48a95095df01

02 bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5 6441e8714d66ae3077e617136353a8d0bdc56318
03 bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5 9bbe178eb29951cf8819e8ec9cac572e423a495b

02 c49d360886e704936a6678e1139d26b7819f7e90 d40dfa96a30216857f8d0a768e1bfb7e7efbca98
03 c49d360886e704936a6678e1139d26b7819f7e90 2bf205695cfde97a8072f58971e404808103e1db

02 a335926aa319a27a1d00896a6773a4827acdac73 7a8d7a04b47ca665132a5a98fbd950c69a328a90
03 a335926aa319a27a1d00896a6773a4827acdac73 857285fb4b83599aecd5a5670426af3865cd21e3

02 d09e8800291cb85396cc6717393284aaa0da64ba d8b87c1b9c2eb455f3804ce0689368de2c43028c
03 d09e8800291cb85396cc6717393284aaa0da64ba 274783e463d14baa0c7fb31f976c9720d3bca9e7

Edit:

I found a pattern, but I don't know, how to continue that.

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:

Code:

0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 0x432562b5328ba8c0aafef5109384b4e43b2503a9
0x78ce563f89a0ed9414f5aa28b261aaceaa96c7e5 0x6a6fa7d9499c6d862b24baf53a2b96f32c0ba1be
0x78ce563f89a0ed9414f5aa28ad0d97117972dde2 0x66392754d8b777e0414311d3eae3863189951c23

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.

[CrunchyF]

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 "|"

Code:

generator | ./cuda_hasher_sha1

would be the more convenient but i don't think than it can support such a speed

[garlonicon]

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

Code:

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

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.

[ecdsa123]

Edit:

I found a pattern, but I don't know, how to continue that.

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:

Code:

0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 0x432562b5328ba8c0aafef5109384b4e43b2503a9
0x78ce563f89a0ed9414f5aa28b261aaceaa96c7e5 0x6a6fa7d9499c6d862b24baf53a2b96f32c0ba1be
0x78ce563f89a0ed9414f5aa28ad0d97117972dde2 0x66392754d8b777e0414311d3eae3863189951c23

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.

It feels amazing to see smart people at work especially when they achieve something which you couldn't.
I was trying to figure out a way to find valid points on different curves, however my attempt is to map a point from a 256 bit curve to a point on a much smaller curve like 160, 96 or even 64 bit.
What you are doing is a start and I believe it can lead to great discoveries about mathematical properties of elliptic curves.

@Digaran:

"find valid points on different curves, however my attempt is to map a point from a 256 bit curve to a point on a much smaller curve like 160, 96 or even 64 bit" it is not a problem, becouse we are working in modulo1 and modulo 2 -> for playing beetween the differenst curves -> we are using crt -> with linear cooefs.

I have implemented after One year testing ,and it is working.

if you would like to I can share with you the code , it could be nice if you can some funds like 0,2 btc for my an address for hard working.

[vjudeu]

It seems that person generated a lot of seeds (I found 13)

There are more MinghuaQu seeds, for example here: https://www.certicom.com/content/certicom/en/curves-list.html

Code:

D3E5D53A 4D696E67 68756151 757779B8 379AC409   ECC2-79 seedE (MinghuaQu)
50CBF1D9 5CA94D69 6E676875 615175F1 6A36A3B1   ECC2-79 seedP (MinghuaQu)
4EC95934 D696E676 87561517 56D5D2A8 FCD02E68   ECC2-79 seedQ (MinghuaQu)

F1DCCA0F F8B74D69 6E676875 6151754B B21CD49C   ECC2-89 seedE (MinghuaQu)
EE37E551 34D696E6 76875615 17502BE9 9063A9F7   ECC2-89 seedP (MinghuaQu)
FD26A4D6 96E67687 5615175E 8B00ABB8 D1EA4015   ECC2-89 seedQ (MinghuaQu)

2B354920 B724D696 E6768756 1517585B A1332DC8   ECC2-97 seedE (MinghuaQu)
21BD8EAF 4D696E67 68756151 75BD8678 E00A46B2   ECC2-97 SeedP (MinghuaQu)
315ADA96 4D696E67 68756151 7535FA24 CBF48397   ECC2-97 SeedQ (MinghuaQu)

50CBF1D9 5CA94D69 6E676875 615175F1 6A36A3B8   ECC2K-95 seedP (MinghuaQu)
4D696E67 68756151 75037272 26FEE987 E96A11FC   ECC2K-95 seedQ (MinghuaQu)

4D696E67 68756151 75037272 26FEE987 E96A11FD   ECC2-109 seedE (MinghuaQu)
1DD8F2C7 84D696E6 76875615 175A36EF 3F72194E   ECC2-109 seedP (MinghuaQu)
A57C94DF 4D696E67 68756151 75E8B486 4BC74FFB   ECC2-109 seedQ (MinghuaQu)

078AB942 84D696E6 76875615 175A36EF 3F7298E2   ECC2K-108 seedP (MinghuaQu)
176894DF 4D696E67 68756151 75E8B486 4BC74261   ECC2K-108 seedQ (MinghuaQu)

8950783D 4D696E67 68756151 750A6732 71EA86E3   ECC2-131 seedE (MinghuaQu)
B5555555 5554D696 E6768756 1517586A A17BF3F4   ECC2-131 seedP (MinghuaQu)
19D059FF E6124D69 6E676875 61517565 06A34421   ECC2-131 seedQ (MinghuaQu)

092FE1A8 9014D696 E6768756 1517586A A17BF123   ECC2K-130 seedP (MinghuaQu)
328D0AE9 E6124D69 6E676875 61517565 06A34A25   ECC2K-130 seedQ (MinghuaQu)

D2C0FB15 760860DE F1EEF4D6 96E67687 56151754   ECC2-163 seedE (MinghuaQu)
C368944D 696E6768 75615175 FF31C825 CC82534A   ECC2-163 seedP (MinghuaQu)
DFD5F8E2 E38F4D69 6E676875 615175F3 B5115321   ECC2-163 seedQ (MinghuaQu)

4D696E67 68756151 75037272 26FEE987 E96A11FD   ECC2K-163 seedP (MinghuaQu)
6BA57515 8BDAF0D9 694D696E 67687561 517574BB   ECC2K-163 seedQ (MinghuaQu)

4E13CA54 2744D696 E6768756 1517552F 279A8C84   ECC2-191 seedE (MinghuaQu)
FD6F9C51 55B4D696 E6768756 15175BB2 BBBEB67B   ECC2-191 seedP (MinghuaQu)
77733A8F C54D696E 67687561 517539F6 FEB6390C   ECC2-191 seedQ (MinghuaQu)

D34B9A4D 696E6768 75615175 CA71B920 BFEFB05D   ECC2-238 seedE (MinghuaQu)
F7930DE1 C514D696 E6768756 15175155 35EAEA7E   ECC2-238 seedP (MinghuaQu)
315ADA96 4D696E67 68756151 7535FA24 CBF48396   ECC2-238 seedQ (MinghuaQu)

D9037BB3 2E4D696E 67687561 51757738 894AE594   ECC2K-238 seedP (MinghuaQu)
2AC709C3 E56AD814 D696E676 87561517 5551F2EC   ECC2K-238 seedQ (MinghuaQu)

2B354920 B724D696 E6768756 1517585B A1332DC6   ECC2-353 seedE (MinghuaQu)
1DD8F2C7 84D696E6 76875615 175A36EF 3F721942   ECC2-353 seedP (MinghuaQu)
A57C94DF 4D696E67 68756151 75E8B486 4BC74FF8   ECC2-353 seedQ (MinghuaQu)

91CB22C7 84D696E6 76875615 175A36EF 670D2FB1   ECC2K-358 seedP (MinghuaQu)
90FA2BDF 4D696E67 68756151 75E8B486 4BC74AA5   ECC2K-358 seedQ (MinghuaQu)

If you remove "MinghuaQu", you will see that:

Code:

D3E5D53A ________ ________ __7779B8 379AC409   ECC2-79 seedE (MinghuaQu)
50CBF1D9 5CA9____ ________ ______F1 6A36A3B1   ECC2-79 seedP (MinghuaQu)
4EC9593_ ________ ________ _6D5D2A8 FCD02E68   ECC2-79 seedQ (MinghuaQu)

F1DCCA0F F8B7____ ________ ______4B B21CD49C   ECC2-89 seedE (MinghuaQu)
EE37E551 3_______ ________ ___02BE9 9063A9F7   ECC2-89 seedP (MinghuaQu)
FD26A___ ________ _______E 8B00ABB8 D1EA4015   ECC2-89 seedQ (MinghuaQu)

2B354920 B72_____ ________ _____85B A1332DC8   ECC2-97 seedE (MinghuaQu)
21BD8EAF ________ ________ __BD8678 E00A46B2   ECC2-97 SeedP (MinghuaQu)
315ADA96 ________ ________ __35FA24 CBF48397   ECC2-97 SeedQ (MinghuaQu)

50CBF1D9 5CA9____ ________ ______F1 6A36A3B8   ECC2K-95 seedP (MinghuaQu)
________ ________ __037272 26FEE987 E96A11FC   ECC2K-95 seedQ (MinghuaQu)

________ ________ __037272 26FEE987 E96A11FD   ECC2-109 seedE (MinghuaQu)
1DD8F2C7 8_______ ________ ___A36EF 3F72194E   ECC2-109 seedP (MinghuaQu)
A57C94DF ________ ________ __E8B486 4BC74FFB   ECC2-109 seedQ (MinghuaQu)

078AB942 8_______ ________ ___A36EF 3F7298E2   ECC2K-108 seedP (MinghuaQu)
176894DF ________ ________ __E8B486 4BC74261   ECC2K-108 seedQ (MinghuaQu)

8950783D ________ ________ __0A6732 71EA86E3   ECC2-131 seedE (MinghuaQu)
B5555555 555_____ ________ _____86A A17BF3F4   ECC2-131 seedP (MinghuaQu)
19D059FF E612____ ________ ______65 06A34421   ECC2-131 seedQ (MinghuaQu)

092FE1A8 901_____ ________ _____86A A17BF123   ECC2K-130 seedP (MinghuaQu)
328D0AE9 E612____ ________ ______65 06A34A25   ECC2K-130 seedQ (MinghuaQu)

D2C0FB15 760860DE F1EEF___ ________ _______4   ECC2-163 seedE (MinghuaQu)
C36894__ ________ ________ FF31C825 CC82534A   ECC2-163 seedP (MinghuaQu)
DFD5F8E2 E38F____ ________ ______F3 B5115321   ECC2-163 seedQ (MinghuaQu)

________ ________ __037272 26FEE987 E96A11FD   ECC2K-163 seedP (MinghuaQu)
6BA57515 8BDAF0D9 69______ ________ ____74BB   ECC2K-163 seedQ (MinghuaQu)

4E13CA54 274_____ ________ _____52F 279A8C84   ECC2-191 seedE (MinghuaQu)
FD6F9C51 55B_____ ________ _____BB2 BBBEB67B   ECC2-191 seedP (MinghuaQu)
77733A8F C5______ ________ ____39F6 FEB6390C   ECC2-191 seedQ (MinghuaQu)

D34B9A__ ________ ________ CA71B920 BFEFB05D   ECC2-238 seedE (MinghuaQu)
F7930DE1 C51_____ ________ _____155 35EAEA7E   ECC2-238 seedP (MinghuaQu)
315ADA96 ________ ________ __35FA24 CBF48396   ECC2-238 seedQ (MinghuaQu)

D9037BB3 2E______ ________ ____7738 894AE594   ECC2K-238 seedP (MinghuaQu)
2AC709C3 E56AD81_ ________ ________ _551F2EC   ECC2K-238 seedQ (MinghuaQu)

2B354920 B72_____ ________ _____85B A1332DC6   ECC2-353 seedE (MinghuaQu)
1DD8F2C7 8_______ ________ ___A36EF 3F721942   ECC2-353 seedP (MinghuaQu)
A57C94DF ________ ________ __E8B486 4BC74FF8   ECC2-353 seedQ (MinghuaQu)

91CB22C7 8_______ ________ ___A36EF 670D2FB1   ECC2K-358 seedP (MinghuaQu)
90FA2BDF ________ ________ __E8B486 4BC74AA5   ECC2K-358 seedQ (MinghuaQu)

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.

[garlonicon]

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).

Code:

+---------+-------------------------------------------------------+
| p-value | ffffffff ffffffff ffffffff ffffffff fffffffe ffffee37 |
| b-value |                                                     3 |
| n-value | ffffffff ffffffff fffffffe 26f2fc17 0f69466a 74defd8d |
+---------+-------------------------------------------------------+
| x-value | db4ff10e c057e9ae 26b07d02 80b7f434 1da5d1b1 eae06c7d |
| y-value | 9b2f2f6d 9c5628a7 844163d0 15be8634 4082aa88 d95e2f9d |
+---------+-------------------------------------------------------+
| (G/2).x |  554123b 78ce563f 89a0ed94 14f5aa28 ad0d96d6 795f9c66 |
| (G/2).y | 90755fc9 3ea4b130 27fc6c8f 337d92c6 d00090fa d0e8b2c6 |
+---------+-------------------------------------------------------+

Some example:

Code:

d=SHA-1("")=0xda39a3ee5e6b4b0d3255bfef95601890afd80709
G=(1,2)
d*G=022717833f506da1bcb54a7548f44fcfeb7b60f3ca6d13dba9

Code for checking values:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffeffffee37
K=GF(p)
a=K(0)
b=K(3)
E=EllipticCurve(K,(a,b))
G=E(1,2)
h=1
E.set_order(0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d*h)
d=0xda39a3ee5e6b4b0d3255bfef95601890afd80709
P=d*G
print(hex(P[0]),hex(P[1]))

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.