In an answer to a previous question it was suggested that one way to protect your asymmetrically encrypted AES-256 keys, from say a solution to prime factorization, would be to chain asymmetric algorithms. Having read about the meet-in-the-middle attacks here and there I am a bit worried that if I chain, say RSA with ECIES (and why not add an ElGamal?), that I would somehow be undermining my own efforts or just doing an exercise in futility. Would such a system be more secure over the long-run (i.e. 30 years) than just going with one asymmetric encryption scheme?
You could protect the ECIES ciphertext with a superencipherment of DLIES, and you would not be weakening your security unless you slipped up and reused keys or used related keys. That means each step should be done carefully and thoughtfully as if it was the only protection step you would be taking. For example, when generating the cryptographically random value to serve as the session key protecting your data it's not the time to use a SHA-1 hash of "password1". Don't use one algorithm to protect both the key and the data of the next algorithm. Don't use ECB mode encryption. Simple, but important steps.
The key protection algorithms chosen don't necessarily all have to be asymmetric unless that best meets your business needs. The threat you're trying to guard against is that of a break in one of the algorithms, so the defense your building should include choosing each algorithm from different algorithmic families. The first algorithm protecting the data should be something venerable and trusted, such as TDEA (3DES). TDEA is used by IBM mainframes and cryptographic co-processors to encrypt their databases of keys - if it's good enough for IBM and their giant corporate customers, that's a good sign. To protect the TDEA key as a session key, choose a non-Feistel algorithm, such as AES, to superencrypt it. Then, choose your asymmetric algorithm such as RSA or ECC to encrypt the AES superencrypted data.
Is this much security necessary to last 30 years? The idea is that if a class of algorithms suffers a massive failure that you've other algorithms that haven't also fallen remaining in place. Let's say someone comes up with an instant factoring algorithm, suddenly rendering every RSA encryption ineffective. If RSA was the only algorithm protecting your AES key, you're at risk. Using RSA to encrypt the AES encrypted TDEA key would mean that both RSA and AES would have to fail before the attacker could get to your data.
Given that you're talking about a 30 year life span, it sounds like an application that will not be seeing daily use, so I am assuming performance isn't a concern. What should be a bigger concern is that you or your heirs will have the software, computing equipment, uncorrupted media, and knowledge available 30 years from now to decrypt it (or at least have enough money to hire an expert in ancient cryptographic data recovery.) The media is important. If you burn it to DVD, do you know the DVD's inks will last 30 years? If you print it on a barcode, will they still have a barcode scanner that can read those olde-timey QR codes? Those are real questions: if my father's will had been encrypted and stored on 96-column punch cards in his safety deposit box, or on a ZIP drive, or an old 9 track tape, or an 8-1/4" floppy, or even printed on cheap fading greenbar, I know I wouldn't have a reader for any of them today. That suggests you create a test plan that can be periodically executed to ensure future decryption will be successful. The test doesn't have to decrypt the actual sensitive data, but it has to prove the hardware and software required for the decryption still works, and that the media is still viable.
Regarding the software, you have choices to make there, too. You need to have faith that if you write a complex unchaining decryption application in .Net that there will be a .Net runtime environment available on Windows 15.1. Will tiny 64-bit CPUs still be infesting the planet for any purpose other than cell phone CPUs? Will Microsoft even exist? If you get 15 years down the path and .Net has evaporated from the face of the earth, what will you do?
And where are you going to store the keys for 30 years? Are you going to split them, keeping the RSA private key in one place, and the AES key in another? Are you going to commit one to memory? If so, are you going to be around in 30 years, or are you OK if the data is lost forever?
Finally, I come back to what should be your first step: go over your business requirements again and determine if you really need this much over-the-top protection, especially considering the costs of developing and maintaining some non-standard forms of encryption. Who are the attackers and what is their motivation? What's the value of the data you're protecting? How badly will someone really need it in 30 years? This kind of long term storage is very, very expensive. Are you willing to commit someone to 30 years of babysitting these secrets? Let's say the secrets are guarding an account number in an overseas bank. What happens to the protected assets if your heirs can't peel this onion apart?
1$\begingroup$ The idea "use TDEA for data, then use AES to encrypt the TDEA key" sounds bogus. Wouldn't you use both symmetric algorithms to encrypt the data, and then the asymmetric algorithms to encrypt the symmetric keys? $\endgroup$ Apr 30, 2013 at 17:34
$\begingroup$ It's not bogus, but it's another layer of protecting the TDEA key. Sure, he could superencrypt the TDEA message with AES, too. There's no particular rule saying keys must be encrypted only with asymmetric algorithms, and data must only be encrypted with symmetric algorithms. That's the common use of public key cryptography, but this application may not even have that need. $\endgroup$ Apr 30, 2013 at 19:20
$\begingroup$ If the application doesn't need public key crypto (i.e. there is nobody who needs to encrypt but not to decrypt), there is no point in encrypting a symmetric key itself – just encrypt the data (with as many algorithms/keys as necessarily), and store the symmetric key at another location (where you would store the private keys of your asymmetric algorithms). Storing the TDEA key alongside with the data just adds another breaking point, not another layer of protection. $\endgroup$ May 1, 2013 at 9:53
$\begingroup$ Now I understand your point. Sorry if the description was confusing, I was trying to state exactly that: to store the TDEA key alongside with the private key. Yes, if you encrypted the TDEA key and kept it with the data, that would be utterly useless. $\endgroup$ May 1, 2013 at 13:52