What makes an open source encryption algorithm safe?

Question

Take for example the popular AES algorithm where we have a combination of substitution, shift row, mix column, and add key steps involved in encrypting plain test.

All of the mathematical operations within the s-boxes, shift row, and mix column should be known to the attacker, correct? I understand they could be hard to calculate but aren't they static operations for the most part? Since they can literally see the implementation of the calculations in the code to see how all the bits were changed around. The only step that is therefore hard to break is the add key stage, where we XOR our key with blocks of bytes.

The XOR state is irreversible without the proper key which is what I understand, so whats the point of all of the other operations that happen on the key? Since the implementation details are known of how the substitution, shift row, and mix column steps work, whats the point of using them in the encryption scheme?

Answer 1

The XOR state is irreversible without the proper key which is what I understand, so whats the point of all of the other operations that happen on the key?

Suppose all we had was secret keys and the XOR operation. Well, actually, it is possible to build a secure cipher out of that, called the one time pad. One time pads offer perfect secrecy, but suffer from fatal practical flaws:

1. The keys must be as long as the messages.
2. You must never use the same key to encrypt two different messages, or it becomes very easy to break.

So we can look at your question from this angle: the extra complexity in modern ciphers is the price that we pay to remove those practical disadvantages. It's what allows us to use a single 128-bit key to safely encrypt gigabytes of data, time and time again.

The other thing that I'd highlight is this: you're assuming that just because you know what operations an algorithm does, it's automatically easy to undo those operations. But one of the core assumptions of modern cryptography is that this is false: there are operations that are easy to do but costly to undo. The prime example is that multiplication is easy (runs in polynomial time), but factorization is costly (doesn't run in polynomial time). It's possible to prove that, if such one-way functions exist, then cryptographic algorithms can be built and fully disclosed, whose security depends exclusively on the secrecy of the key.

So if the designers of AES chose their operations right, then AES encryption and decryption are:

1. Easy for parties who know the secret key;
2. Costly for parties who don't.

Whether this is true for actual algorithms like AES and why, well, that is the hard part, and can't be answered in a brief question/answer format like this.

Answer 2

• All of the mathematical operations within the s-boxes, shift row, and mix column should be known to the attacker, correct?

  • Yes, see Kerckhoff's principle

• I understand they could be hard to calculate but aren't they static operations for the most part?

  • I'm interpreting "static operations" to mean subBytes + shiftRows + mixColumns + addRoundKey, and that these are applied the same way every time, the same number of times, regardless of the plaintext/key being operated on. If so, then yes.

• Since they can literally see the implementation of the calculations in the code to see how all the bits were changed around. The only step that is therefore hard to break is the add key stage, where we XOR our key with blocks of bytes.

  • Well, they usually model ciphers as a "black box", in that an adversary may query the inputs and outputs of the box, but may not peer inside. Obtaining (partial) information about the internal state of a cipher is what leads to attacks. Designing an algorithm that can keep the key secret even when the adversary can observe the entire internal state is a bit of a hot topic right now. See white box cryptography

• The XOR state is irreversible without the proper key which is what I understand, so whats the point of all of the other operations that happen on the key?

  • First, a small correction: Most of the operations happen on the data, not on the key (though the key does undergo transformations in most ciphers, called the key schedule)
  • Basically, as Luis Casillas mentioned in his answer, the operations are there to protect the key, not the data. All of these extra steps are there mostly because of statistical attacks such as linear and differential cryptanalysis. These attacks can recover some of the internal state of a cipher (and therefore the key), given enough pairs of plaintext/ciphertexts.

This last point is arguably the real meat of the question here. Consider a closed source crypto algorithm compared to an open source one. On one hand, you have a black box that you have no idea how it operates, or if even does a good job.

To be honest, if it's a precompiled binary, you are going out on a limb to trust that it will even try to protect your data. For all you know, it will secure your information from all adversaries other then the programs author, who it will regularly send emails of all your private information to.

Even if you know the closed source alternative is trustworthy in it's intent, you don't know if it is well designed and capable of seriously protecting your data. The problem with designing crypto algorithms is that they need to be secure against ideas nobody has had yet. If that sounds impossible, it's because it is.

Algorithms like AES are believed to be secure because we can do math to formally quantify exactly how many bits of data can be safely enciphered with a given key before the key must be changed. This is frankly impossible with a closed source algorithm.

Let's concede that the developers of this trustworthy, closed source algorithm are actually cryptographers and have experience with linear and differential cryptanalysis (we are now basically talking about flying unicorns btw). Because they can't reveal how the algorithm works to you, they cannot prove it's resistance against any attacks.

Even if they did claim resistance to attacks, since the source is closed, this means there will likely be no formal description of the algorithm. This means it is not possible to present the algorithm for review. So this means, the only people that can vouch for it's security, are the people that are trying to sell it to you.

It's not a realistic option for crypto algorithms to be closed source, even without diving into math stuff. Untrusted arbitrary code execution is arguably the definition of insecurity in regards to computing, and you can't "trust" it in the cryptographically certain sense of the word.

• Since the implementation details are known of how the substitution, shift row, and mix column steps work, whats the point of using them in the encryption scheme?

As was mentioned, they are there for statistical attacks that attempt to retrieve the key. More specifically, the subBytes step is designed to maximize resistance to differential and linear cryptanalysis. The shiftRows and mixColumns combine together to provide full diffusion after 2 rounds.