Topic: A basic question - page 3. (Read 5598 times)

You're basically saying cryptographers aren't terrible concerned about security.  Doesn't that sound a little silly?

Also, putting backdoors into hash functions isn't like putting backdoors into operating systems or something like that.
I'm not an expert but I don't think its very doable as MD construction has been around a while.
Of more concern to Bitcoin would be how the ECC is implemented.

2004, but my point has to do with the culture of both cryptography and intelligence.

The "weakness" was that the NSA had not broken it yet".

Most cryptographers are academics. They play the common academic game of justifying their actions. My guess is that a lot of academic cryptographers feel that 'state of the art' should be half a step, not a full step, ahead of 'old'. In other words they have the Marie Antoinetteish posture that "we are doing something good, promoting some higher value others don't see, and so we have certain responsibilities and privileges to enforce". i.e. "We will use cryptography to develop math across borders" etc. i. e. "rather than to do the honest work of providing secure cryptography that can be protected from attacks by anyone, including us".

Specifically I am referring to Snowden type leaks that show deliberate weaknesses built into U.S. cryptography, as well as research showing such deliberate shoddiness, such as the cryptobang article mentioned earlier. If you are not able to find the article, or a copy, I will provide links.

Coin security may be fun and games for some people but I stand to lose quite a high percentage of the little I have if it turns out that governments are going to enforce their academic values on the altcoin economy.

I don't think anyone knows what the weakness is but that was 1995 and there's been other collision attacks published since with SHA 1. 

what is your point?

Okay. But here is from a 2004 article. 2004
https://www.schneier.com/essays/archives/2004/08/cryptanalysis_of_md5.html

"This year, Eli Biham and Rafi Chen, and separately Antoine Joux, announced some pretty impressive cryptographic results against MD5 and SHA. Collisions have been demonstrated in SHA. And there are rumors, unconfirmed at this writing, of results against SHA-1."

"In 1990, Ron Rivest invented the hash function MD4. In 1992, he improved on MD4 and developed another hash function: MD5. In 1993, the National Security Agency published a hash function very similar to MD5, called the Secure Hash Algorithm (SHA). Then in 1995, citing a newly discovered weakness that it refused to elaborate on, the NSA made a change to SHA. The new algorithm was called SHA-1. Today, the most popular hash function is SHA-1, with MD5 still being used in older applications."

Bold added by me.

At this point anyone who does not know what the weakness was is not paying attention.

This is not what collision resistance implies. It would be true if it lacked pre-image resistance. Collision resistance means that you can find two messages that hash to the same value but you don't get to choose the hash value.

In the case of the MD5 certificate attack, they made two certificates that have the same hash: one is regular (SSL), the other is supreme (CA: Certificate Authority). They asked the root CA to sign the SSL one without problem. And then they put the signature in the CA certificate. Because they have the same MD5, the signature is valid for both of them.
They made a CA that appears to be trusted by the root CA. Their CA can issue SSL certificates that will be accepted by the rules of trust delegation.

So you see that this isn't applicable to bitcoin.

The malware that exposed md5 as weak was found by Iranians. It was evidently political malware that was created by several 'anti Iranian' governments.

Wikipedia has a timeline but if you look at actual forum posts on various sites it is clear that Wikipedia is presenting a distorted picture. Forum posts suggest md5 was actually considered quite secure until the Iranian issue.

The fact that private organizations uncovered it makes sense if governments were trying to keep the weakness secret.

Evidently a wide mix of governments were aware of flaws in md5 and used that knowledge for political games.

When Iranian researchers found the malware they gave it to Kaspersky to analyze and look for historical evidence and patterns. Kaspersky seems to have been a bit disingenuous, perhaps the Russian government was benefiting from the crack as well. At any rate, any Iranian can look at the evidence and decide how helpful the Russians actually were.

The bigger question is whether these putrid alphabet soup agencies engaged in a massive deception for years with md5, but then decided 'well let's start playing square now'?

Can we trust them now?

Among the several different md5 cracks is at least one that was used to forge a Microsoft certificate.

But you are saying that if md5 were used for bitcoin, it would be secure?

From Wikipedia
"In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage.

In the context of attack, there are two types of preimage resistance:

    preimage resistance: for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., it is difficult to find any preimage x given a "y" such that h(x) = y. [1]
    second-preimage resistance: it is computationally infeasible to find any second input which has the same output as a specified input, i.e., given x, it is difficult to find a second preimage x' ≠ x such that h(x) = h(x′).[1]

These can be compared with a collision resistance, in which it is computationally infeasible to find any two distinct inputs x, x′ which hash to the same output, i.e., such that h(x) = h(x′).[1]

Collision resistance implies second-preimage resistance,[1] but does not guarantee preimage resistance.[1]"

---

It seems from the descriptions of the various md5 cracks that md5 lacks collision resistance, therefore you could find a second, or fabricated, input which would hash to a legitimate looking output
and
it lacks second preimage resistance which seems to equate to finding a second private key.

Considering the amount of bullshit that has been shoveled already in defense of md5 and sha2 my opinion remains that most likely they are cracked several ways by several governments and those overpaid slippery cunts are trying to drag the game out as long as they can.

The Bitstamp hack may be their undoing though. If that hack was actually a sha2 crack then you would think they would take pains to leave a fake forensic trail. More info will be coming out on that I imagine.

If MD5 were used for bitcoin it would not be possible to steal coins, or at least not directly.  That would require preimages.

What would be possible would be constructing txOuts that could be spent by any of several different keys.  Which could be interesting, but doesn't lead to any immediate capability of theft.

It could be used in some kind of scam or confidence game though; two different keys capable of spending the same BTC25 could coexist in a wallet and most software would think the wallet had BTC50 in it, for example because neither key would appear to be a multisig or shared key. 

"A 2013 attack by Xie Tao, Fanbao Liu, and Dengguo Feng breaks MD5 collision resistance in 218 time. This attack runs in less than a second on a regular computer."

http://en.m.wikipedia.org/wiki/MD5

There seem to be quite a few different md5 cracks which were found independently.

It appears that the government and Microsoft both encouraged the use of md5 until it was exposed publicly by Iranian computer researchers.

If md5 were used for bitcoin it would be possible for anyone to steal bitcoin.

If sha2 is compromised as md5 was, and if the government is covering that up in order to exploit it, as they did with md5, what are the implications?

It is safe to say other governments also have cryptography programs.

Interesting. I was under the impression that MD5 was vulnerable against preimage attacks.

well there's 2^256 private keys and 2^160 addresses so yeah there's many private keys for each address,
but that's not really what's being discussed.

Cryddit's post is enlightening, in revealing that even MD5 is subject to collisions but
not pre-image attacks.

I'm not sure exactly why collisions are that important if they would happen rarely,
or how you would use that to attack a target.

Phew... people should keep in mind that there effectively is an infinite amount of private keys, so every public key (and thus also address) has an infinite number of private keys that can access that address! Scary, isn't it? If you look at the math, it isn't anymore!

For what it's worth, the MD5 break is of a very particular kind.

MD5 has a collision vulnerability, but it does not have a meaningful preimage vulnerability.

What that means is that it is now easy to construct two  or more documents that have the same MD5 hash (a collision), but given a hash value it is still damned hard to construct something which hashes to that value (a preimage). 

It's preimage resistance isn't quite perfect mind you; an attack has been found that takes 2^123.5 operations to find a preimage, when it ought to take 2¹²⁸ if its preimage resistance were as good as it was supposed to be.  So MD5, while completely broken in terms of collision reistance, is only about 1/24 as hard to find a preimage as it ought to be. In practice finding a preimage is still far beyond the amount of computing power that could be produced by a computer the mass of Earth in a time less than the expected lifetime of the sun. 

Of course, attacks never get worse ... and it's possible that the preimage attack can be extended somehow. 

I don't know.  Do you have a reference for that?

Even if they were, it was private organizations that exposed the weaknesses so wouldn't that be a moot point anyway?

Is it accurate that various government agencies were aware of flaws in md5 and yet continued to promote it as secure?

They are different in that no single address appears in both sets, but there is no discernible difference in the statistical distribution of any bit or any pattern of bits.  There is literally no way, given an address, to guess which of these set it's in.  Except, you know, by iterating through all the possible private keys and seeing if it matches. 

No.  It isn't.  There is no way that is "much easier:"  In fact it's every bit as hard as reversing the hash operation in the first place.

That's actually an excellent question and I don't know,
because both do use the Merkle-Damgard construction.
 
Best left to ask a cryptographer.
 
I think there's certainly room to be a skeptic here, given the similarities, but
the fact remains that no one has publicly produced any evidence of significant
weakness so far in SHA-2.

A good idea.

Thank you.

No, you are simply at the wrong place. Why don't you ask on a cryptography forum instead?