Re: Rebuilding the private key from signatures
On Feb 24, 2011, at 9:39 AM, Atom Smasher wrote: > On Thu, 24 Feb 2011, Aaron Toponce wrote: > >> However, I was in a discussion with a friend, and the topic came up that it >> is theoretically possible to rebuild your private key if someone had access >> to all your signed mail. We debated the size of signatures and mail that >> would need to be collected for this to be probable. >> >> Is it? > = > > if an attacker has two messages signed with DSA, and they happen to use the > same value of "k" then it's trivial to recover the private key. > > a random "k" is the achilles heel of DSA and elgamal (and their ECC > derivatives). if "k" is truly random (and reasonably large), the chances of > getting a duplicate "k" approaches zero... if "k" is not reasonably large or > there's a bias that can produce duplicate "k"s with the same value, you're > hosed. > > http://www.the-fifth-hope.org/hoop/5hope_speakers.khtml#panel037 > http://en.wikipedia.org/wiki/Digital_Signature_Algorithm > http://en.wikipedia.org/wiki/ElGamal_signature_scheme It's worth mentioning that a variant of this is what caused the Elgamal signing key problem back in 2003 (and indirectly, what caused Elgamal signatures to be dropped from the OpenPGP standard altogether). See http://lists.gnupg.org/pipermail/gnupg-announce/2003q4/000160.html for the details. In that attack, all you usually needed was the public key alone, since most Elgamal signing keys were primary keys, and primary keys issue signatures over the user ID, giving you the signature needed to mount the attack. David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Rebuilding the private key from signatures
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 Hi On Thursday 24 February 2011 at 2:13:13 PM, in , Robert J. Hansen wrote: > It is also theoretically possible to rebuild your > private key using a fifth of gin and a Ouija board. I couldn't resist asking: do you have a citation for this? - -- Best regards MFPAmailto:expires2...@ymail.com Always forgive your enemies; nothing annoys them so much -BEGIN PGP SIGNATURE- iQE7BAEBCgClBQJNaROjnhSAAEAAVXNpZ25pbmdfa2V5X0lEIHNpZ25pbmdf a2V5X0ZpbmdlcnByaW50IEAgIE1hc3Rlcl9rZXlfRmluZ2VycHJpbnQgQThBOTBC OEVBRDBDNkU2OSBCQTIzOUI0NjgxRjFFRjk1MThFNkJENDY0NDdFQ0EwMyBAIEJB MjM5QjQ2ODFGMUVGOTUxOEU2QkQ0NjQ0N0VDQTAzAAoJEKipC46tDG5pAGoEAJXk 8ho+2GxJatM2jAfn8bXQmbUCNCrPvewukFucFWec/Ma4vPJsH6EEO6KdLQCJtTCl xhDT3wVKE5ckn6cTFYhFERe3u78mLFT0SuXVb39ausP0f2cpnLF0hYAaKqq6zvNn wzd48/wKCtdBalvj+BsG7HwqJDPIf0G2HDOXakVG =lOSk -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Rebuilding the private key from signatures
On Fri, Feb 25, 2011 at 03:39:10AM +1300, Atom Smasher wrote: > if an attacker has two messages signed with DSA, and they happen to > use the same value of "k" then it's trivial to recover the private > key. > > a random "k" is the achilles heel of DSA and elgamal (and their ECC > derivatives). if "k" is truly random (and reasonably large), the > chances of getting a duplicate "k" approaches zero... if "k" is not > reasonably large or there's a bias that can produce duplicate "k"s > with the same value, you're hosed. Found this: http://rdist.root.org/2010/11/19/dsa-requirements-for-random-k-value/ I've learned something new today. Thank you very, very much! -- . o . o . o . . o o . . . o . . . o . o o o . o . o o . . o o o o . o . . o o o o . o o o signature.asc Description: Digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Rebuilding the private key from signatures
On Thu, 24 Feb 2011 10:38:41 -0500 Daniel Kahn Gillmor articulated: > Fortunately, i don't think that the PRNG used in GnuPG has any known > vulnerabilities. The key word there is "known"; although the feasibility of rebuilding a private key by a normal end user is extremely slight. In any case, I am not going to be losing any sleep over it. Besides, if I wanted a truly secure encryption, I would use a one-time pad system. That is about as secure as it gets. -- Jerry ✌ gnupg.u...@seibercom.net _ Disclaimer: off-list followups get on-list replies or get ignored. Please do not ignore the Reply-To header. Ignorance is never out of style. It was in fashion yesterday, it is the rage today, and it will set the pace tomorrow. Franklin K. Dane signature.asc Description: PGP signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Rebuilding the private key from signatures
On Thu, 24 Feb 2011, Aaron Toponce wrote: However, I was in a discussion with a friend, and the topic came up that it is theoretically possible to rebuild your private key if someone had access to all your signed mail. We debated the size of signatures and mail that would need to be collected for this to be probable. Is it? = if an attacker has two messages signed with DSA, and they happen to use the same value of "k" then it's trivial to recover the private key. a random "k" is the achilles heel of DSA and elgamal (and their ECC derivatives). if "k" is truly random (and reasonably large), the chances of getting a duplicate "k" approaches zero... if "k" is not reasonably large or there's a bias that can produce duplicate "k"s with the same value, you're hosed. http://www.the-fifth-hope.org/hoop/5hope_speakers.khtml#panel037 http://en.wikipedia.org/wiki/Digital_Signature_Algorithm http://en.wikipedia.org/wiki/ElGamal_signature_scheme -- ...atom http://atom.smasher.org/ 762A 3B98 A3C3 96C9 C6B7 582A B88D 52E4 D9F5 7808 - "To consider yourself an environmentalist and still eat meat is like saying you're a philanthropist who doesn't give to charity" -- Howard Lyman ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Rebuilding the private key from signatures
On 02/24/2011 09:09 AM, Aaron Toponce wrote: > What is the likelihood that an attacker could rebuild a private key from > a collections of signed mail, and would it depend on the hash used in > the algorithm? It doesn't depend as much on the digest algorithm used as it does on the type of public key and the quality of the PRNG used during the signature process. DSA keys in particular can be recovered if the random number generator used to create the signatures turns out to be predictable: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.1538 Fortunately, i don't think that the PRNG used in GnuPG has any known vulnerabilities. --dkg signature.asc Description: OpenPGP digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Rebuilding the private key from signatures
On 2/24/11 9:09 AM, Aaron Toponce wrote: > However, I was in a discussion with a friend, and the topic came > up that it is theoretically possible to rebuild your private key if > someone had access to all your signed mail. It is theoretically possible to rebuild your private key if someone has access to *one* signed mail. It is also theoretically possible to rebuild your private key using a fifth of gin and a Ouija board. These two theoretical possibilities are of roughly the same magnitude. Don't worry about it. :) ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Rebuilding the private key from signatures
I generated my key back in 2004, and I've been a very vocal and active supporter of GnuPG, encrypting communications, and digitally signing mail. However, I was in a discussion with a friend, and the topic came up that it is theoretically possible to rebuild your private key if someone had access to all your signed mail. We debated the size of signatures and mail that would need to be collected for this to be probable. Is it? What is the likelihood that an attacker could rebuild a private key from a collections of signed mail, and would it depend on the hash used in the algorithm? -- . o . o . o . . o o . . . o . . . o . o o o . o . o o . . o o o o . o . . o o o o . o o o signature.asc Description: Digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
