|
This article is about something basic, not something esoteric. Recently a problem was found in Open PGP, relating to both the Digital Signature Algorithm (DSA) and to RSA. You don't have to care about OpenPGP to care about this problem, because the problem is much more basic to cryptography and your privacy. This article explains the flaw, and gives you a Java cryptanalysis program so you can see and exploit it for yourself. Having actual code and program sample output is especially important as some may have problems following the mathematics of the exploit. The security of many things in cryptography, including, for example, digital cash, is related to the "discrete logarithm problem". This is a "hard" problem, and computer security and financial security are sometimes based on the fact no one has found an easy way to find discrete logarithms. But the forces of tyranny are not always stupid. They prefer to substitute easy problems for hard problems. In a recent article (http://zolatimes.com/V5.12/DMT_simple.html) I pointed out that the FBI got a court order to install a keystroke logger on Nicky Scarfo, Jrs' computer because they couldn't break Scarfo's PGP-encrypted files. It was easier to steal Scarfo's passphrase than to break his encryption. Now two Czech mathematicians have shown an easy way to tamper with DSA signatures by tampering with the parameters used in the signature. The details will be reviewed later but DSA signatures use three parameters p, g, q along with a public key y and a private key x. The method substitutes a faux p' and g' for the original p and g (see Vlastimil Klima and Tomas Rosa, "Attack on Private Signature Keys of the OpenPGP format, PGP programs and other applications compatible with OpenPGP". A copy of this paper in .pdf format can be found here.) Substituting the faux p' and g' is easy in the current OpenPGP format because there is no check on the validity of the parameters. So if you have a hex editor and access to a person's secret key ring, this part is trivial. After that, all you have to do is get the person to sign something and grab that, and then you can back out the person's private key x. This is possible, because with the faux parameters the discrete logarithm problem is no longer hard. (But you still have to do the calculations; that's why I'm writing this article.) The lesson is simple: if you have access to DSA parameters and can alter them, and then obtain a message signed with the faux parameters, you can steal a person's private key. This has implications beyond PGP or the US government's Digital Signature Algorithm, because DSA-type mathematics appears in many other contexts.
A Brief Review of DSAThe Java program below illustrates DSA using the Cryptix cryptography library (chiefly the DSA signature function). Now, technically, the exploit won't work with the Cryptix DSA signature function, because Cryptix does verify the parameters, at least to a certain extent. So I show how to calculate the same signature outside the Cryptix DSA signature function. The point of all this is to give a known and unambiguous context for doing the proper calculations, before we start with the faux parameters and faux signatures and the theft of secret keys. Those unfamiliar with the Cryptix library can review my Java encryption page (http://orlingrabbe.com/javacrypt_index.htm). Suppose you want to DSA-sign a message. You are given DSA parameters g, p, q. You take a hash h of the message. Then you produce two numbers (r and s) that are the signature. First, produce a random number k, 0<k<q, and calculate: r = (gk mod p) mod q. Now calculate the inverse of k: kInv = k-1 mod q. (This is the number such that k*kInv = 1 mod q.) Next, produce the number s, using the hash h and your secret key x: s = [kInv * (h + x*r) ] mod q. The two numbers (r,s) are the signature. To verify the signature, you start with the received message and the signature (r,s). You take the hash h' of the received message, then go through a series of calculations that begin with s. If the end result is r, the signature verifies. If the end result is some number other than r, the signature is not valid. The default parameters g, p, q, for Cryptix and the Sun Java libraries are (for 1024-bit encryption, and written in hexadecimal notation): |
|
g =
F7E1A085D69B3DDE CBBCAB5C36B857B9 7994AFBBFA3AEA82 F9574C0B3D078267 p =
FD7F53811D751229 52DF4A9C2EECE4E7 F611B7523CEF4400 C31E3F80B6512669 |
|
q = 9760508F15230BCC B292B982A2EB840B F0581CF5 Here g and p have 1024 bits, while q has 160 bits. They fulfill the requirement that gq = 1 mod p, and no lower power of g equals 1 mod p. (That is, g is a "generator" and q is the "order" of g with respect to p.) Necessarily, also, p = 1 mod q. The faux parameters the Czech mathematicians substitute for g and p are these: g' = 31AC85291FF814E6 25E4B88C8C5047A7 DB2F0E45 p' = 5380000000000000 0000000000000000 00000001 Here p' has 159 bits, while g' has 158 bits. |
|
Now, the reason this substitution won't work in the Cryptix DSA signature function is that the function checks to see if the number of bits in p is at least 512. So it won't accept p'. So in the program I calculate the signatures and verification independently, to get around this restriction, but only after demonstrating that these signing and verification procedures duplicate those in Cryptix. Also, the DSA signature produced with g', p'—denote it (r',s')—is not a valid signature. That is, taking a hash of the (unaltered) message, and then starting with s' and doing the correct calculations will not give you back r'. But this is not important, because the only reason for the false signature is to steal the secret key--and not to masquerade as a valid signature.
How to Steal the Secret KeyThe first thing to note about p' is the following: p' = t*2s + 1, where t = 167 and s = 151. Now, go back and review the DSA signature procedure. You first start with a random k, 0 < k < q. The first significant thing about the form p' takes is that, since s = 151, you can back out 151 bits of k mod 2s by looking at quadratic residues. Next, you need do not more than 167 calculations to determine the value of k mod t. (Well, that's approximately true. You don't actually determine a single k, but rather one of 4 possible k's.) Then, using the Chinese Remainder Theorem, you can determine k from k mod 2s and k mod t. The other three k's are determined as k+(p'-1), k+2*(p'-1), k+3*(p'-1). Once you've determined k, you just reverse the DSA signature mathematics and solve for x (one of four possible x's). The correct x, of course, is the one that gives the known public key y = gx mod p. In the sample computer output below, the 151 binary bits of k are shown as: k mod 2s =
10101010000100000110001110010010111000001100100100010001100110101100010 which translates into hexadecimal as: k mod 2s = 550831C9706488CD 629EA27210913A57 CC706F Then after 62 calculations, we find the value of k mod t = 62. The Chinese Remainder Theorem then gives us for the value of k: k = 0DD50831C9706488 CD629EA27210913A 57CC706F. However, calculating x and then y from this value of k does not yield the right public key. So next we try k+(p'-1): k+(p'-1) = 61550831C9706488 CD629EA27210913A 57CC706F, which yields the correct value for the private key x: x = 805C2D4BF743063C ABF060AD48E04BD6 813DA8B6.
Beware [?] of Figure 3The tricky part of the calculation is in determining k mod 2s; namely, the 151 bits, bit by bit. This is the only part of the attack for which Klima and Rosa provide pseudocode. However, their pseudocode (in Figure 3 in their Appendix) is erroneous (perhaps deliberately so).[Note added: Perhaps the error is mine: see the letter from Tomas Rosa and Vlastimil Klima following this article and preceding the Java source code. In any case . . .] The proper calculations are given in the code in my program below, namely the lines: |
|
// now set up routine to get the bits of k by looking at quadratic residues
p = pprime;
g = gprime;
BigInteger val, ival, TwoPower, PminusOne;
TwoPower = One;
v = p.subtract(One);
Bv = Zero;
PminusOne = p.subtract(One);
for(i=1;i<=151;i++) {
v = v.divide(Two);
yk = r.modPow(v,p);
if(yk.compareTo(One)==0) wk[i]= 0;
else wk[i]=1;
Ij = new Integer(wk[i]);
w = Ij.toString();
Bj = new BigInteger(w);
Bj = Bj.multiply(TwoPower);
Bv = Bv.add(Bj);
Ba = PminusOne.subtract(Bv);
f = g.modPow(Ba,p);
r=Bfirst.multiply(f);
r=r.mod(p);
TwoPower = TwoPower.multiply(Two);
}
for(i=151;i>=1;i--) output.print(wk[i]);
|
|
General Comments on the ProgramEach time the Java program is run, it uses the same parameters p, g, q, but produces a different private key x and public key y. Both the private key x and the public key y are printed out for reference. (This is the same "unknown" private key which the program finds later through the faux signature.) The program reads in a file called data, does a SHA1 hash of the file, and signs this hash, producing the signature (r,s). Later on, the program uses the faux p', g' to sign this hash value again. That is, the "message" that is captured after the faux parameters are substituted is just the same hash value as before, but this time signed with the faux parameters to produce the faux signature (r', s'). The SHA1 hash of the sample file data is h = 1A01B56EB33FA84A 39EEDDD927977726 38331E94. This is the hash value under Windows, which includes an end-of-file marker. (For a listing of the bytes being hashed, see my "Digital Signatures Illustrated" (http://orlingrabbe.com/digsig.htm). A Linux file will hash differently. The program generates its own random bytes for the DSA signature, including the faux signature, which in the sample given are 61550831C9706488 CD629EA27210913A 57CC706F This is the second of the four possible values for k later backed out in the cryptanalysis section. Since the associated calculated value for x gives the correct public key y, the program stops, after printing out the real value of x (created in the early part of the program) for comparison.
Comment on Java and Cryptix VersionsThe program compiles and runs without errors. I am using Cryptix 3.1 and running Java 1.2.2. Most of the programs on my Java crypto page were written under Java 1.1.7b, but basically run under Java 1.2.2 with no changes, provided you run the programs with oldjava.exe. (Otherwise, in some cases, there are conflicts with the java.security.interfaces module, or something similar.) That is, to compile and run testDES.java under Java 1.2.2 you would enter the commands:
javac testDES.java The current program pgp_dsa_flaw.java, however, was written under Java 1.2.2 and compiles and runs in the normal fashion:
javac pgp_dsa_flaw.java where data is the name of the input file to be signed. A text copy of the file data may be found here. A text file of the java program (listed below on this html page) may be found here. Sample output is given after these listings. |