HN Theater @HNTheaterMonth

Even if you had your GPU-packed Kilo-Google per person multiplanetary Gigagalactic computer guessing numbers for 37 times the age of the universe, it would still have a 1 in 32 billion chance of cracking. https://youtu.be/S9JGmA5_unY?t=32

⬐ vel0city

Your video is talking about 256-bit symmetric encryption. RSA is asymmetric encryption. RSA 2048 is ~112 bits of protection when comparing to symmetric keys, kinda. We're still talking a long time with current computing hardware though.

> For example, if SHA-256 is used with RSA and a 2048-bit key, the combination can provide no more than 112 bits of security because a 2048-bit RSA key cannot provide more than 112 bits of security strength - NIST SP 800-57 PART 1, Page 58

Warning, PDF: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.S...

"but we're rolling an awful lot of dice."

but are the odds better than 2^256 ? https://youtu.be/S9JGmA5_unY?t=38

A good perspective on how big the SHA-256 hash space is: https://youtu.be/S9JGmA5_unY

3Blue1Brown has a convincing visualization of the size of 2^256.

How secure is 256 bit security? https://www.youtube.com/watch?v=S9JGmA5_unY

This video gives a good intuition for that question

https://m.youtube.com/watch?v=S9JGmA5_unY

I wondered the same thing, so I went looking for answers and found this excellent video by 3Blue1Brown:

How secure is 256 bit security? : https://www.youtube.com/watch?v=S9JGmA5_unY

⬐ h3cate

Really informative video but this is talking about hashing functions. Private keys are created differently using (some) shared information between the private and public keys. If there was one area I could see the us investing their time and effort since RSA came out it's here. Don't get me wrong, it would be out there if they could crack even one key but like I said, if anyone can it's them.

⬐ duskwuff

Bitcoin keys are ECDSA (secp256k1) keys. The same scheme is used in many other areas of computer security; it would be incredibly foolish for the NSA to reveal an exploit they're sitting on, even indirectly.

⬐ h3cate

Would it really be that foolish though? Could it not be perceived as a show of strength? That's why America stole them back in the first place right? $4m isn't a lot to the company hacked or to the USA. Why go to the trouble of stealing them back at all?

⬐ TZubiri

No. If anyone had the ability to crack bitcoin addresses, they would not spend that technology on something as inconsequential as this. It would be saved for national defense issues

⬐ h3cate

Completely agree but it could be perceived as a show of strength.

⬐ anonporridge

Still stupid. As soon as some entity reveals they have the power to crack one of these algorithms, everyone scrambles to migrate to something orders of magnitude harder. It's a weapon you'd only be able to use for maybe a few weeks or months before all the worthwhile targets immunize themselves against you.

We already have quantum safe asymmetric cryptography, just no incentive to move fast to deploy it.

⬐ h3cate

And who decides when it's time to make the switch? Because it's not a random government. It will most likely be the us putting pressure on technology companies to switch

⬐ anonporridge

I don't understand the question.

Who decided that we needed to migrate to HTTPs everywhere? Or that authentication for online bank accounts needed to be encrypted?

As cracking of traditional encryption becomes an obvious problem, systems will be upgraded or people will vote with their feet.

⬐ h3cate

Well HTTPS isn't used everywhere and governments have decided that banks need to meet an extremely strict set of rules to operate. As much as we'd like to think of the internet as the wild west, it is not.

⬐ TZubiri

HTTPS is used almost everywhere. And it's not like a government decrees something and it's done. Laws involve multiple stakeholders, and there are multiple governments which converge on the same decision.

It is correct to state that security best practices are not decided by one entity but rather figured out organically and on a non centralized basis.

⬐ TZubiri

How would quantum solve any problems here? I thought the benefit of quantum crypto was the ability to send information while detecting eavesdroppers. I don't think quantum computers have outclassed traditional cpus in processing power.

⬐ h3cate

I believe he's talking about encryption algorithms that are safe from quantum computers

⬐ anonporridge

If they FBI did actually crack a private key, it would almost certainly have to be with a top secret, insanely powerful quantum computer that's decades ahead of what is publicly known to exist. The existence of such a computer that could crack bitcoin private keys would also be a powerful tool against every organization on the planet and their ability to maintain secrets.

I'm referring for post quantum cryptography, https://en.wikipedia.org/wiki/Post-quantum_cryptography, which would negate the usefulness of such a quantum computer at cracking competitor secrets.

Bottom line, there are much more useful things you could use this computer for, like cracking all encrypted communications of a foreign power or hacking into their military or financial systems. Using it to crack a single bitcoin key to recover a few million dollars only serves to alert all your adversaries that it's time to upgrade their cryptography.

Large number comparisons are difficult for humans to comprehend. If you simplify life to a DNA strand 256 nucleotide long (for the sake of math comparison) - then the search space is 4^256. To comprehend how large a search space this is watch 3Blue1Brown's explanation https://youtu.be/S9JGmA5_unY?t=38

We know that life is evolvable because life exists and we know the biochemical mechanisms involved (DNA + cellular biochemistry).

Evolution implies a relatively smooth path through "DNA space" from, say for example, an early single cell eukaryote to a mushroom. However the search space is enormous. Even if we account for billions of years of evolution and a trillions of evolutionary experiments each year, a simple random walk with selection through DNA space should go nowhere because of the numbers involved. The curse of dimensionality[0] means there has to be some other principle of nature to make the search space yield a path from one viable life form to another. The search space of life would have to be 'smooth' in some sense. That 'smoothness' is something we don't understand.

If DNA space is just 256 bits (as a dramatic simplification), then 2^256 is a very very big space to search just by chance [1]. Now imagine a space orders of magnitude bigger.

[0] https://en.wikipedia.org/wiki/Curse_of_dimensionality

[1] https://youtu.be/S9JGmA5_unY?t=22 (3Blue1Browns wonderful illustration of how large 2^256 is)

⬐ leaf_house

Comparing evolution to a random walk with selection doesn’t quite sit right with me. In practice much of evolution occurs via gene duplication and recombination. At that point you can evolve complex changes very quickly. Evolving novel phenotypes is much easier if your starting material is an existing functional gene. Many motifs can be reused and reapplied.

Comparing a mule with it’s parents shows how much novelty can be produced in a single generation (in this case an evolutionary dead-end of course)

⬐ TJSomething

It's not really a random walk in any way. Having designed artificial evolutionary systems, even if you screw up the implementation and the search space is really bumpy, it usually still makes progress, albeit very slowly.

⬐ eindiran

This is an interesting way of framing the idea, but it's not a question of traveling in DNA space from some point (eukaryotic cell) to another specific point (mushroom): that would be very difficult in the way that you're talking about.

Imagine flipping a fair coin 256 times. The particular outcome ('HTTTTHHTTTTTTTTHTHHHTHHTHTHHHHH...') is extremely difficult to replicate, but getting any outcome is very easy: just flip the coins again. In this case we also have a lot of selection bias: all the paths through DNA space that don't result in intelligent life don't result in anyone having this conversation.

Regarding the curse of dimensionality: it's a statement about the available data rapidly becoming sparse in high dimensional spaces. It doesn't really say that high dimensional spaces are necessarily sparse, it's just hard to "fill" them in with the amount of data available.

⬐ galeaspablo

Videos like these are a nice introduction to the power of cryptography. Nevertheless, I feel like the wow factor not only gets prioritized, but it completely takes over the conversation.

There should be more emphasis in how hash functions have been weakened in the past, how that can still happen today, and what it would mean to the world if this happened over night (this last point is unlikely, but still not impossible).

When I first studied cryptography, and Bitcoin, I remember seeing an article that talked about the lifecycles of hash functions http://valerieaurora.org/hash.html ... In my arrogance, I dismissed it. Today I can see how spot on it is.