// Arup Guha
// 12/10/2015
// Solution for CIS 3362 Homework #5: Birthday Attack!

/***
  My first two strategies failed:

  I tried mapping ints to strings and trying those strings in order.
  Then I tried creating random words of a fixed length (5).

  In both these cases, I tried over 12,000,000 strings before running out of heap space.
  Then I tried words of random length. Every time I run the program, I find a pair, very, very
  quickly. Apparently, adding an 'f' to the end of strings of lengths not divisible by 6
  leaves the hash value unchanged - voila!!!
***/

import java.util.*;

public class hmk5 {

    public static void main(String[] args) {

        HashMap<Long,String> map = new HashMap<Long,String>();
        Random r = new Random();

        // Try a bunch of strings.
        for (int i=1; i<(1<<30); i++) {

            // Get this string's hash value.
            String s = str2(r, 1+r.nextInt(13));
            char[] chArray = s.toCharArray();
            long hashval = hashFunction(chArray);

            // Found a match!
            if (map.containsKey(hashval) && !s.equals(map.get(hashval))) {
                System.out.println(map.get(hashval)+" "+s);
                break;
            }

            if (i%1000000 == 0) System.out.println("just tried "+i);
            // Store in our map.
            map.put(hashval, s);
        }
    }

    public static String str2(Random r, int n) {
        char[] res = new char[n];
        for (int i=0; i<n; i++) {
            int num = r.nextInt(52);
            res[i] = num < 26 ? (char)('A'+num) : (char)('a'+num-26);
        }
        return new String(res);
    }
    public static String str(int val) {
        String s = "";
        while (val > 0) {
            s = s + (char)('A'+val%26);
            val /= 26;
        }
        return s;
    }

    // Pre-condition: input must be null terminated.
    public static long hashFunction(char[] input) {

        int i = 0, n = input.length;
        long buffer = 0x3f290785c16eL;
        while (i < n) {
            long temp = 0L;
            int j;
            for (j=0; j<6 && i+j<n; j++)
                temp += ( ( (long)(f((int)input[i+j])) ) << (40-8*j)  );
            i += 6;

            buffer = f2(buffer ^ temp);
        }
        return buffer;
    }

    // value must be 8 bits. Swaps the left and the right halves and runs
    // each through an s-box.
    public static int f(int value) {
        value = reverse(value);
        int left = (value & (0xf0)) >> 4;
        int right = value & (0xf);
        return (box(left) << 4) + box(right);
    }

    // value must be 8 bits. It's reverse (in binary) is returned.
    public static int reverse(int value) {
        int ans = 0, i;
        for (i=0; i<8; i++) {
            ans = (ans << 1) + (value & 1);
            value = value >> 1;
        }
        return ans;
    }

    // Random s-box of values.
    public static int box(int value) {
        int ans[] = {10, 8, 12, 9, 4, 15, 0, 6, 7, 2, 11, 13, 3, 14, 1, 5};
        return ans[value];
    }

    // A second random s-box of values.
    public static int box2(int value) {
        return (37*value)%64;
    }

    // A second function based on the sbox. Value is once again reversed, with
    // another substitution into a different sbox.
    public static long f2(long value) {

        int i;
        long ans = 0L;
        for (i=0; i<8; i++) {
            long index = value & 0x3f;
            if (index < 0) index += 64L;
            ans = (ans << 6)  + box2((int)index);
            value = value >> 6;
        }
        return ans;
    }

}