Which tamper-protection algorithm provides the shortest output?

Question

Background

When making web applications you sometimes need to pass data along with the form which isn't visible to the user. Database IDs are the most common, but texts and IDs are sometimes necessary too. For this reason there is a <hidden> field in HTML, but it has a drawback - any hacker with a basic understanding of what he is doing can modify the value. It would be better if such values would be tamper-protected, if not outright encrypted.

Question

I need to pass a value through hostile territory. The value is most often an integer (and that most often less than 65'000, so mostly just two non-zero bytes, rarely three, almost never 4). However sometimes the value can also be a string (short, a few hundred characters at most). I'm OK with using different algorithms for different kinds of data.

I want to tamper-protect the value, so that it cannot be changed en-route without detecting. Hiding the data isn't necessary, but doing so would be a bonus. So either tamper-protection or encryption would work.

Whatever the algorithm, I want to have the output as short as possible without sacrificing too much of security. This is because it's a webpage and shorter data means faster response times. Also, the HTML code becomes easier to read if there aren't lengthy random strings in it.

What algorithms would you suggest for this purpose?

Answer 1

You are writing out data and reading it back on the same server. You want to ensure that the data that you read back is the same as the data that was written out.

For this use case, symmetric cryptography seems appropriate. Have a single symmetric key that doesn't leave the server. You need to rotate the key only if the server is compromised; this will invalidate sessions in progress, which is likely to happen for other reasons in case of a server compromise as well.

You can take add an HMAC checksum of the data; with HMAC-SHA-256 (a strong, recommended choice), this adds 64 bytes if you encode the checksum in hexadecimal or 44 if you encode it in base64 (or 32 if you include it in binary form but that tends to be hard to parse). There'll probably be a few more bytes' overhead to put the string somewhere. Given the context — a web page — I don't see any point in weakening the cryptographic strength to save a few more bytes.

If you want to encrypt the data as well, use AES-128 with an authenticated encryption mode (CCM or GCM are common choices). There will be an overhead of 16 bytes of IV, up to 16 bytes of padding, 16 bytes of MAC, and a multiplication factor due to the encoding requirement since the encrypted data can use all byte values (4/3 factor for base64). You'll need to decrypt the data before doing any processing with it; in particular, if some of that data is used on the client side, you'll either need to duplicate it or to combine authenticated encryption with a MAC of that plus the client-readable data.

Note that protecting the data in this way only authenticates it — it proves that the data was produced by your server. An attacker can still take the data from one page and send it with another page, or a later version of that page. How to avoid this depends on when the data is legitimate. You may want to include the URL or the user ID in the hashed data, for example, to avoid the data being used out of context.

Answer 2

I wrote this response while thinking I was on Information Security. Oops. Anyway, I think it may be helpful, so sorry if this is not exactly "cryptography" POV. Point of this response is: in this case encryption or hashing is not a good solution. It has a lot of problems, because there is very little entropy and it has to be working over HTTP.

Full programming-and-security POV response:

While this does not answer the question, consider avoiding at all "hidden" values that can be tampered with.

If this is a resource id, simply check if user has a right to make operations on that resource after receiving the form. Otherwise, read on.

Give each form instance a random token (long enough that it cannot be easily guessed by bruteforcing), and put somewhere server-side the "secret" data connected with the form token. Upon receiving the form, pull up the secret data connected with the token, and then delete the token and data on the server-side.

How to do that:

• If you are using sessions, put the sensitive data in a associative array/map/hash (or whatever name of that data structure appeals to you) inside the session.
• Otherwise put them in a database (remember to delete old non-used entries every hour or so)

Why you should do that:

• Protection against CSRF, which is the SQL Injection of the modern day
• Your "tamper proof" data is quite short, there is not a lot entropy in that. If all you did is hashing the data using a secret key, determined attacker may be able to do a "rainbow table" of all possible values.
• Protection against replay attacks (sending the same data twice)

Things to consider:

• Birthday paradox, if you are using single DB to hold all the data, the tokens have to be extra-long to avoid collisions

Last but not least, I have no idea what are you doing, but saving 32 bytes from each request (sha256 length) seems a bit pointless. You can achieve a lot more by optimizing images, removing whitespace from HTML, minifying JavaScript and CSS, using compression... 32 bytes is not that much in terms of webpages.

Answer 3

I second Gilles' suggestion of using an authenticated encryption mode. In particular, if your crypto library provides it, this sounds like a perfect job for SIV mode (RFC 5297).

SIV is designed to be "maximally misuse-resistant" authenticated encryption (AEAD) mode for securely encrypting and tamper-proofing (relatively) short messages (such as private keys for other cryptosystems; hence it is often described as a key-wrapping mode). It provides the following features:

• As an authenticated encryption mode, SIV both encrypts the message and protects it from tampering. If fact, it is an AEAD mode, meaning that it can also, optionally, be used to tamper-protect unencrypted messages, or messages that are only partially encrypted (e.g. unencrypted headers + encrypted data).

• SIV can be used with or without a per-message nonce. When used with a nonce, it provides full IND-CCA2 security; when used without one, it still retains almost all of this security, except for the fact that identical plaintexts can be detected by the fact that they will encrypt to identical ciphertexts. (Contrast this with many AEAD modes like GCM, where a missing or reused nonce can completely destroy the security of the scheme.)

  (Of course, like most encryption modes, SIV also leaks the length of the plaintext, unless the plaintext messages are padded to a fixed length before encryption. This is universal enough that cryptographers tend to assume it without explicitly stating it, but it can sometimes be an important issue in practice.)

• Like most authenticated encryption modes, SIV is based on a block cipher. In principle, any secure block cipher may be used, but AES is generally recommended. Unlike, say, GCM, SIV does not require any other low-level operations such as (generic) Galois field multiplication.

• When SIV-AES is used without a nonce, the ciphertext is 128 bits (= 16 bytes) longer than the plaintext. (Since the ciphertext will, as usual, look like random binary data, you will have to e.g. base64-encode it to embed it in an HTML form, increasing its length by a further 33%.) If used with a nonce, the nonce will, of course, have to be somehow transmitted alongside the ciphertext as well.

  (Technically, it would be possible to modify SIV to shorten the padding down to something like 64 bits (= 8 bytes), but I would not recommend this without a careful security analysis. 128 bits provides a comfortable security level, and the few extra bytes per message are rarely prohibitively expensive.)

The one major disadvantage of SIV, as compared to other AEAD modes like GCM, is that it's an inherently two-pass mode: the plaintext must be processed twice from beginning to end, which reduces its efficiency for long messages. (This is an unavoidable consequence of the maximal misuse-resistance goal, since it requires that every part of the plaintext must affect the encryption of every other part.) Fortunately, for your purposes, this does not seem a major issue.

Another, hopefully temporary, problem for SIV is that it's not yet as widely implemented in crypto libraries as older AEAD modes. While it's possible to implement SIV yourself based on CMAC and CTR mode (or even just a raw block cipher), this is not completely trivial. Hopefully, this issue will disappear over time, as more and more crypto libraries will support SIV.

Answer 4

You need integrity/authenticity and freshness (replay prevention), and in many contexts confidentiality (depending upon the situation). Mere encryption is not enough, because it doesn't provide integrity/authenticity and doesn't prevent replays. A better scheme would be authenticated encryption, with a nonce that is checked on the server and verified not to repeat.

In practice you probably want to encrypt by default (i.e., always provide confidentiality by default), because if you make encryption optional it is too easy for there to be some value that was confidential but where you forgot to enable encryption.

You also need the value to be bound to this particular session and this particular context (e.g., this particular form and form attribute). Otherwise, an attacker can cut-and-paste a hidden value from one form into another form, and that might enable attacks.

Many of these considerations are security considerations, more so than crypto algorithm issues. For that reason, the primary challenges here are IT Security challenges, rather than Crypto challenges -- and you might want to flag your question to have it migrated over to Security.SE.

Look up Windows view state encryption, for a real-world example of such a mechanism.