0
$\begingroup$

Short version

Is it possible to accelerate hashing process by computing several hashing together in a "smart" way?

Long version

It's generally true that the algorithm complexity of several problems together is smaller than one problem alone.

A concrete example is Fast Fourier Transform. Given N points (assume N is power of 2), the time complexity of getting one single frequency in FT spectrum is O(N). However, we have O(N log(N)) time complexity when we need to compute all frequency.

Another classical example is Strassen algorithm on matrix multiplication.

Would it be theoretically possible to design a batch hashing algorithm on classical computer, such that the time complexity is reduced?

For reducing problem scope, let's just consider the SHA class hashing algorithm

Such "smart" algorithm would have a big impact on password cracking, and cryptocurrency mining.

Improve this question
$\endgroup$
3
  • $\begingroup$ like tree hashing? $\endgroup$
    – Ella Rose
    Commented Aug 26, 2017 at 3:55
  • $\begingroup$ "It's generally true that the algorithm complexity of several problems together is smaller than one problem alone." The generality of this statement is simply wrong - otherwise it would be true for every single problem / algorithm. And of course someone would have to prove it. A correct statement would be "It is possible that ..." $\endgroup$
    – tylo
    Commented Aug 28, 2017 at 14:47
  • $\begingroup$ SHA-class hashing algorithms should not be directly used for password hashing anyway. The baseline would be to use PBKDF2-HMAC-SHA-something, with salt. $\endgroup$
    – fgrieu ♦
    Commented Aug 28, 2017 at 14:47

1 Answer 1

Reset to default
6
$\begingroup$

Short version: no. Secure hash algorithms are designed to foil exactly the attack you describe.

Long version: a cryptographic hash function operates starting with a block-size number of bits and a pre-defined starting state, then runs those bits through several "rounds" of transformation. Each round modifies the state. The input to each round depends on the output of the previous round. Once a block is finished, the remaining state of the digest is used as the starting state of the next block. Therefore you can't begin to compute the second block until the first block is completed.

And when brute force attacking SHA became too efficient to protect small inputs like passwords, techniques like "salting" and password based key derivation functions like PBKDF2() were adopted. Salting adds random data as a starting point for the hash, helping ensure that even if two users select the same password, the random salt will be different so their passwords won't hash to the same value. PBKDF2 takes the output of a hash digest, and feeds it back in to the hash algorithm mixed with the original message again and again, repeating this up to 60,000 times (or more). This ensures that any efficiency in computing SHA will require 60,000 (or more) SHA calculations to break, whether they be iterations on a single box, or a chained set of 60,000 (or more) dedicated SHA cracking engines. Not to say that it can't be done by a well-funded government or a well-funded criminal organization, but outside of that elite realm, it's not likely.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For unsalted hashes I believe the answer is yes, in that cracking N hashed passwords doesn't take N times more operations than cracking one hashes password - it will take at most double the operations (as one password is likely to be found after searching through half the password space). $\endgroup$
    – David Wachtfogel
    Commented Aug 27, 2017 at 18:34
  • 1
    $\begingroup$ @DavidWachtfogel: what you consider does not "accelerate hashing process" as asked; it accelerates password search, and only for an extremely poor choice of password hashing method. $\endgroup$
    – fgrieu ♦
    Commented Aug 28, 2017 at 14:54

Your Answer

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

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