Definition
Security
Undecidability
Security properties are undecidable
Security is about the following: If an attacker perform some unexpected action, where there’s an infinite number of possible inputs/actions, the system must not do any really bad action.
This is a black-box statement. We don’t care about the internals/syntax of the problem’s nature. We only care about the output: whether a system is secure.
Further, we know that there are systems that are insecure, and some that are secure, e.g. a program written in a memory-safe language vs. a program written in a non-memory-safe language, assuming that secure refers here to the property of a system being memory-safe.
This is a non-trivial extensional language property. According to Rice’s theorem, this implies the undecidability of security properties. Hence, we can conclude that security is hard.
Link to original
History
World’s First Hack
In 1903, G. Marconi and J. Fleming demonstrated a supposedly secure wireless telegraph at the Royal Academy of Science in London. During the demonstration, British magician N. Maskelyne forged offensive messages, disproving the security claims.
Cryptobombs
In October 1938, M. Rejewski, H. Zygalski, and J. Różycki developed the bomba kryptologiczna, used to break early Enigma machines. In December 1938, two new rotors were added to Enigma, introducing a tenfold increase in the attack’s complexity.
In 1940, the British bombe was deployed by A. Turing, G. Welchman, and H. Keen, based on the Polish one. In 1942, the US Navy constructed an improved bombe supporting the new 4-rotor Enigma machines used from 1941.
Phreaking
Phreaking was a culture of people who experimented with public telephone networks to understand their inner workings. It gained strong popularity through the reverse engineering of routing techniques for long-distance calls.
AT&T’s automated switches used in-band signalling to transmit commands such as ending a call or dialling a number. A tone of 2600 Hz indicated that the call was over while the carrier line remained open. This made it possible to call a toll-free number in the target area, send the command to end the call and start a new one, and then place a new call without being charged.
The First Malware Appears
Creeper (1971) is acknowledged as the first malware in history. It spread over the 28 computers connected to ARPANET that were running the TENEX operating system and printed a message to the console of infected systems, but caused no actual harm. Reaper (1972) is the first anti-malware software in history. It spread using the same technique as Creeper, deleted Creeper from the infected system, and after some time deleted itself.
First Break-ins into Computer Systems
K. Mitnick broke into the Ark in 1979, the computer system used by DEC to develop the operating system RSTS/E. He was sentenced in 1988 to one year in prison and three years of probation for having copied DEC’s software.
A group of teenagers known as the 414s broke into multiple high-profile computer systems between 1982 and 1983. They exploited common and default passwords, which triggered the development of laws specific to computer fraud in the US.
First Legislation Against Computer Fraud
In 1986, the US Congress passed the Computer Fraud and Abuse Act, making breaking into computer systems a crime. In 1990, the UK Parliament passed the Computer Misuse Act in reaction to the acquittal of S. Gold and R. Schifreen, who had managed to access the mailbox of the Duke of Edinburgh by shoulder surfing the credentials of a British Telecom engineer.
They were convicted under the Forgery and Counterfeiting Act 1981, but the Court of Appeal overruled the sentence because the charges were inappropriate and there was no material gain.
The Growing Costs of Malware
The Morris worm (1988) was the first to attract the attention of mainstream media. It exploited weak passwords and vulnerabilities in sendmail and finger. A couple of thousand computers were infected, with an estimated economic impact between 10,000,000.
AIDS (1989) is the first known ransomware. It hid all directories and encrypted all filenames after the 90th reboot of the computer. A floppy disk reversing the changes was shipped upon payment of a ransom.
Melissa (1999) is to date the fastest macro virus to spread via e-mail. Upon opening the infected file, the virus sent itself to the first 50 contacts of Microsoft Outlook and modified the template file Normal.dot to infect other document files. Around 100,000 computers were infected on the first day, and the estimated damages were $80 million.
ILOVEYOU (2000) is a worm that infected over 10 million Windows PCs via e-mail within a few days. It was contained in an attachment whose name included two extensions, “.TXT.vbs”, with the second often hidden. After execution, the worm spread itself via Microsoft Outlook, randomly overwrote local files, and downloaded a trojan to steal the user’s passwords. Estimated damages and removal costs worldwide were $15 billion.