Detecting Non-constant Time Code in Cryptography Libraries using a Static Information Flow Analysis

Open Access
Author:
Mohammed, Adam
Graduate Program:
Computer Science and Engineering
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
November 27, 2018
Committee Members:
  • Danfeng Zhang, Thesis Advisor
Keywords:
  • Information flow
  • Timing Channel
  • Public-key Cryptography
  • Static analysis
Abstract:
Identifying timing channels for cryptosystems is often a manual process. Addressing the cause of the timing channel is only possible once the flaw is identified. Using information-flow analysis it is possible to identify timing channels. For example, a branch dependent on secret data may cause a timing channel if the operations for each path are distinguishable by execution time. An information flow analysis can track the flow of sensitive information through a program. The issue is that the number of positives can be very high, and unequally weighted in the threat that may be posed. A static information-flow analysis can be used and the precision adjusted to improve the precision of the analysis. Improving the precision, means decreasing the overall number of positives while maintaining all of the higher-risk positives. In this work, an information flow analysis and a points-to analysis is used in conjunction to detect secret-dependent branches. Adding field-sensitivity in some cases improves the precision of the analysis. In some cases, field-sensitivity is not able to reduce the number of positives, so a white-list can be used to ignore positives that leak non-sensitive information such as key length. The baseline analysis combined with the field-sensitivity and whitelist were used in a case study exploring the effectiveness of each feature on real-world cryptosystems. The modular exponentiation function was analyzed as it is used in public-key cryptography and timing channel attacks have been identified in the code providing this functionality. The results show that improving the precision can be helpful to reduce the number of positives. An effort to categorize results is described, to help prioritize results in terms of estimated severity.