The Cryptography Project
Each student of the course will study a subject
relating theory and practice of cryptography.
This project will consist of a literature study,
writing a paper, and giving an oral presentation of the subject.
The papers will be collected in a booklet that we will write together.
Following are some subject suggestions.
You may also explore a subject of your own choice,
but only after consultation with the teacher;
for subjects, see for example the Internet section
The references given below of course just represent the view of one author on the subject and are meant as a pointer into the literature on the subject.
LNCS means Lecture Notes in Computer Science, this series of books is found in the Computer Science library.
Projects with a NAME were already assigned.
- Quantum Factorization (Bart):
Over a decade ago, Shorr proposed a quatum algorithm for factoring RSA moduli.
By lack of quantum computers, the algorithm was not yet put into practice, but recently, Chinese and Australian researchers claimed the completion of a successful machine.
How safe is RSA in the decades to come?
- The RSA Challenges (Eleni):
To keep an eye on progress in factoring and discrete logarithm calculation,
RSA Inc. publishes challenges.
With what techniques do people get the prizes?
How fast is the progress?
Can the challenge help us to predict the future?
- Breaking WPA (Wesley vV):
German researchers will present a
break of WPA at a conference in December 2008.
This is a more accessible view of the work.
An attacker, who has about 12-15 minutes access to the network is then able
to decrypt an ARP request or response and send 7 packets with custom
content to network.
- New hash function designs (Wesley K):
There is an open contest going on to find a replacement for the current hash functions like SHA2.
Discuss the requirements,
and the Skein
and MD6 proposals.
- McEliece crypto-system (Steven Bitter):
The public key system by McEliece was called the system of the future, but is was successfully attacked even before the future has begun.
- Hash collisions (Jan-Olav):
Among the more shocking developments in 2006 was the breaking of the MD5 and SHA1 hash algorithms.
What are these algorithms, what technique was used in the attack, and how severely does it endanger existing applications?
Will SHA2 be safe?
Gebroken codes, NRC W&O bijlage, 11 februari 2006.
Impact of Rotations in SHA1,
Pramstaller, Rechberger, Rijmen,
LNCS3897, pp 261-275.
A study of the MD5 attacks: Insights and Improvements,
J. Black, M. Cochran, T. Highland,
iTune vouchers cracked:
Chinese hackers have cracked the algoritm that generates iTunes gift vouchers (March 2009).
How does this algorithm work, and how could it be cracked?
Implementations on current architectures:
Cryptosystems should obviously be hard to break, but they should also be easy to compute.
How Far Can We Go On The X64 Processors?,
- Malleability (René):
A requirement for encryption that is stronger than the usual confidentiality is non-malleability:
Given the public information and a few messages, it is impossible to create ciphertexts whose content is in any way related to the content of the given messages.
Discuss applications where non-malleability is important, systems that have or lack this property,
and techniques to achieve it.
Construction of a Non-Malleable Encryption Scheme from Any Semantically Secure One,
R Pass, A. Shelat, V. Vaikuntanathan,
- Multivariate Cryptography (Sanne):
In many cryptosystems, a plaintext is represented by a single number x, that is subject to a computation (univariate);
consequently, an attacker faces an equation with one unknown.
Multivariate systems represent the plaintext by several numbers and apply encryption with multivariate formulas.
Examples are Hidden Field Equation and the
Matsumoto-Imai scheme discussed by Shamir in his recent lecture.
Despite a decade of research, the success in applying these principles has been limited.
Inverting HFE Is Quasipolynomial,
L. Granboulan, A. Joux, J. Stern,
- Advanced Encryption System (Anieke, Pieter):
The DES algorithm discussed in class was succeeded by the AES in 2002.
Has AES stimulated cryptography research like its predecessor did?
What is known about AES security?
How were the principles of diffusion and confusion applied in AES design?
How many of DES and 3DES applications have actually been converted to AES already?
(So many questions that the project is suitable for two persons.)
- Trust Calculus for PKI:
Certificate Authorities help users decide whom to trust or distrust.
Situations involving delegated permissions and unknown CA's may become so complicated that a trus calculus is helpful.
Modeling Public Key Infrastructures in the Real World,
John Marchesini, Sean Smith, LNCS3545, pp 118-134.
- Certificates and Root Keys (Robin):
Integrity of web sites is verified from signed certificates, but the signatures under these certificates must be checked as well.
What is an X509 certificate,
how are root keys stored,
how are they used in SSL, TLS,
can we do without them,
are successful attacks possible?
Installing Fake Root Keys in a PC,
Adil Alsaid and Chris J. Mitchell,
- Schnorr-like proofs with unknown order:
Some applications of discrete logarithms use generators of unknown order.
Can knowledge of a logarithm be proved in zero knowledge?
Cryptanalysis of an Efficient Proof of Knowledge of Discrete Logarithm,
S. Kunz-Jacques, G. Martinet, G. Poupard, J. Stern,
Practical Elliptic Curve Systems (Tom):
Elliptic Curve Systems are often advocated for their high speed and small memory requirements.
Curve25519: New Diffie-Hellman Speed Records,
- Side Channel attacks and Countermeasures:
Smart devices with a secret exponent can sometimes be attacked by measuring their behavior during the computation.
(As opposed to classical attacks, that are based on input-output observations.)
Splitting the secret exponent is considered an effective countermeasure.
High-Order Attacks Against the Exponent Splitting Protection,
F. Muller, F. Valette,
- Secure Computing with Polynomials:
General Multi-Party techniques can solve all computational problems, but, because a lot of dat operations concer the manipulation of polynomials, it is interesting to do them efficiently.
Efficient polynomial Operations in the Shared-Coefficients Setting,
P. Mohassel, M. Franklin,
- Diffie-Hellman and Logarithms in Abstract groups (Sori):
Some research in the Discrete Logarithm problem concerns approaches that are valid in all groups;
such algoritms cannot use the representation of group elements.
One important research question is, if breaking the Diffie-Hellman Key Exchange is equivalent to computation of Discrete Logarithms.
(Very mathematical topic!)
The Relationship between breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms,
Ueli Maurer and Stefan Wolf, 1999.
- Stream Ciphers: Grain (Zamarak):
Grain was a proposal for the eSTREAM competition.
What is this eSTREAM, what proposals are there?
How does Grain work, and why did the inventors consider it better than A5?
Is it safe?
Cryptanalysis of Grain,
C. Berbain, H. Gilbert, A. Maximov,
- Broadcast Encryption (Tamar):
We usually think of cryptography as protecting important secrets, but many applications of cryptography concern the protection of information that we want to be available.
Broadcast stations want as many as possible viewers to see their information, but they want them to pay for it.
What kind of encryption schemes are used in set-top boxes for pay TV?
How is key distribution and retraction arranged?
- Privacy of RFId systems (Roland):
How can Radio Frequent Identification techniques be used without intruding the privacy of users?
- Receipt-freedom in voting:
To guarantee that voters can express their preference freely, elections should be private.
But to also prevent enforcement or vote stealing, it should be prevented that a voter can prove afterwards what he voted, even if he wishes to do so.
In other words, the voter should not get a receipt of his vote (not even a secret one).
How important is Receipt-Freedom?
Is it a property of current voting systems?
Is Receipt-Freedom contradictory to other requirements that hold for voting?
How is Receipt-Freedom achieved?
Receipt-Free Universally-Verifiable Voting with Everlasting Privacy,
T. Moran, M. Naor,
LNCS4117 pp 373-392.
(See also Wagner on page 393.)
- Partially Blind Signature Schemes:
In a blind signature scheme, a key-holder cooperates in signing a message he does not know, without giving away his key.
Partially blind signature schemes were proposed as an ingredient for cash systems with e-coins in different nominations.
A break of the schema allows an attacker to replace bank notes of small value by notes of large value.
Cryptanalysis of a Partially Blind Signature Scheme or How to Make $100 Bills wit $1 and $2 Ones,
G. Martinet, G. Poupard, P. Sola,
- Phishing Problem (Geerten):
When the Dutch banks stimulate users to secure their computers better, the Phishing problem really appears to run out of hand.
Phoolproof Phishing Prevention,
B. Parno, C. Kuo, A. Perrig,
- Attacks Using Collision Search:
Collision search generalises a number of attacks,
such as meet-in-the-middle without storage,
birthday collisions for hash functions,
and logarithm computations.
The emphasis on parallelisation in the reference article
is perhaps a bit outdated...
or is it modern due to the uprise of multicore processors?
Parallel Collision Search with Cryptanalytic Applications,
P.C. van oorschot, M.J. Wiener.
- The Dutch OV-chipkaart (Marcel):
Dutch politicians debate the roll-out of the chipcard
following breaks reported by Nijmegen scientist.
Other countries are quite happy with the same Mifare chip.
What technique does the card use and how does the break work?
Can the OV-chipkaart be safely introduced?
- Road pricing:
Making people pay for the use of roads is recognized as a means
to reduce traffic jams and pollution.
Discuss the solutions for the accounting of road use.
The solutions must be safe and respect privacy.
- Biometry (Hannelore).
What is expected from you?
The classes and reading material for the course approach cryptography from the theoretic perspective.
In the project you are supposed to show, how it is brought into practice.
You can describe some on-going project or a developed product, or do a business-oriented case study to describe how a crypto application is rolled out in a big organisation.
You will have to study about 4 papers, and perhaps read newspaper articles or watch television shows, to appreciate the subject in general.
The product of past students can be seen in the collections produced during earlier incarnations of the course:
- Gerard Tel (ed.),
- Gerard Tel (ed.),
- Gerard Tel (ed.),
- Gerard Tel (ed.),
- Gerard Tel (ed.),
Cryptografie aan het Werk,
- Gerard Tel (ed.),
Cryptography in Context,