=Paper= {{Paper |id=Vol-2081/paper16 |storemode=property |title=Vulnerability of RSA Algorithm |pdfUrl=https://ceur-ws.org/Vol-2081/paper16.pdf |volume=Vol-2081 |authors=Aleksandra V. Markelova }} ==Vulnerability of RSA Algorithm== https://ceur-ws.org/Vol-2081/paper16.pdf
                            Vulnerability of RSA Algorithm
                                                      Aleksandra V. Markelova
                                                 Information Security Department
                                             Bauman Moscow State Technical University
                                                         Moscow, Russia
                                                    markelova_bmstu@mail.ru



    Abstract—This paper is dedicated to ROCA-vulnerability that            Google, HP, Lenovo and Fujitsu released updates for their
was detected by scientists from Masaryk University, Czech. Their           software products susceptible to this attack.
investigation offers low-cost algorithm of factorization of RSA
module for special type of keys generated by some widely used                  Recall that the public key of the RSA algorithm is a pair
cryptographic library. They proposed a practical factorization             (n, e), where n is the product of two large primes and gcd(e,
method for various key lengths including 1024 and 2048 bits.               (n))=1. Private key is number d such that ed=1(mod (n)).
This attack requires no additional information except for the              Some implementations also store prime divisors of n as part of
value of the public key and does not depend on a weak or a faulty          the private key.
random number generator. We examine the possibility of
modification of type of keys to embed the trapdoor with universal             Thus, RSA requires two large random primes p and q, that
protection into key generator. In some cases we can design                 can be obtained by generating a random candidate number
Secretly Embedded Trapdoor with Universal Protection in the                (usually with half of the bits of n) and then testing it for
generator of RSA key. This problem is serious and relevant for             primality. If the candidate is found to be composite, the
all closed (so-called black-box) implementations of cryptographic          process is repeated with a different candidate.
algorithm in user’s library or device. The first section of this
                                                                               Since the RSA algorithm is very popular, many researches
article (“Introduction”) is devoted to the history of the issue. It
also describes the damage caused by vulnerability ROCA. The
                                                                           are devoted to its reliability [2, 3, 4, 5, 6, 7].
second section (“Fingerprint of weak keys”) describes the                     RSA security is based on the integer factorization problem.
criterion that the key pair is vulnerable to ROCA. The third
section (“Factorization”) is dedicated to the attack ROCA. It also             The most effective modern factorization algorithms (such
estimates the running time of the algorithm. In the fourth section         as quadratic sieve [8], number field sieve [9], special number
(“The trapdoor with universal protection”) we will consider the            field sieve [10, 11]) have subexponential complexity [12] and
possibility of using SETUP mechanism in the implementation of              in the general case do not allow hacking RSA with large key
RSA.                                                                       lengths.

    Keywords— information security, cryptanalysis, vulnerability,             However, if the numbers p and q are a special type, then the
ROCA, RSA, Coppersmith’s algorithm, factorization, weak keys,              time of factorization of the number n = pq can be reduced.
kleptography, trapdoor with protection, backdoor, SETUP
                                                                                    II.      FINGERPRINT OF WEAK KEYS
                       I.    INTRODUCTION                                      There is no common practice for developers of
    On November, 2017 Estonian government made a                           cryptographic library how to generate RSA key pair. But there
statement about blocking 760 000 certificate of ID cards issued            are many recommendations regarding how to select suitable
after October 16, 2014. The reason for this statement was the              primes p and q [13, 14, 15, 16] to be later used to compute the
vulnerability ROCA (Return of Coppersmith's Attack)                        private key and public moduli.
discovered by scientists from Masaryk University, Czech [1].                  In 2016, scientists from Masaryk University analyzed
    Toomas Ilves, the former president of Estonia, said that he            implementations of RSA algorithm and key pairs from 22
believed millions of people in countries had been affected by              open- and closed- source libraries and from 16 different smart
the ROCA flaw, but their authorities were remaining "silent".              cards [17]. In particular, the library RSALib used in Estonian
In particular, according to the researchers of the Enigma                  ID cards was investigated. This library utilizes an acceleration
Bridge, similar problems are possible with ID card of Spain.               algorithm called “Fast Prime”.
    There is a fast detection algorithm to verify whether a                   The foundations of “Fast Prime” date back to the year
particular key is vulnerable to attack. This verification is based         2000. According to its developers, its use started around ten
on the properties of the public moduli.                                    years later after thorough reviews. As a sub-part of one
                                                                           cryptographic software library which is supplied to customers
   Vulnerable keys were also found in some authentication                  as a basis for their own development, this software function
tokens, in the TPM (Trusted Platform Modules), in PGP.                     was certified by the BSI (Federal Office for Information
                                                                           Security) in Germany.




                                                                      74
   When compared to other implementations and theoretical                                               TABLE II.
expectations on distribution of prime numbers, the keys from
                                                                                 Key size                    Size of M                 ordM65537
RSALib exhibited a non-uniform distribution of (p mod x) and
(n mod x) for small primes x.                                             512                   2   219,19
                                                                                                                          2   62,09


                                                                                                    474,92
    Further studies have shown that all RSA primes generated              1024                  2                         2134,73
by the RSALib have the following form [1]:                                2048                  2970,96                   2255,78
                                                                          3072                  2970,96                   2255,78
                                      a
                      p=k*M + (65537 mod M)                   (1)         4096                  21962,19                  2434,69

    The integers k and a are unknown, and RSA primes differ
only in their values of a and k for keys of the same size. The               Online and offline versions of this test are already
integer M is fixed for each key size (table I) and equal to the           developed. They are freely available on the Internet.
product of the first successive primes:
                                                                                    III.    FACTORIZATION
                M = Pm =  pi = 2*3*5*7*…*pm                (2)            Algorithm ROCA iterates over values of a in (1) and use
                                                                          Coppersmith’s algorithm [19] to attempt to find k. To reduce
                                                                          the search, the modulus M is replaced by its divisor M', for
                           TABLE I.                                       which ordM'65537 is small and log2M'>log2n/4. The number M'
                                                                          is selected once for each RSA key size (table III).
           Key size                           M
512                          P39#=167#                                                                  TABLE III.
1024                         P71#=353#
                                                                                 Key size                    Size of M'               ordM'65537 /2
2048                         P126#=701#
                                                                          512                   2140,77                   219,20
3072                         P126#=701#                                                             474,92
                                                                          1024                  2                         229,04
4096                         P225#=1427#
                                                                          2048                  2970,96                   234,29
                                                                          3072                  2552,50                   299,29
      In this case the following comparison takes place:
                                                                          4096                  21098,42                  255,05

                        n = 65537c mod M                     (3)
                                                                              The size of M' (condition log2M'>log2n/4) is chosen to
    The existence of the discrete logarithm c = log65537n mod             apply the modification of the Coppersmith’s attack [19], which
M is used as the fingerprint of weakness of the key pair. In              is successful in case of knowing l/4 the least significant bits of
general, verification of solvability of the comparison (3) can            the number p, where l is the key size.
be difficult [18]. But if M is of the form (2) then the problem               Coppersmith’s attack was repeatedly modified. Now there
is easily solved.                                                         are various attacks on RSA based on Coppersmith’s algorithm.
   The number of residues modulo M for which there exists a               For example, factorization algorithms have been developed for
logarithm at base 65537 is equal to ordM65537. For randomly               cases when the lowest bits of the number p are known or when
generated prime numbers, the remainders from dividing their               primes p and q share bits in the middle ([20, 21, 22, 23]).
product by M are distributed uniformly in the multiplicative                  In attacks of this class, we choose a polynomial f(x)
group of residues modulo M. Therefore, the probability for the            having a small root x0 in the residue field:
number n to satisfy the comparison (3) is ordM65537/(M).
      For the M used, the value of ordM65537 is much less than                                       f(x0) = 0 mod p                                 (4)
(M). For example, ordM65537=262,09, (M)=2215,98 for RSA-
512. Thus, the probability of the false positive result does not
exceed 262–216=2–154. This probability is even smaller for larger                                             |x0|