Cryptanalysis of hashids (2015) | Hacker News Reader

Cryptanalysis of hashids (2015)

carnage.github.io

25 pointsngrilly13 comments

A while ago, i looked into how to do something like this, and ended up asking people on sci.crypt for help. That led me to the "hasty pudding trick" - see the section on 'Encrypting Numbers and Dates':

http://richard.schroeppel.name:8015/hpc/hpc-spec

And ultimately to this this solution (which is a terrible writeup of it, sorry):

https://stackoverflow.com/a/966822/116639

Basically, the hasty pudding trick lets you whittle a block cipher down so that it works on some subset of its natural domain. And you can make a block cipher for an arbitarily small block size using a Feistel network with truncated SHA-3 or whatever as the round function. So, if you want to work with IDs in the range 0 to 999999, you make a 20-bit block cipher, then use the hasty pudding trick to run it over 0-999999 instead of 0-1048575.

There's probably a better way to do this that doesn't involve building your own cipher, but i didn't work it out at the time.

Strange claim about what the site 'implies'.

I use hashids and did not assume such things.

I use it so a jerk end-user can't keep incrementing an integer-based URL param.

yeah seriously. the hashids people are very clear about what a terrible idea it is to think that hashids are secure in any way. fine, do a cryptographic analysis, but don’t suggest you’re actually saving people from some false claim or implication about security.

The hashids website has been updated since the cryptanalysis was published. For example, the old website used the words encrypt/decrypt instead of encode/decode, which was confusing.

You rely on hashids to be secure, so that your jerk end-users can't increment the id. You would like to know how secure it actually is, don't you?

This is exactly what I'm wondering. If an attacker finds a way to reverse the hashids, then he can increment the ID and scan the resources.

No.

If they can figure that out, I will have bigger problems with the users.

So apparently you have bigger problems with the users now.

Do you think it's correct to claim that hashids are not reversible, if the attacker is unable to choose the plain text to be encoded? [1]

[1] In other words, the sequential IDs are generated server-side and the attacker has not control over them.

This is how we use them. It should be fine. That said, they should probably not be used for anything sensitive. Obscuring a database id is probably fine, as a password has no.

> Obscuring a database id is probably fine

If you can guess what the next database ID is, then you can probably use it to take over the cookie session ID, use it in a replay attack, or whatever, depending on how your app is architected.

... if you don't need to keep something secret, then why hash it at all? And if you do, then actually hash it.

I'll tell you for free that our cookies don't use an auto incrementing id.

If you have an asset that is accessed by id, it is beneficial to have a secure, reversable function so that you can prevent trivial crawling while maintaining ease of development. We don't allow chosen plaintexts, so the cryptanalysis here is not relevant. And, even if it did break our use, it would deter most.

you call this cryptanalysis?

Reply on news.ycombinator.com