cryptopals

Solutions to all cryptopals problems: Sets 1-7, Set 8.

The only dependency on top of standard JRE 17 runtime is that on Lombok. The project runs on all subsequent versions of the Java platform such as Java 21 and Java 23.

Additional dependencies:

• Spring Boot 3.x for problems requiring a server side part in addition to a client part
• The GNU Multiple Precision Arithmentic Library (GMP) and the JNA-GMP wrapper for it for a more optimized implementation of modular exponentiation than that provided by BigInteger::modPow. This is relevant only for a few challenges starting with Challenge 48.
• GraalJS engine for Challange 50. In the past JRE provided a JavaScript engine called Nashorn, but this was discontinued in Java15.

How to run

The majority of the challenges of a set can be run by executing the com.cryptopals.Setx.main method of the set or by running the JUnit5 tests found under src/test/java/com/cryptopals/SetXTests. Required dependencies are defined in the project's pom.xml.

Some challenges (31, 32, 34, 35, 36, 37, 49, 57, 58, 59, 60, 66) require a server-side application. This can be produced with mvn install and executed with

java -jar cryptopals_server-0.2.0.jar

as a typical SpringBoot 3.x application. This application provides either a RESTful API or an RMI component depending on a challenge.

For the more advanced problems I created a proper explanation about the implementation of each of these attacks, which you can find in the Table of Contents below.

Table of Contents

• Set 6: RSA and DSA

  • Challenge 48. Bleichenbacher's PKCS 1.5 Padding Oracle (Complete Case)

• Set 7: Hashes

  • Challenge 52. Iterated Hash Function Multicollisions
  • Challenge 54. Kelsey and Kohno's Nostradamus Attack
  • Challenge 55. MD4 Collisions
  • Challenge 56. RC4 Single-Byte Biases

• Set 8: Abstract Algebra

  • Challenge 57. Diffie-Hellman Revisited: Small Subgroup Confinement
  • Challenge 58. Pollard's Method for Catching Kangaroos
  • Challenge 59. Elliptic Curve Diffie-Hellman and Invalid-Curve Attacks
  • Challenge 60. Single-Coordinate Ladders and Insecure Twists
  • Challenge 61. Duplicate-Signature Key Selection in ECDSA (and RSA)
  • Challenge 62. Key-Recovery Attacks on ECDSA with Biased Nonces
  • Challenge 63. Key-Recovery Attacks on GCM with Repeated Nonces
  • Challenge 64. Key-Recovery Attacks on GCM with a Truncated MAC
  • Challenge 65. Truncated-MAC GCM Revisited: Improving the Key-Recovery Attack via Ciphertext Length Extension
  • Challenge 66. Exploiting Implementation Errors in Diffie-Hellman

• Additional problems

Set 6: RSA and DSA

Challenge 48. Bleichenbacher's PKCS 1.5 Padding Oracle (Complete Case)

Challenge 48 is fairly straightforward to implement by following the steps in Section 3.1 Description of the Attack of Bleichenbacher's Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1 paper. An important observation is that thanks to Step 2c the attack runs in O(log(n)), where n is the size of the RSA modulus.

I created a helper class to aid this process. When following the paper, one needs to pay particular attention to rounding in all the equalities. For example I ended up waisting a lot of time with Inequality (2) in Step 2c:

2B + ri·n         3B + ri·n
--------- <= si < ---------    (2)
   b                 a

Initially I implemented it by letting si iterate from the lower bound until (not including) the upper bound. However that resulted in an incorrect implementation. The term on the right of Inequality (2) will most likely not be an integer value. Therefore, when computed using infinite precision integers, it will be less than its counterpart computed over reals. As a result the correct way to implement Step 2c is to let si go to (including) the upper bound when the upper bound is rounded down to an integer:

while (true) {
    BigInteger   lower = divideAndRoundUp(_2B.add(rn), interval.upper),
                 upper = _3B.add(rn).divide(interval.lower);
    for (BigInteger nextS=lower; nextS.compareTo(upper) <= 0; nextS = nextS.add(ONE)) {
        if (paddingOracle.test(pubKey.encrypt(nextS).multiply(cipherText)))  return  s = nextS;
    }
    rn = rn.add(pubKey.getModulus());
}

Practical optimization to tackle real world length RSA moduli

The challenge suggests to go all the way up to 768-bits moduli. With my first implementation using Java's BigInteger it takes about 30 seconds. Yet, in the real world such small RSA moduli are long a relic of the past. Trying to go for 1024-bits moduli and longer let the implementation spin for longer than I wanted to wait. To address that I switched to an optimized implementation of infinite precision integers based on The GNU Multiple Precision Arithmentic Library (GMP). Thanks to the JNA-GMP wrapper this was very easy to do. If you are on macOS, you probably already installed gmp when you installed Python with Homebrew.

With tiny changes to the RSAHelper and RSAHelperExt classes the speedup was remarkable. With GMP 6.2.0 I was able to go all the way to 2048-bits moduli within just a couple of minutes:

| RSA modulus size | Average duration of attack (20 tries) | | ---------------- |:-------------------------------------:| | 256 bits | 2 s 262 ms | | 768 bits | 7 s 207 ms | | 1024 bits | 19 s 271 ms | | 1536 bits | 39 s 213 ms | | 2048 bits | 1 m 54s 607 ms |

This difference between the performance of JRE's implementation of BigIntegers and that of GMP is quite remarkable and goes somewhat against Joshua Bloch's advice given in "Item 66: Use native methods judiciously" of his excellent "Effective Java, 3^rd edition" book. His reply to my tweet confirmed that.

/**
 * @param numBits  number of bits in each prime factor of an RSA modulus, i.e. the modulus is thus {@code 2*numBits} long
 */
@DisplayName("https://cryptopals.com/sets/6/challenges/47 and https://cryptopals.com/sets/6/challenges/48")
@ParameterizedTest @ValueSource(ints = { 128, 384, 512, 768, 1024 })
void  challenges47and48(int numBits)  {
    RSAHelperExt rsa = new RSAHelperExt(BigInteger.valueOf(17), numBits);
    BigInteger   plainText = RSAHelperExt.pkcs15Pad(CHALLANGE_47_PLAI