The World’s Fastest DES Cracker
crack.sh
crack.sh
Now that was easy to crack.
He password protected it so we could only play for controlled periods of time, and chose "tricycle" as the password, but my sister and I guessed "bicycle" in the hours of typing every word we knew into the prompt. "bicycle" worked!
Xilinx was founded in 1984, so the advent of FPGAs is at least that old.
The linked page estimates the price to crack a key via a CPU farm is $125K, and cracking one via a GPU farm is $20K. But they don't say what it costs via their system. The FAQ answers the question, "Why are you charging so much for this", but again, without referencing that price. I don't feel like submitting a credit card and generating a token to find out.
Toward the end of the page. Looks like $20 except for rush orders (for most types)
All the same, it would be better to also state their range of prices on the page where they estimate CPU and GPU-based cracking costs.
> In 1998 the Electronic Frontier Foundation built the EFF DES Cracker. It cost around $250,000
> The system that you're renting time on is over $100k in specialized FPGA hardware
> In 1998 the Electronic Frontier Foundation built the EFF DES Cracker. It cost around $250,000
> The system that you're renting time on is over $100k in specialized FPGA hardware
So it's 10x faster with 23x fewer cores.
Compared to this, AES was much more difficult and it did not fit the FPGA I had and I eventually gave up.
I am wrong.
It's frustrating that I has to refute the argument many times: "If 80-bit is insecure today, 128-bit will be insecure soon any cryptosystem can only guarantee a few decades of security because Moore's Law..." No, it's not how it works (although quantum computers will make 128-bit insecure, but the solution is already available today: 256-bit). The human brain is not wired to understand exponential growth.
I believe you are doing the people you are talking about an injustice here, because assuming Moore's Law held, we would be doubling computing power every two years (well, transistors really).
Doubling... what comes to mind... Ah yes! Bits! Because with every bit you are doubling the number of keys, meaning that you could crack an 81 bit key today in the same it would have taken you to crack an 80 bit key two years ago. So that gives you 100 years, or about 10 decades, to go from 80 bit to 128 bits.
Or, in other words, Moore's law is also about exponential growth.
So if those people you quoted did indeed say "a few decades" they were right on.
So the correct realisation here is that Moore's law (an observation by an engineer) doesn't trump laws of physics.
The transistors Moore was talking about have to be made from something. When they're made of a lump of material you can actually see under a microscope this feels both very real and as if it could be shrunk indefinitely. Just keep cutting that material in half!
But it can't. Matter is made of atoms. If you double the number of transistors you must halve the number of atoms in each transistor. Today's transistors have a few hundred atoms in them. Guess what happens when there's one atom in each transistor and you try to halve that? There's no such thing as "half" an atom, what you've got there isn't an atom any more, and so what you're making isn't a transistor.
The argument that we will never need larger symmetric encryption isn't based on ignorance of Moore's law, it's based on knowledge of the laws of physics. You can't make a 256-bit AES cracker by "just" converting the entire planet into Computronium, that's not enough compute power.
So it would take 26 hours * 2^56 which is a very long time.
UPDATE: A quick calculation on Google yields:
(2^56) * 26 hours = 2.13727751 × 10^14 years
As for ChaCha et al, it’s still not that easy to start using it.
Not that many proven standardized implementations exist, hardware acceleration and performance issue are still there, the amount of research on these ciphers is still dwarfed by the amount of research done against AES and since these aren’t industry standards it’s harder to implement them in systems that require wide interoperability and are pretty much a no go in any industry that has its own standards.
Using extended ChaCha is cool for your side project, but try to implement it to say protect card payments in a system that needs to go through a PCI certification for example.
It's not like other quantum issues, where you're worried about transcripts collected today being broken 15 years from now.
AES-GCM can be tricky to use if you implement it yourself, same goes for all other ciphers it’s perfectly fine when you use a proven implementation of it that ensures that it doesn’t go past its best before date for a given secret key.
I don’t understand why they made such a big deal of cache timing attacks, yes AES and any other cipher/cryptographic system that have time variable operation may be susceptible to timing attacks, and whilst ChaCha doesn’t have time variable operations (tho it doesn’t guarantee that a given cryptographic system implementation won’t introduce them) it’s still quite susceptible to fault injection attacks which are arguably much easier to execute on the CPUs that most phones and small devices run than cache timing attacks.
Overall when your threat model for a personal device includes a compromised application a lot of security assumptions should be thrown out of the window, it’s far more likely to compromise the OS itself than try to compromise the hardware on a phone specifically you’ll run out of battery before you’ll be able to do a successful cache timing attack anyhow.
If the blog was AES-GCM is easy to cock up so remember that nonce is a nonce for a reason and you should be using improvements over AES-GCM like AES-GCM-SIV it would’ve been fine.
How it is it reads like not particularly well constructed I R VERY SMART post.
Especially the quantum issues that primarily affect real time attacks, not offline ones which would allow you to decrypt historic data with ease.
If you have a drive encrypted with AES even “only” 128bit it’s probably going to be safe for a long while even in a post quantum world.
I just wanted to patent the basic idea of using counter-mode to generate a stream cipher from a block cipher. They said that it seemed like such a small idea, couldn't we allow it to generate simultaneous multiple streams, etc. So it was patented, but the patent is a bit of a mess with some half-baked designs for multiple streams. This was absolutely the worst way to design a crypto system: design one yourself while in the patent lawyer's office.
It still covered the basic idea of using a block cipher and a counter to generate a stream cipher, but I think the good stuff was buried in just a few of the claims. That's all ancient history now since the patent would have expired decades ago.
Counter modes were petty well known in the 80's already I'm not sure what the patent could've been applied for but then it's IBM and their lawyers can probably find a way to patent waking up in the morning.
The method takes advantage of network idle time so it doesn’t improve maximum bandwidth but instead reduces the average latency of a network not running at full bandwidth.
"This post is about why I dislike AES-GCM’s design, not “why AES-GCM is insecure and should be avoided”. AES-GCM is still miles above what most developers reach for when they want to encrypt (e.g. ECB mode or CBC mode)."
It's more of a collection of pet peeves about AES (in general) and AES-GCM (in particular).
I like to read opinion pieces that are pithy and well presented. I may or may not agree but I will think about the issue. In this case I know very little about the intricacies involved and its good to know that some people do. I've just recently converted about 45 Phase I IPSEC connections to AES128-GCM, AES-XCBC, DH Group 31 and similar Phase II. Most of them were 3DES MD5 G2, without PFS at Phase2 so I think it's an improvement! A big surprise to me was a major drop in CPU usage at the "hub" end. The hardware doesn't have AES-NI yet but it will soon be replaced and your notes have accelerated that change up my stack of stuff to do.
Sadly some of our peers seem to have forgotten to actually read the thesis first before shootin' wildly. I have quite a low Slashdot number and used to hang out there back in the day - nothing is new in the world!
Again, thank you for sharing.
But for asymmetric (public key) encryption the larger key lengths barely help, so you'd need infeasibly enormous keys. e.g. terabyte RSA keys have been "proposed" facetiously for this purpose.
Thus, Post Quantum Encryption research is mostly interested in finding solutions for two asymmetric problems: Key Agreement (a replacement for today's Elliptic Curve Diffie Hellman) and Signatures (a replacement for things like ECDSA) that would survive an attack by a larger quantum computer able to execute Shor's algorithm.
The paper "A Fast New DES Implementation in Software" calculated 64-parallel DES Round across a 64-bit register in 1,040 DEC Alpha instructions. There are 16 rounds per DES, and then another 2,500 clock ticks to convert the bitwise representation back into normal form.
The key to understanding things:
> The full circuit of DES contains about 16000 gates (including the key scheduling, which costs nothing), and thus we can compute DES 64 times in about 16000 instructions on 64-bit processors.
Each logic-gate can be seen as an AND/OR/XOR instruction on a 1-bit computer. Use 64-bit wide AND/OR/XOR to do 64x calculations in parallel. The modern equivalent would be 256x in parallel (AVX2 for Threadripper), AVX512 for Skylake-X, and 1024x in parallel for NVidia Ampere.
I dunno what kind of post-processing would need to be done, so I'll estimate an even 20,000 clock ticks per 64x DES result on the old DEC Alpha.
A modern GPU can probably execute 1024-bit per clock tick (AMD RDNA / NVidia Ampere 32-way x 32-bit), while a modern AVX512 CPU can execute 512-bit at a time. And AVX2 is 256-bit at a time (but probably faster: AVX2 / AVX512 execute XOR / ADDs at a rate of MORE than one clock tick per clock cycle).
The paper was very innovative: the SBox was a 100-instruction long sequence of AND / OR / XOR instructions. Avoiding the cache probably is a good thing, but I do wonder if there's a way to benefit from memory somehow.
* ~80 AVX2 clock ticks per result (20k clock ticks / 256-bits)
* ~40 AVX512 clock ticks per result (20k clocks / 512 bits)
* ~20 GPU clock ticks per result (20k clocks / 1024 bits)
So a 64-core AMD at 4GHz probably could do ~3.2-billion DES attempts per second.
A 216 SM NVidia A100 at 1.4 GHz probably can do ~15-billion DES attempts per second.
---------------
Hmmmmmm.... the results this page claims is ~16-billion DES attempts per second. Which does seem to be approximately what I'd expect a concerted effort on an NVidia A100 would get. I'm doing very "napkin-level" math here with tons of assumptions.
The SBox-lookup (100-AND/OR/XOR gates) might be better run on AVX / AVX512 however, because AMD Threadripper can do 4x simple AND/OR/XOR instructions per clock tick, and IIRC Intel AVX512 can do 3x simple bitwise instructions per clock tick. With the proper "cut dependencies", an SBox probably can be really executed in under 40 clock ticks instead of 100. CPUs could very well cut out hundreds of cycles from the above estimate.
The S-Box is very curious for DES: it is a non-reversible 6-bit lookup with a 4-bit result.