Jump to content
pvap

Is Ripple vulnerable to a "collision" attack?

Recommended Posts

At this point, I don't believe I'll ever get fully satisfactory information to finalize a perception upon what we are witnessing at the LBC.  A few rounds at Bitcointalk led me to these possibilities:

1) the collisions are outright fraudulent
2) they're a product of low entropy key generators (disprovable/provable by moving the LBC test range higher)
3) hashing algorithms are not as well-distributing as we believe them to be, causing multiplicity in working keys per address

Until more details surface, we're probably stuck with a question mark for now.

Share this post


Link to post
Share on other sites

1 and 2 are non-issues for people who know what they're doing. The only thing which, if true, would shake the foundations of these systems is 3. And there's a very, very good reason to think it's not three -- despite the fact that finding such a collision would bring instant fame, nobody has yet produced such a collision. There is no known account for which there are two private keys. Until such time as someone presents such a collision or any good reason to think that they're more likely than we expect, there's absolutely no rational reason to worry about this particular attack. We have a safety factor of several orders of magnitude and we are only relying on a well-documented property of the hashing algorithm.

Share this post


Link to post
Share on other sites

This has been discussed here: 

Looks like the Large Bitcoin Collider was found to install malicious code and therefore it is somewhat likely this is a hoax (I only say somewhat likely because I haven't examined the claims on the reddit post in any detail).

 

Edited by deadestfish

Share this post


Link to post
Share on other sites
12 hours ago, nikb said:

I’m sorry, but enumerating through all possible 2^160 keys isn’t possible until, to use Schneier’s words, computers are made from something other than matter and occupy something other than space.

I plugged the following statement into the always useful Wolfram|Alpha:

I’m basically asking: “if I have a billion computers, each capable of trying one trillion public keys per second, how long will it take to go through 2^159 keys.”

The answer is: 1,700,000,000 times the age of the Universe.

Let me repeat that, to make sure it sinks in: a computer running at 1 Zettahertz and doing nothing more than COUNTING from 0 to 2^159 will take over a billion times longer than the age of the Universe.

I stand by my previous statements.

So you're saying there's a chance?  :P 

@nikb seriously though, thanks for putting it in terms even us plebs can understand! 

Share this post


Link to post
Share on other sites
8 hours ago, JoelKatz said:

There is no known account for which there are two private keys.

That would be the clincher for sure.  It would seem the only way to verify the distribution of hashing algorithms would be a brute force attack on known addresses by using a range of keys where entropy is assured (using full bitwidth keys), which, if hashing algorithms are indeed well-distributed, should never produce a collision.  Sadly, the LBC appears only to be in search of low-hanging fruit, with some apparent success that distorts the perception of the security of the hash algorithm.  I am concerned however about the potential for quantum computing to magnify any real flaws hidden in there.

I'm hesitant to write off their collision examples as low-entropy original keys, but that seems less painful than accepting a flaw in the Rube Goldberg gears and pistons in SHA-256.  I want to believe!

Share this post


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

I am concerned however about the potential for quantum computing to magnify any real flaws hidden in there.

Why? How would a quantum computer attack a Merkle–Damgård construction?

Share this post


Link to post
Share on other sites

It's clear like a sunny day that math behind crypto is rock solid, @nikb has provided a couple of good examples.

What is unclear is the safety of "window.crypto" libraries in our web browsers and we know that Ripple JavaScript leverages those heavily. If entropy generators are not good enough, I could also imagine situations when you get a seed from clipboard content, or last Rand generated, etc etc (see the recent findings that @Professor Hantzen refers to on the previous page).

I suggest we do some detective work also in "window.crypto" direction.

Share this post


Link to post
Share on other sites
2 hours ago, Sukrim said:

Why? How would a quantum computer attack a Merkle–Damgård construction?

It would come from this:

https://www.iotatoken.com/IOTA_Whitepaper.pdf

"Resistance to quantum computations It is known that a sufficiently large quantum computer could be very efficient for handling problems that rely on trial and error to find a solution. The process of finding a nonce in order to generate a Bitcoin block is a good example of such a problem. As of today, one must check an average of 268 nonces to find a suitable hash that allows a new block to be generated. It is known (see e.g. [15]) that a quantum computer would need Θ(√ N) operations to solve a problem that is analogous to the Bitcoin puzzle stated above. This same problem would need Θ(N) operations on a classical computer. Therefore, a quantum computer would be around √ 2 68 = 234 ≈ 17 billion times more efficient at mining the Bitcoin blockchain than a classical computer. "

Admittedly this would be brute force, but if common hashing algorithms are in any way biased such that they produce uneven distribution, then the odds of finding a doppleganger key to an address of interest can go up radically

38 minutes ago, Duke67 said:

It's clear like a sunny day that math behind crypto is rock solid

No, it's not been proven that hashing has level distribution for the results, and this is 'key' to supporting @nikbs math.

https://en.wikipedia.org/wiki/Security_of_cryptographic_hash_functions#Provably_secure_hash_functions

"Most hash functions are built on an ad hoc basis, where the bits of the message are nicely mixed to produce the hash. Various bitwise operations (e.g. rotations), modular additions and compression functions are used in iterative mode to ensure high complexity and pseudo-randomness of the output. In this way, the security is very hard to prove and the proof is usually not done. Only a few years ago, one of the most popular hash functions, SHA-1, was shown to be less secure than its length suggested: collisions could be found in only 251[1] tests, rather than the brute-force number of 280.  In other words, most of the hash functions in use nowadays are not provably collision-resistant. These hashes are not based on purely mathematical functions. This approach results generally in more effective hashing functions, but with the risk that a weakness of such a function will be eventually used to find collisions. The famous case is MD5."

Edited by galgitron

Share this post


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

No, it's not been proven that hashing has level distribution for the results, and this is 'key' to supporting @nikbs math.

I agree that hashing methods might have some weak points that remain unknown to us for now.

My point was that the level of threat from "Window.Crypto" is ***MUCH*** larger than from hashing itself.

Share this post


Link to post
Share on other sites

I'm outta here, believe what you want about quantum computers or what some paper from 1997 might have to state about an algorithm invented in 2005 applied in a certain way in 2009 cited in a nonscientific "whitepaper" thar tries to argue why it is better than a competitor.

The answer to the original question is still:

Ripple is about as vulnerable as Bitcoin to such an "attack", but the "attack" is not feasible as well as not giving any advantages over brute force at the current understanding of the algorithms involved. It is a (very very very ...) long shot at an experiment to find a direct counter example instead of doing the math involved. The results so far don't indicate any success.

Edited by Sukrim

Share this post


Link to post
Share on other sites
6 minutes ago, Duke67 said:

My point was that the level of threat from "Window.Crypto" is ***MUCH*** larger than from hashing itself.

Agreed, holes abound from all angles. 

My concern is the religious tenacity with which people defend math they don't fully understand..nay, 'nobody' fully understands, just a lot of PhD finger-crossing that their sleight of hand shuffling trick worked.  quantum computing opens a whole new plateau of exposure to unjumbling modulo'd bits and other such hanky panky so it does give me pause.  And for something as hot of a target as money, you have to believe that blockchains will be first in line for attacks.

Share this post


Link to post
Share on other sites

There is clearly a very large (and growing) bounty available for anyone that can reliably generate collisions.  

The fact that apart from the claims of this uncertain reliability site,  there are no reports of people getting rich stealing coins out from under other people... suggests that it is not done in the real world. 

I trust David and Nik.  If there is a problem in the future I would bet that they are on it before we ever knew it was coming.  

Im not loosing any sleep over this...

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...