How can I audit which type of Block Mode encryption is being used when no source code is available?

Question

Given that there are clear advantages to using some block modes of encryption over another, and I would like to ensure that all software used in the enterprise uses a certain "level" of security I'd like to issue a statement of assurance to my stakeholders that the most appropriate technology is being used. e.g.

Ban the following modes

• ECB, CBC, OFB

In favor of the following modes:

• CTR, EAX, GCM

The only way I know of auditing this type of policy (outside of the FIPS mode in GPO) is to observe and test the output of these ciphers is as intended.

Question

• What approaches could be taken to audit the ciphers being used when the sourcecode is unavailable?

• What prerequisites needed for each approach? (e.g. CPA ability, Private Key, IV, key length, block length, etc)

Although I'd like to keep this as simple as possible for auditing purposes, I'm also curious about the permutations of what information is needed (private key, IV, etc) so I can understand how easily an attacker can identify "weak" implementations that exist without that private information.

(note: I am willing to write the necessary statistical or encryption/decryption routines)

Answer 1

Testing for ECB / CBC / OFB / CTR mode is fairly straightforward. It's also straightforward to see if the mode has authenticated encryption like EAX / GCM (though it isn't straightforward to see which mode of AE).

• ECB: have a file with many similar blocks in the plaintext. Do you see identical blocks in the ciphertext? (Yes this is similar to Dan's answer, last part of Adnan's answer, but included for completeness).
• CBC: Encrypt a file, and then flip a bit in the IV (typically in the first block of the ciphertext); say you flipped the fifth bit of the first block. Do you see an identical flipped bit in the first block of the plaintext after decrypting? Similarly, flip a random bit later in the file say the 8th bit in the 10th block of the ciphertext. When you decrypt do you see the 10th block as gibberish, and then the 8th bit of the 11th block flipped? Again, consult the modes of operation diagram for CBC decryption and the reason should be clear.
• OFB/CTR: Test if you have a stream cipher. Without touching the IV / Random Nonce (typically the first block), if you alter a bit later in the ciphertext, do you see same bit flipped in the decrypted plaintext? If so you have a stream cipher; an important difference from CBC is in this case there's no gibberish block. I agree with CodesInChaos's comment that there's little security difference between OFB/CTR. If you have the encryption key¹ call it K, you could differentiate between OFB / CTR. E.g., let c[1], c[2] be the first and second block of ciphertext and p[1], p[2] be the first block of plaintext. Calculate D(K, c[1] XOR p[1]) and D(K, c[2] XOR p[2]), where D(K, c) is the decryption of block c with key K. If they are consecutive numbers, you have CTR mode. If D(K, c[2] XOR p[2]) = c[1] XOR p[1] then you have OFB mode.
• EAX/GCM - Both are authenticated encryption -- they contain a message authentication code (MAC) and the file will not decrypt (even to gibberish) if the file is altered as the MAC will not be valid with overwhelming probability.

Granted, a lot of this assumes things like you know the block size, but that should be easy to figure out. E.g., encrypt a very small (1 byte) message. Then assuming there's no MAC involved, you'll likely create a two block message (IV + one-block of padded ciphertext -- though CTR/OFB may not pad); then encrypt a longer message. From trial and error, you should be able to find out the block size and IV size.

EDIT: I definitely agree with the excellent point Thomas Pornin brought up. This sort of reverse engineering could help uncover the block cipher, but doesn't really test security. There are many backdoors that could have been covertly put in that you can't detect without painfully reverse engineering, by stepping through the assembly. For example, you could believe you have an Authenticated Encryption block cipher that can only be decrypted with your secret key constructed off your passphrase. But really the file is encrypted with a random key, that is itself encrypted at the beginning of the file using both your passphrase, and then once with their backdoor key. Thus, they would be able to decrypt any file you use. Or maybe the scheme does this same scheme, e.g., at the beginning of the file store the per-file-key to be decrypted using your secret key, but there's only about a billion or so keys (that they know all of them). Or maybe its encrypted with only your key, but the key derivation function only uses the first ~30 bits of the hash of your passphrase as your key. Hence, it could be very quickly brute forced with a billion attempts. Similarly, it doesn't have to be a deliberate backdoor; it could just be improper subtle implementation flaw allowing for side-channel ataacks.

¹ This was not assumed for other parts -- there are a lot of ways you could know to enter a passphrase to the decryption system, but not know the key derivation function (or encryption function) used internally to generated the key.

Answer 2

@dr jimbob gives the right answers as to the detection of the block cipher modes. I would like to complement that with another view of the question; namely: if you cannot know what algorithm is used with what mode of operation and what format, from the product documentation alone, then the product should not be used. Generally speaking, security cannot be tested; so we have to resort to the next best thing, which is trying to make sure that the product was designed and implemented with all due care and following best practices and established standards. This calls for extensive documentation and transparency. A big part of "best practices" is to document what you do. If the product uses encryption for your data but does not say how it does it, then you already know that it is sub-standard for the documentation part. It is thus safest to assume that the product is sloppy, and not use it.

Another, unrelated point is that trying to determine how things work within a given product constitutes reverse engineering and that could be illegal, depending on the country you live and/or work in. If it is illegal, then you should refrain from it, and instead insist on proper documentation. If it is legal, then some decompilation or disassembly will often offer a more precise view of what the product does, including type of algorithm and encryption mode. This approach complements the tests suggested by @dr jimbob.

Answer 3

Since you're trying to find the chaining mode, I'm assuming you already know the encryption algorithm and the encryption key.

The easiest solution I can think of is to define a plaintext then give it to your encryption black box and get the ciphertext. Then write a script that will independently decrypt the ciphertext using all the finite number of available chaining modes then compare the result to your plaintext. Whichever produces a match, BINGO!

Another way is to define a plaintext, encrypt it with all available chaining modes then compare the ciphertext to the output of your encryption black box for the same plaintext.

Auditing for ECB is a bit more fun. Define your plaintext to have identical blocks (16 byte blocks for AES) and watch the output for identical 16-byte blocks of ciphertext. This method doesn't require the knowledge of the key.

Answer 4

ECB, at least, is easy to detect as long as you can request the encrypted version of chosen plaintexts.

Simply compare the encryption of 0000000000000000000000... and 1000000000000000000000..., making sure your plaintexts are long enough to span a few blocks.

If ECB is in use the ciphertexts will differ only in the first block - later blocks will be identical. This is because ECB encrypts each block in isolation. If some other (propagating) mode is in use, the two ciphertexts will, with high probability, differ in all blocks. This is because the difference in the first block is incorporated into subsequent blocks.

Note that you do not need knowledge of the encryption key to achieve this.