Hacker News Reader

Comment by sjnu | Hacker News Reader

I’m curious what properties this has that aes(0||id) doesn’t.

I always just have a uuid column with an index (which is populated with a random uuid) and use that externally for URLs and such. What is the benefit of this over “slightly smaller database”, and that nagging feeling of violating DRY due to each row having two unique constraints/identifiers?

UUIDs aren’t big when stored properly (ie not as strings); I just got over it. Am I missing something?

Haha I came here to ask the same question.

This "SIV" mode is silly and breaks down completely when encrypting more than 2^32 IDs.

Your proposal is not only faster, but also safer. AES is a strong pseudorandom permutation, the 00000000 padding is a perfectly fine integrity check.

Author here.

You're right (if you add a constant-time check upon decryption that the bits are zero).

I suggested as much here yesterday, and may revise the scheme to do so:

https://www.reddit.com/r/crypto/comments/fyn8cs/aesbased_syn...

Does the check even need to be constant time?

The usual use case for a constant time comparison is to avoid allowing an attacker to guess a value one byte at a time. For example, a 16 byte MAC value on a packet could be brute forced byte-by-byte if the system reveals to the attacker which byte the MAC check failed on.

But in the zero padded AES case, the check is being done after an AES decryption operation, so the attacker can't attempt to generate each zero value a byte at a time. After 256 guesses, an attacker able to see timing information could figure out when their 128 bit input guess generated a decrypted value with a valid zero in the first padding byte. But that does them no good trying to generate a zero in the next padding byte because any change they make to their input guess changes all the decrypted output bytes, including that first zero. Each successive zero byte means they have to start over, so generating 8 zero bytes requires 2^64 guesses as far as I can tell.

yer. attacker can't generate longer collisions from shorter collisions so constant time comparison is not necessary. assuming AES in ECB mode and you are not doing something weird like using an IV mode where attacker can tweak the IV to generate different plaintext.

I also don’t understand how padding oracle attack corresponds to this if all IDs are under 128 bits.

While AES(0||id) is subject to a padding oracle, it's not immediately obvious why this would be a useful capability to an attacker, since you can't tweak your input based on the oracle's output (unlike e.g. AES-CBC).

How is AES(0||id) subject to a padding oracle? Am I misunderstanding the notation?

Yeah, that's not a padding oracle, but it's similar in concept, because the prefix check after decryption will likely leak whether the app considers the ciphertext valid, ala:

    pk = decrypt(params.id)
    if pk[0:8] != EIGHT_ZEROS:
        return Http404
    id = int(pk[8:16])
    object = db.query(id)

Also stuff like this isn't really specific to using this particular construction. Even if systems are designed to return "does not exist" instead of "forbidden", it's hard to make authorization checks constant time and I've never seen code to even try that.

Sure, but you can't adaptively choose a new ciphertext to iterate with. Which is the core of the concept.

Yeah, exactly. I don't think we disagree, I just abused the name a little bit - not a good idea in this field!

Slowness and complexity, it looks like! Unlike a prefix of zero bytes, the MAC has to be compared in constant time; there are more moving parts; it seems like there might be a birthday problem problem where two ids with colliding IVs (50% chance of existing among 5 billion ids, noticeable without needing the key) will be XORed against the same encrypted counter?

It's 'misuse resistant', detecting malleability. So... what properties does this have that AES(H(id, k1) || id, k2) with 64-bit id and keyed hash function H does not have.

EDIT: actually I don't believe that my above scheme is any better than your original as long as you verify the zero padding is correct.

What does “detecting malleability” mean? Misuse by forgetting to check the zero?

Essentially, yes.

SIV mode is misuse resistant with regard to repeated nonce values, but that property doesn't seem to apply to the SID use-case. And if you assume the user isn't validating the decrypted value, SID has a far more catastrophic malleability problem than the zero padded AES approach.

Because SID encrypts the 64-bit ID using counter mode, not validating the SIV value allows an attacker to make specific changes to the decrypted ID (e.g. flipping individual bits) or inserting chosen ID values if the attacker ever learns the mapping between an 128-bit encrypted ID and the decrypted 64-bit value.

Even if you don't validate the zero padding in the other approach, an attacker is only able to get the system to accept random 64-bit ID values as far as I can tell. Still not great, but less catastrophic and it's not a malleability problem as I understand the term because the attacker is unable to make specific changes in the decrypted output.

It's reversible. That's the whole point. You don't need to keep a separate table or column for the hashed id.

That by itself is an old problem; see for instance Black and Rogaway's paper on restricted domain ciphers:

https://web.cs.ucdavis.edu/~rogaway/papers/subset.pdf

Isn't AES encryption also reversible? The use-case for AES-SID appears to be mapping 64-bit ID values to 128-bit ciphertexts and reversibly producing an authenticated 64-bit ID value from the 128-bit ciphertext. Zero padded AES does both of these things as far as I can tell.

It's also reversible:

newid = AES-EncryptBlock(0||id)

0||id = AES-DecryptBlock(newid)

Check for 8 zero bytes for authentication. Bonus: can use a constant instead of zeros for domain separation (eg different DB columns or tables).

Reply on news.ycombinator.com