How to pick a symmetric cipher for a given cipher text size?

Question

I'm looking to encrypt some 64 bit integers, with a maximum cipher text size of 128bits. The encrypted numbers will be displayed in some public places, so shorter, "vanity" sizes is a primary design constraint.

It's not critical that these integers remain private for ever; ideally they would just be hard enough to decrypt that it would be cost ineffective to do so. My rough goal is that it should cost about $20 on commodity hardware to break.

Most modern ciphers produce cipher text that is frequently too large, and older ciphers are marked as insecure with no discussion of how insecure they are. I looked at Blowfish and 3DES, but both have large warnings on the Internet saying to use something more advanced.

A finally, stretch requirement would be to have some kind of authentication tag (e.g. an AEAD). It appears the popularity of authenticated encryption happened after block sizes had moved up to 128 bit.

My initial use case is for anti scraping (making it hard to guess IDs), where I had planned to rotate the encryption keys every couple of days.

Answer 1

For an arbitrarily small ciphertext size, what one wants is a streaming cipher. Two such ciphers are AES-GCM and ChaCha. Size of ciphertext is equal to size of plaintext.

For a maximum size of 128-bits with ADEAD you might be out of luck. BUT, HMAC would give similar assurances and HMAC can be truncated to any size (with obvious drawback).

So, ChaCha and HMAC-SHA3-256 truncated to 64-bits should get you to your 128-bit total.

192-bits would be ChaCha and untruncated HMAC-MD5. Which one is more secure is a question for a smarter man than me.

Note:

None of this accounts for IV. It must be transmitted with the cipher text or in a side channel. Without a side channel, a more realistic number would could be 64-bit ciphertext + 64-bit truncated hmac + 64-bit IV (chacha) for 192 bits.

Answer 2

Idea

You don't need any "weak" algorithm. Use a normal secure algorithm, use slow password derivation, and but use shorter passwords, so that the brute-forcing costs what you want.

Details

Take any normal secure algorithm like AES-256, ChaCha20, or ThreeFish. Use password derivation (hashing) like Argon2, PBKDF2, bcrypt, scrypt and choose parameters such that derivation of a single password takes about 1s on the PC that you consider as average. If you think a CPU has 16 cores, then it should take 16s for a single core, so that on average the whole CPU takes 1s per password. If you consider a GPU, compute parameters correspondingly. Then set password length such that brute-forcing of all passwords will cost what you want, $20. Actually, this should be costs of brute-forcing of a half of all passwords, because on average they will be found after trying 50% of all possible passwords.

Example

Suppose 1kWh costs $0.15 and a PC needs 200Wh = 0.2kWh. The cost of $20 will be reached in 20/(0.15*0.2) = 667h ~= 2 400 000s. You want that attacker computes 2 400 000 passwords. Assuming passwords are evenly distributed and will be found on average after 50% tried, the total number of passwords will be twice bigger: 2 400 000 * 2 = 4 800 000. Thus, generate randomly a number in the range 0 - 4 800 000 and use it as password. Assuming you set hashing parameters such that it takes 1s per CPU (like 16s per password per core on 16-cores CPU) it will cost about $20 to try a half of them.

But...

It is impossible to know many important factors of the attackers:

• How powerful are their computers?
• Do they use only CPUs of average laptops or PCs, or the use GPUs?
• Do they use a single device or some cluster of devices?
• How much does power cost to them?

That's why there is no reliable solution.