• Sc chevron_right

    Breaking RSA with a Quantum Computer / Schneier · Tuesday, 3 January - 17:38 · 1 minute

A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. This is something to take seriously. It might not be correct, but it’s not obviously wrong.

We have long known from Shor’s algorithm that factoring with a quantum computer is easy. But it takes a big quantum computer, on the orders of millions of qbits, to factor anything resembling the key sizes we use today. What the researchers have done is combine classical lattice reduction factoring techniques with a quantum approximate optimization algorithm. This means that they only need a quantum computer with 372 qbits, which is well within what’s possible today. (IBM will announce a 1000-qbit quantum computer in a few months. Others are on their way as well.)

The Chinese group didn’t have that large a quantum computer to work with. They were able to factor 48-bit numbers using a 10-qbit quantum computer. And while there are always potential problems when scaling something like this up by a factor of 50, there are no obvious barriers.

Honestly, most of the paper is over my head—both the lattice-reduction math and the quantum physics. And there’s the nagging question of why the Chinese government didn’t classify this research.

But…wow…maybe…and yikes! Or not.

“Factoring integers with sublinear resources on a superconducting quantum processor”

Abstract: Shor’s algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglogN ), which is sublinear in the bit length of the integer N , making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.

SIKE is one of the new algorithms that NIST recently added to the post-quantum cryptography competition.

It was just broken , really badly.

We present an efficient key recovery attack on the Supersingular Isogeny Diffie­-Hellman protocol (SIDH), based on a “glue-and-split” theorem due to Kani. Our attack exploits the existence of a small non-scalar endomorphism on the starting curve, and it also relies on the auxiliary torsion point information that Alice and Bob share during the protocol. Our Magma implementation breaks the instantiation SIKEp434, which aims at security level 1 of the Post-Quantum Cryptography standardization process currently ran by NIST, in about one hour on a single core.

News article .

  • Sc chevron_right

    Samsung Encryption Flaw / Schneier · Wednesday, 2 March, 2022 - 20:45 · 1 minute

Researchers have found a major encryption flaw in 100 million Samsung Galaxy phones.

From the abstract:

In this work, we expose the cryptographic design and implementation of Android’s Hardware-Backed Keystore in Samsung’s Galaxy S8, S9, S10, S20, and S21 flagship devices. We reversed-engineered and provide a detailed description of the cryptographic design and code structure, and we unveil severe design flaws. We present an IV reuse attack on AES-GCM that allows an attacker to extract hardware-protected key material, and a downgrade attack that makes even the latest Samsung devices vulnerable to the IV reuse attack. We demonstrate working key extraction attacks on the latest devices. We also show the implications of our attacks on two higher-level cryptographic protocols between the TrustZone and a remote server: we demonstrate a working FIDO2 WebAuthn login bypass and a compromise of Google’s Secure Key Import.

Here are the details:

As we discussed in Section 3, the wrapping key used to encrypt the key blobs (HDK) is derived using a salt value computed by the Keymaster TA. In v15 and v20-s9 blobs, the salt is a deterministic function that depends only on the application ID and application data (and constant strings), which the Normal World client fully controls. This means that for a given application, all key blobs will be encrypted using the same key. As the blobs are encrypted in AES-GCM mode-of-operation, the security of the resulting encryption scheme depends on its IV values never being reused.

Gadzooks. That’s a really embarrassing mistake. GSM needs a new nonce for every encryption. Samsung took a secure cipher mode and implemented it insecurely.

News article .

  • Ar chevron_right

    Divers recover a WWII Code Machine from the Baltic Sea / ArsTechnica · Sunday, 27 December, 2020 - 14:00

A deep-sea diver examines a heavily encrusted piece of machinery on the seabed.

Enlarge (credit: Reuters/Christian Howe )

When Nazi naval officers tossed their ship’s Enigma encryption machine overboard, they probably thought they were putting the device beyond anyone’s reach. Blissfully unaware that Allied cryptanalysts in Poland and at Bletchley Park in the UK had broken the Enigma code, the Nazis had standing orders to destroy their encryption devices to keep them out of Allied hands. Eighty years later, divers found the once-secret device tangled in an abandoned fishing net on the seafloor, and now it’s set to be put on display for everyone to see. LOL, Nazis pwned.

Research diver Florian Huber and his colleagues were trying to clear abandoned fishing nets from the Bay of Gelting, on the Baltic Sea near the German-Danish border, when they found the artifact. Derelict nets and other discarded fishing gear can still entangle fish, sea turtles, diving birds, and marine mammals like seals and dolphins. The World Wildlife Fund had hired the divers to clear them in November 2020.

“A colleague swam up and said ‘There’s a net there with an old typewriter in it,” Huber told the DPA news agency .

Read 7 remaining paragraphs | Comments