Introduction to Computer Security

Michael Goodrich Roberto Tamassia

First Edition
Pearson Education Limited
Edinburgh Gate
Harlow
Essex CM20 2JE
England and Associated Companies throughout the world

Visit us on the World Wide Web at: www.pearsoned.co.uk

© Pearson Education Limited 2014

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted
in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without either the
prior written permission of the publisher or a licence permitting restricted copying in the United Kingdom
issued by the Copyright Licensing Agency Ltd, Saffron House, 6–10 Kirby Street, London EC1N 8TS.

All trademarks used herein are the property of their respective owners. The use of any trademark
in this text does not vest in the author or publisher any trademark ownership rights in such
trademarks, nor does the use of such trademarks imply any affiliation with or endorsement of this
book by such owners.

ISBN 10: 1-292-02540-9

ISBN 13: 978-1-292-02540-7

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library

Printed in the United States of America

 P E A R S O N C U S T O M L I B R A R Y

Table of Contents

1. Introduction
Michael T. Goodrich/Roberto Tamassia 1
2. Physical Security
Michael T. Goodrich/Roberto Tamassia 55
3. Operating Systems Security
Michael T. Goodrich/Roberto Tamassia 113
4. Malware
Michael T. Goodrich/Roberto Tamassia 173
5. Network Security I
Michael T. Goodrich/Roberto Tamassia 221
6. Network Security II
Michael T. Goodrich/Roberto Tamassia 269
7. Web Security
Michael T. Goodrich/Roberto Tamassia 327
8. Cryptography
Michael T. Goodrich/Roberto Tamassia 387
9. Distributed-Applications Security
Michael T. Goodrich/Roberto Tamassia 445
10. Bibliography
Michael T. Goodrich/Roberto Tamassia 499
Index 505

I
This page intentionally left blank
 Introduction

Contents

1 Fundamental Concepts
1.1 Confidentiality, Integrity, and Availability
1.2 Assurance, Authenticity, and Anonymity
1.3 Threats and Attacks
1.4 Security Principles
2 Access Control Models
2.1 Access Control Matrices
2.2 Access Control Lists
2.3 Capabilities
2.4 Role-Based Access Control
3 Cryptographic Concepts
3.1 Encryption
3.2 Digital Signatures
3.3 Simple Attacks on Cryptosystems
3.4 Cryptographic Hash Functions
3.5 Digital Certificates
4 Implementation and Usability Issues
4.1 Efficiency and Usability
4.2 Passwords
4.3 Social Engineering
4.4 Vulnerabilities from Programming Errors
5 Exercises

From Chapter 1 of Introduction to Computer Science, First Edition, Michael T. Goodrich,

Roberto Tamassia. Copyright 2011 by Pearson Education, Inc. Published by
Pearson Addison-Wesley. All rights reserved.

1
 Introduction

1 Fundamental Concepts

In this chapter, we introduce several fundamental concepts in computer

security. Topics range from theoretical cryptographic primitives, such as
digital signatures, to practical usability issues, such as social engineering.
Existing computer systems may contain legacy features of earlier ver-
sions dating back to bygone eras, such as when the Internet was the sole
domain of academic researchers and military labs. For instance, assump-
tions of trust and lack of malicious behavior among network-connected
machines, which may have been justifiable in the early eighties, are surpris-
ingly still present in the way the Internet operates today. Such assumptions
have led to the growth of Internet-based crime.
An important aspect of computer security is the identification of vulner-
abilities in computer systems, which can, for instance, allow a malicious
user to gain access to private data and even assume full control of a
machine. Vulnerabilities enable a variety of attacks. Analysis of these
attacks can determine the severity of damage that can be inflicted and
the likelihood that the attack can be further replicated. Actions that need
to be taken to defend against attacks include identifying compromised
machines, removing the malicious code, and patching systems to eliminate
the vulnerability.
In order to have a secure computer system, sound models are a first
step. In particular, it is important to define the security properties that
must be assured, anticipate the types of attacks that could be launched,
and develop specific defenses. The design should also take into account
usability issues. Indeed, security measures that are difficult to understand
and inconvenient to follow will likely lead to failure of adoption. Next, the
hardware and software implementation of a system needs to be rigorously
tested to detect programming errors that introduce vulnerabilities. Once
the system is deployed, procedures should be put in place to monitor the
behavior of the system, detect security breaches, and react to them. Finally,
security-related patches to the system must be applied as soon as they
become available.
Computer security concepts often are better understood by looking
at issues in a broader context. For this reason, this text also includes
discussions of the security of various physical and real-world systems,
including locks, ATM machines, and passenger screening at airports.

2
 Introduction

1.1 Confidentiality, Integrity, and Availability

Computers and networks are being misused at a growing rate. Spam,
phishing, and computer viruses are becoming multibillion-dollar problems,
as is identity theft, which poses a serious threat to the personal finances
and credit ratings of users, and creates liabilities for corporations. Thus,
there is a growing need for broader knowledge of computer security in
society as well as increased expertise among information technology pro-
fessionals. Society needs more security-educated computer professionals,
who can successfully defend against and prevent computer attacks, as well
as security-educated computer users, who can safely manage their own
information and the systems they use.
One of the first things we need to do in a text on computer security
is to define our concepts and terms. Classically, information security has
been defined in terms of the acronym C.I.A., which in this case stands for
confidentiality, integrity, and availability. (See Figure 1.)

© Fotolia, LLC–Royalty Free

Integrity

Confidentiality Availability
© Andresr/Shutterstock © Yuri Arcurs/Fotolia, LLC–Royalty Free

Figure 1: The C.I.A. concepts: confidentiality, integrity, and availability.

3
 Introduction

Confidentiality
In the context of computer security, confidentiality is the avoidance of the
unauthorized disclosure of information. That is, confidentiality involves
the protection of data, providing access for those who are allowed to see it
while disallowing others from learning anything about its content.
Keeping information secret is often at the heart of information security,
and this concept, in fact, predates computers. For example, in the first
recorded use of cryptography, Julius Caesar communicated commands to
his generals using a simple cipher. In his cipher, Caesar took each letter in
his message and substituted D for A, E for B, and so on. This cipher can be
easily broken, making it an inappropriate tool for achieving confidentiality
today. But in its time, the Caesar cipher was probably fairly secure, since
most of Caesar’s enemies couldn’t read Latin anyway.
Nowadays, achieving confidentiality is more of a challenge. Computers
are everywhere, and each one is capable of performing operations that
could compromise confidentiality. With all of these threats to the confiden-
tiality of information, computer security researchers and system designers
have come up with a number of tools for protecting sensitive information.
These tools incorporate the following concepts:
• Encryption: the transformation of information using a secret, called
an encryption key, so that the transformed information can only be
read using another secret, called the decryption key (which may, in
some cases, be the same as the encryption key). To be secure, an
encryption scheme should make it extremely difficult for someone to
determine the original information without use of the decryption key.
• Access control: rules and policies that limit access to confidential
information to those people and/or systems with a “need to know.”
This need to know may be determined by identity, such as a person’s
name or a computer’s serial number, or by a role that a person has,
such as being a manager or a computer security specialist.
• Authentication: the determination of the identity or role that some-
one has. This determination can be done in a number of different
ways, but it is usually based on a combination of something the
person has (like a smart card or a radio key fob storing secret keys),
something the person knows (like a password), and something the
person is (like a human with a fingerprint). The concept of authenti-
cation is schematically illustrated in Figure 2.
• Authorization: the determination if a person or system is allowed
access to resources, based on an access control policy. Such authoriza-
tions should prevent an attacker from tricking the system into letting
him have access to protected resources.

4
 Introduction

human with fingers password=ucIb()w1V

and eyes
y mother=Jones
pet=Caesar

Something you are

© 15524836/Shutterstock
Something you know
© Sebastian Kaulitzki/Shutterstock

radio token with

secret keys
Something you have
© Stephen VanHorn/Shutterstock

Figure 2: Three foundations for authentication.

• Physical security: the establishment of physical barriers to limit ac-

cess to protected computational resources. Such barriers include locks
on cabinets and doors, the placement of computers in windowless
rooms, the use of sound dampening materials, and even the construc-
tion of buildings or rooms with walls incorporating copper meshes
(called Faraday cages) so that electromagnetic signals cannot enter or
exit the enclosure.
When we visit a web page that asks for our credit card number and
our Internet browser shows a little lock icon in the corner, there is a lot
that has gone on in the background to help ensure the confidentiality of
our credit card number. In fact, a number of tools have probably been
brought to bear here. Our browser begins the process by performing an
authentication procedure to verify that the web site we are connecting to
is indeed who it says it is. While this is going on, the web site might
itself be checking that our browser is authentic and that we have the
appropriate authorizations to access this web page according to its access
control policy. Our browser then asks the web site for an encryption key to
encrypt our credit card, which it then uses so that it only sends our credit
card information in encrypted form. Finally, once our credit card number
reaches the server that is providing this web site, the data center where

5
 Introduction

the server is located should have appropriate levels of physical security,

access policies, and authorization and authentication mechanisms to keep
our credit card number safe. We discuss these topics in some detail in this
text.
There are a number of real demonstrated risks to physical eavesdropp-
ing. For example, researchers have shown that one can determine what
someone is typing just by listening to a recording of their key strokes. Like-
wise, experiments show that it is possible to reconstruct the image of a
computer screen either by monitoring its electromagnetic radiation or even
radiation or even from a video of a blank wall that the screen is shining on.
Thus, physical security is an information security concept that should not
be taken for granted.

Integrity

Another important aspect of information security is integrity, which is the

property that information has not be altered in an unauthorized way.
The importance of integrity is often demonstrated to school children in
the Telephone game. In this game, a group of children sit in a circle and the
person who is “it” whispers a message in the ear of his or her neighbor on
the right. Each child in the circle then waits to listen to the message from
his or her neighbor on the left. Once a child has received the message, he
or she then whispers this same message to their neighbor on the right. This
message passing process continues until the message goes full circle and
returns to the person who is “it.” At that point, the last person to hear the
message says the message out loud so that everyone can hear it. Typically,
the message has been so mangled by this point that it is a great joke to all the
children, and the game is repeated with a new person being “it.” And, with
each repeat play, the game reinforces that this whispering process rarely
ever preserves data integrity. Indeed, could this be one of the reasons we
often refer to rumors as being “whispered”?
There are a number of ways that data integrity can be compromised in
computer systems and networks, and these compromises can be benign or
malicious. For example, a benign compromise might come from a storage
device being hit with a stray cosmic ray that flips a bit in an important file,
or a disk drive might simply crash, completely destroying some of its files.
A malicious compromise might come from a computer virus that infects our
system and deliberately changes some the files of our operating system, so
that our computer then works to replicate the virus and send it to other
computers. Thus, it is important that computer systems provide tools to
support data integrity.

6
 Introduction

The previously mentioned tools for protecting the confidentiality of

information, denying access to data to users without appropriate access
rights, also help prevent data from being modified in the first place. In
addition, there are several tools specifically designed to support integrity,
including the following:
• Backups: the periodic archiving of data. This archiving is done
so that data files can be restored should they ever be altered in an
unauthorized or unintended way.

• Checksums: the computation of a function that maps the contents of a

file to a numerical value. A checksum function depends on the entire
contents of a file and is designed in a way that even a small change
to the input file (such as flipping a single bit) is highly likely to result
in a different output value. Checksums are like trip-wires—they are
used to detect when a breach to data integrity has occurred.

• Data correcting codes: methods for storing data in such a way that
small changes can be easily detected and automatically corrected.
These codes are typically applied to small units of storage (e.g., at the
byte level or memory word level), but there are also data-correcting
codes that can be applied to entire files as well.
These tools for achieving data integrity all possess a common trait—they
use redundancy. That is, they involve the replication of some information
content or functions of the data so that we can detect and sometimes even
correct breaches in data integrity.
In addition, we should stress that it is not just the content of a data
file that needs to be maintained with respect to integrity. We also need to
protect the metadata for each data file, which are attributes of the file or
information about access to the file that are not strictly a part of its content.
Examples of metadata include the user who is the owner of the file, the
last user who has modified the file, the last user who has read the file, the
dates and times when the file was created and last modified and accessed,
the name and location of the file in the file system, and the list of users or
groups who can read or write the file. Thus, changing any metadata of a
file should be considered a violation of its integrity.
For example, a computer intruder might not actually modify the content
of any user files in a system he has infiltrated, but he may nevertheless be
modifying metadata, such as access time stamps, by looking at our files
(and thereby compromising their confidentiality if they are not encrypted).
Indeed, if our system has integrity checks in place for this type of metadata,
it may be able to detect an intrusion that would have otherwise gone
unnoticed.

7
 Introduction

Availability

Besides confidentiality and integrity, another important property of infor-

mation security is availability, which is the property that information is
accessible and modifiable in a timely fashion by those authorized to do so.
Information that is locked in a cast-iron safe high on a Tibetan mountain
and guarded round the clock by a devoted army of ninjas may be con-
sidered safe, but it is not practically secure from an information security
perspective if it takes us weeks or months to reach it. Indeed, the quality of
some information is directly associated with how available it is.
For example, stock quotes are most useful when they are fresh. Also,
imagine the damage that could be caused if someone stole our credit card
and it took weeks before our credit card company could notify anyone,
because its list of stolen numbers was unavailable to merchants. Thus, as
with confidentiality and integrity, computer security researchers and sys-
tem designers have developed a number of tools for providing availability,
including the following:

• Physical protections: infrastructure meant to keep information avail-

able even in the event of physical challenges. Such protections can
include buildings housing critical computer systems to be constructed
to withstand storms, earthquakes, and bomb blasts, and outfitted
with generators and other electronic equipment to be able to cope
with power outages and surges.

• Computational redundancies: computers and storage devices that

serve as fallbacks in the case of failures. For example, redundant
arrays of inexpensive disks (RAID) use storage redundancies to keep
data available to their clients. Also, web servers are often organized
in multiples called “farms” so that the failure of any single computer
can be dealt with without degrading the availability of the web site.

Because availability is so important, an attacker who otherwise doesn’t

care about the confidentiality or integrity of data may choose to attack its
availability. For instance, a thief who steals lots of credit cards might wish
to attack the availability of the list of stolen credit cards that is maintained
and broadcast by a major credit card company. Thus, availability forms the
third leg of support for the vital C.I.A. triad of information security.

8
 Introduction

1.2 Assurance, Authenticity, and Anonymity

In addition to the classic C.I.A. concepts of confidentiality, integrity, and
availability, discussed in the previous section, there are a number of ad-
ditional concepts that are also important in modern computer security
applications. These concepts can likewise be characterized by a three-letter
acronym, A.A.A., which in this context refers to assurance, authenticity,
and anonymity. (See Figure 3.)

Authenticity © Melissa King/Shutterstock

Anonymity

© acequestions/Shutterstock
Assurance
© neelsky/Shutterstock

Figure 3: The A.A.A. concepts: assurance, authenticity, and anonymity.

Note that unlike the C.I.A. concepts, the A.A.A. concepts are independent
of each other.

Assurance

Assurance, in the context of computer security, refers to how trust is

provided and managed in computer systems. Admittedly, trust itself is
difficult to quantify, but we know it involves the degree to which we have
confidence that people or systems are behaving in the way we expect.

9
 Introduction

Furthermore, trust involves the interplay of the following:

• Policies specify behavioral expectations that people or systems have

for themselves and others. For example, the designers of an online
music system may specify policies that describe how users can access
and copy songs.
• Permissions describe the behaviors that are allowed by the agents that
interact with a person or system. For instance, an online music store
may provide permissions for limited access and copying to people
who have purchased certain songs.
• Protections describe mechanisms put in place to enforce permissions
and polices. Using our running example of an online music store,
we could imagine that such a system would build in protections to
prevent people from unauthorized access and copying of its songs.

Assurance doesn’t just go from systems to users, however. A user

providing her credit card number to an online music system may expect
the system to abide by its published policies regarding the use of credit card
numbers, she might grant permission to the system to make small charges
to her card for music purchases, and she may also have a protection system
in place with her credit card company so that she would not be liable for any
fraudulent charges on her card. Thus, with respect to computer systems,
assurance involves the management of trust in two directions—from users
to systems and from systems to users.
The designers of computer systems want to protect more than just the
confidentiality, integrity, and availability of information. They also want
to protect and manage the resources of these systems and they want to
make sure users don’t misuse these resources. Put in negative terms, they
want, for example, to keep unauthorized people from using their CPUs,
memory, and networks, even if no information is compromised in terms
of the C.I.A. framework. Thus, designers want assurance that the people
using the resources of their systems are doing so in line with their policies.
Likewise, managing information in a computer system can also go
beyond the C.I.A. framework, in that we may wish to manage the way that
information is used. For instance, if a user of an online movie rental system
has rented an electronic copy of a movie, we might want to allow that user
to watch it only a fixed number of times or we might want to insist that he
watch it within the next 30 days. Designers of music playing devices and
applications may likewise wish to allow users to make a few backup copies
of their music for personal use, but restrict copying so that they cannot
make hundreds of pirate CDs from their music files.

10
 Introduction

Thus, trust management deals with the design of effective, enforceable

policies, methods for granting permissions to trusted users, and the com-
ponents that can enforce those policies and permissions for protecting and
managing the resources in the system. The policies can be complicated, like
the contracts used in license agreements for movies, or they can be fairly
simple, like a policy that says that only the owner of a computer is allowed
to use its CPU. So it is best if a system designer comes up with policies that
are easy to enforce and permissions that are easy to comply with.
Another important part of system assurance involves software engi-
neering. The designers of a system need to know that the software that
implements their system is coded so that it conforms to their design. There
are, in fact, plenty of examples of systems that were designed correctly
“on paper,” but which worked incorrectly because those designs were not
implemented correctly.
A classic example of such an incorrect implementation involves the
use of pseudo-random number generators in security designs. A pseudo-
random number generator (PRNG) is a program that returns a sequence
of numbers that are statistically random, given a starting number, called
the seed, which is assumed to be random. The designer of a system
might specify that a PRNG be used in a certain context, like encryption, so
that each encryption will be different. But if the person actually writing
the program makes the mistake of always using the same seed for this
pseudo-random number generator, then the sequences of so-called pseudo-
random numbers will always be the same. Thus, the designers of secure
systems should not only have good designs, they should also have good
specifications and implementations.
Placing trust in a system is more problematic. Users typically don’t have
the same computational power as the servers employed by such systems.
So the trust that users place in a system has to come from the limited
amount of computing that they can do, as well as the legal and reputational
damage that the user can do to the company that owns the system if it fails
to live up to the user’s trust.
As mentioned above, when an Internet browser “locks the lock” to
indicate that communication with a web site is now secure, it is performing
a number of computational services on behalf of the user. It is encrypting
the session so that no outsiders can eavesdrop on the communication and,
if it is configured correctly, the browser has done some rudimentary checks
to make sure the web site is being run by the company that it claims is its
owner. So long as such knowledge can be enforced, then the user at least
has some recourse should she be cheated by the web site—she can take
evidence of this bad behavior to court or to a reputation opinion web site.

11
 Introduction

Authenticity

With so many online services providing content, resources, and even com-
putational services, there is a need for these systems to be able to enforce
their policies. Legally, this requires that we have an electronic way of
enforcing contracts. That is, when someone says that they are going to buy
a song from an online music store, there should be some way to enforce this
commitment. Likewise, when an online movie store commits to allowing a
user to rent a movie and watch it sometime in the following 30 days, there
should be some enforceable way for that user to know that the movie will
be available for that entire time.

Authenticity is the ability to determine that statements, policies, and

permissions issued by persons or systems are genuine. If such things can
be faked, there is no way to enforce the implied contracts that people and
systems engage in when buying and selling items online. Also, a person or
system could claim that they did not make such a commitment—they could
say that the commitment was made by someone pretending to be them.

Formally, we say that a protocol that achieves such types of authenticity

demonstrates nonrepudiation. Nonrepudiation is the property that authen-
tic statements issued by some person or system cannot be denied.

The chief way that the nonrepudiation property is accomplished is

through the use of digital signatures. These are cryptographic computa-
tions that allow a person or system to commit to the authenticity of their
documents in a unique way that achieves nonrepudiation. We give a more
formal definition of digital signatures in Section 3.2 but here it is sufficient
to know that a digital signature provides a computational analogue to real-
world, so-called blue-ink signatures.

In fact, digital signatures typically have some additional benefits over

blue-ink signatures, in that digital signatures also allow to check the in-
tegrity of signed documents. That is, if a document is modified, then the
signature on that document becomes invalid. An important requirement
of authenticity, therefore, is that we need to have reliable ways of elec-
tronically identifying people, which is a topic we discuss in Section 3 on
cryptographic primitives.

The concept we discuss next is instead on the necessary flip side of

creating systems that are so tied to personal identities, which is what is
required for digital signatures to make any sense.

12
 Introduction

Anonymity

When people interact with systems in ways that involve their real-world
identities, this interaction can have a number of positive benefits, as out-
lined above. There is an unfortunate side effect from using personal
identities in such electronic transactions, however. We end up spreading
our identity across a host of digital records, which ties our identity to
our medical history, purchase history, legal records, email communications,
employment records, etc. Therefore, we have a need for anonymity, which
is the property that certain records or transactions not to be attributable to
any individual.
If organizations need to publish data about their members or clients, we
should expect that they do so in a privacy-preserving fashion, using some
of the following tools:

• Aggregation: the combining of data from many individuals so that

disclosed sums or averages cannot be tied to any individual. For ex-
ample, the U.S. Census routinely publishes population breakdowns of
zip-code regions by ethnicity, salary, age, etc., but it only does so when
such disclosures would not expose details about any individual.

• Mixing: the intertwining of transactions, information, or communica-

tions in a way that cannot be traced to any individual. This technique
is somewhat technical, but it involves systems that can mix data
together in a quasi-random way so that transactions or searches can
still be performed, but without the release of any individual identity.

• Proxies: trusted agents that are willing to engage in actions for an

individual in a way that cannot be traced back to that person. For
example, Internet searching proxies are web sites that themselves
provide an Internet browser interface, so that individuals can visit
web sites that they might be blocked from, for instance, because of
the country they are located in.

• Pseudonyms: fictional identities that can fill in for real identities in

communications and transactions, but are otherwise known only to
a trusted entity. For example, many online social networking sites
allow users to interact with each other using pseudonyms, so that
they can communicate and create an online persona without revealing
their actual identity.
Anonymity should be a goal that is provided with safeguards whenever
possible and appropriate.

13
 Introduction

1.3 Threats and Attacks

Having discussed the various goals of computer security, we should now
mention some of the threats and attacks that can compromise these goals:
• Eavesdropping: the interception of information intended for someone
else during its transmission over a communication channel. Examples
include packet sniffers, which monitor nearby Internet traffic, such as
in a wireless access location. This is an attack on confidentiality.

• Alteration: unauthorized modification of information. Examples

of alteration attacks include the man-in-the-middle attack, where
a network stream is intercepted, modified, and retransmitted, and
computer viruses, which modify critical system files so as to perform
some malicious action and to replicate themselves. Alteration is an
attack on data integrity.

• Denial-of-service: the interruption or degradation of a data service or

information access. Examples include email spam, to the degree that
it is meant to simply fill up a mail queue and slow down an email
server. Denial of service is an attack on availability.

• Masquerading: the fabrication of information that is purported to

be from someone who is not actually the author. Examples of mas-
querading attacks include phishing, which creates a web site that
looks like a real bank or other e-commerce site, but is intended only
for gathering passwords, and spoofing, which may involve sending
on a network data packets that have false return addresses. Mas-
querading is an attack on authenticity, and, in the case of phishing,
an attempt to compromise confidentiality and/or anonymity.

• Repudiation: the denial of a commitment or data receipt. This in-

volves an attempt to back out of a contract or a protocol that requires
the different parties to provide receipts acknowledging that data has
been received. This is an attack on assurance.

• Correlation and traceback: the integration of multiple data sources

and information flows to determine the source of a particular data
stream or piece of information. This is an attack on anonymity.
There are other types of attacks as well, such as military-level attacks meant
to break cryptographic secrets. In addition, there are composite attacks,
which combine several of the above types of attacks into one. But those
listed above are among the most common types of attacks.

14
 Introduction

1.4 Security Principles

We conclude this section by presenting the ten security principles listed

in a classic 1975 paper by Saltzer and Schroeder. In spite of their age,
these principles remain important guidelines for securing today’s computer
systems and networks.

1. Economy of mechanism. This principle stresses simplicity in the

design and implementation of security measures. While applicable
to most engineering endeavors, the notion of simplicity is especially
important in the security domain, since a simple security framework
facilitates its understanding by developers and users and enables the
efficient development and verification of enforcement methods for it.
Economy of mechanism is thus closely related to implementation and
usability issues, which we touch on in Section 4.

2. Fail-safe defaults. This principle states that the default configuration

of a system should have a conservative protection scheme. For ex-
ample, when adding a new user to an operating system, the default
group of the user should have minimal access rights to files and
services. Unfortunately, operating systems and applications often
have default options that favor usability over security. This has been
historically the case for a number of popular applications, such as web
browsers that allow the execution of code downloaded from the web
server. Many popular access control models, such as those outlined
in Section 2, are based on the assumption of a fail-safe permission
default. Namely, if no access rights are explicitly specified for a
certain subject-object pair (s, o ) (e.g., an empty cell of an access control
matrix), then all types of access to object o are denied for subject s.

3. Complete mediation. The idea behind this principle is that every

access to a resource must be checked for compliance with a protection
scheme. As a consequence, one should be wary of performance im-
provement techniques that save the results of previous authorization
checks, since permissions can change over time. For example, an
online banking web site should require users to sign on again after
a certain amount of time, say, 15 minutes, has elapsed. File systems
vary in the way access checks are performed by an application. For
example, it can be risky if permissions are checked the first time a
program requests access to a file, but subsequent accesses to the same
file are not checked again while the application is still running.

15
 Introduction

4. Open design. According to this principle, the security architecture

and design of a system should be made publicly available. Security
should rely only on keeping cryptographic keys secret. Open design
allows for a system to be scrutinized by multiple parties, which leads
to the early discovery and correction of security vulnerabilities caused
by design errors. Making the implementation of the system available
for inspection, such as in open source software, allows for a more
detailed review of security features and a more direct process for
fixing software bugs. The open design principle is the opposite of the
approach known as security by obscurity, which tries to achieve secu-
rity by keeping cryptographic algorithms secret and which has been
historically used without success by several organizations. Note that
while it is straightforward to change a compromised cryptographic
key, it is usually infeasible to modify a system whose security has
been threatened by a leak of its design.

5. Separation of privilege. This principle dictates that multiple con-

ditions should be required to achieve access to restricted resources
or have a program perform some action. In the years since the
publishing of the Saltzer-Schroeder paper, the term has come to also
imply a separation of the components of a system, to limit the damage
caused by a security breach of any individual component.

6. Least privilege. Each program and user of a computer system should

operate with the bare minimum privileges necessary to function prop-
erly. If this principle is enforced, abuse of privileges is restricted, and
the damage caused by the compromise of a particular application or
user account is minimized. The military concept of need-to-know
information is an example of this principle. When this principle is
ignored, then extra damage is possible from security breaches. For
instance, malicious code injected by the attacker into a web server
application running with full administrator privileges can do sub-
stantial damage to the system. Instead, applying the least privilege
principle, the web server application should have the minimal set of
permissions that are needed for its operation.

7. Least common mechanism. In systems with multiple users, mecha-

nisms allowing resources to be shared by more than one user should
be minimized. For example, if a file or application needs to be
accessed by more than one user, then these users should have separate
channels by which to access these resources, to prevent unforeseen
consequences that could cause security problems.

16
 Introduction

8. Psychological acceptability. This principle states that user interfaces

should be well designed and intuitive, and all security-related set-
tings should adhere to what an ordinary user might expect. Differ-
ences in the behavior of a program and a user’s expectations may
cause security problems such as dangerous misconfigurations of soft-
ware, so this principle seeks to minimize these differences. Several
email applications incorporate cryptographic techniques (Section 3)
for encrypting and digitally signing email messages, but, despite
their broad applicability, such powerful cryptographic features are
rarely used in practice. One of the reasons for this state of affairs is
believed to be the clumsy and nonintuitive interfaces so far provided
by existing email applications for the use of cryptographic features.

9. Work factor. According to this principle, the cost of circumventing

a security mechanism should be compared with the resources of an
attacker when designing a security scheme. A system developed
to protect student grades in a university database, which may be
attacked by snoopers or students trying to change their grades, prob-
ably needs less sophisticated security measures than a system built to
protect military secrets, which may be attacked by government intelli-
gence organizations. Saltzer and Schroeder admit that the work factor
principle translates poorly to electronic systems, where it is difficult
to determine the amount of work required to compromise security.
In addition, technology advances so rapidly that intrusion techniques
considered infeasible at a certain time may become trivial to perform
within a few years. For example, as discussed in Section 4.2, brute-
force password cracking is becoming increasingly feasible to perform
on an inexpensive personal computer.

10. Compromise recording. Finally, this principle states that sometimes

it is more desirable to record the details of an intrusion than to
adopt more sophisticated measures to prevent it. Internet-connected
surveillance cameras are a typical example of an effective compromise
record system that can be deployed to protect a building in lieu of
reinforcing doors and windows. The servers in an office network may
maintain logs for all accesses to files, all emails sent and received,
and all web browsing sessions. Again, the compromise recording
principle does not hold as strongly on computer systems, since it may
be difficult to detect intrusion and adept attackers may be able to
remove their tracks on the compromised machine (e.g., by deleting
log entries).

17
 Introduction

The Ten Security Principles

These ten security principles are schematically illustrated in Figure 4. As

mentioned above, these principles have been born out time and again as
being fundamental for computer security. Moreover, as suggested by the
figure, these principles work in concert to protect computers and infor-
mation. For example, economy of mechanism naturally aids open design,
since a simple system is easier to understand and an open system publically
demonstrates security that comes from such a simple system.












 









 



































Figure 4: The ten security principles by Saltzer and Schroeder.

18
 Introduction

2 Access Control Models

One of the best ways to defend against attacks is to prevent them in the
first place. By providing for a rigorous means of determining who has
access to various pieces of information, we can often prevent attacks on
confidentiality, integrity, and anonymity. In this section, we discuss some
of the most popular means for managing access control.
All of the models assume that there are data managers, data owners,
or system administrators who are defining the access control specifications.
The intent is that these folks should be restricting access to those who have
a need to access and/or modify the information in question. That is, they
should be applying the principle of least privilege.

2.1 Access Control Matrices

A useful tool for determining access control rights is the access control
matrix, which is a table that defines permissions. Each row of this table
is associated with a subject, which is a user, group, or system that can
perform actions. Each column of the table is associated with an object,
which is a file, directory, document, device, resource, or any other entity
for which we want to define access rights. Each cell of the table is then
filled with the access rights for the associated combination of subject and
object. Access rights can include actions such as reading, writing, copying,
executing, deleting, and annotating. An empty cell means that no access
rights are granted. We show an example access control matrix for part of a
fictional file system and a set of users in Table 1.

/etc/passwd /usr/bin/ /u/roberto/ /admin/

root read, write read, write, exec read, write, exec read, write, exec
mike read read, exec
roberto read read, exec read, write, exec
backup read read, exec read, exec read, exec
··· ··· ··· ··· ···

Table 1: An example access control matrix. This table lists read, write, and
execution (exec) access rights for each of four fictional users with respect to
one file, /etc/passwd, and three directories.

19
 Introduction

Advantages
The nice thing about an access control matrix is that it allows for fast and
easy determination of the access control rights for any subject-object pair—
just go to the cell in the table for this subject’s row and this object’s column.
The set of access control rights for this subject-object pair is sitting right
there, and locating a record of interest can be done with a single operation
of looking up a cell in a matrix. In addition, the access control matrix
gives administrators a simple, visual way of seeing the entire set of access
control relationships all at once, and the degree of control is as specific as the
granularity of subject-object pairs. Thus, there are a number of advantages
to this access control model.

Disadvantages
There is a fairly big disadvantage to the access control matrix, however—it
can get really big. In particular, if we have n subjects and m objects, then the
access control matrix has n rows, m columns, and n · m cells. For example,
a reasonably sized computer server could easily have 1,000 subjects, who
are its users, and 1,000,000 objects, which are its files and directories. But
this would imply an access control matrix with 1 billion cells! It is hard
to imagine there is a system administrator anywhere on the planet with
enough time and patience to fill in all the cells for a table this large! Also,
nobody would be able to view this table all at once.
To overcome the lack of scalability of the access control matrix, com-
puter security researchers and system administrators have suggested a
number of alternatives to the access control matrix. We discuss three of
these models in the remaining part of this section. In particular, we discuss
access control lists, capabilities, and role-based access control. Each of these
models provides the same functionality as the access control matrix, but in
ways that reduce its complexity.

2.2 Access Control Lists

The access control list (ACL) model takes an object-centered approach.
It defines, for each object, o, a list, L, called o’s access control list, which
enumerates all the subjects that have access rights for o and, for each such
subject, s, gives the access rights that s has for object o.
Essentially, the ACL model takes each column of the access control
matrix and compresses it into a list by ignoring all the subject-object pairs
in that column that correspond to empty cells. (See Figure 5.)

20
 Introduction

/etc/passwd /usr/bin/ /u/roberto/ /admin/

root: r,w root: r,w,x root: r,w,x root: r,w,x

mike: r mike: r,x roberto: r,w,x backup: r,x
roberto: r roberto: r,x backup: r,x
backup: r backup: r,x

Figure 5: The access control lists (ACLs) corresponding to the access

control matrix of Table 1. We use the shorthand notation of r= read,
w=write, and x=execute.

Advantages
The main advantage of ACLs over access control matrices is size. The total
size of all the access control lists in a system will be proportional to the
number of nonempty cells in the access control matrix, which is expected to
be much smaller than the total number of cells in the access control matrix.
Another advantage of ACLs, with respect to secure computer systems,
is that the ACL for an object can be stored directly with that object as part
of its metadata, which is particularly useful for file systems. That is, the
header blocks for files and directories can directly store the access control
list of that file or directory. Thus, if the operating system is trying to decide
if a user or process requesting access to a certain directory or file in fact has
that access right, the system need only consult the ACL of that object.

Disadvantages
The primary disadvantage of ACLs, however, is that they don’t provide an
efficient way to enumerate all the access rights of a given subject. In order to
determine all the access rights for a given subject, s, a secure system based
on ACLs would have to search the access control list of every object looking
for records involving s. That is, determining such information requires
a complete search of all the ACLs in the system, whereas the similar
computation with an access control matrix simply involves examining the
row for subject s.
Unfortunately, this computation is sometimes necessary. For example, if
a subject is to be removed from a system, the administrator needs to remove
his or her access rights from every ACL they are in. But if there is no way
to know all the access rights for a given subject, the administrator has no
choice but to search all the ACLs to find any that contain that subject.

21
 Introduction

2.3 Capabilities
Another approach, known as capabilities, takes a subject-centered ap-
proach to access control. It defines, for each subject s, the list of the objects
for which s has nonempty access control rights, together with the specific
rights for each such object. Thus, it is essentially a list of cells for each row
in the access control matrix, compressed to remove any empty cells. (See
Figure 6.)

/etc/passwd: r,w,x; /usr/bin: r,w,x;

root
/u/roberto: r,w,x; /admin/: r,w,x

mike /usr/passwd: r; /usr/bin: r,x

/usr/passwd: r; /usr/bin: r;
roberto
/u/roberto: r,w,x

/etc/passwd: r,x; /usr/bin: r,x;

backup
/u/roberto: r,x; /admin/: r,x

Figure 6: The capabilities corresponding to the access control matrix of Ta-

ble 1. We use the shorthand notation of r=read, w=write, and x=execute.

Advantages

The capabilities access control model has the same advantage in space over
the access control matrix as the access control list model has. Namely,
a system administrator only needs to create and maintain access control
relationships for subject-object pairs that have nonempty access control
rights. In addition, the capabilities model makes it easy for an administrator
to quickly determine for any subject all the access rights that that subject
has. Indeed, all she needs to do is read off the capabilities list for that
subject. Likewise, each time a subject s requests a particular access right
for an object o, the system needs only to examine the complete capabilities
list for s looking for o. If s has that right for o, then it is granted it. Thus, if
the size of the capabilities list for a subject is not too big, this is a reasonably
fast computation.

22
 Introduction

Disadvantages
The main disadvantage of capabilities is that they are not associated directly
with objects. Thus, the only way to determine all the access rights for an
object o is to search all the capabilities lists for all the subjects. With the
access control matrix, such a computation would simply involve searching
the column associated with object o.

2.4 Role-Based Access Control

Independent of the specific data structure that represents access control
rights, is another approach to access control, which can be used with any
of the structures described above. In role-based access control (RBAC),
administrators define roles and then specify access control rights for these
roles, rather than for subjects directly.
So, for example, a file system for a university computer science depart-
ment could have roles for “faculty,” “student,” “administrative personnel,”
“administrative manager,” “backup agent,” “lab manager,” “system ad-
ministrator,” etc. Each role is granted the access rights that are appropriate
for the class of users associated with that role. For instance, a backup agent
should have read and execute access for every object in the file system, but
write access only to the backup directory.
Once roles are defined and access rights are assigned to role-object pairs,
subjects are assigned to various roles. The access rights for any subject are
the union of the access rights for the roles that they have. For example,
a student who is working part time as a system administrator’s assistant
to perform backups on a departmental file system would have the roles
“student” and “backup agent,” and she would have the union of rights
that are conferred to these two roles. Likewise, a professor with the roles
“faculty” and“lab manager” would get all the access rights in the union
of these roles. The professor who serves as department chair would have
in addition other roles, including “administrative manager” and “system
administrator.”

Role Hierarchies
In addition, a hierarchy can be defined over roles so that access rights
propagate up the hierarchy. Namely, if a role R1 is above role R2 in the
hierarchy, then R1 inherits the access rights of R2 . That is, the access
rights of R1 include those of R2 . For example, in the role hierarchy for a
computer science department, role “system administrator,” would be above

23
 Introduction

role “backup agent” and role “administrative manager,” would be above

role “administrative personnel.”
Hierarchies of roles simplify the definition and management of permis-
sions thanks to the inheritance property. Thy are the main feature that
distinguishes roles from groups of users. An example of hierarchy of roles
for a computer science department is shown in Figure 7.

Department
Chair

Administrative Lab System Undergraduate Graduate

Manager Manager Administrator TA TA

Lab Backup Undergraduate Graduate

Accountant Secretary
Technician Agent Student Student

Administrative Technical
Faculty Student
Personnel Personnel

Department
Member

Figure 7: Example of hierarchy of roles for a computer science department.

Advantages and Disadvantages

The advantage of role-based access control is that, no matter which access

control framework is being used to store access control rights, the total
number of rules to keep track of is reduced. That is, the total set of roles
should be much smaller than the set of subjects; hence, storing access rights
just for roles is more efficient. And the overhead for determining if a subject
s has a particular right is small, for all the system needs to do is to determine
if one of the roles for s has that access right.
The main disadvantage of the role-based access control model is that it
is not implemented in current operating systems.

24
 Introduction

3 Cryptographic Concepts
Computer security policies are worthless if we don’t have ways of enforc-
ing them. Laws and economics can play an important role in deterring
attacks and encouraging compliance, respectively. However, technological
solutions are the primary mechanism for enforcing security policies and
achieving security goals.
That’s were cryptography comes in. We can use cryptographic tech-
niques to achieve a broad range of security goals, including some that at
first might even seem to be impossible. In this section, we give an overview
of several fundamental cryptographic concepts.

3.1 Encryption
Traditionally, encryption is described as a means to allow two parties,
customarily called Alice and Bob, to establish confidential communication
over an insecure channel that is subject to eavesdropping. It has grown to
have other uses and applications than this simple scenario, but let us nev-
ertheless start with the scenario of Alice and Bob wanting to communicate
in a confidential manner, as this gives us a foundation upon which we can
build extensions later.
Suppose, then, that Alice has a message, M, that she wishes to commu-
nicate confidentially to Bob. The message M is called the plaintext, and it
is not to be transmitted in this form as it can be observed by other parties
while in transit. Instead, Alice will convert plaintext M to an encrypted
form using an encryption algorithm E that outputs a ciphertext C for M.
This encryption process is denoted by

C = E ( M ).

Ciphertext C will be what is actually transmitted to Bob. Once Bob has

received C, he applies a decryption algorithm D to recover the original
plaintext M from ciphertext C. This decryption process is denoted

M = D ( C ).

The encryption and decryption algorithms are chosen so that it is infeasible

for someone other than Alice and Bob to determine plaintext M from ci-
phertext C. Thus, ciphertext C can be transmitted over an insecure channel
that can be eavesdropped by an adversary.

25
 Introduction

Cryptosystems
The decryption algorithm must use some secret information known to Bob,
and possibly also to Alice, but no other party. This is typically accomplished
by having the decryption algorithm use as an auxiliary input a secret num-
ber or string called decryption key. In this way, the decryption algorithm
itself can be implemented by standard, publicly available software and
only the decryption key needs to remain secret. Similarly, the encryption
algorithm uses as auxiliary input an encryption key, which is associated
with the decryption key. Unless it is infeasible to derive the decryption key
from the encryption key, the encryption key should be kept secret as well.
That is encryption in a nutshell.
But before Alice and Bob even start performing this encrypted com-
munication, they need to agree on the ground rules they will be using.
Specifically, a cryptosystem consists of seven components:
1. The set of possible plaintexts

2. The set of possible ciphertexts

3. The set of encryption keys

4. The set of decryption keys

5. The correspondence between encryption keys and decryption keys

6. The encryption algorithm to use

7. The decryption algorithm to use

Let c be a character of the classical Latin alphabet (which consists of 23
characters) and k be an integer in the range [−22, +22]. We denote with
s(c, k ) the circular shift by k of character c in the Latin alphabet. The shift
is forward when k > 0 and backward for k < 0. For example, s( D, 3) = G,
s( R, −2) = P, s( Z, 2) = B, and s(C, −3) = Z. In the Caesar cipher, the set of
plaintexts and the set of ciphertexts are the strings consisting of characters
from the Latin alphabet. The set of encryption keys is {3}, that is, the set
consisting of number 3. The set of decryption keys is {−3}, that is, the set
consisting of number −3. The encryption algorithm consists of replacing
each character x in the plaintext with s( x, e), where e = 3 is the encryption
key. The decryption algorithm consists of replacing each character x in
the plaintext with s( x, d), where d = −3 is the decryption key. Note the
encryption algorithm is the same as the decryption algorithm and that the
encryption and decryption keys are one the opposite of the other.

26
 Introduction

Modern Cryptosystems

Modern cryptosystems are much more complicated than the Caesar cipher,
and much harder to break. For example, the Advanced Encryption Stan-
dard (AES) algorithm, uses keys that are 128, 196, or 256 bits in length, so
that it is practically infeasible for an eavesdropper, Eve, to try all possible
keys in a brute-force attempt to discover the corresponding plaintext from
a given ciphertext. Likewise, the AES algorithm is much more convoluted
than a simple cyclic shift of characters in the alphabet, so we are not going
to review the details here.

Symmetric Encryption

One important property of the AES algorithm that we do note here, how-
ever, is that the same key K is used for both encryption and decryption.
Such schemes as this, which use the same key for encryption and de-
cryption, are called symmetric cryptosystems or shared-key cryptosystems,
since Alice and Bob have to both share the key K in order for them to
communicate a confidential message, M. A symmetric cryptosystem is
schematically illustrated in Figure 8.

Communication
Sender Recipient
channel

encrypt decrypt

ciphertext plaintext

plaintext
shared
h d shared
h d
secret secret
key key
Attacker
(eavesdropping)

Figure 8: A symmetric cryptosystem, where the same secret key, shared

by the sender and recipient, is used to encrypt and decrypt. An attacker
who eavesdrops the communication channel cannot decrypt the ciphertext
(encrypted message) without knowing the key.

27
 Introduction

Symmetric Key Distribution

Symmetric cryptosystems, including the AES algorithm, tend to run fast,
but they require some way of getting the key K to both Alice and Bob
without an eavesdropper, Eve, from discovering it. Also, suppose that n
parties wish to exchange encrypted messages with each other in such a
way that each message can be seen only by the sender and recipient. Using
a symmetric cryptosystem, a distinct secret key is needed for each pair of
parties, for a total of n(n − 1)/2 keys, as illustrated in Figure 9.

shared
secret

shared
secret
shared shared shared
secret secret secret

n (n−1)/2
keys

shared
secret

Figure 9: Pairwise confidential communication among n users with a

symmetric cryptosystem requires n(n − 1)/2 distinct keys, each shared by
two users and kept secret from the other users. (key) © Igor Nazarenko/
Shutterstock ; (avatars) © Moneca/Shutterstock

Public-Key Encryption
An alternative approach to symmetric cryptosystems is the concept of a
public-key cryptosystem. In such a cryptosystem, Bob has two keys: a
private key, SB , which Bob keeps secret, and a public key, PB , which Bob
broadcasts widely, possibly even posting it on his web page. In order
for Alice to send an encrypted message to Bob, she need only obtain his
public key, PB , use that to encrypt her message, M, and send the result,
C = EPB ( M), to Bob. Bob then uses his secret key to decrypt the message as
M = DS B ( C ) .
A public-key cryptosystem is schematically illustrated in Figure 10.

28
 Introduction

Communication
Sender Recipient
channel

encrypt decrypt

plaintext ciphertext plaintext

plaintext
public
bli private
i t
key key

Attacker
((eavesdropping)
g)

Figure 10: In a public-key cryptosystem, the sender uses the public key of
the recipient to encrypt and the recipient uses its private key to decrypt.
An attacker who eavesdrops the communication channel cannot decrypt
the ciphertext (encrypted message) without knowing the private key.
© Igor Nazarenko/Shutterstock

The advantage of public-key cryptosystems is that they sidestep the

problem of getting a single shared key to both Alice and Bob. Also, only pri-
vate keys need to be kept secret, while public keys can be shared with any-
one, including the attacker. Finally, public-key cryptosystems support ef-
ficient pairwise confidential communication among n users. Namely, only
n distinct private/public key pairs are needed, as illustrated in Figure 11.
This fact represents a significant improvement over the quadratic number
of distinct keys required by a symmetric cryptosystem. For example, if we
have 1, 000 users, a public-key cryptosystem uses 1, 000 private/public key
pairs while a symmetric cryptosystem requires 499, 500 secret keys.

private
p private

public public

n key pairs
public
p public
p

private
p private

Figure 11: Pairwise confidential communication among n users with a

public-key cryptosystem requires n key pairs, one per user. (key) © Igor
Nazarenko/Shutterstock; (avatars) © Moneca/Shutterstock

29
 Introduction

Some Disadvantages of Public-Key Cryptography

The main disadvantage of public-key cryptosystems is that in all of the

existing realizations, such as the RSA and ElGamal cryptosystems, the
encryption and decryption algorithms are much slower than the those for
existing symmetric encryption schemes. In fact, the difference in running
time between existing public-key crytosystems and symmetric cryptosys-
tems disourages people for using public-key cryptography for interactive
sessions that use a lot of back-and-forth communication.
Also, public-key cryptosystems require in practice a key length that is
one order of magnitude larger than that for symmetric cryptosystems. For
example, RSA is commonly used with 2, 048-bit keys while AES is typically
used with 256-bit keys.
In order to work around these disadvantages, public-key cryptosystems
are often used in practice just to allow Alice and Bob to exchange a shared
secret key, which they subsequently use for communicating with a symmet-
ric encryption scheme, as shown in Figure 12.

Communication
Sender Recipient
channel
encryptt d
decrypt
t
secret secret
k
key ciphertext
key

public key private key

shared
h d shared
h d
secret key Attacker secret key
(eavesdropping)

encrypt decrypt

plaintext ciphertext plaintext

Figure 12: Use of a public-key cryptosystem to exchange a shared secret

key, which is subsequently employed for communicating with a symmetric
encryption scheme. The secret key is the “plaintext” message sent from the
sender to the recipient. © Igor Nazarenko/Shutterstock

30
 Introduction

3.2 Digital Signatures

Another problem that is solved by public-key cryptosystems is the con-
struction of digital signatures. This solution is derived from the fact that in
typical public-key encryption schemes, we can reverse the order in which
the encryption and decryption algorithms are applied:

EPB ( DSB ( M )) = M.

That is, Bob can give as input to the decryption algorithm a message, M,
and his private key, SB . Applying the encryption algorithm to the resulting
output and Bob’s public key, which can be done by anyone, yields back
message M.

Using a Private Key for a Digital Signature

This might at first seem futile, for Bob is creating an object that anyone can
convert to message M, that is, anyone who knows his public key. But that
is exactly the point of a digital signature—only Bob could have done such
a decryption. No one else knows his secret key. So if Bob intends to prove
that he is the author of message M, he computes his personal decryption of
it as follows:

S = DS B ( M ) .

This decryption S serves as a digital signature for message M. Bob

sends signature S to Alice along with message M. Alice can recover M
by encrypting signature S with Bob’s public key:

M = EPB (S).

In this way, Alice is assured that message M is authored by Bob and not
by any other user. Indeed, no one but Bob, who has private key SB , could
have produced such an object S, so that EPB (S) = M.
The only disadvantage of this approach is that Bob’s signature will
be at least as long as the plaintext message he is signing, so this exact
approach is not used in practice.

31
 Introduction

3.3 Simple Attacks on Cryptosystems

Consider a cryptosystem for n-bit plaintexts. In order to guarantee unique
decryption, ciphertexts should have at least n bits or otherwise two or more
plaintexts would map to the same ciphertext. In cryptosystems used in
practice, plaintexts and ciphertexts have the same length. Thus, for a given
symmetric key (or private-public key pair), the encryption and decryption
algorithms define a matching among n-bit strings. That is, each plaintext
corresponds to a unique ciphertext, and vice versa.

Man-in-the-Middle Attacks

The straightforward use of a cryptosystem presented in Section 3.1, which

consists of simply transmitting the ciphertext, assures confidentiality. How-
ever, it does not guarantee the authenticity and integrity of the message if
the adversary can intercept and modify the ciphertext. Suppose that Alice
sends to Bob ciphertext C corresponding to a message M. The adversary
modifies C into an altered ciphertext C 0 received by Bob. When Bob
decrypts C 0 , he obtains a message M0 that is different from M. Thus, Bob is
led to believe that Alice sent him message M0 instead of M. This man-in-
the-middle attack is illustrated in Figure 13.

Communication
Sender Recipient
channel

encryptt d
decrypt
t

plaintext M plaintext M′

shared shared
secret ciphertext C ciphertext C′ secret
k
key k
key

Attacker
(intercepting)

Figure 13: A man-in-the-middle attack where the adversary modifies the

ciphertext and the recipient decrypts the altered ciphertext into an incorrect
message. © Igor Nazarenko/Shutterstock

32
 Introduction

Similarly, consider the straightforward use of digital signatures pre-

sented in Section 3.2. The attacker can modify the signature S created by
Bob into a different string S0 and send to Alice signature S0 together with the
encryption M0 of S0 using Bob’s public key. Note that M0 will be different
from the original message M. When Alice verifies the digital signature S0 ,
she obtains message M0 by encrypting S0 . Thus, Alice is led to believe that
Bob has signed M0 instead of M.
Note that in the above attacks the adversary can arbitrarily alter the
transmitted ciphertext or signature. However, the adversary cannot choose,
or even figure out, what would be the resulting plaintext since he does not
have the ability to decrypt. Thus, the above attacks are effective only if
any arbitrary sequence of bits is a possible message. This scenario occurs,
for example, when a randomly generated symmetric key is transmitted
encrypted with a public-key cryptosystem.

Brute-Force Decryption Attack

Now, suppose instead that valid messages are English text of up to t
characters. With the standard 8-bit ASCII encoding, a message is a binary
string of length n = 8t. However, valid messages constitute a very small
subset of all the possible n-bit strings, as illustrated in Figure 14.

English Ciphertext of
text English text

Plaintexts Ciphertexts
n-bit strings n-bit strings

Figure 14: Natural-language plaintexts are a very small fraction of the set
of possible plaintexts. This fraction tends to zero as the plaintext length
grows. Thus, for a given key, it is hard for an adversary to guess a ciphertext
that corresponds to a valid message.

33
 Introduction

Assume that we represent characters with the standard 8-bit ASCII

encoding and let n = 8 the number of bits in a t-byte array. We have that the
total number of possible t-byte arrays is (28 )t = 2n . However, it is estimated
that each character of English text carries about 1.25 bits of information, i.e.,
the number of t-byte arrays that correspond to English text is
 t
21.25 = 21.25t .

So, in terms of the bit length n, the number of n-bit arrays corresponding to
English text is approximately 20.16n .
More generally, for a natural language that uses an alphabet instead of
ideograms, there is a constant α, with 0 < α < 1, such that there are 2αn texts
among all n-bit arrays. The constant α depends on the specific language and
character-encoding scheme used. As a consequence, in a natural language
the fraction of valid messages out of all possible n-bit plaintexts is about
2αn 1
n
= (1− α ) n .
2 2
Thus, the fraction of valid messages tends rapidly to zero as n grows.
Note that this fraction represents the probability that a randomly selected
plaintext corresponds to meaningful text.
The above property of natural languages implies that it is infeasible for
an adversary to guess a ciphertext that will decrypt to a valid message or
to guess a signature that will encrypt to a valid message.
The previously mentioned property of natural languages has also im-
portant implications for brute-force decryption attacks, where an adversary
tries all possible decryption keys and aims at determining which of the
resulting plaintexts is the correct one. Clearly, if the plaintext is an arbitrary
binary string, this attack cannot succeed, as there is no way for the attacker
to distinguish a valid message. However, if the plaintext is known to be text
in a natural language, then the adversary hopes that only a small subset of
the decryption results (ideally just a single plaintext) will be a meaningful
text for the language. Some knowledge about the possible message being
sent will then help the attacker pinpoint the correct plaintext.
We know that for some constant α > 1, there are 2αn valid text messages
among the 2n possible plaintexts. Let k be the length (number of bits) of the
decryption key. For a given ciphertext, there are 2k possible plaintexts, each
corresponding to a key. From the previous discussion, each such plaintext
is a valid text message with probability 2(1−1 α)n . Hence, the expected number
of plaintexts corresponding to valid text messages is

2k
.
2(1− α ) n

34
 Introduction

As the key length k is fixed, the above number tends rapidly to zero as
the ciphertext length n grows. Also, we expect that there is a unique valid
plaintext for the given ciphertext when
k
n= .
1−α
The above threshold value for n is called the unicity distance for the given
language and key length. For the English language and the 256-bit AES
cryptosystem, the unicity distance is about 304 bits or 38 ASCII-encoded
characters. This is only half a line of text.
From the above discussion, we conclude that brute-force decryption is
likely to succeed for messages in natural language that are not too short.
Namely, when a key yields a plaintext that is a meaningful text, the attacker
has probably recovered the original message.

3.4 Cryptographic Hash Functions

To reduce the size of the message that Bob has to sign, we often use
cryptographic hash functions, which are checksums on messages that have
some additional useful properties. One of the most important of these
additional properties is that the function be one-way, which means that
it is easy to compute but hard to invert. That is, given M, it should be
relatively easy to compute the hash value, h( M ). But given only a value y,
it should be difficult to compute a message M such that y = h( M). Modern
cryptographic hash functions, such as SHA-256, are believed to be one-way
functions, and result in values that are only 256 bits long.

Applications to Digital Signatures and File System Integrity

Given a cryptographic hash function, we can reduce the time and space
needed for Bob to perform a digital signature by first having him hash the
message M to produce h( M ) and then have him sign this value, which
is sometimes called the digest of M. That is, Bob compute the following
signature:
S = ESB (h( M )).
Now to verify signature S on a message M, Alice computes h( M), which is
easy, and then checks that
DPB (S) = h( M ).
Signing a cryptographic digest of the message not only is more efficient
than signing the message itself, but also defends against the man-in-the-
middle attack described in Section 3.3. Namely, thanks to the one-way

35
 Introduction

property of the cryptographic hash function h, it is no longer possible for

the attacker to forge a message-signature pair without knowledge of the
private key. The encryption of the forged signature S0 now yields a digest
y0 for which the attacker needs to find a corresponding message M0 such
that y0 = h( M0 ). This computation is unfeasible because h is one-way.
In addition, cryptographic hash functions also have another property
that is useful in the context of digital signatures—they are collision resis-
tant—which implies that, given M, it is difficult to find a different message,
M0 , such that h( M) = h( M0 ). This property makes the forger’s job even
more difficult, for not only it is hard for him to fake Bob’s signature on any
message, it is also hard for him, given a message M and its signature S
created by Bob, to find another message, M0 , such that S is also a signature
for M0 .
Another application of cryptographic hash functions in secure com-
puter systems is that they can be used to protect the integrity of critical files
in an operating system. If we store the cryptographic hash value of each
such file in protected memory, we can check the authenticity of any such file
just by computing its cryptographic hash and comparing that value with
the one stored in secure memory. Since such hash functions are collision
resistant, we can be confident that if the two values match it is highly likely
that the file has not been tampered with. In general, hash functions have
applications any time we need a compact digest of information that is hard
to forge.

Message Authentication Codes

A cryptographic hash function h can be used in conjunction with a secret
key shared by two parties to provide integrity protection to messages
exchanged over an insecure channel, as illustrated in Figure 15. Suppose
Alice and Bob share a secret key K. When Alice wants to send a message
M to Bob, she computes the hash value of the key K concatenated with
message M:
A = h(K || M ).
This value A is called a message authentication code (MAC). Alice then
sends the pair ( M, A) to Bob. Since the communication channel is insecure,
we denote with ( M0 , A0 ) the pair received by Bob. Since Bob knows the
secret K, he computes the authentication code for the received message M
himself:
A00 = h(K || M0 ).
If this computed MAC A00 is equal to the received MAC A0 , then Bob is
assured that M0 is the message sent by Alice, i.e., A00 = A0 implies M0 = M.

36
 Introduction

Communication
Co u cat o
channel

(attack detected)
h 6B34339 4C66809 4C66809 =? 87F9024 h
message M MAC MAC received computed
MAC MAC message M’

shared shared
secret secret
key key
Sender Attacker Recipient
(modifying)

Figure 15: Using a message authentication code to verify the integrity of a

message. © Igor Nazarenko/Shutterstock

Consider an attacker who alters the message and MAC while in transit.
Since the hash function is one-way, it is infeasible for the attacker to recover
the key k from the MAC A = h(K || M) and the message M sent by Alice.
Thus, the attacker cannot modify the message and compute a correct MAC
A0 for the modified message M0 .

3.5 Digital Certificates

As illustrated in Figure 12, public-key cryptography solves the problem
of how to get Alice and Bob to share a common secret key. That is, Alice
can simply encrypt secret key K using Bob’s public key, PB , and send the
ciphertext to him. But this solution has a flaw: How does Alice know that
the public key, PB , that she used is really the public key for Bob? And if
there are lots of Bobs, how can she be sure she used the public key for the
right one?
Fortunately, there is a fix to this flaw. If there is a trusted authority who
is good at determining the true identities of people, then that authority can
digitally sign a statement that combines each person’s identity with their
public key. That is, this trusted authority could sign a statement like the
following:
“The Bob who lives on 11 Main Street in Gotham
City was born on August 4, 1981, and has email address
[email protected], has the public key PB , and I stand by this
certification until December 31, 2011.”

37
 Introduction

Such a statement is called a digital certificate so long as it combines

a public key with identifying information about the subject who has that
public key. The trusted authority who issues such a certificate is called a
certificate authority (CA).
Now, rather than simply trusting on blind faith that PB is the public key
for the Bob she wants to communicate with, Alice needs only to trust the
certificate authority. In addition, Alice needs to know the public key for
the CA, since she will use that to verify the CA’s signature on the digital
certificate for Bob. But there are likely to be only a small number of CAs, so
knowing all their public keys is a reasonable assumption. In practice, the
public keys of commonly accepted CAs come with the operating system.
Since the digital certificate is strong evidence of the authenticity of Bob’s
public key, Alice can trust it even if it comes from an unsigned email
message or is posted on a third-party web site.
For example, the digital certificate for a web site typically includes the
following information:
• Name of the certification authority (e.g., Thawte).

• Date of issuance of the certificate (e.g., 1/1/2009).

• Expiration date of the certificate (e.g., 12/31/2011).

• Address of the website (e.g., mail.google.com).

• Name of the organization operating the web site (e.g., “Google, Inc.”).

• Public key used of the web server (e.g., an RSA 1, 024-bit key).

• Name of the cryptographic hash function used (e.g., SHA-256).

• Digital signature.
In fact, when an Internet browser “locks the lock” at a secure web
site, it is doing so based on a key exchange that starts with the browser
downloading the digital certificate for this web server, matching its name
to a public key. Thus, one approach to defend against a phishing attack for
encrypted web sites is to check that the digital certificate contains the name
of the organization associated with the website.
There are a number of other cryptographic concepts, including such
things a zero-knowledge proofs, secret sharing schemes, and broadcast
encryption methods, but the topics covered above are the most common
cryptographic concepts used in computer security applications.

38
 Introduction

4 Implementation and Usability Issues

In order for computer security solutions to be effective, they have to be

implemented correctly and used correctly. Thus, when computer security
solutions are being developed, designers should keep both the program-
mers and users in mind.

4.1 Efficiency and Usability

Computer security solutions should be efficient, since users don’t like
systems that are slow. This rule is the prime justification, for example, for
why a public-key cryptosystem is often used for a one-time exchange of a
secret key that is then used for communication with a symmetric encryption
scheme.

An Example Scenario Involving Usability and Access Control

Efficiency and ease of use are also important in the context of access control.
Many systems allow only administrators to make changes to the files that
define access control rights, roles, or entities. So, for example, it is not
possible in some operating systems, including several Linux versions, for
users to define the access control rights for their own files beyond coarse-
grained categories such as “everyone” and “people in my group.” Because
of this limitation, it is actually a cumbersome task to define a new work
group and give access rights to that group. So, rather than going through
the trouble of asking an administrator to create a new group, a user may just
give full access rights to everyone, thus compromising data confidentiality
and integrity.
For example, suppose a group of students decides to work on a software
project together for a big schoolwide contest. They are probably going
to elect a project leader and have her create a subdirectory of her home
directory for all the project code to reside. Ideally, it should be easy for the
leader to define the access control for this directory and allow her partners
to have access to it, but no one else. Such control is often not possible
without submitting a request to an overworked system administrator, who
may or may not respond to such requests from students. So, what should
the project leader do?

39
 Introduction

Possible Solutions

One solution is to have the leader maintain the reference version of the code
in the project directory and require the team members to email her all their
code updates. On receipt of an update from a team member, the leader
would then perform the code revisions herself on the reference version of
the code and would distribute the modified files to the rest of the team.
This solution provides a reasonable level of security, as it is difficult (though
not impossible) to intercept email messages. However, the solution is very
inefficient, as it implies a lot of work for the leader who would probably
regret being selected for this role.
Another possibility is for the project leader to take an easy way out by
hiding the project directory somewhere deep in her home directory, making
that directory be accessible by all the users in the system, and hoping
that none of the competing teams will discover this unprotected directory.
This approach is, in fact, an example of security by obscurity, which is
the approach of deriving security from a fact that is not generally known
rather than employing sound computer security principles (as discussed in
Sections 1.1 and 1.2). History has taught us again and again, however, that
security by obscurity fails miserably. Thus, the leader of our software team
is forced into choosing between the lesser of two evils, rather than being
given the tools to build a secure solution to her problem.
Users should clearly not have to make such choices between security
and efficiency, of course. But this requirement implies that system designers
need to anticipate how their security decisions will impact users. If doing
the safe thing is too hard, users are going to find a workaround that is easy
but probably not very secure.
Let us now revisit our example of the school programming team. The
most recent versions of Linux and Microsoft Windows allow the owner of
a folder to directly define an access control list for it (see Section 2.2),
without administrator intervention. Also, by default such permissions are
automatically applied to all the files and subfolders created within the
folder. Thus, our project leader could simply add an access control list
to the project folder that specifies read, write, and execute rights for each
of the team members. Team members can now securely share the project
folder without the risk of snooping by competing teams. Also, the project
leader needs to create this access control list only once, for the project folder.
Any newly added files and subfolders will automatically inherit this access
control list. This solution is both efficient and easy to use.

40
 Introduction

4.2 Passwords
One of the most common means for authenticating people in computer sys-
tems is through the use of usernames and passwords. Even systems based
on cryptographic keys, physical tokens, and biometrics often augment the
security of these techniques with passwords. For example, the secret key
used in a symmetric cryptosystem may be stored on the hard drive in
encrypted form, where the decryption key is derived from a password. In
order for an application to use the secret key, the user will have to enter
her password for the key. Thus, a critical and recurring issue in computer
security circles is password security.
Ideally, passwords should be easy to remember and hard to guess. Un-
fortunately, these two goals are in conflict with each other. Passwords that
are easy to remember are things like English words, pet names, birthdays,
anniversaries, and last names. Passwords that are hard to guess are random
sequences of characters that come from a large alphabet, such as all the
possible characters that can be typed on a keyboard, including lowercase
and uppercase letters, numbers, and symbols. In addition, the longer a
password is used the more it is at risk. Thus, some system administrators
require that users frequently change their passwords, which makes them
even more difficult to remember.

Dictionary Attack
The problem with the typical easy-to-remember password is that it belongs
to a small set of possibilities. Moreover, computer attackers know all these
passwords and have built dictionaries of them. For example, for the English
language, there are less than 50,000 common words, 1,000 common human
first names, 1,000 typical pet names, and 10,000 common last names. In
addition, there are only 36,525 birthdays and anniversaries for almost all
living humans on the planet, that is, everyone who is 100 years old or
younger. So an attacker can compile a dictionary of all these common
passwords and have a file that has fewer than 100,000 entries.
Armed with this dictionary of common passwords, one can perform an
attack that is called, for obvious reasons, a dictionary attack. If an attcker
can try the words in his dictionary at the full speed of a modern computer,
he can attack a password-protected object and break its protections in just
a few minutes. Specifically, if a computer can test one password every
millisecond, which is probably a gross overestimate for a standard com-
puter with a clock speed of a gigahertz, then it can complete the dictionary
attack in 100 seconds, which is less than 2 minutes. Indeed, because of
this risk, many systems introduce a multiple-second delay before reporting

41
 Introduction

password failures and some systems lock out users after they have had a
number of unsuccessful password attempts above some threshold.

Secure Passwords

Secure passwords, on the other hand, take advantage of the full potential
of a large alphabet, thus slowing down dictionary attacks. For instance,
if a system administrator insists on each password being an arbitrary
string of at least eight printable characters that can by typed on a typical
American keyboard, then the number of potential passwords is at least
948 = 6 095 689 385 410 816, that is, at least 6 quadrillion. Even if a computer
could test one password every nanosecond, which is about as fast as any
computer could, then it would take, on average, at least 3 million seconds
to break one such password, that is, at least 1 month of nonstop attempts.
The above back-of-the-envelope calculation could be the reason why
paranoid system administrators ask users to change their passwords every
month. If each attempt takes at least a microsecond, which is more realistic,
then breaking such a password would take at least 95 years on average. So,
realistically, if someone can memorize a complex password, and never leak
it to any untrustworthy source, then it is probably good for a long time.
There are several tricks for memorizing a complex password. Needless
to say in a book on computer security, one of those ways is definitely not
writing the password down on a post-it note and sticking it on a computer
screen! A better way is to memorize a silly or memorable sentence and then
take every first letter of each word, capitalizing some, and then folding in
some special characters. For example, a user, who we will call “Mark,”
could start with the sentence

“Mark took Lisa to Disneyland on March 15,”

which might be how Mark celebrated his anniversary with Lisa. Then this
sentence becomes the string

MtLtDoM15,
which provides a pretty strong password. However, we can do even better.
Since a t looks a lot like the plus sign, Mark can substitute “+” for one of the
t’s, resulting in the password

MtL+DoM15,
which is even stronger. If Mark is careful not to let this out, this password
could last a lifetime.

42
 Introduction

4.3 Social Engineering

The three B’s of espionage—burglary, bribery, and blackmail—apply
equally well to computer security. Add to these three techniques good old
fashion trickery and we come up with one of the most powerful attacks
against computer security solutions—social engineering. This term refers
to techniques involving the use of human insiders to circumvent computer
security solutions.

Pretexting
A classic example of a social engineering attack, for instance, involves an
attacker, Eve, calling a helpdesk and telling them that she has forgotten her
password, when she is actually calling about the account of someone else,
say, someone named “Alice.” The helpdesk agent might even ask Eve a
few personal questions about Alice, which, if Eve has done her homework,
she can answer with ease. Then the courteous helpdesk agent will likely
reset the password for Alice’s account and give the new password to Eve,
thinking that she is Alice. Even counting in the few hours that it takes Eve to
discover some personal details about Alice, such as her birthday, mother’s
maiden name, and her pet’s name, such an attack works faster than a brute-
force password attack by orders of magnitudes, and it doesn’t require any
specialized hardware or software. Such an attack, which is based on an
invented story or pretext, is known as pretexting.

Baiting
Another attack, known as baiting, involves using some kind of “gift” as a
bait to get someone to install malicious software. For example, an attacker
could leave a few USB drives in the parking lot of a company with an
otherwise secure computer system, even marking some with the names of
popular software programs or games. The hope is that some unsuspecting
employee will pick up a USB drive on his lunch break, bring it into the
company, insert it into an otherwise secure computer, and unwittingly
install the malicious software.

Quid Pro Quo

Yet another social engineering attack is the quid pro quo, which is Latin
for “something for something.” For example, an attacker, “Bob,” might
call a victim, “Alice,” on the phone saying that he is a helpdesk agent who
was referred to Alice by a coworker. Bob then asks Alice if she has been

43
 Introduction

having any trouble with her computer or with her company’s computer
system in general. Or he could ask Alice if she needs any help in coming
up with a strong password now that it is time to change her old one. In
any case, Bob offers Alice some legitimate help. He may even diagnose
and solve a problem she has been having with her computer. This is the
“something” that Bob has now offered Alice, seemingly without asking for
anything in return. At that point, Bob then asks Alice for her password,
possibly offering to perform future fixes or offering to do an evaluation of
how strong her password is. Because of the social pressure that is within
each of us to want to return a favor, Alice may feel completely at ease at this
point in sharing her password with Bob in return for his “free” help. If she
does so, she will have just become a victim of the quid pro quo attack.
To increase the chances of succeeding in his attack, Bob may use a voice-
over-IP (VoIP) telephone service that allows for caller-ID spoofing. Thus,
he could supply as his caller-ID the phone number and name of the actual
helpdesk for Alice’s company, which will increase the likelihood that Alice
will believe Bob’s story. This is an instance of another type of attack called
vishing, which is short for VoIP phishing.
In general, social engineering attacks can be very effective methods to
circumvent strong computer security solutions. Thus, whenever a system
designer is implementing an otherwise secure system, he or she should
keep in mind the way that people will interact with that system and the
risks it may have to social engineering attacks.

4.4 Vulnerabilities from Programming Errors

The programmers should be given clear instructions on how to produce the
secure system and a formal description of the security requirements that
need to be satisfied. Also, an implementation should be tested against all
the security requirements. Special attention must be paid to sections of the
program that handle network communication and process inputs provided
by users. Indeed, any interaction of the program with the external world
should be examined to guarantee that the system will remain in a secure
state even if the external entity communicating with the system performs
unexpected actions.
There are many examples of systems that enter into a vulnerable state
when a user supplies a malformed input. For example, the classic buffer
overflow attack (see Figure 16) injects code written by a malicious user
into a running application by exploiting the common programming error
of not checking whether an input string read by the application is larger
than the variable into which it is stored (the buffer). Thus, a large input

44
 Introduction

provided by the attacker can overwrite the data and code of the application,
which may result in the application performing malicious actions specified
by the attacker. Web servers and other applications that communicate over
the Internet have been often attacked by remote users by exploiting buffer
overflow vulnerabilities in their code.

malicious
name buffer
code

application
code
enter name

web server

Attacker

(a)

name buffer

malicious
code
application
li ti
code

web server

Attacker
(b)

Figure 16: A buffer overflow attack on a web server. (a) A web server
accepts user input from a name field on a web page into an unchecked
buffer variable. The attacker supplies as input some malicious code. (b) The
malicious code read by the server overflows the buffer and part of the
application code. The web server now runs the malicious code.

45
 Introduction

5 Exercises
For help with exercises, please visit securitybook.net.

Reinforcement
R-1 Compare and contrast the C.I.A. concepts for information security
with the A.A.A. concepts.
R-2 What is the ciphertext in an English version of the Caesar cipher
for the plaintext “ALL ZEBRAS YELP.”
R-3 Explain why someone need not worry about being a victim of a
social engineering attack through their cell phone if they are inside
of a Faraday cage.
R-4 What are some of the techniques that are used to achieve confiden-
tiality?
R-5 What is the most efficient technique for achieving data integrity?
R-6 With respect to the C.I.A. and A.A.A. concepts, what risks are
posed by spam?
R-7 With respect to the C.I.A. and A.A.A. concepts, what risks are
posed by Trojan horses?
R-8 With respect to the C.I.A. and A.A.A. concepts, what risks are
posed by computer viruses?
R-9 With respect to the C.I.A. and A.A.A. concepts, what risks are
posed by packet sniffers, which monitor all the packets that are
transmitted in a wireless Internet access point?
R-10 With respect to the C.I.A. and A.A.A. concepts, what risks are
posed by someone burning songs from an online music store onto
a CD, then ripping those songs into their MP3 player software sys-
tem and making dozens of copies of these songs for their friends?
R-11 With respect to the C.I.A. and A.A.A. concepts, what risks are
posed by someone making so many download requests from an
online music store that it prevents other users from being able to
download any songs?
R-12 Compare and contrast symmetric encryption with public-key en-
cryption, including the strengths and weaknesses of each.
R-13 List at least three security risks that could arise when someone has
their laptop stolen.

46
 Introduction

R-14 Suppose the author of an online banking software system has

programmed in a secret feature so that program emails him the
account information for any account whose balance has just gone
over $10,000. What kind of attack is this and what are some of its
risks?
R-15 Suppose an Internet service provider (ISP) has a voice over IP
(VoIP) telephone system that it manages and sells. Suppose further
that this ISP is deliberately dropping 25% of the packets used in
its competitors VoIP system when those packets are going through
this ISP’s routers. What kind of an attack is this?
R-16 Give an example of the false sense of security that can come from
using the “security by obscurity” approach.
R-17 The English language has an information content of about 1.25 bits
per character. Thus, when using the standard 8-bit ASCII encoding,
about 6.75 bits per character are redundant. Compute the probabil-
ity that a random array of t bytes corresponds to English text.
R-18 Suppose that a symmetric cryptosystem with 32-bit key length is
used to encrypt messages written in English and encoded in ASCII.
Given that keys are short, an attacker is using a brute-force exhaus-
tive search method to decrypt a ciphertext of t bytes. Estimate the
probability of uniquely recovering the plaintext corresponding to
the ciphertext for the following values of t: 8, 64, and 512.
R-19 Suppose you could use all 128 characters in the ASCII character
set in a password. What is the number of 8-character passwords
that could be constructed from such a character set? How long, on
average, would it take an attacker to guess such a password if he
could test a password every nanosecond?
R-20 Doug’s laptop computer was just infected with some malicious
software that uses his laptop’s built-in camera to take a video each
time it senses movement and then upload the video to a popular
video-sharing web site. What type of attack does this involve and
what concepts of computer security does it violate?
R-21 The Honyota Corporation has a new car out, the Nav750, which
transmits its GPS coordinates to the Honyota Corporation comput-
ers every second. An owner can then locate their car any time, just
by accessing this site using a password, which is a concatenation
of their last name and favorite ice cream flavor. What are some
security concerns for the Nav750? What are some privacy concerns,
say, if the car’s owner is the spouse, parent, or employer of the car’s
principle driver?

47
 Introduction

R-22 The HF Corporation has a new refrigerator, the Monitator, which

has a camera that takes a picture of the contents of the refrigerator
and uploads it to the HF Corporation’s web site. The Monitator’s
owner can then access this web site to see what is inside their
refrigerator without opening the door. For security reasons, the
HF Corporation encrypts this picture using a proprietary algorithm
and gives the 4-digit PIN to decrypt this picture to the Monitator’s
owner, so he or she can get access to the pictures of their Monita-
tor’s interior. What are the security concerns and principles that
this solution does and doesn’t support?
R-23 During the 2008 U.S. Presidential campaign, hackers were able
to gain access to an email account of Vice Presidential candidate,
Sarah Palin. Their attack is said to have involved tricking the
mail system to reset Governor Palin’s password, claiming they
were really Palin and had forgotten this password. The system
asked the hackers a number of personal questions regarding Palin’s
identity, including her birthday, zip code, and a personal security
question—“Where did you meet your spouse?”—all of which the
hackers were able to answer using data available on the Internet.
What kind of attack is this an example of? Also, what degree of
security is provided by a password reset feature such as this?

Creativity
C-1 Describe an architecture for an email password reset system that is
more secure than the one described in Exercise R-23, but is still
highly usable.
C-2 Describe an instance of a file that contains evidence of its own
integrity and authenticity.
C-3 Suppose an Internet service provider (ISP) has a voice over IP
(VoIP) telephone system that it manages and sells. Suppose further
that this ISP is deliberately dropping 25% of the packets used in
its competitors VoIP system when those packets are going through
this ISP’s routers. Describe how a user could discover that his ISP
is doing this.
C-4 Computer viruses, by their very nature, have to be able to replicate
themselves. Thus, a computer virus must store a copy of itself in-
side its own code. Describe how this property of computer viruses
could be used to discover that a computer virus has infected a
certain operating system file.

48
 Introduction

C-5 Suppose that you are a computer virus writer; hence, you know
that you need to store a copy of the code for your virus inside
the virus itself. Moreover, suppose you know that a security
administrator is also aware of this fact and will be using it to
detect the presence of your virus in operating systems files, as
described in the previous problem. Explain how you can hide the
embedded copy of your virus so that it is difficult for the security
administrator to find it.
C-6 Describe a hybrid scheme for access control that combines both
the access control list and capabilities models. Explain how the
records for this hybrid model can be cross-linked to support object
removal and subject removal in time proportional to their number
of associated access rights; hence, not in time proportional to all the
subject-object access right pairs.
C-7 Give two examples of attacks that compromise the integrity of the
meta data of files or directories in a file system.
C-8 A rootkit is a piece of malicious software that installs itself into an
operating system and then alters all of the operating system utility
programs that would normally be able to detect this software so
that they do not show its presence. Describe the risks that would
be posed by such software, how it could actually be discovered,
and how such an infection could be repaired.
C-9 Benny is a thief who tried to break into an Automated Teller Ma-
chine (ATM) using a screwdriver, but was only able to break five
different keys on the numeric keypad and jam the card reader, at
which point he heard Alice coming, so he hid. Alice walked up,
put in her ATM card, successfully entered her 4-digit PIN, and took
some cash. But she was not able to get her card back, so she drove
off to find help. Benny then went back to the ATM, and started
entering numbers to try to discover Alice’s PIN and steal money
from her account. What is the worst-case number of PINs that
Benny has to enter before correctly discovering Alice’s PIN?
C-10 As soon as Barack took office, he decided to embrace modern tech-
nology by communicating with cabinet members over the Internet
using a device that supports cryptographic protocols. In a first
attempt, Barack exchanges with Tim brief text messages, encrypted
with public-key cryptography, to decide the exact amounts of
bailout money to give to the largest 10 banks in the country. Let
p B and p T be the public keys of Barack and Tim, respectively. A
message m sent by Barack to Tim is transmitted as E pT (m) and the
reply r from Tim to Barack is transmitted as E pB (r ). The attacker

49
 Introduction

can eavesdrop the communication and knows the following infor-

mation:
• Public keys p B and pT and the encryption algorithm
• The total amount of bailout money authorized by congress
is $900B
• The names of the largest 10 banks
• The amount each bank will get is a multiple of $1B
• Messages and replies are terse exchanges of the following
form:
Barack: How much to Citibank?
Tim: $144B.
Barack: How much to Bank of America?
Tim: $201B.
···
Describe how the attacker can learn the bailout amount for each
bank even if he cannot derive the private keys.
C-11 As a result of the above attack, Barack decides to modify the
protocol of Exercise C-10 for exchanging messages. Describe two
simple modifications of the protocol that are not subject to the
above attack. The first one should use random numbers and the
second one should use symmetric encryption.
C-12 Barack often sends funny jokes to Hillary. He does not care about
confidentiality of these messages but wants to get credit for the
jokes and prevent Bill from claiming authorship of or modifying
them. How can this be achieved using public-key cryptography?
C-13 As public-key cryptography is computationally intensive and
drains the battery of Barack’s device, he comes up with an alter-
native approach. First, he shares a secret key k with Hillary but
not with Bill. Next, together with a joke x, he sends over the value
d = h(k || x ), where h is a cryptographic hash function. Does value
d provide assurance to Hillary that Barack is the author of x and
that xwas not modified by Bill? Justify your answer.
C-14 Barack periodically comes up with brilliant ideas to stop the fi-
nancial crisis, provide health care to every citizen, and save the
polar bears. He wants to share these ideas with all the cabinet
members but also get credit for the ideas. Extending the above
approach, he shares a secret key k with all the cabinet members.
Next, he broadcasts each idea z followed by value h(k ||z). Does
this approach work or can Tim claim that he came up with the ideas
instead of Barack? Justify your answer.

50
 Introduction

C-15 Describe a method that allows a client to authenticate multiple

times to a server with the following requirements:
a. The client and server use constant space for authentication.
b. Every time the client authenticates to the server, a different
random value for authentication is used (for example, if you
have n authentication rounds, the client and the server have
to use n different random values—this means that sharing a
key initially and using it for every round of authentication is
not a valid solution).
Can you find any vulnerabilities for this protocol?
C-16 Consider the following method that establishes a secret session key
k for use by Alice and Bob. Alice and Bob already share a secret key
K AB for a symmetric cryptosystem.
a. Alice sends a random value NA to Bob along with her id, A.
b. Bob sends encrypted message EK AB ( NA ), NB to Alice, where
NB is a random value chosen by Bob.
c. Alice sends back EK AB ( NB ).
d. Bob generates session key k and sends EK AB (k ) to Alice.
e. Now Alice and Bob exchange messages encrypted with the
new session key k.
Suppose that the random values and the keys have the same
number of bits. Describe a possible attack for this authentication
method.
Can we make the method more secure by lifting the assumption
that the random values and the keys have the same number of bits?
Explain.
C-17 Alice and Bob shared an n-bit secret key some time ago. Now
they are no longer sure they still have the same key. Thus, they
use the following method to communicate with each other over an
insecure channel to verify that the key K A held by Alice is the same
as the key K B held by Bob. Their goal is to prevent an attacker from
learning the secret key.
a. Alice generates a random n-bit value R.
b. Alice computes X = K A ⊕ R, where ⊕ denotes the exclusive-
or boolean function, and sends X to Bob.
c. Bob computes Y = K B ⊕ X and sends Y to Alice.
d. Alice compares X and Y. If X = Y, she concludes that K A =
K B , that is, she and Bob have indeed the same secret key.
Show how an attacker eavesdropping the channel can gain posses-
sion of the shared secret key.

51
 Introduction

C-18 Many Internet browsers “lock the lock” on an encrypted web site so
long as the digital certificate offered for this site matches the name
for this web server. Explain how this could lead to a false sense of
security in the case of a phishing attack.
C-19 Explain the risks to Bob if he is willing to sign a seemingly random
string using his private key.
C-20 Describe a good solution to the problem of having a group of
students collaborate on a software construction project using the
directory of one of the group members in such a way that it would
be difficult for nonmembers to discover and would not require the
help from a system administrator, assuming that the only access
rights the group leader can modify are those for “everyone.” You
may assume that access rights for directories are “read,” “write,”
and “exec,” where “read” means the files and subdirectories in that
directory can be listed, “write” means members of that directory
can be inserted, deleted, or renamed, and “exec” on a directory
or subdirectory means the user can change his location to that
directory or subdirectory so long as he specifies its exact name.
C-21 Suppose an operating system gives users an automatic second
chance functionality, so that any time a user asks to delete a file
it actually gets put into a special “recycle bin” directory, which is
shared by all users, with its access rights defined so that users can
get their files back even if they forget their names. Describe the
security risks that such a functionality poses.
C-22 Suppose, in a scenario based on a true story, a network computer
virus is designed so as soon as it is copied onto a computer, X, it
simply copies itself to six of X’s neighboring computers, each time
using a random file name, so as to evade detection. The virus itself
does no other harm, in that it doesn’t read any other files and it
doesn’t delete or modify any other files either. What harm would
be done by such a virus and how would it be detected?

Projects
P-1 Implement a “toy” file system, with about a dozen different users
and at least that many directories and files, that uses an access
control matrix to manage access control rights.
P-2 Perform the project of Problem P-1, but use access control lists.
P-3 Perform the project of Problem P-1, but use capabilities to define
the access control rights of each user.

52
 Introduction

P-4 Perform a statistical analysis of all the spam you get in a week,
classifying each as to the types of attacks they are.
P-5 Implement a toy symmetric cryptosystem based on the following
method.
a. Keys are 16-bit values.
b. Messages are strings with an even number of characters. One
can always add a blank at the end of an odd-length string.
c. The encryption of a message M of length n (in bytes) is given
by
EK ( M) = M ⊕ (K ||K || · · · ),
where the key K is repeated n/2 times.
d. The decryption algorithm for a ciphertext C is the same as the
encryption algorithm:

DK (C ) = C ⊕ (K ||K || · · · ).

Implement a brute-force decryption attack for this cryptosystem

and test it on randomly generated English text messages. Au-
tomate the process of detecting whether a decrypted message is
English test.

Chapter Notes
The ten principles of computer security are from the seminal paper by Saltzer and
Schroeder [86], who caution that the last two principles (work factor and com-
promise recording) are derived from physical security systems and “apply only
imperfectly to computer systems.” The open design principle was first formulated
in a paper by 19th-century French cryptographer Auguste Kerckhoffs [47]. Bruce
Schneier’s Crypto-Gram Newsletter has a well-written article on secrecy, security,
and obscurity [88]. A contemporary introduction to cryptography and its use in
computer systems is given in the book by Ferguson, Schneier and Konho [30]. The
redundancy of natural language was first formally studied by Claude Shannon in
his pioneering paper defining the information-theoretic concept of entropy [91].
Usability issues for email encryption are the subject of an experimental study by
Whitten and Tygar [107].

53
This page intentionally left blank
 Physical Security

Contents
1 Physical Protections and Attacks
2 Locks and Safes
2.1 Lock Technology
2.2 Attacks on Locks and Safes
2.3 The Mathematics of Lock Security
3 Authentication Technologies
3.1 Barcodes
3.2 Magnetic Stripe Cards
3.3 Smart Cards
3.4 RFIDs
3 5. Biometrics
4 Direct Attacks Against Computers
4.1 Environmental Attacks and Accidents
4.2 Eavesdropping
4.3 TEMPEST
4.4 Live CDs
4.5 Computer Forensics
5 Special-Purpose Machines
5.1 Automated Teller Machines
5.2 Voting Machines
6 Physical Intrusion Detection
6.1 Video Monitoring
6.2 Human Factors and Social Engineering
7 Exercises

From Chapter 2 of Introduction to Computer Science, First Edition, Michael T. Goodrich,

Roberto Tamassia. Copyright 2011 by Pearson Education, Inc. Published by
Pearson Addison-Wesley. All rights reserved.

55
 Physical Security

1 Physical Protections and Attacks

We live in a physical world. This is an obvious fact, of course, but it
is surprisingly easy to overlook when discussing the security of digital
information. Our natural tendency is to consider computer security strictly
in a digital context, where computers are accessed only over a network or
through a well-specified digital interface and are never accessed in person
or with physical tools, like a hammer, screwdriver, or container of liquid
nitrogen. Ultimately, however, digital information must reside somewhere
physically, such as in the states of electrons, magnetic media, or optical
devices, and accessing this information requires the use of an interface
between the physical and digital worlds. Thus, the protection of digital
information must include methods for physically protecting this interface.
Physical security is broadly defined as the use of physical measures
to protect valuables, information, or access to restricted resources. In this
chapter, we examine the physical dimensions of computer security and
information assurance, focusing on the following aspects:

• Location protection: the protection of the physical location where

computer hardware resides, such as through the use of locks.

• Physical intrusion detection: the detection of unauthorized access to

the physical location where computer hardware resides.

• Hardware attacks: methods that physically attack the hardware rep-

resentations of information or computations, such as hard drives,
network adapters, memory chips, and microprocessors.

• Eavesdropping: attacks that monitor light, sound, radio, or other

signals to detect communications or computations.

• Physical interface attacks: attacks that penetrate a system’s security

by exploiting a weakness in its physical interface.
We discuss these physical aspects of computer security and information
assurance and we give several examples of vulnerabilities in the physical
aspects of some security solutions, including smart cards, automated teller
machines (ATMs), radio-frequency identification (RFID) tags, biometric
readers, and voting machines. An important theme that runs throughout
this discussion is the way in which physical security directly impacts the
integrity and protection of computer hardware and digital information.

56
 Physical Security

2 Locks and Safes

The notion of using a mechanical locking device to protect access to a
building, vehicle, or container has been in use since ancient times. Primitive
tumbler locks, which are discussed below, have been found in the ruins
of ancient Egyptian and Persian cities. Today, a wide variety of locks are
in common usage, including those that require a key, a combination, or
both, and these mechanisms are often used to protect the physical locations
where computers and digital media are stored. This section covers com-
monly used lock types and techniques for attacking them without having
the corresponding key or combination.

2.1 Lock Technology

Pin Tumbler Locks
The most commonly used type of keyed lock is the pin tumbler lock,
illustrated in Figure 1. In this design, a cylindrical plug is housed within
an outer casing. The lock is opened when the plug rotates and releases a
locking bolt, typically through a lever. When the lock is closed, the rotation
of the plug is prevented by a series of pin stacks, which are housed in holes
that have been drilled vertically through the plug and the outer casing. A
pin stack typically consists of two cylindrical pins. The top pins, called
driver pins, are spring loaded.

Figure 1: A pin tumbler lock: (1) When a key is not present, the pin stacks
are pushed down by the springs so that the driver (top) pins span the plug
and the outer casing, preventing the plug from rotating. Image included
with permission [108]. (2) When the correct key is inserted, the ridges of
the key push up the pin stacks so that the cuts of the pin stacks are aligned
with the shear line. Image included with permission [75]. (3) The alignment
of the cuts with the shear line allows the plug to be rotated. Image included
with permission [76].

57
 Physical Security

The bottom pins are called the key pins, since they make contact with
the key when the key is inserted. The heights of the respective driver
and key pins can vary. When there is no key inserted, the springs force
the pin stacks down so that the driver pins span the plug and the outer
casing, preventing the plug from rotating. When the appropriate key is
inserted, however, the ridges of the key push up the pin stacks so that the
cut between each key pin and its driver pin is at the point where the plug
meets the outer casing, known as the shear line, allowing the plug to rotate
and open the lock.

Tubular and Radial Locks

A variation on the classic pin tumbler design is known as the tubular lock,
or radial lock, depicted in Figure 2. The premise is the same: several
spring-loaded pin stacks prevent the rotation of the plug by obstructing the
shear line. Rather than having the pins located on a line parallel to the axis
of the plug, as in the traditional pin tumbler lock, the pins of a tubular lock
are arranged in circle. As a result, keys are cylindrical in shape. These locks
are most commonly used on laptops, vending machines, and bicycles.

Figure 2: Opening a tubular lock: (1) Closed lock. Image included with
permission [68]. (2) After inserting the key. Image included with permis-
sion [69]. (3) Open lock. Image included with permission [70].

58
 Physical Security

Wafer Tumbler Locks

A third type of lock in common usage is known as the wafer tumbler lock,
depicted in Figure 3. Again, the general principle of the lock relies on
preventing the rotation of a central plug. This time, the obstruction is a
series of wafers that initially sit in a groove at the bottom of the outer
casing. When the appropriate key is inserted, the wafers are raised out
of this groove and allow the plug to rotate. Wafer tumbler locks are used in
cars, filing cabinets, and other medium security applications.

Figure 3: Opening a wafer tumbler lock: (1) Closed lock. Image included
with permission [71]. (2) After inserting the key. Image included with
permission [72]. (3) Open lock. Image included with permission [73].

Combination Locks

A combination lock is any lock that can be opened by entering a predeter-

mined sequence of numbers. Combination locks typically come in one of
three varieties, multiple dial, single dial, and electronic. Multiple-dial locks
feature a sequence of notched disks around a toothed pin, as depicted in
Figure 4.

Figure 4: Opening a multiple-dial combination lock. Image included with

permission [74].

59
 Physical Security

When the disks are rotated to the correct combination, the notches
line up with the teeth of the pin, allowing it to be removed. Multiple-
dial combination locks are often used in briefcases, bicycle locks, and
other low-security applications, since it is often easy to quickly deduce the
combination because of mechanical imperfections. Single-dial combination
locks are generally considered more secure and are used in a wide variety
of applications, including safes, which are discussed later in this section.
Single-dial locks feature a series of disks attached to a numbered dial. When
the correct combination is entered using the dial, these disks line up in such
a way as to release a clasp or some other locking mechanism.
In an electronic combination lock, an electronic mechanism is used to
operate the lock using electromagnets or motors that are activated through
an event that either turns on or turns off an electric current. The event that
opens an electronic lock could be triggered by a number of different actions,
including the following (which could be used in conjunction):
• An electronic combination: the punching of an appropriate sequence
of numbers on a keypad in a given amount of time
• A magnetic stripe card: a plastic card with a magnetic stripe (Sec-
tion 3.2) that contains an authorizing digital combination
• A smart card: a small computational device contained in a card, as
discussed in Section 3.3, that performs an authorizing computation
to open the lock
• An RFID tag: a small radio frequency identification device that
contains a computational element or memory, as discussed in Sec-
tion 3.4, that either performs an authorizing computation or trans-
mits an electronic combination
• A biometric: a biological characteristic, as discussed in Section 3.5,
that is read and matches a characteristic authorized to open the lock
One advantage of electronic locks is that it is relatively easy to change
the combination or condition that opens such a lock—there is no need to
change a physical plug or swap out pins. For instance, most hotels employ
electronic lock systems for their guest rooms, allowing for easy changing of
locks between consecutive guests staying in the same room.
Another advantage is that electronic locks can be fitted with digital stor-
age devices or can be connected to a communication network to monitor
and manage when the locks are opened and closed. The monitoring can
even log who has entered and left through the doors that are fitted with
the various locks in a building, by using different digital combinations or
opening devices for different people. This type of monitoring was useful,
for example, in determining who murdered a Yale graduate student in 2009.
The monitoring system showed that the student had entered a secured

60
 Physical Security

building, but never left, and it also allowed authorities to determine all
the people who had entered the specific room where her body was found.
Electronic locks are also frequently used in audit trails for regulatory com-
pliance, especially in the health care and financial sectors.

Master and Control Keys

Many organizations require a key system that incorporates a hierarchy of
access control. For example, some systems feature locks that have keys
specific to each lock, known as change keys, as well as a single master key
that can open all of the locks in the system. Larger and more complex
organizations may have several different master-keyed systems, with a
single grandmaster key that can open any lock in the organization. Some
locks also accept a control key, which enables a locksmith to remove the
entire core of the lock from its outer casing, allowing easy rekeying.
Locks designed to be opened by a master key have at least two keyings,
one for the change key and one for the master key. Multiple keyings are
created by inserting spacers, or very short pins, between the driver and key
pins. The height of the master key should be greater than that of the change
key to prevent the owner of a change key from filing down their key to
create a master key.
Master-keyed systems require the owner to incorporate access control
policies and procedures for when a key is lost or stolen. If a master key
is lost, it is necessary to rekey the entire system to prevent compromise.
Handling the loss of a change key is left to the discretion of the organization,
however. Some choose to merely rekey the specific lock that accompanies
the lost key, while others rekey the entire system to ensure that the missing
key does not allow an attacker to create a master key.

Safes
Valuables can be secured against theft by placing them in a safe. Safes
can range from small lockboxes in homes to large, high-security safes in
banks. Safes can feature any of the locking mechanisms discussed in this
chapter, but most high-security models employ a combination dial, with
the possible addition of biometric authentication and electronic auditing.
No safe is impenetrable. In fact, safes are rated by organizations such as
Underwriters Laboratories (UL) in terms of how long it would take a well-
equipped expert to compromise the safe. In their ratings, they consider both
destructive and nondestructive approaches. Owners of safes are advised
to ensure that the response time to alarms is less than the average time
required to crack the safe.

61
 Physical Security

2.2 Attacks on Locks and Safes

There are several ways to attack locks and safes, so as to open them without
use of a key or a priori knowledge of a combination.

Lockpicking
The classic approach to bypassing locks is known as lockpicking, which
exploits mechanical imperfections in the locking mechanism that allow an
attacker to replicate the effect of an authorized entry. (See Figure 5.)

(a) (b)

Figure 5: Lockpicking: (a) A lock picker attempts to open a padlock by

applying a rotational force with a tension wrench and picking the pins
individually. Photo by Dan Rosenberg included with permission. (b) Lock-
picking tools. Photo by Jennie Rogers included with permission.

As a simple example, let us examine the common pin tumbler lock.

Recall from Section 2.1 that this type of lock features a cylindrical plug
whose rotation is prevented by pins obstructing the shear line (where the
plug meets the outer casing). To pick a tumbler lock using a common
technique, an attacker first inserts a tension wrench into the keyhole of the
lock and applies a slight rotational force. The plug will rotate a very small
amount before being stopped by the pins. In particular, one of the pins will
be directly in contact with the cylinder—this is known to lock pickers as a
binding pin. Only one pin comes in contact with the cylinder because of
slight imperfections in the manufacturing process causing the pin stacks to
not line up perfectly. Using a feeler pick, the attacker first probes each pin,
lifting it slightly to assess the amount of friction experienced. The binding
pin will offer greater resistance to motion due to it making contact with the
cylinder. The attacker then carefully raises the binding pin until the break

62
 Physical Security

between the key pin and the driver pin is in line with the shear line. At
this point, the plug will further rotate by a tiny amount until it is stopped
by the next binding pin. The driver pin of the previous binding pin will
now sit on a small ledge created by the additional rotation of the plug (it
is “bound”). The attacker then repeats the process for the remaining pins,
identifying and lifting them. When the last pin is picked, all of the pin
breaks are aligned with the shear line, and the rotational force applied by
the tension wrench will open the lock.
It takes a high degree of skill and intuition to determine when a pin
has bound. Lock pickers must practice extensively to recognize the feeling
of a pin binding in a locking mechanism. To make the process easier,
lock pickers often employ a method known as raking or scrubbing. In
this technique, a pick designed to lift several pins simultaneously is run
through the keyhole using a back and forth scrubbing motion in an attempt
to bind more than one pin at the same time. Once several pins are bound,
the remaining pins can be individually picked. Alternatively the attacker
can make another pass with the rake to attempt to set more pins. Pickers
typically use a snake or half-diamond rake for this purpose.
Another approach that can work on inexpensive locks is the use of a
comb pick. For simpler locks an attacker can lift all of the pins simultane-
ously above the shear line using a tool that resembles a hair comb. Once
the pins have been pushed all the way into the lock housing then the plug
is free to rotate. Well-made models combat this weakness by making sure
that the pin stack is long enough to always extend past the shear line.

Lock Bumping
Lock bumping is a technique that received widespread media attention
in 2006. The technique utilizes specially crafted bump keys, which are
unique to each particular brand of lock. (See Figure 6.)

Figure 6: Bump keys and hammer. Photo by Jennie Rogers included with
permission.

63
 Physical Security

Bump keys are made by taking an appropriate key blank (matching a

specific lock brand) and filing down each of the pin ridges to the lowest
setting, keeping the teeth in between each ridge. To “bump” a lock, the
bump key is inserted into the keyhole, and then withdrawn a small amount
so that each tooth rests immediately behind a pin. While applying a slight
rotational force, the bump key is then reinserted by tapping it with a
hammer or other object. This results in the ridges hitting the pin stacks.
As a consequence, the key pins transfer kinetic energy to the driver pins,
which jump above the shear line for a split second, allowing the plug to be
rotated. Interestingly, more expensive locks are often more vulnerable to
bumping because a reduction in mechanical imperfections allows the pins
to move more freely when being bumped.
Professional locksmiths and law enforcement agents often employ the
use of an electronic pick gun, which operates on the same principle as lock
bumping. A pick gun has a single pick that is vibrated rapidly and transfers
energy to all of the pins simultaneously. During the split second after this
energy transfer, which attempts to force the driver pins above the shear line,
the pick gun applies a brief rotational force to attempt to open the lock.

Key Duplication and Impressioning

Several methods can be used to create a key for a given lock. A locksmith
can easily create a key duplicate if the original is available, for instance. It is
not always even necessary to have an original on-hand, however—a mere
photograph of the key can be used if the locksmith is able to deduce the
type of key and approximate its cut. Another technique used sometimes to
“capture” a key consists of briefly taking it and pressing it into a soft, clay-
like material that can later be hardened into a mold for key creation. A key
does not need to be made of metal to be effective.
Another technique that is used to bypass locks is known as key impres-
sioning. An attacker begins with a key blank matched to a specific lock
brand. The top of the blank is polished, and then the key is inserted into the
target lock. A rotational force is applied to the key, which is then jiggled up
and down. The blank is finally removed. Each pin that is not at the shear
line will have left a small scrape on the polished blank. At each scraped
location, the attacker files off a small amount of material. The process is
repeated until no scrapes are created, resulting in a key that can open the
lock. Key impressioning requires the use of keys blanks made of a soft
metal, such as brass. Also, the attacker must use a very precise filing tool,
such as a jeweler’s file.

64
 Physical Security

High Security Locks

A number of innovations have been developed to make bypassing locks

more difficult.
One preventative measure is the incorporation of security pins, such as
mushroom head pins or spool pins. In this design, the pins are narrower
towards the middle, but flare outwards at the top and bottom. This design
does not prevent normal operation of the lock, since a proper key moves
the entire pin above the shear line. This technique makes picking more
difficult, however, because the pin may bind in its midsection, preventing
an attacker from binding the pin properly and from knowing whether or
not the pin has bound in the correct place.
Another form of security pin is a serrated pin. This pin has a series of
small ridges around it that make the pin feel like it is perpetually setting on
the shear line to a lock picker working one pin at a time. Thus each time an
attacker lifts a pin it gives the feeling that the cylinder is rotating slightly,
despite it only moving up the ridges. The top and bottom pins may both
have the ridges to further mislead an unauthorized user.
Security pins may defend against ordinary picking, but do little to
stop techniques such as bumping. For this reason, lock manufacturers
have developed high-security models that do not rely on the traditional
pin tumbler design. Medeco developed a lock called the Biaxial that uses
angular bitting, which requires that each of the pins must be elevated and
rotated by the angled cuts of the key.
As another example, Abloy manufactures a disc tumbler lock that uti-
lizes a series of notched disks. This unique design makes traditional picking
and bumping approaches impossible, but this lock may be vulnerable to
other means of circumvention.
Higher security locks (including Medeco Biaxial and its variants) fea-
ture an internal sidebar, which prevents the cylinder from turning until
all of the pins have been rotated and aligned, making picking extremely
difficult. The lock is marketed as being bump-proof, but recent research
suggests that highly specialized bump keys may still make bumping possi-
ble.
In addition, high security locks tend to be manufactured to tighter
specifications, making it more challenging for a lock picker to identify
the binding pins and feel out a lock. Also, to buy more time against a
destructive attack, most higher security models also feature drill-resistant
pins, which prevent an attacker from being able to use an off-the-shelf drill
to attack the shear line of a lock.

65
 Physical Security

High-value targets, such as nuclear facilities and banks, naturally re-

quire more security precautions for their locks. Typically, these require-
ments are mandated by either insurance underwriters or the government.
There are two main standards for locks commonly used in the United
States: Underwriters Laboratories (UL) 437 and ANSI/Building and Hard-
ware Manufacturers Association (BHMA) 156.30.
These standards attempt to model how well a product will stand up to
well-known attacks, including destructive and non-destructive approaches.
In the case of UL, this means that they evaluate whether a lock can with-
stand picking, impressioning, drilling, pulling, driving, and salt spray cor-
rosion. Each of these tests consists of a specified number of minutes that the
lock must withstand the attack, where the picking and impressioning must
be performed by a certified locksmith with at least five years of experience.
The reader my have noticed that bumping is not included in the list of
UL tests. This attack was first widely published in 2006 and it can take
many years to update standards for vulnerabilities as they are discovered.
This is one of the weaknesses of the standards system. Criminals do not
necessarily follow “well-known” methods of compromising locks and it
behooves them not to share their techniques. A lock certified according
to a standard may be still vulnerable to highly skilled attackers.
Compromising higher security locks often requires domain-specific
knowledge and substantial research. A general specification may not en-
compass the necessary tests for all high security locks. For example, the
attack by Tobias and Bluzmanis exploiting a vulnerability in the Medeco
Biaxial system requires learning specialized codes to rotate the pins in the
correct orientation.
The certification system also makes responsible disclosure for these
locks considerably more complex. There is no common method to issue
“patches” for locks in the field, nor retract a certification for a lock. Like
many other aspects of security, high security lock management is a process
that goes back and forth between security researchers and manufacturers.

Safe Cracking
There are many approaches to safe cracking. The classic approach, often
portrayed in movies, involves a highly skilled expert manipulating the dial
of the safe by feel and sound until they deduce the combination. To pre-
vent this attack, many safe manufacturers include additional components
inside the locking mechanism that are designed to prevent an attacker from
correctly interpreting sounds and tactile clues. In addition, the wheels of
the locking mechanism are often made with light materials such as nylon,
reducing the noise and friction created by manipulating the lock.

66
 Physical Security

An attacker may also attempt to drill through the front of the safe to
see the lock’s inner workings or to directly manipulate the lock mechanism.
High-security safes incorporate composite hardplate, which is an extremely
rugged material designed to be resistant to drilling or other structural dam-
age. Only highly specialized drilling equipment can be used to breach these
materials. Brute-force techniques, such as explosives, may be employed,
but often these approaches are impractical, because they risk damaging the
contents of the safe. To further prevent drilling, many safes feature what is
known as a glass relocker, a thin glass plate that resides in the door of the
safe. If this glass is broken, by drilling or some other force, spring-loaded
bolts are released, permanently locking the safe.

Side Channel Attacks

Many of the principles observed in the design and circumvention of physi-
cal locks are analogous to essential principles of computer security. It is im-
portant to keep in mind that manipulating the mechanism of a lock is only
one way to gain unauthorized access. For example, a door with a highly
secure lock does little good if the door can be removed by unscrewing its
hinges. Attacks such as these are referred to as side channel attacks. (See
Figure 7.)

Figure 7: A side channel attack vulnerability: the fire escape on the side of
the building may lead to an entry point that is easier to attack than the front
door. Photo by Jennie Rogers included with permission.

67
 Physical Security

In a side channel attack, rather than attempting to directly bypass secu-

rity measures, an attacker instead goes around them by exploiting other
vulnerabilities not protected by the security mechanisms. Side channel
attacks are sometimes surprisingly simple to perform.
A classic example of a side channel attack is door plunger manipulation.
In doors that feature a plunger rather than a deadbolt, it may be possible
to open the door by inserting a flat object in between the door and the
doorframe (e.g., a slender screw driver) and manipulating the plunger until
the door opens. This attack can be prevented by shielding the plunger or
by using a deadbolt, but provides a good example of a situation where
picking the locking mechanism may be difficult, but opening the door is
still possible.
The concept of side channel attacks doesn’t only apply to locks and
safes. It can be applied to other aspects of computer security as well, since
attackers often search for the simplest way of bypassing security, rather
than the most obvious. Thus, the security of computer and information
systems should be analyzed in a holistic way, looking at both physical and
digital attacks, so as to identify the most vulnerable components in the
system.

2.3 The Mathematics of Lock Security

The number of possible combinations or configurations for a set of objects,
for which we are interested in finding one particular such object, is com-
monly known as a search space. In computer security, the most common
type of search space is the set of all possible keys used in a cryptographic
function. A large search space reduces the possibility of a brute-force attack,
where all possible combinations are tried. Therefore, anything that reduces
the size of the search space would be extremely valuable for an attacker.

Protecting Against Brute-Force Attacks

The mathematics of search spaces also applies to lock security, of course.

Traditional pin tumbler locks feature between 4 and 7 pin stacks, where
the number of possible heights for the key pins is typically between 4
and 8. Higher quality locks have more pins stacks and a larger number
of possible key pin heights. UL specifies that standard locks should have at
least 1, 000 potential combinations, or differs, and that security containers
have 1, 000, 000 or more differs. In addition, there are around 40 common
varieties of key blanks. Collectively, this results in a search space where the

68
 Physical Security

number of possible keys is no more than

40 × 87 = 83,886,080.

If we know the specific key blank, the search space is much smaller. For
example, for a given key blank with 6 pin stacks and 5 possible key pin
heights, the number of possible keys is

56 = 15,625,

which is still large enough to prevent a brute-force attack. For this reason,
attacks such as picking, key impressioning, and bumping are employed
instead of brute-force techniques.
The mathematics of counting finite collections of objects is known as
combinatorics, by the way, and the above analysis is an example of a
combinatorial argument that quantifies the security of a pin tumbler lock.

Reducing the Size of a Search Space

There are situations where effective use of combinatorics can allow for the
bypassing of locks. For example, in standard lock picking, the attacker
“solves” the lock one pin at a time, breaking the problem into two phases:
finding the binding pin and then raising it slowly. If our attacker has P
pin stacks and D possible pin heights this divide-and-conquer approach
produces a search space of size P · D instead of P D .

Privilege Escalation
Matt Blaze published a paper detailing how an attacker can use combina-
torics to create a master key from an ordinary change key on a master-keyed
lock system. This attack, which is an iterative master-key construction, is
analogous to privilege escalation in computer security, where an attacker
leverages a low-privilege ability into a high-privilege ability.
The attack works as follows. Consider a lock having the same config-
uration of P and D as above. The attacker has a change key and wants to
build a master key using a small number of keys blanks. The only basic
operation used by the attacker is to test whether a given key opens the lock.
For simplicity, we will use the term pin to denote a key pin.
Starting with the first pin stack, the attacker creates D − 1 keys, each
keeping all pins but the first at the same height as in the change key, and
trying all possible variations for the first pin height (except for the height
of the first pin in the change key). The key that results in opening the lock
reveals the height for the first pin of the master key. The process is then

69
 Physical Security

repeated for each of the remaining pins, and a final master key is made
using each pin’s successful key. The above attack requires a total number
of key blanks that is at most

P · ( D − 1).

Also, at most P · ( D − 1) lock opening tests are performed.

In the case where a high-quality lock has 7 pin stacks and 8 possible key
heights, this technique would require a maximum of 49 key blanks, which
is within the realm of possibility. A lower quality lock with 5 pin stacks and
5 possible key heights would instead require no more than 20 key blanks.
Alternatively, the attacker could file the test keys down on the fly, requiring
only P key blanks.

Further Improvements

The search space in this case can be reduced even further, however, depend-
ing on the lock manufacturer. The maximum adjacent cut specification
(MACS) of a lock defines the maximum vertical distance allowed between
any two adjacent key cuts. If this distance is exceeded, the key will have
a steep spike that will be breakable, cause the lock to jam, or prevent a
pin from sitting properly. Removing all sequences that would violate the
MACS of a particular lock from the search space results in a significant
reduction in size. In addition, some master-keyed systems require that the
master key pins are higher on the pin stack than the change keys, which
further reduces the search space.
As another example of combinatorics at work, some brands of single-
dial combination padlocks have mechanical dependencies as a result of
the manufacturing process. As a result of these dependencies, it may be
possible to drastically reduce the number of combinations for testing. On
one brand, which has a dial ranging from 1 to 40 and requires a 3-number
combination, it is possible to reduce the search space from 60,000 (403 ) to
only 80, making a brute-force attack much more feasible.
It is important that single-dial combination locks have some sort of reset
mechanism that is triggered whenever someone attempts to open that lock
after trying a combination. If no such reset mechanism exists, the final digit
of the combination is essentially rendered useless, since it requires a trivial
amount of time to iterate through each final number, trying each one. This
is an example of a measure that prevents a reduction of the search space.

70
 Physical Security

3 Authentication Technologies

The authentication of individuals can be derived from something they know,

something they possess, and something they are. In this section, we dis-
cuss some physical means for achieving authentication through the use of
something a person possesses or something they are (namely, a healthy
human).

3.1 Barcodes

Printed labels called barcodes were developed around the middle of the
20th century as a way to improve efficiency in grocery checkout, and are
now used universally in applications as diverse as identifying wildlife.
First-generation barcodes represent data as a series of variable-width, ver-
tical lines of ink, which is essentially a one-dimensional encoding scheme.
(See Figure 8a.)
Some more recent barcodes are rendered as two-dimensional patterns
using dots, squares, or other symbols that can be read by specialized optical
scanners, which translate a specific type of barcode into its encoded infor-
mation. Among the common uses of such barcodes are tracking postage,
purchasing mass merchandise, and ticket confirmation for entertainment
and sporting events. (See Figure 8b.)

(a) (b)

Figure 8: Examples of barcodes: (a) A one-dimensional barcode. (b) A

two-dimensional barcode, which was used for postage.

71
 Physical Security

Barcode Applications

Since 2005, the airline industry has been incorporating two-dimensional

barcodes into boarding passes, which are created at flight check-in and
scanned before boarding. In most cases, the barcode is encoded with
an internal unique identifier that allows airport security to look up the
corresponding passenger’s record with that airline. Security staff then
verifies that the boarding pass was in fact purchased in that person’s name,
and that the person can provide photo identification. The use of a private,
external system prevents boarding passes from being forged, since it would
require an additional security breach for an attacker to be able to assign an
identifier to his or her own record with the airline.
In most other applications, however, barcodes provide convenience but
not security. Since barcodes are simply ink on paper, they are extremely
easy to duplicate. In addition, barcodes can be read from afar as long as the
ink is within line of sight of the attacker. Finally, once a barcode is printed,
it has no further ability to alter its encoded data. As a result, other mediums
were developed that allowed writing data as well as reading it.

3.2 Magnetic Stripe Cards

Developed in the late 1960s, the magnetic stripe card is one of the most per-
vasive means of electronic access control. Currently, magnetic stripe cards
are key components of many financial transactions, such as debit or credit
card exchanges, and are the standard format for most forms of personal
identification, including drivers’ licenses. These cards are traditionally
made of plastic and feature a stripe of magnetic tape contained in a plastic-
like film. Most cards adhere to strict standards set by the International
Organization for Standardization (ISO). These standards dictate the size
of the card, the location of the stripe, and the data format of the information
encoded into the stripe.
The magnetic stripe on standardized cards actually includes three tracks
for storing information. The first track is encoded using a 7-bit scheme,
featuring 6 bits of data and one parity bit per character, with a total of 79
characters. A parity bit is a bit whose value is a combinational function of
the others, such as exclusive-or. Since magnetic stripes cards can potentially
be worn down and subject to physical damage, the parity bit allows a stripe
reader to read a card even if there is a small amount of data loss.

72
 Physical Security

Magnetic Stripe Card Security

The first track of a magnetic stripe card contains the cardholder’s full name
in addition to an account number, format information, and other data at
the discretion of the issuer. This first track is often used by airlines when
securing reservations with a credit card.
The second track is encoded using a 5-bit scheme (4 bits of data and
1 parity bit per character), with a total of 40 characters. This track may
contain the account number, expiration date, information about the issuing
bank, data specifying the exact format of the track, and other discretionary
data. It is most often used for financial transactions, such as credit card or
debit card exchanges.
The third track is much less commonly used.
One vulnerability of the magnetic stripe medium is that it is easy to read
and reproduce. Magnetic stripe readers can be purchased at relatively low
cost, allowing attackers to read information off cards. When coupled with a
magnetic stripe writer, which is only a little more expensive, an attacker can
easily clone existing cards. Because of this risk, many card issuers embed
a hologram into the card, which is harder to reproduce. Most credit cards
also include space for a customer signature, verifying the authenticity of
the card. Unfortunately, many vendors do not always check this signature.
One effective deterrent against card fraud is a requirement for additional
information known only to the owner, such as a personal identification
number (PIN).
ISO standards do not permit vendors to store money on magnetic stripe
cards. Account numbers can be stored instead, which can be used to
access information in remote databases. Still, many organizations use cards
that store contents of monetary value. For example, transportation tickets
often store “money” that is only available for payment of transportation
fees. So, vendors sometimes use proprietary technology that provides
the convenience of storing data on a magnetic stripe in a format storing
“points” or “credits” on the card that have monetary value.
Unfortunately, the use of a format that allows the cards to contain data
that actually has a monetary value poses serious security risks. Because the
money on the card is simply represented by data, attackers who know the
format of the information on the stripe could create their own cards and
provide themselves with free services. For this reason, it is essential that
vendors protect the secrecy of their data format specifications and provide
some means of validating data integrity, such as employing a cryptographic
signature algorithm.

73
 Physical Security

3.3 Smart Cards

Traditional magnetic stripe cards pose a number of security problems be-
cause they are relatively easy to duplicate and because there is no stan-
dardized mechanism for protecting the information contained on a card.
Solutions to both of these problems are provided by smart cards, which
incorporate an integrated circuit, optionally with an on-board microproces-
sor. This microprocessor features reading and writing capabilities, allowing
the data on the card to be both accessed and altered. Smart card technology
can provide secure authentication mechanisms that protect the information
of the owner and are extremely difficult to duplicate.
Smart cards do not suffer from the inherent weaknesses of the magnetic
stripe medium. They are by design very difficult to physically disassemble,
and an internal cryptoprocessor can provide data protection that simple
stripes cannot. Most security problems in smart cards are a result of
weaknesses in a specific implementation, not the basic technology itself.
First-generation smart cards require the integrated circuit to actually
contact a reading device in order to access or alter information. This
restricts the information on the card to those with physical access. A new
generation of smart cards instead relies on radio frequency technology to
allow contactless interaction of a smart card and a reading device. The
introduction of this capability exposes smart cards to similar security risks
as another popular technology, RFID, which is discussed in Section 3.4.

Smart Card Applications

Today, smart cards are used for a wide variety of applications. They are
commonly employed by large companies and organizations as a means of
strong authentication, often as a part of a single sign-on scheme. Some
credit companies have begun embedding smart cards into their credit cards
to provide more secure customer protection. In addition, many computer
disk encryption technologies rely on smart cards for the storage of an
external encryption key.
Smart cards may also be used as a sort of “electronic wallet,” containing
funds that can be used for a variety of services, including parking fees,
public transport, and other small retail transactions. Current implementa-
tions of these types of smart cards provide no verification of ownership,
so an attacker in possession of a stolen smart card can use it as if he were
the owner. In all electronic cash systems where this is the case, however,
the maximum amount of cash permitted on the card is low, to limit any
possibility of serious fraud.

74
 Physical Security

Smart Card Security

While most sophisticated smart cards feature a microprocessor that allows
them to perform some computational work and alter the contents of the
card, other less expensive versions simply contain a memory card, with no
ability to alter the contents without an external writer. Many phone cards
actually contain a monetary amount encoded on the card, for instance.
To prevent cloning and unauthorized alteration, most cards require that
a secret authentication code be presented to a microcontroller reader/writer
before memory can be written to a card. In addition, many phone cards
authenticate themselves to the phone network using a unique serial number
or PIN mechanism before any transfer of funds takes place, making them
more difficult to clone.

Simple Attacks on Smart Cards

Unfortunately, if a phone card’s secret code can be extracted, it may be
possible to tamper with the monetary value on the card. Possible attacks
include a social engineering approach (trying to recover the code from
employees of the phone company) or eavesdropping on communications
between a card and its reader.

Differential Power Analysis

In addition, even smart cards with secure cryptoprocessors can be subject
to a side channel attack known as differential power analysis. In this
attack, a malicious party records the power consumption of a smart card’s
microprocessor while it is performing cryptographic operations. Because
various operations on a processor require minutely different amounts of
power consumption, it may be possible to statistically analyze this recorded
information in order to reveal information about the cryptosystem or the
underlying cryptographic key that is being processed. In some cases,
this attack can be used to actually recover the secret key, breaking the
cryptosystem.
Since power analysis attacks are passive in that they do not alter the
operation of the analyzed processor, they are difficult to detect and prevent.
As such, in order to prevent this type of attack, hardware designers must
ensure that any information that could be gained by power analysis is
insufficient to compromise the underlying cryptosystem. One way this is
done is to include useless operations in conditional branches, so that the
time and power consumed does not reveal much information about input
values.

75
 Physical Security

SIM Cards
Many mobile phones use a special smart card called a subscriber identity
module card (SIM card), as show in Figure 9. A SIM card is issued by a
network provider. It maintains personal and contact information for a user
and allows the user to authenticate to the cellular network of the provider.
Many phones allow the user to insert their own SIM card, making the
process of switching phones simple and instantaneous. Standards for SIM
cards are maintained by the Global System for Mobile Communications
(GSM), which is a large international organization.

Figure 9: A SIM card used in a GSM cell phone, together with a dime to
show size. Photo by Dan Rosenberg included with permission.

SIM Card Security

SIM cards contain several pieces of information that are used to identify
the owner and authenticate to the appropriate cell network. Each SIM card
corresponds to a record in the database of subscribers maintained by the
network provider. A SIM card features an integrated circuit card ID (IC-
CID), which is a unique 18-digit number used for hardware identification.
Next, a SIM card contains a unique international mobile subscriber iden-
tity (IMSI), which identifies the owner’s country, network, and personal
identity. SIM cards also contain a 128-bit secret key. This key is used for
authenticating a phone to a mobile network, as discussed below. Finally,
SIM cards may contain a contacts list.
As an additional security mechanism, many SIM cards require a PIN
before allowing any access to information on the card. Most phones re-
quiring the use of a PIN automatically lock after three incorrect password
attempts. At this point, the phone can only be unlocked by providing an
8-digit personal unblocking key (PUK) stored on the SIM card. After ten
incorrect PUK attempts, the SIM card is permanently locked and must be
replaced.

76
 Physical Security

GSM Challenge-Response Protocol

When a cellphone wishes to join a cellular network to make and receive

calls, the cellphone connects to a local base station owned by the network
provider and transmits its IMSI to declare its identity. If the IMSI corre-
sponds to a subscriber’s record in the network provider’s database, the base
station transmits a 128-bit random number to the cellphone. This random
number is then encoded by the cellphone with the subscriber’s secret key
stored in the SIM card using a proprietary encryption algorithm known as
A3, resulting in a ciphertext block that is sent back to the base station. The
base station then performs the same computation, using its stored value
for the subscriber’s secret key. If the two ciphertexts match, the cellphone
is authenticated to the network and is allowed to make and receive calls.
This type of authentication is known as a challenge-response protocol. (See
Figure 10.)

IMSI = (this phone’s ID)

R = a 128-bit random number (the challenge)

EK(R) = the 128-bit random number encrypted

using
g the subscriber’s secret key
yK
(the response)

Figure 10: The challenge-response protocol between a cellphone (together

with its SIM card) and a cell tower. The security of this protocol is de-
rived from the fact that only the phone and the tower should know the
subscriber’s key. (cell phone) © Miguel Angel Salinas/Shutterstock; (antenna
tower) © Igor Nazarenko/Shutterstock

After a SIM card has been authenticated to the network, the SIM card
A8.
produces a 64-bit ciphering key by encoding the user’s key and the previ-
ously sent random number, using another secret algorithm known as
Finally, the phone is ready to make the call, and all communications are
encrypted using the ciphering key with A5, another proprietary algorithm.
Initially, each of the algorithms used in protecting cellphone communi-
cation (A3, A5, and A8) were proprietary algorithms developed by GSM,
and were closely kept secrets. These proprietary algorithms were chosen
over other public options, such as 3DES or AES, because the newly de-
veloped algorithms were optimized for cell phone hardware at the time
and had significantly better performance. In many phones, the A3 and A8
algorithms are implemented as a single algorithm, known as COMP128.

77
 Physical Security

GSM Vulnerabilities

Older SIM cards feature an implementation of COMP128 now known as

COMP128-1, which was reverse-engineered and found to be cryptographi-
cally insecure. A weakness in the algorithm reveals information about the
key, given a suitable input, allowing an attacker to recover a SIM card’s key
by rapidly issuing requests and examining the card’s output over the course
of several hours. This attack could be performed over the air, without the
need for physical access to the phone.
If the internal key is recovered from a phone by breaking COMP128,
cloning the SIM card is relatively simple, allowing an attacker to use a
victim’s account to place phone calls. Newer versions of COMP128, dubbed
COMP128-2 and COMP128-3, have not been broken in this way, however,
and as such are not vulnerable to this type of attack. Still, because the im-
plementations of these algorithms are secret, there is little proof of security
beyond GSM’s assurances.
Security flaws have also been discovered in implementations of the A5
algorithm, which is used to encrypt the actual transmission of data and
voice over cell phone networks. Several cryptographic weaknesses have
been identified in A5/1 (the most common version of the A5 algorithm),
which allow an attacker with extensive resources to break it. Compromise
of the A5 algorithm could allow an attacker to eavesdrop on cell phone
communications, a major security concern given the ubiquitous use of cell
phones in our society. Another implementation, known as A5/2, was
designed with heavy input by intelligence agencies to ensure breakability,
and was deployed only in specific countries in Eastern Europe and Asia.
Unfortunately, it was proven that the algorithm can be easily cracked. His-
torically, A5/1 and A5/2 were initially kept secret, but they have eventually
become public knowledge due to reverse engineering.
The weaknesses in COMP128 and A5 demonstrate again the risks of
security by obscurity—the idea that a cryptographic algorithm is safe from
being broken if it is kept secret, which contradicts the open design security
principle. Indeed, this approach is dangerous, because algorithms can
often be reverse-engineered. In addition, the people who work on pro-
gramming such algorithms may leak their design, either deliberately or by
accident. An algorithm is much more likely to leak out than cryptographic
keys, for instance, since an algorithm is always fixed and determined,
whereas keys are ever changing. Fortunately, because of the past reverse-
engineered attacks, future cell phone encryption methods are more likely
to be based on open standards. Because of the heavy public scrutiny placed
on standard cryptographic algorithms, there is higher confidence in their
security.

78
 Physical Security

3.4 RFIDs

The use of radio frequency identification, or RFID, is a rapidly emerg-

ing technology that relies on small transponders to transmit identification
information via radio waves. Like contactless smart cards, RFID chips
feature an integrated circuit for storing information, and a coiled antenna
to transmit and receive a radio signal. (See Figure 11.)

Figure 11: An RFID tag, taken from a DVD package, together with a dime
to show size. Photo by Dan Rosenberg included with permission.

Like smart cards, RFID tags must be used in conjunction with a separate
reader or writer. While some RFID tags require a battery, many are passive
and do not. The effective range of RFID varies from a few centimeters to
several meters, but in most cases, since data is transmitted via radio waves,
it is not necessary for a tag to be in the line of sight of the reader.
This technology is being deployed in a wide variety of applications.
Many vendors are incorporating RFID for consumer-product tracking, to
either supplement or replace barcodes. Using RFID tags, a retailer can track
which items are selling best as well as use the tags for theft detection, just
by putting an RFID reader around the entrance to the shop. In addition,
RFID provides an advantage over barcodes in that chips are much more
difficult to replicate than simple ink on paper. Incidentally, RFID chips are
also used to identify and track animals in the wild.
Because RFID chips operate using radio waves, they can release infor-
mation without the need for direct physical contact. As such, it is crucial
that some mechanism is employed to protect the information contained on
RFID chips from unauthorized readers. If no such mechanism were used, a
malicious party could easily steal personal information from a distance.

79
 Physical Security

Hopping Codes and Remote Automobile Entry

Most modern vehicles feature a key fob that allows the owner to lock, un-
lock, or even start the engine of the vehicle from a distance. These fobs use
RFID technology to communicate with a receiver in the car. Similar devices
are commonly used to allow a driver to remotely open gates or garage
doors. Several security measures are in place to prevent an attacker from
eavesdropping on an RF transmission and recreating the signal, gaining
access to the vehicle or property. The controller chips in the key fob and the
receiver in the vehicle use what is known as a hopping code or rolling code
to accomplish this. The controllers use the same pseudo-random number
generator, so that each device produces the same sequence of unpredictable
numbers.
The challenge is to keep the two sequences synchronized. When the
owner presses a button, say, to unlock doors, the key fob transmits its
hopping code—the next number in the key fob’s sequence (along with a
command instructing the car to open its doors). The receiver in the car
stores a list of the next 256 hopping codes in its sequence, starting from
the last time the key fob and the car synchronized their sequences. If the
hopping code sent by the key fob matches one of these 256 codes, then
the receiver accepts the command and performs the requested action. The
receiver then updates its sequence to the next 256 numbers after the one just
sent by the key fob. Once a number is used, it is never used again. Thus,
even if an attacker can eavesdrop on the communication between the key
fob and the car, he cannot reuse that number to open the car.
The receiver keeps a list of 256 numbers in case the fob and the receiver
become desynchronized. For example, if the button on the key fob is
pressed while it is out of range of the receiver, it uses up the next number in
its sequence. In the event that a fob is used more than 256 times while out
of range, the receiver will no longer accept its transmissions and the two
will need to be resynchronized using a factory reset mechanism.
Because hopping codes are essentially random numbers, it is extremely
unlikely that a key fob would be able to successfully execute a command on
an unmatched receiver. Nevertheless, even though an eavesdropper cannot
reuse a successful communication between a key fob and its receiver, an
attack might be able to capture and replay a signal transmitted while the
fob is out of range. In this case, the receiver will not have incremented
its list of 256 acceptable hopping codes. To take advantage of this, some
car thieves employ a technique where they jam the radio channel used by
a key fob and simultaneously capture the transmission. This prevents the
owner from using their key fob but allows the attacker to unlock or start
the victim’s car by replaying the captured signal.

80
 Physical Security

KeeLoq

More recently, the actual algorithms that generates hopping codes have
been subject to cryptographic attacks. The most common algorithm em-
ployed to generate the pseudo-random codes is known as KeeLoq, a pro-
prietary algorithm designed specifically for RFID hardware. The algorithm
requires a 32-bit key, which is then used to encrypt an initialization vector,
which in turn is incremented with each use.
Researchers have developed attacks on KeeLoq stemming from com-
mon key bits being used in certain car models. These attacks allowed
to reconstruct a fob’s encryption key, given a high number of captured
transmissions and several days of computing time. Subsequently, a side-
channel attack completely broke the KeeLoq system by measuring the
power consumption of a key fob during the encryption process and using
this information to recover the encryption key. Once the attacker had
acquired this key, it was possible to clone a remote entry fob after inter-
cepting two consecutive transmissions. It was also demonstrated that it
was possible to use this attack to reset the internal counter of the receiver,
effectively locking owners out of their cars or garages. These weaknesses
in the algorithm have been addressed by increasing the size of the KeeLoq
key to 60 bits, which prevents these attacks, but this change has yet to be
implemented on a mass scale.

Digital Signature Transponder

Several automobile key fobs and tags for automatic payment systems at gas
stations use an RFID device called Digital Signature Transponder (DST),
which is manufactured by Texas Instruments. A DST stores a 40-bit secret
key and incorporates a proprietary encryption algorithm called DST40.
The main use of a DST is to execute a simple challenge-response protocol,
similar to the one for GSM phones (see Figure 10), where the reader
asks the DST to encrypt a randomly generated challenge to demonstrate
possession of the secret key.
Confirming once again the failure of “security by obscurity,” the DST40
algorithm has been reverse engineered and an attack that recovers the secret
key from two responses to arbitrary challenges has been demonstrated.
This attack allows to create a new device that fully simulates a DST and
can be used to spoof a reader (e.g., to charge gas purchases to the account
of the DST owner).

81
 Physical Security

Electronic Toll Systems

Electronic toll systems allow motor vehicle owners to place an RFID tag
near their dashboards and automatically pay tolls at designated collection
sites. These systems provide great convenience, since they remove the
hassle of dealing with cash and allow drivers to be tolled without coming
to a stop. Unfortunately, many implementations of electronic toll collection
systems provide no encryption mechanism to protect the contents of the
RFID tag.
Because the tag only contains a unique identifier that toll collection sites
use to deduct money from an account, it is not possible to actually alter the
money stored on a user’s account. Still, many tags may be easily cloned,
allowing a malicious party to impersonate a victim and charge tolls to their
account. In addition, it may be possible to create a “digital alibi” in the
event of a crime, if an attacker clones their own tag and places it on another
person’s automobile. If checked, the cloned tag may provide false evidence
that the attacker was not at the scene of the crime.
A typical defense mechanism against cloning attacks is to install cam-
eras to capture photographs of the license plates of vehicles that pass
through toll collection sites. This approach also allows authorities to iden-
tify and impose fines on drivers with missing or expired tags.

Passports

As another example, modern passports of several countries, including the

United States, feature an embedded RFID chip that contains information
about the owner, including a digital facial photograph that allows airport
officials to compare the passport’s owner to the person who is carrying the
passport. (See Figure 12.)
In order to protect the sensitive information on the passport, all RFID
communications are encrypted with a secret key. In many instances, how-
ever, this secret key is merely the passport number, the holder’s date of
birth, and the expiration date, in that order. All of this information is
printed on the card, either in text or using a barcode or other optical storage
method. While this secret key is intended to be only accessible to those with
physical access to the passport, an attacker with information on the owner,
including when their passport was issued, may be able to easily reconstruct
this key, especially since passport numbers are typically issued sequentially.
In addition, even if an attacker cannot decrypt the contents of an embedded
RFID chip, it may still be possible to uniquely identify passport holders and
track them without their knowledge, since their secret key does not change.

82
 Physical Security

RFID chip and

antenna is embedded
in the cover

e-Passport
symbol

Figure 12: An e-passport issued by the United States of America.

(RFID) © Benjamin Haas/Shutterstock; (passport) © Charles Taylor/
Shutterstock

To prevent unauthorized parties from reading private information from

afar without an owner’s knowledge, the covers of some RFID passports
contain materials that shield the passport from emitting radio waves while
it is closed. Even so, these measures can be circumvented if the passport
is open slightly. For example, if a passport’s owner is keeping additional
papers or money inside the passport, it may leak radio waves.

3.5 Biometrics

The term biometric in security refers to any measure used to uniquely

identify a person based on biological or physiological traits. In general,
biometric systems may be used to supplement other means of identification
(biometric verification), or they may provide the sole means of authentica-
tion (biometric identification). Generally, biometric systems incorporate
some sort of sensor or scanner to read in biometric information and then
compare this information to stored templates of accepted users before
granting access.

83
 Physical Security

Requirements for Biometric Identification

There are several requirements that must be met for a characteristic to be
consider usable as biometric identification:
• Universality. Almost every person should have this characteristic.
For example, the presence of a birthmark would not be acceptable bio-
metric identification, because many people do not have birthmarks.
Fingerprints, on the other hand, are universal.
• Distinctiveness. Each person should have noticeable differences in
the characteristic. For example, retinal images and DNA are distinc-
tive, fingerprints are mostly distinctive, and the presence or absence
of tonsils is not distinctive.
• Permanence. The characteristic should not change significantly over
time. For instance, fingerprints and DNA have permanence; hair
color and weight do not (even though they are commonly reported
on government-issued IDs).
• Collectability. The characteristic should have the ability to be effec-
tively determined and quantified.
Other considerations, which are desirable but not absolutely necessary,
include performance (the accuracy and speed of recognition), acceptability
(whether or not people are willing to accept the use of the biometric char-
acteristic), and circumvention (the degree to which the characteristic can
be forged or avoided). The ideal biometric system would satisfy all of these
requirements, both the required and desired ones, but real-life systems tend
to be lacking in some of these areas.

How Biometric Identification is Done

One of the most important aspects of any biometric system is the mecha-
nism used to actually verify a match between a user and a stored biometric
template. Systems may use several techniques to perform this sophisticated
pattern matching. It would be unreasonable to expect a provided biometric
sample to match up exactly with a stored template, due to slight changes
in biometric features and small errors in the sample collection. Some
level of flexibility must be achieved in order for the system to work at all.
Nevertheless, the system must be precise enough that false matches do not
occur, allowing unauthorized users to gain access to restricted resources.
Typically, this is accomplished by converting attributes of a biometric
sample into a feature vector—a set of data values corresponding to essen-
tial information about the sample, and comparing that vector to a stored
reference vector, which is a feature vector of a previous biometric sample
that the system is trying to test against. (See Figure 13.)

84
 Physical Security

Reader
Biometric

Feature vector

Comparison algorithm

Reference vector

matches
t h d
doesn’t
’t match
t h

Figure 13: The verification process for a biometric sample. A biometric

sample is converted into a feature vector and that vector is compared
against a stored reference vector. If the similarity is good enough, then the
biometric sample is accepted as being a match. (“Biometric”) © MarFot/
Fotolia, LLC–Royalty Free; (“Reader”) © Andrew Brown/Fotolia, LLC–Royalty
Free; (“Comparison algorithm”) © Norman Chan/Shutterstock

Generating Feature Vectors

Fingerprint pattern matching works by comparing the locations and ori-

entations of key features in the fingerprint, such as ridge endings and
bifurcations (splits in a line), while allowing for a small margin of error.
Facial pattern matching is much more complex. Usually, the face is adjusted
computationally so that it appears to be looking directly at the camera.
Next, a feature vector is generated by calculating the location of distinct
facial features, such as the ridge of the eyebrows, the edges of the mouth,
the tip of the nose, and eyes. Using advanced techniques such as elastic
graph theory or neural networks, this feature vector is compared to stored
templates to assess the possibility of a match. Other types of biometric
authentication may use different techniques to check for a match, but there
is always the crucial step of generating a feature set that allows a reader to
perform computational comparisons between biometric samples.

85
 Physical Security

Candidate Biometric Characteristics

The most common biometric information is a person’s signature, which

is intended to be unique for each person. Even so, not everyone has a
prepared signature, and such a signature may change over time, or may
be easy to forge. Because of these limitations, signatures are not effective as
a secure means of biometric authentication.
Fingerprints have been used in forensic work since the mid-19th century
to identify criminals, but more recently, fingerprint scanners have been
incorporated into electronic authentication systems as a means of granting
access to specific users. Unlike signatures, fingerprints are universal except
in rare cases, unique, easily collected and analyzed, and difficult to circum-
vent, making them an effective biometric characteristic. While fingerprints
may change slightly over time, the degree to which they change does not
affect a biometric system’s ability to identify the owner.
Voice recognition does not score as well. While most people have a
voice and are willing to use it as a means of authentication, it is often not
distinctive enough to differentiate from another person’s voice. In addition,
the human voice changes significantly from year to year, and voice recog-
nition systems can be easily circumvented using a sound recording of an
authorized user.
Another common biometric system uses a person’s eyes as a unique
characteristic. These types of scans satisfy universality, distinctiveness,
permanence, and collectability, and are very difficult to circumvent. Older
systems employ retinal scanning, which involves illuminating the eye with
a bright sensor and capturing an image of the blood vessels in the back
of the eye. Many users find retinal scanning uncomfortable or invasive,
and would prefer other means of authentication. Iris scanning systems
are generally better received, providing equally strong authentication by
taking a high-quality photograph of the surface of the eye.
Other biometric systems are more commonly used to identify people in
public, rather than provide authentication for a select pool of users. For
example, the United States government is funding research in technologies
that can identify a person based on facial characteristics and gait (the
unique way that a person walks), for use in applications such as airport
security. The advantage of these techniques in a surveillance context is that
they do not require a subject’s cooperation, and can be conducted without
a subject’s knowledge.
Nevertheless, current implementations of these technologies are not
very effective. Face recognition is not especially accurate, and does not
perform well under many conditions, including poor lighting or situations
where the subject’s face is captured at an angle rather than straight-on. In

86
 Physical Security

addition, wearing sunglasses, changing facial hair, or otherwise obstructing

the face can foil facial recognition technology. Similarly, a person can
defeat gait recognition by simply altering the way they walk. With further
development, however, these surveillance techniques may become more
accurate and difficult to circumvent.

Privacy Concerns for Biometric Data

The storage of biometric data for authentication purposes poses a number
of security and privacy concerns. Access to stored biometric data may allow
an attacker to circumvent a biometric system or recover private information
about an individual. Since biometric data does not change over time, once
a person’s biometric data is compromised, it is compromised forever. As
such, encryption should be used to protect the confidentiality of biometric
data, both in storage and transmission. This security requirement poses a
unique problem, however.
A biometric sample provided to a system by a user is not expected to
match the stored template exactly—small discrepancies are expected, and
allowing for these discrepancies is necessary for the system to function
correctly. Thus, the comparison function between a fresh feature vector and
a stored reference vector must be done to allow for slight differences, but
it should also be ideally performed in a way that avoids a confidentiality
breach.
The standard method of storing a cryptographic hash of a value to
be kept private does not work for biometric applications. For example,
suppose that we store a cryptographic hash of the reference vector obtained
from the biometric template and we compare it with the cryptographic hash
of the feature vector obtained from the biometric sample collected. The
comparison will fail unless the sample and template are identical. Indeed
standard cryptographic hash functions, such as SHA-256, are not distance
preserving and are very sensitive to even small changes in the input.
Recently, various methods have been proposed that support efficient
biometric authentication while preserving the privacy of the original bio-
metric template of the user. One the approaches consists of extending the
concept of a message authentication code (MAC) to that of an approximate
message authentication code (AMAC), which has the following properties:
• Given the AMACs of two messages, it is possible to determine effi-
ciently whether the distance between the original messages is below
a certain preestablished threshold δ.

• Given the AMAC of a message, it is computationally hard to find any

message within distance δ from it.

87
 Physical Security

4 Direct Attacks Against Computers

Acquiring physical access to a computer system opens up many avenues
for compromising that machine. Several of these techniques are difficult
to prevent, since hardware manufacturers generally assume that the user
is a trusted party. This vulnerability to physical, direct access to computers
further emphasizes the need for secure access control measures that prevent
physical access to sensitive computer systems. Likewise, the mere fact that
computing equipment is ultimately physical implies a number of environ-
mental considerations as well.

4.1 Environmental Attacks and Accidents

Computing equipment operates in a natural environment and if this envi-
ronment is significantly altered, then the functionality of this computing
equipment can be altered, sometimes significantly. The three main compo-
nents of a computing environment are the following:
• Electricity. Computing equipment requires electricity to function;
hence, it is vital that such equipment has a steady uninterrupted
power supply. Power failures and surges can be devastating for
computers, which has motivated some data centers to be located next
to highly reliable hydroelectric plants.
• Temperature. Computer chips have a natural operating temperature
and exceeding that temperature significantly can severely damage
them. Thus, in addition to having redundant fire-protection de-
vices, high-powered supercomputers typically operate in rooms with
massive air conditioners. Indeed, the heating, ventilating, and air
conditioning (HVAC) systems in such rooms can be so loud that it
is difficult for people to hear one another without shouting.
• Limited conductance. Because computing equipment is electronic,
it relies on there being limited conductance in its environment. If
random parts of a computer are connected electronically, then that
equipment could be damaged by a short circuit. Thus, computing
equipment should also be protected from floods.
For example, accidentally dropping one’s cellphone into a pot of boiling
spaghetti will likely damage it beyond repair. In general, the protection of
computing equipment must include the protection of its natural environ-
ment from deliberate and accidental attacks, including natural disasters.

88
 Physical Security

4.2 Eavesdropping
Eavesdropping is the process of secretly listening in on another person’s
conversation. Because of this threat, protection of sensitive information
must go beyond computer security and extend to the environment in which
this information is entered and read. Simple eavesdropping techniques
include using social engineering to allow the attacker to read informa-
tion over the victim’s shoulder, installing small cameras to capture the
information as it is being read, or using binoculars to view a victim’s
monitor through an open window. These direct observation techniques are
commonly referred to as shoulder surfing. Simple eavesdropping can be
prevented by good environmental design, such as avoiding the placement
of sensitive machines near open windows. Nonetheless, more complex
techniques of eavesdropping have emerged that are more difficult to pre-
vent.

Wiretapping
Given physical access to the cables of a network or computer, it may be
possible for an attacker to eavesdrop on all communications through those
cables. Many communication networks employ the use of inexpensive
coaxial copper cables, where information is transmitted via electrical im-
pulses that travel through the cables. Relatively inexpensive means exist
that measure these impulses and can reconstruct the data being transferred
through a tapped cable, allowing an attacker to eavesdrop on network
traffic. These wiretapping attacks are passive, in that there is no alteration
of the signal being transferred, making them extremely difficult to detect.
(See Figure 14.)

Figure 14: Wiretapping.

89
 Physical Security

Defenses Against Wiretapping

Many networks, including much of the telephone network and most com-
puter networks, use twisted pair cables, which feature two wires, usually
copper, that are entwined to eliminate electromagnetic interference. Un-
shielded twisted pair (UTP) cable is inexpensive compared to coaxial or
fiber optic cable. These cables are subject to the same types of signal leakage
attacks as coaxial cable, without a loss of signal strength.
A more common and less expensive approach, however, is to briefly
disconnect an Ethernet cable, insert a passive wiretapping device, and
reconnect it. While this may go undetected by human users, many intrusion
detection systems are triggered by the disconnection of network cables.
High-security networks often employ the use of fiber optic cable as
a more secure alternative. Fiber optic cables transmit light rather than
electricity, which prevents the signal leakage that occurs in coaxial cable.
It is still sometimes possible to eavesdrop on communications transmitted
over fiber optic cable, however. An attacker can place a fiber optic cable in
a micro-bend clamping device, which holds the cable in a bent position,
where it leaks a tiny amount of light. An attached photo sensor can
transmit the information via an optical-electrical converter, where it can be
reinterpreted by a computer. This attack results in a tiny drop in the signal
being transmitted over the network, so it may be detected by fiber optic
intrusion detection systems. More advanced attacks may employ means of
reboosting the signal to make up for this signal drop.
Both of these attacks demonstrate the importance of protecting not
only computer systems, but also the network cables over which sensitive
information is transmitted. Attacks on fiber optic cables are expensive and
may be detected, but are still a possibility. Many organizations use end-
to-end encryption to protect data being transmitted over the network—
eavesdropping is rendered useless if the contents are not readable by the
attacker.

Radio Frequency Emissions

One of the earliest techniques of computer eavesdropping gained

widespread attention through the 1985 publication of a paper by Dutch
computer researcher Wim van Eck. Cathode Ray Tube (CRT) displays, used
by older computer monitors, emit electromagnetic radiation in the Radio
Frequency (RF) range.

90
 Physical Security

Van Eck demonstrated that these emissions could be read from a dis-
tance and used to reconstruct the contents of a CRT screen. Since RF
emissions can travel through many nonmetallic objects, computer monitors
could be read regardless of whether they are within eye-shot of an attacker.
More recent research has extended this principle to modern Liquid
Crystal Display (LCD) screens. Fortunately, preventative measures have
been developed that utilize techniques to shield monitors and reduce these
emissions, but they are rarely deployed outside of high-security govern-
ment applications, due to a low prevalence of this type of attack and the
expensive cost of equipment necessary to perform it. In an environment
where other attacks are impossible due to security measures, however, this
form of eavesdropping is certainly within the realm of possibility.

Optical Emissions
A more recent attack has emerged that allows eavesdropping using emis-
sions in the range of visible light, rather than the RF range. The attack
requires the use of a photosensor, which is relatively cheap compared to
the expensive equipment needed for an RF eavesdropping attack. CRT
displays work by using an electron beam that scans the surface of the
screen, refreshing each pixel individually at incredibly fast speeds. At the
moment the electron beam hits a pixel, there is a brief burst of brightness,
which makes this attack possible. A photosensor can be trained on a wall in
the room, and by analyzing changes in the light of the room and applying
imaging technology to reduce “noise,” it is possible to reconstruct an image
of the contents of the screen. This attack has been proven to work from up to
50 meters away, requiring only that the attacker can train a photosensor on
any wall in the room. Fortunately, since the attack relies on visible light, as
long as a room is not in an attacker’s line of sight, it is safe from this attack.
Also, this attack does not work on LCD monitors, because of differences
in how pixels are refreshed on the screen. Like RF eavesdropping, this
attack is possible, but considered unlikely to occur in most contexts, and,
especially with the advent of LCD screens, it is not expected to be a high-
priority security concern in the future.

Acoustic Emissions
In addition to RF radiation and visible light, computer operations often
result in another byproduct, sound. Recent research has proven it possible
to use captured acoustic emissions to compromise computer security. These
techniques are still in their infancy, so they are unlikely to occur outside a
lab, but they may become security concerns later on.

91
 Physical Security

Dmitri Asonov and Rakesh Agrawal published a paper in 2004 detailing

how an attacker could use an audio recording of a user typing on a key-
board to reconstruct what was typed. (See Figure 15.) Each keystroke has
minute differences in the sound it produces, and certain keys are known
to be pressed more often than others. After training an advanced neural
network to recognize individual keys, their software recognized an average
79% of all keystrokes.

sound recording
device

microphone to
capture keystroke
sounds

Figure 15: A schematic of how a keyboard acoustic recorder works.

Also in 2004, researchers Adi Shamir and Eran Tromer conducted an

experiment that demonstrated the possibility of revealing a machine’s CPU
instructions by analyzing acoustic emissions from the processor. In theory,
this may provide attackers with additional information about the inner
workings of a computer, including exposing which routine or program is
being executed to perform a certain task. In addition, information can be
gathered to attack cryptographic functions, such as the algorithm used and
the time required for each computation.

Hardware Keyloggers
A keylogger is any means of recording a victim’s keystrokes, typically
used to eavesdrop passwords or other sensitive information. There are
many ways of implementing software keyloggers. A newer innovation,

92
 Physical Security

however, is the hardware keylogger. Hardware keyloggers are typically

small connectors that are installed between a keyboard and a computer.
For example, a USB keylogger is a device containing male and female USB
connectors, which allow it to be placed between a USB port on a computer
and a USB cable coming from a keyboard. (See Figure 16.)

Figure 16: A schematic of how a USB keylogger works.

By including circuits that capture keystrokes and store them in a flash

memory, a hardware keylogger can collect and store all the keystrokes
coming from the keyboard over an extended period of time. An attacker can
install a device like this in an Internet cafe, leave it to collect keystrokes for
a week or more, and then come back to retrieve the device and download
all the keystrokes. Thus, an attacker using such a device can hope to collect
passwords and other personal information from the people who use the
compromised keyboard.

While some advanced hardware keyloggers transmit captured text via

wireless technology, most rely on the attacker’s ability to retrieve them at
a later date. After installing the device, it is completely undetectable by
software, and since it operates at the hardware level, it can even record
BIOS passwords entered before booting to the operating system. Because
of this stealth, the best detection method is simple physical inspection, and
the most effective preventative measure is employing strict access control
to prevent physical access to sensitive computer systems.

93
 Physical Security

4.3 TEMPEST
TEMPEST is a U.S. government code word for a set of standards for
limiting information-carrying electromagnetic emanations from computing
equipment. More broadly, the term “TEMPEST” has come to be used for
the study, limitation, and protection of all types of information-carrying
emanations that come from computing equipment and devices. In terms of
a standard, TEMPEST establishes three zones or levels of protection:
1. An attacker has almost direct contact with the equipment, such as in
an adjacent room or within a meter of the device in the same room.

2. An attacker can get no closer than 20 meters to the equipment or is

blocked by a building to have an equivalent amount of attenuation.

3. An attacker can get no closer than 100 meters to the equipment or is

blocked by a building to have an equivalent amount of attenuation.
To achieve the limits imposed by these three levels of protection, engineers
can use emanation blockage and/or emanation modification.

Emanation Blockage
One approach to limiting the release of information-carrying emanations is
to enclose the computing equipment in a way that blocks those emanations
from escaping into the general environment. Some examples of this type of
emanation limitation include the following:
• To block visible light emanations, we can enclose sensitive equipment
in a windowless room.

• To block acoustic emanations, we can enclose sensitive equipment in

a room lined with sound-dampening materials.

• To block electromagnetic emanations in the electrical cords and ca-

bles, we can make sure every such cord and cable is grounded, so as
to dissipate any electric currents traveling in them that are generated
from external (information-carrying) electromagnetic fields created
by sensitive computing equipment.

• To block electromagnetic emanations in the air, we can surround

sensitive equipment with metallic conductive shielding or a mesh
of such material, where the holes in the mesh are smaller than the
wavelengths of the electromagnetic radiation we wish to block. Such
an enclosure is known as a Faraday cage. (See Figure 17.)

94
 Physical Security

Figure 17: An example Faraday cage. (Image by M. Junghans; licenced

under the terms of the GNU Free Documentation License, Version 1.2.)

In order for these emanation blockage techniques to work, the sensitive

computing equipment (including all its cables and junction boxes) have
to be completely enclosed. Examples of such enclosures range from a
classified office building, which is completely enclosed in a copper mesh
and has two-pass copper doors for entering and exiting, to a metal-lined
passport wallet, which encloses an RFID passport in a small Faraday cage
so as to block unwanted reading of the RFID tag inside it.

Emanation Masking

Another technique for blocking information-carrying electromagnetic ema-

nations is to mask such emanations by broadcasting similar electromagnetic
signals that are full of random noise. Such emanations will interfere with
the information-carrying ones and mask out the information in these sig-
nals by introducing so much noise that the information-carrying signal is
lost in the cacophony.

95
 Physical Security

4.4 Live CDs

A live CD is an operating system that can be booted from external media

and resides in memory, without the need for installation. It can be stored
on a CD, DVD, USB drive or any other removable drive from which the
computer can boot. There are many legitimate uses for live CDs, including
diagnostic and software repair purposes. Unfortunately, an attacker can
boot from a live CD, mount the hard disk, and then read or write data,
bypassing any operating system authentication mechanisms. A native
operating system can do nothing to prevent this, because it is never loaded.
Therefore, preventative measures must be built into hardware.
One effective means of preventing a live-CD attack is by installing a
BIOS password. The BIOS is firmware code that is executed immediately
when a machine is turned on and before loading the operating system.
By protecting the BIOS, an attacker is unable to boot the computer without
a password. Note, however, that this does nothing to prevent an attacker
from removing the actual hard drive from the machine, mounting it in
another machine off-site, and then booting to a live CD.
This vulnerability suggests the need for locking mechanisms preventing
access to the interior of a sensitive computer system. Other prevention
tactics include using a built-in hard drive password or utilizing hard disk
encryption technology.

4.5 Computer Forensics

Computer forensics is the practice of obtaining information contained on

an electronic medium, such as computer systems, hard drives, and optical
disks, usually for gathering evidence to be used in legal proceedings.
Unfortunately, many of the advanced techniques used by forensic inves-
tigators for legal proceedings can also be employed by attackers to uncover
sensitive information. Forensic analysis typically involves the physical
inspection of the components of a computer, sometimes at the microscopic
level, but it can also involve electronic inspection of a computer’s parts as
well. (See Figure 18.)
An important principle of computer forensics is to establish, maintain,
and document a chain of custody for the computer hardware being ana-
lyzed so that it can be shown that the items collected remains unaltered
throughout the forensics analysis process.

96
 Physical Security

Figure 18: Microscopic inspection of a disk drive.

© JP/Fotolia, LLC–Royalty Free

Security Concerns from Computer Forensics

Often, forensic analysis of a system while it is turned on can reveal infor-

mation that would not be obtainable if it were powered off. For example,
online analysis allows an investigator (or attacker) to use tools to examine
or copy the contents of RAM, which is volatile and disappears when the
computer is turned off. By examining RAM, an attacker could uncover
recently entered passwords or other sensitive information that would be
unavailable if the machine were off. In addition, online attacks can often
reveal information about a machine’s presence on a network.
Because computer forensics is designed to provide evidence that is
suitable for use in court, most analysis is performed while the machine is
turned off, in order to establish that its contents have not been altered in the
process of the investigation. By mounting a hard drive in another machine,
most investigators begin by making an exact copy of the entire hard disk
and performing analysis on the copy.
Using forensic techniques, it may be possible to recover data that a user
deleted. File operations on a computer, including reading, writing, and
deleting files, are controlled by a portion of the operating system known
as a filesystem. In the process of deleting a file, many filesystems only
remove the file’s metadata—information about the file including its size,

97
 Physical Security

location on disk, and other properties—without actually overwriting the

contents of the data on the disk. The space in which the file’s data resides
is freed, in that future file operations are allowed to overwrite it, but until
it is overwritten, the deleted file’s data will remain on the disk. Because of
this, forensic investigators can use tools to analyze the contents of the disk
to uncover “deleted” data.
The typical hard drive uses magnetic disks to retain data. A byproduct
of this medium is that overwriting data may leave faint magnetic indi-
cators of the state of the information bits before they were overwritten.
It is possible that advanced hardware forensics techniques can be used
to recover some overwritten data. With the increasing density of how
information is stored on hard disks, this type of attack has become more
difficult, since the probability of successfully recovering any usable amount
of data by examining microscopic magnetic residue is prohibitively small.
Nonetheless, United States government standards mandate that in order to
safely delete classified information on magnetic media beyond all chance
of recovery, it must be overwritten with multiple passes of random data
or be physically destroyed. Note that flash media, which does not rely on
magnetic disks or tape, is not susceptible to this type of attack—a single
pass of overwriting is sufficient to remove data beyond chance of recovery
in flash memory.

Cold Boot Attacks

In 2008, a team of Princeton researchers presented a technique that can

be used to access the contents of memory after a computer has been shut
down. Dynamic random-access memory (DRAM) is the most common type
of computer memory. DRAM modules are volatile storage, which means
that their contents decay quickly after a computer is turned off. Even so, the
study showed that by cooling DRAM modules to very low temperatures,
the rate of decay can be slowed to the point where the contents of memory
can be reconstructed several minutes after the machine has powered off.
Using this technique, the researchers were able to bypass several pop-
ular drive encryption systems. Their cold boot attack consists of free-
zing the DRAM modules of a running computer by using a refrigerant
(e.g., the liquid contained in canned-air dusters), powering off the compu-
ter, and booting it from a live CD equipped with a program that recon-
structs the memory image and extract the disk encryption key (which was
stored in unencrypted form in memory).

98
 Physical Security

5 Special-Purpose Machines
There are certain types of computing machines that have a special purpose,
that is, particular jobs that they are specialized to do. These jobs might
involve sensitive information or tasks, of course, which presents particular
security requirements. In this section, we study two such machines—
automated teller machines and voting machines—and we discuss the par-
ticular types of risks that these machines have with respect to both their
physical and digital security.

5.1 Automated Teller Machines

An automatic teller machine (ATM) is any device that allows customers
of financial institutions to complete withdrawal and deposit transactions
without human assistance. Typically, customers insert a magnetic stripe
credit or debit card, enter a PIN, and then deposit or withdraw cash
from their account. The ATM has an internal cryptographic processor
that encrypts the entered PIN and compares it to an encrypted PIN stored
on the card (only for older systems that are not connected to a network)
or in a remote database. The PIN mechanism prevents an attacker with
access to a stolen card from accessing account funds without additional
information. Most financial institutions require a 4-digit numeric PIN,
but many have upgraded to 6 digits. To prevent guessing attacks, many
ATMs stop functioning after several failed PIN attempts. Some retain the
previously inserted card, and require contacting a bank official in order to
retrieve it.

ATM Physical Security

The ATM’s role as a cash repository has made it a popular target for
criminal activity. Several measures are commonly employed to prevent
tampering, theft, and to protect sensitive customer information. Firstly, the
vault, which contains any valuable items such as cash, must be secured.
Vaults are often attached to the floor to prevent casual theft and include
high-security locking mechanisms and sensors to prevent and detect intru-
sion.
While these measures are effective at preventing on-site removal of cash,
they are ineffective at deterring more brazen criminals from using heavy
construction equipment and a large vehicle to uproot and remove an entire
ATM. In some instances, attackers go so far as to drive a vehicle through

99
 Physical Security

the doors or windows of a financial institution to allow easy access to an

ATM. This technique is known as ram-raiding, and can be prevented by
installing vehicular obstructions such as bollards. Other attacks include us-
ing carefully placed explosives to compromise the vault. To compensate for
an inability to guarantee physical integrity in all situations, most modern
ATMs rely on mechanisms that render their contents unusable in the event
of a breach, such as dye markers that damage any cash inside.

ATM Encryption

To ensure the confidentiality of customer transactions, each ATM has a

cryptographic processor that encrypts all incoming and outgoing informa-
tion, starting the moment a customer enters their PIN. The current industry
standard for ATM transactions is the Triple DES (3DES) cryptosystem, a
legacy symmetric cryptosystem with up to 112 bits of security (See Fig-
ure 19.)

3DES Encryption

Bank

ATM

Figure 19: ATM communications are typically encrypted using the 3DES
symmetric cryptosystem. (“Bank”) © Zlatko Guzmic/Shutterstock; (“ATM”)
© Glowimages-Artbox/Alamy

The 3DES secret keys installed on an ATM are either loaded on-site by
technicians or downloaded remotely from the ATM vendor. Because the
confidentiality of all transactions on an ATM relies on protecting the secrecy
of the cryptographic keys, any attempts to access the cryptoprocessor will
destroy the keys. It should be noted that since early ATM machines used the
obsolete DES cryptosystem with 56-bit keys, the 3DES cryptosystem was
chosen over the more secure AES cryptosystem because 3DES is backward
compatible with DES and thus moving to 3DES was seen as a simple and
inexpensive way to increase the key size. In addition, AES was not finalized
as a standard until 2001, roughly three years after 3DES was standardized.

100
 Physical Security

Attacks on ATMs
There are several techniques used to perpetrate ATM fraud. One popular
attack involves the use of a thin sleeve of plastic or metal known as a
Lebanese loop. A perpetrator inserts this sleeve into the card slot of an
ATM. When a customer attempts to make a transaction and inserts their
credit card, it sits in the inconspicuous sleeve, out of sight from the cus-
tomer, who thinks that the machine has malfunctioned. After the customer
leaves, the perpetrator can then remove the sleeve with the victim’s card.
Another technique makes use of a device known as a skimmer, which
reads and stores magnetic stripe information when a card is swiped. An
attacker can install a skimmer over the card slot of an ATM and store cus-
tomers’ credit information without their knowledge. Later, this information
can be retrieved and used to make duplicates of the original credit cards.
Finally, some scammers may even install fake ATMs in remote locations
to capture both credit/debit cards and PINs at the same time. These fake
ATMs typically respond with a fake error message after the cards and PINs
have been captured, so as not to arouse the suspicions of the users.
In many cases, the card number or physical card is all that is necessary to
make financial transactions, but if an attacker wishes to withdraw money
from an ATM or make a debit transaction, a PIN is also required. Perpe-
trators may employ any number of eavesdropping techniques to acquire
PINs, including installing cameras at ATM locations. Some attackers may
install fake keypads that record customer PINs on entry. Collectively, these
attacks stress the importance of close surveillance at ATM sites. Cameras
and regular security checks are effective at deterring attacks as well as
identifying culprits.

5.2 Voting Machines

Since the 1960s, electronic systems have been used around the world for
another crucial function, voting. Electronic voting systems collect and tally
votes for elections around the world, including the presidential election
in the United States. Clearly, security is paramount—weaknesses could
result in falsified elections and deprive citizens of their rights to voice their
opinions on issues and leaders.

Types of Voting Machines

There are two general types of electronic voting, paper-based and direct-
recording. In a paper-based system, voters submit their votes on a piece
of paper or a punchcard, after which it is counted either by hand or by

101
 Physical Security

an optical scanner designed to read and tally marked ballots. Paper-based

systems have several advantages, including the fact that most people are
familiar with how they work and they allow for hand recounts.
The other type of voting machine, which is used by many countries, is
the direct-recording system, where votes are submitted and tallied electron-
ically, using touch-screen technology, for example. These systems are faster,
more environmentally friendly, more accessible to handicapped voters, and
ostensibly more accurate, since they remove the additional step of tallying
votes on paper. Nevertheless, these electronic voting systems are not as
amenable to hand recounts, since they don’t provide a paper audit trail.

Voting Machine Security

Both types of electronic voting systems introduce new potential avenues

for electoral fraud. Coordinating an election across a region as large as the
United States requires several steps. First, individual voting machines must
accurately tally individual votes, and be tamper proof. Next, the trans-
mission of vote totals to a centralized location must be done securely and
in a way that prevents alteration of vote tallies. Finally, these centralized
locations must calculate the final totals correctly in a tamper-proof way.
Most electronic voting machines in the United States are manufactured
by Diebold, which is also the largest supplier of ATMs in the country.
These voting machines are made with a closed-source platform, despite
the demands of many information security experts, who claim that public
scrutiny is the only way to verify the safety of electronic voting. Diebold
publicizes that its voting machines use AES encryption to encrypt stored
data, digitally signed memory cards, and Secure Socket Layer (SSL) en-
cryption to transmit vote data. Despite these measures, several researchers
have demonstrated the possibility of tampering with these systems.
A group of Princeton researchers showed that by gaining physical ac-
cess to a Diebold AccuVote-TS voting machine for one minute, an attacker
could introduce malicious code into the machine that allowed the attacker
to manipulate vote totals, delete specific votes, and perform other forms of
voting fraud. Diebold issued a statement that the voting machine used in
the study was obsolete, but the researchers insisted that newer machines
are vulnerable to the same types of attacks. In any case, with an increased
reliance on electronic voting during elections, extensive measures should
be taken to assure the security of this important process.

102
 Physical Security

6 Physical Intrusion Detection

Intrusion detection systems alert the owners of a facility, information, or
other sensitive resources if that resource’s security has been compromised.
While visible intrusion detection equipment may act as a deterrent, these
systems are primarily intended as a response measure rather than a preven-
tative one. There are typically two parts to any intrusion detection system,
detection and response.

6.1 Video Monitoring

Video monitoring systems are a standard means of intrusion detection. A
network of video cameras remotely accessible via the Internet or a legacy
closed-circuit television (CCTV) system, which uses a proprietary network,
allow a centralized operator to monitor activity in many locations at once.
(See Figure 20.) Most video monitoring systems are effective at providing
evidence of wrongdoing, because videos can be recorded and archived. Of
course, in order to be effective at intrusion detection, such systems require
a human operator to successfully identify malicious activity.

Figure 20: The components in a video monitoring security system.

(surveillance camera) © Huston Brady/Shutterstock; (thief stealing TV)
© AKS/Fotolia, LLC–Royalty Free; (TV monitor) © Karam Miri/
Shutterstock; (police officer avatar) © Christos Georghiou/Fotolia,
LLC–Royalty Free

103
 Physical Security

More advanced video monitoring systems can automatically track

movement across multiple camera zones, eliminating the need for a human
operator. Systems are in development that can detect suspicious behavior
in a crowded area by analyzing body movement patterns or particular
types of clothing. Such methods of intrusion detection are designed to work
automatically, without human assistance. Likewise, a motion sensor is a
device that detects movement in a space using any number of mechanisms.
For example, some sensors use infrared imaging and are triggered by
changes in heat. Other sensors employ ultrasonic technology—the sensor
emits an inaudible sound wave pulse and measures the reflection off objects
in the room. Finally, other systems are triggered by changes in the sound
of a room. In each case, triggered sensors may sound an alarm, either to
deter attackers or alert security staff, activate a video monitoring system to
record the intrusion, or activate additional locking mechanisms to protect
resources or trap the intruder.

Several of the physical intrusion detection mechanisms mentioned

above may be defeated. For example, a CCTV system may fail to provide
crucial evidence if an intruder makes efforts to disguise his or her features,
if cameras are dismantled or otherwise tampered with, or if an intruder
is careful to stay out of sight. Infrared motion sensors may be defeated by
placing a material that prevents the dissipation of body heat, such as a pane
of glass or insulating suit, between the camera and the intruder. Ultrasonic
sensors may be thwarted by using sound-dampening materials to prevent
the pulse of the sensor from detecting the intruder. Finally, audio sensors
can of course be defeated by remaining extremely quiet. Because of the
relative ease of circumvention, most modern intrusion detection systems
employ sensors that use a variety of technologies, making the system much
more difficult to defeat.

Examining physical intrusion detection systems can provide some in-

sights on what makes an effective network intrusion detection system.
Like physical intrusion detection, network intrusion detection can be used
both as a preventative measure (where the response is intended to stop
the intrusion) or as a means of providing important evidence after the
breach (for example, keeping thorough log files). Also, the most effective
network intrusion detection systems do not rely on a single mechanism
to detect a breach, but rather employ a wide variety of techniques to pre-
vent easy circumvention. Nevertheless, both types of systems often fea-
ture a critical component that cannot be overlooked, human involvement.

104
 Physical Security

6.2 Human Factors and Social Engineering

Despite technological advances, using human guards is still one of the
most common means of detecting intruders. In addition, most response
measures to intrusion are dependent on fast human action. While each tech-
nology has its advantages, humans can adapt in ways that most computers
can’t, giving humans greater flexibility in security applications. Moreover,
human perception can pick up details that computers miss.
Introducing people into a security model can result in a number of
potential problems, however. For example, human-in-the-loop security
solutions are vulnerable to social engineering attacks. Indeed, a major
issue with the human element is reliability. Of course, computers are not
perfect: software often has bugs, hardware occasionally fails, and some-
times systems seem to break without cause. Humans, on the other hand,
may be unreliable for a whole slew of reasons, including improper train-
ing, physical ailment, ulterior motives, or simple lack of judgment. (See
Figure 21.)

Figure 21: An example of a social engineering attack on a security guard:

“Thanks for understanding about me leaving my ID card at home.”

Human reliability also extends to computer security applications—

equipment must be properly configured, monitored, and implemented in
a way that is effective. Many examples of system compromise occur as a
result of a single network administrator failing to install critical security
patches or improperly monitoring server logs. These are mistakes that
can be prevented by placing a high emphasis on training for all personnel,
especially security and systems personnel.

105
 Physical Security

7 Exercises
For help with exercises, please visit securitybook.net.

Reinforcement
R-1 Would increasing the number of pins in the design of a pin tumbler
lock increase its security?
R-2 Would increasing the number of available pin heights in the design
of a pin tumbler lock increase its security?
R-3 What do billiards and lock bumping have in common?
R-4 Given a change key for a certain type of lock, describe how to
derive from it a bump key that works with all the locks of that
type.
R-5 What is the full theoretical size of the search space for a pin tumbler
lock that has 30 possible key blanks and 8 pins, each with 12
different distinct heights? What is the corresponding theoretical
size of the search space for the corresponding iterative master-key
construction?
R-6 Consider a pin tumbler lock with 5 pins and 8 pin heights. Explain
why it is not actually possible to have 85 different change keys.
R-7 The Acme Combination is rated as a two-hour lock, meaning that
it takes two hours to crack this lock by an experienced thief. The
Smacme company has a half-hour lock that looks exactly the same
as the Acme lock and is much cheaper to buy. The XYZ Company
wanted to save money, so they bought one Acme lock and one
Smacme lock. They put one on their front door and one on the back
door of their building. Explain how an experienced thief should be
able to break into the XYZ Company’s building in about an hour or
less.
R-8 Explain why storing secret encryption/decryption keys in a remov-
able drive helps defend against cold boot attacks.
R-9 Among radio-frequency, optical, and radio emissions, which poses
the most significant privacy threat for a user? Consider the cases of
a home office, public library, and university department.
R-10 Explain why knowing in which language the user is typing helps
perform an eavesdropping attack based on analyzing acoustic key-
board emissions.

106
 Physical Security

R-11 Discuss whether barcodes are more or less secure than magnetic
stripe cards.
R-12 Describe an application where smart cards provide sufficient secu-
rity but magnetic stripe cards do not.
R-13 What are the main security vulnerabilities of SIM cards?
R-14 What happens if you accidentally press a car key fob 257 times
while being far away from the car?
R-15 A salesperson at a high-end computer security firm wants to sell
you a protective cover for your passport, which contains an RFID
tag inside storing your sensitive information. The salesperson’s
solution costs “only” $79.99 and protects your passport from being
read via radio waves while it is in your pocket. Explain how you
can achieve the same thing for under $3.00.
R-16 How can you check if a public computer has a USB keylogger
installed?
R-17 Describe which properties, such as universality, distinctiveness,
etc., each of the following biometric identification characteristics
do and do not possess: DNA, dental x-ray, fingernail length, and
blood type.

Creativity
C-1 Describe a simple modification of the design of pin tumbler locks
to defend against lock-bumping attacks.
C-2 For safety reasons, external locked doors on commercial buildings
have mechanisms for people on the inside to escape without using
a key or combination. One common mechanism uses an infrared
motion detector to open an electronic lock for people moving to-
wards a door from the inside. Explain how an air gap under such
an external door could be exploited to open that door from the
outside?
C-3 A group of n pirates has a treasure chest and one unique lock and
key for each pirate. Using hardware that is probably already lying
around their ship, they want to protect the chest so that any single
pirate can open the chest using his lock and key. How do they set
this up?
C-4 A group of n red pirates and a group of n blue pirates have a shared
treasure chest and one unique lock and key for each pirate. Using
hardware that is probably already lying around their two ships,
they want to protect the chest so that any pair of pirates, one red

107
 Physical Security

and one blue, can open the chest using their two locks and keys, but
no group of red or blue pirates can open the chest without having at
least one pirate from the other group. How do they set this up?
C-5 A group of four pirates has a treasure chest and one unique lock
and key for each pirate. Using hardware that is probably already
lying around their ship, they want to protect the chest so that
any subset of three of these pirates can open the chest using their
respective locks and keys, but no two pirates can. How do they set
this up?
C-6 A thief walks up to an electronic lock with a 10-digit keypad and
he notices that all but three of the keys are covered in dust while
the 2, 4, 6, and 8 keys show considerable wear. He thus can safely
assume that the 4-digit code that opens the door must be made up
of these numbers in some order. What is the worst case number
of combinations he must now test to try to open this lock using a
brute-force attack?
C-7 You want to plant a bug in Company X’s office to acquire business
intelligence because they are a competitor. The package needs to
get into their server room and get hooked up to sensitive hardware.
You know the complex hires several guards from a private security
company that regularly patrol and check for authentication by
using well-known badges. You know that they regularly outsource
several functions including janitorial staff, pest control, and pur-
chasing IT equipment (think Staples delivery trucks). These jobs
have a high turnover rate, but require authentication in order to get
access to the premises in the form of a work order for IT supplies
and pest control. The janitorial staff is a recurring service, but
with a lower turnover rate. They are also periodically inspected
by officials like the city or OSHA (Occupational Safety and Health
Administration, an agency of the United States Department of
Labor), but are usually provided with advanced notice of their
arrival. What is your high-level plan of action? A guard challenges
you when you enter, how do you continue your mission? What is
your legend? What is your story? Why is this a good plan? What
are your options for acquiring access to sensitive areas? You realize
you are a target to this attack. How will you defend against it?
C-8 You are planning an urban exploration journey into the abandoned
train tunnel of Providence. It has two ends, one of which is in
a place you vaguely know, in the woods off the road, and the
other is near a moderately populated street corner. Each end is
secured with a simple padlock. The doors are clearly marked
“no trespassing.” Which end do you select and why? How do

108
 Physical Security

you justify being at the end of the tunnel if you are observed and
questioned? What are some of the dangers of this operation? What
time of day do you go on this trip? Weekday or weekend?
C-9 A variation of the following biometric authentication protocol was
experimentally tested several years ago at immigration check-
points in major U.S. airports. A user registers in person by show-
ing her credentials (e.g., passport and visa) to the registration
authority and giving her fingerprint (a “palmprint” was actually
used). The registration authority then issues to the user a tamper-
resistant smartcard that stores the reference fingerprint vector and
can execute the matching algorithm. The checkpoint is equipped
with a tamper resistant admission device that contains a fingerprint
reader and a smartcard reader. The user inserts her smartcard
and provides her fingerprint to the device, which forwards it to
the smartcard. The smartcard executes the comparison algorithms
and outputs the result (“match” or “no match”) to the device,
which admits or rejects the user accordingly. Clearly, an attacker
can defeat this scheme by programming a smartcard that always
outputs “match.” Show how to modify the scheme to make it more
secure. Namely, the admission device needs to make sure that
it is interacting with a valid smartcard issued by the registration
authority. You can assume that the smartcard can perform cryp-
tographic computations and that the admission device knows the
public key of the registration authority. The attacker can program
smartcards and is allowed to have an input-output interaction with
a valid smartcard but cannot obtain the data stored inside it.
C-10 To save on the cost of production and distribution of magnetic
stripe cards, a bank decides to replace ATM cards with printed two-
dimensional barcodes, which customers can download securely
from the bank web site, and to equip ATM machines with barcode
scanners. Assume that the barcode contains the same information
previously written to the magnetic stripe of the ATM card. Discuss
whether this system is more or less secure than traditional ATM
cards.
C-11 A bank wants to store the account number of its customers (an 8-
digit number) in encrypted form on magnetic stripe ATM cards.
Discuss the security of the following methods for storing the ac-
count number against an attacker who can read the magnetic
stripe: (1) store a cryptographic hash of the account number; (2)
store the ciphertext of the account number encrypted with the
bank’s public key using a public-key cryptosystem; (3) store the

109
 Physical Security

ciphertext of the account number encrypted with the bank’s secret

key using a symmetric cryptosystem.
C-12 Consider the following security measures for airline travel. A list
of names of people who are not allowed to fly is maintained by
the government and given to the airlines; people whose names
are on the list are not allowed to make flight reservations. Before
entering the departure area of the airport, passengers go through
a security check where they have to present a government-issued
ID and a boarding pass. Before boarding a flight, passengers must
present a boarding pass, which is scanned to verify the reservation.
Show how someone who is on the no-fly list can manage to fly
provided boarding passes can be printed online. Which additional
security measures should be implemented in order to eliminate this
vulnerability?
C-13 Develop a multiuser car-entry system based on RFID fobs. The
system should support up to four distinct key fobs.
C-14 Consider the following simple protocol intended to allow an RFID
reader to authenticate an RFID tag. The protocol assumes that the
tag can store a 32-bit secret key, s, shared with the reader, perform
XOR operations, and receive and transmit via radio 32-bit values.
The reader generates a random 32-bit challenge x and transmits
y = x ⊕ s to the tag. The tag computes z = y ⊕ s and sends z
to the reader. The reader authenticates the tag if z = x. Show
that a passive eavesdropper that observes a single execution of the
protocol can recover key s and impersonate the tag. What if the tag
and reader share two secret keys s1 and s2 , the reader sends x ⊕ s1
and the tag responds with x ⊕ s2 after recovering x?
C-15 Passports are printed on special paper and have various anti-
counterfeiting physical features. Develop a print-your-own pass-
port pilot program where a passport is a digitally signed document
that can be printed by the passport holder on standard paper.
You can assume that border control checkpoints have the follow-
ing hardware and software: two-dimensional barcode scanner,
color monitor, cryptographic software, and the public keys of the
passport-issuing authorities of all the countries participating in the
pilot program. Describe the technology and analyze its security
and usability. Is your system more or less secure than traditional
passports?
C-16 Unlike passwords, biometric templates cannot be stored in hashed
form, since the biometric reading does not have to match the
template exactly. A fuzzy commitment method for a biometric

110
 Physical Security

template can be developed from an error correcting code and a

cryptographic hash function. Let f be the decoding function, h
be the hash function, and w be a random codeword. A fuzzy
commitment for template t is the pair (h(w), δ), where δ = t − w.
A reading t0 is accepted as matching template t if h(w0 ) = h(w),
where w0 = f (t0 − δ). Analyze the security and privacy properties
of the scheme. In particular, show how this scheme protects the
privacy of the template and accepts only readings close to the
template (according to the error-correcting code).

Projects
P-1 Write a detailed comparison of the features of two high-security
locks, Medeco M3 and Abloy. Discuss whether they are resilient to
the attacks described in this chapter.
Java
P-2 Using the Java Card Development Kit, implement a vending card
application that supports the following operations: add value to
the card, pay for a purchase, and display the available balance.
The vending card should authenticate and distinguish between
two types of readers, those that can add value and those that can
decrease value. Both readers can obtain balance information.
P-3 Design and implement a program simulating the main security
functions of an ATM machine. In particular, your system should
authenticate users based on a PIN and should transmit data to
the bank in encrypted form. You should reduce the sensitive
information stored by the ATM machine in between transactions
to a minimum.
P-4 Write a term paper that discusses the different kinds of RFIDs,
including both self-powered and not. Address privacy concerns
raised by wide-spread RFID use, such as in e-passports. Use
research articles available on the Internet as source material.
P-5 Using a conductive material, such as aluminum foil, construct a
Faraday cage. Make it big enough to hold a cellphone or portable
FM radio receiver and confirm that it blocks RF signals to such de-
vices. Next, experiment with the size of holes in the exterior, to find
the size of holes that allows RF signals to reach the device inside.
Write a report documenting your construction and experiments.
Include photographs if possible.

111
 Physical Security

Chapter Notes
Jennie Rogers contributed material to Section 2 (Locks and Safes). Basics lock
picking techniques are described in course notes by Matt Blaze [8] and in the”
Guide to Lock Picking” by Ted Tool [102]. For more information on safe-cracking,
refer to the paper “Safe-cracking for the Computer Scientist” by Matt Blaze [9].
The attack on the Medeco Biaxial system for locks is due to Tobias and Bluz-
manis [101] The iterative master-key construction attack is presented by Matt
Blaze [7]. The differential power analysis technique is described by Kocher,
Jaffe and Jun [49]. Messerges, Dabbish and Sloan have done pioneering work
on side-channels attacks on smart cards, showing that the RSA cryptosystem is
vulnerable to differential power analysis [59]. An overview of GSM’s encryption
technology is provided in Jeremy Quirke’s article “Security in the GSM System”
[80]. Cloning techniques for GSM SIM cards based on side-channel attacks are
presented by Rao, Rohatgi, Scherzer and Tinguely [81]. Several attacks have been
demonstrated that completely compromise the KeeLoq and DST algorithms used
in popular RFID devices [11, 19, 42, 67]. Jain, Ross and Prabhakar provide an
overview of the subject of biometric recognition [43]. The collection of articles
edited by Tuyls, Skoric and Kevenaar provides an advanced coverage of the
subject of privacy protection for biometric authentication [104]. Di Crescenzo,
Graveman, Ge and Arce propose a formal model and efficient constructions of
approximate message authentication codes, with applications to private biometric
authentication [25]. Wim van Eck pioneered the technique of eavesdropping on
CRT displays by analyzing their radio frequency emissions [105]. Markus Kuhn
has done notable work on eavesdropping techniques using radio frequency and
optical emissions [50, 51, 52]. Adi Shamir and Eran Tromer have investigated
acoustic cryptanalysis of CPUs [90]. Acoustic eavesdropping attacks on keyboards
are discussed by Asonov and Agrawal [2] and by Zhuang, Zhou and Tygar [111].
A survey of results on acoustic eavesdropping is written by Adi Purwono [79].
Wright, Kleiman, and Shyaam debunk the myth of the possibility of data recovery
after more than one pass of overwriting [110]. The cold boot attack to recover
cryptographic keys from the RAM of a computer is due to Halderman et al. [38].
Electronic voting technologies and their risks are discussed in the book “Brave
New Ballot” by Avi Rubin [85]. A security study by Feldman, Halderman and
Felten found significant vulnerabilities in a Diebold voting machine [29].

112
 Operating Systems Security

Contents

1 Operating Systems Concepts

1.1 The Kernel and Input/Output
1.2 Processes
1.3 The Filesystem
1.4 Memory Management
1.5 Virtual Machines
2 Process Security
2.1 Inductive Trust from Start to Finish
2.2 Monitoring, Management, and Logging
3 Memory and Filesystem Security
3.1 Virtual Memory Security
3.2 Password-Based Authentication
3.3 Access Control and Advanced File Permissions
3.4 File Descriptors
3.5 Symbolic Links and Shortcuts
4 Application Program Security
4.1 Compiling and Linking
4.2 Simple Buffer Overflow Attacks
4.3 Stack-Based Buffer Overflow
4.4 Heap-Based Buffer Overflow Attacks
4.5 Format String Attacks
4.6 Race Conditions
5 Exercises

From Chapter 3 of Introduction to Computer Science, First Edition, Michael T. Goodrich,

Roberto Tamassia. Copyright 2011 by Pearson Education, Inc. Published by
Pearson Addison-Wesley. All rights reserved.

113
 Operating Systems Security

1 Operating Systems Concepts

An operating system (OS) provides the interface between the users of a

computer and that computer’s hardware. In particular, an operating system
manages the ways applications access the resources in a computer, includ-
ing its disk drives, CPU, main memory, input devices, output devices, and
network interfaces. It is the “glue” that allows users and applications
to interact with the hardware of a computer. Operating systems allow
application developers to write programs without having to handle low-
level details such as how to deal with every possible hardware device,
like the hundreds of different kinds of printers that a user could possibly
connect to his or her computer. Thus, operating systems allow application
programs to be run by users in a relatively simple and consistent way.
Operating systems handle a staggering number of complex tasks, many
of which are directly related to fundamental security problems. For ex-
ample, operating systems must allow for multiple users with potentially
different levels of access to the same computer. For instance, a university
lab typically allows multiple users to access computer resources, with some
of these users, for instance, being students, some being faculty, and some
being administrators that maintain these computers. Each different type of
user has potentially unique needs and rights with respect to computational
resources, and it is the operating system’s job to make sure these rights and
needs are respected while also avoiding malicious activities.
In addition to allowing for multiple users, operating systems also allow
multiple application programs to run at the same time, which is a concept
known as multitasking. This technique is extremely useful, of course, and
not just because we often like to simultaneously listen to music, read email,
and surf the Web on the same machine. Nevertheless, this ability has an
implied security need of protecting each running application from interfer-
ence by other, potentially malicious, applications. Moreover, applications
running on the same computer, even if they are not running at the same
time, might have access to shared resources, like the filesystem. Thus, the
operating system should have measures in place so that applications can’t
maliciously or mistakenly damage resources needed by other applications.
These fundamental issues have shaped the development of operating
systems over the last decades. In this chapter, we explore the topic of
operating system security, studying how operating systems work, how they
are attacked, and how they are protected. We begin our study by discussing
some of the fundamental concepts present in operating systems.

114
 Operating Systems Security

1.1 The Kernel and Input/Output

The kernel is the core component of the operating system. It handles the
management of low-level hardware resources, including memory, proces-
sors, and input/output (I/O) devices, such as a keyboard, mouse, or video
display. Most operating systems define the tasks associated with the kernel
in terms of a layer metaphor, with the hardware components, such as the
CPU, memory, and input/output devices being on the bottom, and users
and applications being on the top.
The operating system sits in the middle, split between its kernel, which
sits just above the computer hardware, and nonessential operating system
services (like the program that prints the items in a folder as pretty icons),
which interface with the kernel. The exact implementation details of the
kernel vary among different operating systems, and the amount of respon-
sibility that should be placed on the kernel as opposed to other layers of
the operating system has been a subject of much debate among experts. In
any case, the kernel creates the environment in which ordinary programs,
called userland applications, can run. (See Figure 1.)


 
Userland

 



 

Operating System





 


Hardware


Figure 1: The layers of a computer system.

Input/Output Devices
The input/output devices of a computer include things like its keyboard,
mouse, video display, and network card, as well as other more optional
devices, like a scanner, Wi-Fi interface, video camera, USB ports, and other
input/output ports. Each such device is represented in an operating system
using a device driver, which encapsulates the details of how interaction
with that device should be done. The application programmer interface

115
 Operating Systems Security

(API), which the device drivers present to application programs, allows

those programs to interact with those devices at a fairly high level, while
the operating system does the “heavy lifting” of performing the low-level
interactions that make such devices actually work. We will focus here on
We will focus here on the operating system calls that are needed to make
input/output and other hardware interactions possible.

System Calls
Since user applications don’t communicate directly with low-level hard-
ware components, and instead delegate such tasks to the kernel, there
must be a mechanism by which user applications can request the kernel to
perform actions on their behalf. In fact, there are several such mechanisms,
but one of the most common techniques is known as the system call, or
syscall for short. System calls are usually contained in a collection of
programs, that is, a library such as the C library (libc), and they provide
an interface that allows applications to use a predefined series of APIs
that define the functions for communicating with the kernel. Examples
of system calls include those for performing file I/O (open, close, read,
write) and running application programs (exec). Specific implementation
details for system calls depend on the processor architecture, but many
systems implement system calls as software interrupts—requests by the
application for the processor to stop the current flow of execution and
switch to a special handler for the interrupt. This process of switching
to kernel mode as a result of an interrupt is commonly referred to as a
trap. System calls essentially create a bridge by which processes can safely
facilitate communication between user and kernel space. Since moving into
kernel space involves direct interaction with hardware, an operating system
limits the ways and means that applications interact with its kernel, so as
to provide both security and correctness.

1.2 Processes
The kernel defines the notion of a process, which is an instance of a program
that is currently executing. The actual contents of all programs are initially
stored in persistent storage, such as a hard drive, but in order to actually be
executed, the program must be loaded into random-access memory (RAM)
and uniquely identified as a process. In this way, multiple copies of the
same program can be run by having multiple processes initialized with

116
 Operating Systems Security

the same program code. For example, we could be running four different
instances of a word processing program at the same time, each in a different
window.
The kernel manages all running processes, giving each a fair share of the
computer’s CPU(s) so that the computer can execute the instructions for all
currently running applications. This time slicing capability is, in fact, what
makes multitasking possible. The operating system gives each running
process a tiny slice of time to do some work, and then it moves on to the
next process. Because each time slice is so small and the context switching
between running processes happens so fast, all the active processes appear
to be running at the same time to us humans (who process inputs at a much
slower rate than computers).

Users and the Process Tree

As mentioned above, most modern computer systems are designed to
allow multiple users, each with potentially different privileges, to access
the same computer and initiate processes. When a user creates a new
process, say, by making a request to run some program, the kernel sees this
as an existing process (such as a shell program or graphical user interface
program) asking to create a new process. Thus, processes are created by a
mechanism called forking, where a new process is created (that is, forked)
by an existing process. The existing process in this action is known as the
parent process and the one that that is being forked is known as the child
process.
On most systems, the new child process inherits the permissions of its
parent, unless the parent deliberately forks a new child process with lower
permissions than itself. Due to the forking mechanism for process creation,
which defines parent-child relationships among processes, processes are or-
ganized in a rooted tree, known as the process tree. In Linux, the root of this
tree is the process init, which starts executing during the boot process right
after the kernel is loaded and running. Process init forks off new processes
for user login sessions and operating system tasks. Also, init becomes the
parent of any “orphaned” process, whose parent has terminated.

Process IDs
Each process running on a given computer is identified by a unique non-
negative integer, called the process ID (PID). In Linux, the root of the
process tree is init, with PID 0. In Figure 2, we show an example of the
process tree for a Linux system, in both a compact form and an expanded
form.

117
 Operating Systems Security

init-+-Xprt init(1)-+-Xprt(1166)
|-6*[artsd] |-artsd(29493,shitov)
|-atd |-artsd(18719,accharle)
|-automount---22*[{automount}] |-artsd(25796,mdamiano)
|-avahi-daemon---avahi-daemon |-artsd(16834,mchepkwo)
|-3*[bonobo-activati---{bonobo-activati}] |-artsd(25213,xl1)
|-console-kit-dae---63*[{console-kit-dae}] |-artsd(27782,wc9)
|-cron |-atd(4031,daemon)
|-cupsd |-automount(3434)-+-{automount}(3435)
|-dbus-daemon | |-{automount}(3436)
|-dhclient3 | |-{automount}(3439)
|-dirmngr | |-{automount}(3442)
|-esd | |-{automount}(3443)
|-gdm---gdm-+-Xorg | |-{automount}(3444)
| `-gdmlogin | |-{automount}(3445)
|-6*[getty] | |-{automount}(3446)
|-gmond---6*[{gmond}] | |-{automount}(3447)
|-hald---hald-runner-+-hald-addon-acpi | |-{automount}(3448)
| |-hald-addon-inpu | |-{automount}(3449)
| `-hald-addon-stor | |-{automount}(3450)
|-hcid | |-{automount}(3451)
|-hogd | |-{automount}(3452)
|-inetd | |-{automount}(3453)
|-klogd | |-{automount}(3454)
|-lisa | |-{automount}(3455)
|-master-+-pickup | |-{automount}(3456)
| `-qmgr | |-{automount}(3457)
|-monit---{monit} | |-{automount}(3458)
|-nscd---8*[{nscd}] | |-{automount}(3459)
|-ntpd | `-{automount}(3460)
|-portmap |-avahi-daemon(2772,avahi)---avahi-daemon(2773)
|-privoxy |-bonobo-activati(6261,pmartada)---{bonobo-activati}(6262)
|-rpc.statd |-bonobo-activati(2059,jlalbert)---{bonobo-activati}(2060)
|-rwhod---rwhod |-bonobo-activati(2684,bcrow)---{bonobo-activati}(2690)
|-sshd---sshd---sshd---tcsh---pstree |-console-kit-dae(31670)-+-{console-kit-dae}(31671)
|-syslogd | |-{console-kit-dae}(31673)
|-system-tools-ba | |-{console-kit-dae}(31674)
|-udevd | |-{console-kit-dae}(31675)
|-vmnet-bridge | |-{console-kit-dae}(31676)
|-2*[vmnet-dhcpd] | |-{console-kit-dae}(31677)
|-vmnet-natd | |-{console-kit-dae}(31679)
|-2*[vmnet-netifup] | |-{console-kit-dae}(31680)
|-xfs
`-zhm …

(a) (b)

Figure 2: The tree of processes in a Linux system produced by the pstree

command. The process tree is visualized by showing the root on the
upper left-hand corner, with children and their descendants to the right
of it. (a) Compact visualization where children associated with the same
command are merged into one node. For example, 6*[artsd] indicates that
there are six children process associated with artsd, a service that manages
access to audio devices. (b) Fragment of the full visualization, which also
includes process PIDs and users.

Process Privileges

To grant appropriate privileges to processes, an operating system associates

information about the user on whose behalf the process is being executed
with each process. For example, Unix-based systems have an ID system
where each process has a user ID (uid), which identifies the user associated
with this process, as well as a group ID (gid), which identifies a group of
users for this process. The uid is a number between 0 and 32,767 (0x7fff in

118
 Operating Systems Security

hexadecimal notation) that uniquely identifies each user. Typically, uid 0 is

reserved for the root (administrator) account. The gid is a number within
the same range that identifies a group the user belongs to. Each group
has a unique identifier, and an administrator can add users to groups to
give them varying levels of access. These identifiers are used to determine
what resources each process is able to access. Also, processes automatically
inherit the permissions of their parent processes.
In addition to the uid and gid, processes in Unix-based systems also
have an effective user ID (euid). In most cases, the euid is the same as the
uid—the ID of the user executing the process. However, certain designated
processes are run with their euid set to the ID of the application’s owner,
who may have higher privileges than the user running the process (this
mechanism is discussed in more detail in Section 3.3). In these cases, the
euid generally takes precedence in terms of deciding a process’s privileges.

Inter-Process Communication

In order to manage shared resources, it is often necessary for processes to

communicate with each other. Thus, operating systems usually include
mechanisms to facilitate inter-process communication (IPC). One simple
technique processes can use to communicate is to pass messages by reading
and writing files. Files are are readily accessible to multiple processes as
a part of a big shared resource—the filesystem—so communicating this
way is simple. Even so, this approach proves to be inefficient. What if
a process wishes to communicate with another more privately, without
leaving evidence on disk that can be accessed by other processes? In
addition, file handling typically involves reading from or writing to an
external hard drive, which is often much slower than using RAM.
Another solution that allows for processes to communicate with each
other is to have them share the same region of physical memory. Processes
can use this mechanism to communicate with each other by passing mes-
sages via this shared RAM memory. As long as the kernel manages the
shared and private memory spaces appropriately, this technique can allow
for fast and efficient process communication.
Two additional solutions for process communication are known as pipes
and sockets. Both of these mechanisms essentially act as tunnels from
one process to another. Communication using these mechanisms involves
the sending and receiving processes to share the pipe or socket as an in-
memory object. This sharing allows for fast messages, which are produced
at one end of the pipe and consumed at the other, while actually being in
RAM memory the entire time.

119
 Operating Systems Security

Signals

Sometimes, rather than communicating via shared memory or a shared

communication channel, it is more convenient to have a means by which
processes can send direct messages to each other asynchronously. Unix-
based systems incorporate signals, which are essentially notifications sent
from one process to another. When a process receives a signal from another
process, the operating system interrupts the current flow of execution of
that process, and checks whether that process has an appropriate signal
handler (a routine designed to trigger when a particular signal is received).
If a signal handler exists, then that routine is executed; if the process does
not handle this particular signal, then it takes a default action. Terminating
a nonresponsive process on a Unix system is typically performed via sig-
nals. Typing Ctrl-C in a command-line window sends the INT signal to the
process, which by default results in termination.

Remote Procedure Calls

Windows supports signals in its low-level libraries, but does not make
use of them in practice. Instead of using signals, Windows relies on the
other previously mentioned techniques and additional mechanisms known
as remote procedure calls (RPC), which essentially allow a process to call
a subroutine from another process’s program. To terminate a process,
Windows makes use of a kernel-level API appropriately named Termi-
nateProcess(), which can be called by any process, and will only execute
if the calling process has permission to kill the specified target.

Daemons and Services

Computers today run dozens of processes that run without any user in-
tervention. In Linux terminology, these background processes are known
as daemons, and are essentially indistinguishable from any other process.
They are typically started by the init process and operate with varying levels
of permissions. Because they are forked before the user is authenticated,
they are able to run with higher permissions than any user, and survive the
end of login sessions. Common examples of daemons are processes that
control web servers, remote logins, and print servers.
Windows features an equivalent class of processes known as services.
Unlike daemons, services are easily distinguishable from other processes,
and are differentiated in monitoring software such as the Task Manager.

120
 Operating Systems Security

1.3 The Filesystem

Another key component of an operating system is the filesystem, which is

an abstraction of how the external, nonvolatile memory of the computer
is organized. Operating systems typically organize files hierarchically into
folders, also called directories.
Each folder may contain files and/or subfolders. Thus, a volume, or
drive, consists of a collection of nested folders that form a tree. The topmost
folder is the root of this tree and is also called the root folder. Figure 3
shows a visualization of a file system as a tree.

Figure 3: A filesystem as a tree, displayed by Windows Explorer.

File Access Control

One of the main concerns of operating system security is how to delineate

which users can access which resources, that is, who can read files, write
data, and execute programs. In most cases, this concept is encapsulated in
the notion of file permissions, whose specific implementation depends on
the operating system. Namely, each resource on disk, including both data
files and programs, has a set of permissions associated with it.

121
 Operating Systems Security

File Permissions
File permissions are checked by the operating system to determine if a
file is readable, writable, or executable by a user or group of users. This
permission data is typically stored in the metadata of the file, along with
attributes such as the type of file. When a process attempts to access a
file, the operating system checks the identity of the process and determines
whether or not access should be granted, based on the permissions of the
file.
Several Unix-like operating systems have a simple mechanism for file
permissions known as a file permission matrix. This matrix is a represen-
tation of who is allowed to do what to the file, and contains permissions
for three classes, each of which features a combination of bits. Files have
an owner, which corresponds to the uid of some user, and a group, which
corresponds to some group id.
First, there is the owner class, which determines permissions for the
creator of the file. Next is the group class, which determines permissions
for users in the same group as the file. Finally, the others class determines
permissions for users who are neither the owner of the file nor in the same
group as the file.
Each of these classes has a series of bits to determine what permissions
apply. The first bit is the read bit, which allows users to read the file. Second
is the write bit, which allows users to alter the contents of the file. Finally,
there is the execute bit, which allows users to run the file as a program
or script, or, in the case of a directory, to change their current working
directory to that one. An example of a file permission matrix for a set of
files in a directory is shown in Figure 4.

Figure 4: An example of the permission matrices for several files on a Unix

system, using the ls -l command. The Floats.class file has read, write,
and execute rights for its owner, goodrich, and nonowners alike. The
Floats.java file, on the other hand, is readable by everyone, writeable only
by its owner, and no one has execute rights. The file, Test.java, is only
readable and writable by its owner—all others have no access rights.

122
 Operating Systems Security

Unix File Permissions

The read, write, and execute bits are implemented in binary, but it is
common to express them in decimal notation, as follows: the execute bit
has weight 1, the write bit has weight 2, and read bit has weight 4. Thus,
each combination of the 3 bits yields a unique number between 0 and 7,
which summarizes the permissions for a class. For example, 3 denotes that
both the execute and write bits are set, while 7 denotes that read, write, and
execute are all set.
Using this decimal notation, the entire file permission matrix can be
expressed as three decimal numbers. For example, consider a file with a
permission matrix of 644. This denotes that the owner has permission to
read and write the file (the owner class is set to 6), users in the same group
can only read (the group class is set to 4), and other users can only read (the
others class is set to 4). In Unix, file permissions can be changed using the
chmod command to set the file permission matrix, and the chown command
to change the owner or group of a file. A user must be the owner of a file to
change its permissions.
Folders also have permissions. Having read permissions for a folder
allows a user to list that folder’s contents, and having write permissions for
a folder allows a user to create new files in that folder. Unix-based systems
employ a path-based approach for file access control. The operating system
keeps track of the user’s current working directory. Access to a file or
directory is requested by providing a path to it, which starts either at the
root directory, denoted with /, or at the current working directory. In
order to get access, the user must have execute permissions for all the
directories in the path. Namely, the path is traversed one directory at the
time, beginning with the start directory, and for each such directory, the
execute permission is checked.
As an example, suppose Bob is currently accessing directory
/home/alice, the home directory of Alice (his boss), for which he has execute
permission, and wants to read file
/home/alice/administration/memos/raises.txt.
When Bob issues the Unix command
cat administration/memos/raises.txt
to view the file, the operating system first checks if Bob has execute per-
mission on the first folder in the path, administration. If so, the operating
system checks next whether Bob has execute permissions on the next folder,
memos. If so, the operating system finally checks whether Bob has read
permission on file raises.txt. If Bob does not have execute permission on
administration or memos, or does not have read permission on raises.txt,
access is denied.

123
 Operating Systems Security

1.4 Memory Management

Another service that an operating system provides is memory management,
that is, the organization and allocation of the memory in a computer. When
a process executes, it is allocated a region of memory known as its address
space. The address space stores the program code, data, and storage that
a process needs during its execution. In the Unix memory model, which is
used for most PCs, the address space is organized into five segments, which
from low addresses to high, are as follows. (See Figure 5.)
1. Text. This segment contains the actual machine code of the program,
which was compiled from source code prior to execution.
2. Data. This segment contains static program variables that have been
initialized in the source code, prior to execution.
3. BSS. This segment, which is named for an antiquated acronym for
block started by symbol, contains static variables that are uninitial-
ized (or initialized to zero).
4. Heap. This segment, which is also known as the dynamic segment,
stores data generated during the execution of a process, such as
objects created dynamically in an object-oriented program written in
Java or C++.
5. Stack. This segment houses a stack data structure that grows down-
wards and is used for keeping track of the call structure of subroutines
(e.g., methods in Java and functions in C) and their arguments.

Stack

Dynamic

BSS

Data

Text

Figure 5: The Unix memory model.

124
 Operating Systems Security

Memory Access Permissions

Each of the five memory segments has its own set of access permissions
(readable, writable, executable), and these permissions are enforced by the
operating system. The text region is usually read-only, for instance, because
it is generally not desirable to allow the alteration of a program’s code
during its execution. All other regions are writable, because their contents
may be altered during a program’s execution.
An essential rule of operating systems security is that processes are not
allowed to access the address space of other processes, unless they have
explicitly requested to share some of that address space with each other. If
this rule were not enforced, then processes could alter the execution and
data of other processes, unless some sort of process-based access control
system were put in place. Enforcing address space boundaries avoids many
serious security problems by protecting processes from changes by other
processes.
In addition to the segmentation of address space in order to adhere to
the Unix memory model, operating systems divide the address space into
two broad regions: user space, where all user-level applications run, and
kernel space, which is a special area reserved for core operating system
functionality. Typically, the operating system reserves a set amount of
space (one gigabyte, for example), at the bottom of each process’s address
space, for the kernel, which naturally has some of the most restrictive access
privileges of the entire memory.

Contiguous Address Spaces

As described above, each process’s address space is a contiguous block of

memory. Arrays are indexed as contiguous memory blocks, for example, so
if a program uses a large array, it needs an address space for its data that is
contiguous. In fact, even the text portion of the address space, which is used
for the computer code itself, should be contiguous, to allow for a program
to include instructions such as “jump forward 10 instructions,” which is a
natural type of instruction in machine code.
Nevertheless, giving each executing process a contiguous slab of real
memory would be highly inefficient and, in some cases, impossible. For
example, if the total amount of contiguous address space is more than the
amount of memory in the computer, then it is simply not possible for all
executing processes to get a contiguous region of memory the size of its
address space.

125
 Operating Systems Security

Virtual Memory

Even if all the processes had address spaces that could fit in memory, there
would still be problems. Idle processes in such a scenario would still retain
their respective chunks of memory, so if enough processes were running,
memory would be needlessly scarce.
To solve these problems, most computer architectures incorporate a
system of virtual memory, where each process receives a virtual address
space, and each virtual address is mapped to an address in real memory
by the virtual memory system. When a virtual address is accessed, a
hardware component known as the memory management unit looks up the
real address that it is mapped to and facilitates access. Essentially, processes
are allowed to act as if their memory is contiguous, when in reality it may be
fragmented and spread across RAM, as depicted in Figure 6. Of course,
this is useful, as it allows for several simplifications, such as supporting
applications that index into large arrays as contiguous chunks of memory.

Program Sees: Actual Memory:

Another
Program

Hard Drive

Figure 6: Mapping virtual addresses to real addresses.

An additional benefit of virtual memory systems is that they allow
for the total size of the address spaces of executing processes to be larger
than the actual main memory of the computer. This extension of memory
is allowed because the virtual memory system can use a portion of the
external drive to “park” blocks of memory when they are not being used by
executing processes. This is a great benefit, since it allows for a computer
to execute a set of processes that could not be multitasked if they all had to
keep their entire address spaces in main memory all the time.

126
 Operating Systems Security

Page Faults

There is a slight time trade-off for benefit we get from virtual memory,
however, since accessing the hard drive is much slower than RAM. Indeed,
accessing a hard drive can be 10,000 times slower than accessing main
memory.
So operating systems use the hard drive to store blocks of memory that
are not currently needed, in order to have most memory accesses being in
main memory, not the hard drive. If a block of the address space is not
accessed for an extended period of time, it may be paged out and written to
disk. When a process attempts to access a virtual address that resides in a
paged out block, it triggers a page fault.
When a page fault occurs, another portion of the virtual memory system
known as the paging supervisor finds the desired memory block on the hard
drive, reads it back into RAM, updates the mapping between the physical
and virtual addresses, and possibly pages out a different unused memory
block. This mechanism allows the operating system to manage scenarios
where the total memory required by running processes is greater than the
amount of RAM available. (See Figure 7.)

1. Process requests virtual address not in memory,

causing a page fault.
2. Paging supervisor pages out
an old block of RAM memory.
“read 0110101”

“Page fault,
Process let me fix that.”
Paging supervisor

old
Blocks in
RAM memory:

new External disk

3. Paging
g g supervisor
p locates requested
q block
on the disk and brings it into RAM memory.

Figure 7: Actions resulting from a page fault.

127
 Operating Systems Security

1.5 Virtual Machines

Virtual machine technology is a rapidly emerging field that allows an

operating system to run without direct contact with its underlying hard-
ware. For instance, such systems may allow for substantial electrical power
savings, by combining the activities of several computer systems into one,
with the one simulating the operating systems of the others. The way
this simulation is done is that an operating system is run inside a virtual
machine (VM), software that creates a simulated environment the operating
system can interact with. The software layer that provides this environment
is known as a hypervisor or virtual machine monitor (VMM). The operating
system running inside the VM is known as a guest, and the native operating
system is known as the host. Alternately, the hypervisor can run directly
in hardware without a host operating system, which is known as native
virtualization. To the guest OS, everything appears normal: it can interact
with external devices, perform I/O, and so on. However, the operating
system is in fact interacting with virtual devices, and the underlying virtual
machine is bridging the gap between these virtual devices and the actual
hardware, completely transparent to the guest operating system.

Implementing Virtual Machines

There are two main implementations of VMs. The first is emulation, where
the host operating system simulates virtual interfaces that the guest oper-
ating system interacts with. Communications through these interfaces are
translated on the host system and eventually passed to the hardware. The
benefit of emulation is that it allows more hardware flexibility. For example,
one can emulate a virtual environment that supports one processor on a ma-
chine running an entirely different processor. The downside of emulation
is that it typically has decreased performance due to the conversion process
associated with the communication between the virtual and real hardware.
The second VM implementation is known simply as virtualization, and
removes the above conversion process. As a result, the virtual interfaces
within the VM must be matched with the actual hardware on the host
machine, so communications are passed from one to the other seamlessly.
This reduces the possibilities for running exotic guest operating systems,
but results in a significant performance boost.

128
 Operating Systems Security

Advantages of Virtualization
Virtualization has several advantages:
• Hardware Efficiency. Virtualization allows system administrators to
host multiple operating systems on the same machine, ensuring an
efficient allocation of hardware resources. In these scenarios, the
hypervisor is responsible for effectively managing the interactions
between each operating system and the underlying hardware, and
for ensuring that these concurrent operations are both efficient and
safe. This management may be very complex—one set of hardware
may be forced to manage many operating systems simultaneously.

• Portability. VMs provide portability, that is, the ability to run a

program on multiple different machines. This portability comes from
the fact that the entire guest operating system is running as software
virtually, so it is possible to save the entire state of the guest oper-
ating system as a snapshot and transfer it to another machine. This
portability also allows easy restoration in the event of a problem. For
example, malware researchers frequently employ VM technology to
study malware samples in an environment that can easily be restored
to a clean state should anything go awry.

• Security. In addition to maximizing available resources and provid-

ing portable computing solutions, virtual machines provide several
benefits from a security standpoint. By containing the operating
system in a virtual environment, the VM functions as a strict sandbox
that protects the rest of the machine in the event that the guest oper-
ating system is compromised. In the event of a breach, it is a simple
matter to disconnect a virtual machine from the Internet without
interrupting the operations of other services on the host machine.

• Management Convenience. Finally, the ability to take snapshots of

the entire virtual machine state can prove very convenient. Suppose
Bob, a user on a company network, is running a virtualized version
of Windows that boots automatically when he turns on his machine.
If Bob’s operating system becomes infected with malware, then a
system administrator could just log in to the host operating system,
disconnect Bob from the company network, and create a snapshot of
Bob’s virtual machine state. After reviewing the snapshot on another
machine, the administrator might decide to revert Bob’s machine to a
clean state taken previously. The whole process would be reasonably
time consuming and resource intensive on ordinary machines, but
VM technology makes it relatively simple.

129
 Operating Systems Security

2 Process Security
To protect a computer while it is running, it is essential to monitor and
protect the processes that are running on that computer.

2.1 Inductive Trust from Start to Finish

The trust that we place on the processes running on a computer is an
inductive belief based on the integrity of the processes that are loaded when
the computer is turned on, and that this state is maintained even if the
computer is shut down or put into a hibernation state.

The Boot Sequence

The action of loading an operating system into memory from a powered-off
state is known as booting, originally bootstrapping. This task seems like a
difficult challenge—initially, all of the operating system’s code is stored in
persistent storage, typically the hard drive. However, in order for the oper-
ating system to execute, it must be loaded into memory. When a computer
is turned on, it first executes code stored in a firmware component known
as the BIOS (basic input/output system). On modern systems, the BIOS
loads into memory the second-stage boot loader, which handles loading
the rest of the operating system into memory and then passes control of
execution to the operating system. (See Figure 8.)
BIOS

CPU Secondary Loader

Operating
System

Figure 8: Operation of the BIOS.

130
 Operating Systems Security

A malicious user could potentially seize execution of a computer at

several points in the boot process. To prevent an attacker from initiating
the first stages of booting, many computers feature a BIOS password that
does not allow a second-stage boot loader to be executed without proper
authentication.

The Boot Device Hierarchy

There are some other security issues related to the boot sequence, however.
Most second-stage boot loaders allow the user to specify which device
should be used to load the rest of the operating system. In most cases,
this option defaults to booting from the hard drive, or in the event of a new
installation, from external media such as a DVD drive. Thus, one should
make sure that the operating system is always booted from trusted media.
There is a customizable hierarchy that determines the order of prece-
dence of booting devices: the first available device in the list is used for
booting. This flexibility is important for installation and troubleshooting
purposes, but it could allowan attacker with physical access to boot another
operating system from an external media, bypassing the security mecha-
nisms built into the operating system intended to be run on the computer.
To prevent these attacks, many computers utilize second-stage boot loaders
that feature password protections that only allow authorized users to boot
from external storage media.

Hibernation
Modern machines have the ability to go into a powered-off state known
as hibernation. While going into hibernation, the operating system stores
the entire contents of the machine’s memory into a hibernation file on disk
so that the state of the computer can be quickly restored when the system
is powered back on. Without additional security precautions, hibernation
exposes a machine to potentially invasive forensic investigation.
Since the entire contents of memory are stored into the hibernation file,
any passwords or sensitive information that were stored in memory at the
time of hibernation are preserved. A live CD attack can be performed to
gain access to the hibernation file. Windows stores the hibernation file
as C:\hiberfil.sys. Security researchers have shown the feasibility of re-
versing the compression algorithm used in this file, so as to extract a view-
able snapshot of RAM at the time of hibernation, which opens the possibil-
ity of the attack shown in Figure 9.

131
 Operating Systems Security

1. User closes a laptop computer,

putting it into hibernation.
hibernation

2. Attacker copies the hiberfil.sys

file to discover any unencrypted
passwords that were stored
in memory when the computer
was put into hibernation.

Figure 9: The hibernation attack. (user closing laptop) © Sinisa Bobic/

Shutterstock; (open laptop) © JP Photography/Alamy

Attacks that modify the hiberfil.sys file have also been demonstrated, so
that the execution of programs on the machine is altered when the machine
is powered on. Interestingly, Windows does not delete the hibernation
file after resuming execution, so it may persist even after the computer is
rebooted several times. A related attack on virtual memory page files, or
swap files, is discussed in Section 3.1. To defend against these attacks,
hard disk encryption should be used to protect hibernation files and swap
files.

2.2 Monitoring, Management, and Logging

One of the most important aspects of operating systems security is some-
thing military people call “situational awareness.” Keeping track of what
processes are running, what other machines have interacted with the sys-
tem via the Internet, and if the operating system has experienced any
unexpected or suspicious behavior can often leave important clues not only
for troubleshooting ordinary problems, but also for determining the cause
of a security breach. For example, noticing log entries of repeated failed
attempts to log in may warn of a brute-force attack, and prompt a system
administrator to change passwords to ensure safety.

Event Logging
Operating systems therefore feature built-in systems for managing event
logging. For example, as depicted in Figure 10, Windows includes an
event logging system known simply as the Windows Event Log.

132
 Operating Systems Security

Figure 10: The Windows Event Log.

Windows defines three possible sources of logs, “System,” “Applica-

tion,” and “Security.” The System log can only be written to by the
operating system itself, while the Application log may be written to by
ordinary applications. Finally, the Security log can only be written to by a
special Windows service known as the Local Security Authority Subsystem
Service, visible in Process Explorer as lsass.exe. This service is responsible
for enforcing security policies such as access control and user authentica-
tion. In addition to these three predefined sources, users can define their
own log sources. Each log entry is known as an event. Events are given
unique identifiers, which correspond to any of the potential occurrences
on a Windows machine that might prompt logging. Examples include
applications exiting unexpectedly, users failing to properly authenticate,
network connections being made, and so on.

Unix-based systems, including Linux, have differing logging mecha-

nisms depending on the specific distribution. Typically, log files are stored
in /var/log or some similar location and are simple text files with descriptive
names. For example, auth.log contains records of user authentication, while
kern.log keeps track of unexpected kernel behavior. Like Windows logs,
entries contain a timestamp along with a description of the event. Typically,
writing to these log files can only be done by a special syslog daemon.
While Windows log files may allow easier handling when using Microsoft’s
event logging tools, the simple text format of Unix logs, containing one
event per line, allows quick and easy perusing.

133
 Operating Systems Security

Process Monitoring
There are several scenarios where we would like to find out exactly which
processes are currently running on our computer. For example, our com-
puter might be sluggish and we want to identify an application using up
lots of CPU cycles or memory. Or we may suspect that our computer
has been compromised by a virus and we want to check for suspicious
processes. Of course, we would like to terminate the execution of such a
misbehaving or malicious process, but doing so requires that we identify
it first. Every operating system therefore provides tools that allow users
to monitor and manage currently running processes. Examples include
the task manager application in Windows and the ps, top, pstree, and kill
commands in Linux.

Process Explorer
Process monitoring tools might seem like they are aimed at expert users or
administrators, since they present a detailed listing of running processes
and associated execution statistics, but they are useful tools for ordinary
users too. In Figure 11, we show a screen shot of just such a tool—Process
Explorer—which is a highly customizable and useful tool for monitoring
processes in the Microsoft Windows operating system.
Process Explorer is a good example of the kind of functionality that can
be provided by a good process monitoring tool. The tool bar of Process
Explorer contains various buttons, including one for terminating processes.
The mini graphs show the usage histories of CPU time, main memory, and
I/O, which are useful for identifying malicious or misbehaving processes.
The processes tree pane shows the processes currently running and has a
tabular format.
The components of Process Explorer provide a large amount of infor-
mation for process monitoring and managing. The left column (Process)
displays the tree of processes, that is, the processes and their parent-child
relationship, by means of a standard outline view. Note, for example, in
our screen shot shown in Figure 11, that process explorer.exe is the parent
of many processes, including the Firefox web browser and the Thunderbird
email client. Next to the process name is the icon of the associated program,
which helps to facilitate visual identification. The remaining columns
display, from left to right, the process ID (PID), percentage of CPU time
used (CPU), size (in KB) of the process address space (Virtual Size), and
description of the process (Description).
Large usage of CPU time and/or address space often indicate problem-
atic processes that may need to be terminated. A customization window
for the background color of processes is also shown in this example. In

134
 Operating Systems Security

Figure 11: Screen shot of the Process Explorer utility for Microsoft Win-
dows, by Mark Russinovich, configured with three components: a menu
bar (top), a tool bar and three mini graphs (middle), and a process tree pane
(bottom). Microsoft® and Windows® are registered trademarks of the Microsoft
Corporation in the U.S.A. and other countries. Screen shots and icons reprinted with
permission from the Microsoft Corporation. This book is not sponsored or endorsed
by or affiliated with the Microsoft Corporation.

particular, different colors are used to highlight newly started processes,

processes being terminated, user processes (started by the same user run-
ning Process Explorer), and system processes, such as services. All of these
features provide a useful graphical user interface for identifying malicious
and misbehaving processes, as well as giving a simple means to kill them
once they are identified.
In addition to monitoring performance, it is important to gather detailed
information about the process image, that is, the executable program asso-
ciated with the process. In our example of Figure 11, Process Explorer
provides the name of the entity that has developed the program (Company)
and the location on disk of the image (Path). The location of the image
may allow the detection of a virus whose file name is the same as that of a
legitimate application but is located in a nonstandard directory.
An attacker may also try to replace the image of a legitimate program
with a modified version that performs malicious actions. To counter this at-
tack, the software developer can digitally sign the image and Process Ex-
plorer can be used to verify the signature and display the name of the
entity who has signed the image (Verified Signer).

135
 Operating Systems Security

3 Memory and Filesystem Security

The contents of a computer are encapsulated in its memory and filesystem.
Thus, protection of a computer’s content has to start with the protection of
its memory and its filesystem.

3.1 Virtual Memory Security

As we observed in Section 1.4, virtual memory is a useful tool for oper-
ating systems. It allows for multiple processes with a total address space
larger than our RAM memory to run effectively, and it supports these
multiple processes to each view its address spaces as being contiguous.
Even so, these features come with some security concerns.

Windows and Linux Swap Files

On Windows, virtual memory pages that have been written to the hard
disk are actually contained in what is known as the page file, located at
C:\pagefile.sys. Linux, on the other hand, typically requires users to set
up an entire partition of their hard disk, known as the swap partition,
to contain these memory pages. In addition to the swap partition, Linux
alternately supports a swap file, which functions similarly to the Windows
page file. In all cases, each operating system enforce rules preventing users
from viewing the contents of virtual memory files while the OS is running,
and it may be configured such that they are deleted when the machine is
shut down.

Attacks on Virtual Memory

However, if an attacker suddenly powered off the machine without prop-
erly shutting down and booted to another operating system via external
media, it may be possible to view these files and reconstruct portions
of memory, potentially exposing sensitive information. To mitigate these
risks, hard disk encryption should be used in all cases where potentially
untrusted parties have physical access to a machine. Such encryption does
not stop such an attacker from reading a swap file, of course, since he would
have physical access to the computer. But it does prevent such an attacker
from learning anything useful from the contents of these files, provided he
is not able to get the decryption keys.

136
 Operating Systems Security

3.2 Password-Based Authentication

The question of who is allowed access to the resources in a computer system
begins with a central question of operating systems security:

How does the operating system securely identify its users?

The answer to this question is encapsulated in the authentication concept,

that is, the determination of the identity or role that someone has (in this
case, with respect to the resources the operating system controls).
A standard authentication mechanism used by most operating systems
is for users to log in by entering a username and password. If the entered
password matches the stored password associated with the entered user-
name, then the system accepts this authentication and logs the users into
the system.
Instead of storing the passwords as clear text, operating systems typi-
cally keep cryptographic one-way hashes of the passwords in a password
file or database instead. Thanks to the one-way property of cryptographic
hash functions, an attacker who gets hold of the password file cannot effi-
file cannot efficiently derive from it the actual passwords and has to resort
to a guessing attack. That is, the basic approach to guessing passwords
from the password file is to conduct a dictionary attack, where each word
where each word in a dictionary is hashed and the resulting value is
compared with the hashed passwords stored in the password file. If users
of a system use weak passwords, such as English names and words, the
dictionary attack can often succeed with a dictionary of only 500,000 words,
as opposed to the search space of over 5 quadrillion words that could be
formed from eight characters that can be typed on a standard keyboard.

Password Salt
One way to make the dictionary attack more difficult to launch is to use
salt, which is a cryptographic technique of using random bits as part of
the input to a hash function or encryption algorithm so as to increase the
randomness in the output. In the case of password authentication, salt
would be introduced by associating a random number with each userid.
Then, rather than comparing the hash of an entered password with a stored
hash of a password, the system compares the hash of an entered password
and the salt for the associated userid with a stored hash of the password
and salt. Let U be a userid and P be the corresponding password. When
using salt, the password file stores the triplet (U, S, h(S|| P)), where S is the
salt for U and h is a cryptographic hash function. (See Figure 12.)

137
 Operating Systems Security

Without salt:

1. User types userid, X, and password, P. P

Password
d fil
file:

2. System looks up H, the stored hash of …

X’s
X s password
password. X: H
…
3. System tests whether h(P) = H.

With salt:

1. User types userid, X, and password, P.

Password file:
2. System
y looks upp S and H, where S is
the random salt for userid X and H is …
stored hash of S and X’s password. X: S, H
…
3 System tests whether h(S||P) = H.
3. H

Figure 12: Password salt. We use || to denote string concatenation and h to

denote a cryptographic hash function. © PhotoAlto/Alamy

How Salt Increases Search Space Size

Using password salt significantly increases the search space needed for a
dictionary attack. Assuming that an attacker cannot find the salt associated
with a userid he is trying to compromise, then the search space for a
dictionary attack on a salted password is of size

2B × D,

where B is the number of bits of the random salt and D is the size of the list
of words for the dictionary attack. For example, if a system uses a 32-bit
salt for each userid and its users pick the kinds of passwords that would
be in a 500,000 word dictionary, then the search space for attacking salted
passwords would be

232 × 500,000 = 2,147,483,648,000,000,

which is over 2 quadrillion. Also, even if an attacker can find the salt
associated with each userid (which the system should store in encrypted
form), by employing salted passwords, an operating system can limit his
dictionary attack to one userid at a time (since he would have to use a
different salt value for each one).

138
 Operating Systems Security

Password Authentication in Windows and Unix-based Systems

In Microsoft Windows systems, password hashes are stored in a file called

the Security Accounts Manager (SAM) file, which is not accessible to
regular users while the operating system is running. Older versions of
Windows stored hashed passwords in this file using an algorithm based on
DES known as LAN Manager hash, or LM hash, which has some security
weaknesses. This password-hashing algorithm pads a user’s password to
14 characters, converts all lowercase letters to uppercase, and uses each of
the 7-byte halves to generate a DES key. These two DES keys are used
to encrypt a stored string (such as “KGS!@#$%”), resulting in two 8-byte
ciphertexts, which are concatenated to form the final hash. Because each
half of the user’s password is treated separately, the task of performing a
dictionary attack on an LM hash is actually made easier, since each half
has a maximum of seven characters. In addition, converting all letters to
uppercase significantly reduces the search space. Finally, the LM hash al-
gorithm does not include a salt, so using tables of precomputed information
is especially effective.
Windows improved these weaknesses by introducing the NTLM algo-
rithm. NTLM is a challenge-response protocol used for authentication by
several Windows components. The protocol involves a server, in this case
the operating system, and a client, in this case a service attempting to
authenticate a user. The operating system sends an 8-byte random number
as a challenge to the client. Next, the client computes two 24-byte responses
using two secrets, the LM hash of the password and the MD4 hash of the
password. For each secret, the client pads the 16-byte hash to 21 bytes with
null characters, splits the 21 bytes into three groups of 7 bytes, and uses
each 7-byte segment as a key to DES encrypt the 8-byte challenge. Finally,
the three 8-byte ciphertexts (for each secret) are concatenated, resulting in
two 24-byte responses (one using the MD4 hash, and the other using the
LM hash). These two responses are sent to the server, which has performed
the same computations using its stored hashes, and authenticates the user.
While NTLM has not been completely broken, some weaknesses have been
identified. Specifically, both the MD4 and LM hashes are unsalted and as
such are vulnerable to precomputation attacks.
Unix-based systems feature a similar password mechanism, and store
authentication information at /etc/passwd, possibly in conjunction with
/etc/shadow. However, most Unix variants use salt and are not as restricted
in the choice of hash algorithm, allowing administrators to chose their
preference. At the time of this writing, most systems use a salted MD5
algorithm or a DES variant, but many are able to use other hash algorithms
such as Blowfish.

139
 Operating Systems Security

3.3 Access Control and Advanced File Permissions

Once a user is authenticated to a system, the next question that must be
addressed is that of access control:
How does the operating system determine what users have
permission to do?
To address in detail this question with respect to files, we need to develop
some terminology. A principal is either a user or a group of users. A
principal can be explicitly defined as a set of users, such as a group,
friends, consisting of users peter and paul, or it can be one of the principals
predefined by the operating system. For example, in Unix-based systems,
the following users and groups are defined for each file (or folder). User
owner refers to the user owning the file. Group group, called the owning
group, is the default group associated with the file. Also, group all includes
all the users in the system and group other consists of all but owner, i.e., of
all users except the owner of the file.
A permission is a specific action on a file or folder. For example, file
permissions include read and write and program files may additionally
have an execute permission. A folder may also have a list permission,
which refers to being able to inspect (list) the contents of the folder, and
execute, which allows for setting the current directory as that folder. The
execute permission of folders is the basis for the path-based access control
mechanism in Unix-based systems. (See Section 1.3.)

Access Control Entries and Lists

An access control entry (ACE) for a given file or folder consists of a triplet
(principal, type, permission), where type is either allow or deny. An access
control list (ACL) is an ordered list of ACEs.
There are a number of specific implementation details that must be
considered when designing an operating system permissions scheme. For
one, how do permissions interact with the file organization of the system?
Specifically, is there a hierarchy of inheritance? If a file resides in a folder,
does it inherit the permissions of its parent, or override them with its own
permissions? What happens if a user has permission to write to a file but
not to the directory that the file resides in? The meaning of read, write, and
execute permissions seems intuitive for files, but how do these permissions
affect folders? Finally, if permissions aren’t specifically granted or denied,
are they implied by default? Interestingly, even between two of the most
popular operating system flavors, Linux and Windows, the answers to
these questions can vary dramatically.

140
 Operating Systems Security

Linux Permissions

Linux inherits most of its access control systems from the early Unix sys-
tems discussed previously. Linux features file permission matrices, which
determine the privileges various users have in regards to a file. All permis-
sions that are not specifically granted are implicitly denied, so there is no
mechanism (or need) to explicitly deny permissions. According to the path-
based access control principle, in order to access a file, each ancestor folder
(in the filesystem tree) must have execute permission and the file itself
must have read permission. Finally, owners of files are given the power
to change the permissions on those files—this is known as discretionary
access control (DAC).
In addition to the three basic permissions (read, write, and execute),
Linux allows users to set extended attributes for files, which are applied
to all users attempting to access these files. Example extended attributes
include making a file append-only (so a user may only write to the end
of the file) and marking a file as “immutable,” at which point not even
the root user can delete or modify the file (unless he or she removes the
attribute first). These attributes can be set and viewed with the chattr and
lsattr commands, respectively.
More recently, Linux has begun supporting an optional ACL-based
permissions scheme. ACLs on Linux can be checked with the getfacl
command, and set with the setfacl command. Within this scheme, each file
has basic ACEs for the owner, group, and other principals and additional
ACEs for specific users or groups, called named users and named groups,
can be created. There is also a mask ACE, which specifies the maximum
allowable permissions for the owning group and any named users and
groups. Let U be the euid of the process attempting access to the file or
folder with certain requested permissions. To determine whether to grant
access, the operating system tries to match the following conditions and
selects the ACE associated with the first matching condition:
• U is the userid of the file owner: the ACE for owner;
• U is one of the named users: the ACE for U;
• one of the groups of U is the owning group and the ACE for group
contains the requested permissions: the ACE for group;
• one of the groups of U is a named group G and its ACE contains the
requested permissions: the ACE for G;
• for each group G of U that is the owning group or a named group,
the ACE for G does not contain the requested permissions: the empty
ACE;
• otherwise: the ACE for other.

141
 Operating Systems Security

If the ACE for owner or other or the empty ACE has been selected, then
its permissions determine access. Else, the selected ACE is “ANDed”
with the mask ACE and the permissions of the resulting ACE determine
access. Note that the although multiple ACEs could be selected in the
fourht condition, the access decision does not depend on the specific ACE
selected. At the time of this writing, Linux’s ACL scheme is not very widely
used, despite the fact that it allows for more flexibility in access control.
Some Linux distributions have even more advanced access control
mechanisms. Security-Enhanced Linux (SELinux), developed primarily
by the United States National Security Agency, is a series of security en-
hancements designed to be applied to Unix-like systems. SELinux features
strictly enforced mandatory access control, which defines virtually every
allowable action on a machine. Each rule consists of a subject, referring to
the process attempting to gain access, an object, referring to the resource
being accessed, and a series of permissions, which are checked by the
operating system appropriately. SELinux embodies the principle of least
privilege: limiting every process to the bare minimum permissions needed
to function properly, which significantly minimizes the effects of a security
breach. In addition, unlike DAC, users are not given the power to decide
security attributes of their own files. Instead, this is delegated to a central
security policy administrator. These enhancements allow SELinux to create
a much more restrictive security environment.

Windows Permissions
Windows uses an ACL model that allows users to create sets of rules for
each user or group. These rules either allow or deny various permissions
for the corresponding principal. If there is no applicable allow rule, access
is denied by default. The basic permissions are known as standard permis-
sions, which for files consist of modify, read and execute, read, write, and
finally, full control, which grants all permissions. Figure 13 depicts the
graphical interface for editing permissions in Windows XP.
To finely tune permissions, there are also advanced permissions, which
the standard permissions are composed of. These are also shown in Fig-
ure 13. For example, the standard read permission encompasses several
advanced permissions: read data, read attributes, read extended attributes,
and read permissions. Setting read to allow for a particular principal
automatically allows each of these advanced permissions, but it is also
possible to set only the desired advanced permissions.
As in Linux, folders have permissions too: read is synonymous with the
ability to list the contents of a folder, and write allows a user to create new
files within a folder. However, while Linux checks each folder in the path to

142
 Operating Systems Security

Figure 13: Customizing file permissions in Windows XP.

Microsoft® and Windows® are registered trademarks of the
Microsoft Corporation in the U.S.A. and other countries.
Screen shots and icons reprinted with permission from the
Microsoft Corporation. This book is not sponsored or endorsed
by or affiliated with the Microsoft Corporation.

a file before allowing access, Windows has a different scheme. In Windows,

the path to a file is simply an identifier that has no bearing on permissions.
Only the ACL of the file in question is inspected before granting access. This
allows administrators to deny a user access to a folder, but allow access to
a file within that folder, which would not be possible in Linux.
In Windows, any ACEs applied to a folder may be set to apply not to just
the selected folder, but also to the subfolders and files within it. The ACEs
automatically generated in this way are called inherited ACEs, as opposed
to ACEs that are specifically set, which are called explicit ACEs. Note
that administrators may stop the propagation of inheritance at a particular
folder, ensuring that the children of that folder do not inherit ACEs from
ancestor folders.
This scheme of inheritance raises the question of how ACEs should take
precedence. In fact, there is a simple hierarchy that the operating system
uses when making access control decision. At any level of the hierarchy,
deny ACEs take precedence over allow ACEs. Also, explicit ACEs take
precedence over inherited ACEs, and inherited ACEs take precedence in
order of the distance between the ancestor and the object in question—the
parent’s ACEs take precedent over the grandparent’s ACEs, and so on.
With this algorithm in place, resolving permissions is a simple matter
of enumerating the entries of the ACL in the appropriate order until an
applicable rule is found. This hierarchy, along with the finely granulated
control of Windows permissions, provides administrators with substantial
flexibility, but also may create the potential for security holes due to its
complexity—if rules are not carefully applied, sensitive resources may be
exposed.

143
 Operating Systems Security

The SetUID Bit

A related access-control question of operating systems security is how to

give certain programs permission to perform tasks that the users running
them should not otherwise be allowed to do. For example, consider the
password mechanism in early Unix systems, where user login information
is stored in /etc/passwd. Clearly, ordinary users should not be able to edit
this file, or a user could simply change the password of another user and
assume their identity. However, users should be allowed to change their
own passwords.

In other words, a program is needed that can be run by an ordinary user,

allowing changes to a file that ordinary users cannot alter. In the existing
architecture, however, this doesn’t seem possible. Since processes inherit
the permissions of their parent process, a password-changing program run
by an ordinary user would be restricted to the permissions of that user, and
would be unable to write to the /etc/passwd file.

To solve this problem, Unix systems have an additional bit in the file
permission matrix known as a setuid bit. If this bit is set, then that program
runs with the effective user ID of its owner, rather than the process that
executed it. For example, the utility used to change passwords in Unix is
passwd. This program is owned by the root account, has the execute bit set
for the others class, and has the setuid bit set. When a user runs passwd,
the program runs with the permissions of the root user, allowing it to alter
the /etc/passwd file, which can only be written by the root user. Setuid
programs can also drop their higher privileges by making calls to the setuid
family of functions.

Although it is less commonly used, it is possible to set a setgid bit, which

functions similarly to setuid, but for groups. When the setgid bit is set, the
effective group ID of the running process is equal to the ID of the group
that owns the file, as opposed to the group id of the parent process.

The setuid mechanism is effective in that it solves the access-without-

privileges problem, but it also raises some security concerns. In particu-
lar, it requires that setuid programs are created using safe programming
practices. If an attacker can force a setuid program to execute arbitrary
code, as we discuss later with respect to buffer overflow attacks, then the
attacker can exploit the setuid mechanism to assume the permissions of the
program’s owner, creating a privilege escalation scenario.

144
 Operating Systems Security

An Example SetUID Program

An example setuid program can be found in Code Fragment 1. In this

example, the application calls seteuid() to drop and restore its permissions.
Note that this program runs with the permissions of the user for most of
its execution, but briefly raises its permissions to that of its owner in order
to write to a log file that ordinary users presumably cannot access.

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>

static uid t euid, uid;

int main(int argc, char * argv[ ])

{
FILE *file;
/* Store real and effective user IDs */
uid = getuid();
euid = geteuid();
/* Drop priviliges */
seteuid(uid);
/* Do something useful */
/* . . . */
/* Raise privileges */
seteuid(euid);
/* Open the file */
file = fopen("/home/admin/log", "a");
/* Drop privileges again */
seteuid(uid);
/* Write to the file */
fprintf(file, "Someone used this program.\n");
/* Close the file stream and return */
fclose(file);
return 0;
}

Code Fragment 1: A simple C program that uses seteuid() to change its

permissions. The fprintf action is done using the permissions of the owner
of this program, not the user running this program.

145
 Operating Systems Security

3.4 File Descriptors

In order for processes to work with files, they need a shorthand way to
refer to those files, other than always going to the filesystem and specifying
a path to the files in question. In order to efficiently read and write files
stored on disk, modern operating systems rely on a mechanism known
as file descriptors. File descriptors are essentially index values stored in
a table, aptly known as the file descriptor table. When a program needs
to access a file, a call is made to the open system call, which results in
the kernel creating a new entry in the file descriptor table which maps
to the file’s location on the disk. This new file descriptor is returned to
the program, which can now issue read or write commands using that file
descriptor. When receiving a read or write system call, the kernel looks
up the file descriptor in the table and performs the read or write at the
appropriate location on disk. Finally, when finished, the program should
issue the close system call to remove the open file descriptor.

Reading and Writing with File Descriptors

Several security checks occur during the process of performing a read or
write on a file, given its file descriptor. When the open system call is issued,
the kernel checks that the calling process has permission to access the file
in the manner requested—for example, if a process requests to open a file
for writing, the kernel ensures that the file has the write permission set for
that process before proceeding. Next, whenever a call to read or write is
issued, the kernel checks that the file descriptor being written to or read
from has the appropriate permissions set. If not, the read or write fails and
the program typically halts.
On most modern systems, it is possible to pass open file descriptors
from one process to another using ordinary IPC mechanisms. For exam-
ple, on Unix-based systems (including Linux) it is possible to open a file
descriptor in one process and send a copy of the file descriptor to another
process via a local socket.

File Descriptor Leaks

A common programming error that can lead to serious security problems is
known as a file descriptor leak. A bit of additional background is required
to understand this type of vulnerability. First, it is important to note
that when a process creates a child process (using a fork command), that
child process inherits copies of all of the file descriptors that are open in
the parent. Second, the operating system only checks whether a process

146
 Operating Systems Security

has permissions to read or write to a file at the moment of creating a

file descriptor entry; checks performed at the time of actually reading or
writing to a file only confirm that the requested action is allowed according
to the permissions the file descriptor was opened with. Because of these
two behaviors, a dangerous scenario can arise when a program with high
privileges opens a file descriptor to a protected file, fails to close it, and then
creates a process with lower permissions. Since the new process inherits
the file descriptors of its parent, it will be able to read or write to the
file, depending on how the parent process issued the open system call,
regardless of the fact that the child process might not have permission to
open that file in other circumstances.

An Example Vulnerability

An example of this scenario can be found in Code Fragment 2. Notice in

this example how there is no call to close the file descriptor before executing
a new process. As a result, the child is able to read the file. In a situation
such as this one, the child could access the open file descriptor via a number
of mechanisms, most commonly using the fcntl() family of functions. To fix
this vulnerability, a call to fclose(), which would close the file descriptor,
should be made before executing the new program.

#include <stdio.h>
#include <unistd.h>

int main(int argc, char * argv[ ])

{

/* Open the password file for reading */

FILE *passwords;
passwords = fopen("/home/admin/passwords", "r");

/* Read the passwords and do something useful */

/* . . . */

/* Fork and execute Joe’s shell without closing the file */

execl("/home/joe/shell", "shell", NULL);

Code Fragment 2: A simple C program vulnerable to a file descriptor leak.

147
 Operating Systems Security

3.5 Symbolic Links and Shortcuts

It is often useful for users to be able to create links or shortcuts to other

files on the system, without copying the entire file to a new location. For
example, it might be convenient for a user to have a link to a program on
their desktop while keeping the actual program at another location. In this
way, if the user updates the underlying file, all links to it will automatically
be referring to the updated version.
In Linux and other Unix-based systems, this can be accomplished
through the use of symbolic links, also known as symlinks or soft links,
which can be created using the ln command. To the user, symlinks appear to
reside on the disk like any other file, but rather than containing information,
they simply point to another file or folder on disk.
This linking is completely transparent to applications, as well. If a
program attempts to open and read from a symlink, the operating system
follows the link so that the program actually interacts with the file the
symlink is pointing to. Symlinks can be chained together, so that one
symlink points to another, and so on, as long as the final link points to an
actual file. In these cases, programs attempting to access a symlink follow
the chain of links until reaching the file.
Symlinks can often provide a means by which malicious parties can
trick applications into performing undesired behavior, however. As an
example, consider a program that opens and reads a file specified by the
user. Suppose that this program is designed specifically to prohibit the
reading of one particular file, say, /home/admin/passwords, for example.
An unsafe version of this program would simply check that the filename
specified by the user is not /home/admin/passwords. However, an attacker
could trick this program by creating a symlink to the passwords file and
specifying the path of the symlink instead. To solve this aliasing problem,
the program should either check if the provided filename refers to a sym-
link, or confirm the actual filename being opened by using a stat system
call, which retrieves information on files.
More recent versions of Windows support symlinks similar to those on
Unix, but much more common is the use of shortcuts. A shortcut is similar
to a symlink in that it is simply a pointer to another file on disk. However,
while symlinks are automatically resolved by the operating system so that
their use is transparent, Windows shortcuts appear as regular files, and only
programs that specifically identify them as shortcuts can follow them to the
referenced files. This prevents most of the symlink attacks that are possible
on Unix-based systems, but also limits their power and flexibility.

148
 Operating Systems Security

4 Application Program Security

Many attacks don’t directly exploit weaknesses in the OS kernel, but rather
attack insecure programs. These programs, operating at the applications
layer, could even be nonkernel operating system programs, such as the pro-
gram to change passwords, which runs with higher privileges than those
granted to common users. So these programs should be protected against
privilege escalation attacks. But before we can describe such protections,
we need to first discuss some details about program creation.

4.1 Compiling and Linking

The process of converting source code, which is written in a programming
language, such as Java or C++, to the machine code instructions that a
processor can execute is known as compiling. A program may be compiled
to be either statically linked or dynamically linked. With static linking,
all shared libraries, such as operating system functions, that a program
needs during its execution are essentially copied into the compiled program
on disk. This may prove to be safer from a security perspective, but is
inconvenient in that it uses additional space for duplicate code that might
be used by many programs, and it may limit debugging options.
The alternative is dynamic linking, where shared libraries are loaded
when the program is actually run. When the program is executed, the
loader determines which shared libraries are needed for the program, finds
them on the disk, and imports them into the process’s address space. In
Microsoft Windows, each of these external libraries is known as a dynamic
linking library (DLL), while in many Unix systems, they are simply referred
to as shared objects. Dynamic linking is an optimization that saves space
on the hard disk, and allows developers to modularize their code. That
is, instead of recompiling an entire application, it may be possible to alter
just one DLL, for instance, to fix a bug since DLL that could potentially
affect many other programs. The process of injecting arbitrary code into
programs via shared libraries is known as DLL injection. DLL injection can
be incredibly useful for the purposes of debugging, in that programmers
can easily change functions in their applications without recompiling their
code. However, this technique poses a potential security risk because it may
allow malicious parties to inject their own code into legitimate programs.
Imagine the consequences if a guest user redefined a function called by a
system administrator program; hence, the need for administrative privi-
leges.

149
 Operating Systems Security

4.2 Simple Buffer Overflow Attacks

A classic example of such an application program attack, which allows for
privilege escalation, is known as a buffer overflow attack. In any situation
where a program allocates a fixed-size buffer in memory in which to store
information, care must be taken to ensure that copying user-supplied data
to this buffer is done securely and with boundary checks. If this is not the
case, then it may be possible for an attacker to provide input that exceeds
the length of the buffer, which the program will then dutifully attempt to
copy to the allotted buffer. However, because the provided input is larger
than the buffer, this copying may overwrite data beyond the location of the
buffer in memory, and potentially allow the attacker to gain control of the
entire process and execute arbitrary code on the machine (recall that the
address space for a process includes both the data and the code for that
process).

Arithmetic Overflow
The simplest kind of overflow condition is actually a limitation having
to do with the representation of integers in memory. In most 32-bit ar-
chitectures, signed integers (those that can be either positive or negative)
are expressed in what is known as two’s compliment notation. In hex
notation, signed integers 0x00000000 to 0x7ffffff (equivalent to 231 − 1)
are positive numbers, and 0x80000000 to 0xffffffff are negative numbers.
The threshold between these two ranges allows for overflow or under-
flow conditions. For example, if a program continually adds very large
numbers and eventually exceeds the maximum value for a signed integer,
0x7fffffff, the representation of the sum overflows and becomes negative
rather than positive. Similarly, if a program adds many negative numbers,
eventually the sum will underflow and become positive. This condition
also applies to unsigned integers, which consist of only positive numbers
from 0x00000000 to 0xffffffff. Once the highest number is reached, the next
sequential integer wraps around to zero.

An Example Vulnerability
This numerical overflow behavior can sometimes be exploited to trick an
application to perform undesirable behavior. As an example, suppose a
network service keeps track of the number of connections it has received
since it has started, and only grants access to the first five users. An unsafe
implementation can be found in Code Fragment 3.

150
 Operating Systems Security

#include <stdio.h>

int main(int argc, char * argv[ ])

{
unsigned int connections = 0;
// Insert network code here
// . . .
// . . .
// Does nothing to check overflow conditions
connections++;
if(connections < 5)
grant access();
else
deny access();
return 1;
}
Code Fragment 3: A C program vulnerable to an arithmetic overflow.

An attacker could compromise the above system by making a huge

number of connections until the connections counter overflows and wraps
around to zero. At this point, the attacker will be authenticated to the
system, which is clearly an undesirable outcome. To prevent these types of
attacks, safe programming practices must be used to ensure that integers
are not incremented or decremented indefinitely and that integer upper
bounds or lower bounds are respected. An example of a safe version of
the program above can be found in Code Fragment 4.
#include <stdio.h>

int main(int argc, char * argv[ ])

{
unsigned int connections = 0;
// Insert network code here
// . . .
// . . .
// Prevents overflow conditions
if(connections < 5)
connections++;
if(connections < 5)
grant access();
else
deny access();
return 1;
}
Code Fragment 4: A variation of the program in Code Fragment 3, protected
against arithmetic overflow.

151
 Operating Systems Security

4.3 Stack-Based Buffer Overflow

Another type of buffer overflow attack exploits the special structure of the
memory stack. Recall from Section 1.4, that the stack is the component of
the memory address space of a process that contains data associated with
function (or method) calls. The stack consists of frames, each associated
with an active call. A frame stores the local variables and arguments of
the call and the return address for the parent call, i.e., the memory address
where execution will resume once the current call terminates. At the base
of the stack is the frame of the main() call. At the end of the stack is the
frame of the currently running call. This organizational structure allows for
the CPU to know where to return to when a method terminates, and it also
automatically allocates and deallocates the space local variables require.
In a buffer overflow attack, an attacker provides input that the program
blindly copies to a buffer that is smaller than the input. This commonly
occurs with the use of unchecked C library functions, such as strcpy() and
gets(), which copy user input without checking its length.
A buffer overflow involving a local variable can cause a program to
overwrite memory beyond the buffer’s allocated space in the stack, which
can have dangerous consequences. An example of a program that has a
stack buffer overflow vulnerability is shown in Code Fragment 5.
In a stack-based buffer overflow, an attacker could overwrite local vari-
ables adjacent in memory to the buffer, which could result in unexpected
behavior. Consider an example where a local variable stores the name of a
command that will be eventually executed by a call to system(). If a buffer
adjacent to this variable is overflowed by a malicious user, that user could
replace the original command with one of his or her choice, altering the
execution of the program.

#include <stdio.h>

int main(int argc, char * argv[ ])

{
// Create a buffer on the stack
char buf[256];
// Does not check length of buffer before copying argument
strcpy(buf,argv[1]);
// Print the contents of the buffer
printf("%s\n",buf);
return 1;
}

Code Fragment 5: A C program vulnerable to a stack buffer overflow.

152
 Operating Systems Security

Although this example is somewhat contrived, buffer overflows are

actually quite common (and dangerous). A buffer overflow attack is es-
pecially dangerous when the buffer is a local variable or argument within
a stack frame, since the user’s input may overwrite the return address
and change the execution of the program. In a stack smashing attack, the
attacker exploits a stack buffer vulnerability to inject malicious code into the
stack and overwrite the return address of the current routine so that when
it terminates, execution is passed to the attacker’s malicious code instead
of the calling routine. Thus, when this context switch occurs, the malicious
code will be executed by the process on behalf of the attacker. An idealized
version of a stack smashing attack, which assumes that the attacker knows
the exact position of the return address, is illustrated in Figure 14.
previous frames

attacker’s input
malicious code

return address next memory location

current frame

padding
buffer

program code program code

(a) (b)

Figure 14: A stack smashing attack under the assumption that the attacker
knows the position of the return address. (a) Before the attack, the return
address points to a location in the program code. (b) Exploiting the unpro-
tected buffer, the attacker injects into the address space input consisting of
padding up to the return address location, a modified return address that
points to the next memory location, and malicious code. After completing
execution of the current routine, control is passed to the malicious code.

153
 Operating Systems Security

Seizing Control of Execution

In a realistic situation of a stack-based buffer overflow attack, the first

problem for the attacker is to guess the location of the return address with
respect to the buffer and to determine what address to use for overwriting
the return address so that execution is passed to the attacker’s code. The
nature of operating system design makes this challenging for two reasons.
First, processes cannot access the address spaces of other processes, so
the malicious code must reside within the address space of the exploited
process. Because of this, the malicious code is often kept in the buffer itself,
as an argument to the process provided when it is started, or in the user’s
shell environment, which is typically imported into the address space of
processes.
Second, the address space of a given process is unpredictable and may
change when a program is run on different machines. Since all programs
on a given architecture start the stack at the same relative address for each
process, it is simple to determine where the stack starts, but even with
this knowledge, knowing exactly where the buffer resides on the stack is
difficult and subject to guesswork.
Several techniques have been developed by attackers to overcome
these challenges, including NOP sledding, return-to-libc, and the jump-
to-register or trampolining techniques.

NOP Sledding

NOP sledding is a method that makes it more likely for the attacker to
successfully guess the location of the code in memory by increasing the size
of the target. A NOP or No-op is a CPU instruction that does not actually
do anything except tell the processor to proceed to the next instruction.
To use this technique, the attacker crafts a payload that contains an ap-
propriate amount of data to overrun the buffer, a guess for a reasonable
return address in the process’s address space, a very large number of NOP
instructions, and finally, the malicious code. When this payload is provided
to a vulnerable program, it copies the payload into memory, overwriting the
return address with the attacker’s guess. In a successful attack, the process
will jump to the guessed return address, which is likely to be somewhere in
the high number of NOPs (known as the NOP sled). The processor will then
“sled through” all of the NOPs until it finally reaches the malicious code,
which will then be executed. NOP sledding is illustrated in Figure 15.

154
 Operating Systems Security

Before Copying
Other
Return
Buffer Program
Address
Data

After Copying
Guessed
Address
Junk Padding of
NOPs Shellcode
Shellcode

Figure 15: The NOP sledding technique for stack smashing attacks.

Trampolining

Despite the fact that NOP sledding makes stack-based buffer overflows
much more likely to succeed, they still require a good deal of guesswork
and are not extremely reliable. Another technique, known as jump-to-
register or trampolining, is considered more precise. As mentioned above,
on initialization, most processes load the contents of external libraries
into their address space. These external libraries contain instructions that
are commonly used by many processes, system calls, and other low-level
operating system code. Because they are loaded into the process’s address
space in a reserved section of memory, they are in predictable memory
locations. Attackers can use knowledge of these external libraries to per-
form a trampolining attack. For example, an attacker might be aware of a
particular assembly code instruction in a Windows core system DLL and
suppose this instruction tells the processor to jump to the address stored in
one of the processor’s registers, such as ESP. If the attacker can manage
to place his malicious code at the address pointed to by ESP and then
overwrite the return address of the current function with the address of
this known instruction, then on returning, the application will jump and
execute the jmp esp instruction, resulting in execution of the attacker’s
malicious code. Once again, specific examples will vary depending on the
application and the chosen library instruction, but in general this technique
provides a reliable way to exploit vulnerable applications that is not likely
to change on subsequent attempts on different machines, provided all of the
machines involved are running the same version of the operating system.

155
 Operating Systems Security

The Return-to-libc Attack

A final attack technique, known as a return-to-libc attack, also uses the
external libraries loaded at runtime—in this case, the functions of the C
library, libc. If the attacker can determine the address of a C library function
within a vulnerable process’s address space, such as system() or execv, this
information can be used to force the program to call this function. The
attacker can overflow the buffer as before, overwriting the return address
with the address of the desired library function. Following this address,
the attacker must provide a new address that the libc function will return
to when it is finished execution (this may be a dummy address if it is
not necessary for the chosen function to return), followed by addresses
pointing to any arguments to that function. When the vulnerable stack
frame returns, it will call the chosen function with the arguments provided,
potentially giving full control to the attacker. This technique has the added
advantage of not executing any code on the stack itself. The stack only
contains arguments to existing functions, not actual shellcode. Therefore,
this attack can be used even when the stack is marked as nonexecutable.

Shellcode
Once an attacker has crafted a stack-based buffer overflow exploit, they
have the ability to execute arbitrary code on the machine. Attackers often
choose to execute code that spawns a terminal or shell, allowing them to
issue further commands. For this reason, the malicious code included in an
exploit is often known as shellcode. Since this code is executed directly on
the stack by the CPU, it must be written in assembly language, low-level
processor instructions, known as opcodes, that vary by CPU architecture.
Writing usable shellcode can be difficult. For example, ordinary assembly
code may frequently contain the null character, 0x00. However, this code
cannot be used in most buffer overflow exploits, because this character
typically denotes the end of a string, which would prevent an attacker from
successfully copying his payload into a vulnerable buffer; hence, shellcode
attackers employ tricks to avoid null characters.
Buffer overflow attacks are commonly used as a means of privilege
escalation by exploiting SetUID programs. Recall that a SetUID program
can be executed by low-level users, but is allowed to perform actions on
behalf of its owner, who may have higher permissions. If a SetUID program
is vulnerable to a buffer overflow, then an attack might include shellcode
that first executes the setuid() system call, and then spawns a shell. This
would result in the attacker gaining a shell with the permissions of the
exploited process’s owner, and possibly allow for full system compromise.

156
 Operating Systems Security

Preventing Stack-Based Buffer Overflow Attacks

Many measures have been developed to combat buffer overflow attacks.

First, the root cause of buffer overflows is not the operating system it-
self, but rather insecure programming practices. Programmers must be
educated about the risks of insecurely copying user-supplied data into
fixed-size buffers, and ensure that their programs never attempt to copy
more information than can fit into a buffer. Many popular programming
languages, including C and C++, are susceptible to this attack, but other
languages do not allow the behavior that makes buffer overflow attacks
possible. To fix the previous example, the safer strncpy function should be
used, as in Code Fragment 6.

#include <stdio.h>

int main(int argc, char * argv[ ])

{
// Create a buffer on the stack
char buf[256];
// Only copies as much of the argument as can fit in the buffer
strncpy(buf, argv[1], sizeof(buf));
// Print the contents of the buffer
printf("%s\n",buf);
return 1;
}

Code Fragment 6: A C program protected against a stack buffer overflow.

Because of the dangers of buffer overflows, many operating systems

have incorporated protection mechanisms that can detect if a stack-based
buffer overflow has occurred (at which point the OS can decide how to deal
with this discovery). One such technique directly provides stack-smashing
protection by detecting when a buffer overflow occurs and at that point
prevent redirection of control to malicious code.

There are several implementations of this technique, all of which in-

volve paying closer attention to how data is organized in the method stack.
One such implementation, for instance, reorganizes the stack data allotted
to programs and incorporates a canary, a value that is placed between a
buffer and control data (which plays a similar role to a canary in a coal
mine). The system regularly checks the integrity of this canary value, and
if it has been changed, it knows that the buffer has been overflowed and it
should prevent malicious code execution. (See Figure 16.)

157
 Operating Systems Security

Normal (safe) stack configuration:

Other local Canary Return

Buffer (random) Other data
variables address

Buffer overflow attack attempt:

Corruptt
C
Buffer Overflow data return Attack code
address

Figure 16: Stack-based buffer overflow detection using a random canary.

The canary is placed in the stack prior to the return address, so that any
attempt to overwrite the return address also overwrites the canary.

Other systems are designed to prevent the attacker from overwriting

the return address. Microsoft developed a compiler extension called Point-
Guard that adds code which XOR-encodes any pointers, including the
return address, before and after they are used. As a result, an attacker
would not be able to reliably overwrite the return address with a location
that would lead to a valid jump. Yet another approach is to prevent
running code on the stack by enforcing a no-execution permission on the
stack segment of memory. If the attacker’s shellcode were not able to run,
then exploiting an application would be difficult. Finally, many operating
systems now feature address space layout randomization (ASLR), which
rearranges the data of a process’s address space at random, making it
extremely difficult to predict where to jump in order to execute code.
Despite these protection mechanisms, researchers and hackers alike
have developed newer, more complicated ways of exploiting buffer over-
flows. For example, popular ASLR implementations on 32-bit Windows
and Linux systems have been shown to use an insufficient amount of
randomness to fully prevent brute-force attacks, which has required ad-
ditional techniques to provide stack-smashing protection. The message is
clear, operating systems may have features to reduce the risks of buffer
overflows, but ultimately, the best way to guarantee safety is to remove
these vulnerabilities from application code. The primary responsibility
rests on the programmer to use safe coding practices.

158
 Operating Systems Security

4.4 Heap-Based Buffer Overflow Attacks

Memory on the stack is either allocated statically, which is determined

when the program is compiled, or it is allocated and removed automatically
when functions are called and returned. However, it is often desirable to
give programmers the power to allocate memory dynamically and have it
persist across multiple function calls. This memory is allocated in a large
portion of unused memory known as the heap.

Dynamic memory allocation presents a number of potential problems

for programmers. For one, if programmers allocate memory on the heap
and do not explicitly deallocate (free) that block, it remains used and can
cause memory leak problems, which are caused by memory locations that
are allocated but are not actually being used.

From a security standpoint, the heap is subject to similar problems as

the stack. A program that copies user-supplied data into a block of memory
allocated on the heap in an unsafe way can result in overflow conditions,
allowing an attacker to execute arbitrary code on the machine. An example
of a vulnerable program can be found in Code Fragment 7.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[ ])

{
// Allocate two adjacent blocks on the heap
char *buf = malloc(256);
char *buf2 = malloc(16);
// Does not check length of buffer before copying argument
strcpy(buf, argv[1]);
// Print the argument
printf("Argument: %s\n", buf);
// Free the blocks on the heap
free(buf);
free(buf2);
return 1;
}

Code Fragment 7: A simple C program vulnerable to a heap overflow.

159
 Operating Systems Security

As with stack overflows, these problems can be mitigated by using

safe programming practices, including replacing unsafe functions such as
strcpy() with safer equivalents like strncpy(). (See Code Fragment 8.)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[ ])

{
// Allocate two adjacent blocks on the heap
char *buf = malloc(256);
char *buf2 = malloc(16);
// Only copies as much of the argument as can fit in the buffer
strncpy(buf, argv[1], 255);
// Print the argument
printf("Argument: %s\n", buf);
// Free the blocks on the heap
free(buf);
free(buf2);
return 1;
}

Code Fragment 8: A simple C program protected against a heap overflow.

Heap-based overflows are generally more complex than the more

prevalent stack-based buffer overflows and require a more in-depth under-
standing of how garbage collection and the heap are implemented. Unlike
the stack, which contains control data that if altered changes the execution
of a program, the heap is essentially a large empty space for data. Rather
than directly altering control, heap overflows aim to either alter data on
the heap or abuse the functions and macros that manage the memory on
the heap in order to execute arbitrary code. The specific attack used varies
depending on the particular architecture.

An Example Heap-Based Overflow Attack

As an example, let us consider an older version of the GNU compiler (GCC)
implementation of malloc(), the function that allocates a block of memory
on the heap. In this implementation, blocks of memory on the heap are
maintained as a linked list—each block has a pointer to the previous and
next blocks in the list. When a block is marked as free, the unlink() macro
is used to set the pointers of the adjacent blocks to point to each other,
effectively removing the block from the list and allowing the space to be

160
 Operating Systems Security

reused. One heap overflow technique takes advantage of this system. If an

attacker provides user input to a program that unsafely copies the input to
a block on the heap, the attacker can overflow the bounds of that block and
overwrite portions of the next block. If this input is carefully crafted, it may
be possible to overwrite the linked list pointers of the next block and mark
it as free, in such a way that the unlink routine is tricked into writing data
into an arbitrary address in memory. In particular, the attacker may trick
the unlink routine into writing the address of his shellcode into a location
that will eventually result in a jump to the malicious code, resulting in the
execution of the attacker’s code.

One such location that may be written to in order to compromise a

program is known as .dtors. Programs compiled with GCC may feature
functions marked as constructor or destructor functions. Constructors are
executed before main(), and destructors are called after main() has returned.
Therefore, if an attacker adds the address of his shellcode to the .dtors
section, which contains a list of destructor functions, his code will be
executed before the program terminates. Another potential location that is
vulnerable to attacks is known as the global offset table (GOT). This table
maps certain functions to their absolute addresses. If an attacker overwrites
the address of a function in the GOT with the address of his shellcode and
this function is called, the program will jump to and execute the shellcode,
once again giving full control to the attacker.

Preventing Heap-Based Buffer Overflow Attacks

Prevention techniques for heap-based overflow attacks resemble those for

stack-based overflows. Address space randomization prevents the attacker
from reliably guessing memory locations, making the attack more difficult.
In addition, some systems make the heap nonexecutable, making it more
difficult to place shellcode. Newer implementations of dynamic memory
allocation routines often choose to store heap metadata (such as the pointers
to the previous and next blocks of heap memory) in a location separate from
the actual data stored on the heap, which makes attacks such as the unlink
technique impossible. Once again, the single most important preventive
measure is safe programming. Whenever a program copies user-supplied
input into a buffer allocated on the heap, care must be taken to ensure that
the program does not copy more data than that buffer can hold.

161
 Operating Systems Security

4.5 Format String Attacks

The printf family of C library functions are used for I/O, including printing
messages to the user. These functions are typically designed to be passed an
argument containing the message to be printed, along with a format string
that denotes how this message should be displayed. For example, calling
printf(“%s”,message) prints the message variable as a string, denoted by
the format string %s. Format strings can also write to memory. The %n
format string specifies that the print function should write the number of
bytes output so far to the memory address of the first argument to the
function.
When a programmer does not supply a format string, the input ar-
gument to the print function controls the format of the output. If this
argument is user-supplied, then an attacker could carefully craft an input
that uses format strings, including %n, to write to arbitrary locations in
memory. This could allow an attacker to seize control and execute arbitrary
code in the context of the program by overwriting a return address, function
pointer, etc. An example of a program with a format string vulnerability can
be found in Code Fragment 9, where the printf() function is called without
providing a format string.

#include <stdio.h>
int main(int argc, char * argv[ ])
{
printf("Your argument is:\n");
// Does not specify a format string, allowing the user to supply one
printf(argv[1]);
}
Code Fragment 9: A C program vulnerable to a format string bug.

Once again, the solution to this attack lies in the hands of the program-
mer. To prevent format string attacks, programmers should always provide
format strings to the printf function family, as in Code Fragment 10.

#include <stdio.h>
int main(int argc, char * argv[ ])
{
printf("Your argument is:\n");
// Supplies a format string
printf("%s",argv[1]);
}
Code Fragment 10: A C program protected against a format string bug.

162
 Operating Systems Security

4.6 Race Conditions

Another programming error that can lead to compromise by malicious

users is the introduction of what is known as a race condition. A race con-
dition is any situation where the behavior of the program is unintentionally
dependent on the timing of certain events.
A classic example makes use of the C functions access() and open().
The open() function, used to open a file for reading or writing, opens
the specified file using the effective user ID (rather than the real user ID)
of the calling process to check permissions. In other words, if a SetUID
program owned by the root user is run by an ordinary user, that program
can successfully call open() on files that only the root user has permission
to access. The access() function checks whether the real user (in this case,
the user running the program) has permission to access the specified file.
Suppose there were a simple program that takes a filename as an argu-
ment, checks whether the user running the program has permission to open
that file, and if so, reads the first few characters of the file and prints them.
This program might be implemented as in Code Fragment 11.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <fcntl.h>
int main(int argc, char * argv[ ])
{
int file;
char buf[1024];
memset(buf, 0, 1024);
if(argc < 2) {
printf("Usage: printer [filename]\n");
exit(−1);
}
if(access(argv[1], R OK) != 0) {
printf("Cannot access file.\n");
exit(−1);
}
file = open(argv[1], O RDONLY);
read(file, buf, 1023);
close(file);
printf("%s\n", buf);
return 0;
}
Code Fragment 11: A C program vulnerable to a race condition.

163
 Operating Systems Security

The Time of Check/Time of Use Problem

There is a race condition in the above implementation. In particular, there
is a tiny, almost unnoticeable time delay between the calls to access()
and open(). An attacker could exploit this small delay by changing the
file in question between the two calls. For example, suppose the attacker
provided /home/joe/dummy as an argument, an innocent text file that the
attacker can access. After the call to access() returns 0, indicating the
user has permission to access the file, the attacker can quickly replace
/home/joe/dummy with a symbolic link to a file that he does not have
permission to read, such as /etc/passwd.

Next, the program will call open() on the symbolic link, which will be
successful because the program is SetUID root and has permission to open
any files accessible to the root user. Finally, the program will dutifully read
and print the contents of the file.

Note that this type of attack could not be done manually; the time
difference between two function calls is small enough that no human would
be able to change the files fast enough. However, it would be possible
to have a program running in the background that repeatedly switches
between the two files—one legitimate and one just a symbolic link—and
runs the vulnerable program repeatedly until the switch occurred in exactly
the right place.

In general, this type of vulnerability is known as a Time of Check/Time

of Use (TOCTOU) problem. Any time a program checks the validity and
authorizations for an object, whether it be a file or some other property,
before performing an action on that object, care should be taken that these
two operations are performed atomically, that is, they should be performed
as a single uninterruptible operation. Otherwise, the object may be changed
in between the time it is checked and the time it is used. In most cases, such
a modification simply results in erratic behavior, but in some, such as this
example, the time window can be exploited to cause a security breach.

To safely code the example above, the call to access() should be com-
pletely avoided. Instead, the program should drop its privileges using
seteuid() before calling open(). This way, if the user running the program
does not have permission to open the specified file, the call to open() will
fail. A safe version of the program can be found in Code Fragment 12.

164
 Operating Systems Security

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <fcntl.h>
int main(int argc, char * argv[ ])
{
int file;
char buf[1024];
uid t uid, euid;
memset(buf, 0, 1024);
if(argc < 2) {
printf("Usage: printer [filename]\n");
exit(−1);
}
euid = geteuid();
uid = getuid();
/* Drop privileges */
seteuid(uid);
file = open(argv[1], O RDONLY);
read(file, buf, 1023);
close(file);
/* Restore privileges */
seteuid(euid);
printf("%s\n", buf);
return 0;
}

Code Fragment 12: A simple C program that is protected against a race

condition.

165
 Operating Systems Security

5 Exercises
For help with exercises, please visit securitybook.net.

Reinforcement
R-1 How can multitasking make a single processor look like it is run-
ning multiple programs at the same time?
R-2 Give an example of three operating systems services that do not
belong in the kernel?
R-3 If a process forks two processes and these each fork two processes,
how many processes are in this part of the process tree?
R-4 What is the advantage of booting from the BIOS instead of booting
the operating system directly?
R-5 Can a process have more than one parent? Explain.
R-6 Describe two types of IPC. What are their relative benefits and
weaknesses?
R-7 Why would it be bad to mix the stack and heap segments of
memory in the same segment?
R-8 Describe the difference between a daemon and a service.
R-9 What are the benefits of virtual memory?
R-10 Why should a security-conscious Windows user inspect processes
with Process Explorer instead of Task Manager?
R-11 What is the purpose of salting passwords?
R-12 If a password is salted with a 24-bit random number, how big is the
dictionary attack search space for a 200,000 word dictionary?
R-13 Eve has just discovered and decrypted the file that associates each
userid with its 32-bit random salt value, and she has also discov-
ered and decrypted the password file, which contains the salted-
and-hashed passwords for the 100 people in her building. If she has
a dictionary of 500,000 words and she is confident all 100 people
have passwords from this dictionary, what is the size of her search
space for performing a dictionary attack on their passwords?
R-14 Suppose farasi is a member of group hippos in a system that uses
basic Unix permissions. He creates a file pool.txt, sets its group
as hippos and sets its permissions as u=rw,g=. Can farasi read
pool.txt?

166
 Operating Systems Security

R-15 Dr. Eco claims that virtual machines are good for the environment.
How can he justify that virtualization is a green technology?
R-16 Alice, who uses a version of Unix, requires a better program to
manage her photos. She wants Bob to code this program for her.
However, she does not want Bob to be able to see some confidential
files she has in her account (for example, the solutions of some
homework). On the other hand, Bob wants to make sure that Alice
does not read his code, since this will probably be her CS032 final
project. Explain how this can be achieved by using the setuid and
chmod functions provided by UNIX. Also, assume for this question
only (regardless of real systems’ behavior), that a user cannot revert
to the real UID after using the effective UID that was set by the
setuid feature. Specifically consider the fact that Bob could embed
code in his program to transfer data it has access to, to a public
folder and/or a web server.
R-17 Is it possible to create a symbolic link to a symbolic link? Why or
why not?
R-18 Why is it pointless to give a symbolic link more restrictive access
privileges than the file it points to?
R-19 Describe the main differences between advanced file permissions
in Linux and Windows NTFS. Give an example to illustrate each
difference.
R-20 Dr. Blahbah claims that buffer overflow attacks via stack smashing
are made possible by the fact that stacks grow downwards (to-
wards smaller addresses) on most popular modern architectures.
Therefore, future architectures should ensure that the stack grows
upwards; this would provide a good defense against buffer over-
flow. Do you agree or disagree? Why?
R-21 Why is it important to protect the part of the disk that is used for
virtual memory?
R-22 Why is it unsafe to keep around the C:\hiberfil.sys file even after a
computer has been restored from hibernation?

Creativity
C-1 Bob thinks that generating and storing a random salt value for
each userid is a waste. Instead, he is proposing that his system
administrators use a SHA-1 hash of the userid as its salt. Describe
whether this choice impacts the security of salted passwords and
include an analysis of the respective search space sizes.

167
 Operating Systems Security

C-2 Alice has a picture-based password system, where she has each
user pick a set of their 20 favorite pictures, say, of cats, dogs, cars,
etc. To login, a user is shown a series of pictures in pairs—one on
the left and one on the right. In each pair, the user has to pick the
one that is in his set of favorites. If the user picks the correct 20
out of the 40 he is shown (as 20 pairs), then the system logs him in.
Analyze the security of this system, including the size of the search
space. Is it more secure than a standard password system?
C-3 Charlie likes Alice’s picture-password system of the previous exer-
cise, but he has changed the login so that it just shows the user 40
different pictures in random order and they have to indicate which
20 of these are from their set of favorites. Is this an improvement
over Alice’s system? Why or why not?
C-4 Dr. Simplex believes that all the effort spent on access control
matrices and access control lists is a waste of time. He believes
that all file access permissions for every file should be restricted
to the owner of that file, period. Describe at least three scenarios
where he is wrong, that is, where users other than a file’s owner
need some kind of allowed access privileges.
C-5 On Unix systems, a convenient way of packaging a collection of
files is a SHell ARchive, or shar file. A shar file is a shell script
that will unpack itself into the appropriate files and directories.
Shar files are created by the shar command. The implementation
of the shar command in a legacy version of the HP-UX operating
system created a temporary file with an easily predictable filename
in directory /tmp. This temporary file is an intermediate file that
is created by shar for storing temporary contents during its execu-
tion. Also, if a file with this name already exists, then shar opens
the file and overwrites it with temporary contents. If directory /tmp
allows anyone to write to it, a vulnerability exists. An attacker can
exploit such a vulnerability to overwrite a victim’s file. (1) What
knowledge about shar should the attacker have? (2) Describe the
command that the attacker issues in order to have shar overwrite
an arbitrary file of a victim. Hint: the command is issued before
shar is executed. (3) Suggest a simple fix to the shar utility to
prevent the attack. Note that this is not a setuid question.
C-6 Java is considered to be “safe” from buffer overflows. Does that
make it more appropriate to use as a development language when
security is a concern? Be sure and weigh all of the risks involved in
product development, not just the security aspects.
C-7 Dr. Blahbah has implemented a system with an 8-bit random ca-
nary that is used to detect and prevent stack-based buffer overflow

168
 Operating Systems Security

attacks. Describe an effective attack against Dr. Blahbah’s system

and analyze its likelihood of success.

C-8 Consider the following piece of C code:

int main(int argc, char *argv[])

{
char continue = 0;
char password[8];
strcpy(password, argv[1]);
if (strcmp(password, ”CS166”)==0)
continue = 1;
if (continue)
{
∗login();
}
}

In the above code, ∗login() is a pointer to the function login()

(In C, one can declare pointers to functions which means that the
call to the function is actually a memory address that indicates
where the executable code of the function lies). (1) Is this
code vulnerable to a buffer-overflow attack with reference to the
variables password[] and continue? If yes, describe how an attacker
can achieve this and give an ideal ordering of the memory cells
(assume that the memory addresses increase from left to right)
that correspond the variables password[] and continue of the code
so that this attack can be avoided. (2) To fix the problem, a security
expert suggests to remove the variable continue and simply use
the comparison for login. Does this fix the vulnerability? What
kind of new buffer overflow attack can be achieved in a multiuser
system where the login() function is shared by a lot of users (both
malicious and and nonmalicious) and many users can try to log
in at the same time? Assume for this question only (regardless
of real systems’ behavior) that the pointer is on the stack rather
than in the data segment, or a shared memory segment. (3) What
is the existing vulnerability when login() is not a pointer to the
function code but terminates with a return() command? Note that
the function strcpy does not check an array’s length.

C-9 In the StackGuard approach to solving the buffer overflow prob-

lem, the compiler inserts a canary value on the memory location
before the return address in the stack. The canary value is ran-

169
 Operating Systems Security

domly generated. When there is a return from the function call, the
compiler checks if the canary value has been overwritten or not.
Do you think that this approach would work? If yes, please explain
why it works; if not, please give a counterexample.
C-10 Another approach to protecting against buffer overflows is to rely
on address space layout randomization (ASLR). Most implementa-
tions of ASLR offset the start of each memory segment by a number
that is randomly generated within a certain range at runtime. Thus,
the starting address of data objects and code segments is a random
location. What kinds of attacks does this technique make more
difficult and why?

Projects
P-1 Write a program in pseudocode that acts as a guardian for a file, al-
lowing anyone to append to the file, but to make no other changes
to it. This may be useful, e.g., to add information to a log file.
Your program, to be named append, should take two strings file1
and file2 as arguments, denoting the paths to two files. Operation
append(String file1, String file2) copies the contents of file1 to the
end of file2, provided that the user performing the operation has
read permission for file1 and file2. If the operation succeeds, 0 is
returned. On error, −1 is returned.
Assume that the operating system supports the setuid mechanism
and that append is a setuid program owned by a user called
guardian. The file to which other files get appended (file2) is also
owned by guardian. Anyone can read its contents. However, it can
be written only by guardian. Write your program in pseudocode
using the following Java-style system calls:
(1) int open(String path to file, String mode) opens a file in a given
mode and returns a positive integer that is the descriptor of the
opened file. String mode is one of READ ONLY or WRITE ONLY.
(2) void close(int file descriptor) closes a file given its descriptor.
(3) byte[] read(int file descriptor) reads the content of the given
file into an array of bytes and returns the array. (4) void write(int
file descriptor, byte[] source buffer) stores a byte array into a file,
replacing the previous content of the file. (5) int getUid() gets the
real user ID of the current process. (6) int getEuid() gets the effective
user ID of the current process. (7) void setEuid(int uid) sets the
effective user ID of the current process, where uid is either the real
user ID or the saved effective user ID of the process.

170
 Operating Systems Security

Error conditions that occur in the execution of the above system

calls (e.g., trying to open a file without having access right to it or
using a nonexistent descriptor) trigger exception SystemCallFailed,
which should be handled by your program. Note that you do not
need to worry about buffer overflow in this question.
P-2 Implement a system that implements a simple access control list
(ACL) functionality, which gives a user the ability to grant file
permissions on a user-by-user basis. For example, one can create
a file that is readable by joeuser and janeuser, but only writable
by janeuser. The operations on the ACL are as follows. (1) set-
facl(path, uid, uid mode, gid, gid mode) sets a user with uid and/or
a group with gid to the ACL for the object (file or directory) spec-
ified by path. If the user/group already exists, the access mode is
updated. If only (uid, uid mode) or (gid, gid mode) is to be set, null
is used for the unset arguments. (2) getfacl(path) obtains the entire
access control list of the file path. (3) access(uid, access mode,
path) determines whether a user with uid can access the object
stored at path in mode access mode. This method returns a
boolean. path contains the full path to a file or a directory, e.g.,
/u/bob/cs166/homework.doc. You can use groups username to find
out the groups that username belongs to. One way to accomplish
this ACL would be with a linked list; your solution should be
more efficient with respect to the number of users, groups, and
files. Describe how to implement the operations with your data
structure. You have to consider permissions associated with the
parent directories of a file. For this, you are given a method getPar-
ent(full path) that takes a path to a file or directory, and returns the
parent directory.
P-3 In a virtual machine, install the Linux operating system, which
supports the capability-based access control (capabilities are built
into the Linux kernel since the kernel version 2.6.24). Use capabil-
ities to reduce the amount of privileges carried by certain SetUID
programs, such as passwd and ping.
P-4 In a virtual machine, install a given privileged program (e.g., a
SetUID program) that is vulnerable to the buffer overflow attack.
Write a program to exploit the vulnerability and gain the ad-
minstrator privilege. Try different attacking schemes, one using
shellcode, and the other using the return-to-libc technique. It
should be noted that many operating systems have multiple built-
in countermeasures to protect them against the buffer overflow
attack. First, turn off those protections and try the attack; then turn

171
 Operating Systems Security

them back on and see whether these protections can be defeated

(some countermeasures can be easily defeated).
P-5 In a virtual machine, install a given privileged program (e.g., a
SetUID program) that is vulnerable to the format-string attack.
Write a program to exploit the vulnerability and that will crash
the privileged program, print out the value of an internal variable
secret to the user, and modify the value of this secret variable.
Modify the source code of the vulnerable program so it can defeat
the format string attack.
P-6 In a virtual machine, install a given privileged program (e.g., a
SetUID program) that is vulnerable to the race condition attack.
Write a program to exploit the vulnerability and gain adminstrator
privilege. Modify the source code of the vulnerable program so it
can defeat the race condition attack.
P-7 Write a term paper describing how buffer overflows are used as
vectors for many computer attacks. Discuss how they enable
different kinds of attacks and describe how different software en-
gineering practices and languages might encourage or discourage
buffer-overflow vulnerabilities.

Chapter Notes
Operating systems are discussed in detail in the textbooks by Doeppner [27] and
Silberschatz, Galvin and Gagne [94]. Much of the content in this chapter on Unix-
based systems, especially Linux, draws heavily on open source documentation,
which can be accessed at http://www.manpagez.com/. Grünbacher describes in
detail Linux ACLs and the file access control algorithm based on ACLs [37].
Reference material on the Windows API can be found in the Microsoft Developer
Network [60]. A classic introduction to stack-based buffer overflows is given
by Aleph One [1]. Lhee and Chapin discuss buffer overflow and format string
exploitation [54]. A method for protecting against heap smashing attacks is
presented by Fetzer and Xiao [33]. The canary method for defending against
stack smashing attacks is incorporated in the StackGuard compiler extension by
Cowan et al. [20]. Address space randomization and its effectiveness in preventing
common buffer overflow attacks is discussed by Shacham et al. [89]. Project P-1
is from Tom Doeppner.

172
 Malware

Contents

1 Insider Attacks
1.1 Backdoors
1.2 Logic Bombs
1.3 Defenses Against Insider Attacks
2 Computer Viruses
2.1 Virus Classification
2.2 Defenses Against Viruses
2.3 Encrypted Viruses
2.4 Polymorphic and Metamorphic Viruses
3 Malware Attacks
3.1 Trojan Horses
3.2 Computer Worms
3.3 Rootkits
3.4 Zero-Day Attacks
3.5 Botnets
4 Privacy-Invasive Software
4.1 Adware
4.2 Spyware
5 Countermeasures
5.1 Best Practices
5.2 The Impossibility of Detecting All Malware
5.3 The Malware Detection Arms Race
5.4 Economics of Malware
6 Exercises

From Chapter 4 of Introduction to Computer Science, First Edition, Michael T. Goodrich,

Roberto Tamassia. Copyright 2011 by Pearson Education, Inc. Published by
Pearson Addison-Wesley. All rights reserved.

173
 Malware

1 Insider Attacks
This chapter is devoted to the ways that software systems can be attacked
by malicious software, which is also known as malware. Malicious soft-
ware is software whose existence or execution has negative and unintended
consequences. We discuss various kinds of malware, including some case
studies, and how systems and networks can be protected from malware.
We begin our coverage of malware with insider attacks. An insider
attack is a security breach that is caused or facilitated by someone who is
a part of the very organization that controls or builds the asset that should
be protected. In the case of malware, an insider attack refers to a security
hole that is created in a software system by one of its programmers. Such
an attack is especially dangerous because it is initiated by someone that
we should be able to trust. Unfortunately, such betrayals of trust are not
uncommon.
Insider attack code can come embedded in a program that is part of
a computer’s operating system or in a program that is installed later by
a user or system administrator. Either way, the embedded malware can
initiate privilege escalation, can cause damage as a result of some event, or
can itself be a means to install other malware.

1.1 Backdoors
A backdoor, which is also sometimes called a trapdoor, is a hidden feature
or command in a program that allows a user to perform actions he or
she would not normally be allowed to do. When used in a normal way,
this program performs completely as expected and advertised. But if the
hidden feature is activated, the program does something unexpected, often
in violation of security policies, such as performing a privilege escalation.
In addition, note that since a backdoor is a feature or command embedded
in a program, backdoors are always created by one of the developers or
administrators of the software. That is, they are a type of insider attack.
(See Figure 1.)

Backdoors Inserted for Debugging Purposes

Some backdoors are put into programs for debugging purposes. For exam-
ple, if a programmer is working on an elaborate biometric authentication
system for a computer login program, she may wish to also provide a
special command or password that can bypass the biometric system in the

174
 Malware

Public high-level of security Secret entry point

Figure 1: Metaphorical illustration of a software backdoor.

(“Public high-level of security”) © Kirsty Pargeter/Shutterstock;
(“Secret entry point”) © Natalia Bratslavsky/Fotolia, LLC–Royalty
Free

event of a failure. Such a backdoor serves a useful purpose during code

development and debugging, since it helps prevent situations where a sys-
tem under development could become unusable because of a programming
error. For instance, if a programmer were unable to log in to a system due
to a bug in its authentication mechanism, that system might become com-
pletely unusable. In these cases, a backdoor might be created that grants
access when provided with a special command, such as letmeinBFIKU56,
to prevent being locked out of the system when debugging. However, if
such a backdoor remains in the program after finishing development, it can
become a security risk that may allow an attacker to bypass authentication
measures.

A backdoor left in a program even after it is fully debugged might

not be intended to serve a malicious purpose, however. For instance, a
biometric authentication system might contain a backdoor even after it is
debugged, so as to provide a bypass mechanism in the case of an emergency
or unanticipated problem. If a user is injured in a way that makes his
biometric data invalid, for example if a cut on his hand significantly alters
his fingerprint, then it would be useful if he could call the manufacturer
of the biometric system to receive a one-time password in order to gain
access to his system. Such a one-time password override could technically
be considered as a backdoor, but it nevertheless serves a useful purpose.
Of course, if a programmer never tells anyone at her company about such
an override mechanism or if she inserts it as a way of gaining access to the
system after it is deployed, then this backdoor has probably been left in for
a malicious purpose.

175
 Malware

Deliberate Backdoors

Sometimes programmers deliberately insert backdoors so they can perform

malicious actions later that would not otherwise be allowed by the normal
usage of their programs. For example, imagine what could happen if a
programmer who is designing a digital entry system for a bank vault adds
a backdoor that allows access to the vault through the use of a special
sequence of keystrokes, known only to him. Such backdoors are clearly
inserted for malicious purposes, and they have the potential for dramatic
effects. For instance, the classic movie War Games features a backdoor at a
dramatic high point. The backdoor in this case was a secret password that
allowed access to a war-game simulation mode of a computer at the North
American Aerospace Defense Command (NORAD).
Another more subtle way of creating a backdoor involves deliberately
introducing a vulnerability into a program, such as a buffer overflow. Be-
cause the programmer knows about the vulnerability, it may be straightfor-
ward for him to exploit it and gain elevated privileges. In addition, this
situation allows the programmer to simply feign ignorance on being accused
of deliberately creating a backdoor—after all, software vulnerabilities are
extremely common. Such attacks are sometimes employed against open
source projects that allow volunteers to contribute code. An attacker may
deliberately introduce an exploitable bug into the code of an open source
project, allowing him to gain access to systems on other machines.

Easter Eggs

Software may include hidden features that can be accessed similarly to

backdoors, known as Easter eggs. An Easter egg is a harmless undocu-
mented feature that is unlocked with a secret password or unusual set of
inputs. For example, unlocking an Easter egg in a program could cause
the display of a joke, a picture of the programmer, or a list of credits for
the people who worked on that program. Specific examples of programs
containing Easter eggs include early versions of the Unix operating system,
which displayed funny responses to the command “make love,” and the
Solitaire game in Windows XP, which allows the user to win simply by
simultaneously pressing Shift, Alt, and 2. In addition, movie DVDs some-
times contain Easter eggs that display deleted scenes, outtakes, or other
extra content, by pushing unusual keystrokes at certain places on menu
screens.

176
 Malware

1.2 Logic Bombs

A logic bomb is a program that performs a malicious action as a result of a
certain logic condition. (See Figure 2.) The classic example of a logic bomb
is a programmer coding up the software for the payroll system who puts in
code that makes the program crash should it ever process two consecutive
payrolls without paying him. Another classic example combines a logic
bomb with a backdoor, where a programmer puts in a logic bomb that will
crash the program on a certain date. The logic bomb in this case can be
disabled via a backdoor, but the programmer will only do so if he is paid
for writing the program. This type of logic bomb is therefore a form of
extortion.

if (trigger-condition
(trigger condition = true) {
unleash bomb;
}

Figure 2: A logic bomb.

The Y2K Problem

Note that for a piece of software to be a logic bomb, there has to be a
malicious intent on the part of the programmer. Simple programming
errors don’t count. For example, programmers in the 20th century encoded

177
 Malware

dates as two digits, xy, to imply 19xy. When the year 2000 came, this prac-
tice caused several problems. Although Y2K didn’t have the catastrophic
effects that some were expecting, it did cause some problems with some
credit-card transactions and other date-dependent calculations. In spite of
these negative results, there was, as far as we know, no malice on the part
of programmers encoding dates in this way. Instead, these programmers
were trying to save some memory space with what they saw as the useless
storage of two redundant digits. Because of a lack of malicious intent,
the Y2K problem should not be considered a logic bomb although it had
a similar effect.

Examples of Logic Bombs

An example of a logic bomb comes in the classic movie Jurassic Park, where
the programmer, Nedry, installs a piece of code in the software for the
park’s security system that systematically turns off the locks on certain
fences, gates, and doors to allow him to steal some dinosaur embryos.
A real-life logic bomb was reported to have been inserted in 2008 into
the network software for Fannie Mae, a large financial enterprise sponsored
by the United States government, by a software contractor, Rajendrasinh
Makwana. He is said to have set a logic bomb to erase all of Fannie Mae’s
4,000 server computers 3 months after he had been terminated. Fortunately,
the code for this logic bomb was discovered prior to its activation date,
which avoided a digital disaster that would have had major implications in
the financial world.

The Omega Engineering Logic Bomb

An example of a logic bomb that was actually triggered and caused damage
is one that programmer Tim Lloyd was convicted of using on his former
employer, Omega Engineering Corporation. On July 31, 1996, a logic bomb
was triggered on the server for Omega Engineering’s manufacturing oper-
ations, which ultimately cost the company millions of dollars in damages
and led to it laying off many of its employees.
When authorities investigated, they discovered that the files on the
server were destroyed and that Tim Lloyd had been the administrator for
that server. In addition, when they searched for backup tapes for the server,
they only found two—at Tim Lloyd’s house—and they were both erased.

178
 Malware

The Logic Behind the Omega Engineering Time Bomb

In performing a forensic investigation of a true copy of the server’s memory,
agents for the U.S. Secret Service found a program containing the following
sequence of six character strings:
7/30/96
◦ This was the event that triggered the logic bomb—a date that
caused the remaining code to be executed only if the current date
was later than July 30, 1996.

F:
◦ This focused subsequent commands to be run on the volume F,
which contained the server’s critical files.

F:\LOGIN\LOGIN 12345
◦ This is a login for a fictitious user, 12345, that had supervisory
and destroy permissions, but (surprisingly) had no password.
So all subsequent commands would run using the supervisory
permissions of user 12345.

CD \PUBLIC
◦ This is a DOS command to change the current directory to the
folder PUBLIC, which stored common programs and other pub-
lic files on Omega Engineering’s server.

FIX.EXE /Y F:\*.*
◦ FIX.EXE was an exact copy of the DOS program DELTREE,
which can delete an entire folder (and recursively its subfolders),
except that FIX.EXE prints on the screen the words “fixing ...”
instead of “deleting ...” for each file that is deleted. The /Y
option confirms that each file should indeed be deleted, and the
argument F:\*.* identifies all the files on volume F as the ones to
be deleted.

PURGE F:\/ALL
◦ Deleted files can often be easily recovered by a simple analysis of
the disk. This command eliminates the information that would
make such reconstruction easy, thereby making recovery of the
deleted files difficult.
Thus, this program was a time bomb, which was designed to delete all the
important files on Omega Engineering’s server after July 30, 1996. Based in
part on this evidence, Tim Lloyd was found guilty of computer sabotage.

179
 Malware

1.3 Defenses Against Insider Attacks

Protecting a system against backdoors and logic bombs is not easy, since
each of these types of malware is created by a trusted programmer (who
clearly is not trustworthy). But defense against these types of malware is
not impossible. Possible defenses include the following:

• Avoid single points of failure. Let no one person be the only one to
create backups or manage critical systems.
• Use code walk-throughs. Have each programmer present her source
code to another programmer, line by line, so that he can help her
identify any missing conditions or undetected logic errors. Assuming
that there is no “ sleight of hand,” where she would present one set of
source code during the code walk-through and install a different set
later, she should be unable to discuss the code that defines a backdoor
or logic bomb without her partner noticing.
• Use archiving and reporting tools. Several other software engineer-
ing tools, such as automatic documentation generators and software
archiving tools, have a benefit of uncovering or documenting in-
sider attacks, in addition to their primary goals of producing quality
software. Software engineering tools often create visual artifacts or
archival digests, which are often reviewed by managers, not just the
programmers, so using these tools makes it harder for an insider
who is a malware author to have her malicious code go undetected.
Likewise, when program code is archived, it becomes harder for a
team member to avoid the existence of malware source code to go
undiscovered after an attack.
• Limit authority and permissions. Use a least privilege principle,
which states that each program or user in a system should be given
the least privilege required for them to do their job effectively.
• Physically secure critical systems. Important systems should be kept
in locked rooms, with redundant HVAC and power systems, and
protected against flood and fire.
• Monitor employee behavior. Be especially on the lookout for system
administrators and programmers that have become disgruntled.
• Control software installations. Limit new software installations to
programs that have been vetted and come from reliable sources.

180
 Malware

2 Computer Viruses

A computer virus, or simply virus, is computer code that can replicate itself
by modifying other files or programs to insert code that is capable of further
replication. This self-replication property is what distinguishes computer
viruses from other kinds of malware, such as logic bombs. Another distin-
guishing property of a virus is that replication requires some type of user
assistance, such as clicking on an email attachment or sharing a USB drive.
Often, a computer virus will perform some malicious task as well, such as
deleting important files or stealing passwords.
Computer viruses share a number of properties with biological viruses.
When released, biological viruses use their environment to spread to unin-
fected cells. A virus can often lie dormant for a period of time, waiting until
it encounters the right kind of uninfected cell. When a virus encounters
such a cell, it attacks that cell’s defenses at the margins. If it is able to
penetrate the cell, the virus uses the cell’s own reproductive processes to
make copies of the virus instead, which eventually are released from the cell
in great numbers, so as to repeat the process. (See Figure 3.) In this way,
computer viruses mimic biological viruses, and we even use the biological
term vectors to refer to vulnerabilities that malware, such as computer
viruses, exploit to perform their attacks.

Attack Penetration

Replication and assembly

Release

Figure 3: Four stages of a biological virus.

181
 Malware

2.1 Virus Classification

Computer viruses follow four phases of execution:
1. Dormant phase. During this phase, the virus just exists—the virus is
laying low and avoiding detection.

2. Propagation phase. During this phase, the virus is replicating itself,

infecting new files on new systems.

3. Triggering phase. In this phase, some logical condition causes the

virus to move from a dormant or propagation phase to perform its
intended action.

4. Action phase. In this phase, the virus performs the malicious action
that it was designed to perform, called payload. This action could in-
clude something seemingly innocent, like displaying a silly picture on
a computer’s screen, or something quite malicious, such as deleting
all essential files on the hard drive.
These phases characterize many different types of computer viruses.
One way to classify the many varieties of viruses is according to the way
they spread or the types of files that they infect.

Types of Viruses
A program virus, also known as a file virus, infects a program by modifying
the file containing its object code. Once the infection occurs, a program
virus is sure to be run each time the infected program executes. If the
infected program is run often, as with a common operating system pro-
gram or a popular video game, then the virus is more likely to be able
to be maintained and to replicate. Thus, the most common and popular
programs are also the most natural targets for program viruses. Figure 4
gives schematic examples of infected program files, which contain both the
original program code and the virus code.
Several document preparation programs, such as Microsoft Word, sup-
port powerful macro systems that allow for automating sequences of com-
mands. When used benevolently, macros provide, e.g., dynamic updating
of facts, figures, names, and dates in documents when the underlying
information changes. But macro systems often incorporate a rich set of
operations, such as file manipulation and launching other applications.
Since a macro can behave similarly to an executable program, it can become
a target for viruses.

182
 Malware

Header
Jump
Virus
Code Header Virus
Code Original
Virus Program
Code Part 1

Header Header
Jump
Virus Code
Part 1
Original Jump
Original Program Original
Program Program
Original
Program
Part 2

Halt
Virus Code
Part 2
Jump
(a) (b)

Figure 4: How a virus injects itself into a program file: (a) A simple
injection at the beginning of a program. (b) A more complex injection that
splits the virus code into two parts and injects them at different points in
the program. Jump instructions are used to begin execution with the virus
code and then pass control to the original program code.

A macro virus, which is also known as a document virus, is launched

when a document is opened, at which time the virus then searches for other
documents to infect. In addition, a macro virus can insert itself into the
standard document template, which makes every newly created document
infected. Finally, further propagation occurs when infected documents are
emailed to other users.

A boot sector virus is a special type of program virus that infects the
code in the boot sector of a drive, which is run each time the computer is
turned on or restarted. This type of virus can be difficult to remove, since
the boot program is the first program that a computer runs. Thus, if the
boot sector is infected with a virus, then that virus can make sure it has
copies of itself carefully placed in other operating system files. As a result,
antivirus software routinely monitors the integrity of the boot sector.

183
 Malware

Real-World Examples of Computer Viruses

Some real-world examples of computer viruses include the following:

• Jerusalem. This is a virus that originated in the 1980s and infected

DOS operating systems files. It was first discovered in Jerusalem,
Israel. Once it becomes active on a computer, the Jerusalem virus
loads itself into the main memory of the computer and infects other
executable files that are run. In addition, it avoids reinfecting the files
it has already injected itself into. Its destructive action is that if it is
ever executed on a Friday the 13th, then it deletes every program file
that is run. The Jerusalem virus has spawned a number of variants,
such as Westwood, PQSR, Sunday, Anarkia, and Friday-15th, which
cause havoc on other dates and have other slight differences from the
original Jerusalem virus.

• Melissa. This was the first recorded virus that spread itself via mass
emailing. It is a macro virus that infects Microsoft Word 97 or 2000
documents and Excel 97 or 98 documents. Once an infected document
is opened, the Melissa virus would email infected documents to the
first 40 or 50 addresses in the victim’s address book. It would also
infect other Word and Excel documents. When initially launched, the
Melissa virus spread so fast that a number of email servers had to be
temporarily shut down because they were overloaded with so many
emails. It has a number of variants, such as Papa, Syndicate, and
Marauder, which differ in the messages and filenames included in the
contents of the emails that are sent. In each case, the goal is to entice
the recipient to open an enclosed document and further the spread of
the virus.

• Elk Cloner. This is a boot sector virus that infected Apple II operating
systems in the early 1980s It infected systems by writing itself to
the hard drive any time an infected disk was inserted. It was fairly
harmless, however, in that its payload simply printed out a poem each
50th time the computer was booted.

• Sality. This is a recent executable file virus. Once executed, it disables

antivirus programs and infects other executable files. It obscures its
presence in an executable file by modifying its entry point. It also
checks if it is running on a computer with an Internet connection,
and if so, it may connect to malware web sites and download other
malware.

184
 Malware

2.2 Defenses Against Viruses

Since computer viruses share many similarities with biological viruses, it is
appropriate that we defend against them by gaining insight from how our
bodies react to harmful intruders. When a virus enters a person’s body and
gets past her initial defenses, it may spread rapidly and infect many of her
cells. As the virus spreads, however, that person’s immune system learns
to detect unique features of the attacking virus, and it mounts a response
that is specifically tuned to attack infected cells.

Virus Signatures
A computer virus unleashed into the wild may get past the generic defenses
of several systems and spread rapidly. This spread inevitably attracts the
attention of systems managers, who in turn provide sample infected files to
antivirus software companies. Experts then study the infected files looking
for code fragments that are unique to this particular computer virus. Once
they have located such a set of characteristic instructions, they can construct
a character string that uniquely identifies this virus.
This character string is known as a signature for the virus; it amounts to
a kind of digital fingerprint. Then, much like our immune system attacking
a viral infection, a virus detection program is then loaded up with the
signatures of all known viruses. Virus detection software packages have
to be frequently updated, so that they always are using the most up-to-date
database of virus signatures. Detecting the presence of a virus signature
in a file is an instance of a pattern-matching problem, which consists of
finding a search pattern in a text. Several efficient pattern matching algo-
rithms have been devised, which are able to search for multiple patterns
concurrently in a single scan of the file.

Virus Detection and Quarantine

Checking files for viruses can be done either by periodic scans of the entire
file system or, more effectively, in real time by examining each newly cre-
ated or modified file and each email attachment received. Real-time virus
checking relies on intercepting system calls associated with file operations
so that a file is scanned before it is written to disk. Any file that contains a
part that matches a virus signature will be set aside into protected storage,
known as a quarantine. The programs put into quarantine can then be
examined more closely to determine what should be done next. For ex-
ample, a quarantined program might be deleted, replaced with its original
(uninfected) version, or, in some cases, it might be directly modified to
remove the virus code fragments (in a process not unlike surgery).

185
 Malware

2.3 Encrypted Viruses

Because antivirus software systems target virus signatures, computer virus

writers often try to hide their code. As illustrated in Figure 4, a virus may
subdivide itself into multiple pieces and inject them into different locations
in a program file. This approach can have some success, because it spreads
a virus’s signature all over the file, but reassembling the pieces of a virus
will immediately reveal its code (and, hence, its signature). One additional
technique used by virus writers to make the presence of their virus in a file
more stealthy is to encrypt the main body of their program. (See Figure 5.)

Decryption Decryption
Code Code
Key Key

Encrypted
Virus Code Encrypt
Virus Code

Figure 5: How an encrypted virus is structured.

By encrypting the main part of its code, a virus hides many of its distin-
guishing features, including its replication code and, more importantly, its
payload, such as searching for and deleting important files. As illustrated
in Figure 5, this modification results in the virus code taking on a different
structure: the decryption code, the key, and the encrypted virus code.
Alternatively, a short encryption key is used (e.g., a 16-bit key) and the
decryption code is replaced by code for a brute-force decryption attack. The
goal of encryption is to make it harder for an antivirus program to identify
the virus. However, note that code for decrypting the main virus body
must itself remain unencrypted. Interestingly, this requirement implies that
an encrypted virus has a telltale structure, which itself is a kind of virus
signature.
Even though this structure doesn’t tell a security expert exactly what
computations the virus performs, it does suggest to look for pieces of code
that perform decryption as a way of locating potential computer viruses. In
this way, the virus arms race continues, with the attack of signature-based
detection being counterattacked with encrypted viruses, which in turn are
themselves counterattacked with virus detection software that looks for
encryption code.

186
 Malware

2.4 Polymorphic and Metamorphic Viruses

Another technique used by viruses to fight back against signature-based
detection is mutating as they replicate, thereby creating many different
varieties of the same virus. Such viruses are known as polymorphic or
metamorphic viruses. Although these terms are sometimes used inter-
changeably, a polymorphic virus achieves its ability of taking on many
forms by using encryption, with each copy of the virus being encrypted
using a different key. A metamorphic virus, on the other hand, uses
noncryptographic obfuscation techniques, such as instruction reordering
and the inclusion of useless instructions. Polymorphic and metamorphic
viruses are difficult to detect, unfortunately, since they often have few fixed
characteristic patterns of bits in their code that can be used to identify them.

Detecting Polymorphic Viruses

One way to detect a polymorphic virus is to focus on the fact that it must
use a different encryption key each time the virus encrypts and replicates
itself. This choice implies that the body of the computer virus must also
include generic code for an encryption algorithm—so that it can encrypt
copies of itself with new keys. A polymorphic virus might still have a
signature related to its ability to encrypt itself. The encryption code may
itself initially be encrypted, so a virus detection algorithm would, in this
case, have to identify this decryption code first.

Detecting Metamorphic Viruses

Finding a single string that serves as the signature for a metamorphic virus
may be impossible. Instead, we can use more complex signature schemes.
A conjunction signature consists of a set of strings that must appear, in
any order, in the infected file. A sequence signature consists of an ordered
list of strings that must appear in the given order in the infected file. A
probabilistic signature consists of a threshold value and a set of string-score
pairs. A file is considered infected if the sum of the scores of the strings
present in the file exceeds the threshold.
Metamorphic viruses also have an alternative detection strategy. If they
have large amounts of pointless code, techniques similar to superfluous
code detection methods used in optimizing compilers may be employed. In
addition, a metamorphic virus must include code that can perform useless
code injection, reorderings of independent instructions, and replacements
of instructions with alternative equivalent instructions, all of which might
be detected via virus signatures.

187
 Malware

3 Malware Attacks
When malware was first discovered as a r