1

I wrote a huffman encoding program that can compress and decompress files. The file contains a header which contains information that allows me to retrieve the huffman tree.
I wanted to add a simple encryption/decryption feature to my program. I was wondering which way is better:
1. Encrypt the whole file. The problem with that is that people can figure out my header pretty quickly (relative to the 2nd way), as it is a maximum of about 1KB.
2. Encrypt everything but the header. That way, the attacker has the huffman tree, but it's useless unless he can find the right key to decrypt the content. And how will he do that, he can't just simply see if it's plain text or binary (simplified), he has to decompress it with the huffman tree, which will require more time.

I think the second way is better.
Is there something I'm missing here?
(Please don't tell me to use a modern algorithm or something like that, this is a hobby project and I want to code it myself)

Thanks.

Improve this question
7
  • 2
    Encrypt the whole file. The contents do not matter and you want to leak as little info to an attacker as possible. In fact I wouldn't be surprised if you could figure out the file's contents under the right circumstances when leaving the header exposed. I cannot think of a single advantage to leaving anything exposed. For encryption, use something like GCM (galois/counter mode), or if that's unavailable try for AES-256-CTR, or AES-256-CBC. Tip: use a library. (Yeah this comment might be good enough for an answer, but it's just jotting down thoughts.)
    – Luc
    Sep 1, 2014 at 19:40
  • @Luc I get why you shouldn't leave anything to the attacker in general. But still, are my arguments wrong? Why does it still apply here?
    – shoham
    Sep 1, 2014 at 19:43
  • 1
    @shoham 1) I don't know which problem you're talking about in your first point. Why is it relevant that people can figure out your header? 2) Why is "require more time" relevant? It's not like the attacker can afford a brute-force attack against a 128+ bit key.
    – CodesInChaos
    Sep 1, 2014 at 20:41
  • @CodesInChaos 1) If they can figure out my header they already know the whole file. 2) I'm a newbie so be gentle, how else can the attacker decrypt the file?
    – shoham
    Sep 1, 2014 at 20:46
  • If the header is somehow predictable, then it might be possible to mount a known plaintext attack on the cipher that way. The solution is not to expose the header, it is to make the header unpredictable. Others have already mentioned padding.
    – Bob Brown
    Sep 1, 2014 at 20:55

3 Answers 3

Reset to default
5

Judging from the question and the comments, I'll paraphrase your question as:

I'd like to encrypt a file, but part of my file has a predictable format. Will this make it easier to crack the encryption? Should I leave the structured parts out and encrypt only the minimum?

First off: that's not a silly question. Intuitively, you would think that knowing about the structure of the message would help you decrypt it, and this is true—to a certain point.

Luckily, this issue has long been anticipated by cryptography. 'Modern' encryption algorithms have a high branching factor: a small tweak in the input, a single changed bit, will create an unrecognisably different output. Because of this, knowing the structure of part of your file will not help me much, because any variation in content will lead to a very different result.

High branching factors are essential to strong encryption. Here is a brief example(1) of this in action:

> echo HELO1 | openssl aes-128-cbc -k meep -S 0
∙╞X╟ε╜i§B÷FÄ│Γat

> echo HELO2 | openssl aes-128-cbc -k meep -S 0
╩ ëhnw²╜╗ç1L▀≡☼·

(1) Syntax: openssl <algorithm> -k <passphrase> -S <salt>

Note that HELO1 and HELO2 have a similar structure—they differ by only two bits—but produce a very different output. This makes it so that, if I start guessing for your encryption key, I will have no idea of how 'close' I am. Basically, unless I get an exact hit and guess your passphrase, I'm going to have a hard time decerning anything from your file.

Unless, of course, you give me information by leaving your headers exposed. Not only do I now know the file type, I also have access to the Huffman tree, which was built from, and hence contains information about, the message it encoded. I may be able to make an educated guess about the contents without ever trying to decrypt it.

Analogy: HTTP(S)

HTTP is a structured protocol as well: each request starts with a 'method' (GET, POST, PUT...) and ends with HTTP/1.X with X some number. Even more: each line that follows has a predictable structure, as well as some lines which could be accurately guessed (Host:). That sounds like a lot of information for me to use.

Yet HTTPS encrypts the entire conversation, because not doing so would give me a lot more information. Heck, with all the headers, I might not even need to decrypt the payload: I can blackmail you with just the header data.

Improve this answer
4
  • Thanks, great answer. But I still don't get one thing: About the branching factor, how does it change anything? I assume you meant that even if my header has a predictable structure, if you change the data in it it will change the whole output of the encryption algorithm. But that won't matter because you can still decrypt only the header and then you have the whole file. I suspect I'm missing something really big here, maybe you can't decrypt only the header because of the branching factor? Continue reading in the following comment V
    – shoham
    Sep 2, 2014 at 15:40
  • If you were to try to decrypt only the part of the text where the header is, you would never get the right information, even if you have the right key. Am I right saying that?
    – shoham
    Sep 2, 2014 at 15:41
  • @shoham I think you're assuming that the header is 1: trivial to isolate, and 2: given the known structure, easier to decrypt. Padding guards against 1. A high branching factor guards against 2.
    – JvR
    Sep 2, 2014 at 17:34
  • Ok, so if I am going to implement padding, I basically add a random amount of spaces to the file's beginning and when encrypted they will no longer look like spaces. And when I try to decompress after the decryption is complete, I just remove the excess spaces (knowing the first byte of my header is not a space - by definition). Am I doing anything wrong? If not, then thank you very much! If I am, please inform me.
    – shoham
    Sep 2, 2014 at 17:49
2

Encrypt the whole file. This way people will not be able to figure out the header unless they decrypt the file. Leaving the header on clear will make easier to people to figure out what data lies on the encrypted blob.

The first way is way better, as it will create a file that the attackers will have no idea of the contents.

Improve this answer
5
  • OK, so I it separates into 2 situations: 1. If the attacker knows what the file is, the second way is better. Because it takes more time to decrypt. 2. If the attacker doesn't know, the first way is better because he has no idea what he's dealing with. That is how I see it, am I right?
    – shoham
    Sep 1, 2014 at 20:04
  • 1
    I think you are extremely confused. There is no situation in which it's "better" for the attacker if the header is also encrypted, assuming correctly-implemented encryption.
    – Stephen Touset
    Sep 1, 2014 at 20:10
  • 1
    Even if the attacker knows what the file is, the less information you left on clear, the better. Encrypting the whole file is more desirable in both scenarios.
    – ThoriumBR
    Sep 1, 2014 at 20:11
  • I don't get why, if I knew this is a file encrypted with my program and I knew the structure of the header. I know it can be a maximum of 1KB. I can try brute force 1KB and try to find if the structure is of my header. If it is, then I know I got the rest of the file right and I'm done. If I encrypt the file without the header, I have to decrypt the whole file, then decompress it with my huffman tree. The whole process takes a lot more time. It's almost like encrypting the header and the rest of the file with two seperate keys.
    – shoham
    Sep 1, 2014 at 20:22
  • 1
    If you use proper crypto, the header size will not be the same for every file. Little changes on the data will produce a very different cyphertext, and the attacker will not be able to tell where the header ends and where the data starts. If you encrypt the whole file using DES with random padding, the same input will produce different cyphertexts almost every time.
    – ThoriumBR
    Sep 1, 2014 at 20:29
1

Proceed with extreme caution

There have been several sophisticated attacks that use changes in the size of the compressed data to reveal the contents. The CRIME and BREACH attacks both worked because sensitive data was compressed, and by submitting multiple requests that differed only by a single character at a time and comparing the size of the outputs, they were able to recover the data. This is always a risk when you encrypt compressed data.

Improve this answer
1
  • 1
    This is cool. But these exploits are done in a browser where the attacker could add his own data to an encrypted cookie to observe the difference in size. This can't be done in a file, or can it? Can the attacker use the encrypted file and add to it more data then compress the new file and figure out things like that? Wouldn't he just be compressing "garbage"?
    – shoham
    Sep 2, 2014 at 21:03

You must log in to answer this question.

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