• 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

    NIST Announces First Four Quantum-Resistant Cryptographic Algorithms / Schneier · Wednesday, 6 July, 2022 - 16:49 · 1 minute

NIST’s post-quantum computing cryptography standard process is entering its final phases. It announced the first four algorithms:

For general encryption, used when we access secure websites, NIST has selected the CRYSTALS-Kyber algorithm. Among its advantages are comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation.

For digital signatures, often used when we need to verify identities during a digital transaction or to sign a document remotely, NIST has selected the three algorithms CRYSTALS-Dilithium , FALCON and SPHINCS+ (read as “Sphincs plus”). Reviewers noted the high efficiency of the first two, and NIST recommends CRYSTALS-Dilithium as the primary algorithm, with FALCON for applications that need smaller signatures than Dilithium can provide. The third, SPHINCS+, is somewhat larger and slower than the other two, but it is valuable as a backup for one chief reason: It is based on a different math approach than all three of NIST’s other selections.

NIST has not chosen a public-key encryption standard. The remaining candidates are BIKE , Classic McEliece , HQC , and SIKE .

I have a lot to say on this process, and have written an essay for IEEE Security & Privacy about it. It will be published in a month or so.

  • Sc chevron_right

    Hidden Anti-Cryptography Provisions in Internet Anti-Trust Bills / Schneier · Tuesday, 21 June, 2022 - 01:38 · 3 minutes

Two bills attempting to reduce the power of Internet monopolies are currently being debated in Congress: S. 2992, the American Innovation and Choice Online Act ; and S. 2710, the Open App Markets Act . Reducing the power to tech monopolies would do more to “fix” the Internet than any other single action, and I am generally in favor of them both. (The Center for American Progress wrote a good summary and evaluation of them. I have written in support of the bill that would force Google and Apple to give up their monopolies on their phone app stores.)

There is a significant problem, though. Both bills have provisions that could be used to break end-to-end encryption.

Let’s start with S. 2992. Sec. 3(c)(7)(A)(iii) would allow a company to deny access to apps installed by users, where those app makers “have been identified [by the Federal Government] as national security, intelligence, or law enforcement risks.” That language is far too broad. It would allow Apple to deny access to an encryption service provider that provides encrypted cloud backups to the cloud (which Apple does not currently offer). All Apple would need to do is point to any number of FBI materials decrying the security risks with “warrant proof encryption.”

Sec. 3(c)(7)(A)(vi) states that there shall be no liability for a platform “solely” because it offers “end-to-end encryption.” This language is too narrow. The word “solely” suggests that offering end-to-end encryption could be a factor in determining liability, provided that it is not the only reason. This is very similar to one of the problems with the encryption carve-out in the EARN IT Act. The section also doesn’t mention any other important privacy-protective features and policies, which also shouldn’t be the basis for creating liability for a covered platform under Sec. 3(a).

In Sec. 2(a)(2), the definition of business user excludes any person who “is a clear national security risk.” This term is undefined, and as such far too broad. It can easily be interpreted to cover any company that offers an end-to-end encrypted alternative, or a service offered in a country whose privacy laws forbid disclosing data in response to US court-ordered surveillance. Again, the FBI’s repeated statements about end-to-end encryption could serve as support.

Finally, under Sec. 3(b)(2)(B), platforms have an affirmative defense for conduct that would otherwise violate the Act if they do so in order to “protect safety, user privacy, the security of nonpublic data, or the security of the covered platform.” This language is too vague, and could be used to deny users the ability to use competing services that offer better security/privacy than the incumbent platform—particularly where the platform offers subpar security in the name of “public safety.” For example, today Apple only offers unencrypted iCloud backups, which it can then turn over governments who claim this is necessary for “public safety.” Apple can raise this defense to justify its blocking third-party services from offering competing, end-to-end encrypted backups of iMessage and other sensitive data stored on an iPhone.

S. 2710 has similar problems. Sec 7. (6)(B) contains language specifying that the bill does not “require a covered company to interoperate or share data with persons or business users that…have been identified by the Federal Government as national security, intelligence, or law enforcement risks.” This would mean that Apple could ignore the prohibition against private APIs, and deny access to otherwise private APIs, for developers of encryption products that have been publicly identified by the FBI. That is, end-to-end encryption products.

I want those bills to pass, but I want those provisions cleared up so we don’t lose strong end-to-end encryption in our attempt to reign in the tech monopolies.

  • 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

  • Ar chevron_right

    Zodiac Killer cipher is cracked after eluding sleuths for 51 years / ArsTechnica · Saturday, 12 December, 2020 - 16:11

Side-by-side police sketches on a WANTED poster.

Enlarge / Composite drawings of the Zodiac Killer. (credit: Getty Images)

A coded message sent by a brutal serial killer who has never been caught has been cracked more than 51 years after it was sent.

The male suspect, known as the Zodiac Killer, killed at least five people and attempted to kill at least two more in Northern California in 1968 and 1969. In the first three attacks, he targeted couples. The first victims were high school students who were parked in a car on their first date. In attacks on the other two couples, he managed to kill the women, but the men survived. A male San Francisco cab driver was the last known victim.

During the murder spree, the Zodiac Killer sent media outlets a series of letters taking credit for the slayings. To prove the authenticity of the claims, the letters included unreleased details and evidence from the crime scenes.

Read 12 remaining paragraphs | Comments