Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sqids – Generate short unique IDs from numbers

sqids.org

Post reply on HN
Print view View original

201–210 of 249 posts

Re: Sqids – Generate short unique IDs from numbers

#201

Post by hippich »

andix wrote: post #121

Actually I'm a bit disappointed that it can't format 128 bit integers or byte arrays. That would allow formatting UUIDs. I'm not a huge fan of public facing integer IDs. There is always the risk of leaking some kind of critical information with ascending IDs. So I will probably keep Base64URL formatting my UUIDs to make them shorter for URLs, QR Codes and so on. Quick example: 20b30b32-d421-4cfb-bdbc-9a4e0475abea =>…

I actually used sqids algo for something very different where I had to encode arbitrary sized byte arrays. And with Ruby it was very simple to remove limit - I think it was matter of monkey-patching https://github.com/sqids/sqids-ruby/blob/main/lib/sqids.rb#L... to return infinity.

The reason for the limit is most likely to ensure interoperability with libraries in other languages where working with bignums is much more complicated.

Re: Sqids – Generate short unique IDs from numbers

#202

Post by pixel8account »

namtab00 wrote: post #124
leobg wrote: post #114

Earlier quoted context omitted.

Very interesting. I’m a lawyer and using sequential IDs in a fraud case right now, to determine the number of victims. Unfortunately, so far, I only have the IDs of two victims, and those are from just within about a month, whereas the fraud has likely been going on for several years. Just simply extrapolating that growth rate isn’t going to be very accurate. Also, I suspect that the perpetrators did not start at ID…

ehm, yeah, n=2 will not get you anything useful... that'll be like trying to determine the average salary in a company with only two known ones, which could be the janitor's and the CEO's

Even with n=1 you can get something useful. IIRC "on average" if you have ID x than the best population estimation is 2*x. Of course the error margin is immense, but it's still better than nothing.

Re: Sqids – Generate short unique IDs from numbers

#203

Post by 8organicbits »

posix86 wrote: post #155
8organicbits wrote: post #69

Earlier quoted context omitted.

It looks like an easy brute force too, there's no compute-hard operations here. I guess you could scramble your alphabet? Otherwise Uk always comes after bM, etc.

My understanding is that you can re-order the source alphabet, and encode numbers with swapped characters. Unless you know of 36 numbers that they're exactly 1 id apart, you will always have uncertainty to what the ids actually map to.I guess given a large, large number of ids along with the order they're assigned (which might be given through the time at which they're assigned), you could create a pribabilistic stat…

Scambling the source alphabet should have an effect similar to a monoalphabetic substitution cypher. This is not strong cryptography. If the attacker has any ability to generate IDs quickly, like by creating user accounts or other resources they can create many IDs with known ordering. Likely effective against non-serious attempts.

Re: Sqids – Generate short unique IDs from numbers

#204

Post by pixel8account »

wslh wrote: post #152
smashed wrote: post #145

Earlier quoted context omitted.

I'm not a cryptographer and did not understand half the things you said except symmetric crypto. I think there are 2 problems with this approach: How do you prevent the double spend problem, for example duplicate entry tickets. You would have to mark the ticket as used in a central database anyway to prevent it What happens if the secret key material is compromised? Anyone can issue new valid numbers, etc.. Please co…

No problem, the two answers here: 1/ You don't have duplicates because a Feistel network assures you there is no duplicates: every input has a different output with a fixed key in every round. 2/ If the secret is compromised anyone can issue valid numbers in the same way that if your secret encryption keys for encrypting your data exposes it. The idea is that the secret key material is never compromised as it is assu…

>The idea is that the secret key material is never compromised as it is assumed in all security cases.

That's not true, we have (perfect) forward secrecy, backwards secrecy and key rotation mechanisms because we often care what happened after the key is inevitably compromised. In this case the problem makes it hard to "rotate" the keys in a meaningful way, but I'm yet to see a proof it's impossible.

Re: Sqids – Generate short unique IDs from numbers

#205

Post by andix »

hippich wrote: post #201
andix wrote: post #121

Actually I'm a bit disappointed that it can't format 128 bit integers or byte arrays. That would allow formatting UUIDs. I'm not a huge fan of public facing integer IDs. There is always the risk of leaking some kind of critical information with ascending IDs. So I will probably keep Base64URL formatting my UUIDs to make them shorter for URLs, QR Codes and so on. Quick example: 20b30b32-d421-4cfb-bdbc-9a4e0475abea =>…

I actually used sqids algo for something very different where I had to encode arbitrary sized byte arrays. And with Ruby it was very simple to remove limit - I think it was matter of monkey-patching https://github.com/sqids/sqids-ruby/blob/main/lib/sqids.rb#L... to return infinity. The reason for the limit is most likely to ensure interoperability with libraries in other languages where working with bignums is much m…

This limit could easily be lifted with byte array encoding support.

Re: Sqids – Generate short unique IDs from numbers

#206

Post by wslh »

rdpintqogeogsaa wrote: post #188
wslh wrote: post #133

I offered something similar here [1] and it is used by many companies including Philip Morris, and the Argentinian tax agency for the same purposes. The technique I used (I should publish it as open source) is using a Feistel cipher [2] with a key. The Feistel network could be adjusted to almost any size and the key used in every round is an expansion of a general key using a key derivation function [3] (KDF3 if I re…

Interestingly, it seems there might have been independent invention of the same idea[0]. Have you checked for any patents in the space? [0] https://bytes.grubhub.com/why-we-use-crypto-when-generating-...

Thank you for the article. I was not aware of that article. My first implementation was done in 1997 or 1998. I am involve in computer security for three decades and I was familiar with Feistel networks. I am not a cryptographer but I have reverse engineered algorithms using this structure. Never checked patents because I think this is a natural construction and I always wondered why there were no other public ideas around this problem. This is not the first time it happened to me.

Re: Sqids – Generate short unique IDs from numbers

#207

Post by wslh »

pixel8account wrote: post #204
wslh wrote: post #152

Earlier quoted context omitted.

No problem, the two answers here: 1/ You don't have duplicates because a Feistel network assures you there is no duplicates: every input has a different output with a fixed key in every round. 2/ If the secret is compromised anyone can issue valid numbers in the same way that if your secret encryption keys for encrypting your data exposes it. The idea is that the secret key material is never compromised as it is assu…

>The idea is that the secret key material is never compromised as it is assumed in all security cases. That's not true, we have (perfect) forward secrecy, backwards secrecy and key rotation mechanisms because we often care what happened after the key is inevitably compromised. In this case the problem makes it hard to "rotate" the keys in a meaningful way, but I'm yet to see a proof it's impossible.

I think we are talking about different things here or the conversation is not clear.

The assertion you mentioned is the "what" assumption while what you said is the "how" we came to that assertion. Most probably you take my word idea in a specific sense other than I wanted to use. My answer was informal because we are here in HN and not writing a paper.

Re: Sqids – Generate short unique IDs from numbers

#208

Post by slig »

richbell wrote: post #161
paulddraper wrote: post #100

Earlier quoted context omitted.

No, squids are predictable, you can't use them to hide information. They call it out on their front page.

I haven't looked at the implementation yet but HashIds (the former project name) required a salt. It would be weird if they changed that.

The `salt` in hashids just shuffled the alphabet. Now they removed the `salt`, but you can have the same level of "obfuscation" as before if you shuffle the alphabet yourself before calling the library.

Re: Sqids – Generate short unique IDs from numbers

#210

Post by 3cats-in-a-coat »

3cats-in-a-coat wrote: post #112
sandstrom wrote: post #102

Neat library! We're using randomly generated strings for many things. IDs, password recovery tokens, etc. We've generated millions of them in our system, for various use-cases. Hundreds of thousands of people see them every day. I've never heard any complaints about a random content-id being "lR8vDick4r" (dick) or whatever. But nowadays our society is so afraid of offending anyone, that profanity filters has extended…

The block list is 2/3 of the (minified) library. I found this entire choice odd. First, it's highly incomplete because you can find at least 10x more combinations spelling the same "word". And probably 10x more slurs that aren't in this block list. Second, because it's hardcoded in your source. Third, because there are more elegant solutions. Such as to pick an alphabet that can't spell readable words unless you're t…

A slight mod, I'd remove Y despite not exactly a vowel, and add back digits that can't be interpreted as vowels.

bcdfghjklmnpqrstvwxzBCDFGHJKLMNPQRSTVWXZ25679

Gives us base 45. And below is a JS snippet to make an id. There's your lib.

    function id(num) {
        num = BigInt(num);
        const dict = "bcdfghjklmnpqrstvwxzBCDFGHJKLMNPQRSTVWXZ25679";
        let id = '';
        while (num > 0n) {
            id += dict[Number(num % 45n)];
            num /= 45n;
        }
        return id || dict[0];
    }
Example:

    id(123456789012345678901234567890n);

    "bq99hC6fbtjLrkxLPm"
Post reply on HN