ctz / defcon-uhcc Goto Github PK
View Code? Open in Web Editor NEWUnderhanded Crypto Competition (defcon challenge) 2015 entry
Underhanded Crypto Competition (defcon challenge) 2015 entry
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[1] 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. [1]: 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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.