The next morning I slept late. After fixing myself a breakfast around noon, I settled in for a long bout with the X9.17 protocol. This is the ANSI standard I had gotten at the Chicago Public Library on the day of my arrest. I was hoping that I might be able to find a weakness in the protocol that would explain the money mill. Little had suggested that the mill was probably an attack on the protocol used to exchange encrypted messages rather than an attack on DES directly. This was a plausible explanation.
This left me with the question of how the millwright was getting the MAC keys. Was he a trusted insider? Or was he an outsider that had discovered a way to circumvent the security measures designed in the key-exchange protocol used by all banks worldwide? I was determined to find out.
I fixed myself a peanut butter and jelly sandwich, grabbed a can of iced-tea, and sat down at the kitchen table. I opened my copy of the X9.17 standard. On the blue and white cover, in the upper right corner, it was dated 1985 but it also indicated that the standard was reaffirmed without any modifications in 1991. The title of the standard is Financial Institution Key Management (Wholesale). I cracked the cover, sat back with my can of iced-tea (I've always found it more convenient to buy it by the can than to make my own) and, with great determination, set out to learn the protocol. As it turns out, determination was an important requirement; without it I would have tired quickly from all of the acronyms. As it was, they slowed me down but did not deter me.
X9.17 is intended for the exchange of cryptographic keys used in applications for wholesale financial institutions. In other words, for electronic funds transfer. This is the standard used for automatic deposits, automatic payments, wire transfers, and even the automated clearing of paper checks. To maintain the secrecy of keys, all exchanged keys are encrypted using key-encrypting keys. This encryption is done using DES. To provide integrity for exchanged keys, the protocol again uses DES, this time to compute message authentication codes (MAC's).
X9.17 supports the exchange of two types of session keys: keys used to encrypt data for privacy; and keys used to compute MAC's for integrity. The standard refers to both types as data-encrypting keys. The cryptographic keys used to encrypt data-encrypting keys during a key exchange are referred to as key-encrypting keys. So key-encrypting keys are only used to encrypt and authenticate other keys, which in turn are used for EFT's and other inter-bank traffic. X9.17 only specifies key exchange, not key use (i.e. not EFT), but since all evidence indicated that the millwright had knowledge of keys, I wanted to study the X9.17 document to determine if there might be some way for an outsider to eavesdrop on MAC keys.
The standard includes two different architectures. The simpler architecture, called the two-layer version, uses manually distributed key-encrypting keys to exchange data-encrypting keys. The second architecture is a three-layer architecture that supports an additional layer of key-encrypting keys. The manually distributed key-encrypting keys are used to encrypt a layer of automatically distributed key-encrypting keys which are used in turn to encrypt data-encrypting keys. I noted that both architectures require that there be a secure mechanism external to the protocol for exchanging top-level key-encrypting keys.
The standard allows for three different ``environments'' (not to be confused with architectures). Because X9.17 has these three environments, it is really three separate protocols in one standard. The first, the point-to-point environment, is a protocol whereby two parties can agree upon a session key that is generated by one of the parties and is encrypted by that same party. The second environment, the key distribution center environment, is meant to be used when neither of the parties wishing to establish a session key is able to generate a good key or encrypt a key for use by the other party (i.e. the two parties share no prior secrets). In this environment, one of the two parties requests a key from a trusted distribution center and receives two ciphertexts, one of which can be decrypted by that party and the other of which is relayed on to the other party for decryption. The third environment, the key translation environment, makes it possible for one of the two communicating parties to generate the key. The trusted translation center is used to encrypt the key for transmission to the other party. This environment is appropriate when one of the pair is able to generate good keys but the pair does not share a prior secret.
OK, so far so good. I stood up and walked over to the refrigerator. Rummaging through the contents turned up very little in the way of snack foods and I didn't want to prepare anything elaborate, so I settled for a second can of iced-tea.
I found the various message formats for each of the three environments on pages 47 through 50 of the document. Many of the fields are optional. Indeed, many of the messages are optional. I decided that the best way to tackle this was to filter out all of the optional features and concentrate first on the core of the standard. I got up from the table and went over to the telephone stand for a couple of clean pieces of paper. Sitting back down, I opened the iced-tea and took a long sip. Doing so, I noticed that the clock on the wall above the dishwasher read 3:05. Hmmmm, this might be a long afternoon. I used the first sheet of paper to jot down all the acronyms so that I would be able to refer to them easily. The standard already had a table of all the acronyms, listed on pages 4 through 7, but I wanted a list that only included those acronyms I expected to use. I left out all the acronyms for optional features, for example. The first part of my list consisted of the acronyms for the five message types that comprised the core of the protocol. The remainder of the list consisted of acronyms for required field types.
The standard actually contains many more acronyms than my small list. Being a computer scientist I am used to dealing with acronyms, even like it. But enough is a enough! Being inundated with dozens of new three-letter acronyms all at once, while trying to come to grips with the protocol in sufficient detail that I might be able to unravel the mysterious traffic patterns we'd been seeing lately, was a bit much.
I needed some notation for my notes.
I chose A and B to represent arbitrary banks.
Sd denoted a trusted key distribution server and
St denoted a trusted key translation server.
What is the difference between the KD field and the KDU field, I
wondered. Both hold a session key, encrypted with a key-encrypting
key. Flipping back to the definitions section I learned that
the computation for the KDU field includes a notarization step.
OK, so how do they stipulate that notarization of keys be done?
After another iced-tea, two trips to the restroom, and two or three
separate moments staring out the window, I had successfully waded
through the explanation of notarization contained on pages 28 through 30.
It isn't a lengthy explanation, but I had to be careful to understand
it fully and not read anything more into it than was there.
I concluded that notarization is a method for sealing a key with
the identities of the intended users of that key.
A key is notarized by first blinding the key-encrypting key with a notary
seal before using it to encrypt (notarize) the data-encrypting key.
The notary seal is a function of the key-encrypting key and the two
identities, and is designed such that it is difficult to compute a notary
seal without prior knowledge of the key-encrypting key (i.e. it is a
one-way function).
As I was writing down the basic protocol for the Key Translation
Center environment, I was struck by how useful a key translation
service might be to an outside attacker.
The ``translation'' process involves accepting a key that has been
encrypted by one key-encrypting key and returning the same key
encrypted with the key-encrypting key of the requestor's choice.
How convenient! This is exactly the sort of thing that encrypting
the key is supposed to protect against! If anybody can ask to have
a key encrypted using any other key, then what protection does it afford?
In affect, any member of the network can ask the key translation center
to encrypt any key-sized collection of bits using the secret key known
only to the translation center and some other member.
The Key Translation Center is an encrypting service, using other people's
keys!
Well, no. The X9.17 designers apparently anticipated attacks on the
Key Translation Center because the standard requires that the requester
send a MAC with the Request For Service (RFS). An outsider cannot
forge a legitimate RFS. And an eavesdropper of a legitimate RFS and
Response To Request (RTR) pair learns nothing
because the keys in the KD and KDU fields are encrypted.
This was getting way too confusing. I walked across the room and got
a ruler and took out a fresh piece of paper. A glance at the clock
told me it was well past time for dinner. My stomach confirmed this.
Reluctant to stop now that I was fully focused, I pushed on.
I then wrote down the
minimal protocol, leaving out all the optional parts.
I used an arrow from X to Y to indicate that X sends a message
to Y in that step of the protocol.
In the Key Translation Center Environment, the protocol consists
of four core messages.
The first, the Request for Service (RFS) is from A to the center.
This was the first column of my table.
Then the center sends a reply (RTR) back to A. Then there is
a message from A to B, and finally a message from B back to A.
Laid out in this way, the protocol began to make more sense.
The first thing I noticed is that all of the messages contain the
identifiers for the intended sender and recipient, as well as a MAC.
In each message the MAC was written as the last field. The first
three fields were always the same: the MCL holds the message class;
the RCV holds the identifier of the intended recipient; and the
ORG holds the identifier of the purported sender.
The fact that each message contained an explicit identifier for
the recipient, as well as a MAC,
would make it hard, if not impossible, to re-route messages.
Because the messages contain MAC's, they cannot be altered (unless
the attacker knows the MAC key).
I wondered what would happen if an attacker tried to fool B into using
the wrong data-encrypting key in the Key Translation Center Environment.
The attacker might try intercepting the KSM message sent by A and
intended for B. However, there is little that the attacker can do
with the intercepted message. The key contained in the KDU field is
encrypted and therefore inaccessible. The attacker might try to
substitute a different key by replacing KDU with bits of his own
choosing, but he will be foiled by the MAC that must be appended to
the KSM message. Without knowing the key-encrypting key, there is no
way for the attacker to recalculate the MAC for the new KDU field
such that it will pass the verification check performed by B.
This is the essential function of MAC's --- to make it infeasible
to alter intercepted messages or to produce fake messages.
Next I turned to the Key Distribution Center Environment.
According to the standard,
at a minimum the protocol for a key distribution
center environment consists of three basic messages.
the first important message is the RTR message. Flipping back to
page 7, I discovered that RTR stands for Response to Request, and the
actual request (called and RSI or Request Service Initiation)
is one of the optional messages I was ignoring for the time being.
The table on page 47 indicates that RTR messages in this environment
have nine fields.
The first of these nine fields is the Message Class (MCL), which
indicates the type of message. In this case the MCL field indicates
that the message is a Response to Request (RTR).
The next field, RCV, specifies the intended recipient. It is an
identifier. This is followed by the identifier for the sender, or
originator, of the message. The IDU field holds the identifier for
the ultimate recipient of the (second) encrypted key. The entity that
receives the RTR message is expected to relay a copy of the encrypted
key on to the entity named in the IDU field.
The next two fields hold encrypted copies of a key to be used in an
EFT session. The KD field holds a encrypted copy for the recipient of
the RTR message (i.e. entity A), while the KDU field holds an encrypted
copy for the other entity (i.e. B). Thus, KD and KDU will be encrypted
using different keys since they are intended for decryption by separate
entities.
The ciphertext fields are followed by two counters in plaintext. These
counters are used to recognize replays of old messages.
The first counter is a tally of the number of keys sent to entity B while
the second counter is a tally of the number of keys sent to A.
Finally, appended to the RTR message is a MAC. The MAC is computed over
the entire message (i.e. eight fields, beginning with MCL and ending
with CTA).
The content of the fields in the remaining message types is similar to
that of the RTR. The next message, the Response to Service Message (RSM)
is an acknowledgment sent by A back to the key distribution center.
At this point A has a copy of the key (after decrypting the contents of
the KD field in the RTR).
Next A sends a Key Service Message (KSM) to B. The KSM message contains
the KDU field, which A cannot decrypt but B can. The KSM is the heart
of the protocol in each of the three environments; it is the message that
sends the encrypted key to the ultimate recipient.
Each of the protocols ends with a Response to Service Message (RSM) which
is an acknowledgment of the KSM.
Ahh, but wait a minute! The key translation center environment
allows a participant to generate a session key and submit it to the
trusted third party for packaging. In other words, the party that
generates the session key and sends it to the ultimate recipient
does not need to share any prior secrets with the ultimate recipient.
Might there be some way for one party to impersonate another party
and request a key translation?
Some sort of inside attack?
The party sending the RFS to the Key Translation Center still needs
a legitimate key because, as I had noticed earlier, the RFS includes
a MAC, which cannot be computed without the key. OK fine. Some other
bank, separate from A and B partaking in the key exchange, would
have a legitimate key. So that requirement can be met.
I hurriedly took notes on this train of thought, afraid that I might
forget it. Damn --- broke the pencil lead again. I renewed the
pencil point and pressed on.
So as not to add a new level of confusion and make it difficult to
relate my notes to the X9.17 standard, I continued to use the
notation of the standard, although I did yield to the temptation
to deviate slightly.
OK, let's see...
The ciphertexts for encrypted session keys are not always notarized.
Due to this lack of explicit type information in the ciphertext portion
of some messages, it is possible for an attacker to use the ciphertext in
a manner different from the intended use.
Namely, the attacker can use un-notarized ciphertext to impersonate a
party making a seemingly legitimate request for key translation.
There is no MAC in the RSI message format used to request service from a
key distribution center.
Presumably the ciphertext in the response from the server is meant to guard
against misuse.
Hmmm.
I wonder if the lack of explicit information in keys might make them
susceptible to replay attacks.
The attacker would need to be able to predict the values of counters expected
by recipients of forged messages (e.g. CTA and CTB), but this is easily
handled by eavesdropping on a short history of messages. The counters are
sequential and are sent in the clear.
I jumped out of my chair and ran over to the telephone stand,
grabbed the entire stack of scrap paper, and hurried back to the table.
I needed to get this down on paper before I forgot it.
I hurriedly took notes, not bothering to write
things down neatly; there would be plenty of time later to polish it
up and fill in details.
I used YZ to denote entity Y attempting to impersonate entity Z in
the protocol. The attacker, a legitimate member of the network, will be
denoted by X.
KDZ shall denote a key encrypted using a key-encrypting key known to Z.
KDUYZ shall denote a key encrypted using a key-encrypting key known to
Z and notarized with the identities of both Y and Z.
To start things off, the attacker, X, impersonates A requesting a key
from the key distribution center. In the request, X claims that A
wishes to communicate with the attacker (X).
Request messages of this type (RSI) do not contain any authentication codes
and are easily forged.
The key distribution center responds by generating a data-encrypting key.
That key is encrypted using the key-encrypting key associated with A
and included in the KD field. Also, the same key is encrypted and notarized
using the key associated with X.
Because KDUAX is encrypted using X's secret key, X can obtain the
plaintext for KDUAX.
X now sends an RFS message to the Key Translation Center, asking for
a key translation.
It is easy for X to forge this message, despite the MAC, because
X knows the value of the key used to compute the MAC --- it is the same
key as is encrypted in KDA and KDUAX, the latter of which X can
decrypt.
In response to this last message
the key translation center notarizes and encrypts the session key using B's
key-encrypting key and returns that ciphertext to X (thinking that X
is A).
The attacker now has a notarized and encrypted version of the session key
he originally obtained from Sd.
Impersonating A, the attacker can pass this notarized key on to B.
At this point, X can fool B into executing a session with X where
B believes that B is communicating with A.
Or, X can go on to inform A of the new key and allow both A and B to
believe they share a secret key when in fact X knows the key.
If X chooses the latter version of the attack then X impersonates the
key distribution center and sends the following message to A.
I twirled my pencil between my fingers
and leaned back in the chair.
I pursed my lips and whistled silently to myself.
Let's see now...
X can either send this message to A as an unsolicited RTR message
or X can wait until A requests a key for use with B.
After sending this message,
X then intercepts the response from A to B and discards it.
At this point A and B believe that they share a secret key
known only to them (and the trusted key server). However, the
key is also known to X.
Hot damn! This was it!
This attack works!
I leaned forward and let the front legs of the chair hit the floor
with a loud thud.
I took a deep breath.
I reminded myself that this attack requires some preliminary setup by the
attacker. It cannot be used to learn keys already in use.
Nonetheless, with minimal effort, an attacker can obtain the session keys
used by any communicating pair in the network. Thus, the use of separate
keys for each communicating pair is overkill --- the protocol might just
as well use a single key shared by the entire network. There is no additional
security obtained by the use of separate keys.
I walked over to the window.
What are my assumptions? First of all, the attacker needs to
have access to somebody's key-encrypting key...
Whoa!
My blood ran cold. In a sudden fit of paranoia I
glanced at the door, confirming that it was closed and the chain
drawn. I slowly laid my pencil on the desk and walked over to
the window. A shiver ran down my spine.
Staring at the street below, I allowed myself to
come to grips with the realization that the millwright definitely
was an insider, but not necessarily at Bendix.
The easiest way to meet my assumption is to assume that the attacker
was part of the EFT network --- i.e. a member bank,
any member bank.
We had always assumed that if the money mill was an inside job at all,
then the insider was probably at either First Chicago or Bendix.
Strangely, I found it far more disturbing that the mill was
being run by an insider with access to all X9.17 keys than
if the millwright were a lone hacker that had figured a way
to crack DES. A banker with the cleverness and Computer Science
know-how to devise the mill was a very dangerous adversary.
Quite probably with powerful allies.
I shuddered and
ran a hand through my already disheveled hair as I continued to
stare at the dark street below (sometimes it seemed I spent more time
staring at that same empty street than I spent at my desk).
All manner of questions raced through my mind.
Which bank? Was it an institutional effort being run from the
top or was it a single rogue employee? Even if it were the latter, the
employee would have to be one of a small number of highly trusted employees
if he or she had access to a triple-DES key-encrypting key.
Finally, I turned back to the desk.
I was forced to conclude that the X9.17 standard, approved by the
American Bankers Association in 1985, re-affirmed by the same group
in 1991, and recommended by NIST in 1992 for all government key exchange,
was completely vulnerable to impersonations of one member institution
by another member institution. There is little point in the banks
using separate key-encrypting keys because any bank can impersonate
any other bank; they might as well all be sharing a single key.
The protocol completely fails to satisfy requirements 4-6 and 9, as
laid out on page 12 of the standard. Those requirements state:
Nevermind all that, who was the millwright? If I was right in assuming that
the millwright was able to obtain a primary key-encrypting key
because he was a privileged employee of one of the banks,
that limited the number of people somewhat. But only somewhat. He
might be working for any one of the several thousand banks
in the network.
If he was a privileged employee of a bank, regardless of
whether he was acting alone or on behalf of a corrupt bank, he was likely
very knowledgeable in the mechanics of funds transfers. Far more so than
I was, for example.
Could it be that the millwright already knew we were tracking him?
Might he be watching my every move from afar?
I shook off a feeling of being watched. It was an absurd
thought. Somewhat annoyed with myself, I crossed the room and lifted
the phone and began punching in Lisa's number --- a number I'd long
since memorized but never bothered to store in the phone's memory.
But after only one ring I abruptly hung up, having suddenly decided
that it might be better to tell her in person than over the phone.
I knew all too well that phones were not secure from nosy people,
especially nosy people with an interest in noting any progress in
my detective work. In other words, I hadn't succeeded in ridding
the feeling of paranoia.
Grabbing my wallet off the kitchen table, I glanced
at the clock above the dishwasher and headed for the door.
Hmmm, 11:45. It would be 12:30 by the time I got all the way over to
Lisa's place. I wondered if our friendship was close enough to
allow for an unannounced visit at that hour.
Then I wondered if any friendship is close enough to allow for
such an intrusion (excluding friendships that are no longer referred
to as merely friendships).
I decided I'd better take the opportunity to catch up on eating and
sleeping and visit Lisa in the morning.
No good. She would be at work (she had a real job).
Reluctantly I realized I would have to take this discovery straight to
the FBI. Still, it would have to wait until morning.
Acronyms
RSI
Request Service Initiation (optional)
RFS
Request For Service
RTR
Response to Request message
RSM
Response Service Message
KSM
Key Service Message (contains encrypted key)
MCL
Message Class (type code)
RCV
Intended Recipient (identifier)
ORG
Originator (identifier)
IDC
Server used (identifier)
SVR
Service Class (type code)
NOS
Notarization indicator (flag)
IDU
Ultimate Recipient of encrypted key (identifier)
KD
Encrypted key (ciphertext)
KDU
Encrypted and notarized key (ciphertext)
CTA
Request counter for A
CTB
Request counter for B
MAC
Message Authentication Code for all preceding fields
Key Translation Center Environment
A ->St: RFS
St ->A: RTR
A ->B: KSM
B ->A: RSM
MCL
MCL
MCL
MCL
RCV
RCV
RCV
RCV
ORG
ORG
ORG
ORG
IDU
IDU
IDC
IDC
KD
KDU
KDU
MAC
CTA
CTB
CTB
MAC
MAC
MAC
Key Distribution Center Environment
A ->Sd: RSI
Sd ->A: RTR
A ->Sd: RSM
A ->B: KSM
B ->A: RSM
MCL
MCL
MCL
MCL
MCL
RCV
RCV
RCV
RCV
RCV
ORG
ORG
ORG
ORG
ORG
IDU
IDU
IDU
IDC
IDC
SVR
KD
MAC
KDU
MAC
KDU
CTB
CTB
MAC
CTA
MAC
None of these hold!
Not a single one.
The standard fails to meet four of the sixteen objectives clearly laid
out on page 12. How could such a grievous oversight occur in such
an important standard? Trillions of dollars were distributed every
day by EFT. CHIPS alone handles well over 150,000 messages every day.
The CHIPS network spans the globe and includes all of the major banks.