How to check a file was encrypted (really & correctly)

Question

I would like to audit how an implementation of an encryption algorithm is really performed with the following given data of the problem:

• the encryption mechanism is reversible (this isn’t a signature),
• the algorithm is pretended to be AES, but might be implemented correctly or not, or worse something else,
• the key is not known (in the case I am interested in, I want to check that all files are really and correctly encrypted, but I could play with specifically designed ones),
• I don't have access to the source code.

At least I would like to be able to detect that the file is not encrypted. Next I would like to be able to detect that the RNG is running in a tiny set or not really random.

In a first approach I thought to make an analysis of the randomness quality of the encrypted file: average value + standard deviation (with a tool like ent). But I immediatly thought of artificial files with a perfect average value and standard deviation which are perfectly regular and not the result of any encryption. Then my first approach is wrong.

The environment in which I will make this audit is a Unix one. ( I cannot use tools or algorithms I cannot read, compile and check myself. )

---

Practical case:

1. I would like to check that my iPhone is correctly encrypted and what is the AES key derived from either a constant, my password, a hardware uniq identifier.

2. I would like to perform the same validation of an iPhone of any staff member which will ask me to make the same validation for his professionnal iPhone. This is a service toward users to provide them trust in what they think is encrypted and has to be.

Answer 1

If you can't get access to the key for at least some sample uses, there's no way to be sure. For example, it's impossible to distinguish AES-128 from AES-256 if you don't have access to the key. That's true of any encryption method: without knowing the key, you can't distinguish the ciphertext from random data of the same length.

A professional auditor would normally get access to some test keys, if they can't normally access those keys through some administration interface.

You can make a statistical test, but all this will tell you is that the encryption is not completely botched or skipped.

If your vendor is not completely dishonest and they claim to have used AES, they probably did use AES. A far more common problem than not using AES is using AES wrong. Here too, you can't be sure that they got it right, but you can at least check for some common problems.

Check how the length of the ciphertext varies depending on the length of the plaintext. The ciphertext should include an initialization vector and an authentication tag, each of which normally adds 16 bytes. If the ciphertext is not 32 bytes larger than the plaintext, something is probably wrong, but there are cases where it can be ok (e.g. for disk encryption where the sector number is used to build unique IVs and no threat requires authentication).

Pass the same inputs in different conditions and make sure that the resulting ciphertexts are completely different. If you can arrange to encrypt multiple messages with the same key, make sure that identical messages result in completely different ciphertexts. This validates that initialization vectors are generated, if not correctly, then at least non-stupidly.

If there's a way for you to submit modified ciphertexts, do that and check that they are rejected with a generic “invalid ciphertext” error, rather than a specific error due to invalid content. This validates that authenticated encryption is used. There are threat models where it's ok not to have authentication, but you need to tread very carefully.

Two things that you definitely cannot know by looking at the output is whether the keys are generated and stored securely. (As opposed to e.g. using a non-cryptographic random generator to generate keys, and writing a copy of the secret keys to an unprotected location.) You can only audit this by looking at the behavior of the system.

Answer 2

Unless the file has a plaintext header which indicates that it has been encrypted, there is no way to distinguish ciphertext from uniform random data. You can heuristically guess that a file is encrypted if it has absolutely no structure and appears completely random, but you cannot definitively prove it.

Any cipher whose output could be distinguished from random would be considered broken.

Answer 3

In addition to what the other answers have stated, "proper" encryption using AES-256 (block mode choice aside) can still allow backdoors, such as by maliciously choosing IVs/nonces. Phil Rogaway and others discuss this in more detail in their paper "Security of Symmetric Encryption against Mass Surveillance" (abstract available here).

Answer 4

This question is very easy to answer:

The implementation isn't correct and you absolutely should not use it. Any other attitude towards this black box is hopelessly attackable.

Your stance should be: "I must be able to see the source, audit the source, and build the source myself into a binary". Anything short of that is irresponsible on your part. Do not accept the insecure half-measures proposed in the other answers.

You do not need to demand access to the keys used to do the encryption, but you absolutely must be able to verify that the algorithm is correct, and this simply cannot be correctly done only by observing its inputs and outputs. This is not even restricted to encryption -- any program can have a backdoor input that does something nasty and is essentially impossible to discover just by external experimentation -- but its consequences to you are much higher for cryptographic primitives than for other pieces of noncritical software.

Answer 5

If you're wondering about the iPhone's encryption specifically, then this work may have already been done for you. Many Apple/iPhone products have passed formal FIPS 140-2 certification, which does extensive tests on the sorts of things that you're concerned about. If you want to see details about which products have been certified for which algorithms/key sizes, go to NIST's CMVP website and search for vendor "Apple". Apple also has details on their website about the security certifications they've completed on various products.

FIPS 140-2 focuses on the cryptographic module by itself, things like the algorithm implementations or key management practices. This would be enough to show that the random number generator is sufficiently random, or that what they claim is AES really is true AES.

What this doesn't cover is how they use the crypto engine (i.e., did the filesystem really encrypt this particular file). Testing this yourself will be difficult on a mobile device since you can't (for instance) transplant the hard drive to a different system to read the raw data and check for plaintext. Apple's certification page lists a number of additional certifications that I'm not too familiar with. I'd recommend taking a look at those certification programs and seeing if any of them cover the sorts of tests you're wanting to do. After all, companies like Apple spend a lot of time and money going through these certification processes so that you don't have to do tests like these yourself.

Answer 6

Many answers have pointed out that what you seek to do is not possible. Proving that something is encrypted with key X is not possible without having key X and a signature for what was encrypted. If it were possible, then the encryption algorithm would be a faulty one. AES does not fit that bill.

However, if you are really in a bind, where management has told you that you must do this, despite proof that you cannot, there is a solution. Disassemble and reverse engineer the encryption implementation, and confirm by your own eyes that that particular set of bits, when executed as a Unix executable, properly encrypts the data. It's a horrible task, but it's infinitely more doable than proving what cannot be proven.

Beyond that, one step you might try is to develop a threat model. For instance, if you can assume that all files are encrypted in the same way as your test files, you can at least make some statements by inspecting the results of encrypting some known plaintext.

Answer 7

Have you got a reference set some plain text versions of these files at all? A representative set of 10,000 files, large and small, from 1 kb to 1 GB could be passed through the system. Measurements can be taken. , that you could trial encrypt with this cypher, albeit a freshly made new key. See if you can correlate the file sizes probably match to 4KB or 64 KB blocks etc.

Why do you want to audit the 'encryptability' of this enterprise if you say you collectively do not have the master key? Or perhaps does the key exist beyond your reach in someplace? If so, you can arrange proofs to be made from it.

Knowing exactly how long it takes to run down to the CPU cycle can be extremely useful. Maybe you could simulate the processing in virtualbox and run it in slow motion to get a feel for the amount of floating point ops is happening. Maybe try to mount a side-channel attack on the CPU cache and memory controller etc.

It's probably running on AES hardware, with unique boot parameters. For example, the number of cycles to re-hash; or the values of some initial prime numbers etc. After that it's running on the AES hardware. This technique would sure make it a bunch harder cos if you stumble on the right key it might actually not work in time to notice etc.

I think generally speaking, you seek a ZK proof - a zero knowledge proof. That is some cool mathematics right there. Allows one to verify a maths operation but not really know whats going on.