Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Consider that you stumble upon 5 different AES output strings. One of these strings can be decrypted with a secret phrase, the other four strings are based on the real string but have had random parts of it replaced (and thus can no longer be decrypted).

Without knowing anything else about these strings, or their contents, could it be possible to determine that one of the five strings could actually be decrypted? Or would they all be random data without a key to test the strings against?

share|improve this question
    
I'm not sure what you mean by "can be decrypted with a secret phrase". Regardless, assuming AES is secure and assuming that it's used correctly (i.e. with a proper mode of operation), ciphertexts shouldn't reveal any information (extractable in polynomial time) about the plaintexts. So, they should all be computationally indistinguishable from random. –  Reid Dec 28 '13 at 0:10
    
I meant that one of the strings was actually legitimate while the others were similar obfuscated versions. Would it be possible to determine the difference between a ciphertext that can be decrypted and other ciphertexts that have been partially randomized, based on the original ciphertext that can be decrypted? –  Howard Butler Dec 28 '13 at 6:14
    
I believe Reid answered that. “So, they should all be computationally indistinguishable from random.” That implies they are not in computationally distinguishable groups themselves, such as “AES encrypted version of ASCII text that was for whatever reason not compressed first.” –  Christopher Creutzig Dec 28 '13 at 10:53

1 Answer 1

Your question is misguided. Depending on your mode of operation, all five of those strings can still potentially be decrypted. To what, though, depends on the mode of operation.

AES, at its core, is a pseudorandom permutation that transforms a 128-bit input to a 128-bit output, given some key (128, 192, or 256 bits). Since the input size is equal to the output size and AES is reversible, this guarantees that all outputs map to some input given a particular key.

Modes of operation can affect this, however.

Given some modes, like CTR mode, a change to a single byte of the ciphertext will "randomly" permute that byte and only that byte in the plaintext. This is likely trivially bypassable (e.g., attack at dawn becomes at\u034ack at dawn).

In CBC mode, PKCS7 padding is used, and its value is checked for validity upon decryption. There's slightly over a $\frac{1}{256}$ chance of a random byte change corresponding to a valid padding, in which case the ciphertext will still decrypt. In this event, only the modified block will be "randomly" permuted, and later blocks will be mostly unchanged. In those later blocks, only bytes in the same position as the bytes modified in the earlier block will be changed, and they will be XORed by the same value that was used to change the originally-modified byte. This is likely trivially bypassable as well; the recipient can use this information to determine which byte was modified, and how, and then undo it and decrypt again.

In the event that valid padding was not produced, the decryption will "fail" in most software. This failure, however, is completely bypassable by a party with the correct key; they will in most cases simply have some extra padding on the end that needs to be stripped off manually.

I am unfamiliar with how byte errors will affect authenticated modes like GCM, EAX, and CCM. They will certainly fail to decrypt, as the authentication tag won't match. However, it may be possible for someone to bypass the authentication and decrypt the contents in a manner similar to the above.

TL;DR: Flipping bits in encrypted strings probably doesn't have the effect you think it does. In many cases, it does not render the plaintext irretrievable or unrecognizable. In many cases, it only slightly permutes the plaintext. In many cases, it only garbles a limited amount of plaintext. And at the worst case, a bit flip only requires an attacker to flip $len(ciphertext)$ bits before they come across the original plaintext. Your best bet is to simply not hand out cryptographic keys to people who shouldn't be able to decrypt the protected ciphertexts.

share|improve this answer
    
Yes you're right, all five strings can be decrypted even if they are random data, even though I hadn't considered that. But I said if nothing else is known about the strings (their cryptographic keys) or their contents. Basically I'm curious if you took a look at these output strings: "U2FsdGVkX1/v35Ju4ZYa/2Kq3+I3kDvBrvb5ojlKLSo=" and "U2F234VkX13v3534234a22Kq37I3kDvBrvb5ojlKLSo0" and "6fF2dGVkf1kv35Ju4ZYa52Kq3fI3kDfBrvg5ojsKLSb=" if it's possible to tell from the strings alone which are an output of encryption (first string above) and which are randomly obfuscated versions of the 1st string. –  Howard Butler Dec 28 '13 at 6:26
    
Because in essence I'm wondering if you were to throw in 1,000 obfuscated ciphertexts with the ciphertext you're trying to hide, if that would harden the task of trying to brute-force all ciphers (without going straight to the legitimate ciphertext and starting to brute-force that one first). Obviously AES 256 can't be brute-forced now, but I'm curious if this obfuscation would do any good in the off-chance that brute-force becomes a possibility. –  Howard Butler Dec 28 '13 at 6:30
    
You've missed the point of my comment entirely. 1. All of those strings are all actual outputs of AES given some input, regardless of the encryption key. 2. Depending on the encryption mode, your manipulated strings are extremely likely to contain enough information to reconstruct the plaintext, if the attacker has the key. If the attacker doesn't have the key, what threat are you trying to protect against? –  Stephen Touset Dec 28 '13 at 8:40
1  
Although in your particular example, the second example is very highly unlikely to be the legitimate output — your data is encoded in Base64, and by changing the strings you have inadvertently changed the length of the decoded string from 32 bytes to 33 bytes (= characters are used as padding in Base64). This has nothing to do with the encryption itself, however, for which my above comments remain true. –  Stephen Touset Dec 28 '13 at 8:48
    
Brute force will not be an effective attack against AES in any of our lifetimes, if ever. $2^{128}$ is a number which is much larger than you are giving it credit for. –  Stephen Touset Jan 1 at 0:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.