Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I have 2 questions that are somewhat related: 1. When you try and guess the key in a program (in a brute force way), how does the program know if it got it right and it had deciphered the message (I'm not talking about the obvious files with headers, but just a long string of text)? 2. What is the problem with cascade encryption/multiple encryption? If the only way to answer question 1 is to use something like a language processor, then aren't all multiple encryptions unbreakable using brute force methods?

Thanks.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

For multiple encryption, there was a previous question: Is multiple encryption a good idea?

As to how do you know if you decrypt it correctly -- usually you look at the output and decide if it makes sense. E.g., does it have the file format of a gif/jpeg/zip file? If it was plaintext does is it all ASCII or properly encoded UTF-8? Ignoring non-ASCII code-points, only 96 of the 256 possible values of a byte are printable. So if you decrypted garbage message with the wrong key and the message was 1000 characters long, the chance that all of them are printable ASCII letters by random chance will only be (96/256)1000 or about 1 in 10400. Even allowing UTF-8 the characters have to be in certain combinations; e.g., if the first byte is of the form 1110xxxx (where each x could be either a 1 or 0), that means the next two characters both need to be the form 10xxxxxx to be proper unicode). These sorts of things rarely happen by chance.

There's also often padding (that needs a certain form in the plaintext), checksums, or Message Authentication Codes that help distinguish garbage data from the wrong key, from actual data.


EDIT: If you encrypted a file twice with two different (symmetric) keys k1 and k2 and you tried decrypting c=E(k1, E'(k2, m)), there isn't a way you could just brute-force guess k1 by just examining the output of D(k1', c), which will appear random for any pattern. You would have to brute force, k1 and k2 simultaneously to figure out properties of m.

However, its extremely infeasible to guess a high-entropy private-key by brute force. The amount of work to brute-force a 128-bit AES key is about 2128, e.g., a billion (109) computers testing a trillion (1012) keys per second for a 1000 years would only have a 1 in 10 million chance in finding the right key. So the gain from multiple encryption in this scenario doesn't seem to be much.

On the other hand, if you had asymmetric encryption with a known public-key, you can quickly check if the guessed private key is correct -- can you encrypt a message with the known public-key and then decrypt it with your guessed private key to recover the original message?

share|improve this answer
    
My question is: if I encrypt some text twice, or many times. How do you know if you've decrypted the encrypted text? Another question: In the question you sent me to, people say that if one of the algorithms I encrypt with is weak, it damages the whole encryption and I would be better using single encryption, why is that? –  shoham Apr 25 at 9:11
    
@shoham - Imagine you were sending encrypted messages to a remote server that auto-decrypted the messages (to act out commands or what not) with a pre-shared AES-128 key and didn’t use TLS. Your encrypted data would be safe from heartbleed attacks. But if you turned on TLS using OpenSSL v1.0.1a-f all of a sudden your now multiply encrypted data is vulnerable. Your HTTP server is leaking memory potentially with your secret keys or fully decrypted messages. Hence TLS being broken could break TLS+AES, while AES alone would have been secure. –  dr jimbob Apr 26 at 4:36
1  
@shoham - Simply E(k1, E'(k2, m)) mathematically won't be weaker than single encryption (where E and E' are different encryption functions with different keys). But there is a chance that a complicated multiple encryption scheme opens you up to more side-channel attacks from bad implementations (think heartbleed, or padding oracle, or some new attack that you add). Thomas Pornin, recommending "don't do it" in the 2012 post, more recently answered more favorably about using layers of encryption if you "believe in layers, then add layers". –  dr jimbob Apr 26 at 4:49
    
@shoham - I'm not trying to say he's inconsistent, I just brought up that post as he ends is that its relatively obvious that layers of encryption doesn't weaken security (except in the way he mentioned in 2012 and I mentioned in the Heartbleed example, that you potentially open up more side-channel attacks). Granted, the side-channel attacks would still be there if you used a single flawed encryption algorithm and chose the wrong one. –  dr jimbob Apr 26 at 4:53
    
Cool. But you forgot to answer my question: How do you know that you've decrypted a message when it's multiply encrypted? You can't check if it's readable because it won't be. You must have both keys, don't you? –  shoham Apr 26 at 17:53

I'm curious about the practicalities of this. I understand that it is trivial to prove or disprove a private key but that involves a LOT of overhead. It's simply not feasible to do this for every attempt so there would need to be a trigger in the 'decrypted' data to spark that - text, known header values, whatever.

So I think shoham's idea of double encryption will foil just about every attempt out there, simply be denying the attacker any usable triggers.

My 2p.

share|improve this answer

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.