SecurityBrief Australia logo
Australia's leading source of cybersecurity and cyber-attack news
Story image

Quantum Computation: A cryptography armageddon?

Mon 20 Jun 2016
FYI, this story is more than a year old

Article by Cassius Puodzious, ESET analyst

Cryptography is a cornerstone of information security. It is used to encode and decode data in order to fulfil the requirement for confidentiality, integrity, authenticity as well as non-repudiation. Together, these are frequently referred to as cryptography services.

Advances in cryptanalysis, computer science and engineering are always pushing the limits of what is considered secure. RSA, which was once believed secure under 129 bit-keys, nowadays is not considered secure using keys smaller than 2,048 bits. MD5, which was designed in 1992 and had been one of the most widely used hash functions, was proven to be breakable (in the sense of collision-attack) in 2004. Likewise, freestart collision against SHA-1, which is somewhat easier to find than standard collisions, was demonstrated and published at Eurocrypt 2016.

One of the resources in the toolkit of cryptanalysts is quantum computing. Quantum computing is based on physical quantum properties to perform operations, which behaves differently than the electronic properties we are used to finding in today’s computers and its basic unit of information, instead of bit, is called quantum bit or qubit. It started to be used in theoretical attacks against cryptosystems back in 1994, when Peter Shor published a quantum algorithm to find the prime factors of a given integer.

This algorithm enables the solving of integer factorisation and discrete logarithm problems, which are the basis of most (not to say all) widely used public-key cryptography algorithms. Less devastating in its impact but still of major importance, Grover’s quantum algorithm enables a huge speedup in search algorithms that impacts the security of many cryptosystems, including AES. This leads us to make a fairly surprising statement: all major cryptographic algorithms in use today are (virtually) broken!

Today, the only mitigating factor is the absence of a quantum computer large enough to run such algorithms against the parameters currently in use by crypto algorithms.

In the landscape of quantum computing everything is evolving fast. In April 2016, the European Commission announced plans to invest one billion euros in an EU project for a “large-scale EU-wide quantum technologies flagship”. As with this program, many others have been launched to fund the development of large-scale quantum computers.

Also in April 2016, researchers in Canada established a new record in quantum computer factorisation, after factoring the number 200,099 using a D-Wave 2X processor, although it is not clear whether D-Wave produces universal quantum computers able to run the Shor’s algorithm. Furthermore, 200,099 is only an 18-bit number, way too small to need the computation power required to factor a 2,048-bit integer to break current RSA parameters.

The current stage of large-scale deployment of public key cryptosystems counts on pretty elderly algorithms like Diffie-Hellman (1976), RSA (1977) and Elliptic Curves (1985). The latter was first published more than 30 years ago, but has recently started to be deployed on a large scale.

To tackle the cryptography armageddon imposed by large-scale quantum computers, cryptographers around the world have been working for at least a decade to design and improve cryptosystems resistant to quantum attacks, known as post-quantum cryptography or PQCrypto. Many cryptosystems have been designed and even standardised, like NTRU, nonetheless confidence in such new cryptosystems takes time to earn by being thoroughly scrutinised over and over again until they are proven to be ready for large-scale deployment.

What is the current state of PQCrypto?

In 2006 the first PQCrypto Conference was hosted, bringing together researchers to look for secure alternatives against quantum computing attacks. At the time, some alternatives were already at hand, such as McEliece encryption (1978), and ever since many programs to fund research in PQCrypto have been launched. This includes the European Commission’s SAFECrypto, a program for the development of quantum-resistant lattice-based cryptography, and CryptoWorks21, a Canadian program to develop next-generation quantum-safe cryptographic tools for the 21st century. The outcome of all these efforts towards PQCrypto is a huge advance in the field that has already provided post-quantum candidates that meet all desired features of like efficiency and key-size comparable to classic algorithms.

PQCrypto does not entail any special hardware. It is like classic crypto, but built on problems that are infeasible even for large quantum computers. PQCrypto algorithms have been designed to fulfil the services provided by classic crypto and many of them are able to run even on the most limited platforms.

How will PQCrypto evolve?

Even in a quantum world, current security protocols will continue to be as secure as they are today if their design assumptions are fulfilled using post-quantum cryptosystems. Thus, we should see a gradual adoption of modern PQCrypto algorithms by existing protocols over the coming years.

We should see a decline in the use of public-key algorithms most used nowadays, such as RSA and Elliptic Curves. In cases like symmetric crypto and hash functions, the current parameters will have to be revisited (usually doubled) to ensure that they stay secure in a quantum world. This shift to modern algorithms should happen transparently to end users; however, whoever is responsible for development or configuration of security applications should be ready for the coming changes – in particular, those who support these functionalities in legacy systems.

By way of speculating on how long it will take until large quantum computers are able to perform attacks on cryptosystems set with today’s parameters, let’s assume that Moore’s law will be valid throughout the development of quantum computation. Shor’s algorithm requires roughly 3 log2(N) qubits to factor an integer N (it means that Shor’s algorithms require roughly 6K qubits to break RSA-2048), whereas Moore’s law states that the number of bits – qubits here – that can be packed into a circuit doubles every 12-24 months.

As an exercise, let’s take a 5-qubit quantum computer such as the one made available online by IBM this month; then the total number of qubits available to run Shor’s algorithm after M cycles of Moore’s law can be calculated as 5 * 2M, therefore taking 18 months as an average cycle span of Moore’s law, we end up with approximately 16 years from now until attacks against RSA-2048 become feasible – it takes 16.5 years to go over 11 cycles of Moore’s law; this results in the availability of 10K qubits (more precisely 10240=5*211) after this period, which is able to supply the 6K qubits required to run the aforementioned attack.

The same magnitude of qubits goes for Grover’s algorithm (“between around 3,000 and 7,000 logical qubits”) to mount attacks against AES, so that their security level will be halved within that period of time. It means that if our assumptions hold, in sixteen years AES-256 will be as secure as AES-128 is today and AES-128 will be broken. Therefore, if we recall the time taken by Elliptic Curves until it was ready for wide deployment, we realise that clock is ticking for PQCrypto.

What should I care about and what should I do?

A topic that will have major impact along with the advance of quantum computing is long-term security, which can be related to:

Long-term authenticity; such as the life span of a digitally-signed contract

Long-term confidentiality; on legal grounds – for instance, the German Legal Code stipulates that medical data must remain confidential even after the patient´s death – or for strategic reasons, such as organisation or government secrets

Long-term authenticity can be accomplished using simple techniques, like re-signing a document using secure algorithms for as long as needed. Nonetheless, this possibility has to be foreseen and guaranteed by the underlying laws or any system of rules in place; otherwise it will also be threatened by the advance of quantum computation.

Yet, long-term confidentiality is a much more difficult task. There is no established way to address this issue and it is fair to state that none of the current public-key cryptosystems can fulfil this task. It might be a good choice to encrypt these data using strong symmetric cyphers using keys of at least 192 bits to stay secure even if their security level is halved by quantum computers.

Finally, if you expect long-term security for your information, then you should start looking for alternatives or planning for these changes right away. Adversaries who cannot overcome the security of your information today, by decrypting your data or forging your signature, can nevertheless keep a record of the data until they have quantum computers, at which point their attacks will succeed.

Article by Cassius Puodzious, ESET analyst

Related stories
Top stories
Story image
Adobe study finds lack of digital trust and utilisation in Australian Government agencies
New research commissioned by Adobe has revealed a significant lack of digital trust within Australian Government departments, along with the continued underutilisation of key digital processes.
Story image
Artificial Intelligence
Eight top DevSecOps trends to support IT innovation in 2022
The use of DevSecOps practices is growing, as it is increasingly seen as the best way to produce high-quality and secure code. So what are the current trends?
Story image
Digital Fingerprint
Decline in counterfeit cherries after digital fingerprinting
Reid Fruits says there’s been a dramatic decline in counterfeit products for its cherries over the past three export seasons to Asia because of digital fingerprinting.
Story image
Tech job moves
Tech job moves - Bitdefender, Cohesity, Fortinet & MODIFI
We round up all job appointments from June 27-30, 2022, in one place to keep you updated with the latest from across the tech industries.
Story image
Video: 10 Minute IT Jams - An update from CyberArk
Olly Stimpson joins us today to discuss the importance of MSP programmes and how MSP partners are experiencing success with CyberArk.
Story image
Digital Transformation
Cybersecurity priorities for digital leaders navigating digital transformation
In recent years, Asia-Pacific has especially been a hotspot for cyberattacks, and as we continue into 2022, it’s evident that the problem is becoming more significant.
Story image
Threat actors ramp up their social engineering attacks
As people get better at identifying potential threats in their inbox, threat actors must evolve their methods. Their new M.O? Social engineering.
Story image
Cyber Criminal
Identity and access: the fight is on
Blue team defenders are used to protecting our data, applications, and users with access controls and other security mechanisms, which is why attacks like this are especially challenging when they target identity and access control systems.
Story image
Varonis strengthens security capabilities for AWS and S3
Varonis has strengthened and expanded its cloud and security capabilities, with a critical aim of improving safety and boosting data visibility in Amazon Simple Storage Service (S3).
WSLHD and PwC’s Consulting Business came together to solve through the challenges of COVID-19. A model of care was developed to the NSW Health Agency for Clinical Innovation guidelines with new technology platforms and an entirely new workforce.
Link image
Story image
Tech and data’s role in the changing face of compliance
Accenture's study found that 93% of respondents agree or strongly agree new technologies such as AI and cloud make compliance easier.
Story image
Digital Transformation
What CISOs think about cyber security, visibility and cloud
Seeking to uncover the minds of CISOs and CIOs across Asia Pacific, my company recently asked Frost & Sullivan to take a snapshot of cloud adoption behaviour in the region.
Story image
Zero trust security adoption rises 27% in just two years
A survey of WAN managers has revealed that multi-factor authentication and single sign-on are the top zero trust features implemented.
Story image
Amazon Web Services / AWS
Zscaler, AWS accelerate onramp to the cloud with zero trust
Zscaler has announced an extension to its relationship with Amazon Web Services, as well as innovations built on Zscaler's Zero Trust architecture.
Story image
Identity and Access Management
Ping Identity launches corporate venture capital fund
Ping Identity has launched a corporate venture capital fund to foster innovative offerings for the identity security market.
Story image
IT and security team collaboration crucial to data security
Many IT and security decision makers are not collaborating as effectively as possible to address growing cyber threats.
Story image
Gartner's top recommendations for security leaders
"Leaders now recognise that major disruption is only one crisis away. We can’t control it, but we can evolve our thinking, philosophy, program and architecture.”
Story image
Forescout reveals top vulnerabilities impacting OT vendors
Forescout’s Vedere Labs has disclosed OT: ICEFALL, naming 56 vulnerabilities affecting devices from 10 operational technology vendors.
Story image
New study reveals 51% of employees using unauthorised apps
The research shows that 92% of employees and managers in large enterprises want full control over applications, but they don't have it.
Story image
Enterprise Resource Planning / ERP
Five ways your ERP is letting you down and why its time for a change
Wiise explains while moving to a new system may seem daunting, the truth is that legacy systems could be holding your business back.
Story image
Industry-first comprehensive risk-based API security enhances protection
Application Programming Interfaces (APIs) have become a crucial part of operating web and mobile application businesses and are causing significant economic growth in the digital sector.
Story image
Email threats spike 101%, remains a top attack vector
"Each year we see innovation in the threat landscape, but each year email remains a major threat to organisations."
Story image
Video: 10 Minute IT Jams - An update from CrowdStrike
Scott Jarkoff joins us today to discuss current trends in the cyber threat landscape, and the reporting work CrowdStrike is doing to prevent further cyber harm.
PwC's Consulting Business and PwC's Indigenous Consulting are proud to play an important role in helping Australian Indigenous Mentoring Experience build IMAGI-NATION, a free online university for marginalised communities around the world.
Link image
Story image
Vulnerable APIs costing businesses billions every year
Large companies are particularly vulnerable to the security risks associated with exposed or unprotected APIs as they accelerate digital transformation.  
Story image
State Library of Victoria
State Library of Victoria entrusts Oracle support and security to Rimini Street
“Our finance team are very happy with the support and security that Rimini Street provides, which keeps our assets and our customers secure."
Story image
Zscaler launches co-located data centres in Canberra and Auckland
The investment will offer public and private sector enterprises greater resilience in support of their zero trust cybersecurity posture.
Story image
Secure access service edge / SASE
Cloudflare adds new capabilities to zero trust SASE platform
New features for Cloudflare One include email security protection, data loss prevention tools, cloud access security broker, and private network discovery.
Story image
How New South Wales state departments achieved cloud migration success
State departments in New South Wales are heading to the cloud to achieve better workflow solutions, and one company is paving the way for their success.
Story image
Cloud Security
Palo Alto Networks bolsters cloud native security offerings
Latest Prisma Cloud platform updates help organisations continuously monitor and secure web applications with maximum flexibility.
Story image
Stock security features inadequate in face of rising risk
"Organisations must proactively find ways of identifying unseen vulnerabilities and should take a diligent, holistic approach to cybersecurity."
Story image
Artificial Intelligence
Juniper study reveals top AI trends in APAC region
Juniper's research shows an increase in enterprise artificial intelligence adoption over the last 12 months is yielding tangible benefits to organisations.
Story image
Secureworks reveals new information on BRONZE STARLIGHT threat group
New research from Secureworks has uncovered new information on the Chinese threat group BRONZE STARLIGHT and how they are using targeted ransomware to initiate complicated attacks.
Story image
WatchGuard Technologies
Ransomware volume doubled 2021 total by end of Q1 2022
Ransomware detections in the first quarter of this year doubled the total volume reported for 2021, according to a new report. 
Story image
Ingram Micro launches vendor-backed security program
Ingram Micro has unveiled a new program intended to give resellers the effective offerings their customers need to stay safe in the evolving threat landscape.
Story image
Phishing attacks are making a comeback
No matter what approach or tool cybercriminals use to breach a network, they all have one thing in common: access.
Story image
Tech job moves
Tech job moves - ActiveCampaign, Arcserve, LogRhythm & Qlik
We round up all job appointments from June 17-22, 2022, in one place to keep you updated with the latest from across the tech industries.
Story image
Internet of Things
ManageEngine wins big in IDC MarketScape assessment
ManageEngine's Endpoint Central service has been recognised as a leader by IDC MarketScape in several categories including Internet of Things device deployments and UEM software for SMEs.
Story image
HP Inc
Firmware attacks significant threat in age of hybrid work
Changing workforce dynamics are creating new challenges for IT teams around firmware security, according to new research.
Story image
Artificial Intelligence
Abnormal Security finds financial supply chain under threat
New research by Abnormal Security has found a rising trend in financial supply chain compromise as threat actors increasingly impersonate vendors.
Story image
Trend Micro
5G network projects driven by improving security and privacy
Trend Micro's new study reveals the prospect of improved security and privacy capabilities are the main motivations behind private 5G wireless network projects.
Story image
Network Security
Netskope announces zero trust network access updates
Customers can now apply zero trust principles across a range of hybrid work security needs, including SaaS, IaaS, private applications, and endpoint devices.
Story image
Oracle Cloud
Commvault, Oracle to deliver Metallic Data Management as a Service
"We are excited to partner with Commvault and enable our customers to restore and recover their most mission-critical cloud data."
Story image
Sternum joins NXP, collaborates on IoT security and observability
Sternum has announced it has joined the software partner community of NXP Semiconductors, a manufacturer of and large marketplace for embedded controllers.