The Magic of Cryptography
and Magic Attacs against "Secure" Systems
Proseminar in Summer Term 2009
Instructor
Teaching Assistant
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@cs
uva5vcpmmy
.unisb.okyjq6l4gz
deqiydu42ugc
News
 The talks will take place on Monday, July 13 (whole day) and Tuesday, July 14 (morning).
 We assigned the following supervisors to the speakers of the Proseminar

 Raphael Reischuk:
Jingwen Hu (Topic 1/2)
Karsten Knuth (Topic 3)
Aleksandra Pochron (Topic 4)
Nicolas Rickert (Topic 5)  Esfandiar Mohammadi:
Doris Kneip (Topic 6)
Tobias Tebbi (Topic 8)
HasanAli Dinc (Topic 10)
Joachim Lutz (Topic 11)  Markus Dürmuth:
Dominik Feld (Topic 13)
Adam Kusmirek (Topic 14)
Stefan Tombers (Topic 15)
 Raphael Reischuk:
 Organizational Meeting:
Tuesday, April 28, 2009, 12:30  13:30 in room 2.18, second floor of building E1.1.
If you cannot participate at all, please send me an email.  Please register by sending an eMail to the above eMail.
 Site set up.
Description
Can you gain administratorrights with a hairdrier? Can you break ciphers with a stopwatch? 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 (68 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 EMail 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 ShiftCipher; more elaborate ancient ciphers are the Permutation and the VigenèreCiphers. 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. McGrawHill, 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
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. McGrawHill, 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 Onetime 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èreCipher 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 Onetime 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. McGrawHill, 2003 (§4)
 Douglas R. Stinson: Cryptography: Theory and Practice. Chapman & Hall, 2002.
Part II: Modern CryptoMagic
4) Secret SharingSecret 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 socalled threshold schemes, where m out of n parties can retrieve the secret, but m1 parties cannot gain any information about the secret. But also for very general, socalled 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
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: PublicKey Steganography with Active Attacks. In Proc. 2nd Theory of Cryptography Conference (TCC 2005), 2005.
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.
 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)
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 (Advanced)
Almost all cryptographic systems are based on hard mathematical problems like Integer Factoring, the RSAproblem, the DiffieHellmanproblem, 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 polynomialtime 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 Stopwatch: Sidechannel 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, powerconsumption 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 DiffieHellman, RSA, DSS, and other systems. Proceedings of Crypto' 96, 1996.
 JeanJaques 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)
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://reactorcore.org/stacksmashing.html
 Jon Erickson: Forbidden Code. MitpVerlag, 2004
 Heise.de: BufferOverflows und andere Sollbruchstellen. Online available at http://www.heise.de/security/artikel/37958
11) Gaining Rootprivileges with a Hairdrier: Fault Induction (Programming)
Somehow related to sidechannel 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 countermeasures.
 Sudhakar Govindavajhala, Andrew W. Appel: Using Memory Errors to Attack a Virtual Machine. Proceedings of the 2003 IEEE Symposium on Security and Privacy, 2003.
 JeanJaques Quisquater, François Koene: Side channel attacks: State of the Art (October 2002)
12) Looking Around Corners: Visual Screen Emanation
It is wellknown 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 highspeed 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 TimeDomain 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
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 selflearning 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
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 bruteforce attacks quite feasible. A major breakthrough was discovering socalled 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
Anonymity services such as Tor allow for locationhidden 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.