Skip to main content.
The Magic of Cryptography
– and Magic Attacks against “Secure” Systems –
Proseminar in Summer Term 2011

Teaching Assistant
Lecture Time
Blockseminar at the end of term. Presentations: June, 27 & 28, 2011.
First Meeting
Wednesday, April 13, 2011, 14:00 - 15:00 in room 4.07, building E1.1.
Language
Presentations in English or German, depending on the choice of the speaker
Contact
prose
6wg1c49qoj
minar2011@mail-i
nf1w21yvwx
nfsec
zb7xh0se6q
.cs.uni-saarland.de

News

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 summary must be written in LaTeX. If you are not familiar with LaTeX, you may use this draft as a starting point. You need to run pdflatex on the file at least twice to obtain this pdf.
The proseminar will be held as blockseminar at the end of term (see above).

Registration

Please send preliminary registrations to proseminar2011@mail-infsec.cs.uni-saarland.de. Assignment of topics will be done in the preliminary meeting. If you do not show up in this meeting, your registration will be void and the topics will be assigned to other students. We have 15 topics available and students will pick their topic in the order of received preliminary registrations.

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
(Adv: Matthias Berg)

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.
  • Nigel Smart: Cryptography: An Introduction. McGraw-Hill, 2003. (§§3.1 – 3.5)
  • Simon Singh: The Code Book. Doubleday, 1999.
  • Edgar Allan Poe: The Gold Bug, 1843.
  • David Kahn: The Codebreakers. Scribners,1996.

2)      How Cryptanalysis influenced World War II: Cryptanalysis of the Enigma
(Adv: Matthias Berg)

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.
  • Nigel Smart: Cryptography: An Introduction. McGraw-Hill, 2003. (§3.7)
  • Simon Singh: The Code Book. Doubleday, 1999.
  • David Kahn: The Codebreakers. Scribners, 1996.

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

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.
  • Nigel Smart: Cryptography: An Introduction. McGraw-Hill, 2003 (§4)
  • Douglas R. Stinson: Cryptography: Theory and Practice. Chapman & Hall, 2002.
 

Part II: Modern Crypto-Magic

4)      Secret Sharing (Adv: Raphael Reischuk)

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.
  • Adi Shamir: How to Share a Secret, Communications of the ACM, Vol. 22(11), 1979.
  • Josh Benaloh and Jerry Leichter: Generalized Secret Sharing and Monotone Functions. In Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, 1988.

5)      Planning a Jailbreak: Use Steganography
(Adv: Matthias Berg)

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.
  • Fabien A. P. Petitcolas, Ross J. Anderson, and Markus G. Kuhn: Information Hiding – A survey. In Proceedings of the IEEE, 87(7), 1999.
  • Michael Backes, Christian Cachin: Public-Key Steganography with Active Attacks. In Proc. 2nd Theory of Cryptography Conference (TCC 2005), 2005.  

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

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.
  • Oded Goldreich: A Simple Protocol for Signing Contracts. In Proceedings of Crypto ‘83, 1984.
  • Shimon Even, Oded Goldreich, and Abraham Lempel: A Randomized Protocol for Signing Contracts. Communications of the ACM, Vol. 28(6), 1985.
  • N. Asokan, Matthias Schunter, and Michael Waidner: Optimistic Protocols for Fair Exchange. ACM Conference on Computer and Communications Security, 1997.

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

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.
  • Manuel Blum: Coin flipping by telephone – A protocol for solving impossible problems. In Proceedings of the ACM SIGACT, 1983.
  • A.C. Yao: Protocols for secure computation. In Proceedings of the IEEE FOCS ’82.

8)  Beyond Current Limitations: Quantum Cryptology
(Adv: Matthias Berg) (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.
  • Charles H. Bennett and Gilles Brassard: Quantum Cryptography: Public Key Distribution and Coin Tossing. Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, 1984.
  • Charles P. Pfleeger and Shari Lawrence Pfleeger: Security in Computing. Prentice Hall, 2003.
  • Peter W. Shor: A Polynomial Time Algorithm for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, Volume 26 ,  Issue 5 1997.

Part III: Magic Attacks on “Secure” Systems


9)  Breaking a Cryptosystem with a Stop-watch: Side-channel Attacks
(Adv: Raphael Reischuk)

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.
  • Paul Kocher: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. Proceedings of Crypto' 96, 1996.
  • Jean-Jaques Quisquater, François Koene: Side channel attacks: State of the Art (October 2002)
  • Daniel Bleichenbacher: Chosen Ciphertext Attacks against Protocols Based on RSA Encryption Standard PKCS #1. in Advances in Cryptology –  CRYPTO'98, LNCS vol. 1462

10)  Buffer Overflows (Programming) (Adv: Matthias Berg)
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.
  • Aleph One: Smashing the Stack for Fun and Profit. Phrack Volume 7, Issue 49. Online at http://reactor-core.org/stack-smashing.html
  • Jon Erickson: Forbidden Code. Mitp-Verlag, 2004
  • Heise.de: Buffer-Overflows und andere Sollbruchstellen. Online available at http://www.heise.de/security/artikel/37958

11)  Gaining Root-privileges with a Hair-drier: Fault Induction
(Adv: Matthias Berg) (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.
  • Sudhakar Govindavajhala, Andrew W. Appel: Using Memory Errors to Attack a Virtual Machine. Proceedings of the 2003 IEEE Symposium on Security and Privacy, 2003.
  • Jean-Jaques Quisquater, François Koene: Side channel attacks: State of the Art (October 2002)

12)  Looking Around Corners: Visual Screen Emanation
(Adv: Matthias Berg)

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.
  • Markus G. Kuhn: Optical Time-Domain Eavesdropping Risks of CRT Displays. Proceedings of the 2002 IEEE Symposium on Security and Privacy, 2002.
  • Wim van Eck: Electromagnetic Radiation from Video Display Units: An Eavesdropping Risk? Computers and Security, Vol. 4, pp 269 – 286, 1985.
  • R. J. Anderson and M. G. Kuhn. Soft tempest – an opportunity for NATO. In Proceedings of Protecting NATO Information Systems in the 21st Century, IST Symposium, Washington DC, USA, Oct. 1999.

13)  Sniffing Passwords with a Microphone: Acoustic Emanation of Keyboards
(Adv: Matthias Berg)

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.
  • Dmitri Asonov, Rakesh Agrawal: Keyboard Acoustic Emanations. Proceedings of the 2004 IEEE Symposium on Security and Privacy,  2004.
  • Li Zhuang, Feng Zhou, J.D.Tygar: Keyboard Acoustic Emanations Revisited. To appear in Proceedings of the 12th ACM Conference on Computer and Communications Security, November 2005.
  • R. J. Anderson and M. G. Kuhn. Soft tempest – an opportunity for NATO. In Proceedings of Protecting NATO Information Systems in the 21st Century, IST Symposium, Washington DC, USA, Oct. 1999.

14)  How not to do it: Wired Equivalent Privacy (Adv: Matthias Berg)

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. 
  • Andrea Bittau, Mark Handley, and Joshua Lackey: The Final Nail in WEP's Coffin. Proceedings of the 2006 IEEE Symposium on Security and Privacy 2006.
  • Adam Stubblefield, John Ioannidis, and Aviel D. Rubin: Using the Fluhrer, Mantin, and Shamir Attack to break WEP. Proceedings of the Network and Distributed System Security Symposium 2002.     

15)  How the Wrong Time can Reveal Your Location
(Adv: Matthias Berg)

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.
  • Steven J. Murdoch: Hot or Not: Revealing Hidden Services by their Clock Skew. Proceedings of the ACM CCS 2006.