My heart sank. It was hopeless. Even writing a program to trace the money would be futile. The bogus EFT’s were buried in the regular EFT traffic. EFT’s number in the hundreds of thousands every day. This may not seem like a lot, after all a modern computer is capable of millions of instructions per second. Yet, with so many accounts in so many banks with so much activity, even with the use of super-computers there is no hope of being able to trace the money to determine which account is the one the attacker is using to collect his interest. It was an NP problem and for an NP problem, an input of 100,000 is hardly small.
Computer scientists have a way of classifying difficult problems. By measuring the run-time of the fastest algorithm for a problem, we can characterize the difficulty of solving the problem. We measure run-time as a function of the size of the input. For example sorting a list of words into alphabetical order is considered to be an n*log(n) problem. This is because the world’s best sorting programs require n*log(n) operations, where n is the number of words in the list and log is the base-2 logarithm function. A complexity of n*log(n) means that if the program takes 30 seconds to sort 100 words, it will take about 7.5 minutes to sort 1000 words. The time we must wait for an answer grows with the size of the problem. The rate of growth is n*log(n). This is generally considered to be an acceptable rate of growth. There are many natural problems with much higher complexity functions. Many of these problems have exponential complexity. Path enumeration in a directed graph is but one example. There are many such problems. Some of them are well-studied problems with colorful names. The cute names often bely the abstract and complex mathematical nature of the problems. These are names like the Traveling Salesman Problem, the Chinese Postman for Mixed Graphs, the Rural Postman, the Crossword Puzzle Construction Problem, the Knapsack Problem, and, my personal favorite, the Left-Right Hackenbush for Redwood Furniture Problem. These, and many more, are all programming problems for which the best known algorithms have exponential complexity. If a problem with exponential complexity takes one second to process an input of length 20, then it takes 366 centuries to process an input that is only three times that size!
| 10 | 20 | 30 | 40 | 50 | 60 | |
| n | 0.00001 | 0.00002 | 0.00003 | 0.00004 | 0.00005 | 0.00006 |
| n2 | 0.0001 | 0.0004 | 0.0009 | 0.0016 | 0.0025 | 0.0036 |
| n3 | 0.001 | 0.008 | 0.027 | 0.064 | 0.125 | 0.216 |
| n5 | 0.1 | 3.2 | 24.3 | 1.7 min | 5.2 min | 13.0 min |
| 2n | 0.001 | 1.0 | 17.9 min | 12.7 day | 35.7 yrs | 366 cent |
I groaned and slumped down in the chair. It was hopeless.
Lisa was smiling broadly and shaking her head in wonderment. “This is no ordinary hacker,” she laughed. “This guy knows his computer science. Embedding the attack inside an NP problem… you have to admit, he’s no slouch.”
She was positively beeming. I didn’t share her admiration. We needed to solve this NP problem… fast. Apparently she had forgotten that the three of us were prime suspects. With every additional day Lisa spent with Rudy and I, it would be easier for the FBI to build a case against the three of us, claiming that the three of us were in cahoots. I already had a track record for tinkering with things I shouldn’t; Rudy had already been implicated in the delay scam; and Lisa was several thousand dollars wealthier due to one night’s work.
Even if the FBI did not believe that we were guilty of running the attack, with such a bold assault on our nation’s banking system they would need a scapegoat. Any one of the three of us would serve the purpose; together we made a perfect EFT counterfeiting ring.
“It is the perfect crime!” Lisa exclaimed. “And it is all made possible by the electronic banking system. Using a computer to automate the crime, the criminal can mount an attack of staggering complexity!”
She then proceeded to tick off the steps, one by one, on her fingers:
- find a way to forge message authentication codes for banking;
- write a computer program to generate fake payments;
- generate hundreds of thousands of them;
- make it so most of them are only decoys, but also make it so a few of them result in overnight loans;
- launder the money by routing it through thousands of accounts;
- use a computer and do this daily so that there is a continuous flow of dollars through your account;
- collect the interest;
- and, to cap it off, hide the whole thing in a huge graph, making the investigation of your crimes an NP-complete problem.
“And,” she continued, “the real kicker is that the entire thing would never have been discovered at all if it had not been for the coincidence of two other seperate attacks: your replay experiments Carl; and your delay scam Rudy. The interference of the three seperate attacks is the only thing that brought the counterfiet EFT’s to light. Now, even when we know the forgeries exist, there is no feasible way to determine who is behind them. Whoever it is can keep right on doing it; nobody can stop it.”
Rudy sat down and rested his chin in his hand. He spoke quietly, musing to himself. “Our adversary simply channels money from all over the world into his account. He returns the money as quickly as he takes it. He is careful to borrow only small amounts from any individual. Nobody notices the absence of a few dollars for one night. Those customers that do notice the unauthorized EFT’s also notice that they balance. Most of the forged EFT’s are assigned the code used for error corrections, so when cautious customers do call with a complaint, the problem is quickly diagnosed as an internal matter that has been corrected by the bank, with no apparant loss to the customer — the matter never gets beyond the help-desk.
“Our adversary is clever. By forging error-correcting EFT’s, very little suspicion is arroused by customers or by bank personel fielding the occasional complaint. Furthermore, our adversary does not steal money outright; instead he or she makes money off the flow of money. What we are witnessing is a money mill.”
“Yes,” I said, “and the more money flows through the graph, the more interest is paid out. It really is an electronic money mill.” And so it was. Somebody was running a large money mill right in the midst of our nation’s regular banking activity. Intermixed with legitimate transactions were counterfeits. These raced through the EFT network, collecting small amounts of money from accounts all over the world. Like a millrace, these transactions poured money down the chute and over the wheel. As the wheel turns interest is paid out. Once it passes over the wheel, the money flows back to the accounts from whence it came. The total volume of money in the system is preserved. And yet, at the same time, new money, in the form of interest, is generated and paid out to the person running the mill. That person would be the millwright.
Which account did the millwright use to collect his or her interest? There must be some part of the EFT graph where all paths lead through a small number of accounts. These accounts would be the millrace — the chute down which the money flows, leading it to the wheel.