
23 September 1998
See related keys: http://jya.com/anonkeys.htm, http://jya.com/totoskeys.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 antigovernment 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 (p1).(q1) ) 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 keyid in the signature. (I say bonus points because the keyid 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 pollardrho factoring code which comes with ssh1.2.26 in the gmp2.0.2ssh2/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/120997encryptbernstein.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 midsentence. 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. Ancay eway pectexay igpay atinlay ustsbay of ildrenchay? 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, piglatin, 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/120997encryptbernstein.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 sameoldsameold 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 terroristI 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 browniepoints, since I am a sorry enough sonofabitch 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 keyid 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 mindgames 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 fullemployment 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 STools, they must be going boggle eyed guessing passphrases for STools 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[04]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 <remaileradmin@bureau42.ml.org>. Subject: EFF $10,000,0000 Challenge To: cypherpunks@toad.com Sender: ownercypherpunks@Algebra.COM Precedence: bulk XMailingList: cypherpunks@algebra.com XListAdmin: ichudov@algebra.com XLoop: 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.3db2test 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 10241031 > 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 STOOLS4.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 p1 > 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: noninteractive 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 : PohligHellman discrete log algorithm, which applies when p1 has all small : factors. The problem is that there also exists a p1 factoring algorithm : which works when p1 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 (p1)/2 is a : product of several 1315 digit (4350 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: ownercoderpunks@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 10241031 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(p1,q1), or equivalently (p1)(q1)/GCD(p1,q1). If you were able to solve discrete logs mod p1 and q1 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 p1 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 10241031 > > 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 200300 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 10241031 > > > 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 keyIDs 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: SecretKey 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 countermeasures 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 p1 has about 16 small prime factors (about 2535 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; } /* PohligHellman 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; }