Jump to content
pvap

Is Ripple vulnerable to a "collision" attack?

Recommended Posts

19 minutes ago, pvap said:

I think the threat is very real, and honestly a bit upsetting.

Do you think you actually understand the maths behind this or is it more based on a feeling that something on the internet sounds smart because a lot of numbers and formulas are used on a website? I don't mean to sound condescending, but even that page itself states that the search space is far learger than 128 bits...

Share this post


Link to post
Share on other sites
20 minutes ago, Sukrim said:

Do you think you actually understand the maths behind this or is it more based on a feeling that something on the internet sounds smart because a lot of numbers and formulas are used on a website? I don't mean to sound condescending, but even that page itself states that the search space is far learger than 128 bits...

You obviously missed a key point Sukrim.  I'll make it simple for you.  All keys generate hashes (viable) and it is from this fact that people derive their sense of security in the magnitude of the number of keys.  Inversely however some 128-bit potential hash values don't have keys (unviable). The viable hash realm is possibly a lot smaller than we think, which increases the possibility of a collision, as purportedly demonstrated by this project.  Think of it like this, imagine 1000 doorkeys are given out, all of them work, but the community has only 500 homes; how safe would you feel knowing that someone else out there might have a working key?  We can't prove it out of course because that would imply we could check all the answers (breaking the intent of the hash algorithm).  So here we are with this hashing algorithm that promised to as evenly distribute hashes as much as possible (I totally bought into this too), yet in a short period of time with limited computing resources, we've got real-world examples of successful collisions.  The promise of even distribution appears broken.  This means that many, possibly lots of keys, produce the same hash results.  Following?  (not trying to be condescending).  So if we could magically remove the duplicate keys from the full list of keys, we're now approaching the potential of regular collisions against all the blockchains' current addresses with balances.  In fact, we can statistically originate the actual ratio of viable to unviable hashes when we have a few 1000 more collisions.  Before you throw 29 digit numbers around, you need to reconcile how these collisions happened, or provably refute them, or blindly accept them.  Denying them is just religion.

It may be a mathematical curiosity at this time, but quantum computing will chew through big spaces like a T-Rex after a hunger strike.  Don't get me wrong, I'm still waiting for someone to expose shenanigans on this project, I'm having a really tough time digesting it myself, but better to consider the possibility that it could actually be a problem and try to understand it, than patronize people looking into it.   

Share this post


Link to post
Share on other sites

To gain access to a Ripple account requires one of two things:

The seed (the string value begining with s and which is 128 bits long, or the secret key that the seed generates using Ripple’s secret key generation algorithm which has is a 256-bit value.

Even given billions of perfectly efficient computers, a brute force search of either keyspace is, given the fundamental physical laws of the Universe, essentially impossible. 

If you assumed you had a billion computers each running a trillion checks per second and you could eliminate 90% of the keyspace right off the bat, it would still take you over a billion years to go through the remaining 10%.

Not even the best  quantum algorithms available can help you if you must use brute force. What you need is a massive cryptographic breakthrough.

We do have some such breakthroughs… in theory.

We have Grover’s algorithm and Shor’s algorithm. Given practical quantum computers, messages signed with the secret key of interest and and the corresponding public key, you can mount attacks that are in “easier” complexity classes.

But we aren’t there yet. The biggest problem is the lack of a quantum computer big enough. Maybe in the future such quantum beasts will be available at your local Best Buy… but not yet.

Long story short: I’m not worried, for the short and medium term. I agree it’s something to keep an eye out for, long term. And if my estimates are, perchance, wrong that’s still fine: we can migrate to post-quantum crypto.

Hopefully we’ll have some practical (as in signature and key sizes aren’t huge) post-quantum signature algorithms ready by then.

 

Share this post


Link to post
Share on other sites
37 minutes ago, nikb said:

To gain access to a Ripple account requires one of two things:

The seed (the string value begining with s and which is 128 bits long, or the secret key that the seed generates using Ripple’s secret key generation algorithm which has is a 256-bit value.

Even given billions of perfectly efficient computers, a brute force search of either keyspace is, given the fundamental physical laws of the Universe, essentially impossible. 

If you assumed you had a billion computers each running a trillion checks per second and you could eliminate 90% of the keyspace right off the bat, it would still take you over a billion years to go through the remaining 10%.

To the point, how do you account for the purported collisions discovered by this project?  Is it apples to apples?  Fraud?  Nonsense?

https://lbc.cryptoguru.org/trophies

Look at the most recent one.  Over $7000 worth of bitcoins cracked open.  If this doesn't represent a real threat, then I don't know what is

Edited by galgitron

Share this post


Link to post
Share on other sites
18 minutes ago, nikb said:

If you assumed you had a billion computers each running a trillion checks per second and you could eliminate 90% of the keyspace right off the bat, it would still take you over a billion years to go through the remaining 10%.

Ok, based on this, I feel pretty comfortable marking this issue off of my "Things I Need To Worry About" list.  :mail1:

Share this post


Link to post
Share on other sites
43 minutes ago, galgitron said:

To the point, how do you account for the purported collisions discovered by this project?  Is it apples to apples?  Fraud?  Nonsense?

https://lbc.cryptoguru.org/trophies

Look at the most recent one.  Over $7000 worth of bitcoins cracked open.  If this doesn't represent a real threat, then I don't know what is

It depends on how these private keys were generated (e.g. did someone use brainwallet or a faulty random number generator?). It could also be a consequence of how the ephemeral ECDSA keys are generated (improper generation of emphemeral keys can disclose your private key). Basically, it boils down to how well written was your software and its implementation details. This is not necessarily something that would be an inherent weakness of ECDSA.

 

 

 

Share this post


Link to post
Share on other sites
33 minutes ago, T8493 said:

It depends on how these private keys were generated (e.g. did someone use brainwallet or a faulty random number generator?). It could also be a consequence of how the ephemeral ECDSA keys are generated (improper generation of emphemeral keys can disclose your private key). Basically, it boils down to how well written was your software and its implementation details. This is not necessarily something that would be an inherent weakness of ECDSA.

You are assuming they are looking for the original key; they are not, or you're suggesting that their private key is somehow tainted (stretches of zeroes?); it's not.  They are finding other keys in the 0 to 2^159 range, so it's irrelevant how they originally hashed it, which suggests it is an inherent weakness of the paradigm.  Their process is the following:

"Given a bitcoin address 'adr1' from a random(unknown) private key of numeric value between 2^160 and 2^256: find another private key in the interval between 0 and 2^159 which will evaluate to the same bitcoin address."

Presumably the bitwidth was chosen for performance reasons

Edited by galgitron

Share this post


Link to post
Share on other sites
30 minutes ago, galgitron said:

You are assuming they are looking for the original key; they are not, or you're suggesting that their private key is somehow tainted (stretches of zeroes?); it's not.  

Not exactly. I was saying that there are much easier ways to calculate your private keys (e.g., in case of a faulty software) than to brute force keyspace for collisions. Maybe these private keys were found using some other method.

 

Share this post


Link to post
Share on other sites
Just now, T8493 said:

Not exactly. I was saying that there are much easier ways to calculate your private keys than to brute force keyspace for collisions. Maybe these keys were found some using other method.

And that is the exact question I'm searching for an answer for.  You're effectively saying that they are not using the methods they claim to be using.  And not trying to speak for him, but mathematically speaking, I believe @nikb's only position could also be that they came about their successful collisions by fraudulently claiming to do so because it's simply impossible in his mind.  Therefore, both of you are accusing this site of deception.  This seems highly unlikely to me given the number of participants, but not impossible.  However, if they are indeed using the methods claimed, they are uncovering a huge problem.

Myself, I am exploring the notion that SHA-256 isn't as well-distributed as we'd like to believe, which would account for these theoretically impossible collisions.  If this distribution is indeed biased, then current blockchain security is considerably exposed to compromise.  It strikes me as profoundly important to verify the credibility of these collisions, because if we continue to bury our heads in the sand in denial or lack of understanding, quantum computing is going to smash through our comfortable walled garden and rudely awaken us from our complacency.

Share this post


Link to post
Share on other sites
1 hour ago, galgitron said:

And that is the exact question I'm searching for an answer for.  You're effectively saying that they are not using the methods they claim to be using.  And not trying to speak for him, but mathematically speaking, I believe @nikb's only position could also be that they came about their successful collisions by fraudulently claiming to do so because it's simply impossible in his mind.  Therefore, both of you are accusing this site of deception.  This seems highly unlikely to me given the number of participants, but not impossible.  However, if they are indeed using the methods claimed, they are uncovering a huge problem.

 

Quote

Myself, I am exploring the notion that SHA-256 isn't as well-distributed as we'd like to believe, which would account for these theoretically impossible collisions.  If this distribution is indeed biased, then current blockchain security is considerably exposed to compromise.  It strikes me as profoundly important to verify the credibility of these collisions, because if we continue to bury our heads in the sand in denial or lack of understanding, quantum computing is going to smash through our comfortable walled garden and rudely awaken us from our complacency.

Authors don't claim there is any weakness in the SHA-256 (or RIPEMD-160) algorithm. Authors also claim that they need to examine around 2^137 private keys before they find a collision. No one in the world is capable of doing so much work.

Just try to recalculate how many days one would need to find to find 1 collision using the 25 MKeys/sec pool capacity that the authors give as an example. 
 

Share this post


Link to post
Share on other sites

I'm confused....  (I often am)...   :) 

On the one hand folk are saying that they are already finding keys...  maybe fifty found so far  (looked this morn but cant remember exact numbers)?

On the other hand T8493 and Nik (both of whom I respect immensely) are saying its too much work to ever get a hit....  

So are you guys talking about different things?  Is the XRP key harder to find than the Bitcoin one?  Because they do seem to be finding Bitcoin ones....

Share this post


Link to post
Share on other sites

I’m saying one thing: if brute force is the best available option (and I think it is), then iterating over the entire 2^n keyspace for values of n greater than 128 are practically impossible, and attacks against n greater than or equal to 256 are not possible in this universe. See my earlier post here.

I don’t think there’s a fundamental weakness in SHA-256, nor do I think that this project suggests any kind of brokenness, and feel quite safe about my private keys, both Bitcoin and Ripple.

I’d need to understand what exactly they’re doing more in depth before I can comment further.

Share this post


Link to post
Share on other sites
Quote
Quote

 

Posted June 10

  On 6/10/2017 at 12:27 AM, Fanust said:

3. Then when you've found a number of addresses with nice balances, couldn't you then run a program to brute force hack the secret key?

 

 

If it's a 256 encryption, you'll need a supercomputer(maybe golem) and wait for atleast 30-40 years

Uhm... 30-40 years? At a trillion keys per second, running continuously for 40 years you'd go through 1.261×10^21 keys. Sure sounds impressive, doesn't it? It is, but even so, that's only 0.000000000000000000000000000000000000000000000000000001% of the total number of available keys. Think about that...


 

Here's what Bruce Schneier had to say about brute-forcing 256-bit symmetric keys in the seminal tome Applied Cryptography:

  Quote

Quote

 

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38×10^-16 erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume 4.4×10^-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21×10^41 ergs. This is enough to power about 2.7×10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

But that's just one star, and a measly one at that. A typical supernova releases something like 10^51 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

 

The physics (including the hilarious neutrino joke) aside, the bold and underlined bit really says it all: brute forcing of 256-bit symmetric keys ain't happening.

Of course, we're talking about public/private key pairs, not symmetric keys so things are a little different. But if the suggestion is to _iterate_ all the keyspace (that is, looking at all possible private keys), checking everyone to see if it corresponds to a wallet, the above analysis applies and holds.

 

Apologies if formatting is unclear, but here is what nikb refers to.  -amazing, really.  I had no idea. but then there is a reason no one has put me in charge of crypto stuff.  

Share this post


Link to post
Share on other sites
7 hours ago, galgitron said:

Before you throw 29 digit numbers around, you need to reconcile how these collisions happened, or provably refute them, or blindly accept them.  Denying them is just religion.

Easy: Do you see the "This is #__ of the puzzle transaction." part of the "trophies" section? That's because these are known weak(er) keys that will be revealed over time. (https://bitcointalk.org/index.php?topic=1306983.0)

7 hours ago, galgitron said:

It may be a mathematical curiosity at this time, but quantum computing will chew through big spaces like a T-Rex after a hunger strike.

No. https://www.smbc-comics.com/comic/the-talk-3

Edit: Also T-Rexes are extinct.

Edited by Sukrim

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...