Does Cracking Encryption Involve Some Precognition?

jcapell asks: "Let's say I sent an encrypted message using any method that could normally be 'cracked' relatively quickly using brute-force or complex algorithms. Wouldn't any decoding require some minimal knowledge of the format of the contents? What if I (for example) printed out my message, took a photo of the text with a digital camera, and then ran the resulting .jpg file through rot-128? How would an unintended recipient know where to start decoding the message?"

Re:Fundamentals of encryption

[jbert]

But if (following your decrytpion attempt) you can decompress...then you probably succeeded in the decryption - result!

Which gives us an interesting (practical) weakness in the question-asker's proposal. It is no good obfuscating your file format if it is then going to be wrapped in a standardised compression format by the (pre-processor to) the encryption algorithm.

A good related reference...

[lazlo]

A fairly recent CryptoGram had a link to an answer very close to this question. On counterpane [counterpane.com] Schneier goes through a good description of what is called the "unicity distance" of plaintext. In order to test how good an algorithm is, you try and break it with known plaintext attacks. (Or even more intrusive attacks that you will rarely see in the wild, such as chosen plaintext attacks, or chosen ciphertext attacks) If you can't break these, then it's unlikely that you can break the algorithm with an unknown unchosen plaintext/ciphertext pair. If you're attacking a ciphertext in the wild, then the more you know about your target, the easier it is. With english text, you can brute force attack it if you have more than the unicity distance of ciphertext to work with. Your brute force cracking engine should look for several things, including the headers (such as the magic numbers for jpg files) and things that "look" like english (or some other language) text, and probably even apply some of the tests of randomness that one poster earlier mentioned. Of course the interesting thing is that truly random data has an infinite unicity distance, so to make decrypting your messages to [e-mail] really frustrating you might add a cron job something like:
*/5 * * * * if [-f $HOME/message-to-send.txt]; (gpg -$OPTIONS &lt $HOME/message-to-send.txt | mail -s "message" [e-mail]); else (dd if=/dev/urandom bs=1024 count=1 | gpg -$OPTIONS | mail -s "message" [e-mail]); fi
(please pardon if this won't actually run... I'm on a windows box and don't have my man pages handy - but you get the general idea...) Just make sure your message is exactly 1k, set up the appropriate procmail on the other end and... probably nothing. Chances are no one will care, and if they care enough, they'll just put a keyboard sniffer on your machine, find out your password, log in as you, and read your mail anyway. Always remember, you can't win, but sometimes it's fun to try and think of interesting ways to try.

Without precognition

[backslashdot]

The best thing to do is to photograph some misleading text, and then pass that jpg thru steganography software that secretly adds a hidden ascii text message. After that you rot-128. When an enemy cracks it, she will view the jpg and believe she's viewed your message, when in actuality the message is hidden in the binary of the jpg itself. Good steganography software doesnt affect the quality of the jpg being viewed. Also, without precognition, you dont even need to rot-128 it. Or not just have a english text file, and skip the jpg? A person or machine that has no idea of what to look for has to be able to determine at the very least that plain english words are not the correct message. A good cryptanalyst knows that regular text can contain hidden messages. A cracker has to know to look for these subliminal channels. Usually you can figure it out because sometimes the faked message doesnt make sense or sounds like a wierd poem when read. Experience counts there. Basically all forms of decryption require some understanding of what is being searched for and whether the "decryption" is valid.

Re:not to mention

[demaria]

You could also arrange a meeting in a sealed bunker underground (or something less dramatic of course) and predetermine what key and scheme to use.

Of course, crypto analysis assumes that the encryption scheme is public or will be figured out.

Cipher

[PatJensen]

As long as you know the cipher used to encrypt the contents, you have enough to get started. You can then look for points of vulnerability, level of encryption, type of encryption and apply whatever method to break that cipher.

Long day....

-Pat

Security through nostalgia

[Max Webster]

I always fantasize about stumping the world's best cryptanalysts by using software that only exists on out-of-production or slow computers. Instead of JPG, use some image format particular to Commodore 64s. Then embed the result inside an Apple II spreadsheet. And so on and so forth.

Even assuming the NSA can make sense of a giant pile of mid-80s shareware disks that they might confiscate from you, all the decoding software runs at a comparative snail's pace, making it impractical to try a large number of combinations. (Or do crypto agencies have VIC-20 and Timex Sinclair emulators running on Crays?)

Re:Dear Slashdot,

[Pogue Mahone]

Dropping a large object (like an anvil) on them from a great height will normally work.
--

It's lossy.

[cryptochrome]

The most important thing here is that your original text message is now a picture. You still need another decoder (the brain) to extract the original information, which can NOT be done on your computer (not well anyway).

The approach would therefore be centered on breaking your encryption technique. If I had access to an encoder and decoder, even without knowing how it works, I would know that I should be looking for images. In that case I would compare the encoded file with the decoded image and ignore the original text. Determining that it was rot-128 would be a fairly simple matter.

Re:Same as a machine

[Matthew Weigel]

That's what makes symmetric encryption algorithms so useful. You allow someone the ability to decode your message without giving them the ability to encrypt a message as you.

Errr... I think you mean asymmetric encryption. Symmetric algorithms use the same key for encryption and decryption, so there is no difference between sender and recipient.

If you have a block of encrypted data

[Zachary Kessin]

And have no idea what method of encryption was used and what the "plain text" should look like you may have a very tough time. It may even be imposible as when you do decrypt it you may not even know depending on the data.

Many things like the number stations on short wave will probably never be decrypted for that very reason, ofcourse in that case there may not be any data at all it could just be random numbers most of the time.

Decoding?

[SEWilco]

"If I printed out my message, took a photo of the text with a digital camera, and then ran the resulting .jpg file through rot-128? How would an unintended recipient know where to start decoding the message?"

Start with a copy of "Codes & Secret Writing" or any other introduction to coding and decoding. The standard procedure is to find some weakness, decode what is weakened, then repeat the process. The classic example in text decoding is to look for patterns which represent the most common letters and words in the language which is probably being used. Basically, if you have to ask this kind of question then you shouldn't be trying to create an encryption algorithm. It's not easy to create something which is at all secure.

Although I'm not familiar with the format of a .jpg file, there probably is a certain pattern near the beginning due to the definition of the compression patterns. (Yes, I'm ignoring the actual header which announces the file type -- that's too easy) Someone who does this for a living would recognize that type of pattern hiding behind simple encryptions of this type. There probably are some sort of record markers which separate each chunk of the picture, and the pattern of those markers would also reveal clues to the encryption. JPEG also uses compression, and the codes used to indicate reuse of compressed values would also provide patterns (ie, the green in a field of grass may provide a cluster of patterns).

I once had to deal with an encrypted mail system which was being used by thieves. The programmer of the mail system had used a standard library routine which sometimes left a space at the end of a line of text. It was easy to see the patterns of those spaces, and from the way the spaces were encrypted the encryption algorithm and its key were easy to find. The program was available, so the encryption algorithm could have been extracted from the program, but it wasn't necessary to do so -- although the program was also studied later to confirm that it was understood properly.

Re:Fundamentals of encryption

[yamla]

Sorry, I should have rewritten that bit. What I mean is that you have cyphertext file A. You try key 1 and get file B out. Is file B random-looking? If so, it is not the 'plain-text' file you are looking for. You try key 2 and get file C out. File C is not random-looking and is rather compressible. It is therefore all but guaranteed to be the 'plain-text'.

I am assuming that the decryption attempt also uncompresses the file.

--

You're right

[bob_jenkins]

Random noise has several testable statistical properties. All n-bit values appear about equally often, if this n-bit value is x the probability that the next n-bit value is x is 2^^-n, and so forth. The longer the message, the more exactly these probabilities can be tested.

Almost all possible messages pass the tests for random noise. Almost all sets of data that people care about do not pass the tests for random noise. So, the cryptanalyst applies these tests and looks more carefully at any decryption that doesn't pass the tests for random noise.

Knowing what encryption method was used or what message is being sent helps immensely, though.

Re: JPEG Specs

[Rabenwolf]

How does your computer know that a jpeg is a jpeg?

A good place to start for this question would be the Usenet JPEG FAQ [faqs.org]; the question is answered here [faqs.org].

Cryptanalysis

[bgalehouse]

There is, in fact, an entire study of how to draw order from the seeming chaos that is a encrypted message. Various types of spectrums can be taken. The book "Between Silk and Cyanide [barnesandnoble.com]" uses this study as a backdrop in such a way as to give a good feel for it. In some sense, it isn't so different than a crossword. There is both a lot of art, and a lot of science in it.

It is more difficult to develop a sense for this when considering non-text input. It is more difficult to see how it could work when using modern cyphers. But the principles are the same.

Any particular type of message will have some standard formatting information, some patterns that the cryptanalyst can look for. The modern, popular, RC4 stream cipher does have a perceptable bias [cluefactory.org.uk] in the stream of numbers produced. So hope is not lost with modern cyphers.

not to mention

[wmulvihillDxR]

If you want someone else to decrypt this message you need some way of communicating to them on what to do to decrypt it. How do you tell them? Another encrypted message? Recurse ad infinitum.

This is the reason why Public-Key is so popular.

Precognition is my secret

[Anonymous Coward]

I crack encryption with a time machine. Whenever I fail to crack encryption, I send a message to myself back in time saying not to try that particular method. When I get the message, I try any other method. When that fails, I append that method to my original method and send that back in time. I continue doing this, the list growing with more and more failed attempts. Now when I start the task, I have a long list of things not to try. When I try a method not on the list that turns out to be successful, I send a message back to myself with the successful method, and I'm done. All that information about successful and failed attempts comes from a vanishing loop of virtual time, and because of this policy whenever I need to crack something I get a message telling me exactly what to do. If I'm really feeling ambitious, I can brute-force 128-bit keys this way.

By the way, if you're thinking of trying this, you should be aware that I patented it in 2079.

Recognizing Plaintext

[Tim Dierks]

The problem you are describing is the problem of how to recognize plaintext; when we stumble across the correct decryption key, how can we recognize it?

The first part of the answer is that, for security analysis purposes, we generally assume that the attacker knows what system we're using, starting with what the encryption algorithm is, but including the type & format of the messages. If the attacker knows you're sending a rot128 jpeg image, she can just reverse the process to recover the message (or test a key for correctness).

If you believe that an attacker will not know these details of the system, you will add to security, but watch out: the secret of the system can be pretty easily divulged, and even if the attacker doesn't know the secret of the system, it's pretty hard to estimate how hard it will be to guess it. (For example, every rot-128'd JPEG file will begin with the bytes 0x7F 0x68; sooner or later, someone is going to notice and figure it out.)

Fundamentals of encryption

[yamla]

The fundamental assumption of strong encryption is that the attacker knows everything except the specific secret key. The algorithm should be secure regardless. This is true for things like one time pads, Triple-DES, etc. etc. provided the secret key is long enough.

Certainly obfuscating the decryption adds some security, but this is only security through obscurity. It adds less additional security than keeping the encryption algorithm secret. It adds far less than choosing a decent key-size. Heck, it adds less additional security than adding a single bit to the secret key, probably.

The basic problem is that you can never trust security-through-obscurity. If I am protecting trade documents, for example, I may be able to keep my secret key secret but I'm not likely to be able to protect the details of the algorithm (here I'm counting the algorithm itself and the additional obfuscation at the end) because ex-employees or partner companies or some such will necessarily need details of the algorithm.

On top of that, unless your obfuscation is truly secure, you can tell when you've decrypted most files. Most files compress. By definition, strongly-encrypted files do not. So you could see how much entropy is in your test decryption. 8 bits per byte? Then you probably haven't successfully decrypted yet.

--

Same as a machine

[stubob]

How does your computer know that a jpeg is a jpeg? Somewhere in the hex is a tag that says what it is (the infamous CAFEBABE, for example). Some people just seem more able to pick up common elements. I'd imagine that a real code breaker would brute force a bunch of methods (rotX, XOR, etc) and see if anything looks familiar. Kind of like the code breaking scene in (IIRC)'Clear and Present Danger' where guy starts using 'Birthday, wife's birthday, etc.' and surprises Harrison Ford.

What you are proposing is basically a one-time pad, though. The receiver can't decode it either without knowing how you encoded it. Just like you couldn't decode it without knowing how you encoded it. That's what makes symmetric encryption algorithms so useful. You allow someone the ability to decode your message without giving them the ability to encrypt a message as you.

Where are your finite variables?

[dmorin]

Ok, your file exists in a finite system where you have 8bit bytes:

1. Look for magic numbers and header info to see if the file is of a known format.
2. If not, execute rot X on it.
3. Repeat while X It would be a quick test. Does that imply that the person knew you'd rot'd it first? Nope -- just that if you've got a finite variable over which you can test (mod the size of your byte) then at one point or another you should test it.

   Even in an astronomically huge system, that's a good place to start. When you have a crypto puzzle in a magazine to solve, what's the first letter you look for? A or I, because you know that those are your 1-letter words (assuming that you know that your puzzle consists of english words in the first place). Then E because it's most common, and so on. Wherever you can get a hook, you don't lose anything by trying it out.

   Think of it as a variation on "your security is only as strong as the weakest link." In this case, what could give you away is the 8bit nature of your data. Not to mention potential patterns in the nature of the image (don't many image file formats have large sections of constant data if you were to dump them out?)

Re:Fundamentals of encryption

[torinth]

The fundamental assumption of strong encryption is that the attacker knows everything except the specific secret key. The algorithm should be secure regardless. This is true for things like one time pads, Triple-DES, etc. etc. provided the secret key is long enough.

Certainly obfuscating the decryption adds some security, but this is only security through obscurity. It adds less additional security than keeping the encryption algorithm secret. It adds far less than choosing a decent key-size. Heck, it adds less additional security than adding a single bit to the secret key, probably.

The basic problem is that you can never trust security-through-obscurity. If I am protecting trade documents, for example, I may be able to keep my secret key secret but I'm not likely to be able to protect the details of the algorithm (here I'm counting the algorithm itself and the additional obfuscation at the end) because ex-employees or partner companies or some such will necessarily need details of the algorithm. All Good points. Except:

On top of that, unless your obfuscation is truly secure, you can tell when you've decrypted most files. Most files compress. By definition, strongly-encrypted files do not. So you could see how much entropy is in your test decryption. 8 bits per byte? Then you probably haven't successfully decrypted yet.

For the exact reason you mentioned, strongly-encrypted files do use compression. It provides a higher entropy before the data goes in. Compressed data is effectively random data, and there's nothin wrong with encrypting random data. The only thing I can imagine you mean is that strongly-encrypted files, in the purist sense, are uncompressed. But certainly in Practical applications (hehe. shameless plug: Cypherus [cypherus.com]), the content is compressed when encrypted.

-Andrew