Basilisk collection

This article is a repost promoting content originally published elsewhere. See more things Dan's reposted.

Basilisk collection

The basilisk collection (also known as the basilisk file or basilisk.txt) is a collection of over 125 million partial hash inversions of the SHA-256 cryptographic hash function. Assuming state-of-the art methods were used to compute the inversions, the entries in the collection collectively represent a proof-of-work far exceeding the computational capacity of the human race.[1][2] The collection was released in parts through BitTorrent beginning in June 2018, although it was not widely reported or discussed until early 2019.[3] On August 4th, 2019 the complete collection of 125,552,089 known hash inversions was compiled and published by CryTor, the cybersecurity lab of the University of Toronto.[4]

The existence of the basilisk collection has had wide reaching consequences in the field of cryptography, and has been blamed for catalyzing the January 2019 Bitcoin crash.[2][5][6]

Electronic Frontier Foundation cryptographer Brian Landlaw has said that “whoever made the basilisk is 30 years ahead of the NSA, and the NSA are 30 years ahead of us, so who is there left to trust?”[35]

This is fucking amazing, on a par with e.g. First on the Moon.

Presented in the style of an alternate-reality Wikipedia article, this piece of what the author calls “unfiction” describes the narratively believable-but-spooky (if theoretically unlikely from a technical standpoint) 2018 disclosure of evidence for a new presumed mathematical weakness in the SHA-2 hash function set. (And if that doesn’t sound like a good premise for a story to you, I don’t know what’s wrong with you! 😂)

Cryptographic weaknesses that make feasible attacks on hashing algorithms are a demonstrably real thing. But even with the benefit of the known vulnerabilities in SHA-2 (meet-in-the-middle attacks that involve up-to-halving the search space by solving from “both ends”, plus deterministic weaknesses that make it easier to find two inputs that produce the same hash so long as you choose the inputs carefully) the “article” correctly states that to produce a long list of hash inversions of the kinds described, that follow a predictable sequence, might be expected to require more computer processing power than humans have ever applied to any problem, ever.

As a piece of alternate history science fiction, this piece not only provides a technically-accurate explanation of its premises… it also does a good job of speculating what the impact on the world would have been of such an event. But my single favourite part of the piece is that it includes what superficially look like genuine examples of what a hypothetical basilisk.txt would contain. To do this, the author wrote a brute force hash finder and ran it for over a year. That’s some serious dedication. For those that were fooled by this seemingly-convincing evidence of the realism of the piece, here’s the actual results of the hash alongside the claimed ones (let this be a reminder to you that it’s not sufficient to skim-read your hash comparisons, people!):

basilisk:0000000000:ds26ovbJzDwkVWia1tINLJZ2WXEHBvItMZRxHmYhlQd0spuvPXb6cYFJorDKkqlA

claimed: 0000000000000000000000161b9f84a187cc21b172bf68b3cb3b78684d8e9f17
 actual: 00000000000161b9f84a187cc21b1752bf678bdd4d643c17b3b786684d8e9f17

basilisk:0000000001:dMHUhnoEkmLv8TSE1lnJ7nVIYM8FLYBRtzTiJCM8ziijpTj95MPptu6psZZyLBVA

claimed: 0000000000000000000000cee5fe5df2d3034fff435bb40e8651a18d69e81460
 actual: 0000000000cee5fe5df2d3034fff435bb4232f21c2efce0e8651a18d69e81460

basilisk:0000000002:aSCZwTSmH9ZtqB5gQ27mcGuKIXrghtYIoMp6aKCLvxhlf1FC5D1sZSi2SjwU9EqK

claimed: 000000000000000000000012aabd8d935757db173d5b3e7ae0f25ea4eb775402
 actual: 000000000012aabd8d935757db173d5b3ec6d38330926f7ae0f25ea4eb775402

basilisk:0000000003:oeocInD9uFwIO2x5u9myS4MKQbFW8Vl1IyqmUXHV3jVen6XCoVtuMbuB1bSDyOvE

claimed: 000000000000000000000039d50bb560770d051a3f5a2fe340c99f81e18129d1
 actual: 000000000039d50bb560770d051a3f5a2ffa2281ac3287e340c99f81e18129d1

basilisk:0000000004:m0EyKprlUmDaW9xvPgYMz2pziEUJEzuy6vsSTlMZO7lVVOYlJgJTcEvh5QVJUVnh

claimed: 00000000000000000000002ca8fc4b6396dd5b5bcf5fa80ea49967da55a8668b
 actual: 00000000002ca8fc4b6396dd5b5bcf5fa82a867d17ebc40ea49967da55a8668b

Anyway: the whole thing is amazing and you should go read it.

TIL that the “holes” in Swiss cheese were, until recently, seen as a sign of imperfection and something cheesemakers tried to avoid

This link was originally posted to /r/todayilearned. See more things from Dan's Reddit account.

Three types of bacteria are used in the production of Emmental: Streptococcus thermophilus, Lactobacillus helveticus, and Propionibacterium freudenreichii. Historically, the holes were a sign of imperfection, and until modern times, cheese makers would try to avoid them. Emmental cheese is used in a variety of dishes, particularly in gratins, and fondue, where it is mixed with Gruyère.

Wikipedia

Monogamy and Mathematics

“We have to split up… in case somebody better comes along!”

Either from our own real life or from popular culture and the media, we’ve all come across a statement like that. It’s rarely quite so brazen: instead, it’s sometimes concealed behind another reason, whether tactful or simply false. But it still reeks of a lack of commitment and an unwillingness to “give it a try.”

With thanks for Flickr user "i.am.rebecca".

However, it turns out that there’s actually a solid mathematical basis for it. Let’s assume for a moment that you:

  1. Engage exclusively in monogamous relationships. To each their own, I suppose.
  2. Are seeking for a relationship that will last indefinitely (e.g. traditional monogamous marriage, “’til death do us part,” and all that jazz).
  3. Can’t or won’t date your exes.
  4. Can rate all of your relationships relative to one another (i.e. rank them all, from best to worst)?
  5. Can reasonably estimate the number of partners that you will have the opportunity to assess over the course of your life. You can work this out by speculating on how long you’ll live (and be dating!) for, and multiplying, though of course there are several factors that will introduce error. When making this assumption, you should assume that you break up from any monogamous relationship that you’re currently in, and that no future monogamous relationship is allowed to last long enough that it may prevent you from exploring the next one, until you find “the one” – the lucky winner you’re hoping to spend the rest of your life with.

Assuming that all of the above is true, what strategy should you employ in order to maximise your chance of getting yourself the best possible lover (for you)?

The derivation of the optimal policy for the secretary problem.

It turns out that clever (and probably single) mathematicians have already solved this puzzle for you. They call it the Secretary Problem, because they’d rather think about it as being a human resources exercise, rather than a reminder of their own tragic loneliness.

A Mathematical Strategy for Monogamy

Here’s what you do:

  1. Take the number of people you expect to be able to date over the course of your lifetime, assuming that you  never “settle down” and stop dating others. For example’s sake, let’s pick 20.
  2. Divide that number by e – about 2.71828. You won’t get a round number, so round down. In our example, we get 7.
  3. Date that many people – maybe you already have. Leave them all. This is important: these first few (7, in our example) aren’t “keepers”: the only reason you date them is to give you a basis for comparison against which you rate all of your future lovers.
  4. Keep dating: only stop when you find somebody who is better than everybody you’ve dated so far.

And there you have it! Mathematically-speaking, this strategy gives you a 37% chance of ending up with the person who – of all the people you’d have had the chance to date – is the best. 37% doesn’t sound like much, but from a mathematical standpoint, it’s the best you can do with monogamy unless you permit yourself to date exes, or to cheat.

Or to conveniently see your current partner as being better than you would have objectively rated them otherwise. That’s what love will do for you, but that’s harder to model mathematically.

Of course, if everybody used this technique (or even if enough people used it that you might be reasonably expected to date somebody who did, at some point in your life), then the problem drifts into the domain of game theory. And by that point, you’d do better to set up a dating agency, collect everybody’s details, and use a Stable Marriage problem solution to pair everybody up.

This has been a lesson in why mathematicians shouldn’t date.

Looking for Wikipedia?

As you may have noticed, the English-speaking Wikipedia is “blacking out” in protest at SOPA/PIPA. This is a very important thing: SOPA/PIPA are potentially extremely dangerous bits of legislation (if you’re looking for a short explanation of why, here’s a great video).

I’m going to assume that you’re aware of the issues and have already taken action appropriate to your place – if you’re in the US, you’ve written to your representatives; if you’re in the rest of the English-speaking world, you’ve donated to the EFF (this issue affects all of us), etc. But if you’re in need of Wikipedia, here’s the simplest way to view it, today:

Accessing Wikipedia during the blackout

  1. Go to the English-language Wikipedia as normal. You’ll see the “SOPA blackout” page after a second or so.
  2. Copy-paste the following code into the address bar of the browser:

javascript:(function()%7Bdocument.getElementById('content').style.display='block';document.getElementById('mw-sopaOverlay').style.display='none'%7D)()

That’s all. You don’t even have to turn off Javascript in your browser, as others are suggesting: just surf away.

If you get sick of copy-pasting on every single Wikipedia page you visit… you can drag this link to your bookmarks toolbar (or right click it and select “add to bookmarks”) and then just click it from your bookmarks whenever you want to remove the blackout.

And if you just came here for the shortcut without making yourself aware of the issues, shame on you.

The Back Button

How did I get here?

While lying in bed, unwell and off work, last month, I found myself surfing (on my new phone) to the Wikipedia page on torsion springs. And that’s when I found myself wondering – how did I get here?

Thankfully, there’s always the back button: famously the second most-used bit of your web browser’s user interface. So… how did I come to be reading about torsion springs?

An anniversary clock, using a torsion pendulum, so-named because it only needs winding once a year.
  • I got there from reading about torsion pendulum clocks. My grandmother used to have one of these (an “anniversary clock”, like the one above, and I remember that I used to always enjoy watching the balls spin when I was a child).
  • I’d followed a link from the article about the Atmos clock, a type of torsion pendulum clock that uses minute variations in atmospheric temperature and pressure to power the winder and which, in ideal circumstances, will never need winding.
  • Before that, I’d been reading about the Beverly Clock, a classic timepiece that’s another example of an atmospheric-pressure-clock. It’s been running for almost 150 years despite having never been wound.
  • This was an example of another long-running experiment given on the page about the Oxford Electric Bell, which is perhaps the world’s longest-running scientific experiment. Built in 1840, it uses a pair of electrostatic batteries to continuously ring a bell.
The Oxford Electric Bell experiment. It's batteries have lasted for over 160 years, but I have to charge my mobile most nights: what gives, science?
  • I got to the Oxford Electric Bell from another long-running experiment – the one acknowledged as the world’s longest-running by the Guinness Book of Records – the University of Queensland Pitch Drop Experiment. Running since 1927, this experiment demonstrates that pitch is not solid but a high-viscosity fluid. A sample of room-temperature pitch in a funnel forms a droplet about once a decade.
  • Earlier, I was learning about the difference between the different substances we call tar. Traditionally, tar is derived by baking pine wood and roots into charcoal, and collecting the runoff, but we also use the word “tar” to describe coal tar (a byproduct of coke production) and bitumen (viscous, sticky crude oil).
  • I took the initiative to learn about those differences after reading about the name “Jack Tar“, an Empire-era slang term for a sailor in the Merchant Navy or Royal Navy…
  • …which in turn was linked from the similar article about “Tommy Atkins“, a term for a British infantryman (particularly in the First World War), which has an interesting history…
  • …to which I got from the “Doughboy” article. The Doughboys were members of the American Expeditionary Force during the First World War.
R.U.R. - "Private Robot" - loads an artillery piece.
  • Finally, I got to that first Wikipedia article while, when reading an article on The Paleofuture Blog, I wondered about the etymology of the term “doughboy”, and began this whole link-clicking adventure.

It’s fascinating to work out “how you got here” after an extended exploration of a site like Wikipedia (or TV Tropes, or Changing Minds, or Uncyclopedia – and there goes your weekend…). Thank you, Back Button.

I just wish I had a Back Button in my head so that I could “wind back” my wandering thought processes. How did I end up thinking about the salt content of airline food, exactly?