Entries Tagged "cryptography"

Page 31 of 56

New Attack on AES

“Biclique Cryptanalysis of the Full AES,” by Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger.

Abstract. Since Rijndael was chosen as the Advanced Encryption Standard, improving upon 7-round attacks on the 128-bit key variant or upon 8-round attacks on the 192/256-bit key variants has been one of the most difficult challenges in the cryptanalysis of block ciphers for more than a decade. In this paper we present a novel technique of block cipher cryptanalysis with bicliques, which leads to the following results:

  • The first key recovery attack on the full AES-128 with computational complexity 2126.1.
  • The first key recovery attack on the full AES-192 with computational complexity 2189.7.
  • The first key recovery attack on the full AES-256 with computational complexity 2254.4.
  • Attacks with lower complexity on the reduced-round versions of AES not considered before, including an attack on 8-round AES-128 with complexity 2124.9.
  • Preimage attacks on compression functions based on the full AES versions.

In contrast to most shortcut attacks on AES variants, we do not need to assume related-keys. Most of our attacks only need a very small part of the codebook and have small memory requirements, and are practically verified to a large extent. As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

This is what I wrote about AES in 2009. I still agree with my advice:

Cryptography is all about safety margins. If you can break n round of a cipher, you design it with 2n or 3n rounds. What we’re learning is that the safety margin of AES is much less than previously believed. And while there is no reason to scrap AES in favor of another algorithm, NST should increase the number of rounds of all three AES variants. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Or maybe even more; we don’t want to be revising the standard again and again.

And for new applications I suggest that people don’t use AES-256. AES-128 provides more than enough security margin for the forseeable future. But if you’re already using AES-256, there’s no reason to change.

The advice about AES-256 was because of a 2009 attack, not this result.

Again, I repeat the saying I’ve heard came from inside the NSA: “Attacks always get better; they never get worse.”

Posted on August 18, 2011 at 6:12 AM • View Comments

Security Flaws in Encrypted Police Radios

“Why (Special Agent) Johnny (Still) Can’t Encrypt: A Security Analysis of the APCO Project 25 Two-Way Radio System,” by Sandy Clark, Travis Goodspeed, Perry Metzger, Zachary Wasserman, Kevin Xu, and Matt Blaze.

Abstract: APCO Project 25a (“P25”) is a suite of wireless communications protocols used in the US and elsewhere for public safety two-way (voice) radio systems. The protocols include security options in which voice and data traffic can be cryptographically protected from eavesdropping. This paper analyzes the security of P25 systems against both passive and active adversaries. We found a number of protocol, implementation, and user interface weaknesses that routinely leak information to a passive eavesdropper or that permit highly efficient and difficult to detect active attacks. We introduce new selective subframe jamming attacks against P25, in which an active attacker with very modest resources can prevent specific kinds of traffic (such as encrypted messages) from being received, while emitting only a small fraction of the aggregate power of the legitimate transmitter. We also found that even the passive attacks represent a serious practical threat. In a study we conducted over a two year period in several US metropolitan areas, we found that a significant fraction of the “encrypted” P25 tactical radio traffic sent by federal law enforcement surveillance operatives is actually sent in the clear, in spite of their users’ belief that they are encrypted, and often reveals such sensitive data as the such sensitive data as the names of informants in criminal investigations.

I’ve heard Matt talk about this project several times. It’s great work, and a fascinating insight into the usability problems of encryption in the real world.

News article.

Posted on August 11, 2011 at 6:19 AM • View Comments

GPRS Hacked

Just announced:

Nohl’s group found a number of problems with GPRS. First, he says, lax authentication rules could allow an attacker to set up a fake cellular base station and eavesdrop on information transmitted by users passing by. In some countries, they found that GPRS communications weren’t encrypted at all. When they were encrypted, Nohl adds, the ciphers were often weak and could be either broken or decoded with relatively short keys that were easy to guess.

The group generated an optimized set of codes that an attacker could quickly use to find the key protecting a given communication. The attack the researchers designed against GPRS costs about 10 euros for radio equipment, Nohl says.

More articles.

Posted on August 10, 2011 at 4:11 PM • View Comments

Zodiac Cipher Cracked

I admit I don’t pay much attention to pencil-and-paper ciphers, so I knew nothing about the Zodiac cipher. Seems it has finally been broken:

The Zodiac Killer was a serial killer who preyed on couples in Northern California in the years between 1968 and 1970. Of his seven confirmed victims, five died. More victims and attacks are suspected.

The killer sent four messages to newspapers in California’s Bay Area, only one of which has ever been decrypted. This first message ­ split into three parts ­ claimed Zodiac wanted to kill victims so that they would become his slaves in the afterlife.

The 408-symbol cryptogram was cracked by Donald and Bettye Harden of Salinas, California.

Code and solution—with photos—here.

EDITED TO ADD (8/5): Solution seems to be a hoax.

Posted on August 5, 2011 at 12:25 PM • View Comments

New Information on the Inventor of the One-Time Pad

Seems that the one-time pad was not first invented by Vernam:

He could plainly see that the document described a technique called the one-time pad fully 35 years before its supposed invention during World War I by Gilbert Vernam, an AT&T engineer, and Joseph Mauborgne, later chief of the Army Signal Corps.

[…]

The 1882 monograph that Dr. Bellovin stumbled across in the Library of Congress was “Telegraphic Code to Insure Privacy and Secrecy in the Transmission of Telegrams,” by Frank Miller, a successful banker in Sacramento who later became a trustee of Stanford University. In Miller’s preface, the key points jumped off the page:

“A banker in the West should prepare a list of irregular numbers to be called ‘shift numbers,'” he wrote. “The difference between such numbers must not be regular. When a shift-number has been applied, or used, it must be erased from the list and not be used again.”

It seems that Vernam was not aware of Miller’s work, and independently invented the one-time pad.

Another article. And the paper.

Posted on August 3, 2011 at 12:57 PM • View Comments

Breaking the Xilinx Virtex-II FPGA Bitstream Encryption

It’s a power-analysis attack, which makes it much harder to defend against. And since the attack model is an engineer trying to reverse-engineer the chip, it’s a valid attack.

Abstract: Over the last two decades FPGAs have become central components for many advanced digital systems, e.g., video signal processing, network routers, data acquisition and military systems. In order to protect the intellectual property and to prevent fraud, e.g., by cloning an FPGA or manipulating its content, many current FPGAs employ a bitstream encryption feature. We develop a successful attack on the bitstream encryption engine integrated in the widespread Virtex-II Pro FPGAs from Xilinx, using side-channel analysis. After measuring the power consumption of a single power-up of the device and a modest amount of o-line computation, we are able to recover all three different keys used by its triple DES module. Our method allows extracting secret keys from any real-world device where the bitstream encryption feature of Virtex-II Pro is enabled. As a consequence, the target product can be cloned and manipulated at will of the attacker. Also, more advanced attacks such as reverse engineering or the introduction of hardware Trojans become potential threats. As part of the side-channel attack, we were able to deduce certain internals of the hardware encryption engine. To our knowledge, this is the first attack against the bitstream encryption of a commercial FPGA reported in the open literature.

Posted on August 1, 2011 at 12:29 PM • View Comments

Cryptography and Wiretapping

Matt Blaze analyzes the 2010 U.S. Wiretap Report.

In 2000, government policy finally reversed course, acknowledging that encryption needed to become a critical part of security in modern networks, something that deserved to be encouraged, even if it might occasionally cause some trouble for law enforcement wiretappers. And since that time the transparent use of cryptography by everyday people (and criminals) has, in fact, exploded. Crypto software and algorithms, once categorized for arms control purposes as a “munition” alongside rocket launchers and nuclear triggers, can now be openly discussed, improved and incorporated into products and services without the end user even knowing that it’s there. Virtually every cellular telephone call is today encrypted and effectively impervious to unauthorized over-the-air eavesdropping. Web transactions, for everything from commerce to social networking, are now routinely encrypted end-to-end. (A few applications, particularly email and wireline telephony, remain stubbornly unencrypted, but they are increasingly the exception rather than the rule.)

So, with this increasing proliferation of eavesdrop-thwarting encryption built in to our infrastructure, we might expect law enforcement wiretap rooms to have become quiet, lonely places.

But not so fast: the latest wiretap report identifies a total of just six (out of 3194) cases in which encryption was encountered, and that prevented recovery of evidence a grand total of … (drumroll) … zero times. Not once. Previous wiretap reports have indicated similarly minuscule numbers.

I second Matt’s recommendation of Susan Landau’s book: Surveillance or Security: The Risks Posed by New Wiretapping Technologies (MIT Press, 2011). It’s an excellent discussion of the security and politics of wiretapping.

Posted on July 27, 2011 at 2:10 PM • View Comments

World War II Tunny Cryptanalysis Machine Rebuilt at Bletchley Park

Neat:

The rebuild team had only a few photographs, partial circuit diagrams and the fading memories of a few original Tunny operators to go on. Nonetheless a team led by John Pether and John Whetter was able to complete this restoration work.

Pether explained that getting the electronics to work proved to be the most difficult part of the restoration process.

“We’ve succeeded in rebuilding Tunny with scraps of evidence, and although we are very proud of our work it is rather different from the truly astonishing achievement of Bill Tutte’s re-engineering of the Lorenz machine,” he said. “Sourcing 200 suitable relays and dealing with the complex wiring schedules was difficult, but we really got in tune with the original team when we had to set up the electronic timing circuits. They were a continuous source of problems then as they are even now for the rebuild team—except the original team didn’t even have the benefit of digital storage oscilloscopes.”

The rebuild took place in four stages: the construction of a one-wheel Tunny to ensure that timing circuits and relays worked correctly, followed by progressively more complex five-, seven- and 12-wheel Tunny. At each stage, the rebuilds were tested. Key components for the Tunny rebuild were salvaged from decommissioned analogue telephone exchanges, donated by BT. The same components were used to complete the earlier Colussus rebuild project.

Now they have a working Tunny to complement their working Colossus and working Bombe.

Posted on June 3, 2011 at 1:49 PM • View Comments

1 … 29 30 31 32 33 … 56

Sidebar photo of Bruce Schneier by Joe MacInnis.