Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement