Blog entry by Les Bell

Les Bell
by Les Bell - Monday, 6 February 2023, 5:52 PM
Anyone in the world

Welcome to today's daily briefing on security news relevant to our CISSP (and other) courses. Links within stories may lead to further details in the course notes of some of our courses, and will only be accessible if you are enrolled in the corresponding course - this is a shallow ploy to encourage ongoing study. However, each item ends with a link to the original source.

News Stories


2048-bit RSA Cracking Within Reach?

Most contemporary public-key cryptosystems are based on so-called trspdoor functions, which are special cases of one-way functions - functions which are easy to compute one way, but hard to reverse. There are two problems in widespread use: first, integer multiplication, for which the reverse problem, factorization of large composite integers, rapidly becomes very inefficient as the numbers get larger. This is the basis of the RSA public-key cryptosystem.

The second example is the discrete logarithm problem: raising an integer \(g\) to a power \(x\) is very fast, but the reverse - figuring out what power \(x\) a given integer, \(g\), was raised to in order to obtain a specified value \(h\) (finding the logarithm to the base \(g\) of \(h\)), is inefficient. In practice, we make both of these problems much harder by using modular arithmetic. This is the basis of the Diffie-Hellman key agreement protocol as well as the Elgamal cryptosystem.

The generation of RSA public and private keys starts by finding two large prime numbers, \(p\) and \(q\), and multiplying them to produce a large composite modulus \(N\), which becomes part of the public key. RSA would be broken if an attacker could quickly factorize \(N\).

For years, we have known that increases in compute power would therefore progressively weaken RSA. We have also known that improved factorization algorithms would further weaken it. And most of all, we have feared that the development of practical quantum computers could break it.

A new preprint paper which escaped my attention at the time suggests that a team of Chinese scientists may have taken advantage of all these possibilities to develop a technique which brings cracking of 2048-bit RSA keys within reach. In their paper, the researchers used quantum approximation algorithms, running on a quantum computer with 10 superconducting qubits, in combination with a classical lattice reduction algorithm, to factor integers up to 48 bits in size.

But what makes this result particularly interesting - or concerning - is that the algorithm is sublinear in the number of qubits required: \(\mathcal{O}(2N/\log{N})\). The authors suggest that their algorithm could therefore break a 2048-bit RSA modulus using a 372-qubit quantum computer. This is very much more practical than the millions of qubits that would be required by more straightforward approaches such as Shor's algorithm (because of the overhead of error correction).

Now, quantum computers of that size already exist in the public sphere - IBM's Osprey, for example is a 433-qubit machiine. And we do not know what exists inside the data centers of communications intelligence agencies world-wide; anyone who has a larger computer with the capability of breaking public-key crypto is obviously not going to talk about it.

My back-of-an-envelope calculations indicate that a 3072-bit RSA modulus - the smallest recommended for the NSA's Commercial National Security Algorithm Suite - could be cracked by a 531-qubit machine, while a 4096-bit RSA modulus would require a 683-qubit machine.

I do not believe the sky is falling - yet. However, I think this is something of a wake-up call - first, to users who are still using relatively small (1024-bit or 2048-bit) RSA keys, but also to security architects and regulators who have not yet started to prepare for the adoption of post-quantum cryptographic schemes. Personally, I long ago moved to 3072-bit RSA keys and subsequently to elliptic curve keys, which are not vulnerable to this particular attack. But I think it is now time to give serious consideration to a post-quantum escape plan.

Yan, Bao, et al, Factoring integers with sublinear resources on a superconducting quantum processor, arXiv preprint, 23 December 2022. Available online at http://arxiv.org/abs/2212.12372.

Collins, Hugh, IBM Unveils 400 Qubit-Plus Quantum Processor and Next-Generation IBM Quantum System Two, press release, 9 November 2022. Available online at https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two.

MITRE Releases Cyber-Resilience Design Tool

The pendulum of cybersecurity fashion is starting to swing away from playing whack-a-mole with vulnerabilities via pen-testing, then the same game with the remaining vulnerabilities via incident response, towards engineering cyber-resilient systems which are harder and will both slow intruders down and limit their abilities to penetrate further. This approach has most recently been advocated by NIST's Ron Ross and his team, in SP 800-160 volume 2, Developing Cyber-Resilient Systems: A Systems Security Engineering Approach.

Now, MITRE has joined the party, with a new tool called the Cyber Resiliency Engineering Framework (CREF) Navigator. Rather similar to MITRE's ATT&CK and D2FEND databases, the CREF Navigator provides a useful visualization of the various techniques which can be used to develop cyber-resilient systems, and maps them to the corresponding ATT&CK Tactics and Techniques, as well as the ATT&CK Mitigations and their effect on the adversary actions.

The CREF Navigator is organized around four fundamental goals:

  • Anticipate: informed preparedness for adversity
  • Withstand: Continue essential mission or business functions despite adversity
  • Recover: Restore mission or business functions during and after adversity
  • Adapt: Modify mission or business functions, and/or supporting capabilities, to prepare for predicted changes in the technical, operational or threat environments.

The four goals are supported by eight underlying objectives, such as Prevent or Avoid, Prepare, Constrain, Understand and Re-Architect. The techniques are many and varied, such as dynamic reconfiguration, redundancy by means of backup & restore, spare capacity or replication, and various forms of deception.

As well as the Navigator, there is also an Inspector, which allows further drilling down, and Map, which shows the relationships between Goals, Objectives and Techniques. Finally, a Visualizer shows relationships both within CREF and also between ATT&CK and CREF.

Uncredited, Getting Started, web documentation, undated. Available online at https://crefnavigator.mitre.org/gettingStarted.


These news brief blog articles are collected at https://www.lesbell.com.au/blog/index.php?courseid=1. If you would prefer an RSS feed for your reader, the feed can be found at https://www.lesbell.com.au/rss/file.php/1/dd977d83ae51998b0b79799c822ac0a1/blog/user/3/rss.xml.

Creative Commons License TLP:CLEAR Copyright to linked articles is held by their individual authors or publishers. Our commentary is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License and is labeled TLP:CLEAR.

Tags: