1 # DSA 2 3 [TOC] 4 5 The digital signature algorithm (DSA) is one of three signature schemes 6 descripted in the digital signature standard [DSS]. 7 8 ## Key generation 9 10 4.2 Selection of Parameter Sizes and Hash Functions for DSA 11 The DSS specifies the following choices for the pair (L,N), 12 where L is the size of p in bits and N is the size of q in bits: 13 14 L | N 15 ---:|----: 16 1024| 160 17 2048| 224 18 2048| 256 19 3072| 256 20 21 The tests expect the following properties of the parameters used during 22 key generation: 23 24 * If only the parameter L is specified by the caller then N should be one 25 of the options proposed in [DSS]. 26 * If no size is specified then L should be at least 2048. This is the minimal 27 key size recommended by NIST for the period up to the year 2030. 28 29 ## Signature generation 30 31 The DSA signature algorithm requires that each signature is computed with a new 32 one-time secret k. This secret value should be close to uniformly distributed. 33 If that is not the case then DSA signatures can leak the private key that was 34 used to generate the signature. Two methods for generating the one-time secrets 35 are described in FIPS PUB 186-4, Section B.5.1 or B.5.2 [DSS]. There is also the 36 possibility that the use of mismatched implementations for key generation and 37 signature generation are leaking the private keys. 38 39 ## Signature verification 40 41 A DSA signature is a DER encoded tuple of two integers (r,s). To verify a 42 signature the verifier first checks $$0 < r < q$$ and $$0 < s < q$$. The 43 verifier then computes: 44 45 $$ 46 \begin{array}{l} 47 w=s^{-1} \bmod q\\ 48 u1 = w \cdot H(m) \bmod q\\ 49 u2 = w \cdot r \bmod q\\ 50 \end{array} 51 $$ 52 53 and then verifies that \\(r = (g^{u1}y^{u2} \bmod p) \bmod q\\) 54 55 ## Incorrect computations and range checks. 56 57 Some libraries return 0 as the modular inverse of 0 or q. 58 This can happen if the library computes the modular 59 inverse of s as \\(w=s^{q-2} \mod q\\) (gpg4browsers) of simply 60 if the implementations is buggy (pycrypto). if additionally to such 61 a bug the range of r,s is not or incorrectly tested then it might 62 be feasible to forge signatures with the values (r=1, s=0) or (r=1, s=q). 63 In particular, if a library can be forced to compute \\(s^{-1} \mod q = 0\\) 64 then the verification would compute \\( w = u1 = u2 = 0 \\) and hence 65 \\( (g^{u1}y^{u2} \mod p) \mod q = 1 .\\) 66 67 ## Timing attacks 68 69 TBD 70 71 # Some notable failures of crypto libraries. 72 73 ## JDK 74 75 The jdk8 implementation of SHA1withDSA previously checked the key size as follows: 76 77 ```java 78 @Override 79 protected void checkKey(DSAParams params) 80 throws InvalidKeyException { 81 int valueL = params.getP().bitLength(); 82 if (valueL > 1024) { 83 throw new InvalidKeyException("Key is too long for this algorithm"); 84 } 85 } 86 ``` 87 88 This check was reasonable, it partially ensures conformance with the NIST 89 standard. In most cases would prevent the attack described above. 90 91 However, Oracle released a patch that removed the length verification in DSA in 92 jdk9: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/edd7a67585a5 93 https://bugs.openjdk.java.net/browse/JDK-8039921 94 95 The new code is here: 96 http://hg.openjdk.java.net/jdk9/dev/jdk/file/edd7a67585a5/src/java.base/share/classes/sun/security/provider/DSA.java 97 98 The change was further backported to jdk8: 99 http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/rev/3212f1631643 100 101 Doing this was a serious mistake. It easily allowed incorrect implementations. 102 While generating 2048 bit DSA keys in jdk7 was not yet supported, doing so in 103 jdk8 is. To trigger this bug in jdk7 an application had to use a key generated 104 by a third party library (e.g. OpenSSL). Now, it is possible to trigger the bug 105 just using JCE. Moreover, the excessive use of default values in JCE makes it 106 easy to go wrong and rather difficult to spot the errors. 107 108 The bug was for example triggered by the following code snippet: 109 110 ```java 111 KeyPairGenerator keygen = KeyPairGenerator.getInstance("DSA"); 112 Keygen.initialize(2048); 113 KeyPair keypair = keygen.genKeyPair(); 114 Signature s = Signature.getInstance("DSA"); 115 s.initSign(keypair.getPrivate()); 116 ``` 117 118 The first three lines generate a 2048 bit DSA key. 2048 bits is currently the 119 smallest key size recommended by NIST. 120 121 ```java 122 KeyPairGenerator keygen = KeyPairGenerator.getInstance("DSA"); 123 Keygen.initialize(2048); 124 KeyPair keypair = keygen.genKeyPair(); 125 ``` 126 127 The key size specifies the size of p but not the size of q. The NIST standard 128 allows either 224 or 256 bits for the size of q. The selection typically depends 129 on the library. The Sun provider uses 224. Other libraries e.g. OpenSSL 130 generates by default a 256 bit q for 2048 bit DSA keys. 131 132 The next line contains a default in the initialization 133 134 ```java 135 Signature s = Signature.getInstance("DSA"); 136 ``` 137 This line is equivalent to 138 139 ```java 140 Signature s = Signature.getInstance("SHA1withDSA"); 141 ``` 142 Hence the code above uses SHA1 but with DSA parameters generated for SHA-224 143 or SHA-256 hashes. Allowing this combination by itself is already a mistake, 144 but a flawed implementaion made the situation even worse. 145 146 The implementation of SHA1withDSA assumeed that the parameter q is 160 bits 147 long and used this assumption to generate a random 160-bit k when generating a 148 signature instead of choosing it uniformly in the range (1,q-1). 149 Hence, k severely biased. Attacks against DSA with biased k are well known. 150 Howgrave-Graham and Smart analyzed such a situation [HS99]. Their results 151 show that about 4 signatrues leak enough information to determine 152 the private key in a few milliseconds. 153 Nguyen analyzed a similar flaw in GPG [N04]. 154 I.e., Section 3.2 of Nguyens paper describes essentially the same attack as 155 used here. More generally, attacks based on lattice reduction were developed 156 to break a variety of cryptosystems such as the knapsack cryptosystem [O90]. 157 158 ## Further notes 159 160 The short algorithm name DSA is misleading, since it hides the fact that 161 `Signature.getInstance(DSA)` is equivalent to 162 `Signature.getInstance(SHA1withDSA)`. To reduce the chance of a 163 misunderstanding short algorithm names should be deprecated. In JCE the hash 164 algorithm is defined by the algorithm. I.e. depending on the hash algorithm to 165 use one would call one of: 166 167 ```java 168 Signature.getInstance(SHA1withDSA); 169 Signature.getInstance(SHA224withDSA); 170 Signature.getInstance(SHA256withDSA); 171 ``` 172 173 A possible way to push such a change are code analysis tools. "DSA" is in good 174 company with other algorithm names RSA, AES, DES, all of which default to 175 weak algorithms. 176 177 ## References 178 179 [HS99]: N.A. Howgrave-Graham, N.P. Smart, 180 Lattice Attacks on Digital Signature Schemes 181 http://www.hpl.hp.com/techreports/1999/HPL-1999-90.pdf 182 183 [N04]: Phong Nguyen, Can we trust cryptographic software? Cryptographic flaws 184 in Gnu privacy guard 1.2.3, Eurocrypt 2004, 185 https://www.iacr.org/archive/eurocrypt2004/30270550/ProcEC04.pdf 186 187 [O90]: A. M. Odlyzko, "The rise and fall of knapsack cryptosystems", Cryptology 188 and Computational Number Theory, pp.75-88, 1990 189 190 [DSS]: FIPS PUB 186-4, "Digital Signature Standard (DSS)", National Institute 191 of Standards and Technology, July 2013 192 http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf 193
