Devising encryption schemes and protocols

Question

I am wondering how encryption schemes are developed and why certain decisions are made.

For example. I have seen a company hash a string with SHA1 and then RSA encrypt it. Why? I've also seen the hash and plaintext be concatenated and then RSA encrypted.

My (broad) question is how does combining different methodologies impact security?

One could go crazy and add to the above by adding a magic string in between every char in the plaintext, hash every other magic string, etc until you have a really (over-complicated) scheme.

A real example is:

key = hex( rsa( plainText + hex (sha1( plainText ) ) ) )

why choose to do this?

While we're at it why not do

key = hex( rsa( anotherfunc(someOtherFunction(plainText)) + someOtherFunction(plainText) + hex (sha1( plainText ) ) ) )

and go to town...you could combine all sorts of functions.

Why is

key = hex( rsa( plainText + hex (sha1( plainText ) ) ) )

used over

key = hex( rsa( hex (sha1( plainText ) ) ) )

or

my over-complicated example

Answer 1

Cryptographic algorithms are complicated beasts where every single detail matters for security. Unfortunately, cryptographers do not have a simple test which can tell whether a given algorithm is secure or not. It is unknown whether, in a mathematical sense, such a test could exist at all; and, even if it exists, we have not found it yet. We do not even know if secure algorithms can exist in general. Decades of cryptologic research has come up with a lot of partial solutions, such as "security proofs" which reduce some problems to other problems (e.g. a proof that the Rabin cryptosystem cannot be less hard to break than integer factorization -- which does not imply that integer factorization is hard).

So the normal methodology is to have some cryptographer publish a proposal, and let others try to break it and then potentially fix it. When an algorithm has been subject to such external scrutiny for some years and still survives, it is deemed "usable".

The case of RSA is a good illustration. Its mathematical description was first published in 1977, but it was only the core principle, with the modular exponentiation. To turn that into a secure algorithm for asymmetric encryption, or a secure algorithm for digital signatures (not the same thing at all), one must add some other elements, including random bytes, hash functions and behavioural constraints (e.g. whether it is good or not to report a "bad padding" error upon decryption). A number of hastily slapped together proposals turned out to be unsatisfactory. After a long trial-and-error process, RSA (the company) produced PKCS#1 v1.5 in 1993. This standards tells you exactly where each byte goes, including hash functions and random bytes. Although it seems rather sturdy, it turned out, in 1998, to have a weakness which could reveal the private key if the implementation, upon decrypting data, was too talkative about error conditions, when decryption fails.

This prompted new versions of PKCS#1, v2.0 in 1998, v2.1 in 2002, and v2.2 in 2012. What v2.0 describes appear to be robust for encryption; v2.1 extends it for signatures, and v2.2 adds some glue for newer hash functions. Not that a properly implemented PKCS#1 v1.5 would be weak; but the newer versions (called "OAEP and PSS paddings") benefit from partial security proofs (which, by the way, took time to be actually proven; the first published proofs were later found to be erroneous).

This is how algorithms should be designed: with years of effort by people who are specialized in the subject. The lack of reliable test for security means that we have no better way, and even spending 20 years on a single widely-used algorithm does not guarantee that every problem was detected.

---

In parallel, there are a lot of people, in the computing industry, who do not follow this methodology. Instead of waiting for well-studied algorithms to be turned into standards, they just go ahead and slap together a few primitives, sprinkling hash functions and other elements in a seemingly random way. Their guidance is a few very vague notions of security (often badly misunderstood) and whatever they will find in other people's blog posts.

This is why you will observe, in practice, a lot of "homemade schemes" where some developers just went way too much creative. Almost all of these schemes are weak and breakable, but the exact reason why they fail depends on the context.

Why many developers act that way is a mixture of arrogance and ignorance (often more ignorance than arrogance), and the primary cause is that special property of security: you cannot test for security. This is what makes security, and in particular cryptography, quite alien to most developers: it operates differently than all other fields. When you write a Web site or a graphical application which does 3D rendering or an accounting system, you test for functionality: you check that things work as expected when faced with normal situations. In security, you must test for non-functionality: you must check that things fail as expected when faced with abnormal situations. The virtually infinite set of "abnormal situations" makes the usual Q&A processes utterly ineffective for security.

The best we can do is "spread the word", as this present message tries to do: don't do homemade crypto.

---

Summary: if you can give simple explanations of why a given assembly of the RSA modular exponentiation and hash functions yields an "obviously secure" algorithm or not, then you are due for a PhD or even a Turing award.

Answer 2

Your question has two parts, really:

1. How do people design cryptographic techniques?
2. Why do people combine lots of cryptographic techniques?

The first part has a rather complex answer. The short version is "by studying in the field for a very long time, working very hard, and then letting people try to crack their algorithm for many years and seeing if anyone succeeds". The long version is beyond my expertise, so I'll leave it for others to explain. While typing this, Tom Leek has posted an answer that covers this nicely.

The second part is easier to answer.

Generally speaking, the culprit here is a lack of understanding of cryptographic principles. When people (by which I mean, in most cases, big companies and/or over-enthusiastic programmers) realise that they should be securing data, they decide that they don't want to fall short. They want the data to be really secure. When securing a building, two locks are better than one, and seven locks, a big steel barricade and a few miles of razor wire are even better than that, so the assumption is that using lots of cryptographic techniques together will stack up in a similar way and make the data super-secure.

Sadly, this assumption is mostly incorrect. Crypto functions are complex things, with lots of odd quirks, and they're not designed to work together. Using crypto functions in any way other than the way they were designed for generally leads to unintended results. It's frequently said on this site that there are perhaps a half-dozen people in the world who know enough about cryptography to design their own techniques - and if you have to ask who they are or whether you're one of them, then you're not one of them.

Answer 3

I would like to add a little bit more to the already outstanding answers.

First it is useful to distinguish among "primitive" (e.g., AES, SHA1), "protocols" (e.g., TLS1.2, DNSSec, etc) and "constructions" (e.g., HMAC, PBKDF2, AES-CBC). What you are asking about is a particular construction. (Note that the distinction between "construction" and "primitive" depends on what you are talking about. If you are looking at how SHA1 works, you will see that it is a construction of more primitive things.)

So I will break your question down into three parts

1. Why do we need (complex) constructions?
2. How to people devise constructions?
3. WTF is up with key = hex( rsa( plainText + hex (sha1( plainText ) ) ) ) ?

Why do we need constructions?

The classic example of a construction are block-cipher modes. Because a block cipher like AES is a function that takes a key and a block (128 bits) of data and returns 128 bits, every time you encrypt the same block with the same key, you will get the same result; that's what you expect from a function. Because this can lead you to see penguins, we put AES in a construction that makes sure that each block is actually encrypted with a different key or that each block undergoes some transformation before it is encrypted.

Another common construction is HMAC. If Alice and Bob share a secret key, k, and Bob wants to make sure that the messages he gets from Alice really are from Alice they can use k to create a Message Authentication Code (MAC). Now the way that almost every developer naively comes up with for creating a MAC is to send MAC = SHA1(k, message) along with the message. Alice can create that MAC, and Bob can verify it by performing the same computation on the message and seeing if he gets the same result.

Unfortunately that naive MAC construction is vulnerable. Given how SHA1 (and almost every other cryptographic hash algorithm works prior to SHA3) Mallory can take the message and the MAC and add stuff to the end of the message and construct a new MAC based only on the original MAC and the new material. That is, Mallory can actually use the MAC that Alice sends as a key for creating a new MAC for the extended message. So instead of using the naive MAC construction, we use HMAC, which looks like HMAC= H(k_o, (H(k_i, message))) where H is some hash algorithm (and k_o and k_i are derived from the k in a specified way).

Someone looking at HMAC might think that it is overly complex, but it is no more complex than it needs to be in order to be able to do its job. So this is why we use often complex constructions.

How do people devise constructions?

The process is as @tom-leek described it. It involves a process of asking explaining what is expected from the construction, why the parts are there, and then asking people to try to break it.

If you want to see this process in action, take a look at the password hashing scheme competition. There is a community that is looking for a successor to PBKDF2, scrypt, bcrypt. So if you look at the mailing list archives you can see this process. One of the motivations for that project is to discourage things like what we find in the third question ...

What is up with that rsa, sha1 construction?

There is no way to know without asking the person who came up with it. I'm guessing that they'd seen standard salting advice that recommends hash(salt, hash(password)), but don't fully understand what that is for.

RSA in here is particularly odd. First of all, there doesn't seem to be a key in there; so I don't understand that even at the basic level (much less the intent). But assuming that the key is some constant known by the system, I'm guessing that this is a particularly obtuse way of going after the "secret salt" approach to password hashing.

The idea behind a secret salt approach is that even if your password hashes leak, you can make the work factor for someone trying to crack the hashes much harder than the work factor for the legitimate authenticating server because the legitimate server has access to a secret that won't be in the database of password hashes. The secret salt might be available only from a Hardware Security Module (HSM) or such.

But even if that is the intent here, RSA is just not the right way to go about doing this. But as I'm already speculating wildly about the intent, I won't go into further detail.