Cellebrite Can Break Signal

Cellebrite announced that it can break Signal. (Note that the company has heavily edited its blog post, but the original — with lots of technical details — was saved by the Wayback Machine.)

News article. Slashdot post.

The whole story is puzzling. Cellebrite’s details will make it easier for the Signal developers to patch the vulnerability. So either Cellebrite believes it is so good that it can break whatever Signal does, or the original blog post was a mistake.

Zodiac Killer Cipher Solved

Zodiac Killer Cipher Solved

The SF Chronicle is reporting (more details here), and the FBI is confirming, that a Melbourne mathematician and team has decrypted the 1969 message sent by the Zodiac Killer to the newspaper.

There’s no paper yet, but there are a bunch of details in the news articles.

Here’s an interview with one of the researchers:

Cryptologist David Oranchak, who has been trying to crack the notorious “340 cipher” (it contains 340 characters) for more than a decade, made a crucial breakthrough earlier this year when applied mathematician Sam Blake came up with about 650,000 different possible ways in which the code could be read. From there, using code-breaking software designed by Jarl Van Eycke, the team’s third member, they came up with a small number of valuable clues that helped them piece together a message in the cipher

Sidebar photo of Bruce Schneier by Joe MacInnis.

Indistinguishability Obfuscation

Indistinguishability Obfuscation

Quanta magazine recently published a breathless article on indistinguishability obfuscation — calling it the “‘crown jewel’ of cryptography” — and saying that it had finally been achieved, based on a recently published paper. I want to add some caveats to the discussion.

Basically, obfuscation makes a computer program “unintelligible” by performing its functionality. Indistinguishability obfuscation is more relaxed. It just means that two different programs that perform the same functionality can’t be distinguished from each other. A good definition is in this paper.

This is a pretty amazing theoretical result, and one to be excited about. We can now do obfuscation, and we can do it using assumptions that make real-world sense. The proofs are kind of ugly, but that’s okay — it’s a start. What it means in theory is that we have a fundamental theoretical result that we can use to derive a whole bunch of other cryptographic primitives.

But — and this is a big one — this result is not even remotely close to being practical. We’re talking multiple days to perform pretty simple calculations, using massively large blocks of computer code. And this is likely to remain true for a very long time. Unless researchers increase performance by many orders of magnitude, nothing in the real world will make use of this work anytime soon.

But but, consider fully homomorphic encryption. It, too, was initially theoretically interesting and completely impractical. And now, after decades of work, it seems to be almost just-barely maybe approaching practically useful. This could very well be on the same trajectory, and perhaps in twenty to thirty years we will be celebrating this early theoretical result as the beginning of a new theory of cryptography.

New Report on Police Decryption Capabilities

There is a new report on police decryption capabilities: specifically, mobile device forensic tools (MDFTs). Short summary: it’s not just the FBI that can do it.

This report documents the widespread adoption of MDFTs by law enforcement in the United States. Based on 110 public records requests to state and local law enforcement agencies across the country, our research documents more than 2,000 agencies that have purchased these tools, in all 50 states and the District of Columbia. We found that state and local law enforcement agencies have performed hundreds of thousands of cellphone extractions since 2015, often without a warrant. To our knowledge, this is the first time that such records have been widely disclosed.

Lots of details in the report. And in this news article:

At least 49 of the 50 largest U.S. police departments have the tools, according to the records, as do the police and sheriffs in small towns and counties across the country, including Buckeye, Ariz.; Shaker Heights, Ohio; and Walla Walla, Wash. And local law enforcement agencies that don’t have such tools can often send a locked phone to a state or federal crime lab that does.


The tools mostly come from Grayshift, an Atlanta company co-founded by a former Apple engineer, and Cellebrite, an Israeli unit of Japan’s Sun Corporation. Their flagship tools cost roughly $9,000 to $18,000, plus $3,500 to $15,000 in annual licensing fees, according to invoices obtained by Upturn.

New crypto-cracking record reached, with less help than usual from Moore’s Law

New crypto-cracking record reached, with less help than usual from Moore’s Law

Researchers have reached a new milestone in the annals of cryptography with the factoring of the largest RSA key size ever computed and a matching computation of the largest-ever integer discrete logarithm. New records of this type occur regularly as the performance of computer hardware increases over time. The records announced on Monday evening are more significant because they were achieved considerably faster than hardware improvements alone would predict, thanks to enhancements in software used and the algorithms it implemented.

Many public-key encryption algorithms rely on extremely large numbers that are the product of two prime numbers. Other encryption algorithms base their security on the difficulty of solving certain discrete logarithm problems. With sufficiently big enough key sizes, there is no known way to crack the encryption they provide. The factoring of the large numbers and the computing of a discrete logarithm defeat the cryptographic assurances for a given key size and force users to ratchet up the number of bits of entropy it uses.

The new records include the factoring of RSA-240, an RSA key that has 240 decimal digits and a size of 795 bits. The same team of researchers also computed a discrete logarithm of the same size. The previous records were the factoring in 2010 of an RSA-768 (which, despite its digit is a smaller RSA key than the RSA-240, with 232 decimal digits and 768 bits) and the computation of a 768-bit prime discrete logarithm in 2016.

The sum of the computation time for both of the new records is about 4,000 core-years using Intel Xeon Gold 6130 CPUs (running at 2.1GHz) as a reference. Like previous records, these ones were accomplished using a complex algorithm called the Number Field Sieve, which can be used to perform both integer factoring and finite field discrete logarithms. A rough breakdown of the time spent in the sieving and matrixing of both the RSA factoring and the computation of the discrete logarithm problem are:

  • RSA-240 sieving: 800 physical core-years
  • RSA-240 matrix: 100 physical core-years
  • DLP-240 sieving: 2400 physical core-years
  • DLP-240 matrix: 700 physical core-years

Moore’s Law takes a back seat

It’s the first time that records for integer factorization and discrete logarithm have been broken together. It’s also the first time two records have been set using the same hardware and software. These aren’t the only things setting the latest milestones apart from previous ones.

When new records are set, the edicts of Moore’s Law inevitably play a major role. Moore’s Law is the trend that computer chips generally double the number of transistors they have every 18 months or so. The increase in transistors, in turn, boosts the computing power of computers running them, giving computers increased speed and performance over time.

While Moore’s Law was originally an observation made by Intel cofounder Gordon Moore in 1965, it has come to be viewed as almost an inescapable force of nature, like the laws of physics. Given the relentless march of Moore’s Law, it would be unusual if records like the one announced on Monday didn’t occur regularly.

This one, however, is driven less by Moore’s Law than previous milestones and more by improvements made in the software that carries out the Number Field Sieving. To demonstrate the boost in efficiency, the researchers ran their software on hardware that was identical to that used to compute the 768-bit discrete logarithm in 2016. They found that using the old hardware to sieve the record 795-bit size would take 25% less time than it took the same equipment to perform the 768-bit DLP computation.

Another sign of the improved performance: using identical hardware from 2016, the computation on the 795-bit logarithm was 1.33 times faster than it was on the 768-bit one. Estimates that are widely accepted in the field of cryptography predict that the larger size logarithm should be about 2.25 times harder to compute. Taken together, that suggests a three-fold performance increase over what was expected (that is 2.25*1.33=3). Since the hardware was the same for both bit sizes, the performance boost isn’t attributable to the availability of ever-faster computers.

“The acceleration can be attributed to various algorithmic improvements that were implemented for these computations,” the researchers wrote in Monday night’s announcement. Key to those improvements were updates made to the open source software used to implement the Number Field Sieve. Known as CADO-NFS, it comprises 300,000 lines of code written in C and C++.

Emmanuel Thomé, a senior researcher at France’s National Institute for Computer Science and Applied Mathematics and the leader of the team that set the record, said it’s not easy to describe the optimizations in layperson’s terms. The improvements, he wrote in an email, include:

  • we worked on better parallelization and memory usage (but our competitors also did, to be perfectly honest).
  • we took more systematic advantage of asymptotically fast algorithms in some compute-intensive parts of the computation.
  • there’s a big part of this crypto record business that calls to the art of “choosing parameters.” We did that really well. An important part of the picture is the ability to test many different parameter sets and rank them using accurate simulation tools that we developed.

But it’s only slightly less allusive than saying “various improvements.”

Other researchers on the team included Fabrice Boudot, of France’s Ministry of National Education and the University of Limoges, Pierrick Gaudry of the French National Center for Scientific Research, Aurore Guillevic with France’s National Institute for Computer Science and Applied Mathematics, Nadia Heninger with the University of Pennsylvania and the University of California, San Diego, and Paul Zimmermann of France’s National Institute for Computer Science and Applied Mathematics.

With so much attention devoted to the coming advent of quantum computers and their ability to easily break today’s public key encryption, researchers have been busy developing new schemes that can withstand such attacks.

“In the meantime, researchers have been making progress improving classical algorithms to solve factoring and discrete log, which together with Moore’s law results in new key sizes being breakable by computational resources available to academics,” Heninger wrote in an email. “The takeaways for practitioners are basically that we hope they have followed advice to move to at least 2048-bit RSA, Diffie-Hellman, or DSA keys as of several years ago, which would keep them safe from any of these improvements.”

Tech firms “can and must” put backdoors in encryption, AG Barr says

Graffiti urging people to use Signal, a highly encrypted messaging app, is spray-painted on a wall during a protest on February 1, 2017 in Berkeley, California.

Enlarge / Graffiti urging people to use Signal, a highly encrypted messaging app, is spray-painted on a wall during a protest on February 1, 2017 in Berkeley, California.
Elijah Nouvelage | Getty Images

US Attorney General William Barr today launched a new front in the feds’ ongoing fight against consumer encryption, railing against the common security practice and lamenting the “victims” in its wake.

“The deployment of warrant-proof encryption is already imposing huge costs on society,” Barr claimed in remarks at a cybersecurity conference held at Fordham University Tuesday morning. Barr added that encryption “seriously degrades” law enforcement’s ability to “detect and prevent a crime before it occurs,” as well as making eventual investigation and prosecution of crime more difficult.

The existence of encryption means “converting the Internet and communications into a law-free zone” that criminals will happily take advantage of to do more crimes, Barr added, likening it to a neighborhood that local cops have abandoned.

The cost of encryption, he said, is measured in “victims” who might have been saved from crime if law enforcement had been able to lawfully intercept communications earlier.

He also accused tech firms of “dogmatic” posturing, saying lawful backdoor access “can be and must be” done, adding, “We are confident that there are technical solutions that will allow lawful access to encrypted data and communications by law enforcement, without materially weakening the security provided by encryption.”

A long-running battle

In his diatribe, Barr is only picking up where predecessors left off. In 2017, then-deputy AG Rod Rosenstein said in an interview that the tech community’s “absolutist position” on strong encryption impeded law enforcement and was “unreasonable.”

Federal law enforcement has been in a very public encryption face-off with consumer electronics companies, particularly Apple, since 2016.

In December, 2015, a gunman killed and seriously injured dozens of victims in an attack in San Bernardino, California. The FBI ended up in possession of the shooter’s iPhone during the investigation but was unable to unlock the device, as the attacker had been killed and therefore could not be compelled to share his PIN.

The FBI demanded Apple cooperate in unlocking the phone by building a backdoor, and the company effectively told the feds to go pound sand. (The FBI eventually accessed the phone without Apple’s help.)

The relationship between the FBI and companies such as Apple that promote encryption has remained frosty ever since. Last year, an FBI official called Apple “jerks” about encryption, accusing the company of an “evil genius” approach to thwarting law enforcement.

“Responsible” backdoors

Rosenstein proposed a so-called “responsible encryption” scheme back in 2017, a call Barr echoed.

“I am suggesting that it is well past time for some in the tech community to abandon the posture that a technical solution is not worth exploring and instead turn their considerable talent to developing products that will reconcile good cyber security to the imperative of public safety and national security,” Barr said.

FBI Director Christopher Wray said last year that developing a process for allowing government officials lawful entry into encrypted communications would “entail varying degrees of innovation by the industry,” but he said he didn’t “buy the claim that it’s impossible.”

But no matter how many times government officials try to will such an option into existence, what they claim to want isn’t actually possible. Security experts and product makers have said time and time again that introducing a backdoor—an access portal for a specific entity to gain access through—into an encryption scheme weakens the whole thing.

Apple CEO Tim Cook has repeatedly said consumer privacy is of paramount importance to his company and that it’s in “everyone’s best interest” for everyone to be “blocked out,” with no secret backdoors.

Senator Ron Wyden (D-Ore.) in a 2018 letter to Wray (PDF) said the quest for a way in to encrypted communications amounts to “a flawed policy that would harm America’s security, liberty, and our economy.”

“Building secure software is extremely difficult,” Wyden added, “and vulnerabilities are often introduced inadvertently in the design process. Eliminating these vulnerabilities is a mammoth task, and experts are unified in their opinion that introducing deliberate vulnerabilities would likely create catastrophic unintended consequences that could debilitate software functionality and security entirely.”