FNV1 Brute Force

Fnv1Collision.java

import sun.misc.Contended;

import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.LongAccumulator;

/**
 * Created by jcairns on 6/20/17.
 */
public class Fnv1Collision {

    // private static final String idfa = "6D92078A-8246-4BA4-AE5B-76104861E7DC";

    private static final long FNV_64_INIT = 0xcbf29ce484222325L;
    private static final long FNV_64_PRIME = 0x100000001b3L;

    private final String id;
    private final long   hash;

    private final ForkJoinPool forkPool = new ForkJoinPool();

    private volatile boolean foundCollision;

    private final Random secureRandom;

    @Contended
    private LongAccumulator currentCount = new LongAccumulator((x, y) -> x+y, 0L);

    public static void main(String[] arg) throws NoSuchAlgorithmException {
        final Fnv1Collision fnv1 = new Fnv1Collision();
        fnv1.checkCollisionRate();
    }

    private Fnv1Collision() throws NoSuchAlgorithmException {
        foundCollision = false;

        secureRandom = new SecureRandom();

        id = generateIdfa(secureRandom);

        hash = hash64(id);
    }

    // expect a hash collision around 1 in 10B identifiers
    private void checkCollisionRate() {
        final long startTime = System.nanoTime();

        final int nPar = forkPool.getParallelism();

        final long hashSpace = 1_000_000_000_000L;

        final long rangeSize = hashSpace/nPar;
        for(long h=0L; h<hashSpace; h+= rangeSize) {
            final RecursiveAction action = new CheckCollisionsRecursiveAction(h, h+rangeSize);
            forkPool.execute(action);
        }

        while(forkPool.getActiveThreadCount() == 0) {
            Thread.yield();
        }

        long lastCount = 0;
        while(!foundCollision && forkPool.getActiveThreadCount() > 0) {
            if(lastCount < currentCount.get()) {
                lastCount = currentCount.get();
                final long runTime = System.nanoTime() - startTime;
                System.out.println(lastCount/1_000_000 + ", " + String.format("%10.2f", lastCount*1e9/runTime)+"/s");
            }

            try {
                Thread.sleep(250L);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        }

        if(!foundCollision) {
            System.out.println("Key space exhausted.  Try again.");
        }

        final long time = TimeUnit.SECONDS.convert(System.nanoTime() - startTime, TimeUnit.NANOSECONDS);
        System.out.println("Elapsed time: " + time + " s");

    }

    private String generateIdfa(final Random random) {
        final String l1 = Long.toHexString(getLong8Hex(random));
        final String l2 = Long.toHexString(getLong8Hex(random));
        final String l3 = Long.toHexString(getLong8Hex(random));
        final String l4 = Long.toHexString(getLong8Hex(random));
        return new StringBuilder(40).append(l1).append('-').append(l2.substring(0, 4)).append('-').append(l2.substring(4, 8)).append('-').append(l3.substring(0, 4)).append('-').append(l3.substring(4, 8)).append(l4.substring(0, 8)).toString().toUpperCase();
    }

    private long getLong8Hex(final Random random) {
        final long minVal = 0x10000000L;
        long h = random.nextLong() & 0xffffffffffffffffL;
        while(h < minVal) {
            h = random.nextLong() & 0xffffffffffffffffL;
        }
        return h;
    }

    private long hash64(final String s) {
        long rv = FNV_64_INIT;
        final int n = s.length();
        for (int i = 0; i < n; i++) {
            rv *= FNV_64_PRIME;
            rv ^= s.charAt(i);
        }
        return rv;
    }

    private final class CheckCollisionsRecursiveAction extends RecursiveAction {

        public static final long CHUNK_COUNT = 1L<<20;
        public static final long RAND_COUNT = 1L<<10;

        final long xMin;
        final long xMax;

        private CheckCollisionsRecursiveAction(long xMin, long xMax) {
            this.xMin = xMin;
            this.xMax = xMax;
        }


        @Override
        protected void compute() {

            try {
                final Random random = new Random(secureRandom.nextLong());

                for (long i = xMin; !foundCollision && i < xMax; i++) {
                    final String a1 = generateIdfa(random);
                    final long l = hash64(a1);

                    if (hash == l) {
                        if (!id.equals(a1)) {
                            System.out.println("Collision found after " + i + " iterations.");
                            System.out.println(a1 + " collides with " + id + " at value " + l + "=" + hash);
                            foundCollision = true;
                            break;
                        }
                    }

                    final long count = i - xMin;
                    if (count > 0 && ((count & CHUNK_COUNT - 1) == 0)) {
                        currentCount.accumulate(CHUNK_COUNT);
                    }

                    if (count > 0 && ((count & RAND_COUNT - 1) == 0)) {
                        random.setSeed(secureRandom.nextLong());
                    }
                }
            } catch(final Throwable t) {
                System.out.println("Compute failed, unexpected exception.");
                t.printStackTrace(System.out);
            }
        }
    }
}