For the curious, here's the linked blog post describing how the project works: https://eieio.games/blog/writing-down-every-uuid/
Edit to add: I'd only tried searching for an exact UUID when I wrote this comment. I didn't realize it supports full text search! Now I'm even more impressed.
And of course, I'm proud to be providing so much utility here - finally we can find and use UUIDs tailor-fit to our needs
You can do that anyway. You'd only need the twiddling if you wanted to limit the amount of numbers you generate to 2^122. Since you're willing to generate 128 bits:
// get encrypted value
uint128 bits = encipher(seed);
// clear zero bits
bits &= 0xFFFFFFFF FFFF 4FFF BFFFFFFFFFFF; // instead of 4 and B, you can use 0 and 3
// set one bits
bits |= 0x00000000 0000 4000 800000000000; // these have to be 4 and 8
Exercise for further development: modify substring search so that it follows the expected behavior of finding matches in order within the page. [I don't recommend attempting this.]
With a linear algebra library, you can guarantee that you've found the next, or the previous, match in sequence. I don't know what the state of the art is for fast linear algebra in javascript, though.
(The matrix approach also has the advantage that, when your full-text search problem has 2^115 solutions, you can compute the one you want, the next one after some index, without having to compute them all.)
very fun to have received so many pointers here, hopefully I'll be able to do a follow up blog once I've finally let people find all the good UUIDs
fe11a710-babe-4150-ace5-b19b1accd1cc
(I am so sorry)
I wonder if there's (yet) a browser API you could hook into: the same way browsers allow JavaScript to manipulate the history [1], maybe there's a way to manipulate the Ctrl+F/find-in-page search results.
[1] - https://developer.mozilla.org/en-US/docs/Web/API/History_API
That is, right now you're capturing the Ctrl+F keypress and opening your own custom thing to read the user's search string and act on it. But what we'd really like is a way to be notified "The user just asked to search for 'xyz'. Would you like to capture that event, or let it go through to the browser's default behavior?"
A quick Google search found nothing like that exists yet. I then asked ChatGPT about it, hoping that ChatGPT would at least hallucinate a plausible design for the API — and had mixed feelings when it didn't. It just printed that 'Browsers do not provide a way to listen for the "Find in Page" search event due to privacy and security concerns' and suggested capturing the Ctrl+F keypresses exactly as you have done.
As someone else said, it would also be more like full-text search if you also considered the primary-key column, e.g. searching for "0390814603917539994005679487460590835" should jump to the 390814603917539994005679487460590835th row. (Highlighting-to-select pieces of the text also doesn't work: I'm not sure why not, since I would have thought the browser gives you at least that part for free.)
Besides "search" not working on mobile, the styling on mobile is such that the "scrolling" does not convince: to my eyes it looks too obviously like "changing the values in the cells of a fixed table" as opposed to "scrolling through the table itself." You could maybe mitigate that by animating quickly among three different page layouts with the table vertically offset by different amounts.
It occurs to me that if JavaScript has something like Python's `random.sample`-without-replacement, then you could set your `RANDOM_SEARCH_ITERATIONS` to 256 and achieve perfectly consistent (and exhaustive) "search" when the user has entered all but 1 or 2 hex digits of their desired result. And/or, you could just have the page secretly keep a history of the search results the user has already seen: this would prevent the user from finding out so quickly that "search + next + next + prev + prev" doesn't always get them back to where they started.
Speaking of exhaustive search results: With a bit more (probably equally algorithmically interesting) work, you could emulate the browser search's "7/256" by tallying up the number of UUIDs satisfying the constraint, e.g. if the user has typed "1234567" then you could display "1234567 (158456324585806817418058661888 results)" and maybe even fake up a convincing position indicator like "1234567 (17415833585801881134805987465/158456324585806817418058661888)". I guess if you display it as "1234567 (1.742e28/1.585e29)" then you don't even have to cheat that much. :)
This may have been added after your comment.
https://lasvegasweekly.com/news/2008/nov/20/man-ball-hoop-be...
https://www.thisamericanlife.org/619/transcript
https://www.youtube.com/watch?v=dhnATlPdG6A
Here they are showing how they do ball & cups by using clear cups and it's no less amazing:
https://www.youtube.com/watch?v=7jKuHiY397U
You gotta watch to the end. Arsenio bends a card when Ricky looks away and thinks he can follow it that way but... well, just watch. :-)
One of his shows (with some fancy card throwing):
Documentary:
And of course his appearances in various David Mamet–related properties were not to be missed.
Yes, you can see everything. No, you still can't follow it.
Sure, you can see that "something changed" after the fact when it is stable. However, Teller is so damn smooth and fast that any active change looks like teleportation.
But I'm gonna try to get a few more crypto-knowledgeable friends to chat with me about this and write up what I learn!
I think the biggest rabbit hole I went down was trying to use FEAL (which is very breakable) and exploiting the things that make it breakable. But this is very much not my area of expertise - I was learning as I was working - so it's very possible either that that was a dumb idea or that it was a great idea that I didn't figure out.
I also considered things like "focus on add lots of entropy to groups of 200 or so UUIDs, but have obvious patterns beyond that" which I think would be a reasonable strategy; here I just kind of ran out of time (I told myself I'd make this in a week)
Did some light reading about a few other things but nothing substantial
I implemented this in a very quick and hacky way for 32 bits. I generated a random boolean matrix M invertible in Z_2. To turn an input number x into a corresponding number y in an N-bit space, I convert x to binary and turn that into a vector of 1s and 0s, then multiply it by that randomized matrix to get y. Here are the first few y's corresponding to x=0, 1, ...:
00000000000000000000000000000000
0xx0x000xx00x0xx000xxx00xxx0x000
x0xx000xxxx0xxx00x000xxx0xx0xx0x
xx0xx00x00x00x0x0x0xx0xxx0000x0x
x0xx0x00xxx0xx0x00xx0x0xx0xx00x0
xx0xxx0000x00xx000x0x00x0x0xx0x0
00000x0x000000xx0xxx00x0xx0xxxxx
0xx0xx0xxx00x0000xx0xxx000xx0xxx
...
(Hoping the non-monospace font doesn't ruin the alignment too much.)
Which looks... random-ish? I expect that turning these into UUIDs may result in more random-looking sequences.
Not sure how to solve the problem of search with this, but the hope would be that the linear structure gives you what you need, since fixing bytes on UUIDs should correspond to considering linear subspaces of the y vectors. Perhaps this can also be used to apply lexicographic order on the corresponding x vectors (i.e.: ordering the indexes), so that you could jump to each UUID matching the search in order.
The first problem is that, when your enciphering function is a matrix, f(0) = 0. This looks bad, but we can easily solve that problem by starting the webpage sequence at an index higher than 0.
I tried to work through a much smaller version of the problem* by hand, and it looks like this:
We have our enciphering matrix N:
[[1 1 1 1 1]
[1 0 0 1 1]
[1 1 1 0 0]
[0 1 1 1 0]
[1 0 1 0 0]]
[[1 1 1 0 0]
[0 0 1 0 1]
[1 1 1 0 1]
[1 1 0 1 0]
[0 1 1 1 0]]
y_1 = x_1 + x_2 + 1
y_2 = 1
y_3 = x_1 + x_2 + 1
y_4 = x_1 + x_2 + 1
y_5 = x_2
Assuming we want the least possible value for y, this means we will pick y_1 = 0 and y_5 = 0, which then tells us that we want index [0 1 0 0 0], and we can jump to there. If we wanted the least possible value for y above a threshold (such as the current viewport), we'd pick y_n values accordingly.
Instinct tells me that libraries should exist for quickly solving systems of linear equations like this.
(For full full-text search, we'd need to do this several times, also finding solutions for the enciphered values 110xx, and x110x. This multiplies the work we need to do and the storage we need to use by an amount that is linear in the difference in length between the search string and the full UUID, which is still a lot better than trial-and-error.)
* I ended up doing it in 5 bits because every random 4x4 matrix I generated was noninvertible.
5, 7, 31, 10, 18, 16, 8, 11, 19, 17, 9, 28, 4, 6, 30, 0, 24, 26, 2, 23, 15, 13, 21, 22, 14, 12, 20, 1, 25, 27, 3, 29.
This might pass an eyeball test for random when viewed as decimal numbers. (Although there sure are a lot of cases where adjacent values are 2 apart!) It looks much worse as binary. Here's every ones digit, all concatenated into a hex string, starting from 17 again:
e1e01e1f
3332bbbc
To make an analogy with programming, you can think of a matrix as a generic container type. Normally, we think of the contained type as being the real numbers, but you could replace it with anything that supports the multiplication and addition operations -- that implements the "field interface/trait/typeclass". [1]
So you can define linear algebra over any field: the real numbers of course, but also the rational numbers, or the complex numbers. Fields can also be finite. In particular, the integers modulo n is a field if n is prime. My suggestion is to consider the case n=2. [2]
It's a bit hard to get geometric intuition about what matrices on finite fields even mean, but a lot of theorems we can prove in the real case generalize, because they depend only on the field properties of the reals. That's why I suggested it -- it would make things like inverting straightforward. And that natural relationship between linear subspaces and holding certain bits constant might make search possible.
The issue (which others pointed out) is that linearity imposes so much structure that it might not seem pseudo-random anymore. But you could consider something like XORing all numbers with a randomly generated bit string -- it won't hold up if someone looks closely but might fool the cursory human eye.
---
[0] https://en.wikipedia.org/wiki/Field_(mathematics)
[1] The analogy breaks down slightly because not only must the operations be defined, but they must also obey laws, which can't be expressed in (most) programming language type systems. But if you've used Haskell before, you'll have seen this before in the fact that a Monad has to obey the Monad laws.
I think you can get pretty far, if you compromise on your entropy: it only has to look random, not actually be random. (I mean it doesn't have to be cryptographically secure randomness.)
u128 uuid_iter(u128 x) {
b = (x * x | 0x5) + x;
c = prf(x);
return (b ^ (c << 2)) & u122_mask;
}
You can invert this by just running the function N times to test each bit from LSB to MSB against the result. If you know certain bits, you don't have to run those tests and you can order the matching UUIDs by the values of the K unknown bits from 0 to 2^(N - K) - 1.
You also don't need to keep track of the position with this method either, only a stopping point. Unlike the feistel network, this function also produces a full cycle when iterated as x_i+1 = f(x_i), only repeating after all numbers are produced. That means you could run this without a counter at all, just generating until the first value is produced again, for any bit length.
The way that post explains each step in a unique laconic tone is very enjoyable to read.
> Or maybe the site could feature “trending UUIDs” that are particular popular across the world right now.
> Edit to add: I'd only tried searching for an exact UUID when I wrote this comment. I didn't realize it supports full text search! Now I'm even more impressed.
But the trick to the full-text search is that it doesn't work.
The real magic trick here is that the uuids on the page only look random to us because of some bit twiddling and XOR trickery. If we had a better intuition for such things we would notice that successive UUIDs are just as correlated as successive integers.
Elegant stuff
...but that has nothing to do with what the website is doing. The accompanying article specifically calls out the fact that it can't be done while maintaining the appearance of an unordered list, and therefore it isn't attempted.
reminds of me this daniel dennett quote
Real magic, in other words, refers to the magic that is not real, while the magic that is real, that can actually be done, is not real magic.
To facilitate full-text search I created a langchain application in python, hosted on kubernetes, that takes your search query and generates synonymous UUIDs via GPT o1-preview before handing over to opensearch.
Opensearch returns another set of UUIDs, which I look up in my postgres database: “SELECT uuid FROM uuids WHERE id IN (…uuid_ids)”
You need a certain way of thinking to have a gut feeling "this could be expensive" and then go back, question your assumptions and confirm your requirements. Not everyone does that - better to rule them out.
Check if your UUIDs are part of the leak.
I'm from a country that has 6-digit PINs on most cards, and I've traveled to e.g. the United States where people are surprised that credit card PINs can be more than 4 digits, but in my experience, terminals accept them just fine. It seems like they are designed to suggest a PIN is only 4 digits but they will happily accept more. So while you're entering your PIN, the display looks something like:
[....]
[*...]
[**..]
[***.]
[****]
[*****]
[******]
Some of the APIs allow the machine to say "I can accept a PIN up to 12 digits".
However, I don't know if anyone 1) actually delivered on it and 2) how you'd know in advance just poking random devices in stores.
Similarly, any web site or app that can’t correctly handle a space character at the end of the password should never be trusted with anything of consequence.
Conversely, it seems very possible to support 6 digit PINs and yet still make a ton of horrible implementation mistakes, security and otherwise.
To answer the actual question: I don't know because I left my PIN at 4 digits, despite knowing I could use more, precisely because I didn't think it would really make my life any more secure.
The concern is that a 4-digit max PIN length is certainly implemented by someone who couldn't be bothered to read the spec for secure credit card transaction handling.
It's the equivalent of the "No brown M&Ms" clause or "Canary in the coal mine" test.
Nobody actually cares about the M&M color or some dumb bird.
In some markets, issuers only allow 4 digit PINs, and customers don't expect to have to press an "enter" key when they're done entering their 4 digit PIN – so the reasonable implementation is to allow only 4 digit PINs, or you'll be left with people staring at the ATM/POS terminal, waiting for something to happen.
Making an ATM that can accept cards from multiple issuers (which is the norm these days) and allowing only 4 digits is the same category of error as requiring that the first character of someone's last name start with a capital letter, or to block symbol characters in names.
> there are over a dozen different PIN block standards
You almost certainly don't need to support all of these inside the PIN pad or even ATM/POS. If necessary, translation can happen in other parts of the system.
People tend to very very quickly their mind on that one once they get a few right-to-left control characters that flip over the text layout of the entire program.
The reality is that there is often a tradeoff between keeping your test and edge cases simple via constraining allowable inputs and internationalization.
So I think you've got it exactly the wrong way around: These limitations might have happened precisely because somebody wanted to do the right thing from a safety/security perspective by doing overly strict input validation, at the expense of internationalization/compatibility.
Not saying that that's a good tradeoff in every case, but I really don't think you can draw any conclusions about a system's security by looking at whether it arbitrarily disallows some inputs (or if anything, maybe the opposite).
And from there, with variable lengths ranging from L to H, S(L, H) = 5/4 * 9 ^(L-1) * (9^(U-L+1) - 1)
So if the bank allows combinations from 4 - 6 digits, there would be a total of 663390 combinations to choose from.
Now, of course, the bank may decide to go from decimal to hexadecimal in the future - or maybe, there systems allow only duodecimal. In any case, the formula can be generalized further to account for all number systems - with B being the base of the system:
S(L, H, B) = (B/(B-2)) * (B-1) ^(L-1) * ((B-1)^(U-L+1) - 1)
This is only defined for B > 2 - in binary system, there's only ever two combinations which fit the constraint
"1111" would just leave a fingerprint on a single key, for example, and only one possible PIN (or maybe 3, if the bank/card allows 6 digit PINs).
Takes me back to when my password was leaked:
They're coming straight out of your processor :)
Careful where you scroll: Your password and your crypto wallet recovery phrase are in there somewhere too! (Unless you have one of those fancy 24 word long ones.)
They are generated by your device on the fly as you move through the list so you can’t really use it as a rainbow table any more than manually creating the table yourself.
Random key: balance is zero.
Real key: balance is (now) zero
Millions of UUIDs generated! All so one would randomly be picked as the lowest valued and the attached record returned. Such a waste!
What’s fun is what actually happens when you try to do these things. It’s disappointing, you can’t even get anywhere near one trillion pixels.
The limits I found five years ago when working at Fastmail, after a customer using IE found their scrollbar broke when they had around 200,000 emails in a mailbox (plus I just checked a couple of them again now):
• Firefox: a few years ago, ignored declarations that resolved to a value higher than 17,895,697 pixels (a smidgeon under 2³⁰ sixtieth pixels). Now, it clamps at that point instead, but maybe three pixels more or less, not immediately clear quite what’s going on and I can’t be bothered investigating. (All browsers seem to have inconsistencies in how clientHeight/getBoundingClientRect/dev tools/whatever report things, that close to the boundaries of possibility. It’s mildly fascinating.)
• IE: ignores declarations that resolve to a value equal to or higher than 10,737,418.23 pixels (2³⁰ − 1 hundredth pixels).
• WebKit: clamps values somewhere around 2²⁵ (~33,554,432) pixels.
• Chromium: matched WebKit when I tested, now it’s clamping around 22,360,882 pixels, but I’m on a 1.5× display, so the 2²⁵ could be connected with device pixels or such. But I think I was on a 2× display when I did the initial testing!
See also https://news.ycombinator.com/item?id=34299569 where I wrote more about it, with links to relevant source code.
(I'm also super curious how those numbers were chosen and about what would start breaking if the limits weren't there - maybe your example of weirdness around clientHeight etc gets at that)
I think you meant 'terrific' in the old original meaning.
And look forward to my realising your package doesn't quite do want I want and forking it
It's a fun implementation inspired by the short story https://en.wikipedia.org/wiki/The_Library_of_Babel and "At present it contains all possible pages of 3200 characters," though the character set is limited (no dash) so you won't find these UUIDs there.
A Short Stay in Hell (2009) by Steven L. Peck
It's a fun and scary read. Especially if you understand very big numbers.
Update: Another commenter already shared: https://news.ycombinator.com/item?id=42342653
We truly live in an age of wonders.
I wonder if modern web developers of modern web applications could somehow harness this technology.
It's ludicrous how our computer hardware is 1000x faster than it was 30 years ago in 1995, but software is so bloated that it is still slower!
Relevant: "Will Software Stop Getting Slower?" Jonathan Blow https://www.youtube.com/watch?v=4ka549NNdDk
Uncaught Error: Index out of range - must be less than 2^122for a while I thought I had an off by one error, which was pretty funny to think about in the context of trillions of items. but in fact I was just doing some bad react state management.
EDIT: That one is MINE. PLEASE DO NOT USE IT.
And because StackOverflow broke too, there's nobody available to fix it.
https://www.merklemap.com/search?query=*-*-*-*-*.com&page=0
Well, some of them are :)
69420694-2069-4206-9420-694206942069
is a valid UUID.
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
M = 4
N = 8,9,a,b
x = 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f
B00B1E5f-7117-4a61-816d-92710147f63f
* https://www.wolframalpha.com/input?i=ROUND%5B2%5E122%2F1000%...
Edit: Use 122 bit instead of 128 due to UUIDv4
HN recently (last few months) had an article explaining how large a number was. The number was something like busy beaver or 128 bit integers or something else.
It illustrated how large the number was by creating activities you would do, incrementing the counter as you did them. The sequence went something like this:
Walk, and every time you take a step. Add 1
After you have circled the earth, place a sheet of paper on a pile, and start walking again.
Continue, until the paper pile reaches the sun, then place a grain of sand in the Grand Canyon and start over.
Continue until you have filled the Grand Canyon, etc etc
What was the number? What were the steps?
Vsauce has a great video on this, and might be where that example was taken from.
https://www.youtube.com/watch?v=ObiqJzfyACM
That example starts 16 minutes into the video:
https://www.youtube.com/watch?v=ObiqJzfyACM&t=964s
But it's worth watching the whole thing.
That's why we need 128 bit numbers.
It would be great if there was an API because I’m working on an UI that needs UUID autocomplete. Thank you!
Maybe an SMT solver is a rather heavy-weight approach, but I think it fits the task of searching through 2^122 values :)
Edit: even with no cipher, it takes said approach ~1.6s to find that after 0x1067D3DC2F4951AEA8DB8D0108D7D65 the first occurrence of 0xABCD is at 0x1067D3DC2F4951AEA8DB8D0108DABCD with Z3 (cvc5 and Bitwuzla are slightly slower), which is perhaps a bit too slow.. perhaps it could be improved to something more reasonable by restricting the search to near the end until that fails, and reducing the matchable positions based on the dashes, but that's back to effort.
Edit 2: slightly more effort later:
cipher: 0x15FD586DF0CE258730098B94325ACE7 * (val ^ 0x93C324915DB2B3C4D4CD8135C0DDF1)
inverse: (0x1D52334877384DE3A6DAA4A3312A6D7 * val) ^ 0x93C324915DB2B3C4D4CD8135C0DDF1
example first 10 entries:
0: 2839676B79617D5B9FDF9D43CFB3077
1: 123C0EFD889357D46FD611AF9D58390
2: 143418475AFDC869FFF2B46C3468A45
3: 3E36BFD96A2FA2E2CFE928D8020DD5E
4: 002EC9233C9A13786005CB94991E413
5: 2A3170B54BCBEDF12FFC400066C372C
6: 2C2979FF1E365E86C018E2BCFDD3DE1
7: 162C21912D6838FF900F5728CB790FA
8: 18242ADAFFD2A995202BF9E562897AF
9: 0226D26D0F04840DF0226E51302EAC8
binary search max set to `10 * 2**search_bit_width` after after the chosen start
trying to find a match only in the last 3 possible places (i.e. searching WXYZ only matches *****WXYZ, ****WXYZ*, ***WXYZ**)
searching for 0xFF00FFCC after index 0xAAAAAAAAAAAAAA:
nearest match found at: 0xAAAAAAAD04E3DA
ciphered: 0x0E9399CC39B716BC96348AFF00FFCCD
time taken: 0.7s (bitwuzla or cvc5), or 1s (z3)
Have you read the blog post? I wouldn’t summarize it like that, it’s a little more involved than just iterating. I learned something today.
Who do I contact about this breach? I want names and addresses.
(Just like on HN, I can scroll so that just the bottom part of the first line of text is visible.)
99999999-9999-4999-9999-999999999999
(note the 4 in the 3rd block)
I'm curious why it's not 99999999-9999-9999-9999-999999999999 (all 9s)?
Would you suggest random 128 bit numbers, then? Otherwise it's hard to see what else would serve the same role without being UUID in a trenchcoat. And having identifiers is important.
The "4" in the 3rd block is the only permitted value as these UUIDs are using the GUIDv4 format. I'm not sure what's going on in the 4th block, but the references and linked RFC in the Wikipedia article might reveal more details: https://en.wikipedia.org/wiki/Universally_unique_identifier#...
It’s the smallest that’s less than zero right?
Also you'll find that the first character of the 4th block is forced to be 8, 9, a, or b. That's true of standard UUIDs of any version.
If you were looking for the biggest hexadecimal UUID, find one with f instead of 9.
One important feature is missing: From a proper search function I would expect to know how often my string is found. It could be that my password is rare, or that it is rather common. I need to know! Could the search also display the number of hits?
Jokes aside - you know the number of digits of the search string and if it is still a valid uuid. So computing the number of "matches found" should be possible...
(this also breaks browser forward and backward trackpad gestures)
Alternatively just use standard Format-Preserving-Encryption, which is usually a Feistel Network, similar to what they ended up with, but built on a standard algorithm, instead of a homebrew round function.
But the wheel would be tricky because you want to scroll by only one or a few items, not items/10k. With a static viewport-sized DIV set to overflow-y:scroll and large vertical content size, positioned so you don't see the scroll bar, when the mouse is over it it should capture wheel movement which you could translate to an offset from your macro scroll position.
Just a thought. Either way, love the thinking here, fun work :)
but did not find it. Search is just on active page, that gets ever longer?
Aside from missing a grouping in the middle, you need the version and variant bits, ie:
XXXXXXXX-XXXX-4XXX-VXXX-XXXXXXXXXXXX
where V is 8, 9, A, or B
searching for deadbeef-f00d-400d-a00d-deadbeef does return the expected matches
This was my favorite bit and speaks a lot about the craft behind this page! v cool <3
edit: actually this doesn't work because having the same start does not mean they are close together.
IMO that's half of "real work" - figuring out how to think about a problem. Insights are funny that way - stuff that is obvious to one person is game-changing to others.
Now all I need to do is hold my finger on the down arrow and keep watching for a *little* while to see every V4 UUID.
I think that's definitely possible. Especially if you realise that you only need a random-ish looking order, not a cryptographically secure random order.
Does it say anything about code-AI that a problem which should be (is!) very easy for machines, but very difficult for front-endy people, seems to also be very difficult for Claude?
ec971907-4564-46ec-b28b-d76f1a2233c8
58737c1a-9294-4ffa-8082-b5364923a59c
ba6ca980-b405-48b9-9770-252611d40ef1
Thanks!
Now I kind of want to do this for "every 12 character password"...
(0..999999999).
map { |i| i.to_s.rjust(9, "0") }.
map { |i| i[0..2] + "-" + i[3..4] + "-" + i[5..9] }Repeating it three times though I couldn’t (even with dashes added). :) I am sure I am holding the phone wrong.
0d42d789-fd08-44ec-a46e-e1e10e1e10e1
Edit: and the following 2^8-1 for friends and family, thank you.
He's using a bijection between the number on the left (which are ordered) and the UUID that's designed to produce something random-looking. The simple fact that bijection cannot produce the same output out of two inputs (or it's not a bijection) means that all the UUIDs are unique.
This site is specifically about “V4” UUIDs where the two dimensions are random and also-random. If you scroll all the way to the bottom you will see that the last table row is numbered the same value as the maximum 122-bit number, so the site is flipping every possible bit-combination within that space combined with the metadata bits that say “Hello I am a V4 UUID”:
irb> ::Array::new(122, 0b1).reduce { (_1 << 1) | _2 } => 5316911983139663491615228241121378303He's ensuring the uniqueness by indexing from 0, and applying the cipher to come up with a more "random" looking UUID.
[1] https://eieio.games/blog/writing-down-every-uuid/#toc:feiste...
A big part of this is that the possibility space is very large, so the chance of collisions is low. Many UUID versions also determine parts of the UUID via MAC addresses and timestamps, to ensure that different servers are highly unlikely to generate the same UUID.
for a uuid like 414c1bde-b676-4242-be35-887f01a24f10, if I take its suffix 887f01a24f10 (12 chars, 48 bits) there are still 19 chars (76 bits) to the left of it. (barring the constant 13th char identifier 4)
There still are 2^76 uuid's with that suffix to search through. It made sense with ipv6 addresses and cryptography, but for some reason I had this idea that uuid's didn't use an CRNG that covered the whole 128 bit space. A lot of wrong stuff rattling around in my memory for some reason, thanks for clarifying.
But overall you have that right. Every bit is either completely random or fixed. There are no reduced-randomness patterns unless you generated it wrong.
This will be the goto reference for hackers everywhere. Think of how much faster they'll compromise my McDonald's order with all 2^122 possibilities already computed!
185e45bc-750b-43d7-91ee-314159265358
Actually, it looks like it alternates between those two phrases.
Add an exclamation mark to the password
—
Which in turn reminds me of another internship where a computer upstairs got "hacked". Everything on the desktop was messed up, icons moved, random programs open, some files moved into folders at random... why'd anyone do that? The boss left it as-is for me to take a look at how this could happen—yes, including the thematic porn sites hinting 17-year-old me at what happened to his marriage. Not finding any hints, I started sorting the stuff back out and business continued as usual
Come afternoon, I was working on the computer when the mouse moved. Like, not me, I didn't move it. Was it the hacker? How are they connected? After a bit it moved again, but it didn't make any sense. I don't remember how I put 2 and 2 together but, going downstairs and seeing him at the media station using a wireless mouse downstairs, I got a dark suspicion
Yes of course it was an insider threat =) We bought a different wireless receiver for the mouse that day
TIL aaaaaaaa-aaaa-4aaa-aaaa-aaaaaaaaaaaa is a valid uuid