|
Cryptome DVDs. Donate
$25 for two DVDs of the Cryptome collection of 47,000 files from June 1996
to January 2009 (~6.9 GB). Click Paypal or mail check/MO made out to John
Young, 251 West 89th Street, New York, NY 10024. The collection includes
all files of cryptome.org, cryptome.info, jya.com, cartome.org,
eyeball-series.org and iraq-kill-maim.org, and
23,100 (updated)
pages of counter-intelligence dossiers declassified by the US Army Information
and Security Command, dating from 1945 to 1985.The DVDs will be sent anywhere
worldwide without extra cost. |
|
23 September 1998
See related keys:
http://jya.com/anon-keys.htm,
http://jya.com/totos-keys.htm
Date: Sat, 19 Sep 1998 11:52:47 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cypherpunks@cyberpass.net
Subject: 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 <gnu@toad.com>
~~~~~~~~~~~~~~~~~~~~~~~~~~~
p.s.
NOTICE TO LEA AGENTS IN NEED OF A CAREER BOOST!
Yes, I'm just a troublemaking asshole, trying to get John
<spit> Gilmore <fart> in trouble.
However, if you want to go to the trouble of tracking me
down, I will give you some hints, since it seems likely that
anyone who has trouble finding a ton of cocaine at an
airport might not be competent in CyberSpace, either.
You might want to check with the Webmasters at the sites
quoted above to see who has accessed their web sites this
morning. The anonymous remailer I will be using is an open
secret to CypherPunks around the world as a really bad
attempt at disguising my true MeatSpace identity. This alone
ought to be enough for some aggressive young LEA and/or
federal prosecutor to earn themself some brownie-points,
since I am a sorry enough son-of-a-bitch that they would not
have much trouble convicting me in front of a jury of 'their'
peers, assuming that they can make certain that I am not
tried by a jury of my own peers.
Bonus Points:
I can also be tied into Jim Bell's Worldwide Conspiracy to
assassinate government authorities, through my implementation
of an Assassination Bot.
(I am willing to 'rat out' Jim for two bottles of Scotch. If
he is willing to rat _me_ out for less, then I guess it's
just my hard luck, eh? <--that's another hint!)
p.p.s.
You can also charge me with use of 'conventional' encryption
in the commission of a crime.
Must be your lucky fucking day, eh?
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBNI24Hs5WpAclQcU1AQFaggP8CPTVy8EAY3JbIG94frc3C70MW0hUznmp
fRgBrq7m5tLGjX7fh3/s4fpTnQi+xUvRUroFETlR6KhM3srSy456wovpFlcLp7uc
xk31cRPEroFhO9NRVBUjzToCj78iDvdGm9QXUwLctbbohpdId/KKLTAUM6//4mCB
i/9oezfegWc=
=4/6E
-----END PGP SIGNATURE-----
Date: Sat, 19 Sep 1998 19:28:09 +0200
From: Anonymous <nobody@replay.com>
To: cypherpunks@cyberpass.net
-----BEGIN PGP SIGNED MESSAGE-----
September 19, 1998, U.S. Medical Center for Federal
Prisoners, Springfield, Missouri, not a Magic Circle.
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBNgPkchp0s99tXiQlAQEoHQP+IX2GivNiJpIB3ryiu+bte0+YyJRTZDWB
bbF/qRIGrOOVKpNxuu+riAz0oUxHW3xuooPmIVcR8O0tfXljrxyAvK4qdtPFWyr9
+PaE5clU7XdRqxiKGfao569W1vRPJW5vlmUm+/BHmRF1ADG/HqTy/EbivKEvZGcw
UmrV65r+9ho=
=wa8X
-----END PGP SIGNATURE-----
Date: Sat, 19 Sep 1998 19:46:43 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cypherpunks@cyberpass.net
Cc: jya@pipeline.com
Subject: TruthMonger key's password!
Anonymous writes on cpunks (blank subject field from nobody@replay.com
earlier today).
> -----BEGIN PGP SIGNED MESSAGE-----
>
> September 19, 1998, U.S. Medical Center for Federal
> Prisoners, Springfield, Missouri, not a Magic Circle.
>
> -----BEGIN PGP SIGNATURE-----
> Version: 2.6.2
>
> iQCVAwUBNgPkchp0s99tXiQlAQEoHQP+IX2GivNiJpIB3ryiu+bte0+YyJRTZDWB
> bbF/qRIGrOOVKpNxuu+riAz0oUxHW3xuooPmIVcR8O0tfXljrxyAvK4qdtPFWyr9
> +PaE5clU7XdRqxiKGfao569W1vRPJW5vlmUm+/BHmRF1ADG/HqTy/EbivKEvZGcw
> UmrV65r+9ho=
> =wa8X
> -----END PGP SIGNATURE-----
That one I can verify the signature of (unlike the 0x2541C535 key-id
signed post which I proposed we try a signature attack on because of
lack of public key), because I have on my keyring the secret key since
adding the secret key to my key ring from this post which was made to
cypherpunks [1] with headers below (look in the archives, or copied
below):
: From: nobody@REPLAY.COM (Anonymous)
: To: cypherpunks@toad.com
: Date: Tue, 23 Sep 1997 01:58:52 +0200 (MET DST)
: Subject: Persistent Persona
The key in that message was:
Type Bits/KeyID Date User ID
sec 1024/6D5E2425 2041/12/07 TruthMonger
-----BEGIN PGP SECRET KEY BLOCK-----
Version: 2.6.3i
lQHgA4dN5oIAAAEEAM/3b3wHc1iQEmtk9NQhmrHmZmlCdZH4T3kf2APlwA/NRsfU
pAa++0pBdgMMOr9QBMWNWuRuZriEUE/jH9cdMkgBeOrvsviFSe2wN074LrCZSugO
6KabPwokodYl8+R8xY5NC1pZUD4sYf49L6xOwpjiXukrRKqwABp0s99tXiQlAAUR
ARwSOk76t7D7A/0n7XVeJ5qLKatxrzKZ1+U9PLhEeeQkknETkj9aFmRNrj/I4n/Y
TgxKh74zK1/kM4y6bunTNU6+pBDPrvYJgqoq4kMlS3jXNdGBFn0Tw0j2klSZpXzA
Tb593tKD66dztQXiYbYYhydQixUp22NwjruiIfwjFdtU7tOhKfLgZ+dGJQIAH40N
9Gpt3oSQ+ua6I1mOEYzWXdH8HdaNQKxGVRYVH71Wi2TpDLuZbbYq6RB9LDQ0VJO0
6DumKr1OSG32zda+kwIAvjPYd8xEOyCo2NJfL2ZUBh9/GC9nb9UTxdwFP7AFx0F7
DTA+prGb672ly3NAa7/gje2W4isd3NN+T6T13WHmcAH+MnnMDMclF/hNKrhR39aB
1ZvVEBh8yz8xWCm5BQOqp55KyJGgDY0kAcwqejE0PHV8dMG6TVteVvOu7D7GDFcB
4KXvtAtUcnV0aE1vbmdlcg==
=HBLx
-----END PGP SECRET KEY BLOCK-----
which means that anyone can create such signatures.
That PGP correctly copes with signatures made by keys it has only a
private key for (and no public key) is something of a surprise -- PGP
must be smart enough to use the private key if the public key isn't
around on the keyring. (The public key is a subset of private key).
Erk! just tried to create a signed file with that private key, and I
didn't notice before when I commented on the posting of this key that
key has a passphrase! It wouldn't be one of those John Young
forwarded to the list from an anonymous source would it....
Holy smoke! Now we are getting somewhere, the person who remailed
those passphrases to John Young knew that keys passphrase, and yet the
key was posted back in Sep 97!
John Young writes on cpunks:
> This allegedly is forwarded from CJ, though from an unknown source
> so think twice:
>
> "Passwords: sog, sog709, sog709cejCJP,sog709cjpCEJ, D'Shauneaux,
> D'shauneaux, and others..."
The passphrase was sog709. Try it and see. Check in the archives for
yourself for that message, (subject 'Persistent Persona') and become
paranoid!
What is going on here? Is Toto still at large, drunk behind the
keyboard? Is Toto not one person? Or have the IRS extracted Carl
Johnson's passphrases from him and got busy playing mind-games with
us?
Adam
[1]
======================================================================
Date: Tue, 23 Sep 1997 01:58:52 +0200 (MET DST)
Subject: Persistent Persona
To: cypherpunks@toad.com
From: nobody@REPLAY.COM (Anonymous)
-----BEGIN PGP MESSAGE-----
Version: 2.6.2
lQHgA4dN5oIAAAEEAM/3b3wHc1iQEmtk9NQhmrHmZmlCdZH4T3kf2APlwA/NRsfU
pAa++0pBdgMMOr9QBMWNWuRuZriEUE/jH9cdMkgBeOrvsviFSe2wN074LrCZSugO
6KabPwokodYl8+R8xY5NC1pZUD4sYf49L6xOwpjiXukrRKqwABp0s99tXiQlAAUR
ARwSOk76t7D7A/0n7XVeJ5qLKatxrzKZ1+U9PLhEeeQkknETkj9aFmRNrj/I4n/Y
TgxKh74zK1/kM4y6bunTNU6+pBDPrvYJgqoq4kMlS3jXNdGBFn0Tw0j2klSZpXzA
Tb593tKD66dztQXiYbYYhydQixUp22NwjruiIfwjFdtU7tOhKfLgZ+dGJQIAH40N
9Gpt3oSQ+ua6I1mOEYzWXdH8HdaNQKxGVRYVH71Wi2TpDLuZbbYq6RB9LDQ0VJO0
6DumKr1OSG32zda+kwIAvjPYd8xEOyCo2NJfL2ZUBh9/GC9nb9UTxdwFP7AFx0F7
DTA+prGb672ly3NAa7/gje2W4isd3NN+T6T13WHmcAH+MnnMDMclF/hNKrhR39aB
1ZvVEBh8yz8xWCm5BQOqp55KyJGgDY0kAcwqejE0PHV8dMG6TVteVvOu7D7GDFcB
4KXvtAtUcnV0aE1vbmdlcg==
=HBLx
-----END PGP MESSAGE-----
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2
mQENAzOCm1EAAAEIANB5WCFbEjUhNaZ2cEWuh9xcP48QBixzJpxPqGc0Sogj9W1L
ezM5GDF0tZp5ksNbWf5+ErNxXo0yOM7LjDl+sRrEmcbuTkjqPJxG/q4JZ7Al3/FF
h1SFGWpQNz9BPewgHS8/Lp9Ywl+ELeau+FPrr/xmktYifBBaaPUTS5oNMhn4Ih0r
yez6WFn6lRYz+FLsXchjkg+I22tC1aD6iKv/BxCM//GzJ8UNkE7Vx94jZxJ/0vqE
3msqN1coj99okoggWzR5xe/wcLjUjXBw4Z208zhKNEC1AemkJV5HSbztfOgpZOqX
4dwsSDREfFcerM3gusIv3Gz+oU5WPTNSVeg5/HkABRG0GVRydXRoTW9uZ2VyIDx0
bUBkZXYubnVsbD6JARUDBRAzgptRPTNSVeg5/HkBAXUeB/4y3/VlUzua8TVbAiTW
KPXvqTq28XHrhNrTiDWXX7KaFmRyZC20OLbRNtJH1XJUeZv7yhxXkIO2jW6e1i95
MWcx0JAheNjdqKAdNFUVaqs6R2+ySAU7PtfbfVx/RUxsTW8jLfppI7ajTf3E9z3u
nO6NpN/z74DO659tiwfNjT8YoRH3EEomSKNZ3yIGhbyTHv+FOrJs8sQ3jhqmFb37
nr0er1+BWi9Sr2LS7aK+iCK/ZKhUqaofkoo6S/M6nTWKU7RiDhvK0wm40Lassb83
z3NjwN2NNZDwCPYM3d12LjxWA70qljx/qsSRptvkDmnLKXnEUvTsnf9dErhpYLtg
yGBFiQCVAwUQM4LW/7BfjJBm+4xlAQEbJAP/RsKZ/khOS+4nD7JfPnKMKMVjDOif
x0enjzf7kW//GnMsi70yaYi6QeoT0YUYVNQ+wWwGUPgAejs2PLk1VIbn4GIvRU+1
Uj6xTTfHkIibUtvz7LtC/JmNafWSETDnJOlqszgzTnE0duDwZ83ISWdzHkhEXnfC
BxcPay75u1zC6FQ=
=j6da
-----END PGP PUBLIC KEY BLOCK-----
Date: Sat, 19 Sep 1998 22:07:54 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cypherpunks@cyberpass.net
Subject: Toto knows how to make a 0xdeadbeef attack?
As a result of my trawl through my cypherpunks archive last week
looking for publically posted private keys by Toto et al, I grepped
out a selection of encrypted messages sent to the list. I thought I'd
have a go at decrypting these with the selection of passphrases John
Young posted earlier today, in case any were encrypted with the
publically posted keys, or with a conventional encryption key.
I came across this post [1] posted in 5 Sep 97 which contains this
encrypted message, and "challenge" to decrypt it.
Now if you try to decrypt it, it says you need key 0xE6A9C799, the
public key for which is on the key servers. However keyids are
actually stored as 64 bits, internally to PGP messages, but only the
least significant 32 bits are displayed by PGP normally. I use
pgpacket to look at things and it gives you all 64 bits, the message
has keyid:
0xAA33463CE6A9C799
however the key I got off the keyserver [2] has keyid:
0xAA33063CE6A9C799
which differs by 0x400000000000 or one bit. That would require
knowing how to create a 0xdeadbeef key or at least use software to do
this, if it is available.
Unless the bit flip is part of the "challenge". Who knows.
Toto did allude to hacking skills, though largely claimed ignorance.
I wonder if this was feigned, or if there are other Totos who are
doing the key hacks etc. eg this challenge out of bureau42.ml.org
remailer.
Toto is a one man computer crypto forensics persons full-employment
insurance! -- the amount of stuff posted to the list with various
passwords, keys, etc. The IRS guys must be either hiring some one who
knows crypto, or are going to be seriously confused at this point.
Then there's the use of S-Tools, they must be going boggle eyed
guessing passphrases for S-Tools for all the images ever posted
anonymously, or pseudonymously to the list. One wonders almost if
this was his aim.
Any hints Toto(s)? Firstly I haven't got the private key(s) for
0xAA33[0|4]63CE6A9C799, and secondly, what's the deal with the bit
flips/0xdeadbeef attacks?
My september forward secret key is below [3]. It is authenticated by
my high security key, and 12 days time or so, the private key gets
wiped.
Adam
[1]
======================================================================
Date: Fri, 5 Sep 1997 17:31:53 GMT
From: bureau42 Anonymous Remailer <remailer@bureau42.ml.org>
Comments: This message did not originate from the Sender address above.
It was remailed automatically by anonymizing remailer software.
Please report problems or inappropriate use to the
remailer administrator at <remailer-admin@bureau42.ml.org>.
Subject: EFF $10,000,0000 Challenge
To: cypherpunks@toad.com
Sender: owner-cypherpunks@Algebra.COM
Precedence: bulk
X-Mailing-List: cypherpunks@algebra.com
X-List-Admin: ichudov@algebra.com
X-Loop: cypherpunks@algebra.com
The Electronic Forgery Foundation is proud to announce a major
breakthrough in encryption technology -- Forged Encryption.
We are offering a prize of $10,000,000.00 for anyone who can
correctly decipher the following Forged Encryption message.
-----BEGIN PGP MESSAGE-----
Version: PGP for Personal Privacy 5.0
MessageID: od2CIT3fELE7K6bkIkKGJBj0MPUJ2TT8
hQCMA6ozRjzmqceZAQQAh02x0Dxer5vzZiSJ+v7bnMZQdgp425z5OH0NF/f/mXXc
vInw+UsuTXqWNEV5rEQKYjU3qHoe6suCz5f9hEEnOIBacsD28pYU4ahkGOCTuTY6
N3xKrtDRqLPInB8PY7Kfd56jjQsVVRKmJBwXqHbPax4YyUB6ZbKKvSPiuUsAAQSl
BAH3CFNKcmYjf+VtpjAVOpDNM/PMm1e6m33rZ01Sq6pXC0TTabCf7hkWscet0PCL
VX0l1Zw5IKaFqo+pZ3EICRMF6HQrc30G7L9TFeKr//3YsO3/bC4VBgNQHA0qf2nD
ldxAsTGPlRthBTxrzE0LjeOKi/pQOLXQMPQUwEIaL9rncjFgniplFoL6Nj0guJvW
VvS+gxth8hpeWss7WlFFioV0vShsS/lahA+eg/9nVy8ken8pr4m484w2vwoiSdce
CarVigVaRh6tCgh0jub7CHuDFg==
=Q9+G
-----END PGP MESSAGE-----
The EFF doesn't have a copy of the correct answer locked away in
a secret underground cave in Tibet, for verification, because
the above Forged Encryption message is just a bunch of crap we
typed in pretty much at random.
Does the government want to keep your private key in escrow? Give
them a copy of your EFF private key.
Hell, give them _two_ copies, in case one is corrupted.{;>) Smile
when you give them to the government agent. Ask him how his day
has been. Offer him some coffe, and ask about his family. Tell
him you will send him a Christmas card with another copy of your
EFF private key, just in case the government misplaces the copies
you gave them.
Put your hand over your heart, salute the flag, and sing "God Bless
America" as the government agent leaves. Then fart.
Use the EFF Forged Encryption sofware regularly, to send messages
with Subject:'s like "The Plot Against the PREZ," "Confirmation of
the date of our armed assault," "The Nuke has arrived."
Keep a copy of your EFF Forged Encryption secret key in a directory
named "Off the Pigs."
Most importantly, never reveal in your private email to others that
you are a deaf, dumb and blind quadraplegic who has been homebound
since birth. That way, the outrageous claims that government agents
make against you in their secret deposition for a warrant to kick
in your door and terrorize you will look all the more foolish during
your trial.
We at the Electronic Forgery Foundation realize that some of you wise
guys are thinking that, for $10 million, it is well worth your while
to write a program that will decipher the above message into something
meaningful. Well, knock yourself out, dudes, but if you think that
known forgers couldn't possibly be lying about the $10 million, then
go directly to http://www.clueserver/fucking_idiot, do not pass GO
and do not collect $200.
---------------------------------------------------------------------
This message is copyrighted under the auspices of the Electronic
Forgery Foundation. Any misquoting, misrepresentation, or other
abuse of this message would be greatly appreciated. Hell, you can
tell people you wrote it, if you want to. We don't really care.
---------------------------------------------------------------------
[2] (long)keyid 0xAA33063CE6A9C799 (Toto <toto@sk.sympatico.ca>)
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 5.0
Comment: PGP Key Server 0.9.3-db2test
mQCNAzMs140AAAEEAL1CAoB5pd97hIOoT6L0v05Ov8nw0unf0db6NXZ91EJAyq9p
DoPGJl7Z6m5McIsNI2DrCEEt7KYdt0ZIGcqqK2gmCePYI0oQOFj+jznI3jKXg1k2
R+ngk+cUn21EfrNXFGPk1Tuc1/3Qib6cX6BZRJvvz1FNYNt/zqozBjzmqceZAAUR
tBtUb3RvIDx0b3RvQHNrLnN5bXBhdGljby5jYT6JAJUDBRAzgrFaG9qyus40wB0B
AeagA/47sR2GW3y/e3z63ZHqvZwsrNZabNtVsLU6QoEfomfOc0ViI+RY3w5dAjQI
62zCSj/DXaLEwYGNbqVcwjlos5STdoxFqRHpHf6hLCZSNjUaIqY19n0U0qTs6Hw4
WuRURrbMLJYVEgiZpRynmMPnwQ+1USQ1MV6MevboXeJ08lHoDYkAlQIFEDM9HqMi
iRpDQSB+5QEBHJYD/0/VRUy8EAZdjjzx/82+zUJmen9rRI3EQtd+kzInP9V13ZG5
qFFihznQJukXX9A53g9l4RbZo1P+yHF+bdD3OnEbPIWDL/+0Rd3DZp53N1Pigw6A
MGoyvNzYt83zNaoXlxYksBIirBusiSbJlHotQLGYTv1aaBGVAYAd8zDALdYtiQA/
AwUQM4KBc4I3FG4quJ9UEQLr0QCdFQDsbIKVKU6f5olwRSACnq/YtJoAnig/jD9Q
c8CVTPsw++ok1kWZeqXViQCVAwUQM4J+6pfboLn8NWjNAQGTigQAnrFZ8OiAguWq
i1LsClKo0t9y+Ly98EPnpBt2FgQN9/Z8PSZjPqEn9AJk7Z5TBhGJNXBmkULiuNA9
zvGTsRM0S7Oi6/WFUcL9rio6gMsxTnDythGaFa5YDQXgXtFxqcjsojGhe922KFnV
i4xxatO9vm9Zo3JaNAK8zvg2rIrd7VSJAJUDBRAzgn8PsF+MkGb7jGUBAYbmBACV
tqTdmo9Zu/e9hpEL1FQXnp1qzKilzchxf+9/mBmbCy6O/QKVkdUTptkYMVyUHh0q
1KJV4caZIx3vQyeRsK7Fe5vex38LzN9lcP99lOE9Y8nns1bwaiUONe1McWEtkEkG
SMi3FaIxRCb4f5ENjRV8EzydQbHD5+Pyp0+gw9LuXIkBFQMFEDOC1g34yQH5HnUh
EwEBoHAH/RDpelRJCSEtRC7upHwGbfuZL3RhlgXomiOL5plSn2i2El7hm1k1UKcG
UHvcz1ni2deWRK/qLle9xN8wXIjZMATWJLfeSoSpZoq8yFKdN+r2fkpwyN4h6hmb
SI0DBm73eiO7cIRgxszpQDnI5uhTp083JUX/dtFlBMtr/XsIBfg6PN6pYYIAZ1cn
pqkKHHFpdJe3+/AIHzw53nJUKm8EX+Bui1EOfljB63U6oP+Q1F3Wo0C1PaN/9Hbo
3IkVSLC1i3JUQwjh0moFuB+ZeLUFTxBwp+F2Y1AcvQT6JJW529WPTXOvfT2/+wU7
uVaynaHMum8snzPWMr5v0dQbq+6+OPU=
=leOK
-----END PGP PUBLIC KEY BLOCK-----
[3]
Type Bits/KeyID Date User ID
pub 2048/86B519BD 1998/09/10 Adam Back <aba@dcs.ex.ac.uk> (FS key, Sep 98)
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.3i
mQENAzX3ILwAAAEIAL368F4iaAlWFsXFUXdgSttJaHpjcLXmqZP93FlhQRyhSco6
6wyTWEa0UQ25ynf/r/sh4Z7/xjD+HSUUCnpLDJnN9143JUO1UbDIGTq3vC+uKJjr
1OnZQMI0SOrpdUUvbz9zyC2Zsj+CACGbX+sFpecT/XxMpSeEbfoNoy5+AWjB7eIa
27qloHFGRZrDfFvewaSybck21PGVEwkTrpBQ4Yf1RGDod+Xe079jq79uZNNDgnTN
UaFXFS0BmH0nJmjWE5/QkNsgy0aPuFcR65TKn54Fj7e82g1ScEYlwS3iRBuebpAU
pH81flyI4qr9dvBatcpQXut+PxXT+mQxbIa1Gb0ABRO0LUFkYW0gQmFjayA8YWJh
QGRjcy5leC5hYy51az4gKEZTIGtleSwgU2VwIDk4KYkBFQMFEDX3IQ0+e8qoKLJF
UQEBhH4H/3u1USAlPwbGPMfMwZwBU4uCm6EPf03LKgtGa/elSn8nvrSbRrvLVdnQ
aQWJBQpLegUkDlrd0LG9guGdaEJxJ3pZteeaDuC9WeHJWBuUbiyrNooTk7QGeVM1
9yTAW9zaHW/NpXSYL45XfHYuYrKiX50gAY+CSc3rE4Ei++R0gTAwRnS9JkKqsdzP
CJThyy+ppteG5d7aw8L26AQQGUvcZKR3wTvGpGAfU6bZo1gmvnloSYelbxvUfkq2
ybHBZWXj7iBRPwTT6przBVp3DaCm8/gOzUBxvJZkoDsbf/iVBX/Qf8sVGq/86ksB
/JmE7cAVNveJ+a9wx4kTNVmjP7Aciao=
=vpQX
-----END PGP PUBLIC KEY BLOCK-----
Date: Sat, 19 Sep 1998 23:28:19 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cypherpunks@cyberpass.net
Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
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
Date: Sat, 19 Sep 1998 22:39:19 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cypherpunks@cyberpass.net
Subject: (fwd) Re: CHALLENGE? Toto/signature attack w. unpublished public key
[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 <nobody@replay.com>
Comments: This message did not originate from the Sender address above.
It was remailed automatically by anonymizing remailer software.
Please report problems or inappropriate use to the
remailer administrator at <abuse@replay.com>.
Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
To: coderpunks@toad.com
Sender: owner-coderpunks@toad.com
Precedence: bulk
A very interesting problem...
Adam Back writes:
> 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.
Date: Sun, 20 Sep 1998 07:02:05 +0200
From: Anonymous <nobody@replay.com>
Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
To: cypherpunks@cyberpass.net
> > 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?
Actually there is somewhat more flexibility than this. You made up the
padding, it didn't come from the file, did it? You could add perhaps 1
more byte of FF without stretching credibility too extremely. Then n
could be 1020 - 1032 bits. It's too bad that s started out so small
(assuming the "true" n was 1024 bits).
> > 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).
But didn't YOU have to factor n also? That's what you showed, originally,
a large s^e which you factored down to get some small factors and a big
one. If you manage to get a prime factorization you can combine factors
to get your n. But it won't be any harder for him to factor than it was
for you.
> 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.
The discrete log algorithm is similar to quadratic sieve and other modern
factoring algorithms. You do multiple factorizations of other numbers
and combine them to generate the desired relationships. The difference
is that the factor base is not just the primes, it uses special numbers.
There was a break a few years ago of the discrete log modulus being
used by Sun's RPC. This was something like 200-300 bits. Maybe that
discrete log code could be obtained from the authors.
Date: Sun, 20 Sep 1998 09:36:42 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cypherpunks@cyberpass.net
Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
Anonymous writes:
> > > 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?
>
> Actually there is somewhat more flexibility than this. You made up the
> padding, it didn't come from the file, did it?
I used PGP to make an m to match a 1024 bit n which I presumed from a
1024 bit s; s is from the signature packet from the signed post in
question. I made the assumption that for a 1024 bit s, the padded
message digest m would be of size 1024 bit also, with it's leading 00
01 FF ... FF etc.
> You could add perhaps 1 more byte of FF without stretching
> credibility too extremely. Then n could be 1020 - 1032 bits. It's
> too bad that s started out so small (assuming the "true" n was 1024
> bits).
I see what you are saying: that if n had been even 1032 bits, it would
still be possible (though relatively unlikely) to result in a s <
1024, which would mean that the m I presumed could have had been a
byte longer. I think your assumption that PGP would not encode the
leading 0 byte (in the s) is correct, from past PGP code tinkering.
In fact I guess that actually this statement generalises and (with an
even smaller probability) the n could have been 1040 bits, and the s
just happened to come out < 1024 bits, and so on.
I'll see if I can induce this effect by generating a 1025 bit key, and
seeing if any of the signatures come out at 1024 bits:
n = 0x0181291263B847EBEBFDC65E9128DDE9015522B461618F43CDBBF3D707507BA9
A71B002F4F852EEC1465710B1641C8816D3E0851C41C2A11E89062E424116A69
6E0FB179C7439C6C2F88A214E8D9877658A82982783FA5597262D6CD648111EB
A3AB12FC9EB71FB90222624D188E31A3B3333020740860E5F11250D10E2E61F77D
e = 0x11
s = 0x5AA544A471AA79074796D0C85BE01DF44BBED7F14C1189D2D114F8A4E9D4D20E
1E67ED9CFA8E20F4D9B84B9C82918F5721D984C7D3A2E2561D399982DFD38873
3665745849F83EA14A2D2D586CCB253515E63CF81E2C3927D991E25FAE673DEC
E18DB2F6014850CE97F2910393166577F120C4A9512B122F47E05FB117702D6B
So yes, n = 1025 bits, and this particular s is 1023 bits, and this
one is 1025 bits:
s' = 0x012B4B5218E1173DCEF5525C3E9E72BA962371372DA9E9D8D1B469A3BD1060E1
5F0ABA0E0BD9B497944FA9AE039F7F006591470857E0CB4FCB460485307A4366
54105112BD2E548B6BA9E6B950BC37D39A51ADC169B34935D052DFEEEA9A9FFC
BEA4D85BF22D87D66BCB3530EE5316F22A4A4BC4FAB33E592B019E87DE1EAB7336
(most of them work out to be < 1025 bits).
> > > 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).
>
> But didn't YOU have to factor n also? That's what you showed, originally,
> a large s^e which you factored down to get some small factors and a big
> one. If you manage to get a prime factorization you can combine factors
> to get your n. But it won't be any harder for him to factor than it was
> for you.
Yes, you are right.
Presented with two public keys (n,e), and (n',e') and a signature s,
that even if the attacker manages to factor n but not n' the attacker
can't prove that there isn't another public key (n'',e'') which is the
real key which signed the message. Ie the reason the attacker is
unable to factor (n',e') may be either because it is a multiple of two
512 bit primes, or because it is a mutliple of primes of special form
I quoted a post describing in the other post, and he doesn't have
enough compute to recover it. With the quoted algorithm from Maurer,
the attacker needs more compute to show that the key has a special
form than you do to create the key.
Adam
Date: Mon, 21 Sep 1998 13:17:29 +0200
From: Anonymous <nobody@replay.com>
To: cypherpunks@einstein.ssz.com
...
some of the internal key-IDs have been modified. however, both
versions should have been posted in various 'true' messages. No
information if some of the false messages were ever encrypted
with the key twiddles in hidden 32 bits, but probably not.
...
Date: Tue, 22 Sep 1998 03:08:09 +0200
From: Anonymous <nobody@replay.com>
Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
To: cypherpunks@cyberpass.net
This value is wrong: it has 3 bytes of 0's inserted and is therefore
missing the last three bytes of the signature.
s = 0x08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A9007D1801AEAEE6E6
D2C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7A
C28BE916570BA7BB9C00C64DF57113C4AE81613BD351541523CD3A028FBF220E
F7469BD4175302DCB5B6E886974877F28A2D301433AFFFE26081008BFF687B37
Here is the correct value, from the signed message.
08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A97D1801AEAEE6E6D2
C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7AC2
8BE916570BA7BB9CC64DF57113C4AE81613BD351541523CD3A028FBF220EF746
9BD4175302DCB5B6E886974877F28A2D301433AFFFE260818BFF687B37DE8167
Date: Tue, 22 Sep 1998 19:57:09 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cypherpunks@cyberpass.net
Cc: shoulson@cs.columbia.edu
Subject: pgpacket bug (Re: CHALLENGE? Toto/signature attack w. unpublished public key)
Anonymous writes:
> This value is wrong: it has 3 bytes of 0's inserted and is therefore
> missing the last three bytes of the signature.
>
> s = 0x08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A9007D1801AEAEE6E6
> D2C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7A
> C28BE916570BA7BB9C00C64DF57113C4AE81613BD351541523CD3A028FBF220E
> F7469BD4175302DCB5B6E886974877F28A2D301433AFFFE26081008BFF687B37
>
>
> Here is the correct value, from the signed message.
>
> 08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A97D1801AEAEE6E6D2
> C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7AC2
> 8BE916570BA7BB9CC64DF57113C4AE81613BD351541523CD3A028FBF220EF746
> 9BD4175302DCB5B6E886974877F28A2D301433AFFFE260818BFF687B37DE8167
Hmm! That explains this output of pgpacket which I had already
forwarded to Mark Shoulson as a bug in pgpacket:
% pgpacket < totopost.asc
---------------------------
Packet Type: Secret-Key Encrypted Packet (signature)
Length: 149
Version: 3
Adding 5 bytes of header to digest
Signature of canonical text document
Signature Created: 9 Dec 1997 21:29:02
Signing Key ID: 0xCE56A4072541C535
Public Key Algorithm: 1 (RSA)
Message Digest Algorithm: 1 (MD5)
Check bytes: 0x5A82
128 bytes of data (1)
Data: 08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A9007D1801AEAEE6E6D2C68D7E
DF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7AC28BE916570BA7BB9C00C64D
F57113C4AE81613BD351541523CD3A028FBF220EF7469BD4175302DCB5B6E886974877F28A2D3014
33AFFFE26081008BFF687B37
---------------------------
Packet Type: UNKNOWN PACKET!! (36)
Length: 129
(No handler known. Skipping 1 bytes)
Data: 0x67
I couldn't figure out what the spurious packet was about, you just
solved that one... pgpacket is inserting spurious 00s in the message.
(I've Cc'ed Mark Shoulson).
Adam
Date: Tue, 22 Sep 1998 08:01:07 +0200
From: Anonymous <nobody@replay.com>
Subject: CHALLENGE response
To: cypherpunks@cyberpass.net
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2
mQEMAzJEMpEAAAED/0jftmc14q6/r/pGe61N+QymMfQlUdrMNWSl9n9wnst1BGft
/GztVfzwS5QDPc2vAvCJjeYFBj60BbJpILMC6rGH7pnc/GFcQjQDUJzHfGHASkDl
2jvDbzG8f7I5oM6NAC5thtjmMoe9FasHMW+lQ3B3IFNSFgIULM5WpAclQcU1A/0S
K/k9FEU/SX93bC3SqTwwdaW9bvksN6Tqs8YSmVcRCoCAQQrTB9i0I+1y86gA9DnC
UR0EuvalZ54+g/+4G0TOqLVoeSXYhyktqwrIFmwDyK3RPEU6OkwxzlBALNvEKzKB
SsdTm7J6O+jg56yEI3YyyBJM6N+zKvmm7DGB8I2+IbQKVG90bywgdG9vP4kAlQMF
EDYHKcPOVqQHJUHFNQEB7RID/0H14HGr6lB8bqWCxoZfoZ97oHFEURrYVxOGb5MP
ZOOEKCk5d/Q/9d0D0imSZRrV6EQRsiuhA9d0LQy0DuLQC3/NguKFK0Z3fY9gT8/q
xV9JJmmoYTjSEDke0RfexfvNDuOa9aISVxndwYGkkYlUcsZBmOeo1OKPdhWCLbnI
CsB7
=cutG
-----END PGP PUBLIC KEY BLOCK-----
-----BEGIN PGP SIGNED MESSAGE-----
Interested readers may want to verify that the key above does give a
valid signature when applied to the message below.
(It will be necessary to remove any existing key with keyid 0x2541C535
before this key can be added to the keyring.)
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBNgcq+c5WpAclQcU1AQHnZQP+NrThyaPmy8BDw21geFB3B1s59QJJ4Ycs
i1yqu9p6NZfb6qD2pF8AnOSOUMA3KCs98fKMJU9S9TN9eTk5DRbIvXHHSdhMRhuw
qDlmcpy4HggT9yHK0vjOTm6UUR/xkvt0WCheAQEe9ZeshFyPa5BAJ7Sqy2dcI1Xv
X3DzB5pn2yk=
=SmV7
-----END PGP SIGNATURE-----
[Snip PGP signed message given above.]
Date: Tue, 22 Sep 1998 23:41:21 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: nobody@replay.com
CC: cypherpunks@cyberpass.net
Subject: Re: CHALLENGE response
Kudos anonymous!
What form are your primes (did you use Maurers idea to increase the
relative hardness of factoring compared to discrete log, or did you
just use more smaller primes?) How many primes have you used, and how
many CPU hours did it take to calculate the discrete log to discover e?
Also is the code for finding discrete logs given the prime
factorisation of the modulus available?
Obvious counter-measures to this attack on a persistent anonymous
identity are to post more than one signature, or to sign the public
key (as would happen with a self signed PGP public key).
I am left wondering if there are implications of this demonstration
for other protocols (*) involving RSA signatures, where one signed
message is observed before the key is obtained.
- For example, the general case of receiving a message signed by
someone, not having the public key, and looking up the public key on a
key server by keyid (as pgp5.x, and some pgp2.x mail interfaces
automate). With an anonymous individual (and with many peoples keys
where they have poor connection in the web of trust) all you are
aiming to do is to send a message to the author of a given message.
With this attack an attacker who could intercept the key server
lookup, and return an alternate public key with associated
certificates which would match the signature.
Are there other protocols where this attack would have implications?
Adam
(* Toto's impromptu 'protocol' was publishing one signature only, and
then having his machine seized containing the public (and private?)
keys which arguably created the signature). The result of the
identity attack is that Toto's (currently unwanted) proof of
authorship has been called into question.
Date: Wed, 23 Sep 1998 03:00:57 +0200
From: Anonymous <nobody@replay.com>
Subject: Re: CHALLENGE response
To: cypherpunks@cyberpass.net
> What form are your primes (did you use Maurers idea to increase the
> relative hardness of factoring compared to discrete log, or did you
> just use more smaller primes?) How many primes have you used, and how
> many CPU hours did it take to calculate the discrete log to discover e?
N is the product of two primes, but each p-1 has about 16 small prime factors
(about 25-35 bits) to allow calculating the discrete log efficiently. With
this choice of primes it took about three hours to run the discrete log.
> Also is the code for finding discrete logs given the prime
> factorisation of the modulus available?
Here you go. This uses cryptolib by Jack Lacy of AT&T (not to be
confused with cryptlib by Peter Gutmann), available from
ftp://ftp.funet.fi/pub/crypt/cryptography/libs/cryptolib_1.1.tar.gz
/* Calculate discrete log using various algorithms */
/* Algorithms based on Handbook of Applied Cryptography by Menezes et al */
#include "libcrypt.h"
/* Modular multiplication - m1*m2 mod n */
static void
bigMultiplyN (BigInt m1, BigInt m2, BigInt n, BigInt result)
{
BigInt tmp = bigInit(0);
bigMultiply (m1, m2, tmp);
bigMod (tmp, n, result);
freeBignum (tmp);
}
/* Modular addition, m1+m2 mod n */
static void
bigAddN (BigInt m1, BigInt m2, BigInt n, BigInt result)
{
bigAdd (m1, m2, result);
if (bigCompare (result, n) >= 0)
bigSubtract (result, n, result);
}
/* Iterate the pollard rho. Modify x, a, b with next values */
static void
prhoiter (BigInt base, BigInt val, BigInt mod, BigInt order,
BigInt *x, BigInt *a, BigInt *b)
{
int xgroup;
/* First decide what group x is in */
/* This is a cheat to be fast */
xgroup = ((unsigned)(*x)->num[0]+1) % 3;
switch (xgroup) {
case 0:
bigMultiplyN (*x, val, mod, *x);
bigAddN (*b, one, order, *b);
break;
case 1:
bigMultiplyN (*x, *x, mod, *x);
bigAddN (*a, *a, order, *a);
bigAddN (*b, *b, order, *b);
break;
case 2:
bigMultiplyN (*x, base, mod, *x);
bigAddN (*a, one, order, *a);
break;
}
}
/* Pollard rho algorithm for discrete log */
BigInt
pollardrho (BigInt base, BigInt val, BigInt mod, BigInt order)
{
BigInt
x = bigInit(1),
a = bigInit(0),
b = bigInit(0),
x2 = bigInit(1),
a2 = bigInit(0),
b2 = bigInit(0);
int cnt = 0;
for ( ; ; ) {
prhoiter (base, val, mod, order, &x, &a, &b);
prhoiter (base, val, mod, order, &x2, &a2, &b2);
prhoiter (base, val, mod, order, &x2, &a2, &b2);
if (bigCompare (x, x2) == 0)
break;
if (++cnt % 1000 == 0) {
printf ("%d\r", cnt);
fflush (stdout);
}
}
if (cnt >= 1000)
printf ("\n");
if (bigCompare (b, b2) < 0)
bigAdd (order, b, b);
bigSubtract (b, b2, b);
if (bigCompare (a2, a) < 0)
bigAdd (order, a2, a2);
bigSubtract (a2, a, a);
if (bigCompare (b, zero) == 0) {
printf ("Pollard rho failed\n");
exit (1);
}
getInverse (b, order, b2);
bigMultiplyN (a, b2, order, a);
return a;
}
/*
* Do the CRT with multiple congruences. congs are the values that the
* answer should be congruent to, mods are the moduli for each congruence.
* n tells how many in each array.
*/
static BigInt
crtmult (BigInt congs[], BigInt mods[], int n)
{
int i;
BigInt prod = bigInit(0);
BigInt prod1 = bigInit(0);
BigInt sum = bigInit(0);
BigInt quot = bigInit(0);
BigInt rem = bigInit(0);
BigInt dum = bigInit(0);
BigInt inv = bigInit(0);
BigInt term = bigInit(0);
/* Compute product of moduli */
bigCopy (one, prod);
for (i=0; i<n; ++i) {
bigMultiply (prod, mods[i], prod1);
bigCopy (prod1, prod);
}
for (i=0; i<n; ++i) {
bigDivide (prod, mods[i], quot, dum);
bigDivide (quot, mods[i], dum, rem);
getInverse (rem, mods[i], inv);
bigMultiplyN (congs[i], quot, prod, term);
bigMultiplyN (term, inv, prod, term);
bigAddN (term, sum, prod, sum);
}
return sum;
}
/* Pohlig-Hellman discrete log algorithm for composites */
/* Return the exponent such that base^exponent == val modulo mod. */
/* Group order is product of factors[], of which there are n */
/* Assume each factor is to the first power */
BigInt
phlog (BigInt base, BigInt val, BigInt mod, BigInt factors[], int n)
{
BigInt
prod = bigInit(0),
prod1 = bigInit(0),
exp = bigInit(0),
dum = bigInit(0),
b = bigInit(0),
v = bigInit(0);
BigInt *dlogs;
BigInt dl;
int i;
dlogs = (BigInt *) malloc (n * sizeof (BigInt));
/* Compute product of factors to get group order */
bigCopy (one, prod);
for (i=0; i<n; ++i) {
bigMultiply (prod, factors[i], prod1);
bigCopy (prod1, prod);
}
/* Sanity check */
bigPow (base, prod, mod, b);
if (bigCompare (b, one) != 0) {
printf ("Inconsistency in group order on b\n");
fBigPrint (b, stdout);
}
bigPow (val, prod, mod, v);
if (bigCompare (v, one) != 0) {
printf ("Inconsistency in group order on v\n");
fBigPrint (v, stdout);
}
for (i=0; i<n; ++i) {
bigDivide (prod, factors[i], exp, dum);
bigPow (base, exp, mod, b);
bigPow (val, exp, mod, v);
printf ("Trying dlog with factor: "); fBigPrint (factors[i], stdout);
printf ("b: "); fBigPrint (b, stdout);
printf ("v: "); fBigPrint (v, stdout);
/* Special case for 2, pollardrho doesn't work too well on it */
if (bigCompare (factors[i], two) == 0) {
if (bigCompare (b, v) == 0) {
dlogs[i] = bigInit(1);
} else if (bigCompare (v, one) == 0) {
dlogs[i] = bigInit(0);
} else {
printf ("Inconsistent b, v for factor == 2\n");
exit (1);
}
} else {
/* Now find log of v mod b, has group order factors[i] */
dlogs[i] = pollardrho (b, v, mod, factors[i]);
}
printf ("dl: "); fBigPrint (dlogs[i], stdout);
bigPow (b, dlogs[i], mod, b);
if (bigCompare (b, v) != 0) {
printf ("Error in discrete log calc!\n");
exit (1);
}
}
/* Combine results with CRT */
dl = crtmult (dlogs, factors, n);
return dl;
}