11 ms·
Show HN: Accelerating SHA256 by 100x in Golang on ARM
- matt_wulfeck 10y agoAre aes instructions new in aarch64 processors? I'm surprised this doesn't work magically "out of the box", but I'm not up to date with this stuff. Also, this is another really good reason never to use a sha2 as your hashing algo for password storage.
- loeg 10y agoAES and SHA2 are completely different algorithms. > Also, this is another really good reason never to use a sha2 as your hashing algo for password storage. I don't know what you mean by this. I understand that SHA2 is poor for some things, but I'm not sure how this illustrates that.
- niftich 10y ago> but I'm not sure how this illustrates that SHA2 just got even faster, so it illustrates rather well that you wouldn't want to use it for password storage -- of course that was always true, but the improvement drives that point home.
- jerf 10y agoEven if the ARM processor on a cycle-by-cycle basis keeps up with already-existing GPU SHA2 crackers (which I do not know), it will not keep up with the parallelism in the GPUs, which is easy for anybody to get through hashcat: https://hashcat.net/wiki/ https://hashcat.net/wiki/ SHA2 has not gotten faster. It was already blisteringly, unbelievably fast.
- WhitneyLand 10y agoMy understanding is that SHA2 is fine for password storage, given a prudent number of hashing rounds.
- niftich 10y agoIt's fine to use a SHA2 variant HMAC in PBKDF2 with an obscene, ever-increasing number of rounds, but the scrypt paper [1] provides a detailed justification why you may want to switch to a dedicated password hashing function regardless. To quote their website [2]: "We estimate that on [circa-2009] hardware, if 5 seconds are spent computing a derived key, the cost of a hardware brute-force attack against scrypt is roughly 4000 times greater than the cost of a similar attack against bcrypt (to find the same password), and 20000 times greater than a similar attack against PBKDF2." Specifically, PBKDF2 is a tool to produce mostly-okay password storage hash from crypto primitives that are totally unfit for it, while bcrypt, scrypt, Argon2 are purpose-designed to make certain kinds of attacks difficult, like time-memory tradeoffs, parallelized custom hardware attacks, etc. [1] http://www.tarsnap.com/scrypt/scrypt.pdf http://www.tarsnap.com/scrypt/scrypt.pdf [2] http://www.tarsnap.com/scrypt.html http://www.tarsnap.com/scrypt.html
- cperciva 10y agoAlmost right. bcrypt is not designed to be secure against ASICs; it requires a fixed circuit size. In fact, given that CPU acceleration is available for SHA2, I suspect that PBKDF2-SHA256 is now stronger than bcrypt based on the "if my server spends X seconds hashing this password, how much money will someone need to spend to crack it" metric.
- tedunangst 10y agoI waffle about with this metric. If it's cheap to buy a server with some feature, it's obviously cheap for an attacker to buy the same. Widespread SHA2 hardware means that SHA2 cracking hardware is also available to even the poorest of crackers. I think there's a sliding scale, where the ratio changes for some attackers but not for all.
- cperciva 10y agoRight, sophisticated attackers have had custom SHA256 circuits for a long time; less sophisticated attackers are only gaining them now that they are present in CPUs. But if you're defending against such less sophisticated attackers, you're still not losing anything; worst case, SHA256 instructions in CPUs give them the same speedup as you're getting so their cost remains fixed.
- creshal 10y agoIf you're using any hash directly for password storage you're doing it wrong, regardless of the specifics. PBKDF2-SHA2 with a reasonably high amount of rounds (>100000) is still okay-ish, although you should have transited to bcrypt years ago. And hopefully we'll see argon2 stabilizing and getting adoption soon™.
- matt_wulfeck 10y agoIt was a typo in my post, I meant sha2 and not AES.
- sbierwagen 10y agoI don't know what you mean by this. I understand that SHA2 is poor for some things, but I'm not sure how this illustrates that. You want password hashes to be very slow, (and to use a lot of RAM) to make brute force attacks difficult. SHA2 is fast, and having hardware support makes it even faster. This makes it a bad choice for a password hash.
- wyldfire 10y ago... by moving from a software implementation to a mostly hardware one. ;) Still a worthwhile article but the title seemed to make me think of implementation/algorithm changes.
- lossolo 10y agoMost of crypto hashes implementations in Go are hand written assembly for specific platforms.
- fwessels 10y agoNo, there are no algorithm changes (otherwise the results would be different), it is just taking advantage of the ARM SHA accelerations when they are available.
- webkike 10y agoI a change in algorithm does not necessarily lead to change in results. Two algorithms that produce the same results may be disparate, but I suppose it's up to your definition of disparate
- halomru 10y ago>there are no algorithm changes (otherwise the results would be different Insertionsort, Mergesort and Timsort are three wildly different algorithms with different speeds, but on every possible input they produce the exact same result
- gnaritas 10y agoSo with hardware sha256, can this mine bitcoin cheaper than an ASIC?
- argo_ 10y agoor find the private key of a bitcoin address faster?
- deleted 10y ago[deleted]
- astrodust 10y agoDoes it do terahashes per second? If not, then no.
- gnaritas 10y agoHaven't been keeping up on how fast ASIC's are, just asking, thanks.
- fwessels 10y agoNo, compared to an ASIC it will still be significantly slower.
- anonymous7777 10y agook mentioning Go here is a bit pointless. How did Go help compared to any other language when Arm has hardware instructions for SHA1&2?
- deleted 10y ago[deleted]
- fwessels 10y agoGo didn't help specifically, it is just that this package makes support for the ARM SHA instructions available for Golang.
- shurcooL 10y agoAlso Go has support for using assembly in a package natively, not all languages/build tools support that as easily.
- pjmlp 10y agoIt is pretty common in imperative compiled languages. Back when compilers were sold, the professional version always had an assembler in the box. In MS-DOS even BASIC compilers like Turbo Basic could use inline Assembly.
- theparanoid 10y agoThe amount of assembly in the Go ecosystem is crazy, ~1% of the standard library is assembly. There are better ways.
- giovannibajo1 10y agoMost of it is written to take advantage of special hardware instructions in CPUs. If you take OpenSSL (a C library), it's got many assembly code paths as well. I'm not sure why this should be a problem, it just shows attention to performance in my opinion.
- pcwalton 10y agoOpaque assembly blocks that the compiler doesn't understand the effects of are actually suboptimal for performance.
- drchickensalad 10y agoGenerally yes, specialized no.
- dlsniper 10y agoIs this a general thing or a Go specific one? This generic statement seems to be false given how many optimizations that actually need assembly exist in Go and not only.
- pjmlp 10y agoIt is a general thing and quite common. Either you keep adding intrisics to the compiler, or outsource it to an external Assembler. Even managed languages have bytecode Assemblers available.
- dlsniper 10y agoIs this a general thing or a Go specific one? This generic statement seems to be false given how many optimizations that actually need assembly exist in Go and not only.
- mrb 10y ago"Interestingly enough, there are actually comparable Intel SHA extensions to the ARM equivalents. Linux 4.4 has added support for this but so far we have not been able to identify any CPUs that will actually run this code." Intel Goldmont is the only microarch that implements the instructions. It was "released" in April: http://www.extremetech.com/computing/226800-intels-new-low-cost-apollo-lake-platform-skylake-graphics-new-goldmont-cpu http://www.extremetech.com/computing/226800-intels-new-low-c... But it is one of these annoying soft launches where the processors are not for sale anywhere, the specs are incomplete, and even ark.intel.com doesn't know about them. sigh
- kalden_ 10y agoIt seemed to me that some Xeons had those since 2014. See https://software.intel.com/en-us/isa-extensions/intel-sha https://software.intel.com/en-us/isa-extensions/intel-sha Should something be understood instead?
- mrb 10y agoHuh you seem right. Only the multi-socket Haswell seems to have them (E7-xxxxv3 and E5-26xxv3). And now Intel re-introduce the SHA instructions in some low-power low-end CPUs, but not for any desktop or single-socket server CPU? What a bizarre case of feature fragmentation. Typical Intel.
- pbsd 10y agoI think even Intel is confused about their own extensions at this point. The E7 and E5 Xeons are Haswell systems that slightly speed up SHA-256 and 512 with the introduced BMI2 RORX instruction. As far as I know there are no SHA extensions before Goldmont, as mrb said, and in Cannonlake for non-low-power chips.
- nickpsecurity 10y agoThe original one, that I'm aware, was VIA's C3 and such processors with Padlock Encryption. Came in the little Artigo computers I used in designs that gave me, for $300, a 1GHz processor at 25W, hypervisor support, crypto acceleration (incl RSA), and a TRNG. Bad little systems years ago when I was into them.
- serge2k 10y ago> WORD $0x4cdf2025 // ld1 {v5.16b-v8.16b}, [x1], #64 Why is the code written as words like this instead of just the assembly instructions?
- nickcw 10y agoBecause the Go assembler doesn't have those instructions built in most likely. That sort of thing is quite common in Go assembler. The assemblers are a little primitive and they force the assembly language for each processor into a common pattern, so when you are writing ARM assembler for instance, everything is backwards. I imagine having rationalised the assemblers between processors somewhat it makes the core developers lives easier though who have to lightly touch lots of different processor assembler.
- pjmlp 10y agoBackwards from AT&T point of view, right? Because for me it feels very natural, given the Z80 and Intel Assembly.
- fwessels 10y agoThe Golang assembly does not support all instructions, we've created a tool (see https://github.com/minio/asm2plan9s https://github.com/minio/asm2plan9s) to assist in translating instructions into their opcode equivalents.
- chewxy 10y agoDamn. That's neat. I wrote my own python script to translate whatever `as` spits out into BYTE $.... your tool'd have been neat when I wrote this http://blog.chewxy.com/2016/07/25/on-the-memory-alignment-of-go-slice-values/ http://blog.chewxy.com/2016/07/25/on-the-memory-alignment-of...
- fwessels 10y agoNice blog, and the tool would have helped indeed. And also, memory allocation is not the most obvious topic in Go/Golang assembly...
- cloudjacker 10y agoIts a bird! Its a plane! No no thats just my bitcoin miner booting up
- DanielDent 10y agoPretty sure there are planes which are quieter than some bitcoin miners...
- DanielDent 10y agoDid you compare performance to SHA512? Despite being a theoretically more secure/"harder" algorithm, on 64 bit platforms it can sometimes be faster than SHA256. If you don't want to use 512 bits, using 256 bits of the output of SHA512 is standardized as SHA512/256 and is considered valid/secure. (I'm unclear if this performance oddity remains true with the crypto hardware extensions being used here.)
- cyphar 10y agoThe oddity is that I believe sha512 uses 64-bit words while sha256 uses 32-bit words. So on 64 bit hardware sha512 will be faster (presumably because using the 32 bit registers is slower somehow, I don't know). This is why ZFS is adding support for sha512/256 as it's Merkel tree hashing function.
- DanielDent 10y agoThat fits with my understanding. What I don't know is how this interacts with the acceleration functionality the chip has. For instance, do the instructions end up being "please do sha256 on this data", or are they closer to AES-NI where it's "please perform one round of an AES encryption flow".
- akovaski 10y agoJudging from the source code[1] in the author's repository, it is the latter. (what I see is: perform 96 instructions, then subtract 64 from the message length, and repeat until the message length is 0) Intel seems to be the same way [2](2013) - i.e. looping over multiple instructions per 64 byte block. [1] https://github.com/minio/sha256-simd/blob/master/sha256block_arm64.s https://github.com/minio/sha256-simd/blob/master/sha256block... [2] https://software.intel.com/en-us/articles/intel-sha-extensions https://software.intel.com/en-us/articles/intel-sha-extensio...
- DanielDent 10y agoInteresting, thanks for pointing that out. This code is such a good example of the potential value of formal verification tools for crypto primitives.
- smegel 10y ago> minio/sha256-simd. So rather than writing your own module and a blog post bragging about it, why not just send a pull request to Golang core? There are lots of assembly code in there already dealing with special instructions on different architectures, there is nothing special about this. Or is being a humble programmer the antithesis of startup culture?
- tptacek 10y agoWe're not supposed to write comments like this on "Show HN" posts. This is Apache-licensed open source code. You can criticize it on its own terms, but tendentious criticisms of the motivations of its authors are off-topic for Show HN. The rule can/should be boiled down to: "First, respect new work."
- rukittenme 10y agoOr you could just kindly nudge him into opening a pull request. He's probably never done it before.
- mangeletti 10y agoConsidering their code is licensed under Apache 2.0, you could do that yourself, if that's what you think is the right thing to do. I don't see anything wrong with Minio writing a blog post to show off something neat they did. Also, considering how ubiquitous both hashing and ARM have become, 100x is a pretty valuable speedup.
- y4m4b4 10y agoThis is the plan, which will happen eventually right now we are keeping it out there for community comments and improvement in quality that might be needed before it is submitted upstream.
- userbinator 10y agoThis is the sort of thing that shows why the whole "pure RISC philosophy" of implementing only the simplest instructions is ultimately a pretty dead-end in processor design. CISC-style dedicated instructions and hardware which utilises them will always be more efficient than a pure software implementation using just "simple RISC instructions", because hardware can easily express specialised computations like the extreme parallelism of algorithms such as SHA while software implementations essentially rely on the instruction-scheduling mechanisms to arrange potentially hundreds or even thousands of instructions in an optimal order. In addition, when there is dedicated hardware, it is also significantly easier to add a SHA instruction than attempt to recognise sequences of many regular instructions that could be "fused together" into a single operation using that hardware. When there isn't, adding such an instruction that gets internally expanded into multiple uops for the equivalent using the existing functional units is still beneficial, since it leaves open room for an immediate performance gain on all existing software when a future revision does add that dedicated hardware, or optimises its microarchitecture to allow those (possibly different) uops to execute faster. Despite the name, ARM is definitely not very RISC anymore, and that's what has kept it competitive.
- bostik 10y agoBingo. If and when speed matters, ASIC beats a general-purpose CPU hands down, every time.
- femto 10y agoOr there is the middle ground of retaining the general purpose nature by making the "dedicated" hardware an FPGA. Potentially the best of both worlds. Xlinx has the Zynq (ARM+FPGA), Intel has bought Altera and is now doing CPUs with FPGAs in the package [2]. [1] http://www.xilinx.com/products/silicon-devices/soc.html http://www.xilinx.com/products/silicon-devices/soc.html [2] http://www.pcworld.com/article/3055526/intel-starts-baking-speedy-fpgas-into-chips.html http://www.pcworld.com/article/3055526/intel-starts-baking-s...
- cmrx64 10y agoThis can work for special-purpose projects, but might become problematic in general: reprogramming the FPGA can be slow (on the order of 10s of milliseconds) and you don't necessarily want to include FPGA state as part of task state in the OS. You also need to be careful about thermal limits and power draw (especially when reconfiguring). I doubt current-generation FPGAs will land in anything smaller than a server for a long time. There, you can have semi-permanent accelerators according to the server's role, and a larger thermal budget.
- deleted 10y ago[deleted]
- dharma1 10y agoHow about accelerating Keccak/SHA-3 (used on Ethereum)? I found this but seems it's not implemented on ARM/Intel hardware yet http://caslab.eng.yale.edu/workshops/hasp2016/HASP16-10.pdf http://caslab.eng.yale.edu/workshops/hasp2016/HASP16-10.pdf