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

Instructor
Prof. Dr. Michael Backes
Teaching Assistant
Prof. Dr. Michael Backes
Markus Dürmuth
Lecture Time
Blockseminar at the end of term, dates will be fixed in the first meeting
First Meeting
Tuesday, April 17, 2007, 16:15 in Room SR014, E1.3
Language
Presentations in English or German, depending on the choice of the speaker
Contact
d
3orrbybmqp
ue
ulth0ar891
r
aqcbckkvnh
muth@cs.uni-sb.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.

Preliminary 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)      Public-key Cryptography

In 1976, Diffie and Hellman introduced the revolutionary concept of public-key cryptography, where keys no longer needed to be exchanged in a secret manner, but can be exchanged on authenticated but non-private channels. This invention has been one of the key inventions of cryptography in the last 30 years and serves as the basis of many recent results in cryptography. In this presentation, the fundamentals of public-key encryption and signatures are presented, and public-key encryption is compared to the secret-key encryption.

5)      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.

6)      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.

7)      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.

8)      Proving Knowledge of a Secret without Revealing it: Zero-knowledge (Advanced)

The concept of Zero-Knowledge is a very powerful and surprising concept in modern cryptography. How can one prove something to somebody without revealing any information, e.g., how can one prove to know a secret without revealing it? This presentation will motivate basic definitions concerning Zero-knowledge, and describe simple protocols.

9)      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.

10)  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 


11)  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.

12)  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.

13)  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.

14)  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.

15)  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.

16)  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.