search

mirleft / ocaml-nocrypto

OCaml cryptographic library
ISC License
111 stars 53 forks source link

Dsa broken #46

Closed hannesm closed 9 years ago

hannesm commented 9 years ago

being either sign or verify... it is broken depending on the key..

hannesm commented 9 years ago

(might as well be connected to DSA key generation -- both keys have been generated by nocrypto (in Fips1024 mode))

pqwy commented 9 years ago

I think I have an idea, gimme an hour..

pqwy commented 9 years ago

Yeah, the key is invalid. Its y is not gg^x mod p.

Interestingly enough, if I keep domain params and x - all the tricky bits - and literally copy and paste the code which (deterministically) generates y from the rest, and use it to reconstruct the key, I get a valid one.

The valid y is:

11945608279462698190424526383146682999702031530278451886797173134514509168389781234953719923108156520324709256399256461483987584655322216181385783676883746231497539212713405104162740794821897116847929436855153812874573029164668519226608037997796584419339378665393955168267537473909769911985484198097040262054

... which suspiciously sits at the Levenshtein distance of 1 from the bad y. Specifically, it emerges if you insert the numeral 7 at the position 214 in the decimal expansion of the bad y.

Are you really, really, really sure this invalid key was not transmitted by copy-and-paste at some point? :smile:

hannesm commented 9 years ago

so the config file - where I generated the key for - is written to disk on Dec 19 19:32... there was no copy-and-paste involved.. just some Dsa.generate Fips1024 and then writing the sexp of the dsa to disk.. strange, but thanks for your investigations..

pqwy commented 9 years ago

It's still possible we serialized the key badly. Try to track down how the omission happened if you find some time, there still might be a bug with the key writing process.

dbuenzli commented 9 years ago

Feels like a missing flush.