Title: Collision in Hash Function. Everyone Should Know this Post by: Wenbing on April 17, 2020, 06:09:33 AM While taking a course on cryptography and block chain, I came across the concept of Hash function in cryptography.
Here is a quote: Quote " start by mentioning what a hash function is. A hash function is one that receives information of any length as input and outputs a fixed-length alphanumeric string, regardless of the size of the input message, the results it is called the hash of the initial string. A particularity of this hash function is that if for some reason the input message has any variation, however minimal it may be, the alphanumeric string would change radically, it remains the same size but its content will be totally different. There are several hash functions out there; some are in disuse due to real or theoretical demonstrations of weakness, particularly, for finding what is called collisions: this is, find two different inputs that produce the same hash output." I'm particular about the collisions concept of the hash function. 1.What's the effect of detecting collisions on the hash outputs? 2.Is collision an advantageous cryptographic occurrence or not.? 3.Are there cryptographic measures in place in order not to experience collisions in hash outputs? Title: Re: Collision in Hash Function. Everyone Should Know this Post by: nc50lc on April 17, 2020, 08:38:13 AM There's nothing "harsh" about that quote, it's actually mild and comforting :)
FTR, There is currently no recorded collisions for both SHA-256 and RIPEMD-160, Bitcoin is using the two famously for computing "pubkey hash". 1.What's the effect of detecting collisions on the harsh outputs? For the particular hash function, projects that are using it like Bitcoin would start looking for safer alternatives.Like if SHA256 proved to become unsecured after discovering multiple collisions or successful collision attacks, developers might consider using SHA512 instead. <addition, because my answer didn't really answered the question: For Bitcoin address collisions (because it was created through hashing), the two persons who own the private keys that derived the same address can spend each other's funds> Quote from: Wenbing 2.Is collision an advantageous cryptographic occurrence or not.? No.Quote from: Wenbing 3.Are there cryptographic measures in place in order not to experience collisions in harsh outputs? For "pubkey hash", Bitcoin has been using two entirely different hash functions. So if one got compromised, there's another one to break.For some "Redeem script" and "P2SH addresses", the same as above. For Mining, Bitcoin uses SHA-256d (d=double) for a reason: (wiki: SHA-256d (https://en.bitcoinwiki.org/wiki/SHA-256d)) While taking a course on cryptography and block chain, Are those questions part of your exam?Title: Re: Collision in Hash Function. Everyone Should Know this Post by: pooya87 on April 17, 2020, 09:03:29 AM collision in a hash function is a characteristic of it not a problem because it follows the pigeonhole principle (https://en.wikipedia.org/wiki/Pigeonhole_principle). we can have unlimited inputs with any length and all turn into the same size output, it is like having 10 pigeons and wanting to put them in 8 holes, at some point you will end up with one that contains more than one pigeon.
depending on the size of the output the chances of it happening can be very little to the point that it can be considered impossible or be very likely that occur regularly. we have two hash function types, the non-cryptographic and cryptographic hash function. the former is usually used for hash-based lookups like hash tables,... one example is MurmurHash. collision is a common thing in this group and we don't care about it. the later is used for cryptography when security is needed. the output lengths are larger than 160-bit. the one bitcoin uses is SHA256. collision in this group can be considered impossible due to the huge result size that the data is being mapped to. keep in mind that there is a difference between collision attack and a preimage attack. preimage attack is what could be worried in bitcoin not collision. there are also a couple of outputs that are published as a reward and referred to as "collision" are actually ensuring the preimage resistance of the hash algorithms used. preimage resistance refers to two things: a) preimage resistance: having h and finding x that hash(x) = h b) second-preimage resistance: finding x1 and x2 where hash(x1) = hash(x2) to claim any of those puzzle outputs you have to perform a preimage attack of second type. this has already happened for SHA-1 and the reward was claimed back in 2015. Title: Re: Collision in Hash Function. Everyone Should Know this Post by: odolvlobo on April 17, 2020, 09:09:12 AM One of the primary uses of a hash is to validate the authenticity of a digital item. If the hash for an item is known, then any change to the item is easily detected because the hash of the modified item will not be the same as the known hash.
However, the ability to find a collision gives an attacker the ability to make changes to the item in such a way that the hash does not change. Read this article: https://www.zdnet.com/article/sha-1-collision-attacks-are-now-actually-practical-and-a-looming-danger/ Title: Re: Collision in Hash Function. Everyone Should Know this Post by: Wenbing on April 17, 2020, 11:21:06 AM There's nothing "harsh" about that quote, it's actually mild and comforting :) FTR, There is currently no recorded collisions for both SHA-256 and RIPEMD-160, Bitcoin is using the two famously for computing "pubkey hash". 1.What's the effect of detecting collisions on the harsh outputs? For the particular hash function, projects that are using it like Bitcoin would start looking for safer alternatives.Like if SHA256 proved to become unsecured after discovering multiple collisions or successful collision attacks, developers might consider using SHA512 instead. <addition, because my answer didn't really answered the question: For Bitcoin address collisions (because it was created through hashing), the two persons who own the private keys that derived the same address can spend each other's funds> Quote from: Wenbing 2.Is collision an advantageous cryptographic occurrence or not.? No.Quote from: Wenbing 3.Are there cryptographic measures in place in order not to experience collisions in harsh outputs? For "pubkey hash", Bitcoin has been using two entirely different hash functions. So if one got compromised, there's another one to break.For some "Redeem script" and "P2SH addresses", the same as above. For Mining, Bitcoin uses SHA-256d (d=double) for a reason: (wiki: SHA-256d (https://en.bitcoinwiki.org/wiki/SHA-256d)) While taking a course on cryptography and block chain, Are those questions part of your exam?Firstly, I'm sorry for using HARSH instead of HASH, it's a typo error. Secondly, the questions are not part of my exams but part of my efforts to seek more knowledge about what I'm learning since the course didn't treat it the way I wanted. Thanks. we have two hash function types, the non-cryptographic and cryptographic hash function. the former is usually used for hash-based lookups like hash tables,... one example is MurmurHash. collision is a common thing in this group and we don't care about it. the later is used for cryptography when security is needed. the output lengths are larger than 160-bit. the one bitcoin uses is SHA256. collision in this group can be considered impossible due to the huge result size that the data is being mapped to. That's an intelligent input, thanks. From what you mentioned "non cryptographic hash function does not care about security while cryptographic hash care more about security" I want to know what are the applications of the former and why is security negligible ? One of the primary uses of a hash is to validate the authenticity of a digital item. If the hash for an item is known, then any change to the item is easily detected because the hash of the modified item will not be the same as the known hash. However, the ability to find a collision gives an attacker the ability to make changes to the item in such a way that the hash does not change. Read this article: https://www.zdnet.com/article/sha-1-collision-attacks-are-now-actually-practical-and-a-looming-danger/ Is collisions not a malfunctioning of the cypropgraphic Hash function or is it what human or hackers cause in order to have access into another user's private key? I'm not clear about what you explained. Title: Re: Collision in Hash Function. Everyone Should Know this Post by: bitmover on April 17, 2020, 11:43:55 AM Is collisions not a malfunctioning of the cypropgraphic Hash function or is it what human or hackers cause in order to have access into another user's private key? I'm not clear about what you explained. I don't think collisions are "malfunctioning" of a hash function. They are more like a limitation of it. As explained above, you can have a string of ANY lenght and return an output of fixed length. It is mathematically impossible to make unique different unlimited outputs (of limited size) for unlimited inputs of ANY size. There is a limitation in the output (the size) and no limitation in the input. Someday there will be a collision (two different inputs with the same output). But that doesn't mean that this collision will be breaking private keys at will. The computer force necessary to break private keys, like brute forcing it, would be better used in mining. Title: Re: Collision in Hash Function. Everyone Should Know this Post by: pooya87 on April 18, 2020, 03:18:41 AM That's an intelligent input, thanks. From what you mentioned "non cryptographic hash function does not care about security while cryptographic hash care more about security" I want to know what are the applications of the former and why is security negligible ? because they are not designed to be used for anything that requires security. their use case as i mentioned in an example above is different. here is more examples: - checksums and error detections - hashtables - bloom filters (bitcoin uses MurMur3 in its bloom filters). - ... we don't care about security in any of these, the purpose of hash function here is just to make our job easier. for example the checksum is there so that we have a quick way of knowing if the input is corrupted or not. in hashtables it is used to quickly compare big objects by only comparing a tiny integer (32-bit hash ie. Int32). now if a collision occurs it won't be the end of the world, for example in looking up in a hashtable we end up with more than one result with the same hash. keep in mind that even 32-bit is still big enough to keep the chances of collision low (1 in 2^32 or 4.2 billion) |