How would one crack a weak but unknown encryption protocol?

Question

I was reading this interesting question:

Is my developer's home-brew password security right or wrong, and why?

It shows a weak home-brew algorithm developed by "Dave", and the answers discuss why this is a bad idea. (Actually hashing algorithm rather than encryption, but my question applies to both.)

It makes sense to me that a home-brew algorithm is a very bad idea, but there's one thing I'm not understanding.

Assume I'm an attacker, and I am faced with an weak-but-unknown encryption algorithm developed by "Dave". How would I crack it? I wouldn't even know where to begin. It would be a seemingly meaningless string of characters.

For example, say that the home-brew algorithm is like this:

• Use a weak well-known encryption algorithm on the original data, then:
• Do a bitwise-negative on any byte whose serial number in the file has a repeated digit sum which is prime. (Or any other such mathematical manipulation, this is just an example.)

How would one hack a file produced by such an algorithm without knowing it in advance?

Edit: Everybody, please don't try to convince me of how hard it is to keep an algorithm secret. Please answer this question on the assumption that the algorithm is kept completely secret, despite of how difficult that is to achieve in real life.

Also, assume that I have no access at all to the algorithm, only to the resulting data.

Answer 1

Assume I'm an attacker, and I am faced with an weak-but-unknown encryption algorithm developed by "Dave". How would I crack it? I wouldn't even know where to begin. It would be a seemingly meaningless string of characters.

That's correct, you wouldn't. Here's some encrypted data (4587556841584465455874588). Got a clue what that means? Absolutely not.

However, you're missing the core, fundamental most integrally important central pillar key to the universe that holds cryptography together. The idea is simple:

the key is everything

That's it. That's the bit you have to protect. The bit you must guard with your life and hope nobody is going to hit you with a hammer until you tell them what it is.

On this basis, you must assume that your algorithim can be read by the attacker. They know how it works. They can document its process. If there are any weaknesses, they'll find them. And they'll exploit them. Like that angry CIA Dad from Taken.

This, it turns out, is less of an assumption and more of the practical case in use. Dave, the home brew cryptographer, wants to include an encryption algorithm in his program. Deciding to eschew all the testing and design work cryptographers have done for him for free over the years, he writes something involving the odd xor, compiles his program and helpfully gives it to friends.

That algorithm is now in their hands. Game over.

Now, you might ask "can't I just keep the algorithm secret? That'll work, right?" Oh Dave, plz stop. Nonono. The problem with secret algorithms is that they're much more likely to be stolen . After all, the key is different for each user (actually, this is not a requirement, but, let's just assume it is for simplicity) but the algorithm remains unchanged. So you only need one of your implementations to be exposed to an attacker and it is game over again.

---

Edit: Ok, in response to the OP's updated question. Let us assume for a moment that the algorithm is totally unknown. Each of the two participants in an encrypted conversation have perfect security of their algorithm implementation.

In this case, you've got data to analyse. You could do any one of the following:

• Analyze for frequently known letters. This is how you'd break a typical caesar-shift cipher.
• Attempt to guess the length of the key. With this information, you can move into looking for repeated ciphertext blocks which may correspond to the same plaintext.
• Attempt index of coincidence and other such measures used to break the vigenere cipher, since many polyalphabetic ciphers are (possibly) just variants of this.
• Watch for patterns. Any pattern might give you the key.
• Look for any other clues. Do the lengths correspond to a certain measure, are they for example multiples of a certain value such as a byte boundary and so are (possibly) padded?
• Attempt to analyze with one of the symmetric cipher cryptanalysis techniques. These rely on knowing the algorithm in many cases, so may not apply here.
• If you believe the the data in question represents a key exchange, you can try one of the many techniques for breaking public key algorithms.

The fact is that a short piece of data from an unknown algorithm could well be undecryptable. However, this does not mean you should rely on this being the case. The more data a cryptanalyst can recover, the more likely they are to break your algorithm. You probably don't know without serious cryptanalysis what that boundary is - for example, it is reasonable to assume that one could bruteforce a caeser-cipher algorithm for three letter words, since there are few that make sense.

You are up against re-use problems too. In WWII, the Engima overcame this problem by having programmable settings for their secret algorithm, but this was broken too.

There is also the human element of cryptography to consider. I realise the label on the tin says "use once, do not digest" etc, but humans are humans and will likely use twice, three times etc. Any such behaviour plays into the hands of the cryptanalyst.

Answer 2

An unknown "encryption" algorithm has been historically achieved at least once. I am speaking of Minoan Linear B script, a writing method which was used in Crete around 1300 BC. The method was lost a few centuries later, with the death of all practitioners and the overall collapse of civilization during the so-called Greek Dark Ages. When archaeologists began sifting the earth around Knossos and other locations, at the end of the 19th century, all they got was a bunch of tablets with unknown signs, without a clue about the writing system which was used to produce them.

The interesting story here is that Linear B was unravelled in 1950s, using the same analysis tools which were employed against encryption systems of that time. In effect, the writing was considered as an "unknown encryption algorithm". It succumbed to statistical analyses, chained inferences, and some hypotheses on the plaintext (basically, the assumption that the base language for a variant of Greek). This is a classic and masterful illustration of how cryptanalysis works against "manual cryptosystems".

---

Of course, assuming that a cryptographic algorithm can be in use and still remain secret, is implausible. By the same assumption, there is no piracy of video games or media contents. The real world implacably reminds us that this is not true. The only known way by which an algorithm may remain secret is to kill its inventors and practitioners, destroy their apparatus, and wait for a few centuries. This has a few inconvenient side effects.

And even if, in a given specific instance, details on an algorithm have not leaked yet, there is no way of quantifying how much secret the algorithm is, i.e. how much time it will take for reverse engineering, bribes or wholesome theft to rebuild the algorithm. This is the main reason why cryptographers, about 40 years ago, decided that key and algorithm should be split, with the key being secret and the algorithm being non-secret: you can quantify the secrecy of a key, not the secrecy of an algorithm.

This gives us an insight into your specific question. Your "secret algorithm" hinges on the notion of a "mathematical manipulation". How many of these are they ? Can you estimate or describe the set of "mathematical manipulations" ? You will find that an encryption algorithm is itself a "mathematical manipulation", so your question is rather ill-defined.

Answer 3

To attack a cryptographic protocol, you have the following attack methods

• Known plaintext: Trying to find correlations between the plaintext you have and the corresponding ciphertext.

• Chosen plaintext: Encrypting specific plaintext and studying the changes to the ciphertext as the plaintext changes.

• Choosen ciphertext: Decrypting specific ciphertext and studying the changes to the plaintext and the cipher text changes.

• Known cipher text: Where all you have is the cipher text, below is a simple example.

Long time ago I took a cryptography class, in one the lectures we were taught the cryptonalysis of substitution ciphers. This is not how things are done now, but this is where the science of cryptography had started, and this is how cryptonalysis had begun.

Let's say you can across this cipher text.

Mx qeoiw wirwi xs qi xlex e lsqi-fvia epksvmxlq mw e zivc feh mhie, fyx xlivi'w sri xlmrk M'q rsx yrhivwxerhmrk.

You don't know the algorithm, you don't know the key. How should you start?

• Analyze the letter frequency: Total length is 87 letters. We see that i was used 12 times -> ~13%. According to Wikipedia's article on letter frequency, this letter is likely to be e. Our cipher text is now:

Mx qeoew werwe xs qe xlex e lsqe-fvea epksvmxlq mw e zevc feh mhee, fyx xleve'w sre xlmrk M'q rsx yrhivwxerhmrk.

• Now the second most frequent letter is x was used 11 times -> ~11%, so it's likely to be t. Our cipher text is now:

Mt qeoew werwe ts qe tlet e lsqe-fvea epksvmtlq mw e zevc feh mhee, fyt tleve'w sre tlmrk M'q rst yrhivwterhmrk.

• Now we're starting to see the patterns. Replacing i->e and x->t suggests that the key could be 4. Let's try it:

It makes sense to me that a home-brew algorithm is a very bad idea, but there's one thing I'm not understanding.

Ahaa! We got it! Now you've done your first cryptonalysis. This is one way the ciphertext could be analyzed.

Answer 4

I think nobody has said it aloud here, so I will.

If a cryptographer is given only one ciphertext with no means to get more, the ciphertext is short and no knowledge of the plaintext is given, it is near impossible to decrypt the text. The only way this is still possible is if the cipher is around the difficulty level of a substitution cipher.

Given the same algorithm, if there is a way to get more ciphertexts on demand, if the ciphertext is sufficiently long or if there are some known parts of the plaintext to help, it is likely that the algorithm can be cracked given enough effort.

But even still, cryptanalysis takes a lot of effort compared to the effort of creating a simple cryptoalgorithm from scratch, so it is unlikely anyone will expend the effort unless there's a good reason for doing so.

Answer 5

If you're going to distribute a secret algorithm, why not just distribute one-time pads instead? It's more secure.

If you don't like the idea of one-time pads because too much data is moving over the wire, then why are you assuming that the attacker only has one cyphertext?

Assuming somebody only has one cyphertext, and doesn't have the algorithm, (two bad assumptions), then your weak, but well-known underlying encryption system probably doesn't have any vulnerabilities to begin with.

Answer 6

There are several ways.

The first, and most obvious is that the attackers compromised your server to the extent where they managed to obtain your source code. In that particular case, your homegrown scheme is as good as nothing.

The second way is that the attacker might be able to submit his own values to your algorithm and see the before/after result. This is known as the Chosen Plaintext Attack. A good encryption scheme should not be vulnerable to it. A homegrown scheme probably is.

Even without a chosen plaintext attack, a homegrown scheme is usually laughably weak. A laymen like you and I might not be able to make sense of the output of a homegrown scheme. However, there are a class of very smart people who devote their time and effort to breaking such cryptographic schemes usually in return for a good paycheck. You might have heard of them, we call them Cryptographers.

Answer 7

Please answer this question on the assumption that the algorithm is kept completely secret, despite of how difficult that is to achieve in real life.

The problem with this is that you are ignoring Kerckhoffs's principle, which says that the security of an encryption scheme should not depend on the secrecy of the algorithm.

Anyway if you are really interested in crypto you should take a course like this one.

Answer 8

Since it hasn't been mentioned and this question has been around a while...

A computer scientist helped decipher an 18th century secret society's encrypted text. The text was very ornate, with symbols and glyphs. It stumped literary experts for centuries. The trick was to guess some of the letters and what they may stand for, and to guess the original language also, since German has different letter frequencies than English or Italian.

Here is the description of the cipher text and how it was unraveled.

http://phys.org/news/2011-10-scientist-mysterious-copiale-cipher.html

http://stp.lingfil.uu.se/~bea/copiale/

http://www.wired.com/dangerroom/2012/11/ff-the-manuscript/all/ (Very long, very interesting.)

With the Copiale Cipher, the codebreaking team began not even knowing the language of the encrypted document. But they had a hunch about the Roman and Greek characters distributed throughout the manuscript, so they isolated these from the abstract symbols and attacked it as the true code.

"It took quite a long time and resulted in complete failure," Knight says. After trying 80 languages, the cryptography team realized the Roman characters were "nulls," intended to mislead to reader. It was the abstract symbols that held the message.

The team then tested the hypothesis that abstract symbols with similar shapes represented the same letter, or groups of letters. Eventually, the first meaningful words of German emerged: "Ceremonies of Initiation," followed by "Secret Section."