17

Let's say I have a message that I want to keep safe for the next 100 years. Is it theoretically possible?

Let's say the message is unique (raw picture data, raw video video data, raw text data) and the key is unique. Can anything prevent (near)future brute force attack?

daniel.sedlacek
  • 934
  • 1
  • 8
  • 15
  • 1
    Check out Tahoe-LAFS, they've apparently done [some work](https://tahoe-lafs.org/trac/tahoe-lafs/wiki/OneHundredYearCryptography) on 100-year cryptography. – Thomas Dec 22 '12 at 01:36

4 Answers4

23

TL;DR in bold:

We don't have crystal balls to predict where technology will take us, but the purpose of cryptography is to develop algorithms that have just this kind of resistance on a very fundamental level.

Mathematically speaking, in terms of "honestly" brute-forcing a single plaintext from a single ciphertext, knowing everything that would otherwise be needed to decrypt the plaintext other than the key, a 256-bit block cipher should be considered uncrackable by the laws of thermodynamics; our Sun will not emit enough photons in its active life (before it becomes a black dwarf) to enable a computer that works at the electron level with perfect efficiency to try every possible key in the 256-bit keyspace. The computer would be starved for energy after trying about 2^218 key values, meaning that if it tried keys perfectly randomly without replacement, and the key was also chosen perfectly randomly, it would only have a one in 275 billion chance to have found the correct key, given roughly 5 billion years before the Sun goes nova.

There is, however, one distinct disadvantage to the use of any computational hardware or software in existence today; it is already obsolete. It would be foolish to assume that any binary implementation currently used to encipher messages, nor any computer, language or even logical structure used to develop or execute that binary code, will still be in existence in 100 years. We already have problems with the availability of hardware that can read or write storage devices that were universal standards only 20 years ago, like floppy disks and tape drives. Even power plugs have changed fundamentally in the last 50 years, and those plugs and receptacles (and the exact specs of the power they use) are only regional standards as it is. Hell, 100 years ago we were riding horses, not driving cars. So, if you plan to encrypt something and then store the device used to produce it, I can virtually guarantee that in 100 years everything about the device will be so obsolete it will be unusable.

Given this 100-year expected timespan, I would rely on one of the simplest and yet most secure ciphers known to man; the one-time pad.

Simply create a numeric "alphabet" relating a number value to every character symbol you wish to be able to encipher (don't forget any needed punctuation, such as spaces, commas, periods, single/double quotes etc; you must not use more than 100 symbols, but most fully-formatted English-language messages will be well underneath this limit, even with capital letters). Then, gather a series of numbers, from zero to 99. You will need one of these numbers per character of the message. These numbers must be genuinely random; serious users of one-time pads usually gather bit data from environmental sources, such as measurements of background radiation detected on a radio telescope. For today's purposes, you could purchase a 100-sided die and give it a roll around the inside of a bowl to produce each number. It should also be acceptable to use a CSPRNG, provided that it is properly seeded from a source of true entropy (provided that the seed value is discarded after use, you probably won't need enough numbers from the PRNG for an attacker to be able to predict them). Make sure the memory is fully cleared from any electronic device used to generate random data.

To encrypt, take the random pad, the numeric alphabet, and the message you wish to encrypt into a place where you can't be seen by anyone else or any surveillance equipment (you know, just in case). Take the first character of the message, look up its alphabet code number, then get the first number from the random pad, and subtract the random number from the character code. If you end up with a number less than zero, subtract that number from 100. Look the resulting number up on the alphabet chart, and write down the character as the first character of the ciphertext. Repeat with the second character of the plaintext and the second number of the random pad. Continue through the message until you have encoded every character of the plaintext message. You must have used every number of the random pad, in order, once and only once.

When you're done, you burn or otherwise completely destroy your copy of the plaintext, and physically secure the random pad and alphabet. This is important; nobody should be able to get their hands on the random pad for 100 years, but they must be able to get to it in 100 years. The alphabet is not technically a secret, but it's inclusion with the ciphertext is a clue as to the use of a one-time pad (leading people to go searching for the pad), so I'd recommend keeping it with the pad. The ciphertext itself is perfectly secure in its encrypted form; you can chisel it into the stonework of the Supreme Court building if you wanted (and could do it fast enough to finish before the DC Metro Police took you away). It could be any of a number of alphabet ciphers, lending a little entropy to mask the discovery that it's a OTP in the first place.

To decrypt, someone must have the ciphertext, the same one-time pad and the same alphabet table that you used to encrypt. They take the ciphertext's first character, look up the number in the alphabet table, then add the number from the one-time-pad and modulo by 100 (simply truncating the hundreds place wherever it shows up). They turn the resulting number back into a character using the alphabet, and write it down. They then continue, character by character and number by number. Again, they must use every number of the random pad, in order, once and only once.

The one-time pad is a very old system, first being described in 1882 and re-invented in 1917, and it has the ultimate advantage; it is provably impossible to crack. Being genuinely random, there is no mathematical pattern to any of the numbers of the random pad (which forms the "key" of the cipher), and because each number is only ever used once (if you have more than 100 characters you will see the same two-digit number in the pad twice, but you can never predict when), the pad itself is never repeated. Thus, any attempt to decipher the message without the exact same pad is futile; it could produce gibberish, or it could produce a message of exactly the same number of characters, but whose content is something completely different. The only way to be sure that every character of the message is decrypted correctly is to have the exact same sequence of random numbers that encrypted the thing in the first place.

The disadvantages that keep it being used more universally are that it ideally requires a pad of infinite length (to handle any number of messages of any length), and there's a large possibility of offset error; someone can miss some or all of a message sent by the other person, so one person has crossed off fewer numbers on their pad, resulting in all further messages between the two parties being indecipherable and no real way to recover without exchanging a new pad. In your case, these are moot, but pretty much every other cipher system invented in the last 100 years has attempted to mitigate these disadvantages (primarily the infinite-length key) while trading as little as possible of the ideal security of the system.

KeithS
  • 6,678
  • 1
  • 22
  • 38
  • 8
    The problem of the one-time-pad (OTP) is that if anyone ever needs to decrypt the message, they need to be able to store the OTP somehow in complete secrecy. Since the OTP is the same length as the original message, this will be a very difficult task. By this measure, they could forgo encrypting the message and just do whatever they do to the protect the OTP and do it to the plaintext message. – dr jimbob Dec 22 '12 at 04:55
  • @KeithS thanks for the much needed theory, I thought there will be a positive solution like this. Now, as dr jimbob suggests, this is not very practical and I am not sure if it should be considered a cryptography at all. It's equally easy/difficult to hiding the message itself instead of hiding the key. – daniel.sedlacek Dec 23 '12 at 21:03
  • @drjimbob This is true but then if you keep the OTP and the cipher text in separate locations you have added an extra layer of security than if you just secured the original plain text message. I'd say if you stored them in two different bank secure boxes in different towns you should be pretty safe. – Cromulent Dec 27 '12 at 00:11
  • @Cromulent - Yes, you gain a little security via obscurity (the location of the N bank lock boxes; make you break it N+1 times -- generalizing to the case where your message was XORed with N different OTP). But from Kirchhoff's principle, you strive for more than security by obscurity. The designed in security arises only from the lockbox; (and any lockbox can be broken -- picking a lock, forging a signature, bribing your way in, is not impossible like brute forcing a good implementation of AES-256). Not to say OTP is useless; just long term encrypted message storage is not a good fit for it. – dr jimbob Dec 27 '12 at 05:47
  • 5
    Guys, *all* cryptography requires you to keep the key secret. – Graham Hill Dec 27 '12 at 12:20
  • @drjimbob - I would tend to agree with Graham Hill here; you must always keep the key secret, whether it's a OTP or AES, and so all the "non-computational cryptanalysis" methods you mention will get you an AES key just as easily as a OTP. Therefore the crux of your argument is that for sufficiently long message sizes, OTP storage becomes difficult compared to just 256 bits of an AES key. While I see that point, I think the bigger concern is storing the key and the ciphertext in a manner that will still be accessible in 100 years, after USB, Firewire and SATA have all become extinct. – KeithS Dec 31 '12 at 16:05
  • @GrahamHill, KeithS - You are ignoring KDFs. It's easy to commit a high-entropy passphrase (say ~10+ random dictionary words) to memory to the individuals who need permission (passed generation to generation). You can clearly document the [key derivation function](http://en.wikipedia.org/wiki/Key_derivation_function) used with the encrypted message. With an OTP, on the other hand you need to keep a secret message of the same length as the total length of all the encrypted messages. – dr jimbob Dec 31 '12 at 18:50
  • To quote [wikipedia](http://en.wikipedia.org/wiki/One_time_pad): "One-time pads solve few current practical problems in cryptography ... Because the pad, like all shared secrets, must be passed and kept secure, and the pad has to be at least as long as the message, there is often no point in using one-time padding, as you can simply send the plain text instead of the pad (as both can be the same size and have to be sent securely)." This fault is only present with the OTP; not with say key generated from a passphrase with a KDF. – dr jimbob Dec 31 '12 at 18:51
  • 2
    That statement is talking about using a OTP for modern cryptographic needs over an untrusted wide-area network, where there is no such thing as "offline data transfer". The key simply must be exchanged securely, and since "securely" translates to "by public key algorithm" over a network, you're right. However, I could meet you in person, give you a OTP, then send you out into the African bush with a simple wireless ham radio, and you could tell me something securely that neither of us knew when we exchanged the OTP. – KeithS Dec 31 '12 at 19:27
  • From a whitepaper on the subject: "Modern crypto algorithms provide practical reasonable security and privacy, essential to our economy and everyday life. However, sometimes you need ever lasting absolute security and privacy, and that's only possible with one-time encryption. Some experts argue that the distribution of large quantities of one-time pads or keys is impractical. However, ... Current data storage technology such as USB sticks, DVD’s, external hard disks or solid-state drives enable the physical transport of enormous quantities of truly random keys." – KeithS Dec 31 '12 at 19:36
  • The OTP has one critical requirement that shakes out from the three critical pieces that define the scheme (key length = message length, truly random, used once); the two parties to the conversation must be able to *physically* exchange OTPs. That makes it infeasible for most of what we use cryptography for today; we transmit untold gigabytes of data securely every second over the Internet, and would need an unworkable amount of pre-exchanged random data to make a OTP work. – KeithS Dec 31 '12 at 19:44
  • However, for one message, encrypted one time, which must not only withstand 100 years of brute force but must also be decryptable in 100 years, the OTP is perfect. You keep saying you could thoroughly document; how much data in the form of documentation would you have to make readily available, in order to describe the decryption process accurately enough that someone could re-implement the algorithm on whatever hardware we're using in 100 years (whether that's optronics, qubits, or - if we bombed ourselves back to the stone age, paper and pencil)? All for one message? – KeithS Dec 31 '12 at 19:49
7

The problem with the future is that you don't know what will happen. We can guess, of course, but you can never get a guarantee.

AES is presumed to be secure, and no known faults exist in the algorithm. In fact, DES (the original government-endorsed cipher) has no known faults in the algorithm either, the only problem is that the key length is too short.

Assuming that 100 years from now, the best known attack against an algorithm is still brute-force, then yes, you can secure your data for that long. Bruce Schneier wrote up an explanation of why 256-bit keys are as secure as physics in Applied Cryptography (pages 157-158). The gist is this:

Assuming cosmic background temperature of 3.2 Kelvin, and an annual solar energy output of 1.21x10^41 ergs, and given the Boltzmann constant of 1.38x10^-16 ergs/Kelvin: We can therefore be certain that if 100% of the Sun's energy output went into a 100% efficient and impossibly fast computer that did nothing but count, it only could get enough power to represent 2^187 values per year. Given a 256-bit key, that means it would take 5.9 * 10^20 years to represent all values in that range.

Schneier's conclusion:

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

So then all you have to do is make sure that the best attack, 100 years from now, is still brute-force. The best way to do that is to use as many algorithms as possible. For example, encrypt with AES with one random key, then pick another random key and encrypt that result with Twofish, then that result with another key with Serpent, and so on. If, 100 years from now, at least ONE of the algorithms is still standing, then your data is secure.

tylerl
  • 82,225
  • 25
  • 148
  • 226
  • 4
    Actually thermodynamics doesn't rule out quantum brute-force of 256 bit keys(using Grover's algorithm) since it only requires 2^128 operations. I don't consider that a major threat, but it's not as clear-cut as many claim. But it does rule out using Grover to break 512 bit keys. | In theory those limits don't apply to [reversible computing](http://en.wikipedia.org/wiki/Reversible_computing), but that doesn't look like a practical threat either. – CodesInChaos Feb 15 '13 at 10:58
  • @CodesInChaos bear in mind the physics of what you're saying: you're saying that assuming reversible computing is actually achievable and consumes absolutely no power at all except to represent 2^128 states, then cracking a 256-bit key will *still* require more energy than reaches the earth in any reasonable amount of time and necessitate a space-based computer (albeit not a full-size dyson sphere). THe odds of getting there within the next 100 years is effectively zero. – tylerl Feb 15 '13 at 15:04
  • @tylerl Assuming quantum computing is achievable, we only need (2^128)*N operations (where N is some fixed amount of computation to perform the decryption once). If (in addition to that or instead of that) thermodynamically reversible computation is possible then we will only need a small amount of energy for full brute-force search (still 2^128*(2N) or 2^256*(2N) cpu-time though). – fiktor Jan 25 '16 at 06:22
  • @fiktor remember the "next 100 years" caveat on this question. That pretty handily rules out any of the sci-fi theoretical bull that people throw around. Shor's algorithm *might* be usable by then, but Grovers algorithm just makes an impossibility expensive computation impossibility expensive on expensive hardware. – tylerl Jan 25 '16 at 15:47
4

Modern strong encryption with key assumptions will be safe for a hundred years and foreseeably longer; e.g., millions/billions of years from brute forcing. That is if you encrypt a message with a high entropy passphrase (e.g., 20 random diceware words at ~260 bits of entropy) with a suitably strong encryption scheme say AES256 (where the passphrase creates a 256-bit symmetric encryption key). Brute-forcing is not the least bit reasonable. Imagine that 10 billion humans each built a million computers (10^16 computers) and each computer tried a billion keys per second (10^9/sec) for the next million years (3x10^13 seconds), you'll have only tried about 3x10^38 ~ 2^128 keys when you expect to need to try 2^256 keys to have a decent chance at brute forcing the encryption. (You can also see that this is the rough limit of brute-forcing 128-bit encryption -- 10 million billion computers trying a billion keys per second for the next million years).

However, I've made key assumptions:

  1. the passphrase is high entropy and remembered by those who need to use and decrypt the message,
  2. the passphrase is kept secret from all attackers (the passphrase is not re-used elsewhere; not key-logged or written down; not given up under forceful interrogation,
  3. there are no fundamental flaws in the particular encryption algorithm you used discovered in the next 100 years that make it tractable (e.g., right now the best attacks on AES256 reduce it to 2^254 (a factor of 4 easier; but still outside realm of feasibility),
  4. The particular implementation is not susceptible to other attacks (side-channel attacks/related-key attacks/known plaintext attacks) that are much easier than brute forcing,
  5. There are no fundamental advances in CS like an easy proof of P=NP that makes NP problems easy, or making practical large scale quantum computing that somehow make this intractable problem tractable. (I don't see how quantum computing would break AES, though I do see how Shor's quantum algorithm for integer factorization breaks RSA).

1 & 2 are your biggest worries. How do you keep the key to a message (that presumably you want someone to be able to decrypt or else just delete it) known to the right people, but unknown to everyone else for 100 years? For this reason, the solution of the One Time Pad (OTP), while perfectly secure in theory is horrible in practice. This says if your encrypted message is say a million characters long, you need to keep the one-time pad of that same length secure and secret from everyone (except the people who need to decrypt the message) for a hundred years. If you can manage to do that trick, why didn't you leave the message in plaintext and then apply whatever protections you did to the OTP to the plaintext message? (While say hiding a 20 word random phrase for a 100 years is semi-feasible if passed down from generation to generation with some mnemonics and maybe hidden reminder messages.)

dr jimbob
  • 38,768
  • 8
  • 92
  • 161
3

I think AES-256 will (even 128 might be feasible), (not taking quantum computers into account yet) proof to be feasible within the next 100 years.

Also don't forget RSA was created in the 70's and we are even still using it now.

EDIT: Notice

RSA isn't a good example actually. Key sizes touted as unbreakable in the early days are now pretty weak, and bad or absent padding in early implementations causes issues as well. | It's also hard to compare asymmetric and symmetric primitives. They have pretty different security characteristics. – CodesInChaos

Lucas Kauffman
  • 54,169
  • 17
  • 112
  • 196
  • ... But not with the same key lengths or padding schemes that we used in the 70s. It isn't just the conceptual algorithm, but the specific implementation, that must stand the test of time. – KeithS Dec 22 '12 at 00:07
  • Of course, but at the moment you are aware of that. So what you do is you take the length you suppose will be safe in 100 years, you quadruple it and you should be safe. – Lucas Kauffman Dec 22 '12 at 00:14
  • RSA isn't a good example actually. Key sizes touted as unbreakable in the early days are now pretty weak, and bad or absent padding in early implementations causes issues as well. | It's also hard to compare asymmetric and symmetric primitives. They have pretty different security characteristics. – CodesInChaos Feb 15 '13 at 11:01