Author

Topic: PSA: Coders making ad hoc “random” schemes are like kids playing with matches. (Read 302 times)

copper member
Activity: 630
Merit: 2614
If you don’t do PGP, you don’t do crypto!
Joe_Bauers is asking a question about the mining algorithm for his altcoin, which currently has “Market Cap Rank: N/A” on CoinGecko—but it’s listed on Yobit with a 40% spread (!) and no depth (!!), if you want to get cheated.

His mining algorithm has a flaw he does not see.  When time permits, I may post on his altcoin’s development thread with advice for miners who want to exploit it.  The discussion is off-topic on this thread; I will delete further posts about it.

2) A miner could "game the system" by generating a specific char for last position along with the required PoW, though this would require an extra bit of work over non-bad actors.
If you are not generating whatever "random" item publicly, the miners will not know that changing the block header will create any advantage.

What he is actually doing is arguably even worse than that.


Since you don't wish further posts on this.
The dreadful result of someone exploiting this obvious flaw you mention is that the Nfactor for the block is going to be 18 instead of, let's say 20.

No, the dreadful result is that your chain tip will be unstable.  You are giving miners an incentive to build only on blocks that require the next block to use an Nfactor of 18; but you are also giving miners an incentive to broadcast any block they find.  You are also giving miners with significant % of hashrate an incentive to withhold any blocks they find that require the next block to use an Nfactor of 18, build on that in secret, and then broadcast the result.

The ultimate result will be many orphans and reorgs, and a chain that messily converges on having mostly or only blocks that require the next block to use an Nfactor of 18.  If your coin ever has enough value to attract an ASIC designer, then the ASIC will probably do Nfactor = 18 only, and still dominate the network; so I guess that this has the benefit of being ASIC-friendly.



  • Give up, and use urandom.  Not from laziness, but from sufficient wisdom not to shoot myself in the foot.

This is what i would do (even as regular user). But what if your software is browser-based or available on multiple platform? Do you just say it's user risks for not using Linux?

Thanks for the link; I had not seen that thread.  Some of the posts there invited a Nullian rant which is yet unfinished...

Summary:  We went to sleep, and dreamt of a universal platform.  We awoke in a nightmare where the universal platform is the web browser, the universal language is Javascript, the universal ISA is Webasm—and the morals of youths have been corrupted so that they promiscuously run network-loaded executable code from random strangers as a lifestyle.  I want to kill myself, or at least take up a hobby of severe alcoholism.

There are no good ways of dealing with this.  How can one mitigate the horrors?  If I were developing a web app that needed to generate secrets inside the browser, then I would start by reviewing the major browsers’ implementations of crypto.getRandomValues().  Then, I would hope that the “move fast and break things” browser developers don’t change it, accidentally or on purpose.  —Then, I would take a strong drink and/or shoot myself in the head.

As for other platforms:  Every major OS offers an API for obtaining randomness.  Use it.  If it is bad, use a different OS.

A much bigger problem nowadays is an OS running inside of a VM.  A hypervisor must offer a hypercall for obtaining randomness from code that runs “on the metal”, and a guest OS must use it.  Otherwise, the guest OS kernel has the same problem as any application running in userland:  It lacks sufficient hardware access to measure nondeterministic inputs.  Another big problem is, of course, embedded devices... sigh.

The good news is that you only need to obtain a 256-bit random seed.  If you have a 256-bit secure seed, then you can expand it to as much “randomness” as you may desire.  That is what BIP 32 does!  It is cryptographically secure; and there are good ways of doing this for any application, including applications that require forward secrecy.  The focus of my OP here was about extracting randomness into a secure seed, not about what to do after that.

As long as the purpose of generating random numbers is to use them as seeds to electronic signature algorithms like RSA, ECDSA, Schnorr, etc., what matters is not pure mathematical/philosophical concept of security, because the ESA itself is not purely and information theoretically secure! Comparing the two APIs provided by unix like kernels, the myth gives more credit to /dev/random because of its inherent more guaranteed entropy.

This reflects the beginning of OP here, and also an essay that I have been intending to write for the Ivory Tower...  We do not live in the physical world.  The real world, the crypto world, is a world of numbers and computations, where all attackers are computationally bounded.

You behave accordingly, when you generate a Hierarchical Deterministic wallet with BIP 32:  It is computationally pseudorandom, and thus secure against a computationally bounded attacker.

In this context, people who obsess about “information-theoretic security” have no idea what they are talking about.

(N.b. that the whole Linuxland argument looks very foolish to me.  On my BSD systems, /dev/urandom is a symlink to /dev/random; and /dev/random behaves more or less similarly to urandom on a Linux system, except for some extra safety features at boot time when the system hasn’t yet been able to seed the random generator.  In my opinion, Linux should do the same thing.)
copper member
Activity: 2996
Merit: 2374
2) A miner could "game the system" by generating a specific char for last position along with the required PoW, though this would require an extra bit of work over non-bad actors.
If you are not generating whatever "random" item publicly, the miners will not know that changing the block header will create any advantage.

.
Most of the time when you are generating something random, it needs to be secret. If you are deriving something from block headers, you might be able to generate something random, but it will not be secret.
hero member
Activity: 802
Merit: 1003
GCVMMWH
@nullius, I wonder if you would provide your opinion on the following simple algo I devised to determine Nfactor (https://github.com/floodyberry/scrypt-jane) based on previous block hash.

I understand that:
1) This should probably look back to a further level of confirmed block.
2) A miner could "game the system" by generating a specific char for last position along with the required PoW, though this would require an extra bit of work over non-bad actors.

Apart from that, I would expect a 25% chance overall for each of the 4 options.  

Code:
unsigned char CBlockHeader::GetNfactor() const
{

    std::string spb = hashPrevBlock.ToString();
    std::string lasthashchar = spb.substr(block_length,1);

    unsigned char Nfactor = 20;
      if((spb == "0000000000000000000000000000000000000000000000000000000000000000")){
                  Nfactor = 4;}  // Genesis, all chains.

      else if((lasthashchar == "0") || (lasthashchar == "1") || (lasthashchar == "2") || (lasthashchar == "3")){
      Nfactor = 18;}
      else if((lasthashchar == "4") || (lasthashchar == "5") || (lasthashchar == "6") || (lasthashchar == "7")){
      Nfactor = 19;}
      else if((lasthashchar == "8") || (lasthashchar == "9") || (lasthashchar == "a") || (lasthashchar == "b")){
      Nfactor = 20;}
      else if((lasthashchar == "c") || (lasthashchar == "d") || (lasthashchar == "e") || (lasthashchar == "f")){
      Nfactor = 21;}
      return Nfactor;
}

Since you don't wish further posts on this.
Joe_Bauers is asking a question about the mining algorithm for his altcoin, which currently has “Market Cap Rank: N/A” on CoinGecko—but it’s listed on Yobit with a 40% spread (!) and no depth (!!), if you want to get cheated.

His mining algorithm has a flaw he does not see.  When time permits, I may post on his altcoin’s development thread with advice for miners who want to exploit it.  The discussion is off-topic on this thread; I will delete further posts about it.

I have nothing to do with Yacoin if that's what you are referring, and it's listed multiple times on the Yacoin thread from the Yacoin lead that Yobit is a scam.

I was asking your opinion on a proof of concept (not production code) to determine the Nfactor from a previous block-hash of a block-chain which seems to have pissed in your Wheaties for some reason  Roll Eyes The dreadful result of someone exploiting this obvious flaw you mention is that the Nfactor for the block is going to be 18 instead of, let's say 20. But thanks for your educated and truly useful response.

   
legendary
Activity: 1456
Merit: 1175
Always remember the cause!
OP,
I agree that cryptography is hell of a research domain specially for casual readers and hobbyists, and again I agree that programmers shouldn't try to forge homemade random generators, you nailed it, good job. Smiley

But I think you missed the main focus of the sources you referenced: The "/dev/random" vs "/dev/urandom" debate in the field of random number generation while presenting the whole subject as an untouchable topic, exclusively monopolized by a handful of people.

Like any research field, there are both simple and complex issues in cryptography, this debate happens to be a simple one, actually a non-existent one: There is a myth, largely believed, that implies urandom is not "secure enough" compared to "random" API, false claim based on a misinterpretation of the term "secure".

As long as the purpose of generating random numbers is to use them as seeds to electronic signature algorithms like RSA, ECDSA, Schnorr, etc., what matters is not pure mathematical/philosophical concept of security, because the ESA itself is not purely and information theoretically secure! Comparing the two APIs provided by unix like kernels, the myth gives more credit to /dev/random because of its inherent more guaranteed entropy.

But security is not a race between APIs, and it is where the myth falls apart, a good programmer or a qualified software engineer is not just like an ordinary customer shopping in a grocery store looking for "better" stuff, she desperately wants something fit for the application and preferably cheaper in terms of resource consumption.

As of our debate /dev/urandom is ways more adequate for generating pseudo random numbers as seeds for ESA simply because it is unpredictable more than enough for such schemes and the processing power needed for breaking it, could easily break the main algorithm in the first place if it'd  ever exist, and more importantly, it is better choice compared to /dev/random because unlike the latter, it  does not block!

That being said, it is worth mentioning that there are always side channel risks, due to bad implementation/configuration practices for both APis under consideration.

So, you are absolutely right in discouraging programmers from cooking stupid random stuff and concluding that it is better to stick with /dev/urandom, but there is logic, simple logic, behind your recommendations that I'm afraid, you fail to present.
copper member
Activity: 630
Merit: 2614
If you don’t do PGP, you don’t do crypto!
copper member
Activity: 630
Merit: 2614
If you don’t do PGP, you don’t do crypto!
Please, stop the superstitious nonsense.  To adapt a classic DJB quote, think about this for a moment:  Whoever uses physical dice or coin flips to generate the seed for a Bitcoin wallet seems simultaneously to believe that:

  • An OS kernel’s CSPRNG which is designed by actual cryptographers, who have actually studied cryptography, is insufficiently secure because it is somehow not “truly random”.
  • It is secure to use a tiny seed to generate an unbounded tree of pseudorandom private keys in your BIP 32 HD wallet.

“For a cryptographer, this doesn’t even pass the laugh test.”

To generate random numbers for cryptographic keys, Bitcoin seeds, etc., you should use your OS kernel’s system calls for accessing the OS kernel’s random device.  If you do not trust your OS kernel to give you random numbers, then your OS is altogether untrustworthy; you should switch to a better OS before it betrays you, beats you up, and steals your lunch money.

And whatever you do, you should NOT cook up your own ad hoc “random” scheme unless:

  • You have spent quality time studying the relevant theory.
  • You are not confused by such terminology as a discrete uniform distribution from a bounded integer range.
  • You know the basic difference between min-entropy and Shannon entropy.
  • You understand the extract-and-expand model of generating secret key material from an input with the wrong distribution; and you know how properly to extract the randomness you need from, e.g., a string of 6-sided dice rolls, or a shuffled deck of 52 playing cards.
  • You can point out flaws with other people’s ad hoc schemes on this forum, on Reddit, on StackExchange, in the issue trackers of Github projects coded by people who should NOT be writing cryptographic implementation code...  (Whether or not you waste your time doing so is up to you; but you need to be able to see the flaws.)
  • Many other things that I am too lazy to list.

If you do not heed my advice, then you will probably wind up coding some Rube Goldberg style randomness contraption riddled with modulo bias and similar bugs.  You will be fooling yourself with security theatre that results in a false sense of security.  Whether or not you ever suffer negative consequences for this, or by how much, will thenceforth be a matter of dumb luck.

Coders who make their own ad hoc randomness schemes are like kids playing with matches.  If that sounds harsh, well—sorry, but I’m not sorry.  I am warning you not to get burned.



Here lie dragons of terrific complexity, subtle in their souls and heavy on maths.

To understand such things, you need to start by being born with a genius-level IQ, and then study for years.  I myself admittedly have but a bare grasp of these concepts:  I know enough to know how little I know!

In that, I have an advantage over those who have no idea of how little they really know.

If I myself want to make my own randomness from physical sources, here is the plan that I would probably follow:

  • Research existing randomness extractors designed by real cryptographers.
  • Give up on reading papers that I lack the deep mathematical knowledge to understand, and decide to use the extractor specified in HKDF.
  • Ram my head into the maths to try to figure out how best to apply the randomness extractor to my sources of randomness.
  • Give up, and use urandom.  Not from laziness, but from sufficient wisdom not to shoot myself in the foot.

HTH.
Jump to: