Basic theory of state machines
The objective of this section is to provide an introduction to state diagrams, which are used to describe smart card applications, and a general explanation of how to interpret them. A state diagram is a type of graph that represents a set of states and the interrelationships of these states. The states are shown as nodes, and their relationships are shown as lines. If a line indicates a direction, which means that it has an arrowhead at one end, it is called a ‘directed line’ and the graph is a ‘directed graph’. The arrow indicates the direction in which a state transition can take place. The actual placement of the nodes and lines in the graph plays no part in the interpretation of the diagram. A sequence of nodes connected by lines is called a path. If the first and last nodes are the same and there is more than one node, the path is called a loop. This is only a very small part of graph theory, but it is essentially all we need to be able to describe states and their associated state machines in smart card applications.

Practical applications
An additional advantage of microprocessor cards compared with simple memory cards is that the command sequences can be specified in advance. It is thus possible to precisely specify all commands in terms of their parameters and sequence. In combination with object-oriented access authorization for files, this provides additional protection against unauthorized access. However, the possibilities offered by smart cards in this respect vary greatly. Simple operating systems usually cannot manage state machines, while with modern operating systems it is even possible to define application-specific state machines that work with command parameters. A typical example of a simple state machine is provided by the two commands needed to authenticate a terminal. The first command asks the card for a random number. This activates a state machine that accepts only an authentication command as the next command. If the card receives this command, the process completes and all other types of command are allowed. If the card receives any command other than an authentication command, the state machine generates an error message and the process is aborted. The command sequence must then be restarted from the beginning. Such simple state machines have several major advantages in smart cards. Since they are limited to very few commands in a rigidly defined sequence, they require little memory space and program overhead. In many applications, it is sufficient to protect file contents using objectoriented access mechanisms, without imposing any other restrictions on command sequences. Only a few procedures, such as authentication, must follow prescribed sequences. This can be implemented with very little memory using simple state machines.

These simple state machines can be extended to verify all commands, along with all of their parameters, within a defined graph before they are executed. Depending on how the
state machine is constructed, under certain conditions it may be possible to dispense with object-oriented file access protection, since the state machine can perform all the necessary checks before a command is actually executed. Of course, an error in the state diagram could have fatal consequences for the security of the system. As it is very difficult to verify the complete absence of errors in the state diagrams of complex state machines, file access protection is still used in practice. Correctly describing all of the processes and commands present on a smart card is very time-consuming, so it is often necessary to do this empirically to a certain extent. Now that we have described the advantages of state machines, we must mention their drawbacks. Implementing a state machine with the required capabilities is very time-consuming in terms of both design and subsequent programming. Since a state machine is controlled by the stored representation of a graph, a considerable amount of program memory is needed just to hold a state machine, since the graph must be stored in memory in addition to the actual state machine. The amount of memory space naturally depends on the complexity of the graph to be executed. The amount of information contained in a graph having many states and a corresponding number of transitions can be very large relative to typical smart card memory capacities. State machines for smart cards are addressed by the ISO/IEC 7816-9 standard. It describes ‘access control descriptors’ (ACDs), which define the commands that are permitted in a specific state, along with their associated parameters. A smart card operating system can monitor hardcodedstate machines using these ACDs.

In order to illustrate the capabilities of a state machine in summary form, Figure 4.10 shows the state diagram for a small application. Its operation is described below. After a reset, the smart card is in the initial state, denoted by 1. In this state, every file in the directory may be selected using SELECT FILE; this does not cause a state transition. All other commands except PIN verification (VERIFY) are prohibited, and the card responds to such commands with an error message. After successful verification of the PIN, the state machine changes to state 2. Two commands are permitted in state 2. The first path leads via SELECT FILE to state 3, where the selected file may be read. The second path originating from state 2 leads to state 4 after the terminal requests a random number from the card (ASK RANDOM). From here, any command other than EXTERNAL AUTHENTICATE leads back to the initial state (1). When the terminal has been successfully authenticated, the card reaches state 5. In this state, according to the diagram, files may be selected and written using SELECT FILE and UPDATE BINARY. In this diagram, states 3 and 5 cannot be exited during a session, so they represent the two end states. A transition to state 1 is only possible via a card reset. This is not shown in the diagram, since the ‘awareness’ of every state machine is limited to its current session. No information at all is transferred from one session to the next within the state machine.