On Tue, Sep 27, 2016 at 02:43:48PM +0000, Sean Lynch wrote:

...

Is this a bug at all?

I think the bug is that openssl is silently ignoring parameters, because I'm pretty sure what you're doing is producing and verifying sha1 hashes, not cryptographic signatures. Which means your keys aren't entering the picture at all. I

No, this is not the case. openssl do the math. I verified both signatures in my sage implementation and in python's Crypto.DSA, so math is going on, not only hashes. This fails in the same directory with a random new key: $ openssl dsaparam 1024 > dsapar ; openssl gendsa dsapar > keyrandom.priv ; openssl dsa -in keyrandom.priv -pubout -out keyrandom.pub $ openssl dgst -sha1 -verify keyrandom.pub -signature file.txt.sig file.txt Verification Failure

On Tue, Sep 27, 2016 at 06:06:40PM +0300, Georgi Guninski wrote:

On Tue, Sep 27, 2016 at 02:43:48PM +0000, Sean Lynch wrote:

...

...

Is this a bug at all?

I think the bug is that openssl is silently ignoring parameters, because I'm pretty sure what you're doing is producing and verifying sha1 hashes, not cryptographic signatures. Which means your keys aren't entering the picture at all. I

No, this is not the case. openssl do the math. I verified both signatures in my sage implementation and in python's Crypto.DSA, so math is going on, not only hashes.

This fails in the same directory with a random new key:

$ openssl dsaparam 1024 > dsapar ; openssl gendsa dsapar > keyrandom.priv ; openssl dsa -in keyrandom.priv -pubout -out keyrandom.pub $ openssl dgst -sha1 -verify keyrandom.pub -signature file.txt.sig file.txt Verification Failure

Yeah, I emailed too soon... Thats what I got too. John

On Tue, Sep 27, 2016 at 01:39:00PM -0400, John Newman wrote:

You sure your original DSA keys are unique??

Well, they are _distinct_, including congruence equivalence, but I have other pairs with the same properties, so it is not the same key definitely -- p_i and q_i are distinct primes and the rest parameters too. I generated them with a proggie and checked, also with openssl -text. Also the x509 self signed certs with the private keys work with openssl s_client/s_server.

Posting the keys/certs/private keys, this is the README: Distinct DSA keys produce valid single signature of single file and the x509 certificates from the private keys work on openssl 1.0.2j Tested on openssl 1.0.2j (latest and 1.0.1t latest) on Debian 8. The keys (also private are attached). Also at http://j.ludost.net/DSA1.tar.gz We got a triple of distinct DSA keys (key1,key2,key3) which successfully verify a single signature of a single file. By ``distinct" we count congruences, the p_i and q_i are distinct. Verification: $ openssl dgst -sha1 -verify key1.pub -signature file.txt.sig2 file.txt ; openssl dgst -sha1 -verify key2.pub -signature file.txt.sig2 file.txt ;openssl dgst -sha1 -verify key3.pub -signature file.txt.sig2 file.txt Verified OK Verified OK Verified OK Slightly harder to reverse pair of keys with the same properties is (key3,key4): $ openssl dgst -sha1 -verify key3.pub -signature file.txt.sig3 file.txt ; openssl dgst -sha1 -verify key4.pub -signature file.txt.sig3 file.txt Verified OK Verified OK To produce other signatures: choose a key from the two sets and do: $openssl dgst -sign key1.priv -out file.txt.sig file.txt Then verify, which may fail with probability about 1/2 for the first set and about 8/9 for the second set because of the random DSA $k$. Deterministic signatures are possible, but not possible with unpatched openssl. For the x509 certs: cert1 works always. cert2 works with probability about 1/2, to check: $ openssl s_server -accept 8080 -cert cert2 -key key2.priv -www #listen $ openssl s_client -connect localhost:8080 For client lynx(1) works too, with innocent warning about self signed and CN mismatch. In case of error, repeat few times. cert4 works with probability about 1/3. === Sketch of the numerology behind it. For and overview of the simple DSA, check Wikipedia or better source. The main idea is to use low multiplicative order of the generator $g$, which is expected to be of multiplicative order $q$ (at least 160 bit) prime modulo $p$. The signature is (r,s), where for random $k$, r=(g^k mod p) moq q s=some function of x,k,r,MESSAGE The public key is y=g^x mod p. The signature is valid iff $r=v, v=g^f_1(r,s) y^f_2(r,s)=g^f_3(x,r,s)$ We choose $g_i$ of low multiplicative order modulo $p_i$, for (key3,key4) it is $3$. Whenever the "random" $k$ (for the first key of the pair)is multiple of $3$, r=1 mod p mod q and $v=g^f_3_i(x_i,1,s_i)$. Since there are no congruence obstructions, f_3_i(x_i,1,s_i) can both bi divisible by $3$, giving $v_1=v_2=r=1$. This is very easy to verify in a toy implementation or in python's Crypto.*.DSA. Choosing $g=1$ as in key1 works for all $p_i,q_i$ and the private exponent $x$ doesn't matter. === Theoretically the keys are invalid, but the valid x509 certificates working in |openssl s_client| and lynx suggest lack of key validation. ===

On Wed, Sep 28, 2016 at 06:40:57AM -0400, Alfonso De Gregorio wrote:

If you are able to generate colliding signatures for a target (chosen) key, this may amount to an impersonation attack, depending on the exact origin authentication checks -- which may be considered even worse than a repudiation issue.

No, I didn't claim this.

If what you can do is to generate two new key pairs, where the signatures made by first can be verified as signed by the second (or viceversa), then this provides plausible deniability, and the possibility to repudiate any valid signature made by any of the affected signing keys.

Yes, exactly what I claimed. Posted the keys and x509 certificates, which can be verified with openssl. The keys (possibly except g=1) are not valid, but appear to be accepted by openssl without error. The certificates appear to be valid (not counting the key issues).