Has anyone invented this type of crytography? Is it even possible?

[Saffer]

I was reading the other thread on cryptography and was wondering if the following is possible:

You have some information you want to keep secret. You also have some other data that you don't really mind if someone finds. Is there an encryption algorithm that takes your secret data and your real password, and your decoy data and decoy password, and then ecrypts it in such a way that if someone finds the encrypted file and compels you to reveal the password, you can reveal the decoy password which they can use to decrypt the file. Once decrypted they will have your decoy file and hopefully assume that it is the real one. I realise this is a little like steganography but not quite.

I think I can see a way to make it work but your "passwords" will need to be as long as you decoy file, which needs to be at least as large as you real file.

[Lumpy]

Offhand I'd doubt it because the encrypted file (the real data plus the decoy data) would be a lot larger than the decoy data, and somone would wonder what the huge amount of overhead was.

[Saffer]

Originally Posted by Lumpy

Offhand I'd doubt it because the encrypted file (the real data plus the decoy data) would be a lot larger than the decoy data, and somone would wonder what the huge amount of overhead was.

I think I can see a way to make it such that the encrypted file is the same size as the decoy file, but the password would have to be that size also. In that case someone would wonder why you used such a large password.

[Mangetout]

Originally Posted by Saffer

I think I can see a way to make it work but your "passwords" will need to be as long as you decoy file, which needs to be at least as large as you real file.

I think that's the crunch. You want an encrypted file that unpacks into two different, specific, coherent results depending on the key.

I think this means something has to get bigger - either the encrypted file (in its simplest form, the data could just be interleaved somehow). Otherwise, the key has to do 'work' on the encrypted file, and thus would need to be longer (and in fact would just be part of the encrypted load).

Compression theory applies here too - you just can't guarantee to be able to fit twice the normal amount of information in the same container.

[tellyworth]

Yes. Truecrypt does this.

[Mangetout]

Right, but only by essentially concatenating the real and dummy loads.

[Saffer]

To give a demonstration:

Your real data is "real". Your decoy data is "fake". You decide to make your real password "abcd".

The encryption algorithm takes the letters of your password and turns them into numbers. In this case "abcd" becomes "1;2;3;4". The algorithm then shifts each letter in your real data by the corresponding number. "r" is shifted by 1 so becomes "s". "e" is shifted by 2 so becomes "g" and so on till you get the ecrypted version: "sgdp". The algorithm then works out what password would be required to decrypt "sgdp" into your decoy data "fake". In this case to get to "s" from "f" requires a shift of 12. "a" to "g" is 6 places. "k" to "d" needs to go past "z" so would need 19 places. "e" to "p" is 11 places. The numbers together are "12;6;19;11" and the corresponding letters are "lfsk". This is your decoy password.

So in this case your encryped data is "sgdp". If I give you the password "lfsk" then you will decrypt to "fake". If I give you "abcd" then you will decrypt to "real".

[kferr]

You could mix a sort-of one time pad with a normal symmetric cipher. Take your secret message "attack at dawn" and XOR it with you same-length fake message "dogs hate cats". The result is your real secret key, keep it safe. You then encrypt "dogs hate cats" with gnuPGP or whatever.

The problem with this (and all encryption schemes, really) is the key management. If you real secret key is lost or compromised then you're screwed.

[Mijin]

Originally Posted by Lumpy

Offhand I'd doubt it because the encrypted file (the real data plus the decoy data) would be a lot larger than the decoy data, and somone would wonder what the huge amount of overhead was.

I think in many contexts you'd get away with it. Encrypted files are often not the same size as the originals and the difference depends on configuration (e.g. in PGP you can choose whether to compress prior to encryption).

If you're a suspected terrorist or something, then probably someone would take note of the file sizes and do a detailed analysis. But in many other situations I don't think people would be that thorough.

[FasterThanMeerkats]

I have to think once word gets out that there's a decoy method or if the decoy data doesn't mesh with expectations or you gave up the password too easily, then people just "compel" you to give the real password.

Bottom line, if it's at the point that you're being interrogated for a password, you've probably already lost.

XKCD Link

[Mijin]

Having a decoy is not going to make the files less secure though. The OP is not suggesting it is a perfect, uncrackable method.

[si_blakely]

Originally Posted by tellyworth

Yes. Truecrypt does this.

Originally Posted by Mangetout

Right, but only by essentially concatenating the real and dummy loads.

Truecrypt claims to provide plausible deniability, allowing you to provide a password that opens the volume and expose some selective data (i.e. embarrassing porn, with the hidden partition containing plans for world domination). The additional data within that partition can be unlocked with a second password, but there is no evidence that the second hidden partition is there. This means that the data is entirely unprotected - if someone completely fills the outer container without unlocking the inner one, the data in the inner partition will be destructively overwritten with no possibility of recovery.

So the interrogator forces you to open the outer container, and looks at your porn (and scans it for steganographic data). He then asks you if there is another hidden partition.
You say no, so he says, "ok, I'm just going to backup your porn and then format the partition" while watching your face. They don't get your secret plans, or even know that you have them, but you do not have them either. They just need to watch you until you slip up recovering your plans. And some people will not be able to hold a straight face, particularly if the data is especially important to them and there is no backup. Once they determine or suspect that there is additional data, your plausible deniability is out the window. And the interrogator fishes in his wallet for a fiver...

Si

[iamthewalrus(:3=]

Originally Posted by si_blakely

So the interrogator forces you to open the outer container, and looks at your porn (and scans it for steganographic data). He then asks you if there is another hidden partition.
You say no, so he says, "ok, I'm just going to backup your porn and then format the partition" while watching your face. They don't get your secret plans, or even know that you have them, but you do not have them either. They just need to watch you until you slip up recovering your plans. And some people will not be able to hold a straight face, particularly if the data is especially important to them and there is no backup. Once they determine or suspect that there is additional data, your plausible deniability is out the window. And the interrogator fishes in his wallet for a fiver...

Sure, and if they pull out a gun and shoot you, your cryptography won't save you from that either.

You've invented a threat (loss of data) that cryptography is not intended to solve, and pointed out that it doesn't solve it. And, in fact, it's a problem that's mostly obviated by the fact that encryption doesn't exist. The solution to losing the only copy of your data is to have backups that the bad guys can't get to. Before good encryption, it made sense to have only a few copies of sensitive data, and to guard them carefully, since any copy could be leaked and reveal you. If you have strong encryption, then there's little cost to having a bunch of copies of your secure data. The thing you have to keep secret is the key.

The problem cryptography is intended to solve is keeping an adversary from finding out the contents of the data. Only a particularly foolish criminal would be dismayed that his data was being deleted in front of him. Once the adversary has your storage medium, you can't ever trust it again. Furthermore, it would take a particularly foolish adversary to actually delete the only copy they have. You may have backups. If they delete their copy, then all they've done is limit their chance to later decode it.

[md2000]

The "hidden volume" trick is basically this - Truecrypt creates a volume that looks like a blank disk. then you copy a file into it. So the "extra space" just looks like you created a far too big disk and a lot of it is blank. Disk space is cheap nowadays, so creating a 10GB encrypted disk to hold a few 100MB files is not unusual, on a 1TB drive.

If they overwrite it and you lose it - well, shoulda made backups. If they got all those too, or if they destroy them trying to get you to reveal them - presumably given a choice between losing the data and revealing it, losing is preferable?

[septimus]

As others pointed out, it's doable with either passwords as big as the data, or decoy data much bigger than secret data. But OP wants secret data with size that is a sizable fraction of decoy data, and smallish keys.

I think this might be possible, but may require a clever algorithm and flexibility (e.g. selective spelling errors or made-up numbers) in the decoy data. As a very simple example, employing a form of steganography, write your secret message, encrypt and insert blanks; then fill in the blanks with decoy text (with misspellings as needed). Here's a trivial example:

• 1 Secret message
• 2 encrypted
• 3 padded
• 4 decoy text added
• 5 decoy (and secret) encrypted again

1 SEND MORE MONEY
2 RAPY HISA HIPAD
3 R....A....P....Y.... .... H....I....S....A.... ....H....I....P....A....D....
4 Read and apprecyated stop hope ida is dreaming of the ski trip please, do you?
5 Ernq naq nccerplngrq fgbc ubcr vqn vf qernzvat bs gur fxv gevc cyrnfr, qb lbh?

(Ignore that in 3 minutes I could concoct only a nonsensical decoy. In practice some brilliant computer algorithm would be used. ... Perhaps pretend the decoy is output of Google Translate. )

Here the size of the secret is only 20% of the decoy's size. As that percentage increases, more cleverness is required (or more flexibility in decoy text).

[ticker]

I recall from some years back a method that hid data in a portion of an image. The actual data was represented as noise in some unimportant portion of a photo. If normally encrypted first with some good encryption scheme the data should be indistinguishable from random and undetectable. A rather busty woman was touting such a system as this with the data hidden in somewhat racy pictures of herself! Obviously the success of this is scheme is in the attacker not knowing the scheme you are using. Cryptographically speaking it is considered a bad idea to rely on secret methods - far better to use well-known methods with easy to keep secret keys.

[xnylder]

One very old-fashioned code could do this. A book code requires each spy to keep a copy of the same edition of the same book, preferably something with a broad vocabulary. The code is actually a series of numbers corresponding to page number, paragraph number, word number. For example, if the book is a King James Bible (we'll ignore the opening pages) then (1,1,3) (1,1,1) means "beginning in". In theory, you could keep an extra series of dummy numbers that decodes to an innocuous message.

[iamthewalrus(:3=]

Originally Posted by xnylder

One very old-fashioned code could do this. A book code requires each spy to keep a copy of the same edition of the same book, preferably something with a broad vocabulary. The code is actually a series of numbers corresponding to page number, paragraph number, word number. For example, if the book is a King James Bible (we'll ignore the opening pages) then (1,1,3) (1,1,1) means "beginning in". In theory, you could keep an extra series of dummy numbers that decodes to an innocuous message.

I don't think that is what the OP is asking about. In a book code, the book is the key, and the sequences of numbers are the cyphertext.

In any (useful) coding scheme, you can encrypt multiple different messages using the same key. That's what you're describing. But the OP wants the opposite: One cyphertext that can reasonably be decrypted using two different keys.

You could do this if you had two different shared books and could come up with a set of word references that meant one thing based on one book and something else when based on another, but this would be much harder than just encoding things once. In order to reliably encode messages in a deniable way, you'd need some sort of concordance that showed which words you could use in one book that would map to words in another book.

[Dewey Finn]

Originally Posted by ticker

I recall from some years back a method that hid data in a portion of an image. The actual data was represented as noise in some unimportant portion of a photo. If normally encrypted first with some good encryption scheme the data should be indistinguishable from random and undetectable. A rather busty woman was touting such a system as this with the data hidden in somewhat racy pictures of herself! Obviously the success of this is scheme is in the attacker not knowing the scheme you are using. Cryptographically speaking it is considered a bad idea to rely on secret methods - far better to use well-known methods with easy to keep secret keys.

I think you're thinking of steganography, but an expert will notice that the file size is too large to be just a picture and will then attempt to find the hidden data.

[bup]

I think one could also do it so long as the data (both the real and the decoy) was limited to 255, but stored in a 'wide-character' 64-bit encryption. You could encrypt everything, and store the real data in the two high bytes and the decoy in the two low bytes, and decrypt according to whichever password.

[KneadToKnow]

A simpler implementation would be a decryption program that with a secondary password simply returned gibberish from the encrypted data with the error "Unrecoverable error: Encryption failed, restore from backup."

[RaftPeople]

Originally Posted by Mangetout

I think that's the crunch. You want an encrypted file that unpacks into two different, specific, coherent results depending on the key.

I think this means something has to get bigger - either the encrypted file (in its simplest form, the data could just be interleaved somehow). Otherwise, the key has to do 'work' on the encrypted file, and thus would need to be longer (and in fact would just be part of the encrypted load).

Compression theory applies here too - you just can't guarantee to be able to fit twice the normal amount of information in the same container.

I could be wrong (this is just a gut feel), but it seems that the resulting file doesn't necessarily have to be larger but the trade-off is compute time to determine the two transformations with minimal keys that arrive at the desired outcomes.

[Stink Fish Pot]

This is the Zodiac speaking,

Maybe I'm not reading this correctly, but isn't this what PGP essentially did? It made each user have a public key and a private key, so the public key could be compromised without losing the encrypted data.

Or are we talking about a way to encrypt data that, if the key is compromised and the data is decrypted, it will in actuality still be hiding the REAL secret message?

Sorry if I've confused the issue more. I am not sure I've understood the OPs requirements.

[Enola Straight]

What if you used some kind of palimpsest encryption?

Take a file of apparently random noise, a simple image, a musical sample, etc, and apply a password to get a message hidden in the data.

Apply another password to THAT and get an even more deeply buried message...ad infinitum.

[septimus]

Originally Posted by Dewey Finn

I think you're thinking of steganography, but an expert will notice that the file size is too large to be just a picture and will then attempt to find the hidden data.

Not really. Here's a very simple steganography method for Jpeg that will reduce an image's size (slightly) and actually improve the image's SNR!

The count of odd coefficients in a Jpeg block will be either even or odd. Concatenate those count parity bits to form the secret message. This might mean the secret is less than 1% the size of the Jpeg file (say, 1 bit per 64 pixels), a problem with all steganography techniques.

Starting from the unaltered Jpeg (and having its higher-precision form available for the algorithm), half the blocks will need their odd/even sense flipped to yield the desired secret message. Flip, when needed, whichever coefficient is closest to threshold, so its change will have minimal effect on image quality. In many cases the best flip will be to change a +1 or -1 to zero -- a change which will actually improve SNR, though only the best (non-steganographic!) Jpeg compressors take advantage of the idea.

[si_blakely]

Originally Posted by iamthewalrus(:3=

You've invented a threat (loss of data) that cryptography is not intended to solve, and pointed out that it doesn't solve it. And, in fact, it's a problem that's mostly obviated by the fact that encryption doesn't exist. The solution to losing the only copy of your data is to have backups that the bad guys can't get to. Before good encryption, it made sense to have only a few copies of sensitive data, and to guard them carefully, since any copy could be leaked and reveal you. If you have strong encryption, then there's little cost to having a bunch of copies of your secure data. The thing you have to keep secret is the key.

The problem cryptography is intended to solve is keeping an adversary from finding out the contents of the data. Only a particularly foolish criminal would be dismayed that his data was being deleted in front of him. Once the adversary has your storage medium, you can't ever trust it again. Furthermore, it would take a particularly foolish adversary to actually delete the only copy they have. You may have backups. If they delete their copy, then all they've done is limit their chance to later decode it.

I never said that the interrogator destroyed their only copy - they may have destroyed the suspects only copy.

People tend to equate hidden with safe - in the case of a hidden partition, this is not true. It is also not true of a bunch of other things, like money in a mattress, but people do it all the time.
People also do not maintain backups, and are less likely to do so when it takes considerable work, like maintaining encrypted copies. The corollary is also true, multiple copies of encrypted data make it more likely that the data is important.
Some people get emotionally invested in their data. Particularly if the data in question is personal and specific and not able to be recovered or represents a great deal of effort. I have heard that in the case of something like child pornography, this attachment to the material can be extremely strong, and can override self-preservation.

Encryption is intended to raise the cost of accessing data without the specific key - no encryption is immune from a brute-force attack, but the cost/time of that attack is expected to be higher than the value of the encrypted data. But knowing that there is possible data to be found is often as important as the data itself. And sometimes people reveal more than they intend.

Si

[Mangetout]

Originally Posted by RaftPeople

I could be wrong (this is just a gut feel), but it seems that the resulting file doesn't necessarily have to be larger but the trade-off is compute time to determine the two transformations with minimal keys that arrive at the desired outcomes.

Yes, but only for some cases - in others, the result of the computation will be that no minimal key is possible. If it were otherwise, we'd be able to encode any amount of data into a finite space.

[Mangetout]

Originally Posted by Enola Straight

What if you used some kind of palimpsest encryption?

Take a file of apparently random noise, a simple image, a musical sample, etc, and apply a password to get a message hidden in the data.

Apply another password to THAT and get an even more deeply buried message...ad infinitum.

That's exactly what the OP is asking, but it's not possible.