Interesting. Garlo Nicon was quite close, but didn't pick the right seed function:
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-implementationstatic 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.
I will try to check, if secp256k1 generator can be explained in a similar way.
Edit: I reproduced one of the seeds, will try to find next ones later:
#include <cstdint>
#include <cstdlib>
#include <iostream>
int main()
{
srand48(863966734);
for(std::size_t i=0;i<2760;++i)
{
lrand48();
}
for(std::size_t i=0;i<5;++i)
{
std::uint32_t value=(lrand48()>>23);
std::uint32_t value2=(lrand48()>>23);
std::uint32_t value3=(lrand48()>>23);
std::uint32_t value4=(lrand48()>>23);
std::cout<<' ';
std::cout<<std::hex<<value<<value2<<value3<<value4;
}
return 0;
}
Standard output:
3045ae6f c8422f64 ed579528 d38120ea e12196d5
Edit: I tried to find the pattern "ce563f89a0ed", but didn't find anything (however, there were a lot of matches for "ce563f89", as you can see by running it). So, secp256k1 generator seems to be created in a different way:
#include <cstdint>
#include <iostream>
#include <sstream>
#include <string>
std::string print48(std::uint64_t value)
{
std::ostringstream out;
out.width(12);
out.fill('0');
out<<std::hex<<(value&0x0000ffffffffffff);
return out.str();
}
std::uint64_t getNext(std::uint64_t value)
{
std::uint64_t scale=0x00000005deece66d;
std::uint64_t added=0x000000000000000b;
std::uint64_t mask=0x0000ffffffffffff;
std::uint64_t next=((value*scale)+added)&mask;
return next;
}
int main()
{
const std::uint64_t firstValue =0x0000ce0000000000;
const std::uint64_t secondValue=0x0000560000000000;
const std::uint64_t thirdValue =0x00003f0000000000;
const std::uint64_t fourthValue=0x0000890000000000;
const std::uint64_t fifthValue =0x0000a00000000000;
const std::uint64_t sixthValue =0x0000ed0000000000;
const std::uint64_t increment =0x0000010000000000;
for(std::uint64_t firstCandidate=firstValue;firstCandidate<0x0000cf0000000000;++firstCandidate)
{
std::uint64_t secondCandidate=getNext(firstCandidate);
if((secondCandidate>=secondValue)&&(secondCandidate<(secondValue+increment)))
{
std::uint64_t thirdCandidate=getNext(secondCandidate);
if((thirdCandidate>=thirdValue)&&(thirdCandidate<(thirdValue+increment)))
{
std::uint64_t fourthCandidate=getNext(thirdCandidate);
if((fourthCandidate>=fourthValue)&&(fourthCandidate<(fourthValue+increment)))
{
std::uint64_t fifthCandidate=getNext(fourthCandidate);
std::cout<<"trying fifth at 1st: "<<print48(firstCandidate)
<<", 2nd: "<<print48(secondCandidate)
<<", 3rd: "<<print48(thirdCandidate)
<<", 4th: "<<print48(fourthCandidate)
<<", 5th: "<<print48(fifthCandidate)<<'\n';
if((fifthCandidate>=fifthValue)&&(fifthCandidate<(fifthValue+increment)))
{
std::uint64_t sixthCandidate=getNext(fifthCandidate);
if((sixthCandidate>=sixthValue)&&(sixthCandidate<(sixthValue+increment)))
{
std::cout<<"first: "<<print48(firstCandidate)<<'\n';
std::cout<<"second: "<<print48(secondCandidate)<<'\n';
std::cout<<"third: "<<print48(thirdCandidate)<<'\n';
std::cout<<"fourth: "<<print48(fourthCandidate)<<'\n';
std::cout<<"fifth: "<<print48(fifthCandidate)<<'\n';
std::cout<<"sixth: "<<print48(sixthCandidate)<<'\n';
return 0;
}
}
}
}
}
}
}
Standard output:
trying fifth at 1st: ce00013c3f59, 2nd: 56533b9ceef0, 3rd: 3f8fc5bd5c3b, 4th: 899282e1472a, 5th: 9c2e269308ed
trying fifth at 1st: ce0002c50a04, 2nd: 56e6e894dbbf, 3rd: 3fcbfae32a5e, 4th: 89407d717e11, 5th: e7715641f348
trying fifth at 1st: ce000384277c, 2nd: 56a8290e37d7, 3rd: 3f372d6cf096, 4th: 894c15d133e9, 5th: 5c6c27827040
trying fifth at 1st: ce0004a9a3f4, 2nd: 5687227806ef, 3rd: 3fd629a9adce, 4th: 89c90d4e14c1, 5th: ae4e50d03c38
trying fifth at 1st: ce000568c16c, 2nd: 564862f16307, 3rd: 3f415c337406, 4th: 89d4a5adca99, 5th: 23492210b930
trying fifth at 1st: ce0006f18c17, 2nd: 56dc0fe94fd6, 3rd: 3f7d91594229, 4th: 8982a03e0180, 5th: 6e8c51bfa38b
trying fifth at 1st: ce000711e906, 2nd: 56111f839b99, 3rd: 3fd9c7e0b630, 4th: 8963929cb27b, 5th: 7cc06876806a
trying fifth at 1st: ce000959d129, 2nd: 56660cf4e480, 3rd: 3f812f904a8b, 4th: 891d258c9f3a, 5th: 3cfe6965e7bd
trying fifth at 1st: ce000b1e0e2a, 2nd: 56d1373dc3ed, 3rd: 3f2f27cf59f4, 4th: 89c4c30a84ef, 5th: f5a74d3d53ce
trying fifth at 1st: ce000b3e6b19, 2nd: 560646d80fb0, 3rd: 3f8b5e56cdfb, 4th: 89a5b56935ea, 5th: 03db63f430ad
trying fifth at 1st: ce000cc735c4, 2nd: 5699f3cffc7f, 3rd: 3fc7937c9c1e, 4th: 8953aff96cd1, 5th: 4f1e93a31b08
trying fifth at 1st: ce000d86533c, 2nd: 565b34495897, 3rd: 3f32c6066256, 4th: 895f485922a9, 5th: c41964e39800
trying fifth at 1st: ce000eabcfb4, 2nd: 563a2db327af, 3rd: 3fd1c2431f8e, 4th: 89dc3fd60381, 5th: 15fb8e3163f8
trying fifth at 1st: ce000f0f1de7, 2nd: 56eee1414566, 3rd: 3f6efb2c3079, 4th: 890d42e95990, 5th: 0f5c9492825b
...
Will try to check other patterns later. Also, it can be faster, than scanning 2^40 values, but doing it is still fast enough, to check it on a CPU. I guess a different wiring is needed, to recover the internal state of 48-bit seed faster, than by this 2^40 brute-force, for any given number.
