Skip to main content.
The Magic of Cryptography
and Magic Attacs against "Secure" Systems
Proseminar in Summer Term 2009

Teaching Assistant
First Meeting
Tuesday, April 28, 2009, 12:30 - 13:30 in room 2.18, second floor of building E1.1.
Lecture Time
Blockseminar at the end of term, dates will be fixed in the first meeting
Language
Presentations in English or German, depending on the choice of the speaker
Contact
duermuth
rkxc52txf1
@cs
yqr5nc9nqi
.uni-sb.
y2pwxvthq4
de

News

Description

Can you gain administrator-rights with a hair-drier? Can you break ciphers with a stop-watch? Can you prove to know a secret without revealing it? Can you share a secret such that every part of it is useless? Can you sniff passwords with a microphone?
Answers to all of these questions and many more will be given in this proseminar, which will lead us through various areas of cryptography and attacks against "secure" systems.
In the first part, some historic examples will be given, for example how Caesar enciphered his messages, how laziness helped to break the Enigma, and how to encrypt in a provably secure manner.
The second part deals with Modern Cryptography, for example how to securely share secrets, how one can throw fair coins over the internet, how to prove knowledge of a secret without revealing it, and many things more.
The third part deals with recent and surprising attacks against "secure" systems, for example by injecting faults into certain memory areas, by sniffing keyboards with a microphone, and by analyzing power consumption curves.

Requirements

The target audience are students in the third and fourth semester, but even in earlier semesters participation is possible. Some knowledge in theoretical computer science is useful, but not necessary. Some presentations require knowledge in elementary number theory and statistics, but those are marked accordingly.

Organization

Each participant gives a presentation (25 minutes and 5 minutes discussion) and provides a written summary (6-8 pages).

The proseminar will be held as blockseminar at the end of term; the date will be fixed in the first meeting (see above).

Registration

Please send preliminary registrations to the above E-Mail address. Assignment of topics will be done in the preliminary meeting.

List of Topics

The reference printed bold serves as the main reference for each presentation i.e., these should be well understood. The additional references may provide deeper or additional insights and ideas that may be helpful in preparing the presentation, as well as interesting outlooks.

Part I: Ancient Wonders of Cryptography


1)      Decrypting Caesar's Secrets: Historical Cryptosystems


There is a long history of encryption. One of the first encryption schemes we are aware of was used by Julius Caesar, who substituted each letter by its third successor. A generalization is nowadays known as the Shift-Cipher; more elaborate ancient ciphers are the Permutation- and the Vigenère-Ciphers. However, with statistical attacks all of them can be broken rather easily. This presentation will introduce these ciphers, their historical background, and will show how they can be broken.

2)      How Cryptanalysis influenced World War II: Cryptanalysis of the Enigma


In 1918 the German inventor Arthur Scherbius constructed an electric encryption machine called Enigma. There exist several variants of this machine, with some of them being used in World War II to encrypt military communications. However, the Allies where able to break the code and to read the military commands. The main reason was improper use of the Enigma by the Germans, giving enough information away to break the encryption. However, there are also statistical weaknesses that enable attacks against it. This presentation will describe the construction of the Enigma, how improper use can weaken its security, and general attacks against the machine.

3)     The (Almost) Final Solution to Encryption: Shannon Theory and the One-time Pad

In 1949 Shannon came up with the first mathematical definition of security of encryption schemes. He furthermore proposed a cryptosystem that he proved secure according to this definition. It was a generalization of the Vigenère-Cipher where the keys are as long as the text to be encrypted. In this presentation, Shannon's security definition is motivated, the proof for the security of the One-time Pad is given, and a theorem by Shannon is sketched stating that no cipher with shorter secret keys can be secure according to this definition.
 

Part II: Modern Crypto-Magic

4)      Secret Sharing

Secret Sharing means splitting a secret between a group of people such that only certain subgroups together can retrieve the secret. In the simplest case, when one requires collaboration of all parties on can simply XOR the secret with several random strings and distribute the XOR and the random strings to different parties. More sophisticated schemes are so-called threshold schemes, where m out of n parties can retrieve the secret, but m-1 parties cannot gain any information about the secret. But also for very general, so-called monotone access structures, secret sharing schemes exist.

5)      Planning a Jailbreak: Use Steganography


When planning a jailbreak it is not sufficient to simply encrypt messages, as the mere existence of a message might be suspicious, but instead one needs a method to hide information in other, harmless, information. History gives numerous examples of how this can be done, e.g., by using invisible ink, and modern cryptography provides even more sophisticated methods. This presentation discusses definitions of what it means to hide information, and some algorithms to achieve this goal are discussed.

6)      Exchanging Secrets: Fair Exchange and Contract Signing
(Advanced)

If two parties not trusting each other want to sign a contract, they need special measures to prevent the following type of attack against too simple implementations: One party signs the contract, sends it to the other party, which signs it as well, and sends the contract (including both signatures) back. Now if the second party simply aborts the protocol before sending the contract back, it gained an advantage. There are two different approaches to solve this problem. One is “gradually releasing” the signed messages, thus not giving the other party too much advantage at any time, the other approaches is involving a trusted third party that can be invoked upon cheating of one participant. This presentation will mainly focus on the approach of "gradually releasing", but will also give a comparison of the two approaches.

7)      Mental Poker or: Tossing Coins over the Internet
(Advanced)

Imagine you need to throw a coin with somebody on the phone. You can let him throw the coin for you, but this obviously is not what you want. Or both of you throw a coin and then XOR them together, but whoever tells his result first is in disadvantage. Fortunately, with cryptography one can do better. Closely related is the Millionaire's problem, where two millionaires want to find out who is richer, without revealing their wealth. Both problems are instances of secure multiparty computation, which means computing functions in a distributed manner without revealing information (apart from the result of the computation) to the participants.

8)  Beyond Current Limitations: Quantum Cryptology
(Advanced)

Almost all cryptographic systems are based on hard mathematical problems like Integer Factoring, the RSA-problem, the Diffie-Hellman-problem, etc. In contrast, quantum cryptology is based on physical facts. This presentation will concentrate on quantum key exchange, which is one of the first examples of quantum cryptography. Random bits can be transmitted in such a way that any eavesdropping can be detected with very high probability. Another consequence of quantum computation is a polynomial-time factoring algorithm on quantum computers, its implications will be explained briefly.

Part III: Magic Attacks on “Secure” Systems 


9)  Breaking a Cryptosystem with a Stop-watch: Side-channel Attacks


Usually when addressing the security of an algorithm one takes into account only the inputs and outputs of the algorithm. But if additional information is available, like measurements of execution time, power-consumption curves, or electric emanation curves, sometimes even  otherwise secure systems can be broken. This presentation will focus on the first such attack by Paul Kocher, which used timing characteristics to break common implementations of RSA and other systems. Furthermore, it will review related attacks and countermeasures.

10)  Buffer Overflows (Programming)
Arguably the biggest practical threat to computer security is buffer overflows; almost every day new vulnerabilities are found that can be exploited by such an attack. This presentation will introduce the concept of buffer overflows, show how an attack can be carried out, describe countermeasures that are actually implemented, and describe how some of these can be circumvented.

11)  Gaining Root-privileges with a Hair-drier: Fault Induction
(Programming)

Somehow related to side-channel attacks are fault injection attacks. There faults are injected into a computing device, usually by some sort of radiation or heat, which causes memory cells to change. This way, if the setting is chosen carefully, RSA keys can be read, or access control mechanisms can be fooled. The presentation will focus on a specific attack against a Java VM that circumvents access control mechanisms, resulting in gaining administrator rights. It will also give a brief overview of other related attacks and appropriate counter-measures.

12)  Looking Around Corners: Visual Screen Emanation


It is well-known that images on CRT displays can be reconstructed by recording their electromagnetic emanation even from a large distance. New results show that even by recording the optical reflections of the monitors image at a wall using a high-speed optical sensor, it is possible to reconstruct the monitors image. This presentation describes this new attack, and gives a brief survey on related attacks.

13)  Sniffing Passwords with a Microphone: Acoustic Emanation of Keyboards


Not only visual and electromagnetic emanation, but also acoustic emanation can be used to spy out computers. Almost all keyboards produce sounds when keys are pressed that differ from key to key. These differences cannot be distinguished by the human ear, but by computers. There are two versions of this attack: The simpler one is trained by humans, the more complex one is self-learning by exploiting AI techniques.

14)  How not to do it: Wired Equivalent Privacy

There is a long history of attacks against WEP. From the very beginning, the size of the keyspace was limited. Some implementations used alorithms that output keys with entropy as low as 21 bits, making brute-force attacks quite feasible. A major break-through was discovering so-called weak IV's. These attacks where later refined by actively injecting packets to the network, reducing the time needed for an attack to several hours. Very recently, a different type of attack was discovered using packet fragmentation to mount an attack in seconds. 

15)  How the Wrong Time can Reveal Your Location


Anonymity services such as Tor allow for location-hidden services; services that are accessible over the Tor network, but the identity of the server is hidden from the world. However, using the service increases CPU load and thus the temperature of the server. The influence of the temperature on the clock skew can be measured remotely and the location of the hidden service can be determined.