CoCalc Public Files6 - DSA (prof) / DSA (prof).sagewsOpen with one click!
Author: Gabriel Chênevert
Views : 196
Compute Environment: Ubuntu 18.04 (Deprecated)

Lab 6 - DSA (prof version)

Name of collaborators:

A) Verification

In the file mes.sage you will find what I've got to say to you all (the file can be directly interpreted in Sage, but make sure to have a look at what it contains).

'Be true to yourself and you will never fall'

Note: mes.sage will need to be reloaded afterwards because the variables r and s used for the signature are overwritten by those of the certificate.

1. Check that the parameters (p,q,g)(p,q,g) given in the certificate form a valid triple for DSA.

is_prime(p) # takes a minute or so
p % q == 1
power_mod(g,q,p) == 1

Since q\color{blue} q is prime, this is sufficient to guarantee that the multiplicative order of gmodp\color{blue} g \, \mathrm{mod} \, p is q\color{blue} q (since it cannot be a proper divisor of it).

2. Then verify that the message signature checks out correctly. The hash function that was used is simply to take the number of characters in the message (mod qq).

def verify(m, p, q, g, y, r, s): h = len(m) # never use this IRL! t = inverse_mod(s,q) return power_mod(power_mod(g,h,p) * power_mod(y,r,p),t,p) % q == r
load("mes.sage") # to reload the correct signature
verify(m, p, q, g, y, r, s)

3. This is, however, a very insecure hash function. Can you see how an attacker could use this to forge a message bearing my signature? (the signature has to appear valid to anyone that verifies it).

Remember that it's actually a hash of the message that is signed; that is, the signature would still be considered valid on any other message having the same hash value. For example:

mm = "Collisions are easy for this hash function!" verify(mm, p, q, g, y, r, s)

The security of the hash function really is an integral part of the security of the digital signature.

B) Sign message

Your turn now: you should have received a private key from the CA. Check that the (x,y)(x,y) it contains form indeed a valid key pair for DSA with the given (p,q,g)(p,q,g).

Here is my private key:

x = 0x182882788a552a291b51dba1ce131a7153a94a58a03faccd3ddaa4759086039
power_mod(g,x,p) == y

Then compute the SHA256-DSA signature of a message of your choice with this private key. You may post the signed message on the forum on Campus so that everybody can verify the signature.

from Crypto.Hash import SHA256 def sign(m, p, q, g, x): h = ZZ(, 16) k = ZZ.random_element(q) r = power_mod(g,k,p) % q s = inverse_mod(k,q) * (h + x*r) % q return (r,s)
m = "Je me souviens" (r,s) = sign(m, p, q, g, x) (r,s)
(3768874629864200217421975163261212133091241755595436668379640114052496722657, 7892654681716127822166272187632695476056646072518770527276285028147036401439)

And here's the corresponding verification function:

def verify(m, p, q, g, y, r, s): h = ZZ(, 16) t = inverse_mod(s,q) return power_mod(power_mod(g,h,p) * power_mod(y,r,p),t,p) % q == r
verify(m, p, q, g, y, r, s)

C) Importance of CA

Being a certificate authority is not a role that should be taken lightly. Indeed, if you take a look at the certificates generated by Charles-Antoine, you'll see that there is a serious problem with hist implementation of DSA: all components rr of his signatures are equal! What mistake has been committed?

If all values of r\color{blue} r are the same, it means that the same value of k\color{blue} k was used for all signature -- when a new random one should be used each time to protect the private signing key. Indeed, as soon as the same k\color{blue} k is used to sign two different messages m1\color{blue} m_1 and m2\color{blue}m_2, we get a system of linear congruences {s1k1(h1+xr)modqs2k1(h2+xr)modq \color{blue} \begin{cases} s_1 \equiv k^{-1} (h_1 + x r) \, \mathrm{mod} \, q \\ s_2 \equiv k^{-1} (h_2 + x r) \, \mathrm{mod} \, q \end{cases} which is readily solved for x\color{blue} x (and k\color{blue} k), e.g. using Cramer's rule: x(h1s2s1h2)(r(s1s2))1modq. \color{blue} x \equiv ( h_1 s_2 - s_1 h_2 ) \cdot ( r (s_1 - s_2) )^{-1} \, \mathrm{mod} \, q.

-r % s1 %% h1 -r % s2 %% h2 (h1*s2 - s1*h2) / (-r s2 + r s1 ) e909b16f-2d6c-4dc8-875a-29d16bf8aed6i %html <p> Exploit this mistake by recovering the CA private key, hence gaining the ability to generate your own ("verifiable") certificates. Test this ability by forgeing a fake one! </p>

Exploit this mistake by recovering the CA private key, hence gaining the ability to generate your own ("verifiable") certificates. Test this ability by forgeing a fake one!


This is the message that Charles-Antoine actually signed:

m1 = ''.join(file("certs/CHÊNEVERT_Gabriel.sage").readlines()[2:21])
print m1
# BEGIN PUBLIC KEY name = "CHÊNEVERT_Gabriel" role = "teacher" validity = "November 2014" algorithm = "DSA" p = 0xb5828c6f738694558d993ff3d4267895af982f681c74474275466a9e6660a586e3ef40b5671720ade156bfe88e5204f675b6e9245a57a106f610d53ab43bf33dc1313fcb1a9c9b66d3750b54e3d269a5f44c3004bb408fe6c0aa478a74d0194c2a7c22c7536116383ab0dcd1201e58718bd5676e86a42110bf2b53f14a69a96f31df3958302605a29dd0bd3fd6963e52b077c576ee384b4d94617e5411c2f85da7c90d8873fd55419b1cf011c00ef2faa2362fb820ab44aba4676b465fe3ceeae0c036f44dbec10d17af80558a1251bfcf3b040dd92fbf4bae9ff88ff9c51324bed040cf81117b760e5aefbbfd453e5970ce51cc695f6956fb813cd76868351 q = 0x1d4342e8914f37b243ad62eefa17ff836f0aa47efe30f47f1e7761bc37bc9975 g = 0xb3a14dbff59d92583ffeb35b4e485f0c9cfa61779c2ddfca7c6437e6f9619f5e591f9f353f31eb58c7e6007b0fa2b559f694fdb4336624b5a42ddb5451a736b46a0738c583bc8e2041a65cd89b981880d6d07a8487cdb1625941eb5d43d1deeeca1c03cac0c9b5dae882e853ca4d34b66a946124ed7e964d41f03a410073d1dd0bb364c5ff1c5a417a072abaade6d009de87ab45d310d648b6e66980f03ac7151b645e67b3c64bcb90c1c45a7ee3f7878b87e0bce0e2fa2ec09b634cade7cec2bf373e3c2dc4f6fd354828b22973edd473b71fd2f64f962b621b064123aca61a874ee0d641ef31aff9008ae0a908f94a1c87c2e897103b7ff15d0323f4465ee y = 0x21ddcd3c0edb359ba68cfcd812e30a2046b430be6a9300b4faa15d780b9b85361358c8eba2dece02e2f2cfc183df3690d10540b7ac85c1d83f8a64b0b97bfd71500ae2b3a80d71617723793dec6674ff83a764b2bdfaba705e0ee2af5ab7f5e178b9b930a81e8ebbd90af8761ad678043ebf7094706f7b7479eb4b3449a858242eeeae1a5a8e0a001314e48d5eecfdcab08b9dc708a2486f9e427c15a64412a37b9de244d777badcfebf1d83bbd2750f8eadb50fb67976886eb8802d29f0a5209c3d91deaedf7246b34801263566176c439f21b591d76b01cf8249e20670f06ec0ee547076d64263d7f09239bdd51c4620fe4b173fc9ddd5b32ca1f528eafb3 # END PUBLIC KEY
h1 = ZZ(, 16) s1 = s

We only need a second certificate for the attack to work.

load("certs/BIDON_Charles-Antoine.sage") m2 = ''.join(file("certs/BIDON_Charles-Antoine.sage").readlines()[2:21]) h2 = ZZ(, 16) s2 = s

And here's the actual cracking:

x = ( h1*s2 - s1*h2 ) * inverse_mod(r * (s1-s2), q) % q
power_mod(g,x,p) == y

Et voilà! Having recovered Charles-Antoine's private signing key, we can now sign anything we want as him (and a verifier has no way to detect the forgery). Here's for example a fake certificate that binds my public key with someone famous:

m = m1.replace("CHÊNEVERT_Gabriel", "GOLDBLUM_Jeff")
(r,s) = sign(m, p, q, g, x)

Anyone that verifies Charles-Antoine's signature on this certificate using his public key will consider it valid:

verify(m, p, q, g, y, r, s)

D) OpenSSL

As always, to do things properly in real life, it's better not to try to implement your own crypto and instead use a standard tool. Learn how the signature (and subsequent verification of it) of a text file works with OpenSSL and show me an example of it (you can run the commands in a terminal attached to this project).

Assuming you a textfile message.txt that you want to sign, these would be the command you need to issue:

# generate DSA parameters (p,q,g) openssl dsaparam -out dsaparam.pem 2048 # generate a pair of keys (x,y) to use with these parameters (both are actually stored in the "private key" file) openssl gendsa -out private_key.pem dsaparam.pem # extract the public key y for distribution openssl dsa -in private_key.pem -pubout -out public_key.pem # sign the message using the private key openssl dgst -sha256 -sign private_key.pem message.txt > message.sig # verify the signature using the public key openssl dgst -sha256 -verify public_key.pem -signature message.sig message.txt