Jump to content
pvap

Is Ripple vulnerable to a "collision" attack?

Recommended Posts

42 minutes ago, Sukrim said:

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)

Some of the trophies are unrelated to the "puzzle transaction".

They were reported in the following dates:

- 2017-03-30 01:18:00 UTC

- 2017-01-16 05:20:19 GMT

- 2016-10-11 03:00:34 GMT

 

Of course, these could've been created by the project founder himself, to raise suspicion.

But there's no concrete evidence of this. Still, I think it's an interesting subject to follow.

Share this post


Link to post
Share on other sites
adr1 = ripemd160(sha256(pubkey(rand(2^256-2^160)+2^160)))
for (a = 0 to 2^160) {
  adr2 = ripemd160(sha256(pubkey(a)))
  if (adr1 == adr2) {
    print "We got ourselves a collision!\n";
  }
}

Meaning "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."  (Source)

@nikb This is what the LBC project is doing. Is there an applicable case for Ripple?

Obviously low-order seeds will be found first, and there may be many owing to people messing about with address generation (or making puzzles that intentionally exist in the lower-bit realm).  But in principle, it does look like a potentially exploitable vulnerability in Bitcoin addressing.  Is Ripple also vulnerable in this way?  I seem to recall @JoelKatz saying somewhere that Ripple public addresses have more than one corresponding seed (or was it the other way around?), but I confess I didn't understand it even though I am somewhat familiar with the process.

Share this post


Link to post
Share on other sites
24 minutes ago, Professor Hantzen said:

But in principle, it does look like a potentially exploitable vulnerability in Bitcoin addressing.

Well, they are bruteforcing....I don't see anything special. And it won't work for properly generated address/secret. Well it can work, but as always the probability is super low.

Share this post


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

Well, they are bruteforcing....I don't see anything special. And it won't work for properly generated address/secret. Well it can work, but as always the probability is super low.

As I understand it, they've increased the probability by both halving the search space and doubling the chances of finding a collision.  (Edit: "half" and "double" are wildly inaccurate, but in principle I mean...)

Edited by Professor Hantzen

Share this post


Link to post
Share on other sites
1 minute ago, Professor Hantzen said:

As I understand it, they've increased the probability by both halving the search space and doubling the chances of finding a collision.

No, that's just the birthday paradox in action.

The user behind this has been trolling the German BTCtalk community for a while, then emigrated to the english speaking forum part and then still decided to put up a service supporting his poor understanding of cryptography and mathematics.

If anyone wants to actually crack private keys, create a service like directory.io, log user interactions and check all displayed keys for funds. There are enough stupid people out there that would try to see if their seed is part of that website that it could be profitable.

Share this post


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

adr1 = ripemd160(sha256(pubkey(rand(2^256-2^160)+2^160)))
for (a = 0 to 2^160) {
  adr2 = ripemd160(sha256(pubkey(a)))
  if (adr1 == adr2) {
    print "We got ourselves a collision!\n";
  }
}

Meaning "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."  (Source)

@nikb This is what the LBC project is doing. Is there an applicable case for Ripple?

Obviously low-order seeds will be found first, and there may be many owing to people messing about with address generation (or making puzzles that intentionally exist in the lower-bit realm).  But in principle, it does look like a potentially exploitable vulnerability in Bitcoin addressing.  Is Ripple also vulnerable in this way?  I seem to recall @JoelKatz saying somewhere that Ripple public addresses have more than one corresponding seed (or was it the other way around?), but I confess I didn't understand it even though I am somewhat familiar with the process.

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:

Quote

((2^159 seconds) / (1 billion * 1 trillion)) into centuries

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.

Share this post


Link to post
Share on other sites

Lots to chew on here

4 hours ago, Sukrim said:

I'll up your comic book reference to something more prescient.  @nikb, I'd also like your comment on Iota's approach to securing against quantum computing attacks

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. Also, it is worth noting that if a blockchain does not increase its difficulty in response to increased hashing power, there would be an increased rate of orphaned blocks. For the same reason, a “large weight” attack would also be much more efficient on a quantum computer. However, capping the weight from above, as suggested in Section 4, would effectively prevent a quantum computer attack as well. This is evident in iota because the number of nonces that one needs to check in order to find a suitable hash for issuing a transaction is not unreasonably large. On average, it is around 38 . The gain of efficiency for an “ideal” quantum computer would therefore be of order 34 = 81, which is already quite acceptable. More importantly, the algorithm used in the iota implementation is structured such that the time to find a nonce is still a hypothetical construct as of today. Note that Θ(√ N) could easily mean 10√ N. 26 not much larger than the time needed for other tasks that are necessary to issue a transaction. The latter part is much more resistant against quantum computing, and therefore gives the tangle much more protection against an adversary with a quantum computer when compared to the (Bitcoin) blockchain."

Quote

Edit: Also T-Rexes are extinct.

Tell my pet Bamm Bamm that..

8 hours ago, T8493 said:

 

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. 
 

I know that.  I don't even think they know what they've discovered.  I'm not buying into the notion they have enough computing power to burn through a meaningful number of keys, I'm suggesting they are serendipitously discovering an uneven distribution of hashes.  I remember hearing about this project near its inception.  I must admit, I smirked, thinking, what a waste of time that is.  Blind faith in the math I had.  Well, one collision might be written off as a galactic-sized anomaly.  But consistent collisions???...can't be ignored.

There is a lot of confusion in this thread so far, so let me attempt to clear it up a bit.  Nik's position is that it would take till the end of the universe to exhaustively iterate through every possible 128-bit key.  I couldn't agree more.  This gives him, and many others, a sense of security.  These recent collisions from this experiment suggest something not anticipated, and impossible to calculate: that more than one key works for a given hash.  In other words, your Bitcoins are locked behind a hash from a private key you own, but what if there were other keys that also generate that same hash?  What if there were BILLIONS of keys that generate that same hash?  So hopefully you can see that it becomes moot how many umpteen keys there are, if so many keys will produce the same hash.  I eagerly await Nik's analysis because if these collisions are genuine, then I need to see how it's possible to reconcile these facts against his earlier postings.  

@T8493 You are also avoiding the 1000 lb gorilla sitting on your desk.  How are these collisions possible?  Telling the gorilla he doesn't exist will just make him giggle.

Share this post


Link to post
Share on other sites

@tulo @nikb@Professor Hantzen

ok, sorry, missed those recent posts.  There is a very poor comprehension in this thread about what they are doing, hopefully I can explain:

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

This does not mean they are splitting the address space in half.  The absolute supermajority belongs to the 2^160 and 2^256 range, virtually all of it.  Think about it in terms of binary, the higher the bit, the greater the value.  Saying they are splitting it in half is like saying 0 - 99 is half of the values between 0 and 9999.

Further dissecting it, they theorize that within the entire range of the supermajority 2^160 to 2^256, exist keys that produce hashes, for which there are ALSO keys in the superminority range 0 to 2^159 that PRODUCE THE SAME HASH.  They also probably designated the superminority realm based on bitwidth most compatible with processing efficiency.

There is no fudging of the numbers, so shortcut, no diluted or WEAKER  keys, nothing different whatsoever, by their approach of solely searching the superminority.  All keys in the superminority are as equally valid, secure, and relatively statistically probable as supermajority keys.  So, in real world speak, this means that your bitcoin private key statistically most likely lives in the supermajority, but these guys are theorizing that maybe a doppleganger key that can ALSO unlock your Bitcoin address, exists in the superminority realm as well.  

Yes, the superminority realm is HUUUUUUUGGEEE.  It would take billions of computers, FOREVER, to search even that thin slice, but again, they are not looking for one specific key.  It appears that even within the superminority, multiple copies of working keys HASH to the same value.  That means even within the superminority, there are many doppleganger keys that can open your bitcoin address.  This is their serendipitous discovery.  The fact that they've already found copius doppleganger keys, suggests that this dopplegangerism is a massive problem, and the math that we count on to hide our bitcoins behind, is possibly flawed in its ability to sufficiently distribute hashes.

In summary, nobody denies that it would take FOREVER to iterate through all the keys.  But if there are orders of magnitude more WORKING keys than we expect, then we don't need to dig too far to come up with a collision.

@nikb I know you want to shake your hands of this conversation and write it off as nonsense, but these are very important salient facts that need to be addressed, and you haven't directly dealt with the fact that they have produced collisions.  This cannot be ignored or dismissed with faith in statistics.  We need to understand how these collisions came about.  I'd also really love for @JoelKatz to weigh in if you wouldn't mind tapping him on the shoulder

Edited by galgitron

Share this post


Link to post
Share on other sites
19 hours ago, zenkert said:

That question B A A A M just landed on @JoelKatz desktop. @Hodor may also be the one to dig into this.

I defer completely to the others that already answered in this thread. 

However... I remember reading about rainbow tables a couple years ago - I was kind of shocked that some people generate their private keys with nonrandom seeds.  I don't have a link to that article, but it was pretty scary and taught me to only trust proven high-entropy systems for private key generation. 

Otherwise you're risking heartbreak next time you log into your wallet! 

Share this post


Link to post
Share on other sites

@Sukrim & @nikb: As @galgitron has explained, nobody here is disputing how uselessly long it would take to iterate through the entire address space.  i have often-times myself given other people similar examples as Nik as to why this is impossible when explaining bitcoin/ripple and public/private key cryptography to them.

Instead, the issue here could be summarised as follows: 

What guarantee can anyone give that the amount and distribution of multiple seeds to public addresses are not both higher than previously expected?

Is not the value of the LBC that it works to either support (well, given a few billion years) or refute (tomorrow) that expectation?  In that sense, I'd be all for it.  That it may have already found a small number of funded private keys outside this expectation suggests there could be a problem with the expectation.  What I want to see are the seed values of both sides of any collision.  And if the LBC cannot furnish both seeds - its clearly just ********.  So far, they've claimed to have found three, and returned the funds to their rightful owners who presumably furnished the other working private key to prove ownership.  Why they haven't published both private keys side by side and broken the internet and slashed BTC's marketcap by 99% I've no idea (other than that perhaps they didn't want to do those things - but it still all makes little sense).

Anyway, given the lack of both seeds to a collision being published I'm going with @Sukrim that this is a troll.  However, I still believe its a useful and interesting project...

Share this post


Link to post
Share on other sites
5 minutes ago, Professor Hantzen said:

Anyway, given the lack of both seeds to a collision being published I'm going with @Sukrim that this is a troll.  However, I still believe its a useful and interesting project...

'troll' may be a bit harsh because it implies intent.  I don't think anybody's agenda is to induce FUD or defamation.  Still, you're absolutely right that both seeds being published would shake crypto to its knees.  I'm going to reach out to the LBC and see what I can do

Share this post


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

'troll' may be a bit harsh because it implies intent.  I don't think anybody's agenda is to induce FUD or defamation.  Still, you're absolutely right that both seeds being published would shake crypto to its knees.  I'm going to reach out to the LBC and see what I can do

Excellent - good luck!  (And I tended toward the label because of what I read from the person on the btctalk forums.)

Share this post


Link to post
Share on other sites

Alright, that's settled then.  For now... ;)

For those who want to save a click:  no collisions have been found, all 54 found keys are low-order, which meets expectation and isn't anything to be alarmed about (people often mess about with low-order seeds and make insecure wallets out of them, sometimes on purpose for others to find, other times, well...).

Also, for those interested in this kind of thing, this happened recently.  It was the discovery of used bitcoin public addresses being recycled as private keys for new addresses (some of which held active balances at the time this was posted).  Could have resulted from bad or malicious code.  One notable address containing 9 BTC was apparently a virgin one issued by blockstream, hence controversy.  Relation to Ripple?  Hopefully given Ripple's lack of requirement for dealing with unspent outputs ("change") on transactions, such a thing would be unlikely on the XRP Ledger.  One would hope.  (I guess finding out could be interesting homework for someone.)

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