Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

BLAKE2 Claims Faster Hashing Than SHA-3, SHA-2 and MD5

timothy posted about a year and a half ago | from the loose-ends-may-appear-under-the-microscope dept.

Encryption 134

hypnosec writes "BLAKE2 has been recently announced as a new alternative to the existing cryptographic hash algorithms MD5 and SHA-2/3. With applicability in cloud storage, software distribution, host-based intrusion detection, digital forensics and revision control tools, BLAKE2 performs a lot faster than the MD5 algorithm on Intel 32- and 64-bit systems. The developers of BLAKE2 insist that even though the algorithm is faster, there are no loose ends when it comes to security. BLAKE2 is an optimized version of the then SHA-3 finalist BLAKE."

cancel ×

134 comments

Sorry! There are no comments related to the filter you selected.

cool (-1, Offtopic)

Anonymous Coward | about a year and a half ago | (#42388885)

I love hash. But is this legal without a prescription? I don't want the feds bogarting my algorithm!

Re:cool (1)

Taco Cowboy (5327) | about a year and a half ago | (#42392571)

According to wikipedia's page on the NISH-sponsored competition - @

http://en.wikipedia.org/wiki/NIST_hash_function_competition [wikipedia.org]

- one of the criteria of the elimination of potential candidates was ...

Security: "We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because something about them made us 'nervous,' even though we knew of no clear attack against the full algorithm."

Would the clause above invalidate Blake2??

ORAC (4, Funny)

MickyTheIdiot (1032226) | about a year and a half ago | (#42388901)

He was always good with codes...

Re:ORAC (1)

Nyder (754090) | about a year and a half ago | (#42389215)

He was always good with codes...

woot!

I don't trust new, untried crypto. (5, Funny)

SuricouRaven (1897204) | about a year and a half ago | (#42388903)

Give it, oh, five more versions.

Re:I don't trust new, untried crypto. (1)

davester666 (731373) | about a year and a half ago | (#42389377)

So, you want to wait until the version string the tool reports is at least 1.0.5?

Done!

Re:I don't trust new, untried crypto. (-1)

Anonymous Coward | about a year and a half ago | (#42389427)

Wooosh!

Re:I don't trust new, untried crypto. (2, Interesting)

Anonymous Coward | about a year and a half ago | (#42389819)

He's waiting for Blake's 7.

http://en.wikipedia.org/wiki/Blake%27s_7

Re:I don't trust new, untried crypto. (0)

Anonymous Coward | about a year and a half ago | (#42390885)

By then, it will probably be SHA-8.

links to NIST (5, Interesting)

girlinatrainingbra (2738457) | about a year and a half ago | (#42388913)

The BLAKE [wikipedia.org] hash function was an also-ran finalist for the NIST Hash function competition ( http://en.wikipedia.org/wiki/NIST_hash_function_competition [wikipedia.org] ). There is not yet a wikipedia page for BLAKE2, but the winner of the NIST competition was Keccak now known simply as SHA-3 since it won the competition [wikipedia.org] .
.
Why would an optimized (optimized for run time speed? optimized for low memory footprint while running? optimized to minimize the likeliness of hash collisions) version of the same BLAKE entrant be more useful? Perhaps an improved algorithm that made it better competition for Keccak would make more sense. I don't know enough math to say completely, and still need to read the details.

Re:links to NIST (2, Insightful)

Nexion (1064) | about a year and a half ago | (#42389003)

Yeah... I was under the impression that more hashes faster was a bad thing. That is something for which crackers tune their code, but they didn't explicitly mention password storage. Perhaps it is targeted more for checksum like usage.

Re:links to NIST (1, Informative)

nazsco (695026) | about a year and a half ago | (#42389101)

Time to encode is not always related to time to decode. So it would benefit dictionary attacks only,

Re:links to NIST (1)

Anonymous Coward | about a year and a half ago | (#42389179)

If you can decode a hash, your hash is very very broken.

Re:links to NIST (1)

rthille (8526) | about a year and a half ago | (#42390015)

And has a very large number of bits in the resulting hash...

Re:links to NIST (2, Informative)

Anonymous Coward | about a year and a half ago | (#42389207)

There is no "decode" - breaking hashes is done by brute force (or by using dictionaries + modifiers).

Re:links to NIST (1)

Anonymous Coward | about a year and a half ago | (#42389301)

>> Time to encode is not always related to time to decode.
What do you mean with "decode" ?

>> they didn't explicitly mention password storage
a very fast hash is bad for password storage. Password storage needs very slow hashes. generic hashing of a lot of data needs fast hashes.

Re:links to NIST (1)

Anonymous Coward | about a year and a half ago | (#42389969)

A fast cryptographically secure hash function is always nice to have, for example, deduplication in a filesystem. You want it to be as difficult as possible to create a hash collision, while not needlessly wasting time and CPU cycles.

For authentication, you'll of course be adding a salt and as much recursion as necessary to ensure brute force attacks aren't feasable. Nobody is going to depend on the hashing function alone.

Re:links to NIST (1)

sqlrob (173498) | about a year and a half ago | (#42391303)

No, nobody SHOULD depend on the hashing function alone.

There's a big difference between "shouldn't" and "doesn't"

Re:links to NIST (1)

Johann Lau (1040920) | about a year and a half ago | (#42389347)

That also means you can hash more often in the same time, it cancels out. I'm not a crypto expert or even non-doofus, but basically you keep inreasing the number of iterations as processing power increases, e.g. calibrate it to take at least N seconds once a year. Which has nothing to do with the algorithm used really; I just like to throw dangerous half-knowledge out there to see what happens haha.

Re:links to NIST (0)

steviesteveo12 (2755637) | about a year and a half ago | (#42389785)

No, making it easier to run multiple instances of a hash, especially on a CPU, doesn't benefit a legitimate user very much but it hugely benefits an attacker. The problem is the different workload that someone storing and verifying passwords has compared to someone who is trying to crack a long list of them. All but the biggest web services will be dealing with roughly one login at a time (ie. you're usually finished with the previous login before the next user tries to login) whereas people attacking will be trying to run as many hashes as possible as quickly as possible to find any matches.

For password storage, you want a really unwieldy hashing algorithm that runs slowly and expensively (in terms of I/O, memory and processing) because you want to punish an attacker for running it so many times. An algorithm that's too memory hungry or esoteric to run on something like a GPU core is all to the good right now.

Re:links to NIST (2)

Johann Lau (1040920) | about a year and a half ago | (#42389953)

All but the biggest web services will be dealing with roughly one login at a time (ie. you're usually finished with the previous login before the next user tries to login) whereas people attacking will be trying to run as many hashes as possible as quickly as possible to find any matches.

So how does a slower hash help here? It changes nothing about this fundamental principle.

An algorithm that's too memory hungry or esoteric to run on something like a GPU core is all to the good right now.

Botnets.

Re:links to NIST (2)

steviesteveo12 (2755637) | about a year and a half ago | (#42390059)

I thought you weren't a crypto expert?

Re:links to NIST (1)

Johann Lau (1040920) | about a year and a half ago | (#42392137)

I'm not trying to be dense, I just really don't get it.

For me, at least when just considering CPU, 1000 iterations of Algorithm A take as long as 1 iteration of an Algorithm B which is 1000 times slower, and a slower hash makes it slower for both sides in equal measure, likewise for a faster hash. That's why I claimed "it's a wash".

If there is a way to use memory/IO in a way that increases the cost for attacking it more than than the cost of defense, someone has to actually spell it out for me, or I'll remain ignorant :(

Re:links to NIST (5, Informative)

marcansoft (727665) | about a year and a half ago | (#42389439)

For password hashing, that is correct. However, cryptographic hash functions are not designed for such use (and yes, all the websites and services out there using plain hashes for passwords are Doing It Wrong, even if they are using a salt). You can build a good password hashing scheme out of a cryptographic hash function (for example, PBKDF2), but plain hash functions are not suitable (precisely because they are too fast).

Fast cryptographically secure hash functions are a Good Thing, so you can hash a given block of data (and thus compute its digest and e.g. verify its digital signature) as fast as possible. This speeds up things like GPG, SSL, Git*, good old sha1sum checksums, etc. If you then want to use such a hash function as the core of a password hashing scheme, you can compensate for the extra speed by simply increasing the number of iterations. Making a hash function slower is always easy.

*Git is pretty much stuck with SHA-1 for now, but future incompatible versions of the repo format could conceivably switch to a faster hash function if it made sense.

Re:links to NIST (0)

Anonymous Coward | about a year and a half ago | (#42390169)

A 100ghz 100,000 core CPU that could try a hash every 1 clock cycle wouldn't be an issue for a 12char+ strong pass-phrase. I'm not sure why people keep talking about the dangers of "fast" hashes.

Re:links to NIST (1)

Anonymous Coward | about a year and a half ago | (#42390815)

your theoretical CPU is slow

custom ASICs can compute hashes for different data in parallel, for 12 character password to be secure against them, it would have to be completely random, contain letters of mixed case, numbers and symbols

Re:links to NIST (0)

WaywardGeek (1480513) | about a year and a half ago | (#42390867)

I need some good crypto advice.

I happen to be at the point in writing a P2P application framework where I need to select a hash function for authenticating messages. Of course, I'll make it selectable in the future, but I need to choose a default hash. I was about to settle on SHA-2. However, I'm not happy with the performance of SHA-2 and SHA-3 compared to SHA-1, and frankly I need MD5 speed. Blake2p sounds like it fits the bill. I've downloaded the code and it seem simple enough to include in my project. I'm very tempted to start using it, at least for now.

The scheme I'm thinking of using is to do a standard key exchange so both peers share a secret key, and then to append the shared secret key to each message, take a 64-bit cryptographic hash of the whole thing, and append that to the message (without the shared secret key). The other peer can easily verify the hash, which should make random errors virtually impossible to get through, compared to the 16-bit CRC in TCP/IP packets, which I've seen fail plenty of times. 64-bits isn't enough to use as a document signature, but but for P2P message authentication, is there any reason to use a longer hash? Are there any good reasons other than the obvious (blake2 is not well battle tested) to avoid blake2?

The value of transactions over this protocol I expect to be credit-card sized purchases and small bank account values, rather than military grade secrets. If the PSK is long, say 512 bits, I don't see how guessing will get anywhere. Am I missing some attacks? Thanks in advance.

Re:links to NIST (2)

Jorl17 (1716772) | about a year and a half ago | (#42391237)

Why not Ask Slashdot?

Re:links to NIST (1)

marcansoft (727665) | about a year and a half ago | (#42391425)

First of all, you mention the TCP/IP checkum, at the same time as key exchanges, long PSKs, and money transfer. Which is it, simple message integrity or message authentication? If you need authentication, you shouldn't even be mentioning TCP/IP checksums. If all you need is integrity, then just append an MD5.

Assuming you need authentication: I don't have any opinion on Blake2, but you should use an HMAC instead of just appending the shared secret key and taking the hash. HMAC can be built on top of any hash function, including Blake2. You should also make your MACs at leasts 128 bits long, preferably 192 or 256. 64 bits is definitely bruteforceable these days. I wouldn't settle for anything shorter than 256 for a protocol that involves money.

Keep in mind that a basic message authentication code is only one piece of a secure protocol. There are many possible attacks that might slip through (e.g. replay attacks, MITM, timing attacks, ...). For example, you need to ensure that an attacker can neither reinject a message from the current session back into it (e.g. by using a sequence number in the signed payload) nor reinject a message from a different session (e.g. by ensuring that there is a random component to the shared secret) nor somehow guess the right MAC code (e.g. by making sure that the wrong-MAC responses do not leak any information, neither in contents nor timing), and of course there's always the host identification problem (preventing a simple MITM where the attacker performs a key exchange with both sides and resigns/reencrypts traffic both ways). Honestly, your first choice should be to use an existing well-tested protocol, such as TLS (you can build your own host verification rules on top of it, you don't have to use the "well-known" root CA list). Failing that, consult a real crypto expert.

Re:links to NIST (0)

Anonymous Coward | about a year and a half ago | (#42391443)

Okay, so first, what you want is a message authentication code [wikipedia.org] (MAC).

The "industry standard" for MACs is HMAC-SHA-1 or HMAC-SHA-256. You should consider using one of these if at all possible. There are many robust implementations of these, which may also contain protection against less obvious attacks like timing attacks.
(These typically have a verification function that take the message, the given hash, and the key, and returns true if the message is valid. E.g. crypto_auth_verify [cr.yp.to] )

If you really do need the performance and are willing to use a bleeding-edge algorithm, there is nothing technically wrong with using BLAKE2's keyed hashing mode. (Use blake2*_init_key(), or pass a key and keylen to blake2*())
Though if you are going to cut it down to 64 bits anyway, you should also check out SipHash [131002.net] , which is even faster and is geared towards this use case. It uses a 128-bit key and outputs a 64-bit hash.

Re:links to NIST (1)

diamondmagic (877411) | about a year and a half ago | (#42389443)

Don't confuse a hash with a key derivation function. A hash is just a cryptographic primitive, you shouldn't use it directly (like you don't use block ciphers directly). It should be fast, and if you need it to be slower, you can iterate its output through itself and slow it artificially.

A MAC like HMAC uses a hash, but it accepts a secret key as a parameter and it does some stuff to prevent so-called length-extension attacks (whereby given Hash(x) you can determine very quickly Hash(Concat(x, y)) for some C and x, meaning attackers can append data to your secret communications and go unnoticed). Speed is important in this application, and your secret key should already have enough security that speed doesn't matter: 128 bits of security (= 256 bit key) should outlive much of the combined computational power of the Earth. (There's 512 bit hashes because, among other reasons, one use of hashes is to cut their output in half thereby eliminating information about their internal state, and then the effective security is one-half of that, or 128 bits.)

Key derivation functions, like PBKDF2, by contrast, have to work with very low input strength, usually 40-80 bits. By iterating the hash 1000 times, you add 10 bits of security on top of your input strength. It's still not very secure, but it's better than the alternative of nothing.

Re:links to NIST (0)

Anonymous Coward | about a year and a half ago | (#42390105)

You can't “add” any bits of security strength by iteration. Output space is too big to be brute-forced efficiently and you simply slow down exploration of input space by those iterations. It has the same strength as without it, only constants are changed.

Re:links to NIST (1)

Anonymous Coward | about a year and a half ago | (#42389545)

You obviously have never used full disk encryption, ZFS, etc.

Faster hashes will be _very_ welcome!!!!

Re:links to NIST (-1)

Rockoon (1252108) | about a year and a half ago | (#42389153)

I think the elephant in the room is that more efficient hashing makes it less secure simply by being more efficient.

Whatever the metric is, be it keys/second, bytes/watt, .. whatever... greater efficiency for a given key size is weaker.

Re:links to NIST (5, Informative)

Anonymous Coward | about a year and a half ago | (#42389523)

A common misconception, but untrue. Cryptographic hashes can be used for many purposes - for storing passwords, to sign documents, to verify file integrity, as a short unique identifier for content, etc.

The only of these for which slower is better, is password storing.
If you are using e.g. cryptographic hash functions with a 512-bit output, it is irrelevant for practical security that one hash function is a billion times faster than another. Either way, you will not find a collision in the lifetime of the universe without finding a weakness in the hash.

Now, this applies when we can assume that any needed keys are of good randomness. This is not the case with passwords, because human-chosen passwords have low enough entropy that they can be guessed.
However, it is very simple to make a slow hash from a fast one by using a key derivation function like PBKDF2 [wikipedia.org] , which iterates over the hash function a configurable number of time, often hundreds of thousands.

In short, many applications benefit from a fast hash algorithm, and none suffer, because you can always easily make a slower one.

Re:links to NIST (0)

mysidia (191772) | about a year and a half ago | (#42389849)

Either way, you will not find a collision in the lifetime of the universe without finding a weakness in the hash.

If the hash is as strong as it is intended to be.

If the hash has weaknesses (and most any hash certainly will have as of yet undiscovered weaknesses); the increased efficiency in computing the hash for the application, also results in increased efficiency of searching for a collision.

A collision search / attack against the security of the hash will require some very large number of hashing operations. If the hash is more speed efficient, these attack operations will complete much more quickly.

Re:links to NIST (1)

mysidia (191772) | about a year and a half ago | (#42389929)

The only of these for which slower is better, is password storing. If you are using e.g. cryptographic hash functions with a 512-bit output, it is irrelevant for practical security that one hash function is a billion times faster than another.

No, it's not irrelevent. The 64-bit hash that cannot be sped up may be stronger than a 512-bit hash that can be computed quickly.

If the fast hash enables me to build an ASIC that can perform 10^150 hashing operations per second instead of 10^80, then I will be able to find a collision on the weak hash within a few hours, whereas, the slower 64-bit hash might have been something that would take hundreds of years.

Re:links to NIST (1)

Anonymous Coward | about a year and a half ago | (#42390217)

If the fast hash enables me to build an ASIC that can perform 10^150 hashing operations per second

Ohh, I see we're not working within the laws of thermodynamics anymore. 10^150 hashing ops you just did just consumed the entire MilkyWay for energy.

Re:links to NIST (2)

WaywardGeek (1480513) | about a year and a half ago | (#42391131)

No, his point was valid. You can always make a slow hash algorithm out of a fast one, for example by rehashing over and over again a 100K times. Speed in a hashing algorithm is always a good thing, so long as its used properly, which unfortunately often not the case. I'm hoping to avoid making a mistake myself. I'm considering using a blake2 64-bit authentication has in P2P messages. Any good reasons not to?

Re:links to NIST (2)

mysidia (191772) | about a year and a half ago | (#42392377)

I'm considering using a blake2 64-bit authentication has in P2P messages. Any good reasons not to?

That may not be a very conservative choice from a security standpoint. The algorithm is new, and has less review/scrutiny and has stood less of a test of time than some other algorithms such as SHA1, RIPEMD-160, Tiger, VSH, Whirlpool. The protocol or its optimization may be broken in a subtle way that will be discovered within 2 to 6 years.

Even BLAKE the SHA-3 finalist may have stood less scrutiny so far. Although; the finalist protocols for SHA3 will eventually be under a microscope, and a great deal of scrutiny from many crypto researchers. It remains to be seen of there will be an attack against new "optimized" version; frankly, I'm not sure how much scrutiny the optimized version will get if it's not also a finalist for SHA3, and it's not right now a widely used algorithm either.

I would suggest implementing the protocol in some manner with support for multiple choices of hashing algorithm, so you can upgrade later, or replace/transition away from the BLAKE-fast algorithm without breaking the network, if it turns out to have issues.

Re:links to NIST (2, Funny)

Zero__Kelvin (151819) | about a year and a half ago | (#42389211)

Yes. I hate optimized versions of things. Why does everyone think it's better just because they made it better?

Re:links to NIST (5, Informative)

Anonymous Coward | about a year and a half ago | (#42389227)

It is optimized for runtime speed, though they also claim a slightly lower memory footprint.
The chance of hash collisions is about the same for any unbroken cryptographic hash.

Keccak has good performance in dedicated hardware, but was one of the slower SHA-3 candidates in software implementations. Compared to MD5, the best SHA-3 implementation is between 2 to 4 times slower on recent Intel processors, or 5 times slower on a recent ARM CPU.

Note that NIST has stated that any of the five SHA-3 finalists would have been an acceptable SHA-3. Keccak was selected in part due to having a very different composition than the SHA-2 family, decreasing the risk that both are broken at once. That does not mean Keccak is superior to Blake for all purposes - if software speed is the main issue, it is almost certainly worse.

Re:links to NIST (2)

SirMarth01 (1790324) | about a year and a half ago | (#42390137)

NIST's comments on their selection of Keccak to be SHA-3: [nist.gov] (PDF)

Additionally, KECCAK complements the existing SHA-2 family of hash algorithms well. NIST remains confident in the security of SHA-2 which is now widely implemented, and the SHA-2 hash algorithms will continue to be used for the foreseeable future, as indicated in the NIST hash policy statement. One benefit that KECCAK offers as the SHA-3 winner is its difference in design and implementation properties from that of SHA-2. It seems very unlikely that a single new cryptanalytic attack or approach could threaten both algorithms. Similarly, the very different implementation properties of the two algorithms will allow future application and protocol designers greater flexibility in finding one of the two hash algorithms that fits well with their requirements.

So, Keccak wasn't necessarily chosen because it was "superior" to the other finalists (note that it's slow when implemented in software, especially in comparison to the other finalists), but because it was different enough that, should SHA-2 be found to be fundamentally broken, SHA-3 should remain unaffected.

An optimized version of BLAKE would be useful because it can run faster than SHA-3 in software, while also being (theoretically) stronger than SHA-2 (or other older algorithms).

Mind you, I'm not an expert in cryptography; regardless, it probably wouldn't be the greatest choice to use BLAKE2 right away. It's still not been held up to the level of scrutiny that something like SHA-2 has. (Although I'm certain that being a finalist has helped it come under much closer scrutiny than if it hadn't been one.)

As for why a fast cryptographically secure hash function is desirable, others have already answered that question better than I can.

Re:links to NIST (1)

aysa (452184) | about a year and a half ago | (#42390627)

Why would an optimized (optimized for run time speed? optimized for low memory footprint while running? optimized to minimize the likeliness of hash collisions) version of the same BLAKE entrant be more useful?

BLAKE2 is an improved version of the SHA-3 finalist BLAKE. Like BLAKE or SHA-3, BLAKE2 offers the highest security, yet is fast as MD5 on 64-bit platforms and requires at least 33% less RAM than SHA-2 or SHA-3 on low-end systems. I can find applications in cloud storage, software distribution, host-based intrusion detection, digital forensics, revision control and embedded systems https://blake2.net/blake2_20121223.pdf [blake2.net]

Time (1)

Anonymous Coward | about a year and a half ago | (#42388917)

If security is important to you, don't use it until its been around for a few years at least. Boy was it annoying replacing all the md5 usages in various codebases... and that's been around for more than "a few years."

Re:Time (1)

magic maverick (2615475) | about a year and a half ago | (#42389295)

So use a generic hashthis() function (or class, whatever), and then you don't have to replace sha3() or blake2() or whatever through your code, merely modify the hashthis() function to use the new algorithm instead. Forward thinking amirite?

Re:Time (4, Informative)

Gaygirlie (1657131) | about a year and a half ago | (#42389429)

So use a generic hashthis() function (or class, whatever), and then you don't have to replace sha3() or blake2() or whatever through your code, merely modify the hashthis() function to use the new algorithm instead. Forward thinking amirite?

Otherwise yes, but it would make all the existing data unreadable. If you make it easy to change the hashing method like that then you will also have to always track what data was hashed with what method.

Re:Time (1)

preaction (1526109) | about a year and a half ago | (#42389581)

Which is exactly what /etc/shadow does, and it's been around for a long time. These are all solved problems if anyone would pay attention.

Re:Time (1)

Gaygirlie (1657131) | about a year and a half ago | (#42389635)

Which is exactly what /etc/shadow does, and it's been around for a long time. These are all solved problems if anyone would pay attention.

No one was talking about unix passwords here. Data can be almost anything that needs to be hashed and it may be stored in SQL - databases, random text files, proprietary binary files and so on. In other words your referral to /etc/shadow is irrelevant.

Re:Time (1)

preaction (1526109) | about a year and a half ago | (#42389869)

People were talking about storing the hash algorithm with the hash (and implying it was a bad thing, or too much to ask for a simple programmer), which is what /etc/shadow does (which they did back before we had as much power and space as we do now.) The fact that /etc/shadow is storing passwords is, as you said, irrelevant. It stores info about the hash with the hash so that later you know what hash to use to verify.

Re:Time (1)

aliquis (678370) | about a year and a half ago | (#42390183)

Because it's so hard to store hash,MD5 or hash,SHA3 or whatever in two fields in a database.

Re:Time (1)

zippthorne (748122) | about a year and a half ago | (#42389641)

You have to do that anyway...

For passwords, I'd assume (but probably be wrong...) that you'd convert the password to the new hash either when the user signs in next, or when the user changes their password next, but you still have to be able to check against the old hash, so you'd always need to know what type of hash that is. Seems to me that the best place to store that is in a field in the database right next to the hash itself.

One would assume that hashthis() would be implemented to either be aware of the hash's algorithm (a property of its object, perhaps?), or take an argument that indicates the hash.

I would assume that the feature, "able to change the hash algorithm" would tend to get added either around the first time that it needed to be updated, or by experienced developers who have already experienced that event in other applications.

Re:Time (1)

magic maverick (2615475) | about a year and a half ago | (#42389701)

I almost said something like that, along with the solution, but figured people could figure it out on their own.

With password hashes, the type of hash tends to be part of the end result (e.g. $B$ indicates a hash of type B, while $A$ indicates a hash of type A; not real examples, 'cause I can't be bothered looking them up). You could easily do something similar with generic hashes.

zippthorne (in a sibling to this post) gave some other thoughts.

Re:Time (1)

mysidia (191772) | about a year and a half ago | (#42390055)

There is a common method of doing this, by inserting a "HASH TYPE" header in front of a password. RFC2307

SHA256 CRYPT() with 10000 rounds - {SHA256-CRYPT}$5$rounds=100000$hK.9TGSGMfuVhMY1$ukBEvc3eTCJNgiK.BIsNIWmq9JU3D8tMapmqwJB6ip0

Cleartext password - {plain}password {clear}password
Traditional Unix crypt - {crypt}FHrLg6eHMx2nA
Unsalted MD5 - {md5}
Salted MD5 - {smd5}p47J0UeLzLY+/Lk7q0ohOnMJTGI=
Unix MD5 Crypt - {md5-crypt}$1$QgAqzRlm$Wo69omVJhJHZR2aOKJ4qs1
Unsalted SHA - {sha1}...
Unsalted SHA - {sha}W6ph5Mm5Pz8GgiULbPgzG37mj9g=
Salted SHA1 - {ssha}Dh+8hirJLTZa79Pupbn4W5qbRMP9C7Bv
SHA256 - {sha256}
SHA512 - {sha512}
Salted SHA 256 - {ssha256}
Salted SHA 512 - {ssha512}
Windows NT Hash / MD5 - {nt}
NTLM - {ntlm}
Lanman - {lm}
{CRAM-MD5}
{plain-md4}(MD4 in hex)
{SKEY}....

They just need five more versions then.. (0)

Dynamoo (527749) | about a year and a half ago | (#42388947)

'nuff said.

Re:They just need five more versions then.. (1)

MickyTheIdiot (1032226) | about a year and a half ago | (#42388955)

Version 2 was code named Jenna.

Re:They just need five more versions then.. (0)

Anonymous Coward | about a year and a half ago | (#42389351)

I'm waiting for Avon.
"I'm not reversible, I'm not stupid, and I'm not hashing."

mod dP0wn (-1)

Anonymous Coward | about a year and a half ago | (#42389011)

asshole about.' One confirmed that *BSD numbers. The loss and some of the Want them there. declined in market questions, then ju6gernaut either Surprise to the polite to bring

Missing the point (1, Interesting)

Anonymous Coward | about a year and a half ago | (#42389119)

There are 3 aspects that are important to the security of hashing algorithms.

1) one-directional. You cannot get back to the original from the hash.
2) unique-ness. Fewer different sources with hash to the same result.
3) takes time to make. The quicker it is to create the hash, the quicker it is to brute-force your way through all possible combinations to find a hash that matches.

Most password cracking happens by getting a list of hashed password values through some other securitu exploit, and running as many hashes as you can as quickly as you can to find match.
If they're claiming a fast hash is a good thing, they're missing the point.

Re:Missing the point (5, Insightful)

Georules (655379) | about a year and a half ago | (#42389333)

Fast hashing has its uses as well. Such as verifying data transmissions. Passwords aren't the only things that we hash.

Re:Missing the point (1)

pipatron (966506) | about a year and a half ago | (#42389365)

3) takes time to make. The quicker it is to create the hash, the quicker it is to brute-force your way through all possible combinations to find a hash that matches.

Most password cracking happens by getting a list of hashed password values through some other securitu exploit, and running as many hashes as you can as quickly as you can to find match. If they're claiming a fast hash is a good thing, they're missing the point.

Bullshit. You don't bruteforce a 512 bit hash, no matter how fast it is. It simply doesn't work like that. You must find a weakness in the algorithm to break even much smaller hashes.

Re:Missing the point (1)

OneAhead (1495535) | about a year and a half ago | (#42389527)

No weakness required, simply the ability to make educated guesses about the data being hashed. As in brute forcing password hashes [wikipedia.org] . Granted, hash functions are used for a host of other applications, but password hashes happen to be pretty high-profile, and most definitely have a requirement that they shouldn't be too fast. You can call GP's claim 3) not generally true, but to call it bullshit is, well, bullshit.

Re:Missing the point (0)

Anonymous Coward | about a year and a half ago | (#42390407)

In most applications, data being hashed is not even secret. That 3rd claim is simply irrelevant for general purpose cryptographic hash functions. It applies only to special constructions for password storage.

Re:Missing the point (3, Informative)

magic maverick (2615475) | about a year and a half ago | (#42389381)

Nah, you are. Hashes are used for a lot more than just passwords. Yes, for passwords a fast generic hash function like SHA2 or SHA3 (let alone MD5) is not such a good option. But for verifying that a downloaded executable or other file has not been modified, it's mostly fine. But don't use MD5, because it's completely broken (e.g. with it being possible to have two distinct PDF files having the same hash).

For password hashing use Blowfish/Bcrypt [codahale.com] .

Re:Missing the point (1)

Immerman (2627577) | about a year and a half ago | (#42390079)

Just to clarify - it's not the duplicate hashes that are the problem. Hash collisions should *always* be considered inevitable since the number of possible pdfs (or whatever) will exceed the number of possible hash values by many, many orders of magnitude unless the hash size is as large as the original file. The problem is that it's possible to *intentionally* cause a hash collision - for example by appending some "garbage" data to a compromised executable to make it appear to as though it's the original. And that's really only a problem in situations where you're using the hash to guard against malicious intervention, which is only one application of hashes. If you're simply using it to detect transmission or storage errors it's a non-issue. And if you're using it to generate something like a really good hash-table key (something secure hashes can also be quite valuable for) then you still need to be able to recognize and gracefully handle duplicate keys because collisions *will* eventually occur, a good hash just makes them uncommon enough that they're unlikely to cause performance penalties.

Re:Missing the point (1)

Pseudonym (62607) | about a year and a half ago | (#42390543)

Hash collisions should *always* be considered inevitable since the number of possible pdfs (or whatever) will exceed the number of possible hash values by many, many orders of magnitude unless the hash size is as large as the original file.

The number of possible PDFs is larger, but the number of actual PDFs is lower. Much lower.

A very reliable rule of thumb is that if there are N possible hash values, then you should expect 0.5 hash collisions after hashing N items. (Exercise: Prove this. You want to consider the limit as N goes to infinity.) So if you're hashing PDF files and looking for a collision, then for a 512-bit hash, you need around 2^256 PDF files to have a realistic chance of a collision. I'd wager that there aren't anywhere near 2^256 PDF files.

Of course hash collisions should always be considered inevitable. As you say, that's just good programming practice. However, if your hash function is good and has a large range, it can safely be considered rare.

Re:Missing the point (1)

WillerZ (814133) | about a year and a half ago | (#42390843)

A very reliable rule of thumb is that if there are N possible hash values, then you should expect 0.5 hash collisions after hashing N items.

No you shouldn't. You should expect 0.5 collisions after hashing N/2 items. Trivially you are guaranteed at least M collisions when hashing N+M items.

I don't actually know off the top of my head how many collisions you should expect if you hashed N items.

Re:Missing the point (2)

Immerman (2627577) | about a year and a half ago | (#42391041)

Okay, I can only assume that that's a typo - if you have N possible hash values and have hashed N items then you almost certainly already have many, many collisions, and are guaranteed a collision on the (N+1)th hash by the pigeonhole principle.

Consider that a good hash function will bear many similarities to a random number generator and you'll see that it's a variant of the birthday problem - you don't need 180 people in a room to get a 0.5 chance of two people having the same birthday, only something like 20-30 (I don't remember exactly), and the effect scales sub-linearly. Logarithmically if I remember correctly. So yes, a good hundreds-of-bits hash function will generate values that can safely be considered rare, just NOT unique. And even events with billions-to-one against odds happen all the time in the real world, just not in a predictable fashion.

Re:Missing the point (1)

fnj (64210) | about a year and a half ago | (#42392095)

Are you sure you don't mean "you need around 2^511 PDF files"?

2^256 is not anywhere near half of 2^512.

Re:Missing the point (1)

magic maverick (2615475) | about a year and a half ago | (#42390683)

Well yes. Good point that I should have made, it is the intentional aspect that is most worrisome. You take a PDF file, take the hash, and then can easily generate another PDF file with the same hash. Which apparently could be used for fraud. Or, take an executable and then generate a malicious one with the same hash and trick someone into downloading it instead of the correct one. I should have expanded on that point in my original post.

Re:Missing the point (0)

Anonymous Coward | about a year and a half ago | (#42391773)

Link to source? I worked for a short time in anti-malware development. MD5s are often used to identify binaries. Malware authors could benefit somewhat from being able to collide with the MD5 of a well-known benign binary (detection evasion). I am not a crypto expert, but I was only aware of MD5 collision generation based on carefully crafted input files. That is, I did not find that a general method existed for modifying an arbitrary input file in any way such that a different set of bytes would have the same MD5. I would be interested in reading about it if such a thing exists.

Re:Missing the point (2)

fnj (64210) | about a year and a half ago | (#42392187)

Good and fast hashes are all you need for any purpose. You can't make a slow hash fast, but it's trivially easy to make a fast hash slow. You just use sequential rounds [archlinux.org] , enough of them to make it slow.

SHA-512 is fine for passwords. It's the best there is. You're nuts to use anything else, the US military agrees with me, and it is the default in RHEL6 and other recent security conscious distros. The thing is, nobody with any sense uses a single round for this purpose. They use 5000, or 50,000, or 719,246. When you configure your password security on linux to SHA-512, glibc defaults to 5000 rounds.

Re:Missing the point (1)

Agent ME (1411269) | about a year and a half ago | (#42389517)

Taking time is only important if your input data is small and you don't want someone guessing the input data and verifying it against the hash.

If you want a hashing algorithm to take time, it's not that hard: just run it X times.

Re:Missing the point (1)

Desler (1608317) | about a year and a half ago | (#42389615)

Hashes are used for far more than storing passwords securely.

Re:Missing the point (2)

PhrostyMcByte (589271) | about a year and a half ago | (#42389721)

3) takes time to make. The quicker it is to create the hash, the quicker it is to brute-force your way through all possible combinations to find a hash that matches.

I wouldn't say that. The hash itself should be as quick as possible, so long as it satisfies the other requirements. We have things like PBKDF2 when we want a hash to eat up a lot of CPU, and scrypt when we want to eat up lots of RAM as well.

Re:Missing the point (1)

eric_herm (1231134) | about a year and a half ago | (#42389815)

You forgot : changing a little bit the input should ideally produce a totally different output ( ie, good cascading effect, if I am not wrong on the property ).

Re:Missing the point (0)

Anonymous Coward | about a year and a half ago | (#42390423)

A little knowledge is a dangerous thing. Moron.

Re:Missing the point (0)

Anonymous Coward | about a year and a half ago | (#42392435)

It was definately me that was missing the point here. As has been pointed out to me, hashing has many more uses than just passwords (just as thumbprints have more uses than unlocking doors); and as with everything, faster is better — if your password hashing hasn't taken long enough, hash it again, and repeat until it *is* sufficiently time-consuming.

To everyone who pointed out my fallacy without being condescending about it, thank you and Merry Christmas.

To everyone who was an asshole about my mistake, well, Merry Christmas to you too, because that's what I was taught Christmas is about: whether or not you celebrate Christmas, Christmas celebrates you.

Faster? (0)

sgnn7 (2127164) | about a year and a half ago | (#42389221)

Increased speed of hashing is usually a bad thing since passwords stored many times use a one-way hash function. With a faster hashing speed those passwords will be faster to crack. Personally, I'd opt for the highest-enthropy, slowest-speed, and lowest collision ration hashing function.

Re:Faster? (0)

Anonymous Coward | about a year and a half ago | (#42389311)

It would probably be quite easy to get a dedicated FPGA to either perform hashes much faster, or perform many of them in parallel (or both). For a good hashing algorithm, making it run ten times as fast on a CPU will not make it significantly easier to break.

Re:Faster? (1)

Buzer (809214) | about a year and a half ago | (#42389343)

It depends on what hashing function is used or. For passwords, yeah, that kind of function is good. But that's not the only use for hash function. If you need to know if files X and Y in different systems are identical, you want that checksum pretty fast. If you are transmitting data at 10Gbit/s and want to make sure it's going without problems, you are going to need something very fast. But you most likely want to make sure it's still slow enough that it cannot be bruteforced on the wire.

Re:Faster? (4, Informative)

Anonymous Coward | about a year and a half ago | (#42389415)

Faster hashing is better. The good guys have to pay a cost of X for hashing at b bits. The attacker has to, ideally, pay a cost of 2^b*X (well, a little less due to the Birthday paradox, but it'll still be exponential). Halving X helps the good guys, because hashing is now faster for everyone. It doesn't help the attacker because you should have chosen b to be so big that halving X makes just absolutely no difference because 2^b is so big that it's completely impractical even if X is just the time for a single cycle on a CPU.

Here's another way of looking at it: trying to impede the attacker by increasing X is the wrong idea because you ALSO have to pay for X. Instead, you want to focus on b because here your cost grows slowly with b while the attacker's cost grows exponentially with b. So smaller X is better, that is, faster hashes are better.

Re:Faster? (0)

Anonymous Coward | about a year and a half ago | (#42389779)

Mod parent up. It is easy to slow down a hash for specific applications (like passwords, which is about the only application in which you want a slower hash), but for most other applications, a faster hashing algorithm is better.

Re:Faster? (2)

sydneyfong (410107) | about a year and a half ago | (#42390089)

Generally you're right.

However, for passwords specifically, you'll need longer plaintext passwords for this to work. It doesn't matter how many bits your hash function is at, if the average password is only 8 characters of Alphanumeric (which, unfortunately, has entropy much less than 64 bits...). Salts help against things like rainbow attacks, but it won't help if an attacker is trying to crack one specific account that is protected by a 8 character password -- in that case, the speed of the hash function is the only variable in the cracking effort.

We all know we should have longer plaintext passwords, but the fact is -- our puny brains cannot remember random characters that well.

And passphrases haven't really caught on, unfortunately.

Re:Faster? (2, Interesting)

Anonymous Coward | about a year and a half ago | (#42390227)

That's why there are dedicated hash functions for password hashing like bcrypt and scrypt that should be used for this. One should never use generic cryptographic hash function for storage of passwords directly. Being slow was never considered as a goal in design of cryptographic hash functions, they are intended to be practical replacements for random oracles. They could, however, be used as a building blocks for PBKDF that might be appropriate for password storage.

Re:Faster? (1)

Pseudonym (62607) | about a year and a half ago | (#42390565)

The birthday paradox only lets you find a collision faster, not crack a specific password faster.

If you have a good b-bit hash function, then the expected cost of "undoing" a specific hash is X*2^(b-1), but the expected cost of finding half a collision (the birthday paradox scenario) is X*2^(b/2).

Famous last words (-1, Troll)

wonkey_monkey (2592601) | about a year and a half ago | (#42389293)

The developers of BLAKE2 insist that even though the algorithm is faster, there are no loose ends when it comes to security.

Except for the fact that it's faster, as others have already pointed out. Oh, and, on the second point about there being no loose ends - I'll let six months and an army of cryptography geeks on the internet be the judge of that.

Re:Famous last words (1)

Desler (1608317) | about a year and a half ago | (#42389659)

Faster is good for plenty of applications of hashes such as checksums on data.

Before "too fast = bad" (2, Interesting)

Anonymous Coward | about a year and a half ago | (#42389525)

I know I’m already too late for a few, but fast hashing is good. The only thing you want a slow hash for is a PBKDF—and, to be honest, that is and should be an entirely different construct to a hash, although you can make PBKDFs out of cryptographic hashes.

I’m still not seeing anything that makes this better than Skein, however, which is very fast in software, can perform signature pinned and keyed hashes and rounds (which could be used to make a PBKDF of arbitary strength), and even has a built-in tree hash function, and parallelises well. Skein’s still my favourite SHA-3 finalist by far, and I’m going to be using it in production instead of SHA-3—given FIPS won’t be driving SHA-3 adoption in short order, we won’t get hardware support for some time, and the NSA value hardware speed far more than software speed (as they mostly work with hardware CSMs). Further, I am not entirely convinced the round function underneath the sponge construction is necessarily different enough to survive an attack that would weaken AES.

Keccak’s way, way too slow given Skein and BLAKE are faster and of comparable security (although BLAKE was the second least favourite of my picks), and I suspect that SHA-3 will face slow adoption: there’s nothing obviously wrong with SHA-2, and absolutely no reason to move from SHA-256 to something significantly slower than SHA-256 when other hashes of comparable security exist which have received a similar amount of cryptographic attention and run faster. Keccak’s a poor sell.

As for PBKDFs, perhaps we need to hold another contest entirely for them, although it is also getting to the point that by the time we’d finish such a competition, passwords which the average person can remember have too little entropy to survive even brute force on any practical PBKDF you’d want to run (bearing in mind that if it runs too slow it represents a potential point of DoS), and no asymmetric PBKDF can exist that resists offline attacks.

It might also be worthwhile to hold a contest to define a tweakable block cipher and define more modes based on that, and perhaps that would be an interesting way forward.

Re:Before "too fast = bad" (0)

Anonymous Coward | about a year and a half ago | (#42389847)

Iâ(TM)m still not seeing anything that makes this better than Skein, however, which is very fast in software, can perform signature pinned and keyed hashes and rounds (which could be used to make a PBKDF of arbitary strength), and even has a built-in tree hash function, and parallelises well.

BLAKE2 is faster than Skein. BLAKE and Skein is mostly neck-and-neck, and BLAKE2 does some tweaks to make it faster, most importantly reducing the number of rounds by about one fourth. (16 to 12 rounds, and 14 to 10)

They also define a tree hash mode, and an increased-parallelism version.

It's not a bad specification, but the decreased round number does reduce the security margin. The authors claim that it is still comfortable, but I'll wait to hear what other cryptographers have to say on that.

It is also very configurable, which lets you tune it for your internal use case, but can be a disadvantage to implementations and standard specifications.

Re:Before "too fast = bad" (2)

TechyImmigrant (175943) | about a year and a half ago | (#42390455)

> the NSA value hardware speed far more than software speed

I don't think this is true for NIST though. Witness the results of the SHA competition. Keccak sucks in hardware compared to Skein. Skein is lovely to implement in hardware. Ultimately the sponge construction is what won it.

They certainly ignored my advice on hardware implementation.

Re:Before "too fast = bad" (0)

Anonymous Coward | about a year and a half ago | (#42390647)

Keccak sucks in hardware compared to Skein. Skein is lovely to implement in hardware.

I think you are misremembering something here. Keccak was definitely one of the best performers in hardware. Groestl also did well, IIRC. BLAKE was a decent all-rounder. Skein never did well in the performance-per-area metric, neither for FPGA nor ASIC.
I can't at the top of my head remember how JH did, but hopefully better than in software.

Re:Before "too fast = bad" (3, Insightful)

TechyImmigrant (175943) | about a year and a half ago | (#42391109)

The issue is not so much how small and fast you can make one instance of the algorithm, but rather, how it scales from small/slow to fast/big. An algorithm like a hash or block cipher gets baked into many silicon contexts, like instructions, or memory datapaths, or offload processors, or IO datapaths. The size/speed/power requirements of these different contexts varies.

Keccek is harder to divide down into smaller execution chunks in hardware than skein.
Skein has an add-xor core operation that is repeated width-wise and depth-wise. So you can easily scale it in width, depth and pipeline depth in order to meet the needs of the situation.

Fastest Encryption (0)

Anonymous Coward | about a year and a half ago | (#42390027)

Is this: source_byte_to_encrypt XOR some_random_byte.

Re:Fastest Encryption (1)

TechyImmigrant (175943) | about a year and a half ago | (#42390461)

> [Fastest Encryption] Is this: source_byte_to_encrypt XOR some_random_byte.

No it isn't. The complex part is the generation of 'some_random_byte'. Check out SP800-90A,B & C. Those are not efficient algorithms.

The SW speed of BlakeX is moot (3, Interesting)

TechyImmigrant (175943) | about a year and a half ago | (#42390245)

The software speed of the SHA algorithms is somewhat moot in the medium terms because over the medium term, crypto primitives (encryption, hashing, RNGs etc) are moving to hardware and moving to an instruction model instead of a device+device_driver model.

So the hardware implementations available to software through instructions will be faster than software implementations and have much better security properties in terms of attack surface and side channels. Modern crypto tends to fall to side channels and implementation error before it falls to crypto attacks and hardware is the best place to solve these problems.

At the recent NIST RBG Workshop http://www.nist.gov/itl/csd/ct/rbg_workshop2012.cfm [nist.gov]
I presented a short talk on where Intel is going. http://csrc.nist.gov/groups/ST/rbg_workshop_2012/johnston.pdf [nist.gov]

Basically, we've started putting standards based crypto primitives in hardware, on the CPU die, presented through the instruction interface (E.G. AES-NI, RdRand, RdSeed) to provide for more secure crypto on PCs. This is our publicly stated intent going forward. So who cares how many cycles it takes when there's a constant time instruction available that is faster?

Re:The SW speed of BlakeX is moot (0)

Anonymous Coward | about a year and a half ago | (#42390441)

The problem is cryptographic algorithms get broken. Ever heard of SHA0? Turns out they found a problem at the last minute and SHA0 never got much use, instead the 160-bit hash that got a lot of use was SHA1. Once you've got one of these in hardware, you can't accommodate changes. Cryptographic algorithms seem a good fit for GPUs, since they can be readily reprogrammed and (symmetric) cryptographic algorithms tend not to be too complex.

Re:The SW speed of BlakeX is moot (1)

TechyImmigrant (175943) | about a year and a half ago | (#42391067)

Yes, but the NIST competition method to define new algorithms that yielded AES and SHA3 seems to have focused more attention on the algorithms, so the odds of them being broken is reduced. SHA-0 and SHA-1 were essentially handed to the world on a plate, with little outside analysis.

So I have greater confidence in AES and SHA-3 that I did in the older algorithms. Hence me pushing to put such algorithms into CPU silicon.

 

fix the font! (0)

Anonymous Coward | about a year and a half ago | (#42391341)

Hey, Slashdot! Could you fix the formatting? I mean, I zoom pages because 8CPI is too small, but I can't zoom in on it.slashdot.org - you must have specified the font in a way that prevents zoom. This happens with all browsers I've tried (Fx, Sf, IE, Chrome). And it's really annoying

Faster is not better.... (0)

gweihir (88907) | about a year and a half ago | (#42392035)

Faster also means faster to attack. Also, there is absolutely no need for faster crypto-hashes at this time, the available ones are quite fast enough.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>