Java AES Counter Mode Incrementing

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);
    }
  }
}

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.