Anonymous writes:

...

So next we would like to solve:

s ^ e mod n = m

or in other words find e, k and n st:

s ^ e - m = k * n

In addition it has to be that n is the right length based on the "s" padding. This limits it to an 8 bit range, in this case 1024-1031 bits.

The constraint I gave was that log(n) = 1024. Bear in mind that the msbyte of s = 0x08, so we know that n > s, and I think we know that n < 2^1024 also based on the s padding from the signature. So based on this n would be in the range 1020 - 1024 bits, right?

If you make n be a product of a bunch of small primes, so that you can make signatures with it, then a third party can detect this and know it is bogus.

He has to factor your n to determine that it is bogus though? This would imply that he had more compute than you do. (Not unreasonable threat model mind).

Also, this approach won't match the keyid of the original signature.

Agree. Weak counterpoint is that the keyid is not authenticated, though if IRS have a key, they know it's keyid, and if that keyid is the one posted (unauthenticated inside the armor 0xCE56A4072541C535), this tips the probability of authorship towards the key they have. This though is perhaps not incontroverible proof, if one posits that Toto or unknown others were trying to create a complicated mess for people to confuse themselves analysing. Evidence suggests that this was/is the case: there are other messages, for example one with a signature with what is perhaps a 0xdeadbeef attack against a key on the keyservers, with the same 32 bit keyid, but a 64 bit key id differing by 1 bit. Another key which almost but not quite makes sense to PGP (a few bits twiddled). Plus lots of still undecrypted encrypted messages posted to the list, plus possibly stegoed images posted (one image was posted together with a password which was also publically posted together with instructions for recovering using S-TOOLS4.ZIP (a stego package for windows), and lots of other anonymously and pseudonymously posted images.) (One of the encrypted keys which passphrases were forwarded to the list for just today had been posted to the list over a year ago -- Carl Johnson couldn't have posted the passphrase because he is incarcerated).

Another approach is to generate an n such that the discrete logarithm is solvable mod n. Then you can solve for e in s^e = m mod n, with the base of the discrete log being s. Doing this you can match the keyid and size of n without too much difficulty.

Yes! Excellent. This construct (discrete logs over composite modulus to allow the same operation) is used by the identity based crypto people. The trap door is not that good, because 512 bit discrete logs are as you suggest rather expensive to compute.

Unfortunately e will not be small; it will be about the same size as n. There are one or two keys on the public keyring which have large e's, apparently generated by hacked versions of pgp. Some people feel safer with random e than a small e. So this could perhaps be accepted.

It's not a hacked version of PGP, I've generated such keys myself also: it is just a lesser documented feature of pgp2.x, (pgp -kg 1024 768) would give you a 1024 bit n and a 768 bit e).

(OTOH given two keys that both sign the same message, one with a small e and one with a large one, it is obvious that the first is the legit one and the second is the cloned one.)

Not so obvious with the other key tinkering which has been going on here. It seems likely that Toto et al were purposefully trying to sow confusion, and seem to delight in leaving little clues to people trying to understand it looks like this strategy has been operational for over a year now (some of the encrypted messages which passphrases were forwarded to the list for just today had been posted to the list over a year ago -- Carl Johnson couldn't have posted the passphrase because he is incarcerated).

Unfortunately with a 1024 bit RSA modulus it is not going to be feasible to solve 512 bit discrete logs using a reasonable amount of effort. However by using more factors in the RSA modulus it should become practical. The number of factors needed will depend on how much resources you have to work on the discrete log.

Resources available: one low end pentium based linux PC? :-) Just that the attack is clearly feasible is interesting though a demonstration would be perhaps more convincing to less technically aware IRS people. The biggest resource overhead is implementing that lot though, unless there exist packages or libraries which already do most of it for you.

Once you have your n and e you can sign other messages with the key. The n looks OK from outside because the fact that it has more than two factors is not detectable, as long as its factors are not too small. Actually there may be a way of distinguishing n's with two factors from n's with more, check into this.

Also check into whether n's of this form can be factored via a p-1 factoring attack. It may be that making the discrete log easy also makes the modulus factorable.

I think the answer to that is yes. In connection with previous discussions of implementing forward secrecy using identity based crypto (search archives for cypherpunks / coderpunks /cryptography for posts with Subject: non-interactive forward secrecy / identity based crypto ) another Anonymous describes some of the identity based crypto papers on this topic, which suggests another method of being able to compute discrete logs mod composite n. : Maurer describes an alternative set of parameters as well. Rather than : choosing small primes for the discrete logs, larger primes with a : special form are used which make the problem easy. This is based on the : Pohlig-Hellman discrete log algorithm, which applies when p-1 has all small : factors. The problem is that there also exists a p-1 factoring algorithm : which works when p-1 has all small factors. However the former algorithm : costs the square root of the size of the factors, while the later takes : work proportional to the size of the factors themselves. This gives a : window where the discrete log can be done but the factoring will fail. : : For this embodiment, Maurer suggests a modulus which is the product of : two primes, each 100 digits (333 bits) in length. This will produce : a 666 bit modulus. Have each of the primes be such that (p-1)/2 is a : product of several 13-15 digit (43-50 bit) primes. So it could be done, I think, and in such a way that you have lower cpu overhead than the attacker trying to prove one key more likely than the other. Adam