projects
Final Projects

These will be cryptanalytic assignments and challenges. Attacks on both classic and modern ciphers. Basic programming skills will be a benefit, but there will be final projects for a pen and paper analysis as well. Please write your final paper in Latex or HTML (in English), so that we can place it on this site for everybody's benefit.

Cryptanalysis of Classical Ciphers

1. Analysis of a grille cipher (the best possible attack, given a single block of ciphertext, two blocks, etc.).  Try to show that arbitrary-size grilles are breakable in real time. Use 16-24-32 size grilles as a starting point.

2. Analysis of a grandpre cipher. Minimize the amount of text needed for attack.

Cryptanalysis of Modern Ciphers
For those of you who want to try real life ciphers:
(in the order of decreasing interest, Breaking the number of rounds shown in brackets would be an interesting result). The project can consist in understanding and implementation of an attack from some recently published research papers (to have some deterministically doable part)

• RC4 (with less than 2^32 bytes of known stream) (it is possible to find a distinguisher). Attack variant with intial values: i=0, j =1. Want to know who uses RC4? If you are in Netscape click on: Security/Navigator/Configure SSL v3 and see what ciphers you can use in your browser.
• SERPENT (8 -12  rounds) (see AES for attacks, try to improve them)
• RIJNDAEL (8 rounds) (see AES for attacks, try to improve them)
• IDEA (5 rounds) See this paper for attack on 4.5 rounds.
• LUCIFER (8-16 rounds) as given in IBM technical report from 1970. This is a straightforward application of differential and linear methods. Analysis of a reduced variant is given in Biham-Shamir's book.
• SKIPJACK (32 rounds) You can analyze variants without counters or with fewer rounds. See this paper for latest attack (here are some more results). It is possible to improve results for 20-24 round variants. Find a large class of weak keys for a variant without counters.
• MISTY (8 rounds) (see Matsui's paper in FSE'99 proceedings; here is the same  paper from Mitsubishi site [not password protected]).
• TEA (16-32 rounds) Find best differential attack, see if you can make slide attack work.
• RC5 (12-14 "double" rounds) Implement attack on RC5-XOR, apply attack from this paper  to 128-bit version (a direct translation of ideas). Try to find better differentials (it is possible).
IDEA and RC5 are briefly described in Chapter 7 of the Handbook of Applied Cryptography.   Implementations of these algorithms can be found here: library of crypto algorithms.

Design of ciphers with trapdoors.
Try to break proposals given in the papers below (it is possible). Find new ways to set a trapdoor in a block cipher.

V. Rijmen and B. Preneel, A family of trapdoor ciphers [on-line], Fast Software Encryption, LNCS 1267, E. Biham, Ed., Springer-Verlag, 1997, pp. 139-148.

J. Patarin and L. Goubin, Asymmetric Cryptography with S-Boxes,
In Proceedings of ICICS'97, Springer, Lecture Notes in Computer Science, Vol. 1334,  November 1997, pp. 369-380.

And other references.

Study of New Methods of Cryptanalysis
1.  Implement Differential Linear attacks on DES and FEAL. Improving results for 10-round DES would be interesting.
Susan K. Langford, Martin E. Hellman, Differential-linear Cryptanalysis.
See description of this method in this thesis [on-line].

2. Multiple linear approximations.
Similarly to differential cryptanalysis where one can benefit from studying differentials instead of specific patterns/characteristics in linear cryptanalysis one can use several multiple linear approximations.

Kaliski, B. S. and Robshaw, M. J. B., Linear cryptanalysis using multiple approximations, Crypto '94.

Linear Cryptanalysis by Linear Sieve Method

3. High-order and interpolation differential cryptanalysis.
L. Knudsen and T. Jakobsen, The Interpolation Attack on Block Ciphers, Proc. Fast Software Encryption '97.

Thomas Jakobsen
Cryptanalysis of Block Ciphers with Probabilistic Non-linear Relations of Low Degree, LNCS 1462, p. 212 ff.

Takeshi SHIMOYAMA,Shiho MORIAI,Toshinobu KANEKO,Shigeo TSUJII,
Improved Higher Order Differential Attack and Its Application to Nyberg-Knudsen's Designed Block Cipher

L. Knudsen, Truncated and Higher Order Differentials.
Fast Software Encryption - Second International Workshop, Leuven, Belgium, LNCS 1008, pp. 196-211, Springer Verlag, 1995.
Other references.

4. Method: Impossible differentials
Eli Biham, Alex Biryukov, Adi Shamir,
Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials,
EUROCRYPT'99.

Eli Biham, Alex Biryukov, Adi Shamir,
Miss in the Middle Attacks on IDEA, Khufu and Khafre,
FSE'99.

5. Method: Boomerang  attack
D. Wagner, The Boomerang Attack, FSE '99.

S. Vaudenay,
Provable Security for Block Ciphers by Decorrelation
In STACS'98, Paris, France, Lecture Notes in Computer Science No. 1373, pp. 249-275, Springer-Verlag, 1998.

6. Method: Pseudo-Keys
Lars Knudsen, John Mathiassen,
A Chosen-Plaintext Linear Attack on DES, FSE'00. (Ask me for this paper it is not on-line yet.)

7. Method: Non-linear approximations
L. Knudsen and M. Robshaw, Non-linear Approximations in Linear Cryptanalysis, Advances in Cryptology -- Proc. EUROCRYPT'96, LNCS 1070, Springer Verlag, 1996, pp. 224-236.

Takeshi Shimoyama and Toshinobu Kaneko, Quadratic Relation of S-box and Its Application to the Linear Attack of Full Round DES, LNCS 1462, Springer-Verlag, Crypto'99, 1999.

Auxiliary  Cryptanalytic Techniques
1. Implement a search for best differential/linear patterns.
Prove that currently known patterns for DES and FEAL are best possible.  One of the on-line references is this paper:
Kazumaro Aoki, Kunio Kobayashi2, and Shiho Moriai, Best Differential Characteristic Search of FEAL, FSE'97.

2. "Good" S-box generation.
As one task: generate 4x6 S-boxes that satisfy DES design criteria.
(this is probably a 25% project)

2. Analysis of the Enigma cipher (implementation of the "Bomb"). A survey of all the cryptanalytic ideas around
the Enigma cipher. New attacks on Enigma? You are very welcome. It looks more like a large homework than a final project.
Thus it is whitened for a while.

4. Design a cipher? Hmm.. Ok, the deadline for cipher applications will close one month before the end of the
semester. You must provide design principles and your best security estimate for your submission. The cipher
will then be subject to public scrutiny of the people of the course. Anybody finding an attack significantly better
than the one you knew about will get bonus points. There will be  strict rules for the cipher design which will be
published later. I suggest you make your decision on this after we'll have a cipher contest in the mid-term of
this course.

Details on these and other projects will appear later on this page. If you will be interested in one of the projects that will be
listed here mail   to get more info. Kol' ha kodem zohe (The first who comes will take it!) However, note that these are
by far not all the project topics, just a sample of a few.