Elliptic Curve Back Door
According to Google, “Elliptic Curve Cryptography (ECC) is a key-based technique for encrypting data. ECC focuses on pairs of public and private keys for decryption and encryption of web traffic”
To comprehend how this works, let’s delve into random number generators (RNGs)
RNGs rely on a state, termed as the secret, which is initialized using real random data like keyboard taps or hard disk latency. Subsequently, this secret is processed through a one-way function, such as a hash function, to generate a random number. To ensure randomness for subsequent numbers, the secret undergoes further transformations, updating the state. This basic workflow secures the generation of random numbers, essential for cryptographic operations.
It’s crucial that these functions employ hash functions to prevent attackers from deducing the secret state. If the state is compromised, predicting subsequent random values becomes feasible.
In the early 2000s, the National Institute of Standards and Technology (NIST) introduced four new RNGs, including one based on elliptic curve, named Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG). This elliptic curve-based RNG intrigued many due to its unconventional approach.
Theory of Elliptic Curve Back Door
The Theory of Elliptic Curve Backdoor operates akin to the hash function previously mentioned. On an elliptic curve, a point P can generate multiples of itself, like aP.
However, determining the value of ‘a’ is notoriously challenging due to the elliptic curve discrete log problem.
Consider points P and Q on the curve, with a secret state for RNG operations. By traversing the curve multiple times based on the secret (s times), we arrive at sP, a coordinate on the graph. Extracting the x-coordinate of sP yields ‘r’, an intermediate value from which we calculate rQ. After discarding the first 16 bits, we obtain the desired random number. ‘r’ is then utilized to derive a new state by passing it through rP.
An attacker aiming to deduce the secret from the random number encounters obstacles. Even if they manage to obtain rQ, reversing it is infeasible due to its one-way nature.
Lets say if we brute force the first 16 digit from the random number to get to rQ which would be pow(2,16) = 65536, which is not a lot, lets say we get the rQ value but we cannot get to r if P and Q are random. We cannot brute force every r value for 256 bits.
What if there is a relation between P and Q? What if P = eQ, which is very difficult to prove, but it turns out NSA are the one’s who generated the P, Q and didn’t mentioned how
If a relationship exists between P and Q, such as P = eQ, where ‘e’ is a covert factor, theoretically, the secret could be compromised. This scenario raises concerns, especially considering allegations surrounding the origins of P and Q by organizations like the NSA.
So in theory if
P = eQ
P = e(rQ)
P = r(eQ)
P = r(P) Since P = eQSo theoretically we can get to the state function if the P and Q are not random.
When NIST standard was announced, despite cryptographers’ reservations regarding the security implications and inefficiencies of leaving off 16 bits, NIST proceeded with the standardization of this RNG
Around 2007, The revelations by security researchers Dan Shumow and Niels Ferguson regarding potential backdoors added to the skepticism surrounding this elliptic curve-based RNG. At that time this was already implemented on libraries.
The hypothetical scenario where a relation exists between P and Q, such as P = eQ, raises significant concerns about the security of the elliptic curve-based RNG. The discovery of such a relation could potentially compromise the security of cryptographic operations.
During this period, the release of Snowden’s leaks further fueled suspicions surrounding the integrity of cryptographic standards and the involvement of governmental agencies. The timing of these revelations, coinciding with discussions about potential backdoors in cryptographic algorithms, intensified scrutiny and skepticism within the cybersecurity community.
Interestingly, NIST mandated the use of specific P and Q values, implying distrust in allowing users to choose their own. This decision fueled further speculation about the existence of backdoors.
This case underscores the complexity and controversies surrounding cryptographic standards. Despite objections and suspicions, the standard was enforced, leaving lingering doubts about the presence of backdoors and the true extent of security vulnerabilities
