7 ms·
Plan B for UUIDs: double AES-128
- PaulHoule 4y agoI remember years ago rejecting this approach (encrypt internal keys) because the key size I was using wasn't the same as the block size of any standard block cypher and I didn't know of any variable size block size cypher. If the target is 128 bit identifiers though you can use AES.
- MonkeyMalarky 4y agoI like this because once you decrypt you can have all the nice properties of integer keys, like ordering.
- chrismorgan 4y agoThis is an approach that has been around for a long time, mostly with 32-bit and 64-bit block sizes. (e.g. if you search around, you’ll hear about Skip32 as a common choice Back In The Day, a variant of Skipjack crafted for the purpose.) I’ve been working on this problem for a few months from the perspective of yielding human-friendly IDs, and reached what I consider a finished state a few weeks ago, but haven’t published it because I was thinking about other things. I’ll probably publish it in the middle of next week. If anyone’s interested in a sneak peak (and final review!), they can email me and I’ll give a link. My initial just-about-ready-to-publish version encrypted with Speck32/64 (for 32-bit IDs) and Speck64/128 (for 64-bit IDs), and did base-58 stringification (ASCII alphanumeric minus 0, O, I, l). This produced about four billion 6-character IDs, then 11-character IDs after that. I was also toying with things with different block sizes, since I wasn’t enthusiastic about the 6-/11-character ID length. After feedback from interested people I became more determined to do so, because the feedback convinced me that case-sensitivity was sufficiently undesirable, and going down to base-36 or lower took it up to 7/13 characters. I tried Hasty Pudding, but it was too big and complex and unknown for my liking, though I did implement it and it worked… though I couldn’t even find the official test vectors, since they’re on a dead FTP site and the author didn’t respond to an email. I looked into FF1 and FF3-1 too, but patent encumbrance decided me against them. I ended up daring to create a variant of Speck with multiples-of-five word sizes. This actually ended up making my code smaller: the JavaScript implementation of my entire scheme is 1680 bytes minified, 915 gzipped with zopfli (and shedding a bit of functionality it can easily be taken under 1200/700). So now it’s using my custom Speck variant and a base-32 alphabet (lowercase letters and numbers minus 0, o, 1, l). [0, 2²⁰) becomes four characters, [2²⁰, 2³⁰) six, [2³⁰, 2⁴⁰) eight, &c. up to [2⁹⁰, 2¹⁰⁰) twenty. I also add one more step to allow for making valid IDs less guessable and the inclusion of a type discriminant if desired (and these are why I had the cipher go up to a 100-bit blocksize): id → sparsity × id + discriminant. Performance: my Rust implementation encodes all four-character IDs (about a million of them) in about 50ms on my AMD Ryzen 5800HS laptop, single-threaded, which at about 4.4GHz is a bit over 200 cycles each; but that’s actually 99% stringification: a benchmark of just encrypting all 20-bit values takes about 475,000ns, which looks like it might be exactly 2 cycles each, while still being Real Encryption. (I also have Python and JavaScript implementations, but I haven’t benchmarked them.)
- GoblinSlayer 4y agoConvert the identifier to a multiple of block size and encrypt that and back, AES round trip is lossless.
- ex3ndr 4y agoI actually using this scheme for several years now, but AES itself is not authenticated and I added truncated SHA256 to the ID to make it more robust.
- tptacek 4y agoWhat exactly would you be authenticating? The scheme discussed here is just using AES to generate the equivalent of a UUID.
- traceroute66 4y agoIt seems to me that this is (albeit in a somewhat convoluted way), "solving" one problem but opening a whole can of (cryptographic) worms on another. Namely the biggest chestnut being the old classic of performing decryption on untrusted data. Since basic AES-128 is not an AEAD cipher, you are basically in the realms of trusting untrusted input. Personally my preference would be to maintain UUID (or possibly KSUID-type implementations depending on application). And then if you need to partition/shard/whatever you do that by some other means (i.e. by or in conjunction with a different database column).
- aaaaaaaaaaab 4y agoWhat’s the threat model exactly? Here AES is just a bijection between 128bit numbers. It’s not like the AES cipher is going to blow up when you try to decrypt a special harmful bit pattern! It’s just a bunch of ones and zeros… If someone gives you a bogus ID, then it’s gonna decrypt to a non-existent ID. Which can also happen with plaintext IDs…
- BiteCode_dev 4y agoI really like ULID for this problem (e.g: https://github.com/ahawker/ulid https://github.com/ahawker/ulid) - similar characteristics to UUID: same number of bytes, equivalent collision resistance, hard to guess, etc. - start with a date, is monotonic, and is lexicographically sortable: not only it has great locality but sorting is super easy and most code get it right by default. - can be created from an existing date or uuid, and exported to a uuid, so there is a migration path. - you get the creation date for free, which is always nice. As a bonus, you can now use the uuid as a base for dispatching, bracketing, sharding, etc.
- Vanderson 4y agoSame here. I am really, really hopeful there is a drop in replacement for ULIDs if they ever get abandoned.
- BiteCode_dev 4y agoIt's not a very complicated algorithm, they can't get abandoned, you can always recode it, and use it.
- ywain 4y agoI expect the new UUID formats (https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format https://datatracker.ietf.org/doc/html/draft-peabody-dispatch...) to fill that need once they get standardized and made available in standard libraries or popular packages.
- Sytten 4y agoThe last draft expired without any consensus so I dont have high hopes for this one. We will see.
- BiteCode_dev 4y agoEspecially UUID7, it it becomes standard, ULID won't be necessary anymore, unless you want a shorted text representation. But ULID exists right now, UUID7 is still in the making.
- bob1029 4y agoThis is a pretty clever idea, but I have to wonder how much of a concern an "ExternalId" column is today. Assuming you are really paranoid, and each is 256 bits of the best CSPRNG output available, then for a table containing 1 million records you are only talking about an additional ~32 megabytes of overhead. With modern CPUs and most applications, this extra amount of data is not going to move the needle at all.
- piaste 4y agoThe two approaches can be combined! You can use AES to generate and store the ExternalId column. As you pointed out, this saves you from having to encrypt/decrypt it on the fly every time, at the cost of an extra lookup and some storage (you're going to want an index on that column as well). If it ever comes up that you prefer to do it on the fly, you can just drop the column. All your external references will still be valid since the ExternalId was generated deterministically.
- dangerface 4y agoYup, I once tried using aes to create uuids but then ended up with a page that would send a thousand results to the client each one needing a uuid generated, multiply that by a thousand users and the cpu time started to add up it obviously wasn't going to be as scalable as just storing the uuid. Possibly only doing one round of aes or skipping the key expansion steps would make it more scalable but I didn't have the knowledge to do that securely.
- DmitryOlshansky 4y agoPlus the advantage of changing the way you generate your externalIds. As long as they are stored the external links to said record stay stable which is typically important with integration
- dragontamer 4y agoImma just leave this here... https://github.com/dragontamer/AESRand/blob/master/AESRand_Linux/AESRand.cpp https://github.com/dragontamer/AESRand/blob/master/AESRand_L... Algorithm: void AESRand_increment(__m128i& state){ state += increment; } std::array<__m128i, 2> AESRand_rand(const __m128i state){ __m128i penultimate = _mm_aesenc_si128(state, increment); return {_mm_aesenc_si128(penultimate, increment), _mm_aesdec_si128(penultimate, increment)}; } TL;DR: with respect to the original article. The AESenc instruction generates significant entropy so long as all four uint32 changes. Instead of adding +1 to the 128-bit "pre-AES encryption", add " __m128i increment = _mm_set_epi8(0x2f, 0x2b, 0x29, 0x25, 0x1f, 0x1d, 0x17, 0x13, 0x11, 0x0D, 0x0B, 0x07, 0x05, 0x03, 0x02, 0x01); " Because this is a 64-bit add of an odd number, it will repeat after 2^64 iterations, which should be good enough for most people's purposes. Once you have that kind of add happening, you end up with more than sufficient entropy from AESenc. For those unaware, AESenc is approximately 10% of a proper AES, its the hardware AES instruction on x86. Repeating AESenc over the expanded-key 10 times results in a proper AES encryption (or decryption). --------- Because modern CPUs have 2x parallel AES pipelines (2 AES instructions per clock tick), my RNG supports a 256-bit output every 4 clock cycles. I accomplish this by having AESenc on the first argument, and then AESenc / AESdec on the results of that (encode being the first 128-bit result, and decode being the 2nd 128-bit result). -------- If you took my RNG output (which can be generated deterministically every 4 clock cycles), and then just AES encrypted that random number generator, you probably would get your cryptographically random numbers that are guaranteed not to repeat.
- trollied 4y ago> where the fundamental problem is the tension between nicely structured primary keys that tend to improve spatial locality in the storage engine, and unique but otherwise opaque identifiers that avoid running into Hyrum’s law when communicating with external entities and generally prevent unintentional information leakage. I tend to use an integer for the database PK & internal associations, then an external_id that is used with external party data exchanges.
- deleted 4y ago[deleted]
- masklinn 4y agoThere is one thing which troubles me here: Postgres does not support clustered indexes, so the "spatial locality of the storage engine" is non-existent, only the indexes should be impacted. Why would you have "UUIDs writing to pages all over the place"? Or is that, and the WAL amplification, be solely about the updates to random btree leaves?
- to11mtm 4y ago(Not a DB Engineer but poke at enough different DBs to armchair semi-confidently) In the case of Postgres I'd expect to see it indeed be mostly about random updates to leaves. I suppose Partitioning could come into play but I'm not sure how you'd set it up in a way that was beneficial and dynamic enough for the situation in the first place. But, It's worth remembering that most other DBs (Oracle, MSSQL, MySql/etc) do have clustered indexes, and in some cases you can't just flip over to Postgres. (Even if you want to!)
- SigmundA 4y agoboth MSSQL and Postgresql support fill factor as well, which nobody seems to mention. Setting a lower fill factor leaves more room in the pages to avoid page splits with random writes. Also random writes can be beneficial in that you are not hot spotting the last page as you are with sequential ID's. Its not black and white, there are some good advantages with random ID's but you need to manage them properly.
- patrec 4y agoYeah, it does: https://www.postgresql.org/docs/current/sql-cluster.html https://www.postgresql.org/docs/current/sql-cluster.html
- BudaDude 4y agoI read this as Plan B for IUDs and was confused why we would want to encrypt birth control.
- aarontait 4y agoSame. Had to take a sip of coffee and do a double take.
- femto113 4y agoMany years ago people (including me [1]) started using the Skipjack cipher for the purpose of obfuscating sequential numbers when they needed to be externalized (e.g. putting auto-incremented ids in urls). Since it was originally designed to encrypt media in realtime on 90s era silicon it's quite low overhead. I've often wondered if/when a database vendor would get around to building similar functionality directly into their engine since that would make the approach much more practical to adopt. [1] https://www.npmjs.com/package/skip32 https://www.npmjs.com/package/skip32
- Dylan16807 4y ago> Rather than try to pinpoint the exact level of dedication we’re trying to foil, from curious power user to nation state actor, let’s aim for something that’s hopefully as hard to break as our transport (e.g., HTTPS). AES should be helpful. AES is in that range for the short term. Not over months or years. Anyone considering this should keep in mind youtube's mass privating of older unlisted videos, which was needed because they used to use an encrypted counter for video IDs. That key was in so many places, and it got out.
- feanaro 4y ago> AES is in that range for the short term. Not over months or years. Why do you say so?
- Dylan16807 4y agoOh, I guess my second paragraph is not a good enough explanation? The key leaked, which means anyone that has the key can generate all the IDs from videos uploaded before 2017. If your key ever gets out, you face the same problem. The secrecy of all existing IDs is gone. With HTTPS, you can rotate keys often, older connections would have to have been packet-captured to get decrypted, and newer connections mandate perfect forward secrecy.
- feanaro 4y agoOh, I somehow managed to understand those two paragraphs as two separate observations. Sorry. Yes, the key can leak and there's no forward secrecy in this scheme. That's a valid point.
- chrismorgan 4y agoHave you any source for that being the reason? https://support.google.com/youtube/thread/114633828/changes-to-unlisted-videos-uploaded-before-2017?hl=en https://support.google.com/youtube/thread/114633828/changes-... is all I find, and it says this: > In 2017, we rolled out a security update to the system that generates new Unlisted video links. This update included security enhancements that make the links for your Unlisted videos even harder for someone to discover if you haven’t shared the link with them. That doesn’t imply a leaked key to me (I’d consider that wording dishonest if it actually is describing a leaked key), but rather an increase in the sparsity of the ID space, presuming they were using encrypted sequential IDs.
- codereviewed 4y agoUUIDs have always seemed to be an over-engineered solution to a minor problem. In the cases I've seen them used folks are trying to get away from auto-incremented identifying serial numbers. Ostensibly, this is because it makes guessing other IDs in the database (or whatever) fairly simple and that could be a source for leaking information. To me this is just security though obscurity. Just because I know an identifier doesn't mean I should be able to do _anything_ with it. If there are contexts where you really can't share the ID you should salt and hash it and use that value.
- preseinger 4y agoAt a minimum, sequential generated IDs trivially expose creation rate, which is almost always significant information.
- chrismorgan 4y ago> Just because I know an identifier doesn't mean I should be able to do _anything_ with it. Depends. If it’s a sequential ID, then sure, but if it’s sufficiently random and sparse, then it can be fine to use it as authentication. But it’s not always about authentication and security. The information leak itself is regularly a problem. See https://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem for one practical example, though you normally don’t even need anything that fancy. Businesses do this where they can to analyse competitors, figure out how big they are, how they should price things, &c.
- GoblinSlayer 4y ago>If there are contexts where you really can't share the ID you should salt and hash it and use that value. That's UUIDv5.
- nly 4y agoIf it was easier to have scoped id's it wouldn't be so bad. For example, instead of one OrderID for all orders in the order table, have customer specific order numbers that start at 1, and are only unique in tandem with a customer id. It's a pain in the but to implement this though in most databases.
- preseinger 4y agoI struggle to think of use cases where involving encryption in creating, parsing, evaluating, or otherwise using primary keys is anything but a mistake. But I'm sure I'm insufficiently creative.
- chrismorgan 4y agoEncrypting sequential identifiers is an excellent way of avoiding leaking the ID sequence, which is regularly at least mildly sensitive data, generally more sensitive than you expect, and preventing ID enumeration (either completely, if the ID space is sparsely occupied, or at least sequentially if it’s fullish).
- preseinger 4y agoIn what circumstances does the value of that encryption outweigh its costs? Particularly in high-RPS (e.g. 1M+ RPS) applications? My intuition is that UUIDs, ULIDs, etc. would be orders of magnitude faster to {generate, parse} than anything involving an {encryption, decryption} step; am I off base?
- wongarsu 4y agoInternally you can work completely with sequential int64 IDs, and at the API edge you have to spend ~30 clock cycles (about the cost of an L3 cache hit) on each id to encrypt/decrypt it. For any workload that can benefit from better data locality from sequential IDs this could well be a performance win over UUIDs, especially at scale. Of course ULIDs offer something very similar. But they leak more information, which makes them less desirable for some use cases.
- preseinger 4y agoThe benefit here, I guess, that you get the advantages of sequential IDs internally? I can't see how this could possibly outweigh the costs of user-visible IDs being different than internal IDs, and transformable only thru a {de,en}cryption process -- requiring all the standard maintenance, key rotation, etc.
- swyx 4y agoI've been collecting all my notes on UUIDs here https://github.com/sw-yx/brain/blob/master/R%20-%20Dev%20Notes/uuid%20list.md#uuid-list https://github.com/sw-yx/brain/blob/master/R%20-%20Dev%20Not... in case it is helpful to anyone
- kevin_thibedeau 4y agoA maximal length LFSR will give sequential IDs without the problem of known zero bits.
- deckard1 4y agoMaybe I'm way off base here, but this seems like a really really niche solution for a situation you probably(?) won't be in for long. You have a single DB running on a single machine. But you also care this much about write performance that you need sequential ids. How much longer is that single DB going to work for you, if write performance has become an issue? I wonder. Because soon you might need to shard, which you will lose sequential ids and benefit of spatial locality right? There seems a narrow band of operation where you're seeing the benefit of performance from sequential ids but can still function on a single DB instance. I feel like you may be painting yourself into an architectural corner and a headache rather than just doing the easy thing first and using UUID.
- anarazel 4y ago> You have a single DB running on a single machine. But you also care this much about write performance that you need sequential ids. How much longer is that single DB going to work for you, if write performance has become an issue? Potentially a long time. Anecdotal: I helped a PG user in ~2012 (+- 2 years) to move to some sequential-ish uuid-like thing because they were facing outages, and as of last year they were still using a single instance for that service. And they grew by a lot. > Because soon you might need to shard, which you will lose sequential ids and benefit of spatial locality right? You don't need (not even want) perfect spatial locality. It's ok as long as it's not uniformly random.
- chrismorgan 4y agoMost projects can reasonably and usefully stick with central ID allocation forever. And even if you want to decentralise ID allocation, so long as you still have control over the nodes, you can still use roughly sequential identifiers if you choose, by multiplying by some standard value and offsetting the sequence by a node ID. You could reserve ten least significant bits for a node ID, for example, allowing up to 1024 nodes to generate IDs. So node 0 would allocate IDs {0, 1024, 2048, …}, node 1 {1, 1025, 2049, …}, &c. This requires more planning and possibly more maintenance, but will have the advantage of producing shorter IDs which can be highly desirable. Random IDs do have a place, but they’re massively overrated. The length required to control the collision risk is very significant.