Cryptography Reference
In-Depth Information
Others have extended Turing's results to show that it is practically
impossible to ask themachines to say anything definitive about com-
puters at all. Rice's theorem showed that computers can only answer
trivial
questions about other computers [HU79]. Trivial questions
were defined as those that were either always true or always false.
Abraham Lincoln was
really the first person to
discover this fact when
he told the world, “You
can fool some of the
people all of the time
and all of the people
some of the time. But
you can't fool all of the
people all of the time.”
Thesameholdstrueif
you substitute
“computer program” or
“turing machine” for
“people.”
To some extent, these results are only interesting on a theoreti-
cal level. After all, a Macintosh computer can examine a computer
program written for an IBM PC and determine that it can't execute
it. Most of the time, a word processor might look at a document and
determine that it is in the wrong format. Most of the time, comput-
ers on the Internet can try to establish a connection with other com-
puters on the Internet and determine whether the other computer is
speaking the right language. For many practical purposes, comput-
ers can do most things we tell them to do.
The operative qualifier here is “most of the time.” Everyone knows
how imperfect and fragile software can be. The problems caused by
the literal machines are legendary. They do what they're told to do,
and this is often incomplete or imperfect—just like the theoretical
model predicted they would be.
The matter for us is compounded by the fact that this application
is not as straightforward as opening up word processing documents.
The goal is to hide information so it can't be found. There is no co-
operation between the information protector and the attacker trying
to puncture the veil of secrecy. A better model is the world of com-
puter viruses. Here, one person is creating a computer program that
will make its way through the world and someone else is trying to
write an anti-virus program that will stop a virus. The standard virus-
Can you abort a virus?
Can you baptize one?
How smart must a virus
be to be a virus?
scanning programs built today look for tell-tale strings of commands
that are part of the virus. If the string is found, then the virus must
be there. This type of detection program is easy to write and easy to
keep up to date. Every time a new virus is discovered, a new tell-tale
string is added to the list.
But more adept viruses are afoot. There are many similar strings
of commands that will do a virus's job. It could possibly choose any
combination of these commands that are structured correctly. What
if a virus scrambled itself with each new version? What if a virus
carried a context-free grammar of commands that would produce
valid viruses? Every time it copied itself into a new computer or
program, it would spew out a new version of itself using the gram-
marasitscopy.Detectingviruseslikethisisamuchmoredifficult
proposition.
You couldn't scan for sequences of commands because the se-
quences are different with each version of the virus. You need to
