8 ms·

Is SHA-3 slow?

106 points by snakeanus 9y ago

Asdfbla 9y ago
My takeaway from this post kind of is that there are probably too many variants and derivatives of SHA-3. Then again, these days normal developers should probably use some recommended interface of mature crypto libraries anyway and shouldn't play around with cryptographic primitives directly, so maybe more choice for the library devs is good.
- baby 9y ago
  Yeah all these discussions are rather aimed at people who implement cryptography or have to make a well-thought hash choice at some point. As a developer you should use something like libsodium that has a default "hash" API. Underneath, the developers made the choice of choosing Blake2, but this is transparent to the user of the library. If you do not have access to high level libraries like that, and don't want to loose time/dig too much into the topic, following standards (SHA-3) is easy.
- paulddraper 9y ago
  > some recommended interface of mature crypto libraries Maybe for bubble code it'd be okay to just say "gimma a hash". But most real code needs to interoperate with stuff. E.g. I need to send a SHA-256 from a JS client to a Python server. So there needs to be a consistent and portable "SHA-256" concept that everyone understands. A cryptographic hash is not a complicated concept (even if developing one is). I suppose you can think about whether you require collision resistance or merely second pre-image resistance, but the popular ones are all intended to be collision resistant anyway.
  - mikepurvis 9y ago
    The interop situation with the CRC family of hash functions is terrible. Check this madness out: https://bitbucket.org/martin_scharrer/crccheck/src/default/crccheck/crc.py https://bitbucket.org/martin_scharrer/crccheck/src/default/c...
- npscalar 9y ago
  Yes and no. After all, these are just modes using Keccak (think, say, AES-CBC, AES-GCM all use AES), so the choice depends more on the purpose than anything else. But indeed, the naming is confusing. Instead of SHA3-256, SHAKE256, KMAC256 and ParallelHash256, maybe they should have better named them SHA-3-hash256, SHA-3-xof256, SHA-3-mac256 and SHA-3-parallel256 (or so).
annnnd 9y ago
Genuinly curious: isn't the whole point of cryptographic hash functions that they are slow by design, so that they can't be made faster?
- bonzini 9y ago
  No, you're confusing them with password hashing functions (bcrypt, scrypt) and password-based key derivation functions (PBKDF1, PBKDF2). These _are_ cryptographic hash functions, but they are designed to iterate many many times (the exact number is customizable) in order to take a given amount of time. "Generic" cryptographic hash functions like SHA-1/SHA-2/SHA-3 (or BLAKE, or MD5) don't iterate more times than is necessary for security, and are designed to be as fast as possible. This way, you can hash multi-gigabyte documents in a fraction of a second.
  - annnnd 9y ago
    Thank you for the clarification!
- detaro 9y ago
  No. Slow is primarily important for password hashes/key stretching, so specialized algorithms exist for those. General cryptographic hash functions should not be slow, since in many scenarios they are used on a lot of data and slowness has no security benefits.
- phire 9y ago
  For passwords, yes. You want your hash function to be as slow as possible to reduce the impact of brute force attacks. But for all other cryptographic purposes like message integrity checking, file verification, signing, or fingerprinting speed is extremely important. In these cases, the input to the hash is generally public, so there is no reason to even try bruteforcing. And even if you did, these inputs are much longer than passwords.
- baby 9y ago
  No good hash functions are usually fast. You're talking about "password hashing function", and I can understand the confusion. Maybe if people decided to rename these "pash" it would be easier. Anyway the state of the art here is Argon2 which won the latest password hashing competition: https://password-hashing.net/ https://password-hashing.net/
Sami_Lehtinen 9y ago
There are alternatives like BLAKE2. https://blake2.net/ https://blake2.net/
codazoda 9y ago
I'm not sure if SHA-3 has a design goal of being fast. My understanding is that, if your using it for encryption, for example password storage, you want it to be slow. This helps with brute force attacks, particularly if someone gets ahold of your database full of password hashes and can unleash as many calculations as they want. Because the SHA family has typically been fast, they are considered bad candidates for passwords. My quick Google foo doesn't turn up the goals of the competition, but I'm guessing being fast might be a negative.
- Cyph0n 9y ago
  Remember, what you are talking about is only one application of hash functions. In the world of crypto, speed becomes very important in things like MACs and signatures. There are a ton of other uses for hash functions that are not crypto-related too! Besides, even when using a "fast" hash function for password storage, you can always just increase the number of rounds to compensate.
  - deleted 9y ago
    [deleted]
- willvarfar 9y ago
  SHA-3 is supposed to be fast. Do not use SHA-3 for password storage! Use a key-stretching password hash function e.g. bcrypt or scrypt. (These take a fast hash or encryption function and apply it many many times, to make the total work be slow.)
  - dragontamer 9y ago
    You're technically wrong, but your concept is right. BCrypt and SCrypt are originally designed to be slow. PBKDF2 is the function that takes a fast hash function and applies it many times to make it slow.
    - deleted 9y ago
      [deleted]
deleted 9y ago
[deleted]
lucb1e 9y ago
Is this "is SHA-3 slow?" or is this "Look our new Keccak-based variant!"?
ComputerGuru 9y ago
Speaking of hashing quickly, I actually just posted an article about hardware-assisted SHA calculations and their support (or lack thereof) in mainstream processors, if anyone is interested. https://neosmart.net/blog/2017/will-amds-ryzen-finally-bring-sha-extensions-to-intels-cpus/ https://neosmart.net/blog/2017/will-amds-ryzen-finally-bring...
- baby 9y ago
  This was really really interesting! I'm currently trying to get SIMD to work in Go, and my problem right now is that it's hard to understand which SIMD instruction I should support (MMX, SSE, SSE2, SSE3, SSE4, AVX, AVX2, ...?) and how I should test what my architecture supports. If you have any resources on that I'd take it.
  - majewsky 9y ago
    AFAIK x86_64 requires that MMX and SSE1/2 are present, so that should be a pretty safe bet unless you have to support ancient x86_32 models.
  - tjalfi 9y ago
    [0] is a presentation on SIMD targeted at game developers. It has a lot of valuable information about instruction set support and how to make effective use of vector instructions. [1] is a HN comment that summarizes the content. [0] https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afredriksson_simd.pdf https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afr... [1] https://news.ycombinator.com/item?id=9312856 https://news.ycombinator.com/item?id=9312856
    - baby 9y ago
      Interesting, thanks for posting this! > If you have a 64-bit build, you WILL have SSE2 instructions Go allows you to detect a few architecture when you build (amd64, arm, arm64, 386) but not really the CPU model. So using SSE2 for anything amd64/arm64 would probably be a good solution.
- 9y ago
deleted 9y ago
[deleted]
sigmar 9y ago
Summary of the post: SHA-3 is slow, but check out these other recently proposed parallelized variants of Keccak, they could be much faster.
- espadrine 9y ago
  I read it this way: - On hardware, SHA3 is faster than every other contender in the competition. - On software, K12 is so fast that the bottleneck will not be its computation.
Tenoke 9y ago
A bit off-topic, but I am currently trying to recover ~$70000 worth of ether[1] from my presale wallet and the encryption used is indeed SHA-3. I'm currently trying 21970881 passwords against the hash using fairly basic python code (ETA: 2-3 days), and can definitely use tips for speeding up the work, as Id likely need to try an order of magnitude or 2 more generated password in order to crack it. 1. https://etherchain.org/account/0x35f5860149e4bbc04b8ac5b272be55ad1aca58e0 https://etherchain.org/account/0x35f5860149e4bbc04b8ac5b272b...
- webkike 9y ago
  It's pretty easy to speed up the process by using multi threaded gpu code.
- flipp3r 9y ago
  Python? There's tools for this, like oclHashcat/cudaHashcat
- esnard 9y ago
  You should definitively use hashcat[0]. It's the fastest hashing tool at the moment, and it supports both PBKDF2-HMAC-SHA256 and SCRYPT for Ethereum wallets since the last update. It can test 588 passwords per second on my modest GPU. I guess that's a lot better than a basic Python script. You should also have a look at probable wordlists[1], which contains a lot of passwords sorted by their popularity. It could significantly speedup the research, as long as your password has already leaked elsewhere. [0] https://hashcat.net/hashcat/ https://hashcat.net/hashcat/ [1] https://github.com/berzerk0/Probable-Wordlists https://github.com/berzerk0/Probable-Wordlists
  - Tenoke 9y ago
    The password definitely hasn't leaked as it is a one time password I created based on a somewhat complex scheme, but switching to hashcat (as also pointed outby flipp3r) seems to be the best next step.
- insomniasexx 9y ago
  The encryption actually is KECCAK-256, not SHA-3. However, if you are using a library built for Ethereum it'll be called SHA-3. When Ethereum was being developed, the spec for SHA-3 wasn't finished or something: https://ethereum.stackexchange.com/questions/550/which-cryptographic-hash-function-does-ethereum-use https://ethereum.stackexchange.com/questions/550/which-crypt... It sounds like you have it under control but I typically point people to Dave @ https://walletrecoveryservices.com/ https://walletrecoveryservices.com/ for the less tech-savvy. He's pretty good. You can look at his site for what he can and can't crack. I know he's super super busy but it never hurts to give him a shout and ask him if he has any pro-tips or open-source code somewhere. A ping from someone who has a basic understanding of encryption might be refreshing. Here are a random assortment of links I have saved regarding recovering presales: https://www.reddit.com/r/ethereum/comments/46887p/tips_for_recovering_your_presale_password/ https://www.reddit.com/r/ethereum/comments/46887p/tips_for_r... https://forum.ethereum.org/discussion/3045/request-post-password-instructions-that-were-given-for-the-presale-last-year https://forum.ethereum.org/discussion/3045/request-post-pass... https://www.reddit.com/r/ethereum/comments/3g6aw0/i_lost_my_password_to_my_presale_wallet_admit_it/ https://www.reddit.com/r/ethereum/comments/3g6aw0/i_lost_my_...
mtgx 9y ago
I think it's crazy that we're considering "settling" for a 128-bit hash function that we won't even start to adopt until 5-10 years from now, when Google is already planning to announce its 49-qubit quantum computer by the end of this year. It's also very likely that quantum computers will scale at a "Moore's Law" of sorts rate (doubling the qubits every 2 years or so, if not even faster in the first few years). We've seen that with D-Wave already. http://spectrum.ieee.org/computing/hardware/google-plans-to-demonstrate-the-supremacy-of-quantum-computing http://spectrum.ieee.org/computing/hardware/google-plans-to-... I feel the same about all of those "faster" (read: weaker) IoT-optimized crypto algorithms that are being proposed right now for standardization. What we should be talking about now is quantum-resistant algorithms that are likely to be even slower than SHA-3, but would at least protect communications against quantum computers. We need them soon, because they'll have to be deployed on 80%+ of the internet by 2030 or so, and we know how slow the internet ecosystem is at adopting a new protocol.
- johncolanduoni 9y ago
  Quantum computers are pretty unlikely to follow anything like Moore's law. They are fundamentally difficult to scale up due to decoherence and compounding of errors, a property that digital circuits have never shared. It's not "just" a matter of increasing density or clock rates.
- snakeanus 9y ago
  > I think it's crazy that we're considering "settling" for a 128-bit hash function Actually the sponge capacity in the so called 128-bit keccak functions is 256, they only call them 128-bit because they provide 128bits of preimage and collision resistance (at 256 bits of output). In a quantum setting the difficulty for preimage and collision attacks for these functions is 2^(256/3), when assuming that the output is of at least 256 bits. > What we should be talking about now is quantum-resistant algorithms that are likely to be even slower than SHA-3 SHA3-256 has c = 512 and output of 256 bits (128 bits of preimage resistance and ~85 bits of collision resistance on a quantum setting), while SHA3-512 has c = 1024 and output of 512 bits (256 bits of preimage resistance and ~170 bits of collision resistance on a quantum setting). I would say that both of the above sha3 versions are quantum resistant. Most modern symmetric cryptography would safe in a post-quantum world, I would say that the only thing that is left is to adopt post-quantum asymmetric algorithms more widely.
baby 9y ago
There is an RFC being drafted on K12 here: https://tools.ietf.org/html/draft-viguier-kangarootwelve-00 https://tools.ietf.org/html/draft-viguier-kangarootwelve-00
- tptacek 9y ago
  Why would this matter? You can get an IETF RFC drafted on pretty much everything. Dan Harkins even got Dragonfly an RFC: https://tools.ietf.org/html/rfc7664 https://tools.ietf.org/html/rfc7664.
  - baby 9y ago
    I'm just pointing out this thing because it's relevant and was released two days ago :)
SamUK96 9y ago
I'de say it's quite deliberate. Giving the consumer horde better SHA calculators is not necessarily a good idea. A lot of the theory behind making hasher functions strong is the assumed sheer expense a hypothetical brute-forcer would incur in buying the hardware. If Intel and every myChip Corp. releases chips with better SHA calculators, you'd be risking a global "hacking" frenzy and a potential global meltdown. The other reason of course is the NSA and the US deep state strong-arming chip makers to keep the general consumer from getting access to fast SHA calculators, since then they can get "private" chips made just for them so they're computationally ahead of the brute-forcing curve. I mean it's not a big leap to think that, they've already been bribed into the IME...
- dom0 9y ago
  https://www.youtube.com/watch?v=zrWoG8IckyE https://www.youtube.com/watch?v=zrWoG8IckyE
- johncolanduoni 9y ago
  A consumer GPU will already beat the pants off of any hardware SHA-3 implementation in the CPU for brute-forcing purposes.
  - SamUK96 9y ago
    Replace Intel with nVidia or AMD, it was an exemplar manufacturer showing that big chip-makers _can_ do shady things.
    - johncolanduoni 9y ago
      But nVidia and AMD haven't sabotaged their chips to be bad at hashing (it wouldn't surprise me if they did the opposite back before ASICs thrashed the GPU bitcoin mining scene) so I don't see how your point transfers. The Powers That Be also haven't put a damper on bitcoin mining ASICs for that matter, which can do precisely one thing: calculate lots of SHA hashes faster than any other hardware. If there's a shadow war over SHA hardware, the deep state is failing miserably.
almostdigital 9y ago
Who's gonna be the first to launch KangarooCoin or KeccakCoin with a SHA-3 proof-of-work?
- baby 9y ago
  There are already a bunch of blockchain stuff using SHA-3 apparently. If people want to drop a list of products/companies/apps that use SHA-3 (or other Keccak construction) I'd be interested! Ethereum uses SHA-3 to begin with.
  - Kubuxu 9y ago
    To be precise it uses variant of Keccak as NIST changed parameters of SHA-3 when they were already using it.
    - baby 9y ago
      They started using SHA-3 before it was standardized?
kerkeslager 9y ago
Anyone who thinks that Hacker News comments are a great source of information should consider the number of top-level commenters on this thread who don't know the difference between fast collision-resistant hashes and password hashes, but who decided to post as if they knew what they were talking about.
- baby 9y ago
  (on the other hand people were pretty quick to downvote/re-establish the truth)
- dsacco 9y ago
  In fairness, this is because 1) password breaches are the lowest common denominator of hash function discussions in which developers participate, and 2) developers have it beat into their heads not to use e.g. MD5 for password storage, but they don't typically receive the same lectures (with the same vehemence) for things like MACs.
  - kerkeslager 9y ago
    I don't really think this is much of an excuse. Fast collision-resistant hashes and password hashes are very basic crypto concepts. If you don't know that difference, it would be hard to pass even the most introductory course on cryptography. If you've literally no education on crypto except what you heard someone at work say once, you shouldn't feel qualified to correct crypto articles on Hacker News. Ignorance isn't the problem. The problem is ignorance combined with confidence.
    - dsacco 9y ago
      I think crypto is a field where one needs an unfortunately low amount of confidence (relatively speaking) to come across this way, because it's complex enough that the default position is extreme ignorance. That's why I try to be a bit more charitable - I don't think people are trying to come across as authorities on the subject, they just haven't had enough exposure. It's an unknown unknown. Better crypto education would help. I've been thinking for some time now about the state of cryptography education for non-experts, and what I've noticed over the years is we push a lot of digestible soundbites ("Don't use MD5, don't roll your own, use encrypt-then-mac", etc) without significant explanations. Sometimes there is an accessible explanation for these things that's appropriate for a message board comment, sometimes there isn't, and this advice is necessarily separated from a larger corpus of material due to the medium. If telling developers what not to do over and over again in order to dissuade them from shooting themselves in the foot has made them more secure overall, this is a good thing. But I do think it comes at the cost of not encouraging real understanding of why not to do these things. You're right that they shouldn't take specific positions without that understanding, but I think it can be hard for them to know they don't have it due to the culture.
atemerev 9y ago
Slow security is good security. It makes brute forcing more difficult, and promotes decentralization of infrastructure (slowness adds up only for large-scale deployments like Google and Facebook, and we want to depend less on centralized actors, not more). If you need to choose between strength and performance, choose strength in nearly 100% of all cases. You make the job of NSA or GRU much harder, and promote offsetting security mechanisms to the edge, where they ought to be.
- dsacco 9y ago
  Once you've reached an appropriate security margin you shouldn't pour more resources into making it even slower. You don't typically need to choose between performance and security in a general sense, because you can achieve very good performance with very good security. Slowing down your password hashing function any further than is required is overkill, and won't improve your security.
  - atemerev 9y ago
    Today's security margin is tomorrow's past news. Usually, security margins are planned against brute force according to Moore's law. This is not enough. Novel cryptographic attacks do not suddenly render the entire algorithm useless (usually); rather, they dramatically reduce its strength. And novel cryptographic attacks appear all the time even in the public space -- who knows what stays behind closed doors and clearances? If you have large enough security margin, you can escape unscathed while you upgrade your infrastructure. And if not, not.
    - dsacco 9y ago
      Sure, but even assuming Moore's Law, algorithms like SHA-2 and SHA-3 are not likely to broken within our lifetimes, if ever. For the set of hashing algorithms that are quantum-safe, you literally gain nothing in practice by making them arbitrarily stronger - they're already so strong that any increase in security margin is a negligible improvement slighter than a rounding error in computational time. But these improvements can come with a performance cost. There's generally no upside and only a downside for choosing to increase the strength beyond what's required for the sake of future proofing.

106 points by snakeanus 9y ago

My takeaway from this post kind of is that there are probably too many variants and derivatives of SHA-3. Then again, these days normal developers should probably use some recommended interface of mature crypto libraries anyway and shouldn't play around with cryptographic primitives directly, so maybe more choice for the library devs is good.

baby 9y ago
Yeah all these discussions are rather aimed at people who implement cryptography or have to make a well-thought hash choice at some point. As a developer you should use something like libsodium that has a default "hash" API. Underneath, the developers made the choice of choosing Blake2, but this is transparent to the user of the library. If you do not have access to high level libraries like that, and don't want to loose time/dig too much into the topic, following standards (SHA-3) is easy.
paulddraper 9y ago
> some recommended interface of mature crypto libraries Maybe for bubble code it'd be okay to just say "gimma a hash". But most real code needs to interoperate with stuff. E.g. I need to send a SHA-256 from a JS client to a Python server. So there needs to be a consistent and portable "SHA-256" concept that everyone understands. A cryptographic hash is not a complicated concept (even if developing one is). I suppose you can think about whether you require collision resistance or merely second pre-image resistance, but the popular ones are all intended to be collision resistant anyway.
- mikepurvis 9y ago
  The interop situation with the CRC family of hash functions is terrible. Check this madness out: https://bitbucket.org/martin_scharrer/crccheck/src/default/crccheck/crc.py https://bitbucket.org/martin_scharrer/crccheck/src/default/c...
npscalar 9y ago
Yes and no. After all, these are just modes using Keccak (think, say, AES-CBC, AES-GCM all use AES), so the choice depends more on the purpose than anything else. But indeed, the naming is confusing. Instead of SHA3-256, SHAKE256, KMAC256 and ParallelHash256, maybe they should have better named them SHA-3-hash256, SHA-3-xof256, SHA-3-mac256 and SHA-3-parallel256 (or so).

annnnd 9y ago

Genuinly curious: isn't the whole point of cryptographic hash functions that they are slow by design, so that they can't be made faster?

bonzini 9y ago
No, you're confusing them with password hashing functions (bcrypt, scrypt) and password-based key derivation functions (PBKDF1, PBKDF2). These _are_ cryptographic hash functions, but they are designed to iterate many many times (the exact number is customizable) in order to take a given amount of time. "Generic" cryptographic hash functions like SHA-1/SHA-2/SHA-3 (or BLAKE, or MD5) don't iterate more times than is necessary for security, and are designed to be as fast as possible. This way, you can hash multi-gigabyte documents in a fraction of a second.
- annnnd 9y ago
  Thank you for the clarification!
detaro 9y ago
No. Slow is primarily important for password hashes/key stretching, so specialized algorithms exist for those. General cryptographic hash functions should not be slow, since in many scenarios they are used on a lot of data and slowness has no security benefits.
phire 9y ago
For passwords, yes. You want your hash function to be as slow as possible to reduce the impact of brute force attacks. But for all other cryptographic purposes like message integrity checking, file verification, signing, or fingerprinting speed is extremely important. In these cases, the input to the hash is generally public, so there is no reason to even try bruteforcing. And even if you did, these inputs are much longer than passwords.
baby 9y ago
No good hash functions are usually fast. You're talking about "password hashing function", and I can understand the confusion. Maybe if people decided to rename these "pash" it would be easier. Anyway the state of the art here is Argon2 which won the latest password hashing competition: https://password-hashing.net/ https://password-hashing.net/

Sami_Lehtinen 9y ago

There are alternatives like BLAKE2. https://blake2.net/ https://blake2.net/

codazoda 9y ago

I'm not sure if SHA-3 has a design goal of being fast. My understanding is that, if your using it for encryption, for example password storage, you want it to be slow. This helps with brute force attacks, particularly if someone gets ahold of your database full of password hashes and can unleash as many calculations as they want. Because the SHA family has typically been fast, they are considered bad candidates for passwords. My quick Google foo doesn't turn up the goals of the competition, but I'm guessing being fast might be a negative.

Cyph0n 9y ago
Remember, what you are talking about is only one application of hash functions. In the world of crypto, speed becomes very important in things like MACs and signatures. There are a ton of other uses for hash functions that are not crypto-related too! Besides, even when using a "fast" hash function for password storage, you can always just increase the number of rounds to compensate.
- deleted 9y ago
  [deleted]
willvarfar 9y ago
SHA-3 is supposed to be fast. Do not use SHA-3 for password storage! Use a key-stretching password hash function e.g. bcrypt or scrypt. (These take a fast hash or encryption function and apply it many many times, to make the total work be slow.)
- dragontamer 9y ago
  You're technically wrong, but your concept is right. BCrypt and SCrypt are originally designed to be slow. PBKDF2 is the function that takes a fast hash function and applies it many times to make it slow.
  - deleted 9y ago
    [deleted]

deleted 9y ago

[deleted]

lucb1e 9y ago

Is this "is SHA-3 slow?" or is this "Look our new Keccak-based variant!"?

ComputerGuru 9y ago

Speaking of hashing quickly, I actually just posted an article about hardware-assisted SHA calculations and their support (or lack thereof) in mainstream processors, if anyone is interested. https://neosmart.net/blog/2017/will-amds-ryzen-finally-bring-sha-extensions-to-intels-cpus/ https://neosmart.net/blog/2017/will-amds-ryzen-finally-bring...

baby 9y ago
This was really really interesting! I'm currently trying to get SIMD to work in Go, and my problem right now is that it's hard to understand which SIMD instruction I should support (MMX, SSE, SSE2, SSE3, SSE4, AVX, AVX2, ...?) and how I should test what my architecture supports. If you have any resources on that I'd take it.
- majewsky 9y ago
  AFAIK x86_64 requires that MMX and SSE1/2 are present, so that should be a pretty safe bet unless you have to support ancient x86_32 models.
- tjalfi 9y ago
  [0] is a presentation on SIMD targeted at game developers. It has a lot of valuable information about instruction set support and how to make effective use of vector instructions. [1] is a HN comment that summarizes the content. [0] https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afredriksson_simd.pdf https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afr... [1] https://news.ycombinator.com/item?id=9312856 https://news.ycombinator.com/item?id=9312856
  - baby 9y ago
    Interesting, thanks for posting this! > If you have a 64-bit build, you WILL have SSE2 instructions Go allows you to detect a few architecture when you build (amd64, arm, arm64, 386) but not really the CPU model. So using SSE2 for anything amd64/arm64 would probably be a good solution.
9y ago

deleted 9y ago

[deleted]

sigmar 9y ago

Summary of the post: SHA-3 is slow, but check out these other recently proposed parallelized variants of Keccak, they could be much faster.

espadrine 9y ago
I read it this way: - On hardware, SHA3 is faster than every other contender in the competition. - On software, K12 is so fast that the bottleneck will not be its computation.

Tenoke 9y ago

A bit off-topic, but I am currently trying to recover ~$70000 worth of ether[1] from my presale wallet and the encryption used is indeed SHA-3. I'm currently trying 21970881 passwords against the hash using fairly basic python code (ETA: 2-3 days), and can definitely use tips for speeding up the work, as Id likely need to try an order of magnitude or 2 more generated password in order to crack it. 1. https://etherchain.org/account/0x35f5860149e4bbc04b8ac5b272be55ad1aca58e0 https://etherchain.org/account/0x35f5860149e4bbc04b8ac5b272b...

webkike 9y ago
It's pretty easy to speed up the process by using multi threaded gpu code.
flipp3r 9y ago
Python? There's tools for this, like oclHashcat/cudaHashcat
esnard 9y ago
You should definitively use hashcat[0]. It's the fastest hashing tool at the moment, and it supports both PBKDF2-HMAC-SHA256 and SCRYPT for Ethereum wallets since the last update. It can test 588 passwords per second on my modest GPU. I guess that's a lot better than a basic Python script. You should also have a look at probable wordlists[1], which contains a lot of passwords sorted by their popularity. It could significantly speedup the research, as long as your password has already leaked elsewhere. [0] https://hashcat.net/hashcat/ https://hashcat.net/hashcat/ [1] https://github.com/berzerk0/Probable-Wordlists https://github.com/berzerk0/Probable-Wordlists
- Tenoke 9y ago
  The password definitely hasn't leaked as it is a one time password I created based on a somewhat complex scheme, but switching to hashcat (as also pointed outby flipp3r) seems to be the best next step.
insomniasexx 9y ago
The encryption actually is KECCAK-256, not SHA-3. However, if you are using a library built for Ethereum it'll be called SHA-3. When Ethereum was being developed, the spec for SHA-3 wasn't finished or something: https://ethereum.stackexchange.com/questions/550/which-cryptographic-hash-function-does-ethereum-use https://ethereum.stackexchange.com/questions/550/which-crypt... It sounds like you have it under control but I typically point people to Dave @ https://walletrecoveryservices.com/ https://walletrecoveryservices.com/ for the less tech-savvy. He's pretty good. You can look at his site for what he can and can't crack. I know he's super super busy but it never hurts to give him a shout and ask him if he has any pro-tips or open-source code somewhere. A ping from someone who has a basic understanding of encryption might be refreshing. Here are a random assortment of links I have saved regarding recovering presales: https://www.reddit.com/r/ethereum/comments/46887p/tips_for_recovering_your_presale_password/ https://www.reddit.com/r/ethereum/comments/46887p/tips_for_r... https://forum.ethereum.org/discussion/3045/request-post-password-instructions-that-were-given-for-the-presale-last-year https://forum.ethereum.org/discussion/3045/request-post-pass... https://www.reddit.com/r/ethereum/comments/3g6aw0/i_lost_my_password_to_my_presale_wallet_admit_it/ https://www.reddit.com/r/ethereum/comments/3g6aw0/i_lost_my_...

mtgx 9y ago

I think it's crazy that we're considering "settling" for a 128-bit hash function that we won't even start to adopt until 5-10 years from now, when Google is already planning to announce its 49-qubit quantum computer by the end of this year. It's also very likely that quantum computers will scale at a "Moore's Law" of sorts rate (doubling the qubits every 2 years or so, if not even faster in the first few years). We've seen that with D-Wave already. http://spectrum.ieee.org/computing/hardware/google-plans-to-demonstrate-the-supremacy-of-quantum-computing http://spectrum.ieee.org/computing/hardware/google-plans-to-... I feel the same about all of those "faster" (read: weaker) IoT-optimized crypto algorithms that are being proposed right now for standardization. What we should be talking about now is quantum-resistant algorithms that are likely to be even slower than SHA-3, but would at least protect communications against quantum computers. We need them soon, because they'll have to be deployed on 80%+ of the internet by 2030 or so, and we know how slow the internet ecosystem is at adopting a new protocol.

johncolanduoni 9y ago
Quantum computers are pretty unlikely to follow anything like Moore's law. They are fundamentally difficult to scale up due to decoherence and compounding of errors, a property that digital circuits have never shared. It's not "just" a matter of increasing density or clock rates.
snakeanus 9y ago
> I think it's crazy that we're considering "settling" for a 128-bit hash function Actually the sponge capacity in the so called 128-bit keccak functions is 256, they only call them 128-bit because they provide 128bits of preimage and collision resistance (at 256 bits of output). In a quantum setting the difficulty for preimage and collision attacks for these functions is 2^(256/3), when assuming that the output is of at least 256 bits. > What we should be talking about now is quantum-resistant algorithms that are likely to be even slower than SHA-3 SHA3-256 has c = 512 and output of 256 bits (128 bits of preimage resistance and ~85 bits of collision resistance on a quantum setting), while SHA3-512 has c = 1024 and output of 512 bits (256 bits of preimage resistance and ~170 bits of collision resistance on a quantum setting). I would say that both of the above sha3 versions are quantum resistant. Most modern symmetric cryptography would safe in a post-quantum world, I would say that the only thing that is left is to adopt post-quantum asymmetric algorithms more widely.

baby 9y ago

There is an RFC being drafted on K12 here: https://tools.ietf.org/html/draft-viguier-kangarootwelve-00 https://tools.ietf.org/html/draft-viguier-kangarootwelve-00

tptacek 9y ago
Why would this matter? You can get an IETF RFC drafted on pretty much everything. Dan Harkins even got Dragonfly an RFC: https://tools.ietf.org/html/rfc7664 https://tools.ietf.org/html/rfc7664.
- baby 9y ago
  I'm just pointing out this thing because it's relevant and was released two days ago :)

SamUK96 9y ago

I'de say it's quite deliberate. Giving the consumer horde better SHA calculators is not necessarily a good idea. A lot of the theory behind making hasher functions strong is the assumed sheer expense a hypothetical brute-forcer would incur in buying the hardware. If Intel and every myChip Corp. releases chips with better SHA calculators, you'd be risking a global "hacking" frenzy and a potential global meltdown. The other reason of course is the NSA and the US deep state strong-arming chip makers to keep the general consumer from getting access to fast SHA calculators, since then they can get "private" chips made just for them so they're computationally ahead of the brute-forcing curve. I mean it's not a big leap to think that, they've already been bribed into the IME...

dom0 9y ago
https://www.youtube.com/watch?v=zrWoG8IckyE https://www.youtube.com/watch?v=zrWoG8IckyE
johncolanduoni 9y ago
A consumer GPU will already beat the pants off of any hardware SHA-3 implementation in the CPU for brute-forcing purposes.
- SamUK96 9y ago
  Replace Intel with nVidia or AMD, it was an exemplar manufacturer showing that big chip-makers _can_ do shady things.
  - johncolanduoni 9y ago
    But nVidia and AMD haven't sabotaged their chips to be bad at hashing (it wouldn't surprise me if they did the opposite back before ASICs thrashed the GPU bitcoin mining scene) so I don't see how your point transfers. The Powers That Be also haven't put a damper on bitcoin mining ASICs for that matter, which can do precisely one thing: calculate lots of SHA hashes faster than any other hardware. If there's a shadow war over SHA hardware, the deep state is failing miserably.

almostdigital 9y ago

Who's gonna be the first to launch KangarooCoin or KeccakCoin with a SHA-3 proof-of-work?

baby 9y ago
There are already a bunch of blockchain stuff using SHA-3 apparently. If people want to drop a list of products/companies/apps that use SHA-3 (or other Keccak construction) I'd be interested! Ethereum uses SHA-3 to begin with.
- Kubuxu 9y ago
  To be precise it uses variant of Keccak as NIST changed parameters of SHA-3 when they were already using it.
  - baby 9y ago
    They started using SHA-3 before it was standardized?

kerkeslager 9y ago

Anyone who thinks that Hacker News comments are a great source of information should consider the number of top-level commenters on this thread who don't know the difference between fast collision-resistant hashes and password hashes, but who decided to post as if they knew what they were talking about.

baby 9y ago
(on the other hand people were pretty quick to downvote/re-establish the truth)
dsacco 9y ago
In fairness, this is because 1) password breaches are the lowest common denominator of hash function discussions in which developers participate, and 2) developers have it beat into their heads not to use e.g. MD5 for password storage, but they don't typically receive the same lectures (with the same vehemence) for things like MACs.
- kerkeslager 9y ago
  I don't really think this is much of an excuse. Fast collision-resistant hashes and password hashes are very basic crypto concepts. If you don't know that difference, it would be hard to pass even the most introductory course on cryptography. If you've literally no education on crypto except what you heard someone at work say once, you shouldn't feel qualified to correct crypto articles on Hacker News. Ignorance isn't the problem. The problem is ignorance combined with confidence.
  - dsacco 9y ago
    I think crypto is a field where one needs an unfortunately low amount of confidence (relatively speaking) to come across this way, because it's complex enough that the default position is extreme ignorance. That's why I try to be a bit more charitable - I don't think people are trying to come across as authorities on the subject, they just haven't had enough exposure. It's an unknown unknown. Better crypto education would help. I've been thinking for some time now about the state of cryptography education for non-experts, and what I've noticed over the years is we push a lot of digestible soundbites ("Don't use MD5, don't roll your own, use encrypt-then-mac", etc) without significant explanations. Sometimes there is an accessible explanation for these things that's appropriate for a message board comment, sometimes there isn't, and this advice is necessarily separated from a larger corpus of material due to the medium. If telling developers what not to do over and over again in order to dissuade them from shooting themselves in the foot has made them more secure overall, this is a good thing. But I do think it comes at the cost of not encouraging real understanding of why not to do these things. You're right that they shouldn't take specific positions without that understanding, but I think it can be hard for them to know they don't have it due to the culture.

atemerev 9y ago

Slow security is good security. It makes brute forcing more difficult, and promotes decentralization of infrastructure (slowness adds up only for large-scale deployments like Google and Facebook, and we want to depend less on centralized actors, not more). If you need to choose between strength and performance, choose strength in nearly 100% of all cases. You make the job of NSA or GRU much harder, and promote offsetting security mechanisms to the edge, where they ought to be.

dsacco 9y ago
Once you've reached an appropriate security margin you shouldn't pour more resources into making it even slower. You don't typically need to choose between performance and security in a general sense, because you can achieve very good performance with very good security. Slowing down your password hashing function any further than is required is overkill, and won't improve your security.
- atemerev 9y ago
  Today's security margin is tomorrow's past news. Usually, security margins are planned against brute force according to Moore's law. This is not enough. Novel cryptographic attacks do not suddenly render the entire algorithm useless (usually); rather, they dramatically reduce its strength. And novel cryptographic attacks appear all the time even in the public space -- who knows what stays behind closed doors and clearances? If you have large enough security margin, you can escape unscathed while you upgrade your infrastructure. And if not, not.
  - dsacco 9y ago
    Sure, but even assuming Moore's Law, algorithms like SHA-2 and SHA-3 are not likely to broken within our lifetimes, if ever. For the set of hashing algorithms that are quantum-safe, you literally gain nothing in practice by making them arbitrarily stronger - they're already so strong that any increase in security margin is a negligible improvement slighter than a rounding error in computational time. But these improvements can come with a performance cost. There's generally no upside and only a downside for choosing to increase the strength beyond what's required for the sake of future proofing.