CHALLENGE? Toto/signature attack w. unpublished public key
This post discusses the possibility of generating a RSA public key n,
and e given a signature s on a message m creating using an unknown
(unpublished) n and e. A message and signature whose validity has
some bearing on a current IRS investigation is given as a target for
an attack if such an attack is feasible.
Toto published one signed message [1] but not a public key for the
signature. It seems to me that there should be other public keys
which one could generate which could have signed the same message.
I would like comments on the feasibility of the signature attack
proposed below, and suggestions for more efficient methods.
(For those not following the Toto saga, he was the author of a series
of anti-government rants and future fiction stories on cypherpunks.
The posting of [1] to the list seems to have been deemed a handy
excuse for the IRS to arrange Carl Johnson's incarceration See:
http://jya.com/cejfiles.htm. They claim that the presence of a public
key on Carl Johnson's hard disk proves that he authored the post in
question [1].)
What we have is:
Unknowns: e, n, d
Knowns: m, s
Where m = padding || md5( message )
A signature is computed as:
s = m ^ d mod n
and verified by checking that:
s ^ e mod n = m
( where RSA says: n = p.q, d.e = 1 mod (p-1).(q-1) )
We are trying to find an n and an e which satisfy s ^ e mod n = m,
with the additional constraints that log2( n ) = 1024 and n > s
(because we have the signature s, and it is 1024 bits in length).
For bonus points it would be nice for n mod 2^64 = 0xCE56A4072541C535,
which is the key-id in the signature. (I say bonus points because the
key-id in the signature is not authenticated, or included in the
message digest, so could have been for example edited after the
signature was made, or filled with random numbers for whatever
reason).
Tinkering with PGP I can extract the values for the knowns:
s = 0x08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A9007D1801AEAEE6E6
D2C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7A
C28BE916570BA7BB9C00C64DF57113C4AE81613BD351541523CD3A028FBF220E
F7469BD4175302DCB5B6E886974877F28A2D301433AFFFE26081008BFF687B37
m = 0x0001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003020
300C06082A864886F70D0205050004105A82A30F832DC6839C20DD6DB2EF783B
(the 00 01 FF .. FF 00 are the PKCS#7 required padding, then the
3020300c06082a864886f70d020505000410 is the ASN padding indicating
various PKCS #7 cruft, and 5A82A30F832DC6839C20DD6DB2EF783B is the
digest of the message (which includes some of the info in the
signature block: timestamp, signature type, etc))
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
I have been trying to factor f3 = s ^ e - m for e = 3, and can get
factors:
f = 2 2 5 11 17 26496937
and
251048771208077840279253039518619486761149393656018551881762776705901\
323868599665917317036581098944533770815064901485649759588104677561495\
719846643046535204246014520276297740544890135011586884286882393788265\
716989378535974685125268132766806309723740928058713253950594405611241\
121342427851929130344133177905256374336176401503386547907484013668011\
870701681839150463738400849274433891413410494500220449307074230633487\
686485522732190007426023068542565670710414256907678005650439818373128\
045462081252984434043133357326332595300178784873354995536385391488171\
082297914170316457453668703759313538562865586078736676571820284813613\
435988240345557012477625002576044754861439307189875911957770722297269\
127365840009630893296289725097984631185778357339553526670628683341222\
179800672224971064029655723085468566526546006022122686584662976524189\
679277675211381453870834486124773894995875790430641434242560016378644\
4039359130261
(I call the f resulting from choosing e = 3, f3, other e values can be
denoted f5, f7, etc).
It seems to me that if we can get get a factor out (or construct a
composite from factors) which is greater than s, and is 1024 bits
long, then this "key" could have signed the message in question.
If the number has 2 or more factors, which we know because we
constructed it by multiplying them, then we could even "sign" another
message with this key, by generating a d based on the p, q (and
possibly other multiples) and have both messages appear to be signed
by the same key.
If we can get some larger factors, we stand a chance because we have
the flexibility of being able to adjust a potentional n's size by
multiplying by combinations of factors found so far 5 11 17 26496937.
This means we can adjust n's size by adding bits by multiplying by
combinations as follows
combination bits added
5 2 - 3
11 3 - 4
17 4
5 11 5 - 6
5 17 6 - 7
11 17 7 - 8
26496937 24 - 25
So the challenge is to find other factors of:
f = 251048771208077840279253039518619486761149393656018551881762776705901\
323868599665917317036581098944533770815064901485649759588104677561495\
719846643046535204246014520276297740544890135011586884286882393788265\
716989378535974685125268132766806309723740928058713253950594405611241\
121342427851929130344133177905256374336176401503386547907484013668011\
870701681839150463738400849274433891413410494500220449307074230633487\
686485522732190007426023068542565670710414256907678005650439818373128\
045462081252984434043133357326332595300178784873354995536385391488171\
082297914170316457453668703759313538562865586078736676571820284813613\
435988240345557012477625002576044754861439307189875911957770722297269\
127365840009630893296289725097984631185778357339553526670628683341222\
179800672224971064029655723085468566526546006022122686584662976524189\
679277675211381453870834486124773894995875790430641434242560016378644\
4039359130261
One could also try other values for e, although they result in larger
f.
What is the best factoring code available to have a go at factoring
the above? (I have been usign the demo pollard-rho factoring code
which comes with ssh-1.2.26 in the gmp-2.0.2-ssh-2/demos directory).
Anyone interested to give this a go, who has say got a few (hundred?)
workstations already setup for another factoring challenge which they
could divert to attack the above f3 (or f5, f7, etc).
Course, if Toto is still at large, and Carl Johnson is not the only
one with the key (and some messages on cypherpunks recently lend
credence to this), he might trash this challenge by posting another
signed message, or weaken it's value by posting a public key which
proved could be shown to have been derived by this method.
(Interestingly, I think merely posting a public key claiming to be the
`real key' which we couldn't factor nor show to be a factor of f
wouldn't prove that that key was any more legitimate than a key
generated by a success on this challenge, all it would tend to show
would be that the person who posted it had more compute power
available than us!)
Adam
[1]
-----BEGIN PGP SIGNED MESSAGE-----
"Contrary to one famous philosopher,
you're saying the medium is not the
message," Judge Thomas Nelson said,
alluding to the media theorist Marshall
McLuhan.
http://www.nytimes.com/library/cyber/week/120997encrypt-bernstein.html
Bullshit!
The bits and bytes of email encryption are a clear message
that I wish to exercise my right to speak freely, without those
who wish to do me harm invading my privacy.
The death of strong encryption on the InterNet will be the
global death of free speech on the InterNet. Accordingly, I
feel it is necessary to make a stand and declare that I stand
ready and willing to fight to the death against anyone who
takes it upon themselves to try to imprison me behind an
ElectroMagnetic Curtain.
This includes the Ninth Distric Court judges, if they come to
the conclusion that the government that they represent needs to
electronically imprison their citizens 'for their own safety.'
The problem: Criminals with a simple
encryption program can scramble their data
beyond even the government's ability to read it.
http://www.zdnet.com/zdnn/content/zdnn/1208/261695.html
Fuck the lame LEA pricks who whine about not being able to
stop someone bringing in a planeload of drugs without being
able to invade the privacy of every person on the face of
the earth.
Am I supposed to believe that I have knowledge of when and
where major drug shipments are taking place, simply by virtue
of hanging out as a musician, yet the LEA's are incapable of
finding out the same information by being competent in their
profession? Barf City...
[I will shortly provide information for any LEA which wishes
to prosecute me for my coming 'physical' death threat, on
how to hunt me down like the filthy dog that I am.]
"Why are you saying that the fact that [encryption]
is functional takes it out of the First Amendment
context?" Myron Bright, one of the judges, asked
the Justice Department attorney, who was still in
mid-sentence. He answered that the regulations
were not aimed at suppressing speech, but only at
the physical capacity of encryption to thwart
government intelligence gathering.
The Spanish language has the same "physical capacity." So
does (:>), (;[), and {;-|). Likewise, BTW, FWIW, FYI, and
my own personal favorite, YMMV (You Make Me Vomit? --or--
Your Mileage May Vary?). <-- Ambidextrous encryption.
An-cay e-way pect-exay ig-pay atin-lay usts-bay of
ildren-chay?
Whispering also has the "physical capacity" to "thwart
government intelligence gathering."
When does the bullshit stop? When do we stop making the
use of the Spanish language over the InterNet illegal?
When do we stop making whispering, pig-latin, anagrams
and acronyms illegal?
When do we stop saying that our government is such a
piece of crap that it is a danger to let its citizens
communicate freely, in private, and share their private
thoughts with one another?
At one point Fletcher called the government's case
"puzzling."
http://www.news.com/News/Item/0,4,17114,00.html
Only because her mom taught her that it was unladylike to
say "Bullshit!"
In arguments Monday, a Justice Department
lawyer, Scott McIntosh, said the government's
intent was to preserve the ability of intelligence
agencies to eavesdrop on foreign governments
and citizens.
http://www.nytimes.com/library/cyber/week/120997encrypt-bernstein.html
Let's see if I have this right...
The U.S. government needs to destroy the right to free speech
and right to privacy of its own citizens in order to infringe
upon the human rights of the governments and citizens of other
countries? Countries which already have strong encryption?
Countries like Red China, which is currently engaged in
encryption research with an American company who got permission
to export much more diverse encryption material (after making
a huge campaign donation to the Whitehouse) than Professor
Bernstein will ever likely share with others?
Apologies to Judge Fletcher, but that's not "puzzling." That's
the same-old-same-old Bullshit!
OFFICIAL 'PHYSICAL' DEATH THREAT!!!
The pen is mightier than the sword. Thus, I prefer to wage my
'war to the death' against those who would stomp on my basic
human rights *"in the interests of National Security"* with my
electronic pen, on the InterNet, using encryption when I have
reason to fear persecution by Facist, Nazi motherfuckers.
[* ~~ TruthMonger Vernacular Translation ~~ "so that the
government can maintain its authority over the citizens
by use of force and violation of human rights, rather than
going to all of the trouble of acting in a manner that will
garner the citizens' respect."]
I will continue to express my thoughts through the words
I send electronically over the InterNet, both publically
and privately. I will fight to the bandwidth death against
anyone who wants to deny me my right to express my opinions
and access the opinions of those who also wish to express
their own opinions and share their true thoughts with their
fellow humans.
If the ElectronicMagnetic Curtain slams down around me,
then I will have no choice but to continue my current fight
in MeatSpace.
And I am not alone...
I will share the same 'DEATH THREAT!!!' with Judges Fletcher,
Nelson and Bright that I have shared with the President and
a host of Congressional and Senatorial representatives:
"You can fuck some of the people all of the time, and all of
the people some of the time, but you are going to end up in a
body bag or a pine box before you manage to fuck all of the
people all of the time."
Am *I* going to whack you out? Maybe...
I would prefer just dumping some tea in Boston Harbor, if that
will get my message across in MeatSpace, but if it won't, then
I guess I will have to take stronger action.
There are undoubtedly a plethora of LEA's ready and willing to
prosecute and imprison me for agreeing with Patrick Henry, who
said, "Give me liberty, or give me death." The irony, of course,
is that I do not pose a great danger to anyone but myself as
long as I continue to have my human rights and my liberty
unthreatened.
The chances of me actually getting off of my fat butt and
going out into the real world to whack out the enemies of
freedom are probably pretty small (unless I run out of
cigarettes and beer, and wouldn't have to make an extra
trip).
I fully understand that this does not lessen the potential
of any LEA who gets a wild hair up their butt to throw a
mountain of taxpayer resources into prosecuting me and
imprisoning me for their own professional/political gain.
However, if you are performing actions so outrageously against
basic human rights and freedoms as to get me off of my lazy ass,
then I am the least of your problems, because there undoubtedly
are millions of people more functional than myself (who get out
of the house and go further than the liquor store) who are less
willing than myself to put up with increasingly heavy chains
placed around their hands and feet 'in the interests of national
security.'
Feel free to have the Federales break down my door and
imprison me for pointing out the obvious. After all, I fit
the profile of a domestic terrorist--I quote the Constitution
and the Bill of Rights, and I speak out against increasingly
big government.
But remember...it's the quiet ones you've got to watch...
If you force everyone to 'be quiet', then you've got a world
of trouble on your hands.
Sincerly,
John Gilmore
[I thought I posted the post Anonymous is replying to to cypherpunks &
cryptography. He however seems to have followed up to coderpunks.]
Here [1] is a suggestion from Anonymous which sounds technically good,
an improvement over my approach to finding additional keys capable of
signing the message, it shows that quite plausibly one could generate
another key which could have signed the message in question.
Hope Carl Johnson can get a technical expert with enough smarts to
understand the below, and express this if it is necessary.
Adam
[1] Forwarded message from coderpunks:
======================================================================
Date: Sat, 19 Sep 1998 21:48:07 +0200
From: Anonymous
This post discusses the possibility of generating a RSA public key n, and e given a signature s on a message m creating using an unknown (unpublished) n and e. A message and signature whose validity has some bearing on a current IRS investigation is given as a target for an attack if such an attack is feasible. [...] 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. There are two approaches here. First, the one you are doing: try different e values and factor s^e - m until you find one which looks like it could be a plausible k * n. The problem is that n is supposed to be the product of two large primes, and if it is, you won't be able to factor it. So you might be able to create a public key which looks reasonable, but you can't create a private key which does, one which is a multiple of two large primes. 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. Also, this approach won't match the keyid of the original signature. 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. 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. (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.) If you know the factorization of the size of the exponentiation group mod n, and all the factors are small enough, you can solve the discrete log problem mod n. You solve the discrete log separately for each factor and then combine the results. With an RSA modulus, the group order is LCM(p-1,q-1), or equivalently (p-1)(q-1)/GCD(p-1,q-1). If you were able to solve discrete logs mod p-1 and q-1 then you could solve discrete logs mod n. 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. 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.
participants (1)
-
Adam Back