Applied Crypto Challenge Problems

These cryptanalysis challenge problems are designed to complement the material in the textbook Applied Crytanalysis: Breaking Ciphers in the Real World, by Stamp and Low (published by Wiley-IEEE Press, 2007). Source code (in C) for most of the ciphers mentioned below can be found here. These programs were used to generate the ciphertext for the challenge problems presented on this page. Note that source code is not provided for the MD4 or MD5 hash functions, since such code is readily available online.

Each problem includes a rating from 1 (easiest) to 10 (hardest), except for research problems, which are given a rating of 11. The problems rated 11 are, we believe, difficult research problems, but our ratings for the non-research problems are only guesses, which may be wildly inaccurate. In comparison, the more difficult problems in the text would rate about a 2 or 3.

Each problem also includes its status, which we will strive to keep up-to-date. Typically, the status will be either "open" or "solved", but some problems may be partially solved, and we may note in some case. We intend to post solutions (with the solvers' permission, of course), if and when they become available.

Few of the problems here are straightforward implementations of the attacks described in our book—if you want such problems, they are easy enough to generate. Instead, these problems generally include some twist on the basic attack. Note that for each encryption problem below, the plaintext is English, in the form of ASCII text. Finally, new problems may be added from time to time. Any new problems will be appended to the list so that the numbering of the current problems will remain consistent.

Challenge Problems

1. (Rating: 4, Status: open) Decrypt the ciphertext message found here and recover the key. This message was encrypted using a simple substitution, where, in general, more than one ciphertext symbol is used to represent a given plaintext symbol. The plaintext is English and the 65 distinct ciphertext symbols (denoted 1 thru 65) represent the 26 letters. That is, the plaintext consists only of the 26 letters, without spaces or punctuation. This problem was inspired by the unsolved "Zodiac 340-cipher" (see the next problem).
   
   
2. (Rating: 11, Status: open) In the late 1960's a serial killer who called himself "The Zodiac" brutally murdered at least five people in the San Francisco Bay Area. The Zodiac, who was never apprehended, sent several taunting letters to newspapers and police, some of which included encrypted messages. Three of the Zodiac's ciphertexts were quickly broken but one 13-character message and one 340-character message remain unsolved to this day. Solve the Zodiac 340-cipher, or provide strong evidence that it is not ciphertext, or not solvable under reasonable assumptions on the method of encryption. For example, since the solved Zodiac ciphers used a simple substitution, you might reasonably assume this message was encrypted using a simple substitution. Under this assumption, if you are able to generate several different plausible "plaintext" messages that are consistent with the ciphertext, then it would not be possible to provide a "correct" decryption, assuming that a simple substitution (or more general substitution technique) was actually used.
   
   
3. (Rating: 4, Status: open) Recover the key and plaintext corresponding to the Enigma-encrypted ciphertext found here. There are 5 rotors and 2 reflectors available, and their wirings match those of the rotors and reflectors in our simulator. The stecker has no cables connected and the movable ring is in the same fixed position as in our simulator. Consequently, the unknown key consists of the selection of rotors, the selection of the reflector, and the initial position of each of the 3 rotors. Hint: The plaintext is from an English novel, but it may not be entirely straightforward to automatically recognize it as such.
   
   
4. (Rating: 4, Status: open) The ciphertext here was generated using the Enigma cipher. Rotors number 1, 2, and 3 from our simulator are the L, M, and R rotors, respectively, reflector B was used, and the movable ring is in the same fixed position as in our simulator. Determine the initial settings for the rotors and the stecker and decrypt the message. Hint: The stecker uses 8 cables.
   
   
5. (Rating: 5, Status: open) This ciphertext was created using the Purple cipher, where the switch wirings are the same as those in our simulator. Your challenge, should you choose to accept it, is to recover the key and decrypt the message. Note that the key consists of the plugboard settings, the order of the fast, medium, and slow switches, and the initial switch positions. For this message, the input plugboard setting is the same as the output plugboard setting.
   
   
6. (Rating: 6, Status: open) The ciphertext here was encrypted with the Sigaba cipher. For this ciphertext, the rotor wirings are the same as given in the Sigaba simulator we have provided. In addition, the cipher and control rotor initial settings are ABCDE and ZYXWV, respectively, and the index rotor order is 01234. The unknown key consists of the order of the 10 cipher/control rotors, the orientation of each of these 10 rotors, and the initial setting of each of the 5 index rotors. The first six letters of the corresponding plaintext are available here. The challenge is to recover the unknown key and decrypt the message.
   
   
7. (Rating: 11, Status: open) The ciphertext here was encrypted with the Sigaba cipher. The initial segment of the corresponding plaintext is available here. Recover the key and decrypt the message. Note that the full practical World War II keyspace was used, which implies a keyspace of size 2^95.6. The rotor wirings are those that appear in the Sigaba simulator that we have provided.

   A not-quite-practical attack on the full keyspace is outlined in Section 2.4.3 of the text. More details regarding this attack are provided in the paper, SIGABA: Cryptanalysis of the Full Keyspace, which will appear (or "appeared", depending on when you read this) in Cryptologia, July 2007, and can also be found here.
   
   

8. (Rating: 11, Status: open) Develop an efficient algorithm to compute the k-error linear complexity of binary sequences of arbitrary period length. For binary sequences of period 2ⁿ an efficient algorithm is given here and efficient algorithms exist for a few other special cases, but no efficient algorithm for the general case is known.
   
   
9. (Rating: 7, Status: open) This challenge deals with the ORYX stream cipher. Here, we give three initial keystream segments, the first of which was generated using standard ORYX (with the L permutation given), the second was generated with ORYX with the L permutation equal to the identity, and the third was generated with ORYX using an unknown L permutation. The key is different in each case. The challenge is to recover the three 96-bit keys.
   
   
10. (Rating: 4, Status: open) The ciphertext found here was encrypted using PKZIP. The first 12 bytes of plaintext, as a string (i.e., ASCII representation), are given here. Decrypt the message and recover the key.
    
    
11. (Rating: 8, Status: open) In this article, Schneier claims that 40 to 80 known plaintext blocks suffice to break the CMEA cipher. Here, we put this claim to the test. We have created CMEA-encrypted ciphertext messages with 100, 90, 80, 70, 60, 50, and 40 known plaintext blocks. The corresponding initial known plaintext blocks can be found here: 100, 90, 80, 70, 60, 50, and 40. The challenge is to decrypt each of these messages and recover each 64-bit key. In all cases, a 3-byte block size was used.
    
    
12. (Rating: 7, Status: open) Recall that the Akelarre cipher uses a 128-bit block size, with a variable-length key and a variable number of rounds. The ciphertext here was encrypted using Akelarre, with 4 rounds and a 128-bit key. The first 5 corresponding plaintext blocks can be found here. As is the case for all of these challenge problems, the underlying plaintext is English, in the form of ASCII text. Decrypt the message and recover as much of the key as possible.
    
    
13. (Rating: 3, Status: open) For this problem define h(x) to be the MD4 hash of x, truncated to 48 bits. Implement Yuval's digital signature attack (see Section 5.2.3 of the text), where the "innocent" message has the same meaning as the message found here and the "evil" message has the same meaning as the message here. That is, the challenge is to generate two meaningful messages, a message E with the same meaning as the given evil message and an innocent message I with the same meaning as the given innocent message, such that h(E) = h(I).
    
    
14. (Rating: 6, Status: open) For this problem, let h(x) be the MD4 hash of x, truncated to 70 bits. Implement Kelsey and Kohno's Nostradamus attack for the hash function h. To get credit for solving this challenge, you will need to "predict" the future by providing the hash of the close of the S&P 500 index for some specified date in the future. To validate your predictive powers, soon after the specified date has passed, you must provide a message that begins with the correct S&P 500 index and your prediction must hash to your pre-specified hash value. For simplicity, we do not require that the part of the message that follows your prediction is sensible.
    
    
15. (Rating: 11, Status: open) Implement the Nostradamus attack on a 128-bit hash, such as MD4 or MD5. The rules for this challenge are the same as for the previous problem.
    
    
16. (Rating: 3, Status: open) Write a program to generate meaningful MD4 collisions and give an example of the results.
    
    
17. (Rating: 5, Status: open) Consider the MD4 attack discussed in the text. Recall that the intermediate values generated by the hash algorithm applied to the message M are denoted by Q₀ through Q₄₇. Suppose that the intermediate hash values Q₁₄ through Q₁₉ are given by the values found here, where we use the notation Q[i] instead of Q_i.

    The challenge is to find a pair of message M and M' (in 32-bit hexadecimal block format) such that M has the specified Q values under the MD4 hash, and h(M) = h(M'), where h is the MD4 hash function. Note that the solution is not unique.

    This problem was created by Thang Dao and Jung Chang.
    
    

18. (Rating: 11, Status: open) Find another useful output differential for the MD5 attack. That is, your output differential must be distinct from Wang's but also lead to a viable attack.
    
    
19. (Rating: 7, Status: open) In Section 5.4.7 of the text, it is shown that a meaningless MD5 collision can be used to generate a collision for two postscript files which display very different text. It is also possible, although more difficult, to use a meaningless MD5 collision to generate collisions for PDF files. The PDF files found here and here display very different text, but they have the same MD5 hash. These colliding PDF files were generate by Da Lin and Nirmaladevi Rajaram.

    Your challenge is to develop a general technique to automatically create such colliding PDF files, given a meaningless MD5 collision and two arbitrary (non-colliding) PDF files as input.
    
    

20. (Rating: 8, Status: open) The challenge here is to develop an attack analogous to that described in the previous problem, but for a file format which has not yet been successfully attacked. As far as we are aware, only postscript and PDF files have been successfully attacked. It should be possible to attack other file formats, such as Word and TIFF.
    
    
21. (Rating: 6, Status: Solved by Steffen Rumpf [steffen.rumpf@student.uni-siegen.de], under the supervision of Bernhard Esslinger, November 2007) Bleichenbacher has given a signature forgery attack on certain incorrect implementations of RSA. The signature and verification work as follows. Let M be the message, N the RSA modulus and d the private key. Then the signature is computed as
    
    S = (padding || h(M))^d (mod N)
    
    where h is a cryptographic hash function, "||" is concatenation, and the padding is known. The verification consists of computing S^e(mod N), which yields the string (padding || h(M)), from which h(M) is extracted. The received message M is then hashed and if it agrees with the extracted h(M), the signature is accepted.

    Some implementations fail to check whether h(M) is the last element in the string obtained from S^e(mod N). If a common exponent of e = 3 is used, an attacker can take advantage of this error as follows. First, the attacker generates a desired message M' and computes h(M'). By carefully choosing a garbage value, the attacker can create the "signed" message
    
    S' = (padding || h(M') || garbage)^d (mod N)
    
    and the victim will then verify the "signature" on M'. See this brief note for more details. Amazingly, a valid (M,S) pair is not required for this attack. The attack is also independent of the actual value of the modulus—we only need to know the number of bits in N.

    The challenge is to forge a signature for this message, assuming that a common encryption exponent of e = 3 is used, the modulus is 3072 bits, the padding is this value (in hex), and the hash function is SHA-1.

    This problem was created by Jeet Morparia and Neel Parikh.