ADDITIONAL SYSTEM INFORMATION :
Tested on Linux, Mac, Java 11, 17, 19
A DESCRIPTION OF THE PROBLEM :
The title pretty much sums up the issue, the runtime of GCM decryption is O(n²) with respect to the size of the input.
issue was also described https://stackoverflow.com/questions/74575538/why-is-the-runtime-complexity-of-gcm-mode-encryption-on²-in-java
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Looking at the code, it is buffering all input before it would push it out, but that should be (at worst) O(lg(n)) as the buffer doubles in size each time to copy the input bytes.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
That the runtime of the decrypt would be linear with respect to the size of the input, that is, doubling the size of the input should take roughly double the time to decrypt.
ACTUAL -
On my machine, this gives:
```
*** Run 3 ***
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE Size=1M Encrypted=13ms Decrypted1=91ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE Size=2M Encrypted=25ms Decrypted1=236ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE Size=4M Encrypted=56ms Decrypted1=854ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE Size=8M Encrypted=104ms Decrypted1=3552ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE Size=16M Encrypted=202ms Decrypted1=13896ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE Size=32M Encrypted=394ms Decrypted1=53576ms result1=true
```
The O(n²) runtime of the decrypt is quite clear to see!
---------- BEGIN SOURCE ----------
import java.io.BufferedInputStream;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.function.BiFunction;
import java.util.function.Function;
import javax.crypto.Cipher;
import javax.crypto.CipherInputStream;
import javax.crypto.CipherOutputStream;
import javax.crypto.spec.GCMParameterSpec;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.SecretKeySpec;
public class AES_Test {
public static void main(String[] args) throws Exception {
Random r = new Random();
byte[] key = new byte[32];
byte[] spec = new byte[12];
byte[] iv = new byte[16];
r.nextBytes(key);
r.nextBytes(spec);
r.nextBytes(iv);
List<BiFunction<Integer, SecretKeySpec, Cipher>> cipherCreators = List.of(
(mode, serverKey) -> {
GCMParameterSpec eGcmParameterSpec = new GCMParameterSpec(16 * 8, spec);
try
{
Cipher eCipher = Cipher.getInstance("AES/GCM/NoPadding");
eCipher.init(mode, serverKey, eGcmParameterSpec);
return eCipher;
} catch (Exception e) {
throw new RuntimeException(e);
}
},
(mode, serverKey) -> {
IvParameterSpec ivSpec = new IvParameterSpec(iv);
Cipher eCipher;
try {
eCipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
eCipher.init(mode, serverKey, ivSpec);
} catch (Exception e) {
throw new RuntimeException(e);
}
return eCipher;
},
(mode, serverKey) -> {
IvParameterSpec ivSpec = new IvParameterSpec(iv);
Cipher eCipher;
try {
eCipher = Cipher.getInstance("AES/CTR/NoPadding");
eCipher.init(mode, serverKey, ivSpec);
} catch (Exception e) {
throw new RuntimeException(e);
}
return eCipher;
},
(mode, serverKey) -> {
IvParameterSpec ivSpec = new IvParameterSpec(iv);
Cipher eCipher;
try {
eCipher = Cipher.getInstance("AES/CTS/NoPadding");
eCipher.init(mode, serverKey, ivSpec);
} catch (Exception e) {
throw new RuntimeException(e);
}
return eCipher;
}
);
SecretKeySpec serverKey = new SecretKeySpec(key, "AES");
GCMParameterSpec gcmParameterSpec = new GCMParameterSpec(16 * 8, spec);
for (int j = 0; j < 3; j++) {
System.out.println("*** Run " + (j + 1) + " ***");
for (BiFunction<Integer, SecretKeySpec, Cipher> cipherCreator : cipherCreators) {
for (int i = 1; i <= 32; i *= 2) {
byte[] randomBytes = new byte[i * 1024 * 1024];
r.nextBytes(randomBytes);
long start = System.currentTimeMillis();
// Encrypt
ByteArrayOutputStream bout = new ByteArrayOutputStream(randomBytes.length);
{
Cipher encryptCipher = cipherCreator.apply(Cipher.ENCRYPT_MODE, serverKey);
ByteArrayInputStream fin = new ByteArrayInputStream(randomBytes);
OutputStream cout = new CipherOutputStream(bout, encryptCipher);
fin.transferTo(cout);
cout.close();
}
byte[] encBytes = bout.toByteArray();
long encrypted = System.currentTimeMillis();
// Decrypt
{
InputStream fin = new ByteArrayInputStream(encBytes);
Cipher decryptCipher = cipherCreator.apply(Cipher.DECRYPT_MODE, serverKey);
InputStream cin = new CipherInputStream(fin, decryptCipher);
bout = new ByteArrayOutputStream(randomBytes.length);
cin.transferTo(bout);
}
long decrypted = System.currentTimeMillis();
System.out.println(cipherCreator.apply(Cipher.ENCRYPT_MODE, serverKey).toString() + " Size=" + i + "M Encrypted=" + (encrypted - start) + "ms Decrypted1=" + (decrypted - encrypted) + "ms result1=" + Arrays.equals(randomBytes, bout.toByteArray()));
}
}
}
}
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
It is something specific to the JDK implementation, since Bouncycastle does not exhibit this behaviour:
```
*** Run 3 ***
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC Size=1M Encrypted=15ms Decrypted1=16ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC Size=2M Encrypted=28ms Decrypted1=30ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC Size=4M Encrypted=51ms Decrypted1=59ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC Size=8M Encrypted=111ms Decrypted1=124ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC Size=16M Encrypted=196ms Decrypted1=222ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC Size=32M Encrypted=362ms Decrypted1=443ms result1=true
```
FREQUENCY : always