Title: Differential Power Analysis
Description:
Differential power cryptanalysis has been invented in 1998 by a group of researchers from Cryptography Research, Inc., led by an inventor of timing cryptanalysis Paul Kocher. As of today, these attacks are successful against majority of cryptographic tokens available on the market, including all types of smart cards, PCMCIA cards and cryptographic buttons, and no effective countermeasure has been developed, yet. The only effective defense is the physical protection, as the attack requires an access to a cryptographic token with secret parameters, such as a cryptographic key, stored on. No tamper-resistant covers seem to prevent analysis. The attack is based on sampling the power consumption of the device for a series of cryptographic transformations involving hundreds to thousands of random ciphertexts, and then performing a statistical analysis, leading to a full recovery of the key. Reconstructing the full secret or private key takes no more than several minutes, and requires only standard readily-available measurement equipment worth a few hundred to a few thousand dollars. Your task would be to fully understand the attack, show how it can be applied to symmetric ciphers such as triple DES, IDEA, and RC5, and to analyze possible countermeasures.
Literature:
Description:
Bruce Schneier in his book "Applied cryptography" states that if a software security program proclaims that it has a "proprietary" encryption algorithm - significantly faster than DES - the odds are that it is some variant of Vigenere polyalphabetic cipher. Cryptanalysis of the Vigenere cipher is believed to take only few seconds with a computer. The algorithm for breaking the cipher is based on so called "index of coincidence," and is very well described in the literature. Your task is to implement this algorithm, test it, and then try to apply your program to files encrypted using Word Perfect, Lotus 1-2-3, etc. Additional task would be to create an updated list of applications such as Word Perfect, etc. that still use a "proprietary" algorithm based on Vigenere cipher (see the catalog of Access Data [2] for a couple of likely candidates).
Literature:
Description:
In December 1995, Paul C. Kocher, a 22-year old independent cryptography consultant from Stanford, CA, released a draft version of his paper warning vendors and users of two most widespread public key cryptoalgorithms, RSA and DSS, about the attack he devised. The attack works under the condition that the intruder can measure the amount of time used to complete cryptographic operations. Extra computations necessary to mount the attack take time proportional to the number of bits of the operands, leading to a full recovery of a secret (private) key in less then one hour for practical operand lengths. Paul is working on a complete implementation of his idea, but he already presented his preliminary results at the RSA Data Security and CRYPTO conferences in 1996. His attack got the recognition of the most respected cryptographers, including the authors of the RSA cryptosystem. The countermeasure eliminating the threat of this attack is currently being added to software products sold by RSA Data Security Inc., it is however not obvious how to protect all implementations of the RSA and DSS against timing attacks. Your task is to implement the attack for a selected implementation of the RSA available in a public domain (RSAREF library, PGP, or PEM) on the basis of Kocher's preliminary papers. Additional tasks could be to analyze possible countermeasures, and find the dependence between the difficulty of the attack and the algorithm for modular multiplication used in the implementation of the cryptoalgorithm.
Literature:
e-mail: pck@cryptography.com
address: P.O. Box 8243, Stanford, CA, 94309, USA
Prerequisites: C in UNIX environment, basics of probability theory
Description:
Security of the RSA cryptosystem is based on the difficulty of finding prime factors of large numbers. Therefore, RSA Data Security, Inc., which holds a patent for RSA, organizes a Factoring Challenge. Fifty one integer numbers, in the range from 100 to 500 decimal digits, were generated by choosing two primes at random and multiplying them together, according to the rules used in the RSA cryptosystem. Prime factors were afterwards destroyed. Anybody, who is able to factor a smallest (!) unfactored number from the list, receives an award. If there are no successful attempts within a given quarter, the award accumulates. The largest number from the list factored so far had 130 decimal digits. Computations are performed simultaneously by many volunteers from all over the world who use spare time of their machines to complete initial, most time-consuming, phase of the algorithm. Obtained partial results are send over the Internet to one place, where the final result is calculated. Two fastest algorithms devised to date are: Quadratic Field Sieve (QFS) and Number Field Sieve (NFS). The latter is more efficient for numbers greater than 100 decimal digits, but its idea and implementation is more complicated. Your task is to get familiar with one of these algorithms and implement it. An additional task is to get familiar with public domain implementation of the program for factorization of large numbers, and associate different parts of its code with particular phases of the algorithm.
Literature:
Basic:
Description:
RC5 is a new block cipher devised by Ron Rivest - one of the inventors of the RSA cryptosystem - as an alternative for the old American standard DES. The cipher has a variable key size, and a variable input/output block size. Variable key length permits RC5 to be exported abroad, but only under the condition that the key size is less or equal to 40 bits. Such a small key length, may make the cipher vulnerable to the exhaustive key search attack. Your task is to design at the logic level the RC-5 breaking machine, and to estimate the number of chips that are necessary to break a single key within one hour. You can follow the design and cost estimates for the DES breaking machine devised by Michael Wiener [5]. Basic operations of the RC5 are: XOR, rotation, and addition.
Literature: