conclusions.tex 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
  1. \chapter{An Empirical Study \label{chap:empirical_study}}
  2. Excluding Dixon's factorization method, all attacks analyzed so far exploit
  3. some peculiarities of a candidate RSA public key $\angular{N, e}$ in order to
  4. recover the private exponent.
  5. Summarizingly:
  6. \begin{itemize}
  7. \item Pollard's $p-1$ attack works only if the predecessor of any of
  8. the two primes factorizing the public modulus is composed of very small
  9. prime powers;
  10. \item Williams' $p+1$ attack works under similar conditions - on the
  11. predecessor or the successor of any of the two primes ;
  12. \item Fermat's factorization is valuable whenever the two primes $p$ and $q$
  13. are really close to each other;
  14. \item Pollard's $\rho$ method is best whenever one of the two primes is
  15. strictly lower than the other;
  16. \item Wiener's attack is guaranteed to work on small private exponents.
  17. \end{itemize}
  18. Dixon's factorization method instead, being a general-purpose factorization
  19. algorithm, can be employed to \emph{measure} the strength of a RSA
  20. keypair: the more relations (satisfying \ref{eq:dixon:fermat_revisited}) are
  21. found, the less it is assumed to be resistant.
  22. Given these hypothesis, it has been fairly easy to produce valid RSA candidate
  23. keys that can be broken using the above attacks. They have been used to assert
  24. the correctness of the implementation.
  25. On the top of that, there has been a chance to test the software under real
  26. conditions: we downloaded the SSL keys (if any) of the top one million visited
  27. websites, and survey them with the just developed software. This not only gave
  28. us the opportunity to survey the degree of security on which the internet is
  29. grounded today, but also led to a deeper understanding of the capacities and limits of
  30. the most widespread libraries offering crypto nowadays.
  31. \vfill
  32. \section{To skim off the dataset}
  33. What has been most scandalous above all was to discover that more than
  34. \strong{half} of the most visited websites do \strong{not} provide SSL
  35. connection over port 443 - reserved for HTTPS according to IANA
  36. \cite{iana:ports}.
  37. To put it in numbers, we are talking about $533, 000$ websites either
  38. unresolved or unreachable in $10$ seconds.
  39. As a side note for this, many websites (like \texttt{baidu.com} or
  40. \texttt{qq.com}) keep a TCP connection open without writing anything to the
  41. channel, requiring us to adopt a combination of non-blocking socket with the
  42. \texttt{select()} system call in order to drop any empty communication.
  43. It would be interesting to investigate more on these facts, asking ourselves how
  44. many of those unsuccessful connections are actually wanted from the server, and
  45. how many dropped for censorship reasons; there is enough room for another
  46. project.
  47. Of the remaining $450,000$ keys, $21$ were using different ciphers than RSA. All
  48. others represent the dataset upon which we worked on.
  49. \section{To count}
  50. Once all valuable certificate informations have been stored inside a database,
  51. almost any query can be performed to get a statistically valuable measure of
  52. degree of magnitude to which some conditions are satisfied. What follows now is
  53. a list of commented examples that we believe are relevant parameters for
  54. understanding of how badly internet is configured today.
  55. \begin{figure}[H]
  56. \includegraphics[width=0.7\textwidth]{e_count.png}
  57. \end{figure}
  58. The most prolific number we see here, $65537$ in hexadecimal, is the fourth
  59. Fermat number and no other than the largest known prime of the form $2^{2^n} +
  60. 1$. Due to its composition, it has been advised by NIST as default public
  61. exponent, and successfully implemented in most software, such as \openssl\!.
  62. Sadly, a negligible number of websites is using low public exponents,
  63. which makes the RSA key vulnerable to Coppersmith's attack; though, this
  64. topic goes beyond the scope of this research and hence has not been analyzed
  65. further.
  66. \begin{figure}[H]
  67. \includegraphics[width=0.7\textwidth]{n_count.png}
  68. \end{figure}
  69. What is interesting to see here is that an enormous portion of our dataset
  70. shared the same public key, pushing down the number of expected keys of one
  71. order of magnitude. Reasons for this are mostly practical: it is extremely
  72. frequent to have blogs hosted on third-party services such as ``Blogspot'' or
  73. ``Wordpress'' which always provide the same X.509 certificate, as they belong to
  74. an unique organization.
  75. Though improbable, it is even possible that exists a millesimal portion of
  76. different websites sharing the same public key due to a
  77. bad cryptographically secure random number generator, and therefore also the
  78. same private key. Such a case has been already investigated in \cite{ron:whit}.
  79. \begin{figure}[H]
  80. \includegraphics[width=0.6\textwidth]{localhost_certs.png}
  81. \end{figure}
  82. Here we go. A suprisingly consistent number of websites provides certificates
  83. filled with dummy, wrong, or even testing informations.\\
  84. Some do have non-printable bytes in the \emph{common name} field.\\
  85. Some are certified from authorities. \\
  86. Some are even gonvernmental entities.
  87. \begin{figure}[H]
  88. \includegraphics[width=0.9\textwidth]{bits_count.png}
  89. \end{figure}
  90. According to \cite{nist:keylen_transitions} \S 3, table $2$, all RSA keys of
  91. bitlength less than $1024$ are to be considered deprecated at the end of $2013$
  92. and shall no more be issued since the beginning of this year. Not differently
  93. from the above results, the remark has been globally adopted, yet still with a
  94. few exceptions: around a dozen of non-self-signed certificates with a 1024 RSA
  95. key appears to have been issued in 2014.
  96. \section{The proof and the concept}
  97. At the time of this writing, we have collected the output of only two
  98. mathematical tests performed in the university cluster.
  99. \paragraph{Wiener.} The attack described in chapter \ref{chap:wiener} was the
  100. first employed, being the fastest one above all others. Recalling the different
  101. public exponents we probed and discussed in the preceeding section (all $\leq
  102. 65537$), we expected all private expenents to be $> \rfrac{1}{3}\sqrt[4]{N}$
  103. and therefore not vulnerable to this particular version of Wiener's attack.
  104. Indeed, we found no weak keys with respect to this attack. Though, as
  105. pointed out in \cite{20years} \S 3, there is still the possibilty that the
  106. public keys we collected could be broken employing some variants of it.
  107. \paragraph{GCD.} On the wave of \cite{ron:whit}, whe attempted also to perform
  108. the $\gcd$ of every possible pair of dinstinct public modulus present in the
  109. dataset. In contrast to our expectations, this test led to no prime factor
  110. leaked, for any key pair. We have reasons to believe this depends on the
  111. relatively small size of our dataset, with respect to the one used in
  112. \cite{ron:whit}.
  113. \chapter{Conclusions \label{conclusions}}
  114. Everytime we surf the web, we share our communication channel with lots of
  115. entities around the globe. End-to-end encryption protocols such as TLS can
  116. provide the security properties that we often take as granted, like
  117. \emph{confidentiality}, \emph{integrity}, and \emph{authenticity}; though,
  118. these holds only if we \emph{trust} the authorities certifying the end entity.
  119. %% Wax Taylor - Que Sera
  120. There is this mindless thinking that whenever we see that small lock icon in the
  121. browser's url bar, somebody is telling us the connection is safe.
  122. There is some authority out there telling what to do, and we should be thinking
  123. more about what these authorities are and what they are doing.
  124. This issue is no more a technical problem, but instead is becoming more and more
  125. a social and political problem.
  126. It is our responsability as citzens to do something about that.
  127. %%% Local Variables:
  128. %%% mode: latex
  129. %%% TeX-master: "question_authority"
  130. %%% End: