Simple proof-of-work (based on HashCash)

Question 1

I’m trying to build a simple (yet effective) brute-force protection for my App-API.

The client requests an identity – the server supplies a random string (called seed, which it remembers via PHP session) and a security level.

If the client wants to login it needs to supply a suffix for the seed which results in a SHA512 hash with leading zero-bytes (security level times).

Java (generation):

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class HashCash {
    private final static String HASH_ALGORITHM = "SHA-256";

    private final MessageDigest hashGenerator;

    /**
     * Creates a new HashCash generator using the SHA-256 algorithm
     * @throws NoSuchAlgorithmException If the "SHA-256" algorithm is not available
     */
    public HashCash() throws NoSuchAlgorithmException {
        hashGenerator = MessageDigest.getInstance(HASH_ALGORITHM);
    }

    /**
     * Generates a HashCash for the specified level
     * @param seed A seed for the HashCash
     * @param targetLevel The target level for the HashCash
     * @return The generated HashCash
     */
    public long generateHashCash(final String seed, final int targetLevel) {
        // Variation counter (and final result)
        long counter = 0;
        while(true) {
            // Check if the current hashCash reaches the desired security level
            if(getSecurityLevel(seed + counter) >= targetLevel)
                return counter;
            // Increase hash counter
            counter++;
        }
    }

    /**
     * Computes the security level of the given value
     * @param value The value to compute the level of
     * @return The security level of the value
     */
    private final int getSecurityLevel(final String value) {
        hashGenerator.update(value.getBytes());
        final byte[] hash = hashGenerator.digest();
        int level = 0;
        for(final byte b: hash) {
            if(b != 0)
                break;
            level++;
        }
        return level;
    }
}

PHP (verification):

const HASH_CASH_SEC_LEVEL = 8;

/**
 * Verifies a HashCash suffix (by checking it's security level)
 * @param string $seed The seed of the identity
 * @param string $suffix The HashCash suffix
 * @return bool Whether the given HashCash suffix is valid
 */
function verifyHashCash(string $seed, string $suffix): bool {
    $hash = hash('sha256', $seed.$suffix, true);
    $level = 0;
    $length = strlen($hash);
    for($b = 0; $b < $length; $b++) {
        if(ord($hash[$b]) !== 0)
            break;
        $level++;
    }
    return $level >= HASH_CASH_SEC_LEVEL;
}

Are there any security related issues?
Are there performance optimizations for the Java code?

Question 2

public HashCash() throws NoSuchAlgorithmException {

SHA-256 is a requirement for any Java SE environment. Instead of throwing you should be catching and converting to a RuntimeException (or IllegalStateException) with this particular exception as cause.

public long generateHashCash(final String seed, final int targetLevel) {
...
private final int getSecurityLevel(final String value) {

If you’re going to design for performance you should not be using String types. The seed should be a byte array from the start. And you could use e.g. ByteBuffer to write an integer to an existing array that already starts with the seed.

Note that SHA-256 is a Merkle-Damgard hash function that handles input block-by-block. That means that if you start off with a large enough seed (512 bits or larger) you might as well pre-hash it. Of course this means mucking about within the hash implementation.

if(b != 0)
    break;
level++;

Generally the level calculation is performed on bits or even values (where the hash value, when seen as a unsigned number, is below a certain value).

As for performance: you can stop comparing whenever you encounter a number that doesn’t have the right level. It won’t matter much when compared the time required to perform SHA-256 in all probability, but it is still wasteful.

I don’t expect getSecurityLevel to perform the actual hash calculation. A getter is generally not expected to perform any work at all.

The PHP code doesn’t seem to reflect the structure of the Java application. If you have one getSecurityLevel method I would expect the same in the verification application, whichever language is used.

Otherwise, yes, it is a very simple proof of work. I’d rather require a few hashes instead of one, to average out the amount of work performed. With just one hash there will be a lot of luck involved, and the actual work will therefore vary rather wildly.

In the unlikely case that you’ve invented yet another popular PoW: I’d use 128 bits rather than a 64 bit long. It’s pretty easy to make a counter that operates on bytes directly, so you would not even have to convert to the binary values required for the hashing.

Leave a Reply Cancel reply