Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I need to encrypt relatively short strings (generally less than 100 characters). If possible, I want to avoid leaking the length of these strings. How can I do that?

The thing that came to my mind is to pad the text to 1 KiB with random data, separating the content from the padding with a 0x00 byte. Is this a good idea?

share|improve this question

migrated from stackoverflow.com Oct 8 '12 at 21:18

This question came from our site for professional and enthusiast programmers.

1  
stackoverflow.com/questions/7781348/… –  Alex Oct 7 '12 at 19:08
    
@Alex I don't see too much similarity, I must admit. The question you pointed to uses questionable techniques too (ECB encoding for instance). –  owlstead Oct 8 '12 at 1:12
    
Side-question: what is the danger of exposing string lengths, especially if they're encrypted? –  Marcin Oct 10 '12 at 15:14
    
@Marcin That's very application dependent. In some cases it doesn't matter much, in others it can be fatal. A simple case could be distinguishing "yes" and "no" in a stream mode. Or as practical example, a recent attack on TLS was based on exposing the length of a compressed text. –  CodesInChaos Oct 11 '12 at 21:33
    
@Erik Consider adding authentication/a MAC. Without authentication you can't detect modifications of the data, and in some cases(padding oracle) modifications can be used to decrypt your data interactively. –  CodesInChaos Oct 11 '12 at 21:34
show 1 more comment

5 Answers 5

The best thing to do with your strings will depend on what you are using them for.

According to Nate Lawson, who knows a lot more about this than either of us, you should generally use either SSL or GPG:

Designing a crypto protocol is extremely costly due to the careful review that is required and the huge potential damage if a flaw is found. Instead of incurring that cost, it’s often better to keep state on the server or use well-reviewed libraries that provide SSL or GPG interfaces. There are no flaws in the crypto you avoid implementing.

share|improve this answer
    
That's probably a good idea. Does either of these have a native method for obscuring the length? Otherwise I'll still have to do that on top. –  Erik Oct 7 '12 at 20:10
    
The aes encryption has a fixed block size of 16 bytes. So if you encrypt the string using aes (see my posted link), the length of the string will be obscured by the block size of aes. –  Alex Oct 7 '12 at 20:21
    
Anything using a block cypher is probably going to pad up the block size. Depending on what you are doing it might also be more appropriate to use a hash function instead of encryption. –  Samuel Edwin Ward Oct 7 '12 at 20:51
    
No, I actually need reversible encryption, not a hash function. –  Erik Oct 8 '12 at 19:44
add comment

1: Your idea of padding the string in order to obscure its length is a good one.

2: The Java API already has encryption capabilities. I suggest using the Cipher class in the javax.crypto.* package. No need to use additional libraries.

share|improve this answer
add comment

Adding almost a kilobyte of padding will limit the types of padding you can use. The main thing is that the padding be cleanly removable. Using a 0 as separator will fail in 50% of cases, because the real text ends in a 0 itself. I would suggest one of these methods:

1 Bit Padding: add a 1 bit, and then pad with 0 bits for as far as you want. Remove all trailing zeros and the single 1 bit. In byte terms this is one 0x80 byte followed by as many 0x00 bytes as needed.

2 Byte Padding: pad almost to the end with zero bytes. Use the last two bytes to record the number of zero bytes added. Make sure you know if those two bytes are big endian or little endian.

share|improve this answer
    
I was thinking of a 0x00 byte, not a 0 bit. That would have worked for ASCII, but now I'm not sure if UTF-8 (or any other unicode encoding) actually guarantees that no character ends with a 0x00 byte. Obviously 1 bit padding does indeed require 0x00 bytes. Also, why pad with zeros? I thought random padding would be more effective as part of the plain text is effectively known if the padding is all 0x00 –  Erik Oct 8 '12 at 19:41
    
"Using a 0 as separator will fail in 50% of cases, because the real text ends in a 0 itself." Why would the real text end in a 0 at all, much less exactly half the time? –  Samuel Edwin Ward Oct 8 '12 at 19:50
1  
@Erik it won't, UTF-8 was created to only allow bytes that are compatible with ASCII printable characters for all Unicode code points of 20h and over. That's one reason for its popularity. –  owlstead Oct 8 '12 at 20:49
    
@SamuelEdwinWard: That's what I was wondering too. I guess rossum thought that I wanted to use a 0 bit as a separator, not a 0x00 byte. –  Erik Oct 8 '12 at 20:51
1  
@Erik: I was giving the standard definition of bit padding, which is defined in terms of bits. My last sentence in that section, "In byte terms..." gives the byte version. –  rossum Oct 9 '12 at 0:31
show 1 more comment

Instead of saving the padding length as rossum explained, you can also put a length encoding in front of your plain text. A standardized way to do this would be DER encoding (which uses a dynamic number of length bytes), but in your case you could also use a 2 byte short. Then just add 00h bytes padding up to X times the block size, and encrypt using a cipher without padding.

The advantage is that during decryption you can simply discard the bytes, and you don't need no unpadding mechanism, just discard any bytes behind the plain text.

This method is used e.g. in the PKCS#11 standard (for hardware tokens).

share|improve this answer
add comment

Clearly you need to pad the plaintext before encrypting it.

Pad it to some fixed size – optimally this should also be a multiple of the block size (16 bytes are nowadays standard for block ciphers), so you don't have to pad again for encryption.

Make the padding removable. There are several methods of doing this:

  • If you now that your message can't contain certain bytes or byte sequences, you can use a separator. A zero byte works if your plaintext contains only printable text in ASCII or some compatible encoding.

    This will not work if the plaintext can contain arbitrary binary data, if you don't escape it first. Not generally recommended.

  • If your message has a certain internal structure which tells you when it is finished, you don't need a separator – simply parse it and stop when the message ends.

    Here you'll have to pay attention to buffer overruns and similar. Not generally recommended.

  • Encode the length of the message at the start of the message. (Of course, this only works when you have the whole message before starting to encrypt, but for your short messages this seems doable.)

    This is also quite easy to implement.

  • Encode the length of the message or the padding at the end of the padding. A popular version is the padding used in PKCS #5, which indicates the padding size repeatedly in all the bytes of the padding. (This limits you to maximally 255 bytes of padding, though.) You can use a similar scheme, indicating the padding size with two bytes.

    This has the advantage to be easy to strip off.

  • Have the padding of some fixed format. Rossum's bit padding variant is this: add one one bit, then fill with zeros.

    This makes you parse the message from the end to find the start of the padding. Often backwards parsing is more complicated.

Whatever you do, the actual padding can then be either random, zero, or arbitrary (of course not for the versions with fixed padding format).

Then encrypt the message using a secure encryption algorithm and mode of operation (do not use ECB mode – it is generally broken, and even more in the case of some empty or otherwise fixed padding when you want to hide the size).

Then add authentication (a MAC such like HMAC), of the whole encrypted message. The receiver should reject the message if the MAC is wrong, and not even start decrypting then. Doing otherwise can give an padding oracle when an invalid padding is detected after decrypting, which can lead to loss of confidentiality.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.