Padding for the TEA

Sorry if this is a noob questions, but I finally figured out how to implement the Tiny Encryption Algorithm in C++.

My question is what to do about padding the key and the plaintext? I know that there are various ways of doing this, but is there a "default" way to do this or does one make a choice?

-
The method described in PKCS#5 is the most commonly used way, but there is no "default". I'm assuming you are using TEA in CBC mode. – Chris Smith Jun 9 '12 at 22:19
@ChrisSmith: I think I am using the ECB mode – Thomas Jun 9 '12 at 22:21
My previous comment equally applies to ECB mode. However, I'd suggest using another mode of operation. See the following page for more details: en.wikipedia.org/wiki/Block_cipher_modes_of_operation – Chris Smith Jun 9 '12 at 22:29
@ChrisSmith: Yes, I am doing this more as an exercise in the algorithm. I will try to do both modes. So, I can't find anything about the PKCS5. I found something about PKSCS7 on Wikipedia: en.wikipedia.org/wiki/Padding_%28cryptography%29#Bit_padding – Thomas Jun 9 '12 at 22:32
The terms "PKCS#5 padding" and "PKCS#7 padding" are used interchangeably, they essentially mean the same thing. – Chris Smith Jun 9 '12 at 22:34

The fragment " what to do about padding the key ? " of the question looks scarily like transforming a password into a cryptographic key using some padding mechanism.

Doing this would be a known, serious, often made and often exploited mistake. A standard security assumption for ciphers is that the key is chosen at random, and a padded password is not random by any stretch of imagination. If a fraction of plaintext (like 8 bytes at the beginning) is known, it becomes very easy to test (with high confidence) if the password is any given value: the cost is one block cipher per password tested (using a hash of the password makes the password look random, but gives marginally more security: cost is raised only by one hash per test). This is ideal grounds for password cracking, that is basically trying plausible passwords. Many tools do that using CPU or GPU, at rates sometime well over $10^9$ per second per GPU. There's a business for it, even FPGA-based devices in rack-mountable units; and perhaps for well-funded organizations, specific silicon. I stress that I am not endorsing theses products and have no practice with password cracking.

Turning a password into a key suitable for a block cipher is the job of a Key Derivation Function specially designed for passwords (not of a hash function). Such functions require a parameterizable amount of work, allowing to increase the amount of time required to test if a password is correct, even if it remains easy to test if a key is correct. This can greatly increase the resistance to password cracking (a factor of $2^{30}$ is often realistic).

Among good such functions in common use is PBKDF2 (formally defined in RFC2898), which is based on iterated hashing. A state-of-the-art one is Scrypt, which use sequential memory-hard functions; it has a strong security rationale and uses one of the best primitive for the job in its inner loop (Bernstein's Salsa20); however that very quality makes it inconvenient in many practical use cases where there is no efficient implementation of Salsa20 possible, e.g. when making a software add-on constrained to some interpreter and access to a limited number of crypto primitives with efficient implementation.

The parameter(s) controlling the amount of RAM used (for Scrypt), and the number of iterations (for all Password Based Key Derivation Functions) should be turned up, increasing the cost to compute a key from a password, within the limit of practicality.

Both PBKDF2 and Scrypt have a salt input. In the context of encryption, salt is some public data that is, inasmuch as possible, not reused. Salt needs to be available for decryption, e.g. included as preamble of ciphertext. Salt helps because passwords get reused (by the same user as a simplification, and by different users accidentally), and without salt would lead to reuse of identical keys, in turn making pre-computation possible for password guessing, and facilitating some attacks.

When that's possible, salt can be true random (256 bits would be aplenty), but true random is hard to gather, and increases the plaintext size. In order to reduce overhead, salt could be some public data that is implicitly known (device serial number, user id, name, email..) or needs to be transmitted anyway (file name/date/size..). A counter requires less space, but can be reset (accidentally or deliberately), and it is hard to get several users or computers using the same counter. The concatenation of clock time + local MAC address is often not unique even at instants separated by more than the clock granularity (clock can jump back due to adjustments, daylight savings, or deliberately; MAC address sometime is accidentally botched by the hardware manufacturer, and is typically read using an API that may alter it).

One fine approach is to concatenate as much as possible from the above that can safely be made public, and use that as salt, either directly, or after hashing in order to reduce the salt's size/overhead.

As to padding mechanisms for data: it you need one, use any deterministic standard one, they are functionally equivalent. Whatever one you choose, pay attention to what happens when the padding is incorrect after decryption, which could happen if the ciphertext gets corrupted (accidentally or intentionally): checking the padding could lead to buffer overflow, and revealing that the padding is incorrect can leak information on the plaintext. The simplest is not to pad data: you do not need any data padding if you use CFB, OFB or CTR.

-
It's a well written answer, but I'm not sure I fully agree with the last sentences on data padding. I don't think it makes much sense which padding you choose regarding padding oracle attacks, which is what you seem to be hinting at. In those cases you should simply add a MAC or HMAC or choose a mode that includes integrity & authentication. You can only mitigate the attack slightly when using random bytes within the padding. – Maarten Bodewes Jun 10 '12 at 18:01
Ok, so I think that I understand how to do the plaintext padding. If I want to use this PBKDF2, how exactly would I do that? I see that it requires salt. How, for example does one produce that? (This might be an entirely new question?) – Thomas Jun 10 '12 at 18:42
@owlstead: I have attempted to clarify the section on data padding. – fgrieu Jun 10 '12 at 19:27
@Thomas: I added explanation on salt. – fgrieu Jun 10 '12 at 20:48
@mikeazo: I'm pointing that if a password is turned into a key without precautions, including by a mere padding or hashing, then (known plaintext ⇒ very easy test of password), with cost like one block cipher operation per password tested. With PBKDF2 or Scrypt, that cost can be raised considerably (a factor of 2^30 is realistic), that's controlled by a parameter. It remains very easy to test for a key, but it is no longer as easy to test for a password. – fgrieu Jun 11 '12 at 6:11