Posting the keys/certs for: Two distinct DSA keys sign a file with the same signature. Is this repudiation issue?

[Georgi Guninski]

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.
===




-------------- next part --------------
A non-text attachment was scrubbed...
Name: DSA1.tar.gz
Type: application/gzip
Size: 7544 bytes
Desc: not available
URL: <http://lists.cpunks.org/pipermail/cypherpunks/attachments/20160928/0e14543e/attachment.bin>