Saturday, August 16, 2014

Performance of RSA vs. DES


Choice of encryption algorithm matters. "In software, DES is about 100 times faster than RSA. These numbers may change slightly as technology changes, but RSA will never approach the speed of symmetric algorithms". [1]

DES can be cracked with brute force in hours but for our application that needs to encrypt a nonce to check the integrity of the conversational state, that's good enough security. So, it looked like it was worth investigating a change of algorithm.

"DES is a symmetric algorithm: The same algorithm and key are used for both encryption and decryption" [1]. AS a result, the means of getting a key are slightly different to getting an RSA private/public key pair:

    KeyGenerator keyGenerator   = KeyGenerator.getInstance("DES");
    SecretKey    secretKey      = keyGenerator.generateKey();

But using the cipher is pretty similar:

    Cipher cipher        = Cipher.getInstance("DES/ECB/PKCS5Padding");
    cipher.init(ENCRYPT_MODE, secretKey);
    byte[] encrypted     = cipher.doFinal("hello world".getBytes());

The performance improvements were dramatic, even better than Schneier's estimate. To measure them, I used the Java Microbenchmark Harness. To allow your project to use JMH, you need Maven and a pom.xml that looks a little like this below (my version of Eclipse - Kepler SR2 - auto-generated it for me but my work computer couldn't seem to as it didn't have the relevant Maven archetype so I'll include my pom.xml explicitly here):

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.phenry</groupId>
    <artifactId>microbenchmarks</artifactId>
    <version>0.0.1-SNAPSHOT</version>
    <packaging>jar</packaging>

    <name>Auto-generated JMH benchmark</name>

    <prerequisites>
        <maven>3.0</maven>
    </prerequisites>

    <dependencies>
        <dependency>
            <groupId>org.openjdk.jmh</groupId>
            <artifactId>jmh-core</artifactId>
            <version>${jmh.version}</version>
        </dependency>
        <dependency>
            <groupId>org.openjdk.jmh</groupId>
            <artifactId>jmh-generator-annprocess</artifactId>
            <version>${jmh.version}</version>
            <scope>provided</scope>
        </dependency>
   <dependency>
     <groupId>junit</groupId>
     <artifactId>junit</artifactId>
     <version>4.8.1</version>
     <scope>test</scope>
   </dependency>
    </dependencies>

    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <jmh.version>0.9.4</jmh.version>
    </properties>

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>3.1</version>
                <configuration>
                    <compilerVersion>1.6</compilerVersion>
                    <source>1.6</source>
                    <target>1.6</target>
                </configuration>
            </plugin>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-shade-plugin</artifactId>
                <version>2.2</version>
                <executions>
                    <execution>
                        <phase>package</phase>
                        <goals>
                            <goal>shade</goal>
                        </goals>
                        <configuration>
                            <finalName>benchmarks</finalName>
                            <transformers>
                                <transformer implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
                                    <mainClass>org.openjdk.jmh.Main</mainClass>
                                </transformer>
                            </transformers>
                        </configuration>
                    </execution>
                </executions>
            </plugin>
        </plugins>
        <pluginManagement>
            <plugins>
                <plugin>
                    <artifactId>maven-clean-plugin</artifactId>
                    <version>2.5</version>
                </plugin>
                <plugin>
                    <artifactId>maven-deploy-plugin</artifactId>
                    <version>2.8.1</version>
                </plugin>
                <plugin>
                    <artifactId>maven-install-plugin</artifactId>
                    <version>2.5.1</version>
                </plugin>
                <plugin>
                    <artifactId>maven-jar-plugin</artifactId>
                    <version>2.4</version>
                </plugin>
                <plugin>
                    <artifactId>maven-javadoc-plugin</artifactId>
                    <version>2.9.1</version>
                </plugin>
                <plugin>
                    <artifactId>maven-resources-plugin</artifactId>
                    <version>2.6</version>
                </plugin>
                <plugin>
                    <artifactId>maven-site-plugin</artifactId>
                    <version>3.3</version>
                </plugin>
                <plugin>
                    <artifactId>maven-source-plugin</artifactId>
                    <version>2.2.1</version>
                </plugin>
                <plugin>
                    <artifactId>maven-surefire-plugin</artifactId>
                    <version>2.17</version>
                </plugin>
            </plugins>
        </pluginManagement>
    </build>

</project>

Your code now needs a minimum of the @Benchmark annotation like this:

    @Benchmark
    public byte[] decrypt() throws Exception {
        cipher.init(DECRYPT_MODE, secretKey);
        return cipher.doFinal(encrypted);
    }

You don't need to return anything but I did for the sake of the my unit tests.

There are many ways to run your benchmark but the one I quite like looks something like this:

$ mvn clean install && java -jar target/benchmarks.jar ".*CryptoBenchmarks.*" -wi 4 -i 20 -f 1 -bm avgt -tu ns

where wi is the number of warm-up iterations, i is the number of actual iterations for the test, f is the number of times we fork for a particular iteration and tu is time units (here it is nanoseconds). The options can be found in the CommandLineOptions class. The -bm switch is the benchmark mode and options can be found in the Mode class where here we're asking it to measure the average times.

Note: you'll need to add a main method to your classes.

The output for my comparison of RSA and DES looked like this:

Benchmark                                                      Mode   Samples        Score  Score error    Units
c.p.m.RsaCryptoBenchmarks.decryptionUsingPrivateKey            avgt        20  6257593.175   197497.265    ns/op
c.p.m.RsaCryptoBenchmarks.encryptionUsingPublicKey             avgt        20   203438.819     2428.467    ns/op
c.p.m.DesCryptoBenchmarks.decrypt                              avgt        20      672.128       40.558    ns/op
c.p.m.DesCryptoBenchmarks.encrypt                              avgt        20      731.335       57.101    ns/op


So, encryption is roughly 1000 times more expensive in RSA and decryption 10 000.

[1] Applied Cryptography, Bruce Schneier.

No comments:

Post a Comment