Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Type||Name||Latest commit message||Commit time|
|Failed to load latest commit information.|
NAME OF PROJECT: RFC6979 is not optional WAS THIS A TEAM PROJECT: no PROJECT LICENSE: CC0 CHALLENGE (GPG KEY LEAK / PASSWORD HASHING BACKDOOR): GPG key leak DESCRIPTION: See submission/patch.txt for the underhandedness. This is for GnuPG 1.4. DSA needs a entirely secret, unique-per-key number (`k') for each signature. If you fail at these constraints (like it being low entropy, or one bit being biased, or reusing a k value) your private key is recoverable from signatures. k needs to be chosen uniformly in [0,q). gnupg's choice of k starts by choosing |q| random bits, setting the top bit and seeing if the result is <q. If it's not, it chooses the top 32 bits again. The probability of this happening is very low (will vary by group, a group I generated gave a 4.5% hit rate). Because k is a super-sensitive security parameter, it obviously needs to be zeroised instead of left on the heap! Unfortunately my patch clears the buffer when the candidate is >=q, as well as at the end. That means some signatures have a 32-bit entropy k. This is enough to brute force. To demonstrate that, submission/recover.py unpicks the resulting pgp signature to extract everything needed to recover k from a sample signature in submission/sigs/attack.asc. There's also submission/recoverk.c which uses openssl's bignum library to search faster. Instant gratification: $ python recover.py > script.sh $ make recoverk $ sh script.sh k search: 00000000..0000ffff search 00000000 search 00001000 <about an hour passes> k search: 003dffc2..003effc1 search 003e0000 search 003e1000 search 003e2000 search 003e3000 with k = 003e3dfb, we found x = 3B29FC0B63E77D73C4956FD35F6A5E3E0DCA04D55A3A3197BB82C6CBC32985A5 recoverk can search 16-bits worth of space in 50 CPU seconds. The search is embarrassingly parallel, so you can hire an EC2 m4.10xlarge (40 cores) and extract the private key from an affected signature for about USD50 in 22 hours. The user will not see any difference: their signatures will always still work, and be properly randomised with overwhelming probability. I think it's also likely to be overlooked in source code review. : see cipher/dsa.c gen_k(). note that GnuPG 2.0 is different and unaffected. Files in submission: - dsa.orig.c: unchanged cipher/dsa.c. GPL license. - dsa.patched.c: altered cipher/dsa.c. GPL license. - dsa.py: comedy insecure DSA in python. - generate-sigs.sh: generate a shedload of signatures and keep the ones affected. - gnupg/: a test key recovered by submission, passphrase is 'test'. - Makefile: builds recoverk. - patch.txt: the patch. - recoverk.c: DSA k recovery program. Needs libcrypto. - recover.py: unpicks sigs/attack.asc and outputs shell invocations of recoverk to do the work. - sigs/: directory of affected signatures.