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 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.

share|improve this question
7  
If you're looking for responses related to Cryptanalysis you might want to specify a couple of additional pieces of information. Firstly, how many cipher texts would the attacker have access to, secondly how many ciphertexts would the attacker have access to and thirdly what type of data is encrypted by the ciphertext (e.g. is it binary data or text). –  Rоry McCune Mar 18 '13 at 16:16
6  
Well, it appears that you made your point. That's it, you win. A bunch of guys on a security site weren't able to crack your "encryption". –  Adnan Mar 18 '13 at 18:24
4  
Hello RamRachum, Challenge to decode something style-questions are considered off topic here. –  Hendrik Brummermann Mar 18 '13 at 20:28
6  
Hi Ram, I think you have a few misplaced assumptions. First of all, as I understand it, you are only asking about the pure mathematical aspects of cryptanalysis. If this is the case, the question should probably be moved to Cryptography, instead of remaining on Information Security - Here we do look at the whole picture, and we definitely do remain in the realm of reality and not a perfectly spherical chicken (as one of the commenters mentioned). –  AviD Mar 18 '13 at 20:50
5  
In real-world scenarios, if the confidentiality of your data is dependant on the secrecy of your encryption algorithm, it would probably be easier to steal the details of that algorithm (assuming the algorithm is not trivial). Weakest link, and all that. Moreover, in non-trivial real-world usage scenarios, it is nearly impossible to keep the algorithm to any level of secrecy, even without the attacker's involvement - whether it is other consumers of the algorithm, developers with access to the source code repository, or other inside attackers. –  AviD Mar 18 '13 at 20:53

8 Answers 8

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.

share|improve this answer
1  
@AndySmith Fine fine. :P Edited. –  Terry Chia Mar 18 '13 at 15:32
1  
@RamRachum I'm sorry, but why is this useless? You can't expect me to tell you how to break every single homegrown scheme out there can you? The crux of the matter is that homegrown schemes are weak, and there are very smart people out there breaking them. –  Terry Chia Mar 18 '13 at 15:52
1  
@RamRachum So you want me to give an answer specific to your algorithm with frankly very unrealistic limitations? Sorry no can do. That would be "Too Localized". My answer is sound as long as you are living in the real world. –  Terry Chia Mar 18 '13 at 16:01
2  
@Ram - how about remaining polite, okay? –  Rory Alsop Mar 18 '13 at 16:28
2  
Worse than nothing because it breeds a false sense of security. At least if you don't have a control in place you continue to rationalise future security decisions on that assumption, rather than relying upon the assumption that you have a control in place that is better than it really is. –  Rushyo Mar 18 '13 at 17:17

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.

share|improve this answer
5  
You've made an argument that keeping the secrecy of the algorithm is very hard. I completely agree. However, this is not what the question is about so this answer is not helpful. –  Ram Rachum Mar 18 '13 at 15:51
23  
@RamRachum: You might want to update your answer to specify that our starting assumptions are a perfectly spherical chicken on a frictionless plane. –  Scott Pack Mar 18 '13 at 15:57
4  
Scott: usually, the chicken occupies a point mass, because air resistance is really complicated with all those feathers and uh, yeah. @Ram ok, I've updated the answer to give some general pointers on where you'd start with some random data and what constitutes a risk to the "random" data. Disclaimer: if you rely on that information, you do so at your own risk. –  user2213 Mar 18 '13 at 16:18
1  
@Ram probably. Altering a file per byte position might confuse some of the text, but if you have enough you'd soon work out that's the pattern, particularly if parts of words are appearing. You'd essentially break it in two stages: 1) the weak algorithm, then 2) ok, I have parts of words, now, what's the pattern with the remaining ones? –  user2213 Mar 18 '13 at 16:35
1  
If you don't know the algorithm, and depending on how good its design is, it is not trivial, but it has been proven you just need either enough ciphered messages or a few clear messages and their ciphered versions to remove the noise and infer the transformation by applying a correlation algorithm between ciphered messages and their most probable decryption (using the known messages as training sequence, if available). If you are interested on the maths involved, reading about information theory, signal processing and machine learning may help you. –  elcodedocle Mar 18 '13 at 21:32

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.

share|improve this answer
4  
It's a principle. It's meant to guide decision making. It's not a law, rule or theory that is actually fact. –  Rushyo Mar 18 '13 at 17:18
1  
It is a rule. –  Smit Johnth Mar 18 '13 at 23:09
1  
@Rushyo Given how well Kerckhoff's principle has worked for modern algorithms, I'd say it's a fact. –  Terry Chia Mar 19 '13 at 2:12
    
@SmitJohnth For it to be a rule it would need an obligation. You can apply a rule to a principle (i.e. everyone must follows Kerckhoff's principle to work on this library) but that doesn't make the principle itself a rule. –  Rushyo Mar 20 '13 at 13:53
1  
@TerryChia A principle can be applied successfully 100% of the time and still doesn't become a fact. A fact isn't actionable, like a principle is. You can enact a principle by following it, you can't enact a fact. You don't say "We need to apply the laws of gravity for this". You do say "We need to apply Kerckhoff's principle for this". Someone can choose to ignore Kerckhoff's principle (at their peril). They can't choose to ignore the laws of gravity. –  Rushyo Mar 20 '13 at 14:07

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.

share|improve this answer

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.

share|improve this answer
1  
+1 for mentioning one-time pads. –  Roy Tinker Mar 18 '13 at 21:36

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.

share|improve this answer
5  
+1 this has a few inconvenient side effects. –  Mr.Mindor Mar 18 '13 at 18:47
1  
Excellent answer, shows clearly why the question is "flawed" in itself. –  mafutrct Mar 18 '13 at 20:02
    
I don't really understand all this "The real world implacably reminds us that this is not true." in all the answers. Real life example: one uses a reversible encryption algorithm to protect sensitive user data on the server. That means that it can't be a one-way algorithm like we can use to store passwords, so it must have a key. So now how exactly protecting this key is different from protecting the algorithm? Just assume that the guy who wrote this algorithm is the same guy who generates/manages the encryption keys. Bribes, stealing etc. would apply in the same way to both methods. –  XzKto Mar 19 '13 at 6:59
2  
I'm not saying that it is the way to go and I will never use something like this in production, but all the answers are just lazy, imho. –  XzKto Mar 19 '13 at 7:00
5  
The algorithm exists as compiled code in files, and also source code on developers' machines, revision control software, backups... and there are design documents, as printed paper, emails, and in the head of several people. It would be very hard to track them all and ensure secrecy. This contrasts with a key, which exists only in RAM or, at worst, in a single file, and not in all the other mediums I just listed. You can abduct all the developers, none of them has the slightest clue about the value of the key since it never entered their brain in the first place. –  Tom Leek Mar 19 '13 at 12:16

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.

share|improve this answer
2  
Hmm, so the ultimate security arrangement would be to couple a well-known encryption algorithm with a home-brew one, no? Because then you enjoy the advantages of both: You enjoy the security of the well-known algorithm, but if a vulnerability was discovered in it, you're still protected by the home-brew one. No? –  Ram Rachum Mar 18 '13 at 20:22
8  
Not an unreasonable position, if you are proficient enough to combine the algorithms safely without introducing new vulnerabilities. Another choice, if you are proficient enough, is to make a trivial modification to a well known algorithm and keep the modification secret. However, in the real world, you are almost 100% guaranteed to make things worse by adding something to it - cryptography is hard, even though it might at times seem like it isn't. –  Nakedible Mar 18 '13 at 20:34
1  
If, in symmetric encryption, you apply your home-brew algorithm before or after a well-known algorithm, you will in no case make things worse. I think that applying your home-brew algorithm after a well-known algorithm in encryption (and so before the well-known algorithm in decryption) would be better than applying it before the well-known algorithm. What you're stating in your comment is probably true, Ram. –  Paul Mar 19 '13 at 15:25
    
To give an other example of the 'security through obscurity' and 'well-known algorithms' combination approach: When doing a cryptographic hash, applying an injective function (such as salting or xor-ing with a constant) on the data before or after hashing cannot decrease security, if the hash function has no weaknesses. –  Paul Mar 19 '13 at 16:41

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."

share|improve this answer

protected by AviD Mar 18 '13 at 21:09

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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