package cz.muni.fi.pv079.exercises02;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import org.apache.commons.codec.binary.Hex;

/**
 * Compute 72bit collision between two 72bit strings after application of SHA256
 * hash function
 * 
 * @author Tomas Sedmik, tomas.sedmik@gmail.com
 * @since 16. 10. 2012
 */
public class SHACollider72 {
    
    /**
     * Print binary data on the standard output in hexadecimal form
     * 
     * @param data binary data
     */
    private static void printHexString(byte[] data) {
        for (byte bytes : data) {
            String temp = Integer.toHexString(bytes & 0xFF);
            if (temp.length() == 1) {
                System.out.print("0" + temp + "-");
            } else {
                System.out.print(temp + "-");
            }
        }
        System.out.println();
    }
    
    /**
     * Method prints the collision strings on the standard output. 
     * 
     * @param first a first collision chain
     * @param second a second collison chain
     * @throws NoSuchAlgorithmException 
     */
    private static void printOrigin(Triplet first, Triplet second) throws NoSuchAlgorithmException {
        
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        
        List<Triplet> firstChain = new ArrayList<Triplet>();
        List<Triplet> secondChain = new ArrayList<Triplet>();
        
        // fill the first chain with data
        byte[] sp = first.getSp();
        for (int i = 0; i < first.getCounter(); i++) {
            md.reset();
            byte[] sphash = md.digest(sp);
            byte[] sphashsplit = new byte[9];
            System.arraycopy(sphash, 0, sphashsplit, 0, 9);
            firstChain.add(new Triplet(sp, sphashsplit, i));
            sp = sphashsplit;
        }
        
        // fill the second chain with data
        sp = second.getSp();
        for (int i = 0; i < second.getCounter(); i++) {
            md.reset();
            byte[] sphash = md.digest(sp);
            byte[] sphashsplit = new byte[9];
            System.arraycopy(sphash, 0, sphashsplit, 0, 9);
            secondChain.add(new Triplet(sp, sphashsplit, i));
            sp = sphashsplit;
        }
        
        // search for collision
        int chainLength = 0;
        if (firstChain.size() > secondChain.size()) {
            chainLength = secondChain.size();
        } else {
            chainLength = firstChain.size();
        }
        for (int i = 1; i < chainLength; i++) {
            
            // we search for two records with different starting points
            // we process the chains from the end to the begining
            if (!Arrays.equals(firstChain.get(firstChain.size() - i).getSp(), 
                    secondChain.get(secondChain.size() - i).getSp())) {
                
                printHexString(firstChain.get(firstChain.size() - i).getSp());
                md.reset();
                byte[] sphash = md.digest(firstChain.get(firstChain.size() - i).getSp());
                printHexString(sphash);
                
                printHexString(secondChain.get(secondChain.size() - i).getSp());
                md.reset();
                sphash = md.digest(secondChain.get(secondChain.size() - i).getSp());
                printHexString(sphash);
                
                return;
            }
        }
        
        // no solution (rerun program)
        System.out.println("No solution (rerun program)");
    }

    /**
     * Method find a corresponding triplet for a given triplet, print them and
     * call printOrigin method.
     * 
     * @param triplet triplet which is already stored (which means a collision)
     * @param triplets set of all stored triplets
     * @throws NoSuchAlgorithmException 
     */
    private static void printResults(Triplet triplet, Set<Triplet> triplets) throws NoSuchAlgorithmException {
        
        // print first triplet
        System.out.print("1st SP: ");
        printHexString(triplet.getSp());

        // search for second triplet with same output as first
        for (Triplet item : triplets) {

            if (triplet.equals(item)) {

                // print second triplet
                System.out.print("2nd SP: ");
                printHexString(item.getSp());
                System.out.println("1st counter: " + triplet.getCounter());
                System.out.println("2nd counter: " + item.getCounter());
                System.out.print("hash: ");
                printHexString(item.getOutput());
                System.out.println("Triplets: " + triplets.size());
                System.out.println();
                
                // find collision strings
                printOrigin(triplet, item);
            }
        }
    }

    public static void main(String[] args) throws Exception {

        // generate a first random 72bit binary string
        SecureRandom random = new SecureRandom();
        byte[] sp = new byte[9];
        random.nextBytes(sp);

        // hashing
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        byte[] sphash = md.digest(sp);

        // processing
        Set<Triplet> triplets = new HashSet<Triplet>();
        long counter = 0;

        while (true) {

            counter++;

            // get 72 bits from hash
            byte[] sphashsplit = new byte[9];
            System.arraycopy(sphash, 0, sphashsplit, 0, 9);

            // check if 17 most significant bits equal to zeros
            byte[] temp = new byte[3];
            byte[] zeros = new byte[]{0x00, 0x00, 0x00};
            System.arraycopy(sphash, 0, temp, 0, 3);            
            String maskString = "000080";
            byte[] mask = Hex.decodeHex(maskString.toCharArray());
            temp[2] = (byte) (temp[2] & mask[2]);
            
            if (Arrays.equals(temp, zeros)) {
                
                System.out.println(triplets.size());
                
                // create a new triplet
                byte[] tempSp = new byte[9];
                System.arraycopy(sp, 0, tempSp, 0, 9);
                Triplet triplet = new Triplet(tempSp, sphashsplit, counter);

                // we found a match (same outputs)                
                if (triplets.contains(triplet)) {

                    // print out a results and exit
                    printResults(triplet, triplets);
                    System.exit(0);
                }

                // store triplet
                triplets.add(triplet);

                // generate a new starting point
                random.nextBytes(sp);
                md.reset();
                sphash = md.digest(sp);
                counter = 0;
                continue;
            }

            // get 72 bits from hash and use it as a new starting point (chaining)            
            md.reset();
            sphash = md.digest(sphashsplit);
        }
    }
}