Creating cryptographic algorithms at runtime

Question

Would it be possible to create a program with which to create a cryptographic algorithm (i.e. encryption or hash) using well-known elements of other algorithms in the same way that algorithms "reuse" systems such as Feistel's structure? That is, eventually decide to use an algorithm that combines the Rijndael KeySchedule, and the Pseudo-Hadamard Transform. All this correctly applying the concepts of diffusion and confusion of Shannon.

The objective of this would be during a communication to change cryptosystem repeatedly, so that if you want to do cryptanalysis of the messages you have to do cryptanalysis on several different algorithms. In this way a kind of PFS (Perfect Forward Secrecy) would also be obtained.

EDIT: I wasn't proposing the use of security by obscurity, in fact I thought the negotiation of the new cryptosystem as public, in the same way the negotiation of the cryptosystem in TLS is public, and only the key is confidential (being shared using a well-known key distribution algorithm, like DH or RSA). On the other hand I know the definition of Forward Secrecy, that's why I said "a kind of". I was referring to the scenario in which an attacker discovers a vulnerability in a previous algorithm, but because currently is being used another totally different, the cryptanalysis is different now, and the information transmitted before and after the broken algorithm would remain unrevealed, similar to the concept of PFS.

Regarding the use of algorithms already used (and therefore proven in theory their safety), I do not plan to create a new system that is adopted worldwide (or even on a small scale), I only played with the possibility of creating a system like this so that, for example, the AES is found to be ineffective, not all communications made since the adoption of the AES (or any other algorithm) are disclosed. I mean, I propose the possibility of not trusting a single algorithm, and given the problem of the existence of infinity of communications, the solution would be to generate infinity of algorithms.

Answer 1

This doesn't add new security as much as it just shifts it.

Encryption algorithms are carefully studied. Hmm... I didn't make that emphatic enough. Encryption algorithms are C A R E F U L L Y studied. There. That's better.

There are all sorts of tiny nuances to be had when designing an algorithm. A famous example were some of the S-Boxes in DES which were developed in a classified environment. Many thought they were a NSA backdoor. Several years later, differential cryptoanalysis was "discovered," and suddenly we found that these S-Boxes were the thing that prevented such an attack (thus the NSA had clearly known about these attacks for some while). This was not a "just got lucky by combining the right bits" thing. It was carefully thought out.

So the likelihood that your mix-and-match algorithm is breakable is far greater than any of the carefully studied algorithms. Far greater. Its basically guaranteed that a dedicated attacker will break your algorithm. The thing you have bought is anonymity. By using a publicly accepted algorithm, you are using an algorithm that provides great value to attackers to break. If they get access to your little secrets, they also get access to things like bank mainframes.

So you make yourself weaker against a reasonably determined attacker while making yourself a bit stronger against a very strong attacker like a state. Or do you?

A final issue to deal with is that you're mixing and matching known algorithmic pieces, and from your comments the pieces you choose are know in public. These algorithms were carefully studied, as I said before. This also means the attacks that these algorithms had to be tuned against are also well known. So all one needs to do is identify which basic pattern you are using, pull up a list of known attacks against it, and find out what attacks work. Which puts you in a strange corner where an AI might actually have enough data available to it in a convenient enough form to take your encryption on.

And that would be something a highly skilled attacker would be able to do, so you didn't really solve anything.

Answer 2

Suppose you have two cryptosystems $A$ and $B$ with $n$-bit keys. Maybe they're both secure at what they aim to do; maybe they aren't. Say they both take about the same cost to implement.

You are proposing using an $(n + 1)$-bit key, where the extra bit selects between $A$ or $B$. You have now doubled the cost to implement your system.

Does this add any security? At best, it adds a single bit of security.

But it is quite likely there are side channels that will distinguish whether $A$ or $B$ is being used. For example, one of my laptops sounds different (probably due to EM leakage causing tiny resonance in different components) during different crypto operations—you might be able to hear this from openssl speed aes-256 and openssl speed dsa2048 or similar. It might take appreciably longer to compute $A$ than to compute $B$, which even an adversary on the network might be able to measure.

So it more likely actually adds essentially no security at all.

What if $A$ or $B$ is broken, but you don't know which? Well, there are generic ways to compose two different cryptosystems of a single type—like IND-CPA encryption, or EUF-CMA authentication—so that the composition is at least as secure as the most secure component. For instance, if either $A_{k_a}(x)$ or $B_{k_b}(x)$ is a secure MAC, then the concatenation $A_{k_a}(x) \mathbin\| B_{k_b}(x)$ is a secure MAC with independent keys $k_a$ and $k_b$.

But using a key bit to flip between them does not make a secure composition—if it turns out that $A$ is secure but $B$ is not, then your key system is secure for only half the users on average, which is a rather modest way to bear the bad news of a broken design.

Does this provide forward secrecy? No. This is unrelated to forward secrecy. Forward secrecy is a confusing term that you should avoid—and especially the value-loaded variant ‘perfect forward secrecy’—in favor of just saying when keys are erased.

Erasing keys doesn't help if the adversary has a cryptanalytic breakthrough that ruins the security of the cryptosystem. Erasing keys only helps to ensure that compromising a device that participated in the cryptography won't reveal keys that can decrypt past sessions.

Answer 3

Suppose that one of your cipher suites has some weaknesses. Then the adversary can play with your network to force you to select the weak cipher to exploit the weakness. This is highly done in TLS. Therefore your system can turn into a single case during an attack.

Also, the attacker can store all off your communication. If somehow they can break one of them, they can use this in recorded communications.

There is no infinity of communications. With classical computers, we cannot search AES-128, but QC can. The mitigation is simply using larger AES key 192, or 256. Creating infinity algorithms, that is why we use keys.

From the implementation perspective, it will be hard and will take time to design all securely. But concentrating on one is more efficient.

---

This part before the update of the question

In Cryptography, we are acting on the Kerckhoffs's principles. Therefore, in the view of the attacker, the attacker will know each of the programmatically constructed ciphers. Actually, each newly-built crypto algorithm needs analysis before use. This is almost like you rolled your crypto algorithm. This is where your design is going to fail. An attacker analyzes all of your new constructions and exploits weaknesses.

Even double encryption with two different proven encryption algorithms can be more secure than your design. Or make double encryption with AES and apply the AES then your construction. This can prevent the weakness of your designs.

This is not forward secrecy this is some kind of security by obscurity. Forward secrecy in Wikipedia term;

Forward secrecy is a feature of specific key agreement protocols that gives assurances that session keys will not be compromised even if the private key of the server is compromised.

So forward secrecy is about the key agreement. The keys must be erased after use.

Instead of using such construction, select constructions that resisted rigorous analysis and attacks many years? Like, AES-GCM, Nonce-misuse-resistance AES-GCM-SIV or NaCL CryptoBox XSalsa20Poly1305.

Answer 4

You can do something like this. See Automated Analysis and Synthesis of Authenticated Encryption Schemes. They model (authenticated) encryption as a circuit, develop a certain basic set of primitives, and type inference rules to "automatically" prove authenticity + privacy.

That being said, this is all defined relative to a single block cipher I believe, so if this is attacked you're hosed. You could theoretically randomly sample from a certain class of pre-defined block ciphers as well though.

There are certain ways to compose cryptographic primitives such that the composition is secure if at least one of the primitives are. Basic examples are OT Combiners, and: $$\mathsf{Enc}_{a\lor b}(k_1,k_2;m) = \mathsf{Enc}_{a}(k_1;\mathsf{Enc}_b(k_2;m))$$ Where the scheme $\mathsf{Enc}_{a\lor b}$ is secure if $\mathsf{Enc}_a$ is or $\mathsf{Enc}_b$ is. I would suggest looking into this combiner-based approach if you really want this notion of security, although it doesn't seem useful in general --- if $\mathsf{AES}\text{-}\mathsf{GCM}$ is broken, the world has bigger problems than whatever application you're personally developing.