Unlike protocols that require a neutral third party to complete (arbitrated), or protocols that require that neutral third party to resolve disputes (adjudicated), 🔸self-enforcing protocols🔸 just work.
Cut-and-choose works because neither side can cheat. And while the math can get really complicated, the idea generalizes to multiple people.
Well, someone just solved gerrymandering in this way.
Prior solutions required either a bipartisan commission to create fair voting districts (arbitrated), or require a judge to approve district boundaries (adjudicated), their solution is self-enforcing.
And it’s trivial to explain:
• One party defines a map of equal-population contiguous districts.
• Then, the second party combines pairs of contiguous districts to create the final map.
It’s not obvious that this solution works. You could imagine that all the districts are defined so that one party has a slight majority. In that case, no combination of pairs will make that map fair.
But real-world #gerrymandering is never that clean. There’s “#cracking,” where a party’s voters are split amongst several districts to dilute its power; and “#packing,” where a party’s voters are concentrated in a single district so its influence can be minimized elsewhere.
It turns out that this “define-combine procedure” works; the combining party can undo any damage that the defining party does—that the results are fair.
The paper has all the details, and they’re fascinating.
Of course, a theoretical solution is not a political solution. But it’s really neat to have a theoretical solution.
Most has heard of #cracking: Removing or bypassing software #protection. But how does one crack a game? @h0ffman shows the process in this pair of VODs of twitch streams. The catch? He’s cracking 30 year old games using period accurate gear and tools:
• #Amiga500
• Floppy disks only
• Action Replay MKIII
@epixoip - I seem to remember you saying rainbow tables are obsolete. If so, presumably because with a decent gpu you can blitz through all the 8-9 char NTLM passwords faster than reading anything off disk these days?
In any given password database, 92-98% of the passwords are going to be created by highly predictable humans (as opposed to being randomly generated.) Because of this, modern password cracking is heavily optimized for exploiting the human element of password creation, concentrating on probabilistc methods that achieve the largest plaintext yield in the least amount of time. As such, modern password cracking tools and techniques have evolved to become highly dynamic, requiring agility, flexibility, and scalability.
This is evident when looking at how #Hashcat has evolved over the last decade. Hashcat used to be heavily optimized for raw speed, but today it is optimized for maximum flexibilty (plus, lite, and cpu merged into a single code base, dropped the 15-character limit, introduced pure kernels, brain, and slow candidate mode, etc.) This need for dynamicity is also why we largely still use GPUs today, rather than having moved on to devices with potentially higher throughput, such as FPGAs or even ASICs.
With this in mind, it's rather easy to see that rainbow tables are the antithesis of modern password cracking. Rainbow tables are static, rigid, and not at all scalable. They directly compete with unordered incremental brute force, which in the context of modern password cracking, is largely viewed a last resort and generally only useful for finding randonly-generated passwords (although, can also be useful in identifying new patterns that rules and hybrid attacks failed to crack.) They also do not scale. If you have a handful of hashes, rainbow tables will likely be faster than brute forcing on GPU. But if you are working with even a modestly large hash set, rainbow tables will be slower than just performing brute force on GPU, even if you are using GPU rainbow tables.
Overall, rainbow tables are an optimization for an edge case: cracking a small amount of hashes of an algorithm for which we have tables, within the length and character sets for which we have tables, that fall within that 2-8% of hashes that we cannot crack with probabilistic methods. And even then, most people who are #security conscious enough to use use random passwords aren't going to make them only 8 or 9 characters long, so the percentage of those passwords that will actually be found in your tables will be much lower.
The questions you have to ask yourself: is that worth the disk space and the bandwidth to download and store rainbow tables, and do you really care about that 2-8%, keeping in mind that only a small percentage of that is going to fall within the tables you have? If the answer is "yes", then continue to use rainbow tables. However, the for the vast majority of us, the answer for the past 11 years has been a resounding "no." And that's why rainbow tables are, by and large, a relic of a bygone era.
With that said, rainbow tables do still have some utility outside of #passwords. For instance, cracking DES or A5/1 #encryption. There's also the cousin of rainbow tables, lossy hash tables (LHTs), which have some utility as well for things like old Microsoft Office and Adobe Acrobat encryption keys.
Cracking the Cryptic: The Times Crossword Friday - Episode 19 (www.youtube.com)
Mark takes on Friday's Times Crossword, and talks you through all its cryptic clues. Then he has a quicker dash at Thursday's too!