This file is raw output from pdftotext and may not be ideal for distribution. If you are a maintainer for Hackipedia, please sit down when you have time and clean this text version up. Source PDF: /mnt/fw-js/docs/Authentication/RSA SecurID/Initial Cryptanalysis of the RSA SecurID Algorithm.pdf Like all conversions the text below should be fully readable as UTF-8 unicode text. --------------------------------------------------------------- Initial Cryptanalysis of the RSA SecurID Algorithm Mudge and Kingpin {mudge,kingpin}@atstake.com @stake, Inc. http://www.atstake.com January 2001 Abstract 1 Introduction Recently, I.C. Wiener published a reverse engineer- The RSA SecurID token is currently based upon a ing effort of the RSA SecurID1 algorithm [1]. There proprietary algorithm and provides a 6- to 8-digit were few speculations on the security ramifications tokencode as output. This output is said to be a of the algorithm in I.C. Wiener’s posting, so this “new, unpredictable code” [4] displayed at 30- or note is an effort to touch upon areas of concern. We 60-second intervals. The algorithm being used as have verified that I.C. Wiener’s released version of of this writing was originally designed for and used the proprietary algorithm is accurate by comparing on a custom 4-bit microcontroller with an operating it with our own prior reverse engineering of the same speed of less than 1 megahertz. Given these opera- algorithm. tional and computational capabilities, the use of a 64-bit time value and a 64-bit secret component in Due to the time sensitivity imposed by the public a destructive algorithm were responsible choices to release of RSA’s proprietary algorithm, we felt it protect authentication over non-promiscuous chan- necessary to release this brief to help people better nels. understand and work toward reducing the risks to which they might currently be exposed. The risk If the tokencodes are presented over a medium that profile of token devices changes when they are im- can be monitored by an attacker or are viewed on plemented in an uncontrolled environment, such as a temporarily borrowed token device, the SecurID the Internet, and the research in this paper aims to implementation is left vulnerable if an attack ex- educate and to help manage those risks. The pri- ists to determine the secret component by viewing mary concern is the possiblity to generate a com- previously generated or successive tokencodes. Ad- plete cycle of tokencode outputs given a known se- ditionally, with the advent of soft-tokens existing cret, which is equivilent to the cloning of a token on popular operating systems and not dependent device. on specific hardware, the level of effort needed to retrieve the proprietary algorithm and secret com- This short paper will examine several discovered sta- ponent has been greatly reduced. If the algorithm is tistical irregularities in functions used within the Se- reversible or the initial components to the algorithm curID algorithm: the time computation and final are deducible, the risk of cloned cards or prediction conversion routines. Where and how these irregu- of future tokencodes is very real. larities can be mitigated by usage and policy are explored. We are planning for the release of a more The protective measures become simple: ensure the thorough analysis in the near future. This paper integrity and handling of hardware and software to- does not present methods of determining the secret ken devices, authenticate through encrypted com- component by viewing previously generated or suc- munications, and, as recommended in [2], ensure cessive tokencodes. that the back-end communications with the appli- cation server to the ACE authentication server [3] 1 SecurID is a registered trademark of RSA Security, Inc. are not implemented over public links. Pre-convert Value 64-bit Time Actual Algorithm Convert Tokencode 64-bit Secret Value Figure 1: High–level process of tokencode generation. With this stated, the rest of this document will ex- INT64 time64; amine areas of concern within the algorithm. INT32 time; UCHAR byte; // Seconds since 01/01/86, 00:00 time = gettimeofday(); 2 Algorithm Concerns // Round down time time = time / 30; time = time / 4; The tokencodes generated by the algorithm are de- time = time * 4; rived from two internal values: a 64-bit time value // Expand time into 64-bits and a 64-bit secret. The result of the algorithm is // (Duplicate least significant byte) then run through a final convert routine which fur- byte = time & 0xFF; time = time << 8; ther obfuscates the true algorithm output and pro- time = time | byte; duces a value suitable for display on a hardware- time64 = time; or software-based token (Figure 1). The value out- time64 = time64 << 32; put by the convert routine is 64-bits in length and time64 = time64 | time; is split into multiple tokencodes depending on the token device and display interval. Figure 2: Pseudo–code for the 64–bit time compu- tation routine. 2.1 Time shifted twice, which is equivalent to a multiplica- tion by 4. This guarantees, through the associative The variable input into the SecurID algorithm rep- property of multiplication, that the resultant value resenting the current time is a 64-bit value. How- will always be even. Hence, the least significant two ever, examination shows that this 64-bit value is bits will always be 00 and the only possible values generated from a 32-bit representation of the cur- for the least significant nibble are 0x0, 0x4, 0x8, rent time (GMT) in seconds since midnight on and 0xC. This multiplication removes two more bits 01/01/862 as shown in Figure 2. of entropy from the 24-bit time value leaving 222 or 4,194,304 total possible time values. It should For example, should the number of seconds from be pointed out that the possible time values can be the SecurID epoch be 0x1C39B862, the time further reduced if we assume the attacker has some value input to the SecurID algorithm would be prior knowledge of the approximate time the token- 0xF0DB7878F0DB7878. This is derived by round- code was generated. ing the initial number of seconds from the epoch to achieve a value of 0x00F0DB78. From this, the value The result of this reduced time space is that it is pos- is shifted left by 8 bits and the least significant byte sible to generate a complete tokencode “cycle” by in- is represented twice. Thus, it is apparent that only crementing through all possible values of time for a 24 bits are represented from the original 32-bit value single secret. The complete cycle contains 4,194,304 representing seconds from the epoch. total possible 64-bit outputs from the SecurID al- gorithm. The period of the cycle was designed to Within the rounding function, the value is left be longer than the lifetime of the token device, if 2 Security Dynamics, the creators of the SecurID card, be- the device is run in real-time (in the case where an gan operations in 1986. 8-digit tokencode length is used with a 60-second 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 A B A B A B A B A B C D C D C D C D C D E F E F E F E F E F Table 1: Displayed tokencode nibble and its possible pre–convert values display interval, it would take ≈16 years to cycle vide additional security to the SecurID algorithm. through all possible tokencode values). However, The fact that it provides a manner of obfuscation of using a modified soft-token device, time can be in- the pre-convert value is a by-product. cremented at a much faster rate, thus producing the entire tokencode cycle in a matter of minutes. For each nibble in the pre-convert value, if the nibble is greater than 9, the transform is used. Otherwise, if the nibble is less than or equal to 9, the natural 2.2 Secret number is displayed. From this, the value shown to the user could originate as represented in Table 1. In an ideal design, a hex value from 0xA through RSA has not divulged how they generate the initial 0xF could potentially be mapped to a decimal value 64-bit secrets that are used as one of the inputs into from 0 through 9. However, since 0xA, 0xC, and 0xE their algorithm. As these values are pre-ordained, can only be mapped to 0, 2, 4, 6, or 8 and 0xB, 0xD, one can assume that even if the generation mecha- and 0xF can only be mapped to 1, 3, 5, 7, or 9, nism was predictable, it can be changed transpar- the number of possible pre-convert values is greatly ently to a more random generation scheme. How- reduced. ever, even with strong pseudo-random or random number generation of the secret, the limited number of possible time values makes this point irrelevant For each nibble in hexadecimal pre-convert value { in certain cases. if (nibble > 9) { Should the secret component be compromised from nibble = nibble - 2; the physical hardware token or application execut- nibble = nibble - {0, 2, 4, 6, 8}; nibble = nibble % 10; ing the soft-token, all possible output values can be } cycled through and recorded by using the propri- } etary SecurID algorithm as in [1]. This could be done without tampering with the legitimate token device, so the attack would not be immediately de- Figure 3: Pseudo–code of simple transform within tected. the convert routine. Methods of determining the 64-bit secret from sam- plings of the token space will be looked at in the Given tlen as the length of the tokencode, for any more thorough analysis paper. given tokencode value the convert routine only pro- vides 4tlen possible pre-convert values, which can then be analyzed to determine particular bit config- 2.3 Convert urations of the actual secret. The ideal design would result in 7tlen possible pre-convert values. For ex- ample, a typical 6-digit tokencode has 46 or 4096 The tokencode value to be entered by the user is possible pre-convert values that could have gener- represented in decimal ranging from 6- to 8-digits in ated it. The ideal case would give 76 or 117,649 length. This decimal value is derived from a 64-bit possible pre-convert values. hexadecimal value, called the “pre-convert value”, using a simple transform (Figure 3). This function For each value of the actual displayed tokencode, was designed to map hexadecimal to decimal value there is a 62.5% probability that the number is the in a non-obvious manner and not intended to pro- natural number (e.g., a 0 displayed has a pre-convert value of 0), and a 12.5% probability that the number not to loan their devices to other people. In ad- is either {A, C, E} or {B, D, F}. Statistical detail dition, extra caution must be taken when utilizing is deferred to the more thorough paper. software-based tokens to verify that the host system is not easily compromised. 2.4 Collisions in Tokencode Cycle We are planning for the release of a more thorough analysis of RSA’s SecurID algorithm in the near fu- ture, which will further detail the statistical irreg- Analyzing tokencode cycles for a small sample of ularities described in this paper. We plan to ex- pseudo-randomly generated 64-bit secrets yields in- plore methods of determining the secret component teresting results. Out of the 8,388,608 possible to- by viewing previously generated tokencodes. Addi- kencodes (2 tokencodes produced for each value of tionally, we will examine exhaustive attack scenarios time), ≈8 million of those tokencodes are unique and and solutions based upon hypothesized deployment occur only once per cycle. The remaining ≈300,000 scenarios. are repeating or “colliding” values. unique tokens Collision % = (1 − total possible tokens ) × 100 References [1] I. C. Wiener, Sample SecurID Token Hence, 4% of the tokencode cycle consists of repeat- Emulator with Token Secret Import, ing values. We believe this is partly due to the con- BugTraq posting, December 21, 2000, vert routine. http://www.securityfocus.com/archive/1/ 152525. [2] PeiterZ, Weaknesses in SecurID 3 Conclusions [3] RSA Security, ACE/Server Web Page, http://www.rsasecurity.com/products/ securid/rsaaceserver.html. The concerns mentioned in this brief hope to mo- tivate further public assessment of the current Se- [4] RSA Security, SecurID Authenticators Web curID algorithm. Do they negate the usefulness Page, http://www.rsasecurity.com/ of an infrastructure utilizing this technology? No. products/securid/datasheets/ However, it does point to the possibility that com- dsauthenticators.html. panies might be assuming more risk than they need to. Hopefully, the detailed concerns provide an op- portunity for companies to evaluate how they have deployed this product. By encrypting the communications, limiting access to back-end communications, and ensuring the in- tegrity and whereabouts of the token generator, the risks of promiscuous viewing of the user authen- tication and tokencodes and potential retrieval of the secret component are minimized greatly. SSH, DESTelnet, SSL, and other encryption mechanisms can be deployed to help minimize these risks. IPSec, separate back-end management networks, and other means can be implemented to protect the back-end authentication that occurs between the application server and the ACE/Server. Users are encouraged to vigilantly protect their hardware token cards or software token key files and