package cz.muni.fi.pv079.exercises03;

import java.security.Key;
import java.util.Arrays;
import javax.crypto.Cipher;
import javax.crypto.spec.SecretKeySpec;
import org.apache.commons.codec.DecoderException;
import org.apache.commons.codec.binary.Hex;

/**
 * Class show how to crack MS-CHAPv2 protocol. The method is based on the article
 * https://www.cloudcracker.com/blog/2012/07/29/cracking-ms-chap-v2/
 * 
 * @author Tomas Sedmik, tomas.sedmik@gmail.com
 * @since 2012-10-23
 */
public class MSCHAPv2Cracker {

    /**
     * Print binary data on the standard output in hexadecimal form
     * 
     * @param data binary data
     */
    private static void printHexString(byte[] data) {

        if (data != null) {
            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 increment byte array
     * 
     * @param array input array
     * @param index which byte should be increment
     */
    private static void incrementAtIndex(byte[] array, int index) throws DecoderException {
        byte[] temp = Hex.decodeHex("10101010101010".toCharArray());
        if (array[index] == temp[index]) {
            array[index] = 0;
            if (index > 0) {
                incrementAtIndex(array, index - 1);
            }
        } else {
            array[index]++;
        }
    }

    // Takes a 7-byte quantity and returns a valid 8-byte DES key.
    // The input and output bytes are big-endian, where the most significant
    // byte is in element 0.
    // taken from http://www.exampledepot.com/egs/javax.crypto/MakeDes.html
    public static byte[] addParity(byte[] in) {
        byte[] result = new byte[8];

        // Keeps track of the bit position in the result
        int resultIx = 1;

        // Used to keep track of the number of 1 bits in each 7-bit chunk
        int bitCount = 0;

        // Process each of the 56 bits
        for (int i = 0; i < 56; i++) {
            // Get the bit at bit position i
            boolean bit = (in[6 - i / 8] & (1 << (i % 8))) > 0;

            // If set, set the corresponding bit in the result
            if (bit) {
                result[7 - resultIx / 8] |= (1 << (resultIx % 8)) & 0xFF;
                bitCount++;
            }

            // Set the parity bit after every 7 bits
            if ((i + 1) % 7 == 0) {
                if (bitCount % 2 == 0) {
                    // Set low-order bit (parity bit) if bit count is even
                    result[7 - resultIx / 8] |= 1;
                }
                resultIx++;
                bitCount = 0;
            }
            resultIx++;
        }
        return result;
    }

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

        byte[] challengeHash = Hex.decodeHex("1234567890abcdef".toCharArray());

        // ChallengeResponse divided into three parts (ciperhtext1..3)
        byte[] ciphertext1 = Hex.decodeHex("02673e6d0153e574".toCharArray());
        byte[] ciphertext2 = Hex.decodeHex("be19c6582dbcacb9".toCharArray());
        byte[] ciphertext3 = Hex.decodeHex("bb8f29c87d60c990".toCharArray());

        // keys 
        byte[] keyOne = null;
        byte[] keyTwo = null;
        byte[] keyThree = null;
        byte[] NTHash1 = null;
        byte[] NTHash2 = null;
        byte[] NTHash3 = null;

        // find third key
        // only two bytes are non zero
        // every odd bit is equal to 1
        // => there are only 256 possibilities (4bits in each byte)
        byte counter = 0x00;
        for (int i = 0; i < 256; i++) {

            // create key in form 10101010 10101010 00000000 ...
            byte[] key = Hex.decodeHex("aaaa0000000000".toCharArray());

            // compute key
            byte mask = 1;
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 4; k++) {
                    if ((byte) (counter & mask) == mask) {
                        key[j] = (byte) (key[j] | (1 << k * 2));
                    }
                    mask = (byte) (mask << 1);
                }
            }

            // add parity to the key
            byte[] keyWithParity = addParity(key);

            // initialize DES
            Cipher cipher = Cipher.getInstance("DES/ECB/NOPADDING");
            Key keyDES = new SecretKeySpec(keyWithParity, "DES");
            cipher.init(Cipher.ENCRYPT_MODE, keyDES);
            
            // encrypt challengeHash
            byte[] result = cipher.doFinal(challengeHash);

            // if we find a match, save third keys
            if (Arrays.equals(result, ciphertext3)) {
                keyThree = keyWithParity;
                NTHash3 = key;
                break;
            }

            counter++;
        }

        // find first and second key
        // one bit in each byte is parity bit
        // every odd bit is equal to 1
        // => there are only 2ˆ28 posibilities (4bits in each byte - 7 bytes)
        byte[] count = new byte[] {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
        for (long i = 0; i < 268435456; i++) {
            
            if (i % 1000000 == 0) {
                System.out.println(i / 1000000);
            }

            // create key in form 10101010 10101010 ...
            byte[] key = Hex.decodeHex("aaaaaaaaaaaaaa".toCharArray());

            // compute key
            byte[] mask = new byte[] {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01};
            for (int j = 6; j >= 0; j--) {
                for (int k = 0; k < 4; k++) {
                    
                    if ((mask[j] != 0) && ((byte) (count[j] & mask[j]) == mask[j])) {
                        key[j] = (byte) (key[j] | (1 << k * 2));
                    }
                    
                    // mask shift
                    for (int l = 0; l < 7; l++) {
                        if (mask[6-l] != 0) {
                            if (mask[6-l] == 8 && l != 6) {
                                mask[6-l-1] = 0x01;
                                mask[6-l] = 0;
                                break;
                            } else {
                                mask[6-l] = (byte) (mask[6-l] << 1);
                            }       
                        }
                    }        
                }
            }         
            
            // add parity to the key
            byte[] keyWithParity = addParity(key);

            // initialize DES
            Cipher cipher = Cipher.getInstance("DES/ECB/NOPADDING");
            Key keyDES = new SecretKeySpec(keyWithParity, "DES");
            cipher.init(Cipher.ENCRYPT_MODE, keyDES);
            
            // encrypt challengeHash
            byte[] result = cipher.doFinal(challengeHash);

            // if we find a match, save keys
            if (Arrays.equals(result, ciphertext1)) {
                keyOne = keyWithParity;
                NTHash1 = key;
            }
            if (Arrays.equals(result, ciphertext2)) {
                keyTwo = keyWithParity;
                NTHash2 = key;
            }
            if (keyOne != null && keyTwo != null) {
                break;
            }
            
            // increment counter
            incrementAtIndex(count, 6);
        }

        // print results
        System.out.print("1st DES key: ");
        printHexString(keyOne);
        System.out.print("2nd DES key: ");
        printHexString(keyTwo);
        System.out.print("3th DES key: ");
        printHexString(keyThree);
        System.out.println("NTHash: ");
        printHexString(NTHash1);
        printHexString(NTHash2);
        printHexString(NTHash3);
    }
}