THE SMALL-OS SMART CARD OPERATING SYSTEM
The features and basic working principles of smart card operating systems are summarized in the previous sections of this chapter. For those readers who wish to immerse themselves more deeply into this subject, this section provides a detailed description of the internal interrelationships of a complete operating system. This is a classical smart card operating system according to the ISO/IEC 7816-4 or GSM 11.11 standard. The name of the operating system described in this section is ‘Small-OS’, which reflects its very small memory demands and the fact that it can be run on hardware platforms that are not particularly powerful. It is written in a pseudocode resembling Basic. The pseudocode shown here cannot be compiled as is, since some assignments have not been fully decoded to the last bit and are explained only verbally.We do not wish to present page after page of true program code in a language such as C or C++, which can be incomprehensible and boring to read. Instead, our objective is to present a graphic example that illustrates the subject. The ready comprehensibility of pseudocode greatly outweighs the advantages of using a real programming language, which are that it can be directly compiled and executed. With pseudocode, you do not get lost in the details of the implementation, and you can instead completely concentrate on the fundamental processes. The system presented here is platformindependent and is not tailored to any particular hardware. There is an actual implementation of Small-OS, but it is not programmed in assembler to run on a smart card microcontroller. Instead, it runs as a simulation in the program The Smart Card Simulator. This program is available at no charge under a GPL via the Internet [Rankl].

Programming in pseudocode
First we would like to make a few remarks about programming style and the programming of Small-OS. The pseudocode, which is derived from Basic, in principle represents a semiformal description of the Small-OS smart card operating system. Similar operating system characterizations are often used for software evaluations according to the ITSEC. They are used as the basis for the evaluation and for checking the source code. The pseudocode that is presented in this section thus represents a good example of how formalized processes within a smart card operating system are portrayed. The pseudocode is listed here in tables with extensive comments. Similar forms of presentation can be found in the EN 1546 series of standards, for example, in which the internal processes of smart cards for electronic purses are semi-formally described. The individual terms used in the pseudocode are described at the front of the book. The program code is based on the standard dialects of Basic, with object-oriented extensions. Only generally understandable constructs are used. All labels, constants and references are in English. Numerical values are usually given in hexadecimal form using ISO notation (such as ’42′). However, decimal or binary forms are used where necessary to aid understanding, using a notation that is derived from the ISO notation. For example, all countable values, such as length specifications, are shown in decimal form. Nobody would program a smart card operating system in this form in assembler or C, since it would be far too complicated. One of the design objectives with Small-OS was to create a simple yet powerful smart card operating system in a manner that is most easily understood and well commented. Intentionally, no attempt was made to minimize program execution time, program code, RAM usage or stack depth, since doing so would seriously impair the readability of the code. In real smart card operating system programming, for example, it is sometimes common practice to use a JUMP instruction instead of a CALL instruction for calls to rarely used subroutines, since this saves two bytes of expensive stack space. A flag that is set before the subroutine is called with the JUMP instruction and is used to determine the return address when the subroutine process is completed. This sort of optimization is not found in Small-OS, for the reason just given. The pseudocode has been optimized only with regard to readability and comprehensibility. The resulting deviations from real smart card operating systems are identified wherever they occur, either in the text or in the commented pseudocode. The majority of a smart card operating system is located in ROM, due to the notorious shortage of memory in smart card microcontrollers. It thus cannot be modified after the chip has been manufactured. Software cannot be produced with absolutely no errors (except for trivial miniprograms), but only with as few errors as possible. An error in ROM program code would have serious consequences. To make it possible to use bug fixes to patch such errors, jumps to EEPROM are provided at critical locations in the ROM. This technique is very old in software engineering and is not specific to smart cards. Nearly identical mechanisms are used in the MacOS and OS/9, for example. Locations in EEPROM that are called by the program code, called ‘handles’, are used for this. A handle normally contains only a RETURN instruction, which causes an immediate return to the calling code. If a bug fix for the ROM code is necessary, corrective code is inserted in the EEPROM at a handle location. In this case, the call to the handle does not produce an immediate return. This mechanism is not included in Small-OS, for reasons of simplicity and understandability. The relatively detailed description of the smart card operating system provides an interesting opportunity to follow several typical types of attacks directly in pseudocode. At suitable locations, possible attacks and defensive measures at the operating system level are described in detail. For example, it is possible to examine an attack on the PIN by comparing processing times, which has now become a ‘classic’ form of attack, in all of its details in the pseudocode. A comprehensive listing of typical attacks and their defenses is given in Chapter 8, ‘Security Techniques’.

Design criteria
The above considerations led to the following design criteria that guided the conception and programming of Small-OS. Small-OS should be a simple smart card operating system that does not need a lot of program code and has a low level of complexity, just like the real models that inspired it. This makes its structure comprehensible and easy to grasp. It is built up in a strictly modular fashion, which means that it can be directly extended with additional commands at a reasonable effort. The file system and the supported commands are without exception compliant with the international ISO/IEC 7816-4 standard. The ‘N’ profile of ISO/IEC 7816-4 was chosen as an option, with some extensions that are commonly present in the smart card world. Small-OS is thus intended to be used in situations in which it is not necessary to download applications after the cards have been issued. However, depending on the amount of available memory, several different applications could be run in the smart card independently of each other. This means that Small-OS is a multiapplication operating system. However, it is not possible to download program code to the card and then execute it in the card. In summary, Small-OS is comparable to the first general smart card operating systems, such as are still used in various forms for GSM applications. The ISO/IEC 7816-4 standard describes a basic file system and several fundamental commands for smart cards, among other things. In this way, it primarily characterizes the interface of the smart card, rather than the internal architecture of the operating system. In addition, there are numerous options and a few passages that unfortunately are subject to interpretation. The number of possible variations that are thus made possible must be sharply reduced in practice by specifications, such as the GSM 11.11 specification, to ensure compatibility between different implementations. With actual smart card operating systems, therefore, the designation ‘ISO/IEC 7816-4 compatible’ by no means signifies that they behave exactly the same way in all respects. This would need a detailed specification, which would again in part be an individual interpretation of the ISO/IEC 7816-4 standard. Consequently, in practice the behavior is usually the same only if the command is successfully executed, while there are various differences in case of an error.With Small-OS, interpretations of the ISO/IEC 7816-4 standard are usually identified as such in the pseudocode.Within the limits of the interpretation of the standard, Small-OS is truly compliant with the ISO/IEC 7816-4 standard and corresponds to the normal interpretations of the standard in the smart card industry as much as possible. Major differences between operating systems are frequently to be found in regard to return codes. Since the usage and priority of the individual return codes are not described in detail in ISO/IEC 7816-4, assumptions must be made. Small-OS, in contrast to all other operating systems, at least has the advantage that the code is public. This means that it is always possible to determine exactly which return code is generated. If one were to implement Small-OS for a smart card microcontroller, it would need around 5–6 kB of ROM, 128 bytes of RAM and at least 1 kB of EEPROM, depending on the number of applications present (using an 8051 processor). This assumes as general conditions that only the T = 1 data transmission protocol is used and that DES is used as the cryptographic algorithm. If certain applications were to need more memory, a microcontroller with more EEPROM could be used without any problems. This would not affect the operating system or require any modifications.

File access
The file system described in the ISO/IEC 7816-4 standard allows an enormous number of options with regard to access conditions and key management. For Small-OS, therefore, a solution that is often used in practice for multiapplication operating systems has been chosen. The file headers of working EFs contain prescribed states for each of the various access commands (for example, the condition . . . .AccessCondition.Read for the READ command). Each state is described by a positive integer. This means that each EF has independent state values for read and write accesses in its header. These values must be achieved within the current directory before the command can be executed. State 0 represents the base state (idle), so that a state condition of 0 means that all accesses are allowed. State variables are always assigned to the MF and the currently selected DF (Security State.MF and SecurityState.DF ). These can be altered by commands relating to security (VERIFY and INTERNAL AUTHENTICATE). In case of an access to a specific EF, the current state in the directory is compared with the required state in the EF file header. If the actual and required states are the same, then the file may be accessed for writing or reading. Real smart card operating systems often allow a large variety of less-than, greater-than, greater-than-or-equal and not-equal comparisons to be made here. It is also frequently possible to define several possible access states independently in the file header. This further complicates a process that is already not exactly simple, and for this reason it is not used in Small-OS. In principle, however, Small-OS could be extended to allow such comparisons without any structural modifications.

Access to internal secrets (PINs and keys)
All PINs and keys are held in special internal EFs. Such EFs are called EF Key here. This type of file can be read or written only by the operating system itself. External selection or access is not possible. There are no mechanisms at all in the design that would allow external access to such EFs. This is a part of the security philosophy of the Small-OS smart card operating system. Only one EF Key file can be created for each directory. It automatically has a linear variable structure, so that it can store PINs and keys of various lengths in a minimum amount of memory. Each record in an EF Key file contains either a PIN or a key, with an address number that is unique within the file ( . . . .KeyNo). For each secret object (PIN or key), a state value is stored. This defines the state ( . . . .EntryState) that is required for a command to be used (VERIFY or INTERNAL AUTHENTICATE). Following the execution of a command, the result state ( . . . .ResultState.OK or . . . .ResultState.NOK ) is set in the directory to which the EF belongs according to the result achieved (such as PIN comparison successful or not successful). In addition, a retry counter ( . . . .RCntr) is assigned to each secret object. This counter is incremented for each unsuccessful result until it reaches its maximum value. If the retry counter has reached its maximum value ( . . . .RCntrMaxValue), the associated secret object can no longer be used. Some smart card operating systems allow ‘cross-level’ access to keys. This allows keys stored in the next higher directory to be accessed from within a particular DF. The mechanisms needed for this are not included in Small-OS, since the functionality would not justify the amount of code needed to implement them. Key accesses via aliases are also not implemented, for the same reason.

Small-OS constants
Basically, constants are used in the pseudocode as much as is reasonable for numerical and non-numerical values. This considerably increases the readability of the code, and it is purely and simply good programming style. All constants are identified by the prefix C . The values of these constants normally depend on the target hardware or the implementation, so they are not further defined here. The constants for the 2-byte return codes all have the prefix C RC . Table 5.21 lists the associated return codes. In practice, the constants of an operating system are usually stored in unalterable form in the ROM.

Small-OS variables
The variables in Small-OS can basically be divided into RAM and EEPROM variables. The RAM variables are re-initialized each time the smart card is reset and retain their values only for the duration of one session. However, data can be stored in RAM variables without any loss of time, and the number of write cycles is unlimited. EEPROM variables, by contrast, are typically used primarily for the implementation of the file manager, for which data contents and access conditions must exist between sessions as well. Small-OS RAM variables The regions for the transmit and receive buffers take up the majority of the RAM variables. All data elements of an APDU can be addressed via their own specific variables. In order to manage with the small amount of available RAM, the transmit and receive buffers are in practice sometimes made partially overlapping. Some commands must then learn from the operating system exception handler that data can be written to the transmit buffer only after all the data in the receive buffer has been processed. In order to promote understandability, no such memory minimization is used here, and the transmit and receive buffers are thus completely separate from each other. The second large group of RAM variables relates to the management of the file tree. Several pointers are provided, which point to the current directory (. . . .Ptr.CurrentDF ), the current file (. . . .Ptr.CurrentWEF ) and the current valid key file (. . . .Ptr.CurrentIEF.Key ). With record-oriented EFs (linear fixed EFs), the currently selected record is also assigned a pointer (. . . .Ptr.CurrentRecord ). All pointers are identified by the prefix Ptr and are explicitly set to the value C InvalidPointer whenever they are not allowed to be used. The two variables SecurityState.MF and SecurityState.DF identify the security state in the MF and the currently selected DF, respectively. The security states that files have achieved are stored in these variables as positive integers. Here the value’0′indicates that no security state has been achieved. This value is automatically set when Small-OS is initialized after a reset. AdditionalRAMmemory is needed for the program stack, the DES cryptographic algorithm and working registers. Here it is assumed that these are implicit, so no special variables are assigned for them. Small-OS EEPROM variables For the sake of simplicity, the file tree in the smart card is implemented as a multidimensional array. This approachwould be much too memory-intensive for use in a real smart card operating system. The basic structures that are usually used in real systems for file management are one-way linked lists. The lengths of the list elements can be kept variable with the help of TLV encoding. This minimizes the amount of memory needed for file management, since only the necessary data elements have to be stored in memory. The size of the file headers for DFs and EFs, with all the information necessary for these files, is normally between 20 and 40 bytes. However, the multi-dimensional array file structure used in Small-OS can without question provide a simpler and more efficient solution when the operating system is implemented in a high-level language and runs in a hardware environment with relatively few memory limitations. A nearly identical construction is used in the ‘Smart Card Simulator’ program, for example