2

Suppose you encrypt a list of names of Americans with a 512-bit secret-key algorithm. Currently no supercomputer can break it, but someday a supercomputer might exist that could iterate through all possible keys and find a key that decrypts the list to what sound like American-sounding names, and when you find that, you know you've probably got the right key.

Is there a term for secret-key encryption where many possible keys will decrypt the ciphertext to realistic-looking plaintext, so the encryption can never be brute-forced, because even if you find a key that decrypts to one of the realistic plaintexts, you won't know if you got the right one? (And thus, presumably, the encryption could be done with a shorter encryption key, since it can't be brute-forced anyway.)

A one-time pad would have this property, of course, but presumably so could other systems.

Say, instead of storing a list of American names, you come up with an index of every American first name and every American last name. Then when storing the firstname-lastname pairs, you store them as pairs of numbers. Then any key that decrypts the ciphertext to a list of numbers will thereby decrypt to a list of names. (Except, you'd need to do more work than that, because some names are more common than others, so the attacker could try to find a key which decrypts to a list where the names follow the expected distribution. But that's the idea.)

So does this have a name? Many-plaintext encryption or something?

Improve this question

2 Answers 2

Reset to default
3

That reminds me of the concept of encryption that offers Plausible Deniability, aka "Deniable Encryption" which has the following property:

Deniable encryption makes it impossible to prove the existence of the plaintext message without the proper decryption key. This may be done by allowing an encrypted message to be decrypted to different sensible plaintexts, depending on the key used. This allows the sender to have plausible deniability if compelled to give up his or her encryption key.

The commonly-cited use for this is at airports: have two operating systems steganographically overlapped on the same hard drive. When airport security asks you to boot up your laptop, enter the decryption password for the "innocent" OS. Even if they forensically examine your laptop, nobody would guess that there's a second OS hiding in plain sight.

Thanks to @JamesMishra for pointing out in this post that:

TrueCrypt had a similar hidden operating system feature where the TrueCrypt bootloader would accept two different passwords, giving access to two different operating systems. The hidden operating system was concealed with a bit of clever steganography.

Second, let's talk about this:

someday a supercomputer might exist that could iterate through all [2512] possible keys and find a key that decrypts the list

I see where you're coming from, but brunt computing power alone isn't enough. See this answer of mine for math showing that counting from 0 to 2208 would require you to consume the energy equivalent of the sun.

The YouTube channel 3Blue1Brown has an excellent video showing just how mind-bogglingly large the number 2256 is.

In summary:

2^256 = (4 billion) x (4 billion) x (4 billion) x (4 billion) x (4 billion) x (4 billion) x (4 billion) x (4 billion)

Counting from 0 to 2256 would require: a GPU capable of doing 4 billion ops/s x 1 kilo-Google's worth of servers x 4 billion people each having their own personal kilo-Google's worth of servers x 4 billion copies of the planet Earth x 4 billion copies of the Milky Way x 37 time the age of the universe. And we're still missing one more factor of 4 billion. Yeah, 2256 is an unfathomably large number.

Your intuition is not entirely wrong though; over time we do get better at cracking encryption keys, but that has more to do with advances in understanding the mathematics of a specific encryption algorithm that let us narrow in on likely keys, but brunt computer speed alone won't even get us there.

Improve this answer
18
  • Does your analysis take quantum computing into account -- i.e. is it possible that quantum computing would offer a practical way to brute-force the password, notwithstanding everything you said? (I know nothing about quantum computing except for hearing that it makes brute-forcing much easier.)
    – Bennett
    Commented Sep 9, 2018 at 22:17
  • Regarding the "duress password" for booting up your laptop, this technically doesn't meet my requirement because of the attacker did make an image of your disk and a virtual simulation of your laptop, they could still use brute-force to find the two passwords that lead to two different operating systems, and then they could probably guess which was the one you were trying to hide.
    – Bennett
    Commented Sep 9, 2018 at 22:19
  • @Bennett Quantum computers give a square-root speedup, so cracking a 512-bit key takes 2^256 quantum ops, cracking a 256-bit key takes 2^128 quantum ops. But doing 128 quantum ops (ie cracking a single key) would still consume the power equivalent of the sun's output for 30 years.
    – Mike Ounsworth
    Commented Sep 10, 2018 at 13:03
  • An important property of a cipher is that the cipher text (or equivalently, decrypting with the wrong key) is indistinguishable from a random string. If you take a string at random, there's a 99.99...% chance that it's unintelligible. You seem to want a cipher where the wrong key gives you intelligeable text with high probability. This would make it vulnerable to all sorts of statistical attacks, and therefore a terrible cipher. So I think what you want is a duress key system, but with many duress key / data pairs. (still unsure why you want this, a 256-bit key will not be guessed, ever).
    – Mike Ounsworth
    Commented Sep 10, 2018 at 13:09
  • take the example that I used in the post -- rather than storing people's first names and last names, make a list of all possible first names and last names and then store a list of indexes into that list. If that's the format of your plaintext, then decrypting with the wrong key will still give you "intelligible" plaintext -- it will be a list of numbers which are indexes into those lists, it just won't be the right names.
    – Bennett
    Commented Sep 11, 2018 at 5:44
0

The word you may be thinking of is a duress password, one that is given when you suspect or know you are being monitored.

It is possible to provide two different plaintexts from the same ciphertext, by using a true One Time Pad with XOR. (For text, this can also be done with a classical Vigenere cipher.) But this requires a key as long as your message. That works for short text messages, but isn’t practical for something like a disk image.

Improve this answer
1
  • I know about duress passwords but it's not exactly what I'm looking for because, for example, there is usually one "real" password and one "duress" password, and if a brute-force effort found both of them, the attacker could usually guess which cleartext was the one you were trying to hide. I'm talking about systems where there are so many possible plausible plaintexts, depending on which decryption key you use, that the attacker can't guess which one is real.
    – Bennett
    Commented Sep 9, 2018 at 22:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .