Java AES Counter Mode Incrementing

Question

I've written a an encryption/decryption prototype with Java using sample code in this answer. However, I'm trying to play with AES' counter mode (CTR) and the encrypted values appear to be just as incrementable as the integer sequence that I'm trying to encrypt.

Consider the following output of my prototype:

i = 0: enc='5941F8', dec='000', length=6
i = 1: enc='5941F9', dec='001', length=6
i = 2: enc='5941FA', dec='002', length=6
i = 3: enc='5941FB', dec='003', length=6
i = 4: enc='5941FC', dec='004', length=6
i = 5: enc='5941FD', dec='005', length=6
i = 6: enc='5941FE', dec='006', length=6
i = 7: enc='5941FF', dec='007', length=6
i = 8: enc='5941F0', dec='008', length=6
i = 9: enc='5941F1', dec='009', length=6
i = 10: enc='5940F8', dec='010', length=6
i = 11: enc='5940F9', dec='011', length=6
i = 12: enc='5940FA', dec='012', length=6

Notice how the enc values usually only differ from the dec values by a single digit. Are encrypted values generated by AES' counter mode usually this iterable/similar to each other or am I doing something wrong?

So far, I have tried playing with different encryption keys, init vectors, padding schemes, longer/shorter integer sequences (starting from different values) etc. but nothing seems to work so far. Also, Google and other SO questions on the Java AES Cipher in Counter Mode have been of little use so far. Please bear in mind also that I'm a crypto newbie.

Code for my prototype is as follows:

public class Encryptor {
  public static String encrypt(String key, String initVector, String value) {
    try {
      IvParameterSpec iv = new IvParameterSpec(initVector.getBytes("UTF-8"));
      SecretKeySpec skeySpec = new SecretKeySpec(key.getBytes("UTF-8"), "AES");

      Cipher cipher = Cipher.getInstance("AES/CTR/PKCS5PADDING");
      cipher.init(Cipher.ENCRYPT_MODE, skeySpec, iv);

      byte[] encrypted = cipher.doFinal(value.getBytes());
      return DatatypeConverter.printHexBinary(encrypted);
    }
    catch (Exception ex) {
      throw new RuntimeException(ex);
    }
  }

  public static String decrypt(String key, String initVector, String encrypted) {
    try {
      IvParameterSpec iv = new IvParameterSpec(initVector.getBytes("UTF-8"));
      SecretKeySpec skeySpec = new SecretKeySpec(key.getBytes("UTF-8"), "AES");

      Cipher cipher = Cipher.getInstance("AES/CTR/PKCS5PADDING");
      cipher.init(Cipher.DECRYPT_MODE, skeySpec, iv);

      byte[] decrypted = cipher.doFinal(DatatypeConverter.parseHexBinary(encrypted));
      return new String(decrypted);
    }
    catch (Exception ex) {
      ex.printStackTrace();
    }

    return null;
  }

  public static void main(String[] args) {
    String key = "Bar12345Bar12345"; // 128 bit key
    String initVector = "RandomInitVector"; // 16 bytes IV

    System.out.println(decrypt(key, initVector,
        encrypt(key, initVector, "Hello World")));
    for (int i = 0; i < 1000; ++i) {
      String encrypted = encrypt(key, initVector, StringUtils.leftPad("" + i, 3, '0'));
      String decrypted = decrypt(key, initVector, encrypted);
      int encLen = encrypted.length();
      System.out.println("i = " + i + ": enc='" + encrypted + "', dec='" + decrypted + "', length=" + encLen);
    }
  }
}

Interestingly, I downvoted the answer you're linking to. You should too. Using the same IV in CBC mode is a problem, but it's a bigger problem in CTR mode, hence your question. — Artjom B., Apr 20 '17 at 19:42
Note my comment under the linked answer which should have prevented you from asking this question. Was I not clear enough of what should be done? — Artjom B., Apr 20 '17 at 20:28
Nope the answer was fine. I got better data when I took your advice. But your answer poses an interesting corollary problem. See comment below to your answer. — entpnerd, Apr 20 '17 at 20:33

Artjom B. · Accepted Answer · 2017-04-20T19:54:00.437

CTR mode is a streaming mode of operation. It means that a nonce and key pair creates a unique key stream which is then XORed with the plaintext. Since, XOR is symmetric, the exact same operation is applied to decrypt the ciphertext.

Now, XOR work bit-wise. If you use the same key and nonce pair for multiple encryptions, you will encrypt the plaintext with the exact same key stream every time. This means that the bit positions that are different between two plaintext will also be different when comparing the two resulting ciphertexts. This is called the two-time pad or the many-time pad.

In your example, if you XOR enc and dec for each iteration, you will always get 0x6971C8. Those are the first three bytes of the key stream. The ASCII character 0 is 0x30 which when XORed with 0x59 is 0x69 and so on.

The solution would be to use a different nonce (number used once) every time you encrypt with the same key. The nonce (sometimes called IV) is supposed to be smaller than the block size of the underlying block cipher. AES has a block size of 16 bytes. We generally choose random nonces with a length of 8 bytes or 12 bytes depending on how much data we want to encryption without a counter collision. A 12 byte nonce seems like the best compromise, because you can generate many random nonces without much of a chance of a collision and you can encrypt up to 68 GB with a key+nonce pair without a chance of a counter collision.

Your solution, works. Thanks very much. I basically used a similar version of my variable `i` as the initialization vector. However, this raises a larger issue for me than it solves. Am I correct in surmising that there really isn't a viable way to decrypt values that should be integers in some sequence? In order for decryption to work, I need to know the initialization vector. Thanks again! — entpnerd, Apr 20 '17 at 20:32
Yes and no, the nonce doesn't have to be chosen randomly, but it has to be different. For example, if there is a unique ID associated with the integer you want to encrypt, then you can simply use that ID as your nonce. If you don't want that, then there is always the possibility of using format-preserving encryption. Keep in mind that there are not many implementations of FPE. — Artjom B., Apr 20 '17 at 20:40
Warning: the IV is not a nonce, it's the initial counter value for CTR mode. The nonce should be e.g. the first (leftmost) 8 bytes of the IV, leaving the others empty as not to overlap counter values even when using a unique IV. This is not sufficiently clear from the answer — Maarten Bodewes, Apr 21 '17 at 01:34

Java AES Counter Mode Incrementing

1 Answers1