the funny thing is, even if you had 4 billion galaxies of computers working on that problem, even if someone found the solution, because light has a speed limit, and the universe is expanding, you wouldn't even be able to communicate the solution to everyone.
I might be wrong, but if you already have some sort of quantum powered way of comunication, then you DON'T NEED to guess in the first place, isn't? what is easier to get? Quantum powered way of comunications or a quantum computer capable to destroy to dust SHA-256 encryption?
A 1/115792089237316195423570985008687907853269984665640564039457584007913129639936 chance? That man would be so fucking lucky I'm pretty sure the universe would simply explode from the improbability. I mean, it's on that level
@@khf3940 So close to zero that you can safely call it zero though. Our brains aren't made to understand such numbers so when we say "not zero" we usually overestimate how likely it is. It's the same problem with the lottery. People buy that even though they mathematically shouldn't. Because of that it might actually be _more_ correct to call it zero to make people understand what you're talking about.
A chain is only as strong as its weakest link. You can have the most secure system in the world, but all you need is the wrong user to use 'password' as their password and a breach is inevitable.
@Jonny Nobody so you just replied to a 4-month-old reply that is on a 1-year-old comment and I only have seen your reply now(4 hours after you replied) so new password !1Y4 M4h
Password hashed is secure just If It have never been hashed, and believe me, It probably have been, unless you take It into account to make your password. The ingenuos be like: But my password is my birthday and just me have It as birthday! Ah! Of course no one on earth have the same birthday as you! Hahahah
nyx211 not really...You see, quantum computing can cut down the required processing time(hence increased processing power) in logarithmic scale, which means cutting down the time needed to "hash" until match is wayyy lower compared to the current day method. So yes, we are quite fucked.
And don't forget that the hash can be guessed in the early stages, not always having to be the last computed hash, so there's a chance to be even faster
They already found solutions to way more secure encryption, so secure it can completely render quantum computers useless. This is done by using other quantum computers.
Arthur Machado it is not just billion trillion time faster, it is logarithmicly faster. For example a computer can do x amount of work at a time, the quantum computer can do x^8 amount of work, which is not just *fast* can justify it.
Theres always some kind of simplicity behind complexity. In computers, sometimes, the "security" looks like a big iron door, until you realize you can pass beside that door, coz theres no walls beside that door..
Which is actually one of the major reasons cryptocurrencies are such a misguided idea. It's like building a castle made of indestructible stone that has no guards.
Q&A Answers: th-cam.com/video/8r5WKpK9-m8/w-d-xo.html Edit: One thing I wish I had said explicitly is that even though a perfect and idealized cryptographic hash function would behave like a random function, in reality, there is some element of predictability to functions like those in the SHA-2 family. So even though SHA256 has a 256-bit output, it's actual level of security is lower than 256 bits.
You state that it takes an average of 2^256 guesses to get the correct hash. Wouldn't the correct value for that be 2^255 guesses, as you'd on average search half the solution space? Also, hasn't there been research on some cryptographic hash functions (not sure if it would include SHA-256) which dramatically lower these exponents?
There's been plenty of research. Governments have lots of cash and lots of reasons to find a way to hack into these hash functions, but SHA-256 has not been "cracked" yet. As the previous video says, no one really knows if it's mathematically cryptographically secure because it's very complex math. SHA1 is not secure but only because it doesn't require enough computing power to break. It only takes one Google to crack it. Google "sha1 cracked".
In the video you describe the complexity of a brute-force pre-image attack. Wouldn't a collision attack work for digital signatures? The complexity of that for SHA-256 seems to be 2^65.5, which while still not being practical is not as impressive as 2^256. Edit: 2^65.5 attack that I mention seems to apply only for a SHA-256 with a reduced number of hashing rounds performed (31 out of 64), for a full method there's a 'birthday collision attack' with a complexity 2^128
-2^255 is right on average- [see correction by 3blue1brown below], but complexity theory usually uses big O which is worst case, I think that might be way people often say 2^256. As for collision attacks, finding proof of work is indeed not a pre-image attack, think of the difficulty as bounding a set of elements, and you get a chance for a collision with each of those. But that doesn't apply to digital signatures - in bitcoin those are made using ecdsa, with the secp256k1 curve, and I think it's possible to attack it more efficiently than brute force, but I don't think it's as cheap as a collision attack. As far as the size of the search space, NIST used to recommend 2^80 for being secure for the "foreseeable future", otherwise known as a security parameter of 80 bits, and since the 90s they changed the general to 128. Collision resistance requires a hash that outputs double that bit width, so modern hashes are usually 256 bits (and also why ripemd and sha1 are 160, note that ripemd is used in bitcoin for addresses, on top of sha256 if I remember correctly). Finally, if to attempt to future proof against quantum computing, if you double the bitwidth again then this is supposed to be enough to resist nondeterministic collision searches, which is the main reason to use 512 bit hashes as far as I know. Update: I should say - regarding ecdsa attacks - I think that because I know I don't know enough about the algebraic structures of elliptic curves, but as far as I know the 256 bit representations have some bias because of them, and also because improperly chosen curves are breakable, but don't quote me on this since I don't actually understand the details.
To the point about it really requiring half as many guesses, (i.e. 2^255 not 2^256): This is true for something like hacking a digital signature, where you are methodically going through all possibilities. But if a cryptographic hash function truly behaves like a random function, guessing and checking a nonce with a hash will not look like going through all possible hashes one-by-one, it's more like rolling a die over and over until you hit a 6, in which the expected number of rolls needed is 6, not 3. While running this GigaGalactic supercomputer, many of the guesses will actually collide, so it is not a methodical search through all possible hashes. However, as you point out, the actual security on SHA256 is indeed lower than 256-bits. It turns out not to quite behave like a nice random function. But this discussion just centered on an idealized cryptographic hash function.
Bonus fun fact: If you actually take 4,000,000,000 to the 8th power, what you'd get is closer to 2^255 than 2^256 (specifically, about 2^(255.18), or 1.13 * 2^255). Approximating 2^32 (4,294,967,296) as just "4 billion" ends up losing more overall value here than you might expect.
Small note: it would likely not take you 2^256 guesses to get it correct, as that is every single possible combination of guesses. Rather, it would take an average of 2^255, which is the halfway point between 0 and 2^256 (as any power of 2 is twice as many as the previous power). Minor detail but helps with the general understanding.
To chime in a year late, ALittleOff was correcting at 0:35 when he says it would take “on average” 2^256 guesses. Worst case it would take 2^256 guesses, but on average, it would take 2^255 + 1/2 guesses. You can find this with some simple math: Let n = 2^256 just for ease of reading. Since there is a 1/n chance for the hash to be any numbered guess, we can find the average number by adding up the possible numbers of guesses and dividing by n. The number of guesses can be anything from 1 to n. If we add up those numbers, we get n(n+1)/2. Dividing by n gives us (n+1)/2=2^255 + 1/2.
There is no such a thing as worst case in here since(assuming sha256 to be an ideal hash function) every new guess gives you exactly 1/2^256 probability of success independently of previous guesses. Actually, after 2^256 guesses you'll still have failed to find the preimage wuth probability very close to 1/e.
I know it's quite a while ago you commented here but how does it make sense to take 4 billion copies if only 1 percent of 1 copy actually is filled with planets that are important for the calculation?
@@Superphilipp yeah I know that but I doubt anyone would have seen it if I wrote my own comment, so I just tried my luck with you but thanks for the answer✌
@@cedrik1031 I thought he said imagine that the Milky Way was filled with 4 billion planets where 4 billion peoplee had access to a Googlekilo worth of computers. Meaning that in this hypothetical more than 1% of the Milky Way would be filled with planets
Worth mentioning: Some cryptocurrencies (I think Litecoin does this) use a different hash function called scrypt instead of SHA-256. scrypt is designed to be impossible to create application-specific integrated circuits for, because it requires large amounts of RAM and computing power, unlike something like SHA-256 which is essentially a bunch of logic gates. Neat!
Impossible is really the wrong word. Impractical is better. It wouldn't significantly improve your efficiency enough to matter even if you did make an ASIC for it, basically.
Amir Abudubai Correct, mostly, though it will just start looking more and more like a CPU ;) These coins also have the feature that they can modify the parameters without creating a new chain, so you would either need ASICs with redundant hardware (fails the "becoming a CPU" stumbling block), of you would need new ASICs each time this happened (fails by being infeasible due to cost and time)
Really an amazing way to quantify these numbers...great job. So often when a number is big enough it just falls into the category of "a really really big number" so people never, or, could never, figure out how big it really is.
4:33 Now the channel surpassed 2^21 subscribers And close to reach 2^22 subscribers Congratulations I always loved your videos, the quality of the explanation of the topics is simply unmatched, I swear I learned more from this and other educational channels than from school/college on the last 4 years Keep going, the world need more channels like this.
Uh, sure, but not hash functions. Further, Shor's algorithm (which is the one that gets all the hype about this) only works on encryption schemes that depend on factoring large numbers, namely RSA. Since RSA uses prime numbers, it makes factoring the multiple of two of them really hard (the numbers are huge). We can revamp everything to stop using RSA (and already have been, for many, many years) relatively easily, given the impetus that it'll be completely broken soon enough. We've already got encryption schemes that can run on classical computers that are hardened against both known classical and known quantum attacks. Often they take more compute time and are more complicated to implement, but with how classical computing is still getting faster, and specialized hardware can be built to accelerate encryption and decryption once the standards are set, this really shouldn't be a big issue.
♫ I'm a menace, a miner, a hash-figure finder ♫ ♫ Gimme a table and in less than an hour ♫ ♫ Give the chain a new link in it ♫ ♫ Get some bits for fixin' it, Slide 'em in some hooker's tit ♫
3 blue 1 brown always comes In clutch with the visualizations. This reminds of combinatorial explosion, and how often it comes up in real world problems, it would be interesting to see you make a video going into depth on this topic.
My personal favorite "big number" is the number of atoms in the universe - about 10^80 (Wikipedia), or 2^83. Molecules vibrate at 10^13 .. 10a^14 Hz - call it 2^17. So, if every atom did one guess-and-check every time it twitched, you'd still need 2^156 seconds - about 2^40 years, which is 250 times the age of the universe.
This video is pretty misleading. It's a good illustration of how big a 256 bit number is, but NOT a good illustration of how secure 256 bit security is. These cryptographic hash functions are broken and need to be replaced every few years. This happens because weaknesses are found in the algorithm that make them easier to guess, and has very little to do with raw computing power. SHA-1 is now considered dangerously weak, and output 160 bits. No one made a computer that checked all 2^160 combinations. People found weaknesses in the algorithm. This has been true for almost everything in cryptography from the Enigma to MD5.
the weakness is collision and i think in this case it's not important. with files you can add bytes and so on to create the same hash for 2 different files... with blochchain it's much much harded even if sha256 would be cracked.
Well... It's important to know how many bits you need in an algorithm where the only option is brute force. And it seems as though 256 bits is enough for that. It tells me that there's no need to jump up to 512 or 1024 or more in order to secure against brute force attacks, we've already got all that we need. How many extra bits of padding is needed to compensate for an algorithm's flaws would require a video of its own.
"It would require on average 2^256 guesses". Shouldn't it be "at most" ?, if all the guesses are wrong until the very last? And on average (2^256)/2 guesses?
No. I just replied to another comment about this, where 3blue1brown himself commented: "While running this GigaGalactic supercomputer, many of the guesses will actually collide, so it is not a methodical search through all possible hashes". So yes, if you do it this way you can expect to find the answer after only checking half of the pool: Have a list of all 256 bit numbers, guess 1 & remove it from the list & calc the hash & check it, repeat until you have the hash you want.
Python is fast. And you should know that printing to the console is an IO task and C++ isn't that much faster than any other programming language at doing that.
@Omar alpjaly For the differences between languages being "very small and hardly noticeable", python sure takes 62 times longer than c++ to count to 2^32 - 1 Yes I tested it
@@chappie3642 considering that it's a fucking TH-cam comment, it should be obvious why a smaller line count as well as more readability is more desirable than execution time, because guess what, everyone READ the comment as opposed to execute it. Furthermore, if you still insist on execution time mattering, then I'm sure that you'll be thrilled to know that since the bottle neck in both cases is the console, both python and c++ have the same execution time as they're both faster than the CLI's output capability. In other words, by using python, you'll literally write 2 lines of code to achieve the same result in the same time as if you did it in c++.
Chinese/Japanese/Korean use a different system for abbreviating large numbers: 10,000 is 万 or equivalent; 100,000,000 is 億 or equivalent; etc. And the Chinese, Japanese, and Korean subtitles _all_ use "40億" instead of "42億" or "43億" when translating "4 billion". It hurts to look at.
@@lagillas The easiest way to solve the problem is to find the root of the problem. The easiest way to crack Satoshi Nakamoto's private key is to point a gun at him! 😳
+adrian peiron You are right in that many of the existing economic structures were created by the elite to serve the elite. Modern economic 'science' is applied mathematics. You have to know the rules to led you to a sound methodology. Without that you are just a theorist no better than a hack. Unfortunately there are certain fields in economics that are stuck in a habit of intellectual masturbation rather than doing something based in reality.
phyrexkasgaming definitely* also, we would have different processors for maximum efficiency and just communicate it all through a database. The computers would each have assigned images which they process into hashes and repeat. That’s how I would do it, but we would be limited heavily by physical and storage space.
They don't really need to communicate at all. When you assign the problem you can easily just say that A solves numbers 1 to 1000, B solves numbers 1001 to 2000 etc. Report back if you have something. Then you just wait for someone to report back that they either are out of numbers to solve or have solved it.
This is an excellent illustration of the number 2^256. Cryptographer Bruce Schneier has an interested paragraph in his book "Applied Cryptography", suggesting we don't have enough energy in our solar system to count through 2^256. This is because the 2nd law of thermodynamic states that a bit change requires minimum energy of kT erg, where k is the Boltzman constant, T is the absolute temperature. 2^256 is such a huge number, that to cycle through will require more energy than our sun can produce for the next so many billions of years, even including the supernova. Notice the video assumes billions of galaxies. So with the current physics and math 2^256 is beyond reach. However, we don't know about new physics and new math...
I doubt anybody will ever see this, but I came up with my own analogy to describe how absurdly huge this number really is. FIrst off, I saw in some other random YT video - that humans are pumping out roughly 60 quintillion inputs for the SHA 256 per second. So if humanity continued calculating at this pace, how long would we have to keep computing before we found 2 inputs that equate to the same output? TLDR: A long fucking time. Analogy: We have a lot of time to kill, so let's start by imagining that we kill time by walking in a straight line until we reach the moon. Once you reach the moon, turn around and come home. When you get home, (you would have been gone roughly 18 years) buy a powerball ticket. If that ticket wins the jackpot, buy a mega millions ticket. If the mega millions is ALSO a winner, flick a penny into the Grand Canyon. After flicking the penny into the Grand Canyon, continue on your walk - back and forth from the Earth to the moon and back. Again, when you return to Earth, buy another powerball ticket. The only way you will ever throw a penny into the Grand Canyon, is if both the Powerball AND Mega Millions tickets are winners. As you could imagine, you're going to do this until all 5.45 million cubic yards of the Grand Canyon is completely filled to the brim with pennies. That's a lot of lotto wins! Of course you haven't even scratched the surface of how much time needs to pass, so we're going to continue on with this pattern - until you have filled the Grand Canyon with pennies 200,000 times over. Eventually I'm assuming you will get bored of filling the Grand Canyon with pennies, so after 200,000 of these fills you can switch to the Pacific ocean. The pacific ocean is a lot bigger than the Grand Canyon, and it would take about twice as long to fill with pennies as it took to fill the Grand Canyon 200,000 times. Woah. Now that the pacific ocean is filled to the brim with pennies, empty it out and find a nice place on Earth to park a Chevy Malibu. Return to the Grand Canyon - Fill it with pennies 200,000 times. Return to the pacific ocean, and fill that with pennies as well. Keep in mind, each penny represents winning back-to-back lotteries after a round trip from the Earth to the moon and back at a walking pace. Each Chevy Malibu is going to be the equivalent amount of time as: filling the Grand Canyon with pennies 200,000 times as well as the pacific ocean once. How many Chevy Malibus will we have to stack before we finally have run out of possible calculations? Answer: It's a fucking lot of Chevy Malibus. You're gonna stack those babies on top of each other until they too reach the moon. Then you're going to start a new stack of Chevy Malibus - and that stack too will also reach the moon. And then you're going to do another. and another and another and another until you have reached roughly 33.7249 Earth-Moon length stacks of Chevy Malibus. Now that you are exhausted, sick of pennies, and a little over 61 quindecillion years old, you can drive the last Chevy Malibu down the giant cosmic escalator of Malibus from roughly 3/4 of the way to the moon back to Earth where you will finally get to rest - and enjoy seeing 2 different inputs that provide the exact same 256 bit output in the SHA 256. I can only imagine what those 2 different inputs look like. I hope you'll share with the rest of us. Is it a picture of a Chevy Malibu and the dimensions of a penny? Is it one of the back-to-back lottery winning numbers? Who knows? You do. Because you did it.
someone commemted sarcastecly that if one randomly guess in first try,,,,i want to say that,,,, chances are zero not near zero,,, in probability we simply assume that probability< 1/10⁵¹ is zero,,, not as near zero but zero,,,
I once saw an argument based on energy rather than speed that followed this very general outline: Suppose you had a computer that operated at absolute maximum theoretical efficiency, so that there was no way it could possibly use less energy to flip a bit from zero to one, or one to zero. Suppose that's all this computer did: flip a single bit from one to zero and back again, over and over. (No counting: that's too complicated, reserved for a future version of the system. Certainly no complicated hashing or other common brute-force crypto-attack techniques: this is just a prototype.) Suppose you put this computer in the most naturally-cold place in the universe, to maximize its efficiency. (Don't want to spend energy on cooling, only on bit-flipping.) Now suppose you could capture the entire energy output of a standard-size supernova, and feed this energy into your super-cold bit-flipper--assuming the existence of whatever energy-storage technology would be necessary to spread out the energy consumption over whatever time interval the bit-flipper required. A supernova's worth of energy would be enough to power the bit-flipper through about 2^192 bit flips; which means you'd need to feed in 2^64 supernovas to get all the way up to 2^256. So that's version 0.1. By version 1.0, you'd need an actual crypto-attack algorithm, rather than just bit flipping, where each of the 2^256 attempts would require hundreds of thousands or maybe millions of bit flips. But..first things first. So I probably have the numbers wrong, and perhaps some of the details as well...but that was the overall shape of the argument. I'd love to see you do a video on the real argument with actual numbers.
*Another statement that explains the size of 2²⁵⁶...* $2²⁵⁶ per *millennium* is enough to make everyone on Earth *(distributed)* an *unvigintillionaire* in ~0.27 seconds, and 1 unvigintillion is 10⁶⁶, which is typed/written out as 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000.
If you compare it to daily numbers then yes it is big but compare to the world of big numbers it's small compare to even googol, which is just the beginning of big numbers. There is an infinite number of numbers bigger than it.
@@carbrickscity Yes but compared to how fast computers can generate and guess numbers it is really big. Imagine flipping a coin 256 times and you need to land on heads every time. How long will it take you to get there? A really long time. Granted, a computer can generate number much faster than you can flip a coin but the problem remains - it will take a really long time. You will reach the heat death of the universe before then. And, in a couple years, SHA-512 will be adopted and now the problem is significantly longer.
The video is great and I'm not at all trying to discredit it, but there's a small error in which it is stated that, on average, it would require 2^256 guesses to find the correct hash. Since 2^256 is actually the total number of possible guesses that any given sha256 can be, the average number of guesses needed per hash would be 2^256/2 = 2^255 due to the random nature of any given guess being correct. Not that such a difference matters too much when talking about timespans 37 times as long as the age of the universe as we know it. Just thought I'd clarify.
wow that's big. just watched this and you cryptocurrency video, this blew my head as I know an analogy to describe what relationship 1 Billion is to 1 Million using time. The crypto video answer so many questions, thank you
LunarCoffee because it takes longer to recognize what it actually is about? Would be my guess. I.e. For c++, when the 'c' is spoken, I know it's about a programming language and am then waiting to hear which one.
In this video it says 262,144 subscribers (some 4 years ago). Today, 15 June 2021, we're at 3,74 million. As a lot has happened in these 4 years (faster hardware and growing number of crypto-miners) it would be nice to have not just an update, but a now/then comparison. Congrats and keep up the good work!
is just a product of two prime numbers You need a deterministic solution for the system N=x*y No dictionaries checking, no iterations, just a deterministic solution for that system of equations where N is your 256 digit number, and x and y are two different prime numbers. Yo set up the system, you get the only one solution. End of the story I reach a non-linear system of 5 equations with 5 unknown parameters. But hard to use into large digit numbers, I need new algebra tools to multiply, square root and potenciate them efficiently
first guess: 01000101101001001010101001111100101000101101001001010101001111100110010001001011100101010101010110100010101001010110101010010000010100010110100100101010100111110010100010110100100101010100111110011001000100101110010101010101011010001010100101011010101001000001
1:26 And there's me wondering how the game Factorio reached such a fine level of performance efficiency and my quad core still struggles really hard with more than 100k calculations per second
Hah. I remember watching this video (and the main one) on release day back when you had 2^18 subscribers (262,144 people). But now you've recently passed 2^22 subscribers (4,194,304 people)!!! Great work, 3b1b :)
This is good but you should remind your audience what Edward Snowden said (paraphrasing) "Encryption is secure but end point security is generally terrible." Any system is only as strong as its weakest point. Congratulations on 2^18 subscribers. Well deserved. I hope you get to 2^20!
Not really, since the outcome of the hash function is unpredictable, it can (and it does) give the same output for different messages, so basically, in each try you'd have 2^(-256) chance of guessing it right independently of how many tries you've done before. That gives you sum over n of n*p*(1-p)^(n-1) from n=0 to infinity average guesses (where p=2^(-256)), which you can solve using n*(1-p)^(n-1)=-d/dp((1-p)^(n)) and trying to write the sum as function of it's derivative and solving the differential equation, or alternatively writing n*(1-p)^(n-1) as (1/(1-p))-*-((n+1)-*-(1-p)^n-(1-p)^n) and trying to write the sum as function of itself and solving the linear equation. Or even more alternatively, you could plug that on wolfram and see that when m goes to infinity (the sum goes from 1 to m) the sum goes to 1/p, which is 2^256. Another thing is that the average amount of guesses isn't necessarily when amount that gives you 50% chance, that's the median. But since if we could avoid doing repeated guesses the probability would grow linearly, the 2 would coincide.
Yes, after you checked half of them, the chance of having found the right hash would be 50%. This would also be the average time it would take to find the right hash.
Nice mind blowing video. Loved it. A followup that would be neat is if quantum computing advancements in processing power was projected out 10 years what would that look like in terms of quantum computers coming near this problem mathematically.
This video is pretty misleading. It's a good illustration of how big a 256 bit number is, but NOT a good illustration of how secure 256 bit security is. These cryptographic hash functions are broken and need to be replaced every few years. This happens because weaknesses are found in the algorithm that make them easier to guess, and has very little to do with raw computing power. SHA-1 is now considered dangerously weak, and output 160 bits. No one made a computer that checked all 2^160 combinations. People found weaknesses in the algorithm. This has been true for almost everything in cryptography from the Enigma to MD5.
This video is incorrect because it expects a perfect hash function, which would give a truly unique hash value for every possible value. But because we are using a finite range (2 ** 256 possible values), this is impossible. Knowing this, we can use what is called a birthday "attack", which is based on the principle described above and allows us to reduce the number of guesses from 2 ** 256 to "only" 2 ** 130 for a probability of a 0.9999 of obtaining a valid guess. EZPZ guys
0:37...The worst case is when you need to make 2^256 attempts, and the best case - when you need to make just 1 attempt. So... why average number of attempts is 2^256?
I don't think there is any algorithm for quantum computers that easily solve hashes. And currently, making them say 15 = 3X5 is a big success, so I think there is no need to worry before a few years/decades
@@sarthaksharma4816 Correct me if I'm wrong, wouldn't it be for guessing it once : 1/(1/2^256) = 1/1.1579208923731619542357098500869x10^77 And then to guess it twice you square it? So, 1/1.3407807929942597099574016910872x10^154
It also depends what do you mean by "security", as the latter comes in many forms: confidentiality, data integrity and so on. Also when we consider just hash functions there is always the problem of collisions (pigeonhole problem), i.e. finding two inputs that map to the same output. Because of the birthday paradox there is already a 50% chance to get a collision within 2^128 inputs.
Not exactly, it would destroy the premise of Bitcoin since a single Quantum Computer will have enough computation power to outperform the whole network.
If quantum computers someday achieve enough power to guess a PV key.... Well we don't have to care about money anymore because that fkn thing ( quantum computer ) would be able to create AI that will do EVERY work for us
Dont ever dream about those computers working. Because when that day comes, cracking current block chain is going to be so easy since quantum computer can easily factor huge prime number with Shor's algorithm.
Not at all. Quantum computers will reduce the security of public keys encryption into dust because the shor's algorithm can factor primes really fast. So it would take almost no efforts to crack any current crypto system because they all use ECC. If you can factor primes fast, you cracked pretty much all the public encryption system because they are all based on the idea of factoring being a hard task.
@louisphillippe1100 Nice thought but not every Public-Key Encryption system uses the premise that the prime factorization of large integers is infeasible. Look at the discrete logarithm. IIRC it doesn't have an algorithm that is designed for quantum computers. (Although polynomial time would most likely still be too little to actually stop such a machine...)
Two mistakes in the first minute of the video: 1) it is not necessarily the ONLY way to guess all combinations. SHA256 algorithm could be broken. Happened to other hash algorithms like DES before. 2) it takes on average 2^255 guesses for brute force
2 is wrong. It is 2^256 as you are not going through the hashes, but through random guesses, where the hash could be the same. You have no way of avoiding double guesses (at least right now)
I was thinking about A GPU that can do 4 billion hashes per second A computer with 4 billion such GPU's A person with 4 billion such computers A planet that has 4 billion such people A galaxy with 4 billion such planets And let the galaxy use the computational power for 4 billion seconds And you still only have 1 in 4 billion chance of guessing it right
He is talking about hashing functions. Hashing functions like SHA256 are relatively safe from quantum, attacks, but public-private key cryptography is not, and that is the danger. Well, currently public private key cryptography. There are quantum resistant cryptography things.
When he started mentioning the time KG++ would take, I started thinking that it must be the whole world could together crack that... *But...but he started talking about the age of the universe* 😑
the funny thing is, even if you had 4 billion galaxies of computers working on that problem, even if someone found the solution, because light has a speed limit, and the universe is expanding, you wouldn't even be able to communicate the solution to everyone.
Taran Van Hemert
Maybe they can use quantum entanglement as some form of communication. Not sure how though.
2010ngojo - Even with quantum entanglement you couldnt do it because it doesnt allow for information to be sent faster than light.
DeusExAstra I need to brush up on some physics
Taran Van Hemert sup taran
I might be wrong, but if you already have some sort of quantum powered way of comunication, then you DON'T NEED to guess in the first place, isn't? what is easier to get? Quantum powered way of comunications or a quantum computer capable to destroy to dust SHA-256 encryption?
* 507 Billion years later
"I'm in"
All
And I think by then if people would be still alive we would have 1024 bit secure lock or something
@@clayz1 bruh thats going to be around 3.09e1,292,913,986
exp(2)
@@Owenrandom brruh
Imagine a lucky bastard getting it right in the first guess.
Luckier than 4 billion Giga galactic Super computers would most probably be in 507 billion years lmao.
A 1/115792089237316195423570985008687907853269984665640564039457584007913129639936 chance?
That man would be so fucking lucky I'm pretty sure the universe would simply explode from the improbability. I mean, it's on that level
@@lucaslucas191202 chances are low, but never zero!
@@khf3940
So close to zero that you can safely call it zero though. Our brains aren't made to understand such numbers so when we say "not zero" we usually overestimate how likely it is. It's the same problem with the lottery. People buy that even though they mathematically shouldn't.
Because of that it might actually be _more_ correct to call it zero to make people understand what you're talking about.
A 256-bit quantum computer will do it in less than 6 months
The funny thing is, even though 256 bit is really secure, a number of people are just dumb enough to just tell attackers their password.
Yeah even my brother who set up my wifi router set the password as "password"
A chain is only as strong as its weakest link. You can have the most secure system in the world, but all you need is the wrong user to use 'password' as their password and a breach is inevitable.
Most forms of compromising rely on human error
The human link in the security chain is always the weakest; there's a reason most successful hacks are done with social engineering. (No really.)
@Jonny Nobody so you just replied to a 4-month-old reply that is on a 1-year-old comment and I only have seen your reply now(4 hours after you replied) so new password !1Y4 M4h
But can all these computers combined able to run crysis?
Yes, unlike you can not able in English
I think like 10 FPS in 720
But can they run Microsoft Flight Simulator 2020?
@@SBerTtube I had more of a stroke trying to read your comment than the one you responded to
New thing is MS Flight Simulator
In reality:
hashed "qwerty" and "password"
Boom!
Hit!
we need to write qwertyui because it requires 8 characters
Password hashed is secure just If It have never been hashed, and believe me, It probably have been, unless you take It into account to make your password.
The ingenuos be like: But my password is my birthday and just me have It as birthday!
Ah! Of course no one on earth have the same birthday as you! Hahahah
@@MrRenanwill A password with 990k characters would be possible to hack?
@@Lucas_strable impropable, but possible
Hash and salt, now you'll HAVE to brute force everything
i love you
uh...hi
We should just be friends
Why don’t you marry him
How could u not apreciate this
We are watching this at practically the same time!
Turns out it's preeeettty secure...
nyx211 not really...You see, quantum computing can cut down the required processing time(hence increased processing power) in logarithmic scale, which means cutting down the time needed to "hash" until match is wayyy lower compared to the current day method. So yes, we are quite fucked.
And don't forget that the hash can be guessed in the early stages, not always having to be the last computed hash, so there's a chance to be even faster
They already found solutions to way more secure encryption, so secure it can completely render quantum computers useless. This is done by using other quantum computers.
Lancelot V even if quantum computers turns out to test these billions of trillions times faster it would still be an unbelievable amount of time.
Arthur Machado it is not just billion trillion time faster, it is logarithmicly faster. For example a computer can do x amount of work at a time, the quantum computer can do x^8 amount of work, which is not just *fast* can justify it.
Theres always some kind of simplicity behind complexity. In computers, sometimes, the "security" looks like a big iron door, until you realize you can pass beside that door, coz theres no walls beside that door..
And that's exactly what hackers try to do. get your passwords or details in some other way than bruteforcing.
Which is actually one of the major reasons cryptocurrencies are such a misguided idea. It's like building a castle made of indestructible stone that has no guards.
I have done the calculations. I discovered that it takes a approximate maximum of 497.1026 centuries for the speed of 4Billion hashes per second.
@@harshavardhanamnholla7026Are you sure that is correct? I checkd and it takes approximately 8 × 10^59 years
@@jmiller6066 how so?
Q&A Answers: th-cam.com/video/8r5WKpK9-m8/w-d-xo.html
Edit: One thing I wish I had said explicitly is that even though a perfect and idealized cryptographic hash function would behave like a random function, in reality, there is some element of predictability to functions like those in the SHA-2 family. So even though SHA256 has a 256-bit output, it's actual level of security is lower than 256 bits.
You state that it takes an average of 2^256 guesses to get the correct hash. Wouldn't the correct value for that be 2^255 guesses, as you'd on average search half the solution space? Also, hasn't there been research on some cryptographic hash functions (not sure if it would include SHA-256) which dramatically lower these exponents?
There's been plenty of research. Governments have lots of cash and lots of reasons to find a way to hack into these hash functions, but SHA-256 has not been "cracked" yet. As the previous video says, no one really knows if it's mathematically cryptographically secure because it's very complex math. SHA1 is not secure but only because it doesn't require enough computing power to break. It only takes one Google to crack it. Google "sha1 cracked".
In the video you describe the complexity of a brute-force pre-image attack.
Wouldn't a collision attack work for digital signatures?
The complexity of that for SHA-256 seems to be 2^65.5, which while still not being practical is not as impressive as 2^256.
Edit: 2^65.5 attack that I mention seems to apply only for a SHA-256 with a reduced number of hashing rounds performed (31 out of 64), for a full method there's a 'birthday collision attack' with a complexity 2^128
-2^255 is right on average- [see correction by 3blue1brown below], but complexity theory usually uses big O which is worst case, I think that might be way people often say 2^256. As for collision attacks, finding proof of work is indeed not a pre-image attack, think of the difficulty as bounding a set of elements, and you get a chance for a collision with each of those. But that doesn't apply to digital signatures - in bitcoin those are made using ecdsa, with the secp256k1 curve, and I think it's possible to attack it more efficiently than brute force, but I don't think it's as cheap as a collision attack. As far as the size of the search space, NIST used to recommend 2^80 for being secure for the "foreseeable future", otherwise known as a security parameter of 80 bits, and since the 90s they changed the general to 128. Collision resistance requires a hash that outputs double that bit width, so modern hashes are usually 256 bits (and also why ripemd and sha1 are 160, note that ripemd is used in bitcoin for addresses, on top of sha256 if I remember correctly). Finally, if to attempt to future proof against quantum computing, if you double the bitwidth again then this is supposed to be enough to resist nondeterministic collision searches, which is the main reason to use 512 bit hashes as far as I know.
Update: I should say - regarding ecdsa attacks - I think that because I know I don't know enough about the algebraic structures of elliptic curves, but as far as I know the 256 bit representations have some bias because of them, and also because improperly chosen curves are breakable, but don't quote me on this since I don't actually understand the details.
To the point about it really requiring half as many guesses, (i.e. 2^255 not 2^256): This is true for something like hacking a digital signature, where you are methodically going through all possibilities. But if a cryptographic hash function truly behaves like a random function, guessing and checking a nonce with a hash will not look like going through all possible hashes one-by-one, it's more like rolling a die over and over until you hit a 6, in which the expected number of rolls needed is 6, not 3. While running this GigaGalactic supercomputer, many of the guesses will actually collide, so it is not a methodical search through all possible hashes.
However, as you point out, the actual security on SHA256 is indeed lower than 256-bits. It turns out not to quite behave like a nice random function. But this discussion just centered on an idealized cryptographic hash function.
"...so you're telling me there's a chance!"
I knew it! ....I read ya...
YEAHHHHH!
Bonus fun fact: If you actually take 4,000,000,000 to the 8th power, what you'd get is closer to 2^255 than 2^256 (specifically, about 2^(255.18), or 1.13 * 2^255). Approximating 2^32 (4,294,967,296) as just "4 billion" ends up losing more overall value here than you might expect.
So basically you lose about half the total value.
so the final time to take has to be double
Small note: it would likely not take you 2^256 guesses to get it correct, as that is every single possible combination of guesses. Rather, it would take an average of 2^255, which is the halfway point between 0 and 2^256 (as any power of 2 is twice as many as the previous power). Minor detail but helps with the general understanding.
ALittleOff the worst case scenario is implied I guess, Big O wise
ALittleOff so with the giga galactic super computer running for 37 times the age of the universe it is just a 1in 2 billion chance. Got it.
No, it would still be 1 in 4 billion chance
To chime in a year late, ALittleOff was correcting at 0:35 when he says it would take “on average” 2^256 guesses. Worst case it would take 2^256 guesses, but on average, it would take 2^255 + 1/2 guesses.
You can find this with some simple math: Let n = 2^256 just for ease of reading. Since there is a 1/n chance for the hash to be any numbered guess, we can find the average number by adding up the possible numbers of guesses and dividing by n. The number of guesses can be anything from 1 to n. If we add up those numbers, we get n(n+1)/2. Dividing by n gives us (n+1)/2=2^255 + 1/2.
There is no such a thing as worst case in here since(assuming sha256 to be an ideal hash function) every new guess gives you exactly 1/2^256 probability of success independently of previous guesses. Actually, after 2^256 guesses you'll still have failed to find the preimage wuth probability very close to 1/e.
"next, try to imagine 4 billion copies of the milky way" ... okay, I'm out.
I know it's quite a while ago you commented here but how does it make sense to take 4 billion copies if only 1 percent of 1 copy actually is filled with planets that are important for the calculation?
@@cedrik1031 It's not my hypothetical, ask him that.
@@Superphilipp yeah I know that but I doubt anyone would have seen it if I wrote my own comment, so I just tried my luck with you but thanks for the answer✌
@@cedrik1031 I thought he said imagine that the Milky Way was filled with 4 billion planets where 4 billion peoplee had access to a Googlekilo worth of computers. Meaning that in this hypothetical more than 1% of the Milky Way would be filled with planets
Man this acid is really messing with me
Everyone of this man's videos is like a weird mixture of extremely informative yet peaceful and therapeutic LOL. Another amazing video!
Worth mentioning: Some cryptocurrencies (I think Litecoin does this) use a different hash function called scrypt instead of SHA-256. scrypt is designed to be impossible to create application-specific integrated circuits for, because it requires large amounts of RAM and computing power, unlike something like SHA-256 which is essentially a bunch of logic gates.
Neat!
quaternary It took awhile but we already have 500mh scrypt ASICS. Still Ethereum is only mined with GPUs.
The number of all chess games possible is arround 10^10^50. I love this number.
There is no such thing as a program that is impossible to design an ASIC for.
Impossible is really the wrong word. Impractical is better. It wouldn't significantly improve your efficiency enough to matter even if you did make an ASIC for it, basically.
Amir Abudubai Correct, mostly, though it will just start looking more and more like a CPU ;)
These coins also have the feature that they can modify the parameters without creating a new chain, so you would either need ASICs with redundant hardware (fails the "becoming a CPU" stumbling block), of you would need new ASICs each time this happened (fails by being infeasible due to cost and time)
Really an amazing way to quantify these numbers...great job.
So often when a number is big enough it just falls into the category of "a really really big number" so people never, or, could never, figure out how big it really is.
4:33 Now the channel surpassed 2^21 subscribers
And close to reach 2^22 subscribers
Congratulations
I always loved your videos, the quality of the explanation of the topics is simply unmatched, I swear I learned more from this and other educational channels than from school/college on the last 4 years
Keep going, the world need more channels like this.
2^22 surpassed, and in the middle in the way to 2^23
Introducing, quantum computers! (all traditional security screwed up)
hey hello
Uh, sure, but not hash functions. Further, Shor's algorithm (which is the one that gets all the hype about this) only works on encryption schemes that depend on factoring large numbers, namely RSA. Since RSA uses prime numbers, it makes factoring the multiple of two of them really hard (the numbers are huge). We can revamp everything to stop using RSA (and already have been, for many, many years) relatively easily, given the impetus that it'll be completely broken soon enough.
We've already got encryption schemes that can run on classical computers that are hardened against both known classical and known quantum attacks. Often they take more compute time and are more complicated to implement, but with how classical computing is still getting faster, and specialized hardware can be built to accelerate encryption and decryption once the standards are set, this really shouldn't be a big issue.
@@liesdamnlies3372 is lattice-based cryptography a candidate for post-quantum
@@absolutezero6190 I wasn't familiar with them until you mentioned it and I did a little bit of reading. Seems like it though.
nah as long as the "checker" has traditional methods, quantum computing wont work.
♫ 2 to the 2 to the 2 to the 3 ♫
♫ i like good currency and i like good trees ♫
♫ conversion and currency ♫
♫ I'm a menace, a miner, a hash-figure finder ♫
♫ Gimme a table and in less than an hour ♫
♫ Give the chain a new link in it ♫
♫ Get some bits for fixin' it, Slide 'em in some hooker's tit ♫
♫ so, find that hash for me, find that hash for me ♫
♫ come on, mine, find that hash for me, find that has for me ♫
🎵England is my city 🎵
tits
3 blue 1 brown always comes In clutch with the visualizations. This reminds of combinatorial explosion, and how often it comes up in real world problems, it would be interesting to see you make a video going into depth on this topic.
My personal favorite "big number" is the number of atoms in the universe - about 10^80 (Wikipedia), or 2^83. Molecules vibrate at 10^13 .. 10a^14 Hz - call it 2^17. So, if every atom did one guess-and-check every time it twitched, you'd still need 2^156 seconds - about 2^40 years, which is 250 times the age of the universe.
2^256/(10^80*10^14) is about 1.2*10^-17, so your scenario would actually only take around 12 attoseconds.
Mines TREE(G57K57)
This video is pretty misleading. It's a good illustration of how big a 256 bit number is, but NOT a good illustration of how secure 256 bit security is. These cryptographic hash functions are broken and need to be replaced every few years. This happens because weaknesses are found in the algorithm that make them easier to guess, and has very little to do with raw computing power. SHA-1 is now considered dangerously weak, and output 160 bits. No one made a computer that checked all 2^160 combinations. People found weaknesses in the algorithm. This has been true for almost everything in cryptography from the Enigma to MD5.
the weakness is collision and i think in this case it's not important. with files you can add bytes and so on to create the same hash for 2 different files... with blochchain it's much much harded even if sha256 would be cracked.
The CIA probably already has quantum computers that crack this shit in hours. I mean D-wave is a thing so...
David Vermillion Thats false, Current quantum computers are way weaker than the regular(Binary) computers.
Well... It's important to know how many bits you need in an algorithm where the only option is brute force. And it seems as though 256 bits is enough for that. It tells me that there's no need to jump up to 512 or 1024 or more in order to secure against brute force attacks, we've already got all that we need. How many extra bits of padding is needed to compensate for an algorithm's flaws would require a video of its own.
so do you mean that after enough time patterns start to become apparent and you can start reducing the number of bits you have to guess?
"It would require on average 2^256 guesses".
Shouldn't it be "at most" ?, if all the guesses are wrong until the very last?
And on average (2^256)/2 guesses?
So 2^255 guesses
@@aarushparvataneni3249 Oh yeah that's true
I think it's 2^256 on average. You may guess a new message which evaluates to a hash you've already seen before.
No. I just replied to another comment about this, where 3blue1brown himself commented: "While running this GigaGalactic supercomputer, many of the guesses will actually collide, so it is not a methodical search through all possible hashes". So yes, if you do it this way you can expect to find the answer after only checking half of the pool:
Have a list of all 256 bit numbers, guess 1 & remove it from the list & calc the hash & check it, repeat until you have the hash you want.
No. You could guess 2^1000 times and still get it wrong, there's no "at most guesses" in probability.
I just want an hour long video of a growing binary number at 0:11
1 week*
Python is fast. And you should know that printing to the console is an IO task and C++ isn't that much faster than any other programming language at doing that.
@Omar alpjaly For the differences between languages being "very small and hardly noticeable", python sure takes 62 times longer than c++ to count to 2^32 - 1
Yes I tested it
@@chappie3642 considering that it's a fucking TH-cam comment, it should be obvious why a smaller line count as well as more readability is more desirable than execution time, because guess what, everyone READ the comment as opposed to execute it.
Furthermore, if you still insist on execution time mattering, then I'm sure that you'll be thrilled to know that since the bottle neck in both cases is the console, both python and c++ have the same execution time as they're both faster than the CLI's output capability. In other words, by using python, you'll literally write 2 lines of code to achieve the same result in the same time as if you did it in c++.
>>> # in python:
>>> import time
>>> x = 0
>>> while True:
... print('{0:b}'.format(x))
... x += 1
... time.sleep(0.1)
2:51 okay I get it, its a large number
Not as large as a Googol :)
CarBricksCity and a Googol isn't even anything near Grahams Number.
graham Number is infinite time smaller than infinity
But can it run Crysis?
It's a relativ large number
Chinese/Japanese/Korean use a different system for abbreviating large numbers: 10,000 is 万 or equivalent; 100,000,000 is 億 or equivalent; etc.
And the Chinese, Japanese, and Korean subtitles _all_ use "40億" instead of "42億" or "43億" when translating "4 billion". It hurts to look at.
This video is awesome. Imagine a super advanced galactic empire just trying to break into a single file.
Mr. Rigden's Channel Sub-humans aliens in the Year 70.5 Billion in the future and still to get the private key of Satoshi Nakamoto
@@lagillas The easiest way to solve the problem is to find the root of the problem. The easiest way to crack Satoshi Nakamoto's private key is to point a gun at him! 😳
how are all of his animations always so smooth?
Video is in 60fps
1 kilogoogle of computing power for rendering frames
Well, he is a mathematician and a programmer...
It's because he uses his self developed animation library "manim", written in python.
@@vinzer72frie i heared that humans can only hear 30fps
Hey congrats on surpassing 2^22 subscribers!
Literally just finished the last video. Loving these cryptography videos!
Yet you weren't able to understand when Oscar explained the idea of a budget surplus to you??
+adrian peiron You are right in that many of the existing economic structures were created by the elite to serve the elite.
Modern economic 'science' is applied mathematics. You have to know the rules to led you to a sound methodology. Without that you are just a theorist no better than a hack.
Unfortunately there are certain fields in economics that are stuck in a habit of intellectual masturbation rather than doing something based in reality.
Michael Scott
You are the best math teacher I've ever come across. Amazingly lucid.
Now in 2021, you're almost at 4^22 subscribers. Keep up the good work
I think you mean 2^22? 4^22 is... _a tiny bit_ larger.
Oh, and keep in mind, that they'd all have to be working on the same, single hash/key.
Yeah exactly they need to communicate to not try the same thing some other computer already did.
@@sayamqazi and that, will use petabytes of ram, and even an i9 propably can't handle it
phyrexkasgaming definitely* also, we would have different processors for maximum efficiency and just communicate it all through a database. The computers would each have assigned images which they process into hashes and repeat. That’s how I would do it, but we would be limited heavily by physical and storage space.
They don't really need to communicate at all. When you assign the problem you can easily just say that A solves numbers 1 to 1000, B solves numbers 1001 to 2000 etc. Report back if you have something. Then you just wait for someone to report back that they either are out of numbers to solve or have solved it.
@@ShadowManceri Horray for basic software engineering logic. ... Sadly in short supply at most schools that teach software engineering but whatever...
3:14 to 3:30 will be my new phone ring or my alarm sound :D
Great visualization, as allways ^-^
Twin Helix you mean Pi to 3:30
Twin Helix I
0817283866
yes
yes
"Next, try to imagine four billion copies of the Milky Way."
No. My brain will break if I try to imagine that.
*try*
actually only computations by a single GPU can't be imagined
This is an excellent illustration of the number 2^256. Cryptographer Bruce Schneier has an interested paragraph in his book "Applied Cryptography", suggesting we don't have enough energy in our solar system to count through 2^256. This is because the 2nd law of thermodynamic states that a bit change requires minimum energy of kT erg, where k is the Boltzman constant, T is the absolute temperature. 2^256 is such a huge number, that to cycle through will require more energy than our sun can produce for the next so many billions of years, even including the supernova. Notice the video assumes billions of galaxies. So with the current physics and math 2^256 is beyond reach. However, we don't know about new physics and new math...
If the universe is infinite, then someone, somewhere will guess and get it right on the first try. In fact, infinite number of people would.
already happened, infinitely many times
But it would also take infinite time to transmit the correct answer back to earth.
@@MAUROtele thar comment already happened an infinite amount of times
@@theodiscusgaming3909 not if it got there an infinite time ago
@@B-DINO the universe has a finite age though
I doubt anybody will ever see this, but I came up with my own analogy to describe how absurdly huge this number really is. FIrst off, I saw in some other random YT video - that humans are pumping out roughly 60 quintillion inputs for the SHA 256 per second. So if humanity continued calculating at this pace, how long would we have to keep computing before we found 2 inputs that equate to the same output?
TLDR: A long fucking time.
Analogy: We have a lot of time to kill, so let's start by imagining that we kill time by walking in a straight line until we reach the moon. Once you reach the moon, turn around and come home. When you get home, (you would have been gone roughly 18 years) buy a powerball ticket. If that ticket wins the jackpot, buy a mega millions ticket. If the mega millions is ALSO a winner, flick a penny into the Grand Canyon.
After flicking the penny into the Grand Canyon, continue on your walk - back and forth from the Earth to the moon and back. Again, when you return to Earth, buy another powerball ticket. The only way you will ever throw a penny into the Grand Canyon, is if both the Powerball AND Mega Millions tickets are winners. As you could imagine, you're going to do this until all 5.45 million cubic yards of the Grand Canyon is completely filled to the brim with pennies. That's a lot of lotto wins!
Of course you haven't even scratched the surface of how much time needs to pass, so we're going to continue on with this pattern - until you have filled the Grand Canyon with pennies 200,000 times over. Eventually I'm assuming you will get bored of filling the Grand Canyon with pennies, so after 200,000 of these fills you can switch to the Pacific ocean. The pacific ocean is a lot bigger than the Grand Canyon, and it would take about twice as long to fill with pennies as it took to fill the Grand Canyon 200,000 times. Woah.
Now that the pacific ocean is filled to the brim with pennies, empty it out and find a nice place on Earth to park a Chevy Malibu. Return to the Grand Canyon - Fill it with pennies 200,000 times. Return to the pacific ocean, and fill that with pennies as well. Keep in mind, each penny represents winning back-to-back lotteries after a round trip from the Earth to the moon and back at a walking pace. Each Chevy Malibu is going to be the equivalent amount of time as: filling the Grand Canyon with pennies 200,000 times as well as the pacific ocean once.
How many Chevy Malibus will we have to stack before we finally have run out of possible calculations? Answer: It's a fucking lot of Chevy Malibus. You're gonna stack those babies on top of each other until they too reach the moon. Then you're going to start a new stack of Chevy Malibus - and that stack too will also reach the moon. And then you're going to do another.
and another
and another
and another
until you have reached roughly 33.7249 Earth-Moon length stacks of Chevy Malibus. Now that you are exhausted, sick of pennies, and a little over 61 quindecillion years old, you can drive the last Chevy Malibu down the giant cosmic escalator of Malibus from roughly 3/4 of the way to the moon back to Earth where you will finally get to rest - and enjoy seeing 2 different inputs that provide the exact same 256 bit output in the SHA 256. I can only imagine what those 2 different inputs look like. I hope you'll share with the rest of us. Is it a picture of a Chevy Malibu and the dimensions of a penny? Is it one of the back-to-back lottery winning numbers? Who knows? You do. Because you did it.
I must say, you have a brilliant way of explaining things!
Thanks for sharing this sense of scale! It's amazing to think about how large the numbers we are able to represent actually are. すごい!
Tim Swast です
someone commemted sarcastecly that if one randomly guess in first try,,,,i want to say that,,,, chances are zero not near zero,,, in probability we simply assume that probability< 1/10⁵¹ is zero,,, not as near zero but zero,,,
This example is beautiful.
I once saw an argument based on energy rather than speed that followed this very general outline:
Suppose you had a computer that operated at absolute maximum theoretical efficiency, so that there was no way it could possibly use less energy to flip a bit from zero to one, or one to zero. Suppose that's all this computer did: flip a single bit from one to zero and back again, over and over. (No counting: that's too complicated, reserved for a future version of the system. Certainly no complicated hashing or other common brute-force crypto-attack techniques: this is just a prototype.) Suppose you put this computer in the most naturally-cold place in the universe, to maximize its efficiency. (Don't want to spend energy on cooling, only on bit-flipping.)
Now suppose you could capture the entire energy output of a standard-size supernova, and feed this energy into your super-cold bit-flipper--assuming the existence of whatever energy-storage technology would be necessary to spread out the energy consumption over whatever time interval the bit-flipper required.
A supernova's worth of energy would be enough to power the bit-flipper through about 2^192 bit flips; which means you'd need to feed in 2^64 supernovas to get all the way up to 2^256. So that's version 0.1. By version 1.0, you'd need an actual crypto-attack algorithm, rather than just bit flipping, where each of the 2^256 attempts would require hundreds of thousands or maybe millions of bit flips. But..first things first.
So I probably have the numbers wrong, and perhaps some of the details as well...but that was the overall shape of the argument. I'd love to see you do a video on the real argument with actual numbers.
*Another statement that explains the size of 2²⁵⁶...*
$2²⁵⁶ per *millennium* is enough to make everyone on Earth *(distributed)* an *unvigintillionaire* in ~0.27 seconds, and 1 unvigintillion is 10⁶⁶, which is typed/written out as 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000.
To show you how small 2^256 is:
2^256 < 10^78 < Googol < Googolplex < Googolplexian < 3^^^3 < G1 < Graham's number
To show you how big 2^256 is: 00:00
That's small. Very small.
@@carbrickscity its not small you can just compare it to a bigger number
If you compare it to daily numbers then yes it is big but compare to the world of big numbers it's small compare to even googol, which is just the beginning of big numbers. There is an infinite number of numbers bigger than it.
@@carbrickscity Yes but compared to how fast computers can generate and guess numbers it is really big. Imagine flipping a coin 256 times and you need to land on heads every time. How long will it take you to get there? A really long time. Granted, a computer can generate number much faster than you can flip a coin but the problem remains - it will take a really long time. You will reach the heat death of the universe before then. And, in a couple years, SHA-512 will be adopted and now the problem is significantly longer.
Now you're almost at 2^19 subs. Congrats!
Thanks! I think a second Q&A round will be in order soon.
The video is great and I'm not at all trying to discredit it, but there's a small error in which it is stated that, on average, it would require 2^256 guesses to find the correct hash. Since 2^256 is actually the total number of possible guesses that any given sha256 can be, the average number of guesses needed per hash would be 2^256/2 = 2^255 due to the random nature of any given guess being correct. Not that such a difference matters too much when talking about timespans 37 times as long as the age of the universe as we know it. Just thought I'd clarify.
wow that's big.
just watched this and you cryptocurrency video, this blew my head as I know an analogy to describe what relationship 1 Billion is to 1 Million using time. The crypto video answer so many questions, thank you
steve martin what's that analogy?
Glad to see you getting close to 2^32 subscribers! I've always enjoyed the topics you discuss and how you explain them :)
approx 2^22.213 so far
Bruh
yea, I think you meant 2^22
@@ryanKeenN 2^22.27 now
2^22.253 so far
That was actually fun to watch. Cheers
This is perfection! Your explanation in brilliant! Now can you do one about the private key security function and the possible key combinations. 🙏
Google++ xD
is used by 1/(4 Billion) people
That name made me think of C++
Google+ next gen (but stille not popular xD)
We can only wonder why it wasn't ++Google. What is it with people and disliking prefix?
LunarCoffee because it takes longer to recognize what it actually is about? Would be my guess.
I.e. For c++, when the 'c' is spoken, I know it's about a programming language and am then waiting to hear which one.
In this video it says 262,144 subscribers (some 4 years ago). Today, 15 June 2021, we're at 3,74 million. As a lot has happened in these 4 years (faster hardware and growing number of crypto-miners) it would be nice to have not just an update, but a now/then comparison. Congrats and keep up the good work!
@3Blue1Brown can you consider doing a video about md5 and sha1 hash colisions? thanks for the amazing explanations again
Quick maths!
Admin Panel, Bootstrap, On-line chat, Responsive, Sample Data Installer, Theme Color Switcher. e-web.top/category/security/
is just a product of two prime numbers
You need a deterministic solution for the system N=x*y
No dictionaries checking, no iterations, just a deterministic solution for that system of equations where N is your 256 digit number, and x and y are two different prime numbers.
Yo set up the system, you get the only one solution. End of the story
I reach a non-linear system of 5 equations with 5 unknown parameters. But hard to use into large digit numbers, I need new algebra tools to multiply, square root and potenciate them efficiently
I do invest and refer people to Mrs.ChangChang because she is the best trader I have seen
You can can reach Her on what:::::::::app
🇱🇷.+1......46/9-3[12-2)97....1
My first guess: 111111111111111111111111111...111110111...111111111
Computer: Hello, sad loser
Me: I’m in
first guess: 01000101101001001010101001111100101000101101001001010101001111100110010001001011100101010101010110100010101001010110101010010000010100010110100100101010100111110010100010110100100101010100111110011001000100101110010101010101011010001010100101011010101001000001
000011001101010101010101010101101010101010101001000010101020101
@@guardianangel1468 I'll use your guess as my key, thanks
@@garrettzucker2894 wait, that's illegal
3:16 lol i love that phrase
2^256 is 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936.
Time to borrow some intergalactic supercomputers from alternative universes...then borrow a time machine...then a inter dimensional portal
Yeah, just gotta make some calls
1:26 And there's me wondering how the game Factorio reached such a fine level of performance efficiency and my quad core still struggles really hard with more than 100k calculations per second
Hah. I remember watching this video (and the main one) on release day back when you had 2^18 subscribers (262,144 people). But now you've recently passed 2^22 subscribers (4,194,304 people)!!! Great work, 3b1b :)
4:23, now the channel is ½ of 2^20 in a span of 3 years! 2^256 will take a long time to crack!
2^21 and counting
2^22 now, keep going.
This is good but you should remind your audience what Edward Snowden said (paraphrasing) "Encryption is secure but end point security is generally terrible." Any system is only as strong as its weakest point.
Congratulations on 2^18 subscribers. Well deserved. I hope you get to 2^20!
Yes cant do much if the end users are stupid
"...now, this is a number, so far removed from anything we ever deal with, that it may be hard to appreciate it's size."
*That's what she said*
"But let's give it a try!"
Giggity!
wouldn't it be 2^255 guesses on average? 2^256 possibilities, try half of them and you have a 50% chance of breaking through
+Abhishek Shivkumar I thought the same...
Not really, since the outcome of the hash function is unpredictable, it can (and it does) give the same output for different messages, so basically, in each try you'd have 2^(-256) chance of guessing it right independently of how many tries you've done before.
That gives you sum over n of n*p*(1-p)^(n-1) from n=0 to infinity average guesses (where p=2^(-256)), which you can solve using n*(1-p)^(n-1)=-d/dp((1-p)^(n)) and trying to write the sum as function of it's derivative and solving the differential equation, or alternatively writing n*(1-p)^(n-1) as (1/(1-p))-*-((n+1)-*-(1-p)^n-(1-p)^n) and trying to write the sum as function of itself and solving the linear equation. Or even more alternatively, you could plug that on wolfram and see that when m goes to infinity (the sum goes from 1 to m) the sum goes to 1/p, which is 2^256.
Another thing is that the average amount of guesses isn't necessarily when amount that gives you 50% chance, that's the median. But since if we could avoid doing repeated guesses the probability would grow linearly, the 2 would coincide.
Yes, after you checked half of them, the chance of having found the right hash would be 50%. This would also be the average time it would take to find the right hash.
is not 255 vs 256 remember that he group them in 8 groups of 2^32
So the difference is actually 2^224 vs 2^256
Nice mind blowing video. Loved it. A followup that would be neat is if quantum computing advancements in processing power was projected out 10 years what would that look like in terms of quantum computers coming near this problem mathematically.
5 years later...
how 256 bit encryption is useless thanks to quantum computers
Ricardo Milos 🙄😂
😂😂😂😂 absolutely 👍
+1
quantum computers in 2024??? LOL!!! do you mean 50 years later?
Quantum computer can only break RSA with has keys of 2048 bit 256 bit RSA has been Made useless and quantum computers Cannot break AES
Now imagine doing these guesses manually by hand instead of a GPU in even the first step.
3:16 what i heard just now was really really technical
Holly crap I'm addicted to this.
Thanks to smaterEveryDays to send me here.
This video is pretty misleading. It's a good illustration of how big a 256 bit number is, but NOT a good illustration of how secure 256 bit security is. These cryptographic hash functions are broken and need to be replaced every few years. This happens because weaknesses are found in the algorithm that make them easier to guess, and has very little to do with raw computing power. SHA-1 is now considered dangerously weak, and output 160 bits. No one made a computer that checked all 2^160 combinations. People found weaknesses in the algorithm. This has been true for almost everything in cryptography from the Enigma to MD5.
This video is incorrect because it expects a perfect hash function, which would give a truly unique hash value for every possible value. But because we are using a finite range (2 ** 256 possible values), this is impossible.
Knowing this, we can use what is called a birthday "attack", which is based on the principle described above and allows us to reduce the number of guesses from 2 ** 256 to "only" 2 ** 130 for a probability of a 0.9999 of obtaining a valid guess. EZPZ guys
It's so fun to hear Grant say "wow, we recently passed 262k subscribers" and I look over to the sub count today and there's 6.21 MILLION of us.
6.38 Million now
Answer: Way too secure, SAVED YOU 5 MINUTES
My Intel 8086:
Heavy sweating.
🙃
Nice video. Now you're close to passing 2^22 subscribers.
2^22 subs?
@@broodjenoodles 2 to the power of 22 or 4194304 subs
@@ThatJay283 😂
Ah yes ! The 3 AM content i was looking for .
What about SHA512?
The naming was really nice
0:37...The worst case is when you need to make 2^256 attempts, and the best case - when you need to make just 1 attempt. So... why average number of attempts is 2^256?
So the average number would be 2^255
@@FeloLato Wow, an answer to 8 month old comment
but if P=NP, we are fucked no ?
We would be indeed. Also, quantom Computers. (Probably)
www.quora.com/Is-cryptographic-hash-inversion-believed-to-be-NP-complete-or-NP-hard-etc
If P=NP and an AI generated, we would be fucked^256
Not necessarily. Even if P = NP, you still would have to show which P replaces the current NP. Not easy.
I don't think there is any algorithm for quantum computers that easily solve hashes. And currently, making them say 15 = 3X5 is a big success, so I think there is no need to worry before a few years/decades
Now you have surpassed 2^22 subscriber ;)
Just imagine your first guess from all of these 2^256 turns out to be the true one
Don't ever go to Las Vegas.
Friendly advice: You should not try gambling ever.
But it would still be a 'Guess'.
Try to calculate the probability of guessing the correct answer twice. :)
@@sarthaksharma4816 Due to how exponents work I think the answer is 2^258 which seems like a difference but that's really pretty massive.
@@sarthaksharma4816 Correct me if I'm wrong, wouldn't it be for guessing it once :
1/(1/2^256) = 1/1.1579208923731619542357098500869x10^77
And then to guess it twice you square it? So, 1/1.3407807929942597099574016910872x10^154
so chances are like getting text from crush
It also depends what do you mean by "security", as the latter comes in many forms: confidentiality, data integrity and so on. Also when we consider just hash functions there is always the problem of collisions (pigeonhole problem), i.e. finding two inputs that map to the same output. Because of the birthday paradox there is already a 50% chance to get a collision within 2^128 inputs.
"Never tell me the odds!"
And, assuming Moore's Law continues unabated, this entire process will take 1 second around the year 2540.
Getting close to the 2^22 subs mark. Keep it up!!
Love this~
any idea if quantum computing might help in bitcoin mining?
Not exactly, it would destroy the premise of Bitcoin since a single Quantum Computer will have enough computation power to outperform the whole network.
If quantum computers someday achieve enough power to guess a PV key.... Well we don't have to care about money anymore because that fkn thing ( quantum computer ) would be able to create AI that will do EVERY work for us
Dont ever dream about those computers working. Because when that day comes, cracking current block chain is going to be so easy since quantum computer can easily factor huge prime number with Shor's algorithm.
Not at all. Quantum computers will reduce the security of public keys encryption into dust because the shor's algorithm can factor primes really fast. So it would take almost no efforts to crack any current crypto system because they all use ECC. If you can factor primes fast, you cracked pretty much all the public encryption system because they are all based on the idea of factoring being a hard task.
@louisphillippe1100
Nice thought but not every Public-Key Encryption system uses the premise that the prime factorization of large integers is infeasible.
Look at the discrete logarithm. IIRC it doesn't have an algorithm that is designed for quantum computers.
(Although polynomial time would most likely still be too little to actually stop such a machine...)
Two mistakes in the first minute of the video:
1) it is not necessarily the ONLY way to guess all combinations. SHA256 algorithm could be broken. Happened to other hash algorithms like DES before.
2) it takes on average 2^255 guesses for brute force
2 is wrong. It is 2^256 as you are not going through the hashes, but through random guesses, where the hash could be the same. You have no way of avoiding double guesses (at least right now)
Trading has been the best but one needs a professional trader to be to secure his or her coins
That is very true
I lost alost Alot before I was able to get reaches to Mrs.ChangChang
She Is a professional and reliable trader
I have so much Alot of people speaking good about Mrs.ChangChang
She must be a very nice trader please how can I be able to rwach her?
pretty sure dream could "guess" them first try
I was thinking about
A GPU that can do 4 billion hashes per second
A computer with 4 billion such GPU's
A person with 4 billion such computers
A planet that has 4 billion such people
A galaxy with 4 billion such planets
And let the galaxy use the computational power for 4 billion seconds
And you still only have 1 in 4 billion chance of guessing it right
Pretty darn safe.
#savedyou10minutes
Spoiler alert: The Universe is actually a computer that's trying to find a 256 bit hash.
Excellent video mate, loved the visualizations of 2^256. Really puts it into perspective !
what about quantum computers? it is said (theoretically) it takes less then 1 hour to decrypt a 266-bit signature with quantum computers...
He is talking about hashing functions. Hashing functions like SHA256 are relatively safe from quantum, attacks, but public-private key cryptography is not, and that is the danger.
Well, currently public private key cryptography. There are quantum resistant cryptography things.
With quantum computers quantum cryptography might come, i.e. using entangled particles instead of generating keys.
current quantum computers are for optimisation. They use the fundamental laws of the universe to solve problems.
d-wave, NASA.
When he started mentioning the time KG++ would take, I started thinking that it must be the whole world could together crack that...
*But...but he started talking about the age of the universe* 😑