Improvements in Brute Force Attacks

New paper: “GPU Assisted Brute Force Cryptanalysis of GPRS, GSM, RFID, and TETRA: Brute Force Cryptanalysis of KASUMI, SPECK, and TEA3.”

Abstract: Key lengths in symmetric cryptography are determined with respect to the brute force attacks with current technology. While nowadays at least 128-bit keys are recommended, there are many standards and real-world applications that use shorter keys. In order to estimate the actual threat imposed by using those short keys, precise estimates for attacks are crucial.

In this work we provide optimized implementations of several widely used algorithms on GPUs, leading to interesting insights on the cost of brute force attacks on several real-word applications.

In particular, we optimize KASUMI (used in GPRS/GSM),SPECK (used in RFID communication), andTEA3 (used in TETRA). Our best optimizations allow us to try 2^35.72, 2^36.72, and 2^34.71 keys per second on a single RTX 4090 GPU. Those results improve upon previous results significantly, e.g. our KASUMI implementation is more than 15 times faster than the optimizations given in the CRYPTO’24 paper [ACC+24] improving the main results of that paper by the same factor.

With these optimizations, in order to break GPRS/GSM, RFID, and TETRA communications in a year, one needs around 11.22 billion, and 1.36 million RTX 4090GPUs, respectively.

For KASUMI, the time-memory trade-off attacks of [ACC+24] can be performed with142 RTX 4090 GPUs instead of 2400 RTX 3090 GPUs or, when the same amount of GPUs are used, their table creation time can be reduced to 20.6 days from 348 days,crucial improvements for real world cryptanalytic tasks.

Attacks always get better; they never get worse. None of these is practical yet, and they might never be. But there are certainly more optimizations to come.

EDITED TO ADD (4/14): One of the paper’s authors responds.

Tags: academic papers, cryptanalysis, keys

Posted on March 17, 2025 at 11:09 AM • 9 Comments

Comments

Brad Knowles • March 17, 2025 12:07 PM

Very interesting results. I wonder if the authors could calculate a theoretical speedup using an HPC cluster of 1024 nodes, each node having eight NVIDIA H200 GPUs. That would be about one large HPC datacenter worth of equipment. A 256 node cluster would be less expensive and easier to build, but for someone wanting to crack keys like this, I don’t think they would stop short of a 1024 node cluster.

Knowing the typical different performance characteristics of a single NVIDIA 4090 GPUs compared to NVIDIA H200s, they should be able to figure out how fast a modern HPC cluster could crack those same key types/lengths.

Then it would be interesting to compare against the next-generation NVIDIA Blackwell GPUs.

Then we might be able to predict performance with future GPUs that we know NVIDIA is already working on.

Joseph Kanowitz • March 17, 2025 1:41 PM

ב”ה,

Y’know, nowhere else to put this, so in the era of agricultural drones and Roundup / Roundup-Ready litigation, it’s miraculous we haven’t heard news of glyphosate-laden swarms ‘hacked by foreign actors’ knocking down neighbors’ unmodified crops.

Loosened EPA regulations offer GMO investors other opportunities with irrigation water.

I’d prefer to be able to eat, myself. Anyone mind helping with rent?

Clive Robinson • March 17, 2025 3:39 PM

@ Bruce, ALL,

With regards “cracking” security systems, usually the best approach is not to go after the crypto algorithm… But to go after the weaknesses in the “Key Managment”(KeyMan) systems.

For instance knowing that a “Crypto Secure – Random Bit Generator”(CS-RBG) has defects in it’s implementation that leaks information by timing side channels, can make most of the work detailed in this paper a highwater mark on “effort” or resources.

But there is one “weak link in the system chain” that almost always pays dividends, and that is the incredibly weak human mind.

It’s why I’m surprised the use of current AI LLM and ML systems have not been used to “predict password/phrases” it is kind of what they are almost perfectly designed to do.

ResearcherZero • March 18, 2025 1:42 AM

@Clive

Some ransomware operators for a long time used pretty poor code, meaning that their own decryptors often do not properly decrypt files and instead corrupt them. Plus many of the claims they have historically made falsely stated the implementation and key lengths, or they were simply not as adept as other groups and oversold their abilities and tools.

Though some of the criminal outfits have gotten better, this method targeted a weakness of using the current time as a seed, and then brute forced the solution with GPU power.

‘https://tinyhack.com/2025/03/13/decrypting-encrypted-files-from-akira-ransomware-linux-esxi-variant-2024-using-a-bunch-of-gpus/

Clive Robinson • March 18, 2025 5:26 AM

@ ResearcherZero, ALL,

With regards,

“Some ransomware operators for a long time used pretty poor code, meaning that their own decryptors often do not properly decrypt files and instead corrupt them.”

Yup, and that’s why the advice is,

1, Take backups to segregated storage.
2, Take backups frequently.
3, Check the backups on segregated test systems.
4, duplicate the backups to geo-segregated storage systems.

And a couple of other things to do with protection of the backups from theft etc when in transit and storage.

Where the “protection” involves encryption as well, which brings in the issue of “Key Managment”…

But… All this is for the “simple case” where the backups are in effect “trivially small”.

Some people have datasets so large that even a truck full of high capacity SSDs is not going to be big enough… Which is why some ill advisedly “send it to the cloud” because in the short term ONLY it’s less expensive.

Back in the 1990’s it was a problem I was kind of looking into as part of geo-distributed databases.

But I never got a solid handle on the KeyManagment issues they are something that quickly get to complex to be,

1, Secure
2, Reliable
3, Timely

Thus “available” in a usable way.

These three issues also hit Ransomware operators that use encryption.

Have a think on how as a ransomware operator, you would generate “the key” in a way that it is known only to you, but without pointing to you via network traffic etc. It’s actually quite a hard problem and very easy to get wrong, thus give “a crack into the system”.

Z.Lozinski • March 19, 2025 7:15 PM

@Bruce, is it time to get the band back on the road?

Do we need an update to the 1996 “Minimal Key Lengths for Symmetric Ciphers
to Provide Adequate Commercial Security” (of which you were a co-author) to address the progress in GPUs, driven by USD billions of investment?

Resistance to quantum attack was the major focus of the NIST work on PQC, which addresses public key cryptography.

I’m now wondering if we also need to consider the progress in GPU. I need to do the maths but it feels like we are giong faster than Moore’s Law (just for GPUs) ar present.

Zoulok • March 20, 2025 3:13 PM

Do RTX4090 graphics cards allow to find a 96-bit key from the original ZIP encryption in deflate mode or it’s always out of reach?
As of today, this represents $8.5 million:
https://archive.org/details/bitcoins_202305

ResearcherZero • March 26, 2025 5:04 AM

@Clive Robinson, @Joseph Kanowitz

I also like eating.

It is also why they advise to use the SCIF at the embassy, one at a secure facility or the purpose built Situation Room to discuss the name of an active CIA agent, while waiting to meet with Vladimir Putin. Behaving in a cavalier manner with the identities of your own agents and with sensitive classified information, is highly unlikely to embolden trust from either your own personnel, or from allies, who may then decide to withhold intelligence.

There is likely a lot of brute forcing and decrypting taking place at this very moment.

The inability to handle or evaluate intelligence seriously is an indicator of carelessness which can easily be exploited by an adversary to blind or influence decision making. Any communications captured by adversarial networks would be sent immediately for analysis.

Telling fibs and hoping to disguise or hide mistakes will not make those mistakes go away. History is full of lessons regarding those who failed to heed or ignored the warning signs.

It is now apparent why China’s top offensive teams were tasked to aggressively target communications. Clearly they identified the incompetent, unorganized and chaotic team which would likely be in office. The current U.S. administration has consistently demonstrated a tendency to ignore and dismiss intelligence. Unlike adversarial nations states, it has failed to identify, prepare and then deploy resources to counter a number of key threats.

🪳 ‘https://www.odni.gov/index.php/newsroom/reports-publications/reports-publications-2025/4058-2025-annual-threat-assessment

China has a formidable analysis capability and likely anticipated multiple opportunities to target. It is now taking full advantage of those opportunities, as are many others.

https://fortune.com/asia/2025/03/26/china-swoops-in-to-replace-asian-usaid-projects-axed-by-trump/

That a participant was in Moscow during the group chat, demonstrates a pattern of missteps.
https://www.cbsnews.com/news/trump-envoy-steve-witkoff-signal-text-group-chat-russia-putin/

“…Soviet espionage in the United States changed history. The espionage-enabled rapid acquisition of the atomic bomb emboldened Stalin’s policies in the early Cold War and contributed to his decision to authorize North Korea’s invasion of South Korea. 🪳 Soviet espionage also led to the loss of America’s ability to read Soviet military communications and ensured that the Korean invasion was a surprise for which American forces were unprepared.”

‘https://americandiplomacy.web.unc.edu/2010/04/spies-the-rise-and-fall-of-the-kgb-in-america/

I do not fancy eating radroaches (the mutant cousins of cockroaches). 🪳

Cihangir Tezcan • March 30, 2025 6:38 AM

As an author of the paper I beg the differ about the part “None of these is practical yet…”. We showed that every GSM/GPRS communication can be broken in 38 hours with 2400 RTX 4090 GPUs. That is pretty practical for me. Note that the numbers will be lower if you use the newly announced RTX 5090.

Schneier on Security

Improvements in Brute Force Attacks

Comments

Leave a comment Cancel reply