6 Replies Latest reply: Dec 21, 2012 2:05 AM by Kayaman RSS

    PBKDF2WithHmacSHA1 Java speed up?

    980860
      Hello everyone. I'm making model in Java that is able to calculate keys used in WPA/WPA2 protocol. So, model is able to calculate Pairwise Master Key from given "password" and "salt", than calculate Pairwise Transient Key and Eapol hmac. For calculating PMK, "PBKDF2WithHmacSHA1" is used. Every call of that function is extremely slow, and because final idea for this model is to be used in distributed computing environment for testing all possible keys (brute-force) attack I can't accept this slowness of function.

      For example, with this code, I'm able to calculate ~56 keys per second and slowest part is PBKDF2WithHmacSHA. And for comparation, program used for same thing on linux (aircrack-ng), written in C, on same computer is able to calculate over 1000 keys per second! Am i mistaking somewhere? Could I implement this in some way that it is going to work faster? Yes, there are 4096 iterations, that's how WPA works. Maybe If I somehow write this method differently it will work faster?
      Here is example:

      import java.security.NoSuchAlgorithmException;
      import java.security.spec.InvalidKeySpecException;
      import java.security.spec.KeySpec;
      import javax.crypto.SecretKeyFactory;
      import javax.crypto.spec.PBEKeySpec;

      public class temp {
      static String pmkAlgorithm = "PBKDF2WithHmacSHA1";
      static int pmkLength = 256;
      static int pmkIterations = 4096;
      static byte[] pmk = new byte[32];

      //-------- PMK --------
      public static byte[] calculatePmk(char[] password, byte[] salt) throws NoSuchAlgorithmException, InvalidKeySpecException {
      KeySpec spec = new PBEKeySpec(password, salt, pmkIterations, pmkLength);
      SecretKeyFactory f = SecretKeyFactory.getInstance(pmkAlgorithm);
      return f.generateSecret(spec).getEncoded();
      }

      public static void main(String[] args) throws NoSuchAlgorithmException, InvalidKeySpecException{
      char[] password = "password".toCharArray();
      byte[] salt = "salt".getBytes();


      long t1 = System.currentTimeMillis();
      pmk = calculatePmk(password, salt);
      long t2 = System.currentTimeMillis();

      System.out.println(t2 - t1);
      }

      }

      Any ideas? THanks!
        • 1. Re: PBKDF2WithHmacSHA1 Java speed up?
          fxmatz
          Hi,
          this is a good example to compare the runtimes of C and JAVA ;-)
          On the client side you can also wrap the C-CryptLib with JNI and get so the speed of the C-Lib.

          In Oracle 11g you have a Java 1.6 JVM and you can load and run your demo on the database JVM.

          Regards,
          Friedhold.
          • 2. Re: PBKDF2WithHmacSHA1 Java speed up?
            980860
            So, Java is actually really that slow when it comes to calculating heavy functions and there is no way to speed up process with using only java?
            I'm still not some super Java programer so I didn't know about this wrapping of C Libraries into Java? I'll read more about that.

            I don't understand what you meant here?
            user12155310 wrote:
            In Oracle 11g you have a Java 1.6 JVM and you can load and run your demo on the database JVM.
            Thanks for fast answer :)
            • 3. Re: PBKDF2WithHmacSHA1 Java speed up?
              sabre150
              I'm not convinced JNI will help. I'm betting that the difference between a JNI and a pure Java solution is small since when Java uses JIT it is very close in speed to writing in C. I have even found situations where Java is faster than C especially when JNI is used because of the JNI overhead.

              The basic problem is that the PBKDF2WithHmacSHA1 algorithm is very very slow and since you are forced to use it you are pretty much stuffed.

              From the point of view of security making the key generation algorithm slow is a distinct advantage since, as you are finding, it makes brute force attacks more difficult!!!!!!!!!!!
              • 4. Re: PBKDF2WithHmacSHA1 Java speed up?
                Kayaman
                I would imagine the C implementation uses inline assembler code to use the most optimized opcodes available. I'm not sure if JIT is able to recognize complex enough structures to compile things into for example SSE3 instructions.
                • 5. Re: PBKDF2WithHmacSHA1 Java speed up?
                  sabre150
                  Kayaman wrote:
                  I would imagine the C implementation uses inline assembler code to use the most optimized opcodes available. I'm not sure if JIT is able to recognize complex enough structures to compile things into for example SSE3 instructions.
                  From memory the slowest part of that algorithm is the SHA1 which is used for each iteration in the iteration count. Maybe using inline assembler for just the SHA1 will be all that is needed to make a significant difference. We will have to see but I doubt it will make more than a factor of 2 difference.
                  • 6. Re: PBKDF2WithHmacSHA1 Java speed up?
                    Kayaman
                    sabre150 wrote:
                    I doubt it will make more than a factor of 2 difference.
                    Considering it was designed to be slow, that would seem likely.