oh hm, i thought I had fixed every case where that popped up. I can't reproduce the issue on any browser on my machine - how did you jump to the bottom (hotkey, scrollbar, scrolling for a trillion years) and what platform are you on (if you don't mind sharing)?
Chome on Windows. Grab the right scroll bar and pull to the very bottom. Once at the bottom try to scroll down with mouse scroll wheel. Screen goes blank and the error appears in the console.
OH! Thanks for the precise reproduction steps, I had done my testing with a trackpad and had missed that! Writing a little fix now (I'd hate for you to not be able to see the last UUID)
alright, a fix that I think covers this crash and a few others I found as a result is rolling out now.
for 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.
This reminds me of some code I stumbled on recently, where someone had implemented a custom exception they could throw if their 32-bit loop counter was greater than the maximum value of a 32-bit integer.
This is funny I like it. Basically just captures the scroll input and iterates through int128s and their UUIDs on a static page to fake a scroll. My feature request would be to add smooth scrolling.
I use this all the time but someone decided to disable it by default. For those who haven't turned it on after a reinstall yet, or haven't discovered the setting: about:preferences -> search autoscrolling
Oh my. Brings me back to my internship at a web development firm in Venlo. Someone "hacked" the company (somehow knew the master password used for everything) and deleted half the websites. Could restore from backup iirc but you know what the solution was?
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
PINs can be up to 6 digits (at least here in the UK, but I doubt it's country specific), even though the ones they give you by default are only ever 4. So that's only a leak of 1% of them.
That provides very valuable information: DO NOT TRUST this machine to be secure!
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.
Are you really worried that a card machine is going to leak your PIN? That doesn't seem to be a common attack vector compared to a third-party skimmer being attached or someone just mugging you and demanding your PIN under threat of physical violence.
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.
I'm not worried specifically about the PIN leaking.
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.
"Must support 6-digit PINs" is not part of "the spec for secure credit card transaction handling" – which is also not a (or at least one) thing: There are dozens of card networks, and many of them have tons of regional variations.
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.
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.
Are you arguing to just allow any byte in names (which are ultimately user-defined input data), including 0x00, Unicode byte order markers etc., in a thread about a perceived correlation between developers' lack of i18n awareness and security bugs no less?
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).
I agree: An annoying/avoidable implementation shortcoming, but arguably relatively orthogonal to security.
> 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.
Ok, but that doesn't answer my question: what specific problem are you worried about that would allow someone to steal your money, that isn't incomparably unlikely compared to other methods? I'm just not aware of any problem that has happened in practice from poorly written card reader software.
Why? PINs are limited to 4 digits in many markets, so it's not exactly extreme for a developer to not consider the (to them) edge case of 6 digit PINs on foreign cards.
Conversely, it seems very possible to support 6 digit PINs and yet still make a ton of horrible implementation mistakes, security and otherwise.
Why is the space thing inherently insecure? I’m thinking bad form validation could trip it up and be considered “not handled” vs concerns suggesting plaintext storage
For some reason, a lot of credit card processing APIs are still oriented around physical card machines, so they have a lot of fields devoted to self-declaration of the available features.
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.
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:
My card doesn't even let me include repeating digits in its PIN. I suppose it can make a one-off guess more likely than one in a thousand to correctly guess my PIN.
Is it repeating in the whole PIN, or in digits next to each other? I'm trying to resist the nerd snipe of what the total number of possibilities would be in the latter case...
I believe it would be 7290, or more generalized, S(N) = 10 * 9 ^(N-1) with N being the length of the code and S being the number of combinations (assuming that a decimal system is used)
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:
Which is honestly not a bad idea, given that somebody shoulder surfing or trying to read smudges on the PIN pad becomes much easier in the case of repeated numbers.
"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).
Haha, I have a file in my home directory that has every possible SSN because I wanted to be able to tell a friend “I have your SSN in a file on my computer.”
I think this is a joke, but I think it is a problem if someone finds any sensitive uuid here, because the list on this website is a tiny subset of all possible uuids, so it provides a useful rainbow table for anyone attempting brute force attacks. I.e. generating and using random uuids would have an astronomically small success rate, whereas trying the ones on this site may not (depending on where they came from, which I'm not sure of).
Oh.. ha, gotcha. Thanks for explaining. Incidentally, glad uuid's computed on the fly (as opposed to pre-computed) as I think the site would require a very (impossibly?) large database.
All possible UUIDs are in this page, it’s not a tiny subset.
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.
> depending on where they came from, which I'm not sure of
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.)
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.
Yeah, I at first, I though I knew exactly how it worked. Then I saw the search field, and I suddenly had no idea what the hell was going on. Now, the big question, do I want to spoil the magic trick and read how this was done, or should I keep being astonished and flabbergasted?
I disagree with my sibling comment. The trick is beautiful. If you generate UUIDs such that each bit in the result can be reliably traced back to a single bit in the input, then you can take a substring of the UUID and use that to infer which bits of the input integer must be set to produce that substring. So you can produce a whole list of input bytes that meet the criteria and those become your search results.
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.
> I disagree with my sibling comment. The trick is beautiful. If you generate UUIDs such that each bit in the result can be reliably traced back to a single bit in the input, then you can take a substring of the UUID and use that to infer which bits of the input integer must be set to produce that substring.
...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.
I'm really happy that the trick was magical to you - I was so surprised and delighted when I realized that this was possible, and I wasn't really sure if anyone else would feel the same way!
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
> If we didn’t care about generating valid UUID v4s, we could just generate 2^128 numbers, scramble them, convert the resulting bits into a hex string, and intersperse some dashes.
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
But since you're generating more numbers than you need, you're going to end up with 64 copies of each UUID in your final stream. This won't matter because no one will ever be able to notice, as long as your faux search functions avoid pointing it out.
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.)
FWIW, "search" doesn't work on mobile (Chrome on Android): I go to "Find in Page" and none of the magic happens. It's also bypassed on desktop when I manually open the search box via Edit->Find->Find... instead of using Ctrl+F.
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.
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. :)
Searching is very similar to a common approach for building a naïve spellchecker: given an input, generate all the possible matches it can be part of. You're not searching in a corpus, you're using the input to generate indices into the corpus (list of UUIDs here, list of words in the dictionary in a spellchecker).
The explanation for full-text search was actually slightly more intelligent than what I initially assumed. I figured it just generated UUIDs until it found one that was in the correct direction of search (for the next/previous button), since I had observed that walking forwards and backwards in search results was giving different results each time, but in fact the author did the slightly better thing which is to just generate a bunch of possible results and then pick the best (I wonder how many results it generates for this?).
The full text search is a little confusing because it doesn't actually search them in order, though it appears to at first. And if you click "next" a few times and then "prev" the same number of times, you don't necessarily end up back at the same UUID you were at before. It's a neat-seeming trick though.
It’s an interesting question whether that could be fixed. I think the answer is Yes. If the author didn’t do any scrambling, and just displayed UUIDs in numeric order, then it’s trivial to enumerate search results in order. Likewise, if you do something like adding a constant mod 16 to each hex digit, you could do the same thing when you generate UUIDs matching a substring. So the question becomes whether you could find something like that that gives a sufficiently convincing illusion of entropy but is still reversibile when you hold a subset of the digits constant. And it seems like it should be.
FWIW I am super interested in this question but feel like I don't know how to derive a satisfying answer, maybe because the one of my goals here (add "enough" entropy) is a real fuzzy "I know it when I see it" sort of thing.
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!
My first thought was to use linear transformations over Z_2 as a field, as that would create a natural interpretation of fixing certain bits as taking a linear subspace. Interestingly this leads to the property that XOR is preserved.
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.
I did some fooling around with this and it seems promising.
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 want to find the next index whose encipherment ends in -110. This sets up a system of equations Dx = y, where x_3 = 1, x_4 = 1, x_5 = 0, and y tells us the index of x. By multiplying that out, we get:
So we can freely choose any values for y_1 and y_5, and the rest will be filled in by constraints.
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.
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
Let's note that ~(e1e0) = 1e1f. Start from 16 instead and you'd see f0f00f0f. Here are the eights:
3332bbbc
Individual bits show pretty striking patterns. Since the UUID is reported in hex, that can be mitigated a little by the fact that each hex digit combines four binary columns. But so far it seems pretty likely that this would result in the list of UUIDs looking decidedly nonrandom. There might be quite a bit of shared material between adjacent UUIDs.
Can you solve this in general without doing integer linear programming? How else would you know how to find the lowest index greater than the current? In the field GF(2), using 0 might not minimize.
Hi! I do not know enough of the relevant math to appreciate what you're doing here (yet); I am going to try to do some reading to understand this better, but if you have any advice on where I should start I will gladly take it.
The important thing about matrices is their linear properties. Most proofs in linear algebra over real vector spaces don't rely on the particularities of the real number system, just the fact that it is a field [0].
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.
[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.
You've sniped me and I'm going to try and tackle this over the weekend. What's the best way to exchange things for you? Also, have you explored modular multiplicative inverses at all?
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
Would it be easier if only the lowest bits of the index contributed to the "entropy"? Like if the 2^16th UUID was the one right after the first and n + 2^16 was the one after the nth. You wouldn't notice the pattern but it'd be easier for the computer to handle. I guess if you were searching for a substring you might notice the ones surrounding the matches look almost the same from match to match...
Let me cook something up for you. It's an interesting puzzle.
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.)
Yes, it's possible with certain restrictions on the function. Here's an example:
u128 uuid_iter(u128 x) {
b = (x * x | 0x5) + x;
c = prf(x);
return (b ^ (c << 2)) & u122_mask;
}
This is a T-function, a function where the Kth bit only depends on the K-1 lower bits. prf() is a pseudo-random function that can be anything you like as long as it's another T-function. A standard LCRNG like (48271 * x) % 2147483647 works just fine for instance.
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.
A great example of Teller's observation that "sometimes magic is just someone spending more time on something than anyone else might reasonably expect."
My favorite of these was a trick where someone picked a card out of a deck and then Teller revealed a large version of that same card in an unexpected area in the vicinity, It turns out that what he had done was hide a complete set of large cards in the area before the trick and memorized the location of every one of them so, e.g., the king of hearts would be at the top of a palm tree, the three of spades under a drink tray, etc.
The best part is that that kind of trick usually becomes more, rather than less, impressive when its inner working is revealed. I recently got to see them perform live, and my favorite trick by far was one of that kind.
I love these and my kids who are a little obsessed with stage magic right now are at the perfect age for Penn & Teller videos so I need to stash these for the next time I have them. There’s definitely skill levels involved, even at the professional level (and Penn & Teller are definitely among the best out there). We’ve been to two professional magic shows in the last year, one in Wisconsin Dells, the other in Lake Geneva (both venues starring their owners) and it was apparent that the Dells guy was much better than the Lake Geneva guy (although the second magician the Lake Geneva guy had some impressive work to show).
Ricky Jay (RIP) is also extraordinary and has a handful of videos on YouTube. His stuff is mostly with cards and his humor is more aimed at adults. One of my favorites is his appearance on Arsenio Hall (I wish this was better quality):
Yeah, Ricky Jay was the last of a breed (he was also a friend of a friend, something I only learned after both he and the friend had died). He was very schooled in a lot of the street con games and was also a scholar of historical frauds and cams. He published a small-circulation magazine with his researches in the latter.
And of course his appearances in various David Mamet–related properties were not to be missed.
Watching Teller do the cups and balls trick with transparent cups is mesmerizing.
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.
There was a video of a magic trick I saw where the trick was almost certainly accomplished by false shuffles. I know how to do a few false shuffles, in theory, but, the magician (Ricky Jay, I think?) was just so good at the false shuffles that I was more impressed than if I didn't know how it was done.
Agreed. Everyone love puzzles that are worthy of an entire section in a blogpost for their interview questions, rather than stuff actually relevant to the job.
So I just brute forced every UUID in existence on my RTX GPU and loaded the dataset into a HA opensearch cluster on AWS. It took about 5 years of calling ‘uuid.Random()’ to effectively cover about 64% of the keyspace which is good enough.
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)”
I could imagine some candidates starting with their default tools like this, and start complaining about the cluster performance after a few weeks.
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.
> The fact that the search works impressed me more than anything. Of course, like every great magic trick, it seems so simple once it is explained.
> 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.
I searched for 1337, and then 13371337, and then 133713371337, and I was flabbergasted they've got a search setup for this (which ctrl-f opens up). Thanks for posting the blog post!
For the even more curious, UUID has 5316 decillion 911 nonillion 983 octillion 139 septillion 663 sextillion 491 quintillion 615 quadrillion 228 trillion 214 billion 121 million 397 thousand 304 values. Imagine the fact that there aren't as many kms to reach GN-Z11 (farthest known galaxy in the Universe I think) as there are digits above
This is neat, although I pushed it later with incremental search and it seems to be skipping results as it only found ~50 when searching for `-000000000000`.
The UIA (Universal Internet Authority) is worried that by using UUIDs we are left with only around 34 trillion UUIDs per star and planet in the observable Universe. So the cosmic router might become DHCP-leasing dark matter.
We may be lucky that it didn't work. It appears from GNU units that printing this all out on paper would be about a hundred solar masses. Maybe about fifty solar masses if you print double-sided.
At work our clickstream data carries an 'event_uuid' column which combines uuid, bigint, account numbers and about 10 other identifiers. It makes joining really convenient when you don't know what column to use.
Weissman score doesn't really have meaning anymore if the input is constrained. For example this website is 200KB as per the network traffic and I can beat it handily with ten-line script to generate every UUID. Or even verbally by just saying "every UUID".
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.
You were so preoccupied with whether you could, you never stopped to ask if you should.
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!
For the implementation of the core logic, I probably would have gone for the lazy solution of iterating AES until the output is <2^122 (64 times on average).
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.
Thank you for finally giving me a name for this concept. I've run into lots of code implementing them badly, but there's a bit of a semantic hill for others when you don't have a better name than "1-cycle permutation".
380 comments
[ 6.0 ms ] story [ 313 ms ] thread[0]: https://privatekeys.pw/keys/bitcoin/1
Random key: balance is zero.
Real key: balance is (now) zero
No spoilers, but the last one's a doozy!
for 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.
https://www.merklemap.com/search?query=*-*-*-*-*.com&page=0
Well, some of them are :)
It would be great if there was an API because I’m working on an UI that needs UUID autocomplete. Thank you!
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.
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
Check if your UUIDs are part of the leak.
Takes me back to when my password was leaked:
https://github.com/danielmiessler/SecLists/pull/155
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.
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.
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.
Also: https://www.ancestry.com.au/name-origin?surname=null
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).
> 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.
Conversely, it seems very possible to support 6 digit PINs and yet still make a ton of horrible implementation mistakes, security and otherwise.
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.
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:
And then you hit OK and the PIN is accepted.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).
Both in terms of security, and in the crime of vulnerating it.
Oh well, time to reformat
https://eieio.games/blog/writing-down-every-uuid/
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.
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.)
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.
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.
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
(I am so sorry)
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:
But since you're generating more numbers than you need, you're going to end up with 64 copies of each UUID in your final stream. This won't matter because no one will ever be able to notice, as long as your faux search functions avoid pointing it out.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
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.
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 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:
and our deciphering matrix D, the inverse of N: We want to find the next index whose encipherment ends in -110. This sets up a system of equations Dx = y, where x_3 = 1, x_4 = 1, x_5 = 0, and y tells us the index of x. By multiplying that out, we get: So we can freely choose any values for y_1 and y_5, and the rest will be filled in by constraints.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:
Let's note that ~(e1e0) = 1e1f. Start from 16 instead and you'd see f0f00f0f. Here are the eights: Individual bits show pretty striking patterns. Since the UUID is reported in hex, that can be mitigated a little by the fact that each hex digit combines four binary columns. But so far it seems pretty likely that this would result in the list of UUIDs looking decidedly nonrandom. There might be quite a bit of shared material between adjacent UUIDs.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.
[2] https://en.wikipedia.org/wiki/GF(2)
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 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.)
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.
-- Night Watch by Terry Pratchett
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=8osRaFTtgHo
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):
https://youtu.be/z7InE1zXAY4
Documentary:
https://www.youtube.com/watch?v=iWM4qQWwnu0
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.
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.
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.
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.
Actually, it looks like it alternates between those two phrases.
Millions of UUIDs generated! All so one would randomly be picked as the lowest valued and the attached record returned. Such a waste!
We truly live in an age of wonders.
29113161-136d-411e-9efd-5b24a910c307
I'm going to take this one if no one minds, please select something else for your purposes.
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.
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!
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.