Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lifetimes of cryptographic hash functions

valerieaurora.org

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Lifetimes of cryptographic hash functions

#41

Post by cperciva »

jpdus wrote: post #24
rorrr2 wrote: post #23

It's missing the most important ones: Scrypt, PBKDF2, Bcrypt. https://en.wikipedia.org/wiki/Scrypt https://en.wikipedia.org/wiki/Bcrypt https://en.wikipedia.org/wiki/PBKDF2 Scrypt being an absolute nightmare to bruteforce, even for short passwords. http://i.stack.imgur.com/sOMvu.png

Can you explain why a 40 char text is 1000 times easier to crack than a 10 char password according to the graphic? Is it assumed you don't use any numbers/symbols and the attacker knows your dictionary?

The "40 char text" is based on NIST guidelines for estimating the entropy in English text -- i.e., dictionary words which make grammatical sense together. The "10 char password" is for 10 random printable ASCII characters.

Re: Lifetimes of cryptographic hash functions

#42

Post by dlitz »

mistercow wrote: post #28

>[1] Note that 128-bit hashes are at best 2^64 complexity to break; using a 128-bit hash is irresponsible based on sheer digest length. Can a short hash which has not been weakened be lengthened by taking two hashes and concatenating? fixedSalt = "blah" longerHash = (salt, input) -> hash(salt + input) + hash(salt + fixedSalt + input) Edit: Never mind. Obviously an attacker would only have to break the first half of t…

As an aside, you can use PBKDF2 with an iteration count of 1 to extend the output of a hash function to arbitrary lengths:

    output = HMAC-SHA256("passphrase", "salt" + x"00000001")
           + HMAC-SHA256("passphrase", "salt" + x"00000002")
          ...
This is useful when you want to derive keys from a (strong) master secret, but if you don't trust the underlying algorithm, all bets are off.

Re: Lifetimes of cryptographic hash functions

#43

Post by eterm »

qnr wrote: post #37
josephagoss wrote: post #32

If the SHA-2 family have weaknesses, and SHA-2 is used for generating Bitcoin blocks, whoever breaks this first will be an overnight millionaire, just make sure you break them slowly (about 20 a day max) to avoid suspicion that the hashing is compromised. Sell as much as possible and then release your paper.

Indeed, bitcoin is like a cryptography competition with ridiculously huge prize. 1. Break SHA2 -> control bitcoin generation ($2500 each generated block at current prices) 2. Break ECDSA -> unlock any addresses that have ever sent money on the blockchain 3. Break ECDSA+SHA2+RIPEMD160 -> break ALL addresses, even those that have never sent money. Incidentally, the difference between 2 and 3 is why it is not recommende…

Break any and the value of bitcoins will crash hard.

You can't take millions out of a system which doesn't actually have millions worth of liquidity backing it. The total worth of all bitcoins is actually far smaller than the market capitalization of all bitcoins because the trade of them is based off an assumption that many if not most coins are dead coins.

Re: Lifetimes of cryptographic hash functions

#44

Post by kolinko »

ReidZB wrote: post #26
rorrr2 wrote: post #23

It's missing the most important ones: Scrypt, PBKDF2, Bcrypt. https://en.wikipedia.org/wiki/Scrypt https://en.wikipedia.org/wiki/Bcrypt https://en.wikipedia.org/wiki/PBKDF2 Scrypt being an absolute nightmare to bruteforce, even for short passwords. http://i.stack.imgur.com/sOMvu.png

These aren't cryptographic hash functions exactly , though, at least not in the sense that a cryptographer would think. I mean, they will fit just about any definition of a cryptographic hash function you can think of, but really it's not that useful to label them as such. Instead, they're usually called key derivation functions. On top of that, even if we were to include these in a hash function list, they're decide…

Scrypt is being used by a few altcoins (litecoin for one), that's what makes it interesting for some people.

Re: Lifetimes of cryptographic hash functions

#45

Post by mistercow »

dlitz wrote: post #42
mistercow wrote: post #28

>[1] Note that 128-bit hashes are at best 2^64 complexity to break; using a 128-bit hash is irresponsible based on sheer digest length. Can a short hash which has not been weakened be lengthened by taking two hashes and concatenating? fixedSalt = "blah" longerHash = (salt, input) -> hash(salt + input) + hash(salt + fixedSalt + input) Edit: Never mind. Obviously an attacker would only have to break the first half of t…

As an aside, you can use PBKDF2 with an iteration count of 1 to extend the output of a hash function to arbitrary lengths: output = HMAC-SHA256("passphrase", "salt" + x"00000001") + HMAC-SHA256("passphrase", "salt" + x"00000002") ... This is useful when you want to derive keys from a (strong) master secret, but if you don't trust the underlying algorithm, all bets are off.

Hmm. That seems like it's still susceptible to the weakness sdevlin mentioned. For c = 1, it is the same thing that I suggested initially, and for larger c, it merely makes the hash more expensive to compute by iterating it, but the concatenation weakness would still hold, wouldn't it? It seems to me that this is perhaps useful for generating keys from passphrases, but not for lengthening a hash used to store a password in a database.

Re: Lifetimes of cryptographic hash functions

#46

Post by dlitz »

mistercow wrote: post #45
dlitz wrote: post #42

Earlier quoted context omitted.

As an aside, you can use PBKDF2 with an iteration count of 1 to extend the output of a hash function to arbitrary lengths: output = HMAC-SHA256("passphrase", "salt" + x"00000001") + HMAC-SHA256("passphrase", "salt" + x"00000002") ... This is useful when you want to derive keys from a (strong) master secret, but if you don't trust the underlying algorithm, all bets are off.

Hmm. That seems like it's still susceptible to the weakness sdevlin mentioned. For c = 1, it is the same thing that I suggested initially, and for larger c, it merely makes the hash more expensive to compute by iterating it, but the concatenation weakness would still hold, wouldn't it? It seems to me that this is perhaps useful for generating keys from passphrases, but not for lengthening a hash used to store a passw…

Yes, I think so. IIUC, with this construction, the difficulty only increases linearly with the length of the output, rather than exponentially, as one might expect.

I don't think there's a generically secure way to extend short hash functions to get an exponential difficulty increase. Otherwise, we could just construct arbitrary-length hash functions using small (e.g. 32-bit) building blocks without needing to cryptanalyze the result.

But then again, I haven't been paying attention to the literature lately.

Re: Lifetimes of cryptographic hash functions

#47

Post by qnr »

eterm wrote: post #43
qnr wrote: post #37

Earlier quoted context omitted.

Indeed, bitcoin is like a cryptography competition with ridiculously huge prize. 1. Break SHA2 -> control bitcoin generation ($2500 each generated block at current prices) 2. Break ECDSA -> unlock any addresses that have ever sent money on the blockchain 3. Break ECDSA+SHA2+RIPEMD160 -> break ALL addresses, even those that have never sent money. Incidentally, the difference between 2 and 3 is why it is not recommende…

Break any and the value of bitcoins will crash hard. You can't take millions out of a system which doesn't actually have millions worth of liquidity backing it. The total worth of all bitcoins is actually far smaller than the market capitalization of all bitcoins because the trade of them is based off an assumption that many if not most coins are dead coins.

Well, MtGox monthly volume is over 1 million BTC [1] or $100 million at current prices. I think you should be able to take out at least a few million without raising suspicion

In case of SHA2 compromise in particular, generating, say 20% of daily blocks would hardly be noticed (and can be easily explained as a new shipment of ASICs). This is about 720 BTC or $72000 daily.

[1] http://bitcoincharts.com/markets/mtgoxUSD.html

Re: Lifetimes of cryptographic hash functions

#48

Post by finnw »

qnr wrote: post #37
josephagoss wrote: post #32

If the SHA-2 family have weaknesses, and SHA-2 is used for generating Bitcoin blocks, whoever breaks this first will be an overnight millionaire, just make sure you break them slowly (about 20 a day max) to avoid suspicion that the hashing is compromised. Sell as much as possible and then release your paper.

Indeed, bitcoin is like a cryptography competition with ridiculously huge prize. 1. Break SHA2 -> control bitcoin generation ($2500 each generated block at current prices) 2. Break ECDSA -> unlock any addresses that have ever sent money on the blockchain 3. Break ECDSA+SHA2+RIPEMD160 -> break ALL addresses, even those that have never sent money. Incidentally, the difference between 2 and 3 is why it is not recommende…

Breaking SHA2 (i.e. developing an economically-feasible preimage attack) would indeed crash bitcoin, but the converse is not true.

A near-collision attack on double SHA256 (if you treat it as a single hash not a pair of independent hashes) would also crash bitcoin, but would not necessarily be a threat to use of SHA256 for authentication purposes.

A bitcoin block solution just needs the hash to include enough leading zeros. Authentication (nearly always being automated) requires every bit to match - hitting 255 of 256 bits is no better than hitting 0 bits, as either way your message will be rejected.

Re: Lifetimes of cryptographic hash functions

#49

Post by finnw »

nly wrote: post #21
tudorconstantin wrote: post #3

Confession time: i still have some apps with salted md5 hashed passwords

So migrate? Hash the hashes with Bcrypt or PBKDF2. Bcrypt(MD5(password)) is just as effective as Bcrypt(password) at knocking brute force attempts on the head.

Unless the Bad Guys already have the MD5 hashes

Re: Lifetimes of cryptographic hash functions

#50

Post by 16s »

ReidZB wrote: post #26
rorrr2 wrote: post #23

It's missing the most important ones: Scrypt, PBKDF2, Bcrypt. https://en.wikipedia.org/wiki/Scrypt https://en.wikipedia.org/wiki/Bcrypt https://en.wikipedia.org/wiki/PBKDF2 Scrypt being an absolute nightmare to bruteforce, even for short passwords. http://i.stack.imgur.com/sOMvu.png

These aren't cryptographic hash functions exactly , though, at least not in the sense that a cryptographer would think. I mean, they will fit just about any definition of a cryptographic hash function you can think of, but really it's not that useful to label them as such. Instead, they're usually called key derivation functions. On top of that, even if we were to include these in a hash function list, they're decide…

Cryptographic hash functions must be efficient to compute. Those examples (scrypt, bcrypt, etc) were designed to be difficult to compute. Those are password hash functions, not cryptogrpahic hash functions. Two totally different things with different purposes.
Post reply on HN