 |
The Texas Instruments signing key controversy resulted from Texas Instruments' (TI) response to a project to factorize the 512-bit RSA cryptographic keys needed to write custom firmware to TI devices.
| |
The Texas Instruments signing key controversy resulted from Texas Instruments' (TI) response to a project to factorize the 512-bit RSA cryptographic keys needed to write custom firmware to TI devices.
In July 2009, Benjamin Moody, a United-TI forum user, published the factors of a 512-bit RSA key used to sign the TI-83+ series graphing calculator. The discovery of the private key would allow end users to flash their own operating systems onto the device without having to use any special software. Moody used two free implementations of the general number field sieve, msieve and ggnfs; the computation took 73 days on a 1.9 GHz dual-core processor. This demonstrates the progress of hardware development: the factorization of the similar 512-bit RSA-155 in 1999 using the same algorithm required a large dedicated research group, 8000 MIPS-years of computing time, and a Cray C916 supercomputer. [1]
In response, members of the wider TI graphing calculators community (at yAronet) set up a BOINC-based distributed computing project, RSA Lattice Siever (RSALS for short), that quickly factored the other keys. [2] RSA Lattice Siever remained active for nearly three years after outliving its initial purpose, by factoring other integers for the mathematical community. After factoring over 400 integers, [3] RSALS moved to RSALS-inspired NFS@home [4] at the end of August 2012.
Texas Instruments began by sending out two initial Digital Millennium Copyright Act (DMCA) take-down requests to the hackers, referring to sites or forum posts that they controlled. [5] [6] The hackers responded by removing the keys, without consulting an attorney. [7] TI then sent further DMCA notices to a variety [8] of websites displaying the keys, including United-TI, Reddit, and Wikipedia. [9] Texas Instruments' efforts then became subject to the Streisand effect, [10] and the keys were mirrored on a number of sites, including WikiLeaks. [11] In September 2009, Dan Goodin from The Register alerted the Electronic Frontier Foundation (EFF) to TI's actions, and the EFF agreed to take on the case pro bono , representing three people who had received DMCA notices.
On October 13, 2009, the EFF sent a letter to TI warning them that the posting of the keys did not violate the DMCA, and that it might be liable for misrepresentation. [12] Despite the letter by the EFF, TI continued to send DMCA notices to websites that posted the keys, but stopped doing so after late 2009. The EFF filed a DMCA Section 512 counter-notice on behalf of three of the bloggers who received DMCA notices. When the EFF did not receive a response by the deadline, the bloggers reposted the content that had been taken down. [13]
The public RSA parameters of the original TI-83+ / TI-83+ Silver Edition OS signing key factored by Benjamin Moody are the following 512-bit modulus n and public (or encryption) exponent e (specified in hexadecimal): [14]
n = 82EF4009ED7CAC2A5EE12B5F8E8AD9A0AB9CC9F4F3E44B7E8BF2D57A2F2BEACE83424E1CFF0D2A5A7E2E53CB926D61F347DFAA4B35B205B5881CEB40B328E58F e = 11
By factoring n, Moody obtained the factors p (252 bits) and q (260 bits), which can be used in turn to quickly compute the 512-bit private (or decryption) :
p = B709D3A0CD2FEC08EAFCCF540D8A100BB38E5E091D646ADB7B14D021096FFCD q = B7207BD184E0B5A0B89832AA68849B29EDFB03FBA2E8917B176504F08A96246CB d = 4D0534BA8BB2BFA0740BFB6562E843C7EC7A58AE351CE11D43438CA239DD99276CD125FEBAEE5D2696579FA3A3958FF4FC54C685EAA91723BC8888F292947BA1
The value d can then be used to sign arbitrary OS software.
The keys factored by RSA Lattice Siever (the TI-92+, TI-73, TI-89, Voyage 200, TI-89 Titanium, TI-84+ / TI-84 Silver Edition OS signing and date-stamp signing keys) are similar but with different values of n, p, q, and d. A single date-stamp signing key is shared by all models.
In cryptography, key size or key length refers to the number of bits in a key used by a cryptographic algorithm.
In number theory, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.
Daniel Julius Bernstein is an American mathematician, cryptologist, and computer scientist. He is a visiting professor at CASA at Ruhr University Bochum, as well as a research professor of Computer Science at the University of Illinois at Chicago. Before this, he was a visiting professor in the department of mathematics and computer science at the Eindhoven University of Technology.
The TI-83 series is a series of graphing calculators manufactured by Texas Instruments.
The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography. They published a list of semiprimes known as the RSA numbers, with a cash prize for the successful factorization of some of them. The smallest of them, a 100-decimal digit number called RSA-100 was factored by April 1, 1991. Many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time, however advances in quantum computers make this prediction uncertain due to Shor's algorithm.
In mathematics, the RSA numbers are a set of large semiprimes that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories in March 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. The challenge was ended in 2007.
"The Magic Words are Squeamish Ossifrage" was the solution to a challenge ciphertext posed by the inventors of the RSA cipher in 1977. The problem appeared in Martin Gardner's Mathematical Games column in the August 1977 issue of Scientific American. It was solved in 1993–94 by a large, joint computer project co-ordinated by Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland. More than 600 volunteers contributed CPU time from about 1,600 machines over six months. The coordination was done via the Internet and was one of the first such projects.
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than the square root of n.
The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.
The TI-84 Plus is a graphing calculator made by Texas Instruments which was released in early 2004. There is no original TI-84, only the TI-84 Plus, the TI-84 Plus Silver Edition models, the TI-84 Plus C Silver Edition, the TI-84 Plus CE, and TI-84 Plus CE Python. The TI-84 Plus is an enhanced version of the TI-83 Plus. The key-by-key correspondence is relatively the same, but the TI-84 features improved hardware. The archive (ROM) is about 3 times as large, and the CPU is about 2.5 times as fast. A USB port and built-in clock functionality were also added. The USB port on the TI-84 Plus series is USB On-The-Go compliant, similar to the next generation TI-Nspire calculator, which supports connecting to USB based data collection devices and probes, and supports device to device transfers over USB rather than over the serial link port.
The TI-81 was the first graphing calculator made by Texas Instruments. It was designed in 1990 for use in algebra and precalculus courses. Since its release, it has been superseded by a series of newer calculators: the TI-85, TI-82, TI-83, TI-86, TI-83 Plus, TI-83 Plus Silver Edition, TI-84 Plus, TI-84 Plus Silver Edition, TI-84 Plus C Silver Edition, TI-Nspire, TI-Nspire CAS, TI-84 Plus CE, and most recently, the TI-84 Plus CE Python. Most of them share the original feature set and 96×64-pixel display that began with this calculator, with the exceptions of the TI-84 Plus C Silver Edition and the TI-84 Plus CE family.
The TI 73 series is a series of graphing calculators made by Texas Instruments, all of which have identical hardware.
In cryptography and number theory, TWIRL is a hypothetical hardware device designed to speed up the sieving step of the general number field sieve integer factorization algorithm. During the sieving step, the algorithm searches for numbers with a certain mathematical relationship. In distributed factoring projects, this is the step that is parallelized to a large number of processors.
TWINKLE is a hypothetical integer factorization device described in 1999 by Adi Shamir and purported to be capable of factoring 512-bit integers. It is also a pun on the twinkling LEDs used in the device. Shamir estimated that the cost of TWINKLE could be as low as $5000 per unit with bulk production. TWINKLE has a successor named TWIRL which is more efficient.
The TI-Nspire is a graphing calculator line made by Texas Instruments, with the first version released on 25 September 2007. The calculators feature a non-QWERTY keyboard and a different key-by-key layout than Texas Instruments's previous flagship calculators such as the TI-89 series.
Integer factorization is the process of determining which prime numbers divide a given positive integer. Doing this quickly has applications in cryptography. The difficulty depends on both the size and form of the number and its prime factors; it is currently very difficult to factorize large semiprimes.
Peter Lawrence Montgomery was an American mathematician who worked at the System Development Corporation and Microsoft Research. He is best known for his contributions to computational number theory and mathematical aspects of cryptography, including the Montgomery multiplication method for arithmetic in finite fields, the use of Montgomery curves in applications of elliptic curves to integer factorization and other problems, and the Montgomery ladder, which is used to protect against side-channel attacks in elliptic curve cryptography.
Digital signatures are a means to protect digital information from intentional modification and to authenticate the source of digital information. Public key cryptography provides a rich set of different cryptographic algorithms the create digital signatures. However, the primary public key signatures currently in use will become completely insecure if scientists are ever able to build a moderately sized quantum computer. Post quantum cryptography is a class of cryptographic algorithms designed to be resistant to attack by a quantum cryptography. Several post quantum digital signature algorithms based on hard problems in lattices are being created replace the commonly used RSA and elliptic curve signatures. A subset of these lattice based scheme are based on a problem known as Ring learning with errors. Ring learning with errors based digital signatures are among the post quantum signatures with the smallest public key and signature sizes
In post-quantum cryptography, ring learning with errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms, such as NewHope, designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption. Public-key cryptography relies on construction of mathematical problems that are believed to be hard to solve if no further information is available, but are easy to solve if some information used in the problem construction is known. Some problems of this sort that are currently used in cryptography are at risk of attack if sufficiently large quantum computers can ever be built, so resistant problems are sought. Homomorphic encryption is a form of encryption that allows computation on ciphertext, such as arithmetic on numeric values stored in an encrypted database.
