|
http://www.spinellis.gr/pubs/jrnl/1999-TISS-Reflect/html/reflect.html This is an HTML rendering of a working paper draft that led to a publication. The publication should always be cited in preference to this draft using the following reference:
|
Information appliances and other devices with embedded software are becoming ever more sophisticated and widely used [7]; increasingly in situations where their integrity is a prime concern. The complexity of their software and the rapidly evolving environment they are nowadays called to work in often mandate a field programming feature. Using this feature the owner or manufacturer can rapidly fix problems found after the product has left the factory, or even introduce new features.
Devices fitting the above description include mobile phones [3], pay-tv interfaces, sophisticated set-top boxes such as Web-tvs, credit card terminals, automatic teller machines, smart cards, routers, firewalls network computers, satellites, and space probes. As these devices often operate in a domain not fully controlled by the software’s stakeholders their software can be compromised. An adversary might want to modify a device’s software in order to avoid billing, bypass the device’s anti-theft measures or intellectual property protection mechanisms, or implant a surveillance or denial of service Trojan horse. A mechanism is therefore needed to remotely verify the integrity of a device’s controlling software.
In the following sections we will describe the problem, propose a solution based on software reflection, and outline some applications of our approach. The remainder of this paper is structured as follows: Section [sec:prob] outlines the problem we are addressing and the underlying assumptions; Section [sec:strat] describes the reflection-based solution strategy; Section [sec:vuln] contains an analysis of our approach’s vulnerabilities, while Section [sec:app] provides examples of possible applications. In Section [sec:rel] we outline work related to our approach, and Section [sec:concl] concludes the paper with an assessment of the approach’s contribution.
The problem concerns the integrity verification of a device’s controlling software. For risk analysis purposes we assume that the assets that are to be protected and the respective threats are those associated with consumer goods and services.
The global system for mobile communications (gsm), apart from the mobile subscriber identification and privacy security, provides functionality to secure the mobile terminal equipment (e.g. mobile phones) against theft. Each gsm terminal is identified by a unique International Mobile Equipment Identity (imei) number [14]. A list of imeis in the network is stored in the Equipment Identity Register (eir). The status returned in response to an imei query to the eir is one of the following:
The terminal is allowed to connect to the network.
The terminal is under observation from the network for possible problems.
The terminal has either been reported stolen, or is not type approved (as the correct type of terminal for a gsm network). The terminal is not allowed to connect to the network.
A widely used mobile phone stores the imei number in an eeprom (read-only memory that can be electrically re-programmed). The phone also provides a “debug mode” which is accessed by setting an external connector pin to a high voltage and sending a specific command sequence through the phone’s serial interface. The debug mode allows the programming of all the eeprom contents, including the control software and the location used to store the imei number. Reportedly, as a security measure, the phone’s software detects alterations to the imei number and resets all transceiver calibration data rendering the phone unusable. However, since all the phone’s program and data memory is field programmable using the phone’s serial interface, a sophisticated thief could reprogram a stolen phone with software that did not perform the imei security checks and a new imei.
Our problem can be formulated around the following entities:
The client is a software-controlled field-programmable device whose software integrity the software stakeholder wishes to protect. Examples of such clients are the devices outlined in Section [sec:intro].
The software stakeholder is an entity which has a business, legal, or regulatory interest in protecting the software’s integrity. Examples of software stakeholders are the gsm operators, the owners of communication satellites, or the operators of pay-per-view systems.
The server is a secure computer system under the control of the software stakeholder. The server can communicate with the client using a suitable communication protocol such as the remote procedure call.
The adversary is an entity which has an interest in modifying the client’s controlling software against the software stakeholder’s will.
The approach we propose is meaningful when the entities we described operate within a framework of specific assumptions. These assumptions, although they cannot be guaranteed are realistic under a risk-analysis view [15]: they hold true for a wide set of typical assets that are to be protected and associated threats. Examples of such typical asset-threat pairs include the illegitimate operation of a mobile phone by a well-connected street criminal, or the unauthorized viewing of a pay-per-view movie by a computer-science student.
[ass:re] The adversary can reverse engineer the client’s software and hardware. We assume that the client’s software including the software that controls the software upload session is stored in unprotected memory devices which can be read, reverse engineered, and modified. This assumption is typically valid due to cost restrictions imposed by tamper-resistant hardware and the low cost associated with modifying many firmware storage technologies such as eeproms, flash roms, and cd-roms.
[ass:mod] The adversary can modify the client’s software at will. As we will explain in Section [sec:nsauth] it is not feasible to protect the client’s upgrade procedure when Assumption [ass:re] holds true.
[ass:hw] The adversary cannot modify or substitute the client’s hardware. Under the risk analysis regime we outlined the cost of this operation would be prohibitive compared to the potential benefits.
[ass:mim] The adversary cannot mount a man in the middle attack. This mode of attack is often difficult and costly; its cost is comparable to that of the hardware substitution (Assumption [ass:hw]). In addition, if such an attack is mounted the integrity of the client’s software will be the least of the software stakeholder’s concerns.
[ass:entr] The effective entropy of the machine representation of the client’s functioning software is for practical purposes equal to the device’s available storage. This assumption means that the client is not allowed to contain empty or low-entropy memory contents. To realize this assumption empty memory can be filled with random data. In addition, low entropy memory can be compressed to increase its entropy. For cases where this approach is not feasible, in Section [sec:ext] we outline an extension to our approach which obviates the need for this assumption.
A number of solutions to the problem we outlined turn out to offer relatively weak protection or be infeasible in practice. In the following paragraphs we briefly outline these approaches, because each one of them contains a part of the solution we propose.
Protecting the client’s software integrity from unauthorized modification can be viewed as a standard access control problem solved through a suitable identification and authentication (i&a) service. I&a is the twofold process of identifying an entity and afterwards validating the identity of this entity. In order to implement an authentication mechanism, one must determine what information will be used to validate the potential user. Whatever that information is, it can be described by one or more of the following categories:
secret information (something the user knows),
possession of a device (something the user has),
biometrics (something the user is), or
location-based authentication (somewhere the user is).
Thus, the client could implement an i&a protocol for the software upgrade disallowing unauthorized software modifications. Unfortunately, since the adversary can reverse-engineer the client’s software, she can also reverse engineer the client’s authentication protocol and keys, and consequently obtain access to the software modification functionality.
One other approach could involve the calculation of a checksum of all the client’s program memory contents. The server could then periodically query the client for that checksum and verify it against a locally stored copy. The obvious weakness of this approach is that rogue software uploaded to the client by the adversary could implement a dummy version of the checksum function that would send back the checksum of the original software.
Although the adversary could implement a dummy checksum calculation function, it would be impossible for her, to store a complete copy of the original software in conjunction with the modified version due to the constraint imposed by the Assumption [ass:entr]. The server could therefore verify the client’s software integrity by requesting the client to transmit a copy of its operating software. The problem of this approach is the bandwidth required to implement it. Many clients communicate over a low bandwidth channel, yet contain a large amount of controlling software. Transmitting a copy of the software to verify its integrity could consume large amounts of time over a potentially costly communications medium.
Our approach is based on a synthesis of the two solution attempts described above.
Our solution is based on having the client’s software respond to queries about itself. The theoretical basis for this course is reflection. The foundation for the concept of reflection is Smith’s reflection hypothesis [18]:
“In as much as a computational process can be constructed to reason about an external world in virtue of comprising an ingredient process (interpreter) formally manipulating representations of that world, so too a computational process could be made to reason about itself in virtue of comprising an ingredient process (interpreter) formally manipulating representations of its own operations and structures.”
Based on this hypothesis, reflective programs can access, reason about, or alter their interpretation.
An important property of reflection is the casual connection between the system’s internal structures and the domain they represent [11]. It is this property of reflection, that requires the connection to internal structures and the represented domain to be behavioral rather than just functional, that we exploit to provide an authentication mechanism. Specifically, we reason that the internal representations of a system can be used to authenticate its external, functional properties.
Although the semantics of reflection in programming languages are often complicated, our requirements are modest and can in most cases be satisfied as a normal part of the system’s implementation i.e. without imposing special needs on the implementation language or environment. For our application it is sufficient to amend the client’s program with the ability to access its own internal, machine-code representation. Thus, the theory-relative self-knowledge implied by reflection boils down in our case to read-only access of the program’s internal representation. If the client’s program and its associated data are stored in memory locations \([0-L]\) the program needs to be able to bind the name of a memory location \(M\) with the value of its contents \(V\) and obtain that value. The viability of this operation is a consequence of a shared code-data (von Neumann) architecture and made possible in languages that support the use of unrestricted pointers such as C and C++. At a higher level, access to an application’s code memory can be supported through operating system abstractions such as system calls or special block device files [21].
In order to be able to verify the integrity of the device’s software, stakeholder Bob (\(B\)) amends the protocol the server uses to communicate with the client device (\(D\)) by adding the following message: \[\label{eq:db} B \rightarrow D: H(S, E)\]
This message requests from the device to compute and send back a cryptographic hash [16] (message digest) such as ripemd-160 [4] of its program storage locations ranging from \(S\) to \(E\). When the device receives this message it responds with the tuple:
\[D \rightarrow B: (V, H_{(V,S,E)})\]
which contains its operating program version \(V\) and the computed hash value \(H\) for that given version.
In order to verify the integrity of the device’s software, \(B\) needs to choose two random integers \(M_1\) and \(M_2\) that satisfy the following condition: \[0 \leq M_2 \leq M_1 \leq L\]
The following message exchange will then take place: \[\begin{aligned} B \rightarrow D& : & H(0, M_1) \label{eq:m1} \\ D \rightarrow B& : & (V, H_{(V,0,M_1)}) \label{eq:m2} \\ B \rightarrow D& : & H(M_2, L) \label{eq:m3} \\ D \rightarrow B& : & (V, H_{(V,M_2,L)}) \label{eq:m4}\end{aligned}\]
\(B\) will then retrieve from the server’s secure database a copy of the same software version \(V_L\), calculate the corresponding hash values, and compare them against the values sent by \(D\): \[\begin{aligned} H_{(V_L,0,M_1)} & \stackrel{?}{=} & H_{(V,0,M_1)} \\ H_{(V_L,M_2,L)} & \stackrel{?}{=} & H_{(V,M_2,L)}\end{aligned}\]
If the two values do not match \(B\) knows that the software has been tampered and can refuse service to that device, or reprogram it with the correct software.
The verification procedure we outlined overcomes the problems described in Section [sec:nonsol]. Specifically, unauthorized software modifications of any part of the software, including the part that implements the verification protocol, will be detected, as the modified software will be covered by the input range of at least one of the two hash functions and the respective function will yield a result different from the one calculated by the server on the original software. In addition, as the two positions used to delimit the ranges of the hash functions are specified dynamically as random integers during the protocol operation, the rogue software cannot precalculate and store all possible responses to the hash value query message [eq:db]; storage availability for storing the precalculated values is restricted by Assumption [ass:entr]. Finally, the amount of information transferred using the outlined protocol (messages [eq:m1]–[eq:m4]) is modest totaling less than 64 bytes in both directions for a 160 bit hash function; it is therefore practical to implement it even over low bandwidth channels.
The hash function used for evaluating the return value should be a cryptographicaly secure function such as ripemd-160. For a given program version \(V\) and a program of length \(L + 1\) this function maps the \(2(L+1)\) different \((S, E)\) tuples that can be requested by \(B\) onto the corresponding hash values. The properties of this function should preclude its emulation by any implementation other than one that has access to the original program code.
As \(M_2 \leq M_1\) the hashes computed will span over the entire program storage locations of \(D\). With ripemd-160 hash function implementations computing hashes at \(19.3\) Mbit/s (portable C implementation) up to \(39.9\) Mbit/s (hand-tuned x86 assembly) on 90 MHz Pentium machines [1] the performance of our approach is within the practical limits of both high-end (e.g. 2Mbyte rom 100MHz processor information appliances) and low-end (e.g. 20Kbyte rom 10MHz processor smartcards) hardware.
Our Assumption [ass:entr] specifies that the effective entropy of the machine representation of the client’s functioning software is for practical purposes equal to the device’s available storage. This assumption is not always easy to satisfy in practice. Physical memory contents are typically of low entropy and thus compressible [5]. An adversary could therefore compress the original software into an unused memory area and then execute and digest the compressed version using on-the-fly decompression techniques.
A way around this attack is based on the difficulty of predicting and monitoring a modern machine’s processor behavior. Although in the absence of external interrupts (which can be disabled) a processor operates in a deterministic fashion, the exact modeling and prediction of a modern processor’s state after a calculation is nowadays impossible without a low-level simulator and intimate knowledge of the processor’s architecture. The difficulty arises in sophisticated pipelined processor architectures [8] from the interdependencies of the multiple functional units, the many levels of cache, and branch predictors all dynamically changing their behavior as the program executes [19].
Processor state can be set to a known value before the message digest calculation and returned as part of the result to the server. The server can then query a client known to contain valid software for the same values and compare the results. Examples of processor state that can be queried are the contents of the processor’s cache or the processor’s clock-cycle granular “performance counter”. On-the-fly decompression will be immediately revealed by examining the number of clock-cycles that were required to calculate the hash using the performance counter. In addition, the behavior of the cache is affected by its \(n\)-way associativity — even a shift of the client’s software to a different address will probably affect the cache’s behavior during the program’s operation.
The meta-reflective extension to the protocol we propose can be implemented by amending the message exchange [eq:db] (the reply of \(D\)) to contain a representation of the state \(T_D\) at the end of the calculation of \(H_{(V,S,E)}\): \[D \rightarrow B: (V, H_{(V,S,E)}, T_D)\] \(B\) will then need to perform the same calculation on a second device \(D'\) known to contain a authentic version \(V\) of the software and compare the corresponding results: \[\begin{aligned} H_{(V_L,S,E)} & \stackrel{?}{=} & H_{(V,S,E)} \\ T_{D'} & \stackrel{?}{=} & T_D\end{aligned}\]
Although the precise details for obtaining \(T\) are hardware architecture and implementation dependent the general outline of this procedure is as follows:
Disable external interrupts.
Set the system state to a known initial value (e.g. clear the cache and the clock counter).
Perform the hash calculation.
Record the final system state \(T\).
Re-enable external interrupts.
An obvious vulnerability of the described scheme stems from the possibility of storing the original program code into locations not read by the hash function (e.g. unused memory) and using that code for generating the hash reply. A practical implementation of this approach could only store the original parts of the modified portions in unused memory and adjust the digest function accordingly. This vulnerability can be overcome by filling all unused program memory space with random data elements and extending the program space that can be hashed to include those elements. A refinement of the above attack involves either storing the original program code into unused data storage locations, or compressing the original and the modified program code to fit into the program memory together. In the latter case the modified program code is executed using either interpretive or on-the-fly decompression techniques. Both attacks can be avoided by using meta-reflective techniques or by structuring the software and the communications protocol in a way that will make such attacks detectable. As an example the end that communicates with the device can measure the reply latency for a given version to detect the slowdown imposed by decompression or interpretation.
Our approach is particularly vulnerable to a man in the middle attack. Specifically, an adversary can store a valid program in another pristine device \(D_p\); the compromised device \(D_c\) can relay the server authentication requests to \(D_p\) and send back the response of \(D_p\) to the server. Although we assumed that such an attack will typically be economically unattractive a simple solution exists: in many cases where communication takes place over a network with stable and controlled timing properties — such as the applications described in the following section — the attack can be detected by timing differences in the reply of \(D_c\).
In the following paragraphs we outline some applications of reflective software integrity verification in the areas of mobile phones, intellectual property protection, and smartcard-based systems.
The attack against the firmware of a mobile phone described in Section [sec:exemplar] can be made considerably more difficult by making the phone’s software sufficiently reflective. As an example, copies of the software of registered mobile phones could be kept in a secure database. Every time a mobile phone identifies itself to a base station, the base station could send it a software verification command and compare the phone’s response against the result calculated using the software copy in the server’s database. Phones failing the software verification would not receive service, making them unusable.
One other deployed technology that fits the usage scenarios of our approach is the one used for pay-per-view billing of digital content. The scheme used by the Digital Video Express dvix [13] discs allows consumers to view a film they purchase on a cheap dvd-like disc within 48 hours after first hitting the play button. Additional viewing sessions or “for life” viewing can be selected from a menu and then paid by credit card. The billing information is transferred overnight from the device to the company operations center using a modem built into the device. It is natural to assume that the device’s software will receive considerable interest from adversaries wishing to be able to view the disks without getting billed. Assuming that in order to continue to be able to view disks some keys will need to be supplied by the system’s server (thus prohibiting the stand-alone operation of a cracked system), the device’s communication protocol can be enhanced to respond to reflective commands in order to guard against unauthorized modifications to the device’s software. Similar strategies can be used to protect pay-per-view tv set-top boxes as well as the next generation of game consoles that will contain a built-in modem. Attacks against set-top boxes and game console software are already a reality; attacks against the DirectTV system were widely publicized; we are also aware of a modification performed on Sony Playstation consoles to make them work with illegal cd-r games copies.
Many smartcard applications such as electronic purses, credit cards, and phone cards depend on the smartcard’s integrity to protect the stakeholder’s financial interests against fraud. Advanced smartcard models integrate a microprocessor, ram, rom, an operating system, and application programs. Although smartcards are relatively tamper-proof devices, the possibility of attacks based on reverse engineering, fault injection [12], or misappropriation of confidential design information cannot be excluded. If a smartcard and its memory contents are successfully reverse engineered an adversary could implement a contraband version of the smartcard, or a corresponding emulator. A practical defense against contraband smartcards based on the same hardware as legitimate ones can be the extension of the card’s protocol with reflective verification techniques. In addition, meta-reflective techniques can be used to guard against attacks based on smartcard emulators.
Reflective capabilities were originally proposed to provide computational processes with the capability to reason both about a given domain and about their reasoning process over that domain [18]. The use of the reflection paradigm quickly spread beyond the area of programming language design and was applied in diverse areas such as windowing systems [17], operating systems [21], and distributed systems [6]. The power of reflection allows the implementation of open, flexible, and adaptable systems; a requirement in the areas it as been applied, and — in our view — an asset for security applications operating outside the absolute control of their stakeholders.
Reflective techniques for verifying the integrity of software are often used as part of a device’s power-up self-test procedure. This approach typically guards against hardware malfunctions of the memory system and therefore uses simple checksums instead of cryptographically secure hash functions. As an example, the bios rom of the original ibm pc contains code that calculates and verifies the rom checksum at power-up time [9]. Similar self-checking techniques have also been proposed for protecting programs against viruses [2]. Both types of protection cannot withstand attacks that can reverse engineer and modify the program that performs the check and, at the same time, is being checked.
A protocol similar to the one we outline has been proposed to supply a proof of existence of a particular block of data [20]. When \(B\) wants to prove to \(A\) that it possesses a particular block of data \(D\) (the exemplar case mentioned entails auditing of off-site backup services), \(A\) sends to \(B\) a random number \(R\). When responding, \(B\) calculates and returns to \(A\) the digest of \(RD\). \(A\) can the compare this value against a pre-calculated and stored value.
Finally, the use of hashes together with user-supplied passwords has been proposed as part of a method to securely boot workstations operating in a hostile environment [10]. Under this approach collision-rich hashing is used in conjunction with a low-entropy user password to protect the kernel against off-line password guessing attacks.
Reflection — the software reasoning about its operation — can provide a software verification basis for a large, commercially important, class of products and services. In the previous sections we formalized its use and described a verification protocol that can be used to verify that the software embedded in a device has not been modified. The reflective techniques can be extended at a meta level by reasoning about the software’s reasoning process thus providing an extra layer of security. The applications of our approach include software verification in personal communication devices, intellectual property protection, and smartcards. We believe that the increasing convergence of communication and information devices in a domain where security, privacy, and financial interests are often controlled by software will provide a fertile ground for applying many reflective techniques similar in spirit to the ones we described.
[1] A. Bosselaers, R. Govaerts, and J. Vandewalle. 1996. Fast hashing on the Pentium. In Advances in cryptology — CRYPTO ’96 16th annual international cryptology conference, 298–312. Retrieved from ftp://ftp.esat.kuleuven.ac.be/pub/COSIC/bosselae/pentium.ps.gz
[2] Fred Cohen. 1990. Implications of computer viruses and current methods of defense. In Computers under attack: Intruders, worms, and viruses, Peter J. Denning (ed.). Addison-Wesley, 381–406.
[3] Mark Cummings and Steve Heath. 1999. Mode switching and software download for software defined radio: The SDR forum approach. IEEE Communications 37, 8 (August 1999), 104–106.
[4] H. Dobbertin, A. Bosselaers, and B. Preneel. 1996. RIPEMD-160: A strengthened version of RIPEMD. In Fast software encryption: Third international workshop, Dieter Gollmann (ed.). Springer-Verlag, Berlin, 71–82. Retrieved from ftp://ftp.esat.kuleuven.ac.be/pub/cosic/bosselae/ripemd/ripemd160.ps.gz
[5] Fred Douglas. 1993. The compression cache: Using on-line compression to extend physical memory. In USENIX conference proceedings, 519–529.
[6] D. Edmond, M. Papazoglou, and Z. Tari. 1995. An overview of reflection and its use in cooperation. International Journal of Cooperative Information Systems 4, 1 (1995), 3–44.
[7] Brian Halla. 1998. How the PC will disappear. Computer 31, 12 (December 1998), 134–136.
[8] John L. Hennessy and David A. Patterson. 1996. Computer architecture: A quantitative approach (second ed.). Morgan Kaufmann, San Mateo, CA.
[9] IBM Corporation. 1983. IBM personal computer technical reference manual.
[10] Mark Lomas and Bruce Christianson. 1995. To whom am I speaking: Remote booting in a hostile world. Computer 28, 1 (January 1995), 50–54.
[11] Pattie Maes. 1987. Concepts and experiments in computational reflection. sigplan 22, 12 (December 1987), 147–155. Retrieved from http://www.acm.org/pubs/citations/proceedings/oops/38765/p147-maes/
[12] David P. Maher. 1997. Fault induction attacks, tamper resistance, and hostile reverse engineering in perspective. In Financial cryptography: First international conference, fC ’97, 109–121.
[13] Rajiv Mehrotra. 1999. In the news: Dueling over DVD and DIVX. IEEE Multimedia 6, 1 (January-March 1999), 14–19. Retrieved from http://dlib.computer.org/dynaweb/mu/mu1999/@Generic__BookTextView/685;nh=1;hf=0?DwebQuery=divx&DwebSearchAll=1#X
[14] Michel Mouly and Marie-Bernadette Pautet. 1992. The gsm system for mobile communications. Published by the authors.
[15] Charles Pfleeger. 1996. Security in computing. Prentice-Hall.
[16] J. Pieprzyk and B. Sadeghiyan. 1993. Design of hashing algorithms. Springer Verlag.
[17] R. Rao. 1991. Implementational reflection in Silica. In Proceedings of ECOOP ’91 european conference on object-oriented programming, 251–267.
[18] Brian Cantwell Smith. 1982. Procedural reflection in programming languages. Massachusetts Institute of Technology. Retrieved from http://theses.mit.edu:80/Dienst/UI/2.0/ShowPage/0018.mit.theses%2f1982-1?npages=762&format=inline&page=1
[19] Diomidis Spinellis. 1999. Software reliability: Modern challenges. In Proceedings ESREL ’99 — the tenth european conference on safety and reliability, 589–592. Retrieved from http://www.spinellis.gr/pubs/conf/1999-ESREL-SoftRel/html/chal.html
[20] Ross N. Williams. 1994. An introduction to digest algorithms. Retrieved from ftp://ftp.rocksoft.com/clients/rocksoft/papers/digest10.ps
[21] Yasuhiko Yokote. 1992. The Apertos reflective operating system: The concept and its implementation. sigplan 27, 10 (October 1992), 414–434. Retrieved from http://www.acm.org/pubs/citations/proceedings/oops/141936/p414-yokote/