2
$\begingroup$

Is this algorithm demonstrating proof of work? This is a algorithm where a "token" is combined with a time stamp and then a cryptographic hash is generated from the combination, next the objective is to find a token whose hash will collide with N digits of the timestamp+token hash.

This operation is computationally intensive and requires work by the client. The resulting token is time sensitive and expires. This could possibly be used to deter a denial of service attack. or other brute force attacks.

What is this algorithm called? Is something similar in use? is it a demonstration of "proof of work"?

Here is a demonstration of the algorithm in python. 

import hashlib
import time 
import os
import base64 

# Number of digits that should collide 
dificulty = 4
my_token = "nTDKIHbBus1O5cyebXQfFw==" 
the_time = str(int(time.time()))  
temporary_token = the_time+my_token

hash_stamp = hashlib.sha256(temporary_token).hexdigest()
collison_to_find = hash_stamp[:dificulty] 
the_hash = ""

# Find a hash where the first N digits collide 
while the_hash[:dificulty] != collison_to_find:
    # Generate a random token
    access_token = base64.b64encode(os.urandom(16))
    the_hash = hashlib.sha256(access_token).hexdigest()

print "temporary_token: ", temporary_token
print "access_token: ", access_token

This is the output

temorary_token:  1387573427nTDKIHbBus1O5cyebXQfFw==
access_token:  UwwSWGw14GK262rVPLPSOQ==

the first 4 digits of the token's hash will collide.

6095e4f38cd5f8e4581531fc29910614ecc54b8359ea8640bc5967d60ae1b043

609549c931eac0934d1fbb49d0dca7f2e4a621832251a8d786e60936a8761f41

Improve this question
$\endgroup$
  • $\begingroup$ In the future, we generally ask that questions on Crypto.SE should use pseudocode to describe the algorithm concisely -- rather than giving a full implementation. Here the code makes it harder to understand what is going on, whereas you could describe the basic algorithm in one or two lines of simple mathematics. Just letting you know for the future.... $\endgroup$ – D.W. Dec 20 '13 at 23:52
3
$\begingroup$

In anticipation of this question being migrated.....

  • there is no need for the client-side to hammer /urandom. The odds of any subsequent random byte stream hashing to the same prefix are the same (actually worse) as the odds of any simple incrementing value.... i.e. you may as well change the urandom reference to just something++
  • A sophisticated client-side 'attacker' who knows the number of significant digit matches would be easily able to compute a rainbow-table of tokens that match the incoming digits. This ranbow-table will not take much longer to generate than the actual proof-of-work you require, and would be almost instantaneous to query.

All this process does is make legitimate access harder, and nefarious access fast.... ;-)

Improve this answer
$\endgroup$
  • $\begingroup$ My algorithm is not for authentication in and of itself , Here is a wikipedia article describing the concept en.wikipedia.org/wiki/Proof-of-work_system $\endgroup$ – kyle k Dec 20 '13 at 22:48
  • $\begingroup$ @kylek, I think you've misunderstood rolfl's answer. Rolfl is 100% correct on both of his criticisms, and I think you misunderstood his points and haven't fully grokked his critique yet. Maybe read it a second time? (Rolfl clearly does understand that this is for proof-of-work, not for authentication.) $\endgroup$ – D.W. Dec 20 '13 at 23:50
2
$\begingroup$

No. This is not a good design of a proof-of-work system. Your design involves the server providing a value $y$ and asking the client to provide $x$ such that $H(x)=y$ (where $H$ is a hash function truncated to a suitable number of bits). As rolfl explains, this is not adequately secure; it is vulnerable to precomputation attacks, e.g., Hellman's time-space tradeoff or rainbow tables.

The proper protocol is to have the client provide a random 128-bit value $r$ and ask the client to provide $x$ such that $H(r,x)=0$ (where again $H$ is a cryptographic hash function truncated to a suitable number of bits). That is secure against precomputation attacks.

Rolfl already made this exact point; I am just elaborating in more detail, since it appears you didnt quite appreciate his observation.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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