DES Brute Force (academic)

Question

I am taking a class in computer security, one of our assignments is to brute force DES that has a weak key.

My Code:

    public static void main(String[] args) throws Exception {
        String temp;
        String current;
        String plaintext;
        
        //Generate key for DES
        String initkey = "00000006";
        byte[] Rawkey = initkey.getBytes();
        DESKeySpec dks =  new DESKeySpec(Rawkey);
        SecretKeyFactory skf = SecretKeyFactory.getInstance("DES");
        SecretKey desKey = skf.generateSecret(dks);
        
        //Text Enc & Dec
        Cipher cipher = Cipher.getInstance("DES/ECB/PKCS5Padding");
        
        //Declare wether to enc or dec
        cipher.init(Cipher.ENCRYPT_MODE,desKey);
        byte []message = "Decrypted Successfully".getBytes();
        byte []messageEnc = cipher.doFinal(message);
        plaintext = new String(message);
        System.out.println("Cipher Text: " + new String(messageEnc) );

        for(int i=0;i<10;i++){
            try{
                temp = padLeftZeros(Integer.toString(i),8);
                System.out.println(temp);
                byte []RawkeyTest = temp.getBytes();
                DESKeySpec dksTest =  new DESKeySpec(RawkeyTest);
                SecretKeyFactory skf2 = SecretKeyFactory.getInstance("DES");
                SecretKey desKeyTest = skf2.generateSecret(dksTest);
                cipher.init(Cipher.DECRYPT_MODE,desKeyTest);
                byte []dec = cipher.doFinal(messageEnc);
                current = new String(dec);
                if(current.equals(plaintext)){
                    System.out.println("Decrypted Text: " + current);
                    System.out.println("");
                    //break;
                }
                
            }catch (BadPaddingException ex){
                System.out.println("Wrong Key.");
                System.out.println("");
            }
            
        }
   
    }

    public static String padLeftZeros(String inputString, int length) {
        if (inputString.length() >= length) {
            return inputString;
        }
        StringBuilder sb = new StringBuilder();
        while (sb.length() < length - inputString.length()) {
            sb.append('0');
        }
        sb.append(inputString);
    
        return sb.toString();
    }
}

Output

Cipher Text: �
B��4#Ǡ�`=Π��H�č:�
00000000
Wrong Key.

00000001
Wrong Key.

00000002
Wrong Key.

00000003
Wrong Key.

00000004
Wrong Key.

00000005
Wrong Key.

00000006
Decrypted Text: Decrypted Successfully

00000007
Decrypted Text: Decrypted Successfully

00000008
Wrong Key.

00000009
Wrong Key.

00000010
Wrong Key.

00000011
Wrong Key.

00000012
Wrong Key.

00000013
Wrong Key.

00000014
Wrong Key.

00000015
Wrong Key.

00000016
Decrypted Text: Decrypted Successfully

00000017
Decrypted Text: Decrypted Successfully

00000018
Wrong Key.

00000019
Wrong Key.

The key #6 is the only one that is supposed to decrypt successfully. So I don't understand why the keys: 7, 16, 17 works as well.

Any help or advice would be greatly appreciated. Thanks in advance.

Sheetfed

Weak key has a specific meaning in DES See NIST Special Publication 800-67 Revision 2, 3.3.2 Weak keys. It's unclear from your question whether you're brute forcing across the entire key space which would likely be out of the scope of a class assignment. Your results can't be duplicated without the actual values of the ciphertext (e.g. in hexadecimal). – Arrogant

Answer 1

There is no problem, actually, there is one.

DES normally uses 64-bit keys where the last bit (lsb) of each byte is a parity bit and that makes a total of 56 bits of cryptographic keys. The parity bits don't contribute to the key schedule. This is why we say DES has a 56-bit key size. They are discarded once the parity is checked. Each byte of the key must have odd parity. The library ignores the parity problem and doesn't provide an exception.

• 0x0...6 = 0x..0110 and 7=0x..0111. If you remove the right bit they are the same.

• 0x0..16 = 0x...0001 0110 and 17=0x...0001 0111. Now remove the last bits in each of the bytes, then the keys will be the same as 0x00000006

And note that none of the above keys are valid in terms of parity. If you want to check the parity or make your keys valid you can use the following Java code from Alejandro Revilla github

public static void adjustDESParity (byte[] bytes) {
    for (int i = 0; i < bytes.length; i++) {
        int b = bytes[i];
        bytes[i] = (byte)((b & 0xfe) | ((((b >> 1) ^ (b >> 2) ^ (b >> 3) ^ (b >> 4) ^ (b >> 5) ^ (b >> 6) ^ (b >> 7)) ^ 0x01) & 0x01));
    }
}

public static boolean isDESParityAdjusted (byte[] bytes) {
    byte[] correct = (byte[])bytes.clone();
    adjustDESParity(correct);
    return  Arrays.equals(bytes, correct);
}

---

If you are looking for the DES's weak keys then those are

0101 0101 0101 0101
1F1F 1F1F 0E0E 0E0E
E0E0 E0E0 F1F1 F1F1
FEFE FEFE FEFE FEFE

Acord

I understand why now, any ideas how to fix it and make the bits on the right not ignored? – Sheetfed

"There is no problem, actually, there is one." - Not sure what you are saying here :-) – Pyramid

@StephenC both :) It is not a problem if you know it, however, It is a problem since nobody uses the parity check. Well, it was designed for the old times. As we see, the libraries don't check either. It is not hard to write one that test and throw an exception but not cared. – Acord