2
$\begingroup$

Previously, I asked what is the simplest digital signature scheme known, under the assumption simpler implementations could provide valuable insights on the nature of the problem.

Among competing hypotheses, the one with the fewest assumptions should be selected. (...) In science, Occam's razor is used as a heuristic technique (discovery tool) to guide scientists in the development of theoretical models https://en.wikipedia.org/wiki/Occam's_razor

I specifically asked for implementations that didn't use number theory, because numeric operations (division, modulus) require some added complexity to implement in any "neutral" language that doesn't have numbers.

I received a plenty of negative comments claiming simpler schemes aren't proven to be secure, that simplicity is subjective and the general sentiment was that the question was pointless.

My question, thus, defies my own beliefs: has Occam's Razor ever proven useful for cryptography at all? Is there, for example, any historic occurrence of someone starting with a complex cryptographic scheme, looking from simpler solutions, and eventually finding answers that led to a better understanding of the problem itself?

$\endgroup$
  • $\begingroup$ "to guide scientists in the development of theoretical models", but it's unclear to me what theoretical models of cryptography you have in mind. $\endgroup$ – bmm6o Jan 27 '17 at 0:25
  • $\begingroup$ Cryptographers don't try to make things needlessly complex. Everyone will agree simpler is better provided it doesn't hurt security. Cipher design usually starts with something simple and adds complexity as needed. $\endgroup$ – user13741 Jan 27 '17 at 1:34
  • 1
    $\begingroup$ "Is there, for example, any historic occurrence of someone starting with a complex cryptographic scheme, looking from simpler solutions, and eventually finding answers that led to a better understanding of the problem itself?" That's basically how research always works, in cryptography and probably in many other fields. You'd find plenty of examples if you cared to actually look at the literature. $\endgroup$ – fkraiem Jan 27 '17 at 2:07
  • $\begingroup$ Yet on the other thread I'm receiving a lot of hostility for merely asking for simpler solutions. I give up. $\endgroup$ – MaiaVictor Jan 27 '17 at 2:44
  • 2
    $\begingroup$ @fkraiem asking questions is part of how normal people educate themselves. Your arrogance is the reason SO has a bad fame. $\endgroup$ – MaiaVictor Jan 27 '17 at 18:35
3
$\begingroup$

In general, I feel that academics are drawn to complexity even if there's no compelling reason for it. I've looked at many ciphers from the hardware perspective, and the simplest ciphers are the best for power, area, throughput, and analysis. The push for lightweight ciphers in the last 10 years has given us what I consider to be "occam's razor" ciphers, such as Simon, Prince, Present, etc, as they have equivalent security at a fraction of the hardware cost of the *fish and AES, for example. (I know that this is not a completely fair comparison because we have bit-based vs. byte based, but it is true from the hardware perspective.)

$\endgroup$
  • 2
    $\begingroup$ It's not just academics, there are plenty of engineers and programmers and just people in general who have the habit of opting for additional complexity for no good explicit reason... $\endgroup$ – Ella Rose Jan 27 '17 at 3:30
  • $\begingroup$ The definition of lightweight cipher / lightweight crypto is still vague and not yet defined by NIST... And by design you could say that AES is pretty simple (as opposed to DES...) $\endgroup$ – Biv Jan 27 '17 at 5:16
  • $\begingroup$ @Biv We define lightweight by power. I was at the NIST 8114 workshop and you are correct that "lightweight" is vague. Internally, AES is the arbitrary comparison. A pretty good lightweight cipher is about 100x the power of a storing just plain bits in a register. AES is somewhere between 500x~600x. I doubt this will never be formalized because it depends so much on the process. Newer processes take more power (contrary to the marketing), but those are ballpark multipliers that I see on nodes <32nm. $\endgroup$ – b degnan Jan 27 '17 at 13:42
8
$\begingroup$

The definition you cite says that "among competing hypotheses, the one with the fewest assumptions should be selected". If you take this literally and don't understand fewer assumptions as simpler, this principle is widely accepted in cryptographic research: Having a provably secure scheme means that it can be shown to satisfy some security definition under certain assumptions. If you propose a new scheme and prove its security under weaker (or less) assumptions than what was needed for previous schemes, this is considered to be a substantial contribution.

As an example, consider RSA. A necessary assumption for RSA to be secure is that factoring is hard. However, nobody has succeeded so far in proving that under that assumption, RSA is actually secure. There exist security proofs for (variants of) RSA, but they require additional assumptions. At Eurocrypt 2009, a paper [1] received the best paper award for proposing an encryption scheme that is provably secure assuming only that factoring is hard. That scheme is not simpler than RSA, but the hypothesis that it is secure can be based on fewer assumptions.

[1] Dennis Hofheinz, Eike Kiltz: Practical Chosen Ciphertext Secure Encryption from Factoring. EUROCRYPT 2009.

$\endgroup$
  • $\begingroup$ Note that lack of adoption would not be a contradiction here. Readily available hardware, historic resistance to cryptanalysis, comparable technology and much more influence what will actually be popular. $\endgroup$ – Elias Jan 27 '17 at 10:56
2
$\begingroup$

The answer is yes, simplicity has been used to drive cryptographic algorithms.

Ironically, the strongest (and the only provably secure) cryptographic algorithm is also the simplest -- the One Time Pad. The algorithm has virtually no complexity, requiring only an XOR operator.

However, the simplicity has its price: distributing and managing one-time keys is exactly as hard as managing the secrets themselves, and generating them securely is not only exceedingly difficult, but the process is responsible for all of the security.

Every other symmetric algorithm employs some form of "key stretching" at its core, where the information that makes up the key is applied to the plaintext in a repetitive or iterative fashion, yielding a ciphertext. This is true whether the key is the order in which transposition boxes are shuffled, or whether the key is a finite set of bits that drive a Feistel network. In all cases, it's the complexity of the stretching that hides the original bits of the key, and is used to hide the data as well.

Complexity of the key stretching is not the sole arbiter of what makes for a secure algorithm. Generally, security comes from having some complexity amplified by repetition. And here, the more repetition, the less complex the core of the algorithm needs to be. Compare the high complexity of DES with 16 rounds, AES128 with 10 rounds, AES256 with 14 rounds, and the simple (3 step) MIX function of Skein/Threefish, which uses MIX for 72 rounds.

And this is where the evidence for the answer to your question comes in. Skein can operate very efficiently on large, modern processors, but its design was deliberately kept simple specifically to work in low memory, small state, small CPU environments, such as a smart card. The simplicity of the Skein MIX function means it can be implemented in just three instructions: addition, rotation, and XOR; and only 100 bytes of state are needed (in addition to the program itself.) The more complex the algorithm, and the higher the amount of state needed, the larger the processing requirements. Lower requirements reduces the overall cost of encryption. And simplicity was used to reduce those requirements.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure "key stretching" is the right term to use; That term has an established meaning: Using PBKDF2 with a high iteration count to turn a weak password into a strong encryption key is an example of key stretching. Secure "key reuse" is arguably what all the additional complexity is really for. $\endgroup$ – Ella Rose Jan 27 '17 at 3:27
  • $\begingroup$ @EllaRose, I agree that it's not exactly the right term, but the concept is the same. Start with n bits of key material, stretch it to cover x bits of plaintext material. I suppose I could call it "watering down the entropy", but that has even less meaning. $\endgroup$ – John Deters Jan 27 '17 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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