138
2 Computer Viruses, Malicious Logic, and Spyware
Pseudo-random binary sequences
Fig. 2.10 Illustration of the algorithm’s operation according to the NSA specification
the method used for its selection is unknown. Parameters of the curve itself are also
set by a standard.
Operating Principle
Equation of the curve y = x
3
+ ax + b mod p can be rewritten as x = f (x, y) mod p; in
this case, we can write the following expressions for the operation of the algorithm:
r i = ϕ(s i · P), t i = ϕ(r i · Q), s i+1 = ϕ(r i · P)
s—internal state of the generator during the current step; s n—internal state of
the generator during the next step; t.—generator output during the current step.
Supposed Backdoor
Since p is a prime number, there is such number e that e Q = P. Finding e is a
computationally complex task of discrete logarithmation on an elliptic curve; there
are currently no effective algorithms to solve this task. However, if we suggest that
the intruder knows the value of e, we get the following attack: if x = t. is the next
operator output, and there is such y that y
2
= x
3
+ ax + b mod p, then the point A
= (x, y) lies on the curve, and the following equation is valid for it: A = r. · Q. If the
value e is known, it is possible to calculate the following: s. + 1 = f (e · A) = f (e · g.
· Q) = f (g · P). Thus, the intruder who knows the value e is able not only to calculate
the next generator output, but also to quickly search all possible internal states of
the generator and restore its initial internal state. According to independent studies,
if the value of e is known, it only takes 30 bytes of the output generator sequence
to search 215 values and restore its initial internal state. According to experts, such
vulnerability can be considered a backdoor.
2. Error in the implementation of the Apple TLS certificate verification protocol
Yandex researchers discovered a vulnerability in the implementation of the TLS
protocol in one of the Apple software products. According to the researches, this
error can very well be a backdoor, which was built into the algorithm by one of the
developers.
Code section containing the error:
2 Computer Viruses, Malicious Logic, and Spyware
Pseudo-random binary sequences
Fig. 2.10 Illustration of the algorithm’s operation according to the NSA specification
the method used for its selection is unknown. Parameters of the curve itself are also
set by a standard.
Operating Principle
Equation of the curve y = x
3
+ ax + b mod p can be rewritten as x = f (x, y) mod p; in
this case, we can write the following expressions for the operation of the algorithm:
r i = ϕ(s i · P), t i = ϕ(r i · Q), s i+1 = ϕ(r i · P)
s—internal state of the generator during the current step; s n—internal state of
the generator during the next step; t.—generator output during the current step.
Supposed Backdoor
Since p is a prime number, there is such number e that e Q = P. Finding e is a
computationally complex task of discrete logarithmation on an elliptic curve; there
are currently no effective algorithms to solve this task. However, if we suggest that
the intruder knows the value of e, we get the following attack: if x = t. is the next
operator output, and there is such y that y
2
= x
3
+ ax + b mod p, then the point A
= (x, y) lies on the curve, and the following equation is valid for it: A = r. · Q. If the
value e is known, it is possible to calculate the following: s. + 1 = f (e · A) = f (e · g.
· Q) = f (g · P). Thus, the intruder who knows the value e is able not only to calculate
the next generator output, but also to quickly search all possible internal states of
the generator and restore its initial internal state. According to independent studies,
if the value of e is known, it only takes 30 bytes of the output generator sequence
to search 215 values and restore its initial internal state. According to experts, such
vulnerability can be considered a backdoor.
2. Error in the implementation of the Apple TLS certificate verification protocol
Yandex researchers discovered a vulnerability in the implementation of the TLS
protocol in one of the Apple software products. According to the researches, this
error can very well be a backdoor, which was built into the algorithm by one of the
developers.
Code section containing the error: