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

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.

Masaki TAKEDA,Takeshi HAMADE,Kazuyuki HISAMATSU,Toshinobu KANEKO,

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.