1
$\begingroup$

Let's imagine one hash function that is based on 10 hash functions. For every input, it changes the order of the 10 hash functions. So, for example:

Hello, World! -> md5 -> sha256 -> sha512 -> sha3_256 ... -> resulted hash -> sha256 (additionally)

Hello, World? -> shake_256 -> md5 -> sha256 -> sha3_256 ... -> resulted hash -> sha256 (additionally)

Will it be impossible to create an ASIC for such an algorithm? And if yes, what would be effective for brute force?

$\endgroup$
3
  • 2
    $\begingroup$ What is your actual aim? Why do you want such a randomly ordered hash function? If your actual problem is the passwords, we have already password hashing algorithms like Scrypt and Argon2 that are designed to be a memory-hard that prevents the GPU/FPGA/ASICs. Besides, they have an iteration parameter that linearly affects the cost of brute force. If you are considering the small input space then HMAC is the solution. $\endgroup$
    – kelalaka
    Jan 27, 2021 at 15:40
  • $\begingroup$ @kelalaka Thanks for question. In fact, this idea just came to my mind (not sure if I was the first) and it seemed to me that it was protected from ASIC (obviously because I was not in the subject). I implemented it, posted it on GitHub and hopefully described it as protected from ASIC, but something bothered me, and for good reason :) $\endgroup$
    – Non
    Jan 27, 2021 at 16:10
  • $\begingroup$ ASIC? do you know how many transistors the CPU designers use? you play on the beach, they are in the sea. $\endgroup$
    – kelalaka
    Jan 27, 2021 at 17:00

1 Answer 1

7
$\begingroup$

Will it be impossible to create ASIC for such algorithm?

No, actually it is quite easy.

The way you'd design a single brute-force core then is that you take a hashing engine for each hash function used, an input generator, a hash validator and a smart interconnect.

Then when you want to brute-force an invocation of ordering 1, the input generator outputs the guess along with routing / ordering information for the interconnect which then sends it to the appropriate engines in the appropriate order. As you are only targeting one ordering at a time, you could possibly even make this a state register of the interconnect. Then, once the first engine has processed the first piece of data, the interconnect receives it back, checks its ordering register and sends it to the next engine, while accepting the next guess for that ordering from the input generator which is promptly sent to the first engine.

Will it be impossible to create ASIC for such algorithm?

As you have seen exemplified above, there is no algorithm which is really hard to brute-force for an ASIC. The best one could hope for is that the optimal ASIC configuration would be (close) that of a modern CPU, but even then, chances are that the algorithm will not use specific parts of the CPU, e.g. FP cores, which a dedicated ASIC can drop.

$\endgroup$
7
  • $\begingroup$ I would think the best way to make an algorithm hard to brute-force with an ASIC or FPGA would be to make it easy to process with commodity graphics hardware which legitimate users could use. An FPGA may test more possible keys per joule than a commodity CPU running code for a commodity CPU, but wouldn't be able to process as many keys per joule as a GPU processing an algorithm that was designed to be GPU-friendly. $\endgroup$
    – supercat
    Jan 27, 2021 at 22:42
  • $\begingroup$ @supercat yes, GPUs tend to offer more raw power and make it easier to use large parts of the die. However, password hashing is commonly a server task and so assuming availabiity of a GPU is not something most designers want to make. $\endgroup$
    – SEJPM
    Jan 28, 2021 at 0:02
  • $\begingroup$ I thought the way to prevent an ASIC board was to construct an algorithm that inherently depends on a couple of GB of RAM. $\endgroup$
    – Joshua
    Jan 28, 2021 at 0:11
  • $\begingroup$ @SEJPM: There may be a chicken and egg problem, but if a system has some servers devoted to password hashing, including GPUs in those servers and migrating to password hash algorithms that exploit them could allow servers to offer more bang for the buck. The migration could be handled by having the database store what hashing scheme is used with each password, and converting passwords to the new format the next time a user logs in. $\endgroup$
    – supercat
    Jan 28, 2021 at 6:50
  • $\begingroup$ @Joshua That can be a very valid strategy to force the ASIC to imitate a CPU as the memory subsystem is a large and highly optimized part of modern CPUs. $\endgroup$
    – SEJPM
    Jan 28, 2021 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.