
Date: Thu, 5 May 2016 11:17:57 +0300 From: Solar Designer <solar@...nwall.com> To: osssecurity@...ts.openwall.com Subject: Re: broken RSA keys I posted some halfbaked thoughts in here yesterday. (Not that this message is fully baked.) When suspecting that some of what we were seeing was an artifact of the process, I temporarily forgot that those shared factors were supposed to be GCDs (not arbitrary shared factors), which doesn't leave freedom to the process. The patterns seen in the GCDs should in fact have to do with pairs of keys, rather than with the process. Luckily, there is a simple explanation for the patterns: When a modulus is (mangled?) such that each of its 64bit limbs consists of two matching 32bit limbs, it is necessarily a multiple of 2^32+1. That's because it can be represented as: N = {an an ... a1 a1 a0 a0} = (2^32+1) * {0 an ... 0 a1 0 a0} where the {...} notation means concatenated 32bit limbs (or base 2^32 digits, if you will). From this, it follows that pairwise GCDs of such moduli will also have 2^32+1 as a factor, and this is what ultimately causes the 32bit limb patterns in the GCDs. As Alexander Cherepanov correctly pointed out, even the seemingly slightly more complex 32bit limb patterns in the GCDs are merely indication of them being multiples of 2^32+1. There's probably nothing else to see here. I made the mistake yesterday of looking at hex representations of the posted shared factors without first looking at hex representations of the moduli. Now that I just did, I see that the example modulus I posted does follow the pattern mentioned above, and which Stanislav mentioned below. On Wed, May 04, 2016 at 09:18:26PM 0400, Stanislav Datskovskiy wrote: > Author of Phuctor speaking. Thank you for posting your comments! > 1) We presently know of 165 keys containing 'mirrored' moduli. This is similar but not the same as the number Alexander Cherepanov posted after analyzing your data: "From 225 keys listed at http://phuctor.nosuchlabs.com/phuctored, 152 ones have modulus and exponent divisible by 2**32+1 [...] Modulus and exponent are divisible by 2**32+1 or not simultaneously." Is your definition of "mirrored" different from "divisible by 2**32+1", or does something else (what?) cause the 165 vs. 152 discrepancy? > 2) The list of affected persons and organizations includes a number of > possibly 'politically interesting' targets, e.g., mathematicians, open > source projects (Debian, a few others), plus a few other delicacies, > such as 'Apple Product Security', 'PGP Corporation Update Signing > Key', etc. > > 3) The 'mirrored' keys found thus far in no case have valid > selfsignatures. (A number of the remaining phuctored keys  do.) Thus > it does not follow from the facts at hand that these particular keys > were generated /by the people and organizations whose names appear in > the user string/ ! Are all of the "politically interesting" targets' keys (at least those you explicitly listed in 2 above) "mirrored" (and don't have valid selfsignatures, as you say)? > 4) One parsimonious explanation for (1) given (2) and (3) is that the > 'mirrored' keys were generated by a malicious actor, Makes sense, but why would they similarly mangle the exponent as well? As Alexander Cherepanov wrote, if I understand him correctly, there's 100% overlap between keys with such moduli and with such exponents. > who counted on the principle described at, e.g., https://evil32.com , > https://bugs.gnupg.org/gnupg/issue1579 As I understand it, the description at evil32.com in particular is about generating valid (and not necessarily weak) keypairs that would happen to have the intended 32bit key id. This is more computationally intensive than the "mirroring", but it is fast enough, is an olderknown(?) and more obvious attack, and it doesn't expose the encrypted data to other/unintended attackers (OK, the "evil guys" might not care either way). So it is a little bit surprising (but just a little) that someone would go for the "mirroring" instead. Alexander
Powered by blists  more mailing lists
Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.