Common DSA key parameter generation follow FIPS 186-3, which requires (L, N) bits length for P and Q, where L is at least 1024 and N is at least 160. However, sometimes we may want non-FIPS (L, N), for example, to make the signature length less than 40 bytes. This post first investigate some possible solutions then introduces a smart way to generate non-FIPS DSA key parameters by hacking into the Go compiler source. Note: I am neither the expert of Go nor DSA! Happy hacking:)

0. Requirement

Say we want to generate DSA key parameters using (1024, 152) for P and Q (there is another long story why we want to do that:) Note that this does NOT follow FIPS 186-3, which requires Q at least 160 bits. However, this still follows the requirement of DSA key parameter generation, which requires only Q length <= data digest length. The security guarantee is reduced as well as the length of the final signature.

1. Python

The first thing I looked for was Python implementation (Yep, PyFan). There are 2 libs popped out from Google – PyCrypto and gdata-python-client. Interestingly, the 2 implementation of DSA are basically the same. Check out PyCrypto’s DSA implementation (https://github.com/dlitz/pycrypto/blob/master/lib/Crypto/PublicKey/_DSA.py). Function ‘generateQ‘, as it is named, assumes the default 160-bit seed to generate the 160-bit Q in a weird way (that I could not understand if this is the so called ‘random’). Even worse, function ‘generate_py‘, generating both P and Y, are tightly coupled with the number 160. And again, I doubt it would work if all ‘160’ are replaced with ‘152’ (in case I am wrong, please do let me know). Apparently, you have to understand it before you can change it.

2. Java

As Python was not that friendly and I am stupid, I referred to Java (this is the reason why I am stupid:) Look at Dr Yang’s DSA example (http://www.herongyang.com/Cryptography/DSA-Java-Generating-DSA-Key-Pair.html). The class we are looking for is ‘KeyPairGenerator‘, which is under ‘jdk/src/share/classes/java/security’ directory within the OpenJDK source code. Digging deeper, we will find the real DSA implementation is in ‘jdk/src/share/classes/sun/security/provider/DSAParameterGenerator.java‘. Moving on, check out method ‘generatePandQ‘ and you would not be surprised to see ‘160’ everywhere. Meanwhile, you can tell from the source code that the implementation follows FIPS step by step.

3. Go

Fortunately, I came across the Go DSA implementation within the compiler source before I had made up my mind to ‘understand’ PyCrypto. Check this out (http://golang.org/src/pkg/crypto/dsa/dsa.go). Oops, you do not know anything about Go? Neither do I! Look at function ‘GenerateParameters‘ – there is only one place where ‘160’ is used. So…

Daves-MacBook-Pro-2:dsa daveti$ diff dsa.go.orig dsa.go
43a44,45
> // daveti: hack
> L1024N152
62a65,68
> //daveti: hack
> case L1024N152:
> L = 1024
> N = 152
Daves-MacBook-Pro-2:dsa daveti$

The hack looks so elegant that we have to run some test to make sure it works indeed. Before this, let us build the Go compiler – src/all.bash. The hacked Go compiler locates under bin directory. Use the DSA application example here (https://www.socketloop.com/tutorials/golang-example-for-dsa-functions) and remember to replace the ‘L1024N160’ with ‘L1024N152’. It works like a charm and we do have a shorter DSA signature!

4. Summary

Finding the existing and popular implementation and hacking it is always a best solution given a task. It is time saving and it is fun. Even though I am not familiar with Go, it has become one of my hacking targets regarding its graceful design and implementation. When hacking Python or Java is not straightforward, try Go!