Skip to the bottom header “My Favorite Number” if you care little about my rambles.
New Life Events
Life’s been a tad busy. Instead of doing cryptopals (whoops) I’ve participated in HACKDAC2020 where I was pretty much the only single person participant; the rest consisted of pretty large teams (from what I saw, ranging from size 4 – 12).
I was in the process of writing up what bugs I found when I came across the #MegaFavNumbers phenomenon on YouTube. Basically, a bunch of people (including one of my favorite YouTubers 3Blue1Brown) are all sharing some of their favorite numbers over 1 Million. I’m not sure why 1 million, but my guess is it’s because most of us have a large obsession with “million” or “billion” because they are reasonably nice, big numbers that come up in everyday vernacular.
Because I think it’s a quick fun write-up, I thought I’d share my own number!
A Preface (Or, Rambling on my Indecisiveness)
I actually struggled a bit, long enough to where it’s slightly embarassing, to settle on one. “A favorite number” should be so simple and meaningless, yet somehow for every number that I chose, I thought to myself “why did I pick this number? It’s so silly, no? I should stop thinking about it”. Note: I did not stop thinking about it.
And from there, I began to iterate. This number had to represent me. It would be like a tattoo– my personality. A bit silly, but I think it’s precisely because it’s so silly that I put a lot of thought into it before deciding something that will have 0 impact on my life. Like some quiz result on Buzzfeed, I’m most definitely reading too much into it.
Crypto Numbers
Considering my love of crypto, I thought about using a parameter from the elliptic curve secp256k1 since that was the curve of which I based one of my first real-ish projects on that got me interested in security. It has some definite meaning to me, academically and personally.
Then I went against it. I’d learned a lot more about elliptic curves since then, and realize some of its faults. I then thought about curve25519, since it has some relevance in my work, and it’s (personally) a stronger curve than the Bitcoin curve above and thus, much cooler, obviously.
Still fixated on crypto, my mind branched out to other potential primes and my possible connection with them. As I fell asleep, I remembered the best numbers of all– Lucas primes! (Yes, it’s a French Lucas, so not the same pronounciation, but let me have my fun). The best thing about these numbers is not just that the name is fantastic, but that it’s actually relevant for hunting primes in the Great Internet Mersenne Prime Search. They use the Lucas-Lehmer test to verify results, which is a beautifully simple deterministic polynomial (wow!!) time algorithm to test Mersenne primes. Definitely one of my favorite algorithms since it’s just so cool, almost as cool as the Bellcore attack.
Additionally, Lucas numbers (specifically, Lucas pseudoprimes) are used in the essentially most used algorithm to test for primality: the Baillie-PSW test which is basically just a combination of the “normal” Lucas primality test and the Miller-Rabin test, which shores up each other’s weak points essentially.
Ultimately though, there is no “single” Lucas number/prime that specifically stands out. One Honorable Mention I’d like to bestow though is the number 82,589,933, or more specifically, 2**82,589,933 - 1, which is currently the largest prime number. It’s definitely quite intriguing that most (9/10) of the largest primes are Mersenne primes, but that makes sense and is likely due to the simplicity of detecting these primes rather than being representative of true nature.
Security Numbers
I began to think outside of cryptography for a bit, half out of curiosity, and half out of wondering what else I might get on my Buzzfeed quiz. After all, I like to think I’m more than just an amateur cryptographer.
I thought about my first forays into security, and remembered the one article that inspired many people and is single-handedly responsible for dozens of paper titles doing anything remotely security related: Smashing the Stack for Fun and Profit.
In this pretty amazing write-up that still stands today, the author uses “A” as an example for overwriting the stack– and thus 0x41414141 was born, or 1,094,795,585 normally, and it has become the “foo function” of the system security world.
Still, this didn’t feel all too unique to me. Furthermore, it’s not too common in reality. In reality, people will use Metasploit’s pattern generator. Because oftentimes, in hunting for buffer overflows, 1) you’ll likely overwrite a lot of memory and 2) you need to find out exactly which byte was overwritten by memory to precisely figure out certain offsets for your input data. After all, it’s easier to see what exact bytes were corrupts with “AAABACAD” than “AAAAAAAA”. Thus, ‘AAAAAAAA’, however prototypical, isn’t used too much.
Then I thought back to one of my first “wild” bugs with a company that won’t be named.
Flask is quite a common and useful app to easily get webapps up and going and has probably some of the cleanest and clearest documentation I’ve seen. Specifically, though, under the “Configuring from Files” section and following, you have some defaults for a secret key, such as:
>set SECRET_KEY='5f352379324c22463451387a0aec5d2f'
which, in the case of this company, was a secret key that was being used. This was likely an error simply due to copy and pasting the instructions under Flask, which is a more common mistake than you would think, even though Flask is quite explicit on best practices for the secret key (and seemingly is still reasonably common). (Also note that, for Flask specifically, the severity of secret key leakage depends on how a server uses cookies. Generally though, it’s usually not good)
This number (or rather, hex string, but still counts as a number to me!) was especially resonant to me because, in initial testing, it had popped up a lot and was simply present as an environment variable. It was only until I was speaking to a coworker about “that weird ‘5f’ hex number” that I realized what it meant.
Of course, saying “my favorite number is 126552570819579436533483798445723245871” is quite the mouthful, and felt kind of half cheating, but it’s something I definitely favored because I always find it a good story and will forever be a “number” I recognize, no matter how weird it might be.
My Favorite Number (and 1,597,463,007)
This whole challenge actually made me think more about the significance of numbers and what I find cool, which I’m positive is what the challenge was meant to do. Now that I’m done rambling, let me tell you about 1,597,463,007, also known as 0x5F3759DF.
To me, this was largely the factoid that got me into hardware (among many others… but this was the most math-y and largest number!).
Here is some code ripped off Wikipedia.
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( t hreehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}
In case you didn’t read the Wiki, this is a quite (in)famous algorithm found in the Quake source code to yield approximately 1⁄√x for whatever x very fast, hence the name “fast inverse square root”. This calculation is incredibly relevant for graphics, since it’s an operation used in distance calculations and, particularly, normalizing vectors. Such an operation would usually be pretty expensive in hardware, and for real-time graphics rendering used in video games, is even more critical for performance (of
course, rsqrtss exists these days, but not in the 90’s!).
Obviously the most confounding thing is the magic number outlined colorfully, and anybody reading the code most definitely has the same reaction. But– it works. And nobody remembers how they came up with it.
You can read on the Wikipedia article on how good of an approximation it is (but it’s not the only one, nor the best!), and it’s pretty dang close.
Source: http://h14s.p5r.org/2012/09/0x5f3759df.html
And it is this sort of horrible hack that really speaks to me. Not only does it take advantage of some really cool hardware tricks for floating point representation (and I love hardware for all the tricks people can do!), I feel it gets at the heart of engineering. Just try random (guided) crap, and iterate on results. And occasionally, you’ll get some beautiful intersection of math and hardware like this.
There are already some pretty good explanations (the best being this pretty technical one) but what I love about this number is how the solution came first, and explanations came second. This is in stark contrast with every other number previously mentioned, where the numbers were used/discovered secondarily to help a problem primarily like elliptic curves.
I often think of this number whenever I get lost in the weeds or overwhelmed on a project and remind myself that, ultimately, engineering is about getting things done and iterating. It might not be perfect, and it might be horrible to upgrade/maintain, but if you try to make every decision perfect and future-proof/minimize technical debt, nothing gets done. It serves as a reminder to me that “done and working” is the best project of all.
That’s not to say it’s unimportant to plan things ahead of time– rather that, personally, I can get sidetracked in researching and planning and reading docs to the point I’m hesitant to write any code at all for fear of having to refactor it later on, when really I should think of this number and just try stuff.
======
This mini challenge really got me thinking about numbers, which I’m sure was the entire point. It made me realize how many numbers actually have meaning in my life, even though I seldom use these “big numbers” in my day to day life.
While I definitely thought about this way too much (see above), and I don’t think I’ll ever forget any of these numbers, I find 0x5f3759df to be especially inspirational to me: a reminder of what engineering means.