Crypto-making vs Crypto-breaking
Cypherpunks often think of Crypto as the state-killing technology which will free us all from the clutches of inculcation in the collectivist mentality. It should be noted, however, that advances in complexity theory or quantum computing that would render cryptography useless, would also have a detrimental effect on the state apparatus. So I pose a question. You have two boxes. In the first is crypto so powerful that it will keep peoples data safe for 1000 years, against all advances in mathematics, with perfect forward secrecy. In box number two is technology that will break any crypto designed by mankind in the next 1000 years. You are allowed to take the contents of one of the boxes, and publish it on the Internet. You wish to do maximum damage to the state, free the Sheeple, enable Tim's libertopian vision of the future, crush totalitarian centralized government, and make the world safe for flowers and other living things. Which box do you pick? And why? -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
Which box do you pick? And why?
I ignore the thought experiment and work on something at hand. Launching www.printyourownmoney.com in a few days. The technology that makes digital cash possible is also useful for many other things. I realize there's a place for arguing whether "digital money" can work today, tomorrow, or in two hundred years. But Cypherpunks have already spent more than a decade talking about it. Why not try it for a while, to see if it works? It's not so hard. It doesn't take a billion dollars, or a million, or a hundred thousand. Apparently it takes one engineer, without venture capital, a couple of months. The Lucrative source is MIT X license - basically don't blame me for using it, but do whatever you like. Lucrative has an open API - you could ignore the code and use the API. Or you could ignore both and build your own. Or you could hire me - I'm jobless - to do it for you. Patrick http://lucrative.thirdhost.com/
Patrick writes:
I ignore the thought experiment and work on something at hand. Launching www.printyourownmoney.com in a few days.
Let's see. The mint picks a prime, p, a generator, g, and a random number k, and publishes (p, g, g^k mod p). The mint then signs stuff by raising it to the k power mod p, and not telling anyone what k is. We blind coins by picking a random b, and sending the coin times g^b to the mint, and after the mint raises it to the k power and sends it back, we can reverse engineer coin^k. Perhaps you'd care to publish your p, g, and g^k here on the list, so we can begin hacking them while you finish your pre-launch checkout. :) (Does anyone recall the approximate equal difficulty ratio between bits of factorization and bits of discrete log?) -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
Perhaps you'd care to publish your p, g, and g^k here on the list, so we can begin hacking them while you finish your pre-launch checkout. :) -- Eric Michael Cordian 0+
Lucrative mints support an arbitrary number of simultaneous series, so the g, p, and g^k components will vary, but here's a set to work on. p is straight from Ben Laurie's Lucre paper (8.1). (8.2) gives us a good g as well: 4. g=4 p=ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbe a63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c2 45e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24 117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf 5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c 08ca237327ffffffffffffffff public=1fd29bb747e2db8f3389d7be7abc1a6abb6d7f698f7eb85b49fb83d41be883cd5 de6d6afb802913c5df7621688b91ee647971742fbf8f5ec82873ea72dedfe755e95fe6eb 30d4143645ac43d8660a5d54d837aabaa56be93598a452b6bf951a1be342c4b3dd53a0a5 64bdabb6802f408472a9bdfefea909bc224af381d52bb3b4e21401888b2b053b82d422d1 ac0a6f2ae35d33da9b1b69951eeef73d09da617ad01cb18017374423de47ee3de33730ac be0a86f55c2764f9a01e377175b785d Knock yourself out! If you can identify a weakness, I would be very grateful. Patrick http://lucrative.thirdhost.com/
At 04:33 PM 5/3/2003 -0600, Patrick wrote:
Which box do you pick? And why?
I ignore the thought experiment and work on something at hand.
Launching www.printyourownmoney.com in a few days.
I don't need no stink'n web site to print my own money. Been 'doin it for years. Just need the right paper, Photoshop and a good dye sublimation printer. Hehe steve
I'll take this challenge, silly as it is. On Saturday, May 3, 2003, at 01:50 PM, Eric Cordian wrote:
Cypherpunks often think of Crypto as the state-killing technology which will free us all from the clutches of inculcation in the collectivist mentality.
It should be noted, however, that advances in complexity theory or quantum computing that would render cryptography useless, would also have a detrimental effect on the state apparatus.
So I pose a question. You have two boxes. In the first is crypto so powerful that it will keep peoples data safe for 1000 years, against all advances in mathematics, with perfect forward secrecy.
In box number two is technology that will break any crypto designed by mankind in the next 1000 years.
You are allowed to take the contents of one of the boxes, and publish it on the Internet. You wish to do maximum damage to the state, free the Sheeple, enable Tim's libertopian vision of the future, crush totalitarian centralized government, and make the world safe for flowers and other living things.
Which box do you pick? And why?
By "any crypto designed by mankind" I assume you are excluding one-time pads, which are not breakable by any amount of computer power and any amount of mathematical knowledge. I assume you are referring to public key approaches, where _conceivably_ mathematical advances or almost inconceivable advances in computer power could result in PK ciphers being broken. Assuming your conditions are exactly as you state, I would of course pick box number ONE. We still outnumber those in government, and what they have to hide is mostly of little interest to me or my causes (troop movements, submarine positions, etc.). Also, they can easily fall back to courier-delivered one-time pads, which are not part of the assumption, as I see it. (If you are including even one-time pads being broken, then you are assuming magic, which is not interesting.) Thus, having a way to securely and untraceably communicate and transact business is much more important than being able to read THEIR bullshit communications. That was easy. And the cool thing is that every indication is that cipher-making is still pulling away from cipher-breaking by leaps and bounds, so it looks to me that we are falling further into the right choice. --Tim May "That government is best which governs not at all." --Henry David Thoreau
Tim writes:
I'll take this challenge, silly as it is.
Yes, please humor me. I do so yearn to be entertained.
By "any crypto designed by mankind" I assume you are excluding one-time pads, which are not breakable by any amount of computer power and any amount of mathematical knowledge. I assume you are referring to public key approaches, where _conceivably_ mathematical advances or almost inconceivable advances in computer power could result in PK ciphers being broken.
I would exclude one-time pads equal in length to the message. I would include all public key crypto, and all use of symmetric block ciphers where an attacker given both the correct key and a wrong key could tell which was which. Let's assume the "technology" in box two can do big exponential searches almost instantly.
Assuming your conditions are exactly as you state, I would of course pick box number ONE.
We still outnumber those in government, and what they have to hide is mostly of little interest to me or my causes (troop movements, submarine positions, etc.). Also, they can easily fall back to courier-delivered one-time pads, which are not part of the assumption, as I see it. (If you are including even one-time pads being broken, then you are assuming magic, which is not interesting.)
While government secrets may be of little importance to you, governments might very well be harmed if all those years worth of secure phone conversations, faxes, and other communications stored in the archives of various intelligence agencies were suddenly decrypted en masse and made public. Consider the economic impact of SSL no longer hiding your credit card numbers from hackers, or ssh being no more secure than telnet. The cost of having no secure communications without the parties meeting to exchange one-time pads generated by nuclear decay would run into the many billions.
Thus, having a way to securely and untraceably communicate and transact business is much more important than being able to read THEIR bullshit communications.
That was easy.
And the cool thing is that every indication is that cipher-making is still pulling away from cipher-breaking by leaps and bounds, so it looks to me that we are falling further into the right choice.
Cough. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
At 04:58 PM 05/03/2003 -0700, Tim May wrote:
I'll take this challenge, silly as it is.
What Tim said ...
On Saturday, May 3, 2003, at 01:50 PM, Eric Cordian wrote:
It should be noted, however, that advances in complexity theory or quantum computing that would render cryptography useless, would also have a detrimental effect on the state apparatus.
I'm not sure how detrimental an effect it would have. Most of the evil things that the State can do don't depend on secrecy; the day-to-day bureaucracy doesn't care, and Brinworld would have much more of an effect on them (i.e. people actually bothering to watch their bureaucrats in action, as opposed to wiretapping them.) Disrupting the banking system and online trade is much more of an issue, because tapping the flow of money is critical to the state, and if it's not flowing, they've got problems. Governments like secrecy, and if they assume that they have it, individuals working for more willing to do things that would get them fired, shot, or hanged, and the military would have to go back to sending guys with briefcases handcuffed to their wrists to haul one-time pads around for tactical applications, and jackboot-net the rest of their planning data, which would be annoying but isn't much different from 100 years ago, when we managed to have a War To End All Wars just fine. Tax collectors can work perfectly well without privacy, as long as they don't mind violating their subjects' privacy -- which they don't. Welfare-state bureaucrats and case-workers can redistribute income and poke into people's family business without crypto-privacy.
So I pose a question. You have two boxes. In the first is crypto so powerful that it will keep peoples data safe for 1000 years, against all advances in mathematics, with perfect forward secrecy.
In box number two is technology that will break any crypto designed by mankind in the next 1000 years. .. Which box do you pick? And why?
The problem, of course, is that you don't get to pick :-) We have crypto that lets you keep your data secure against however many iterations of Moore's Law you believe will happen in your lifetime (unless you believe Nanotech will save us all.) Quantum crypto could trash public-key crypto, and we'd have to resort back to keyserver-based systems like Kerberos. The real risks aren't from picking the front door locks - they're from the back doors. Smart Dust isn't very dusty yet, and Brinworld ubiquitous cameras aren't ubiquitous yet either, but that 10000-bit RSA key and 7-DES don't do much good if you can't enter the keys into your computer securely or read the decrypted results without the dust on your Smart Contact Lenses also reading them or the cameras across the room watching your eyes move (either the hidden ones, or the wall-screen interactive TV ones) or Microsoft Patriotware or Back Orifice relaying your keystrokes to fbivax. Brinworld ain't pretty, but the important tax in the future won't be the cash you pay, but the N% of your time you have to spend watching your government officials at work, and the main way to minimize it is to decrease the number of government workers that need watching.
Eric Cordian wrote:
In box number two is technology that will break any crypto designed by mankind in the next 1000 years.
Such a machine cannot exist. Proof: Let O be an oracle such that any encrypted message, E can be decrypted by O. That is, if E=Enc(M), then O(E)=M. Now, encrypt a message I as follows. If bit 0 of I (I_0) is 1, then choose E_0 s.t. the MS bit of O(E_0)=0 If bit 0 of I is 0, then choose E_0 s.t. the MS bit of O(E_0)=1 Then for each subsequent bit, proceed as follows: If I_n is 1, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS bit that is 0. If I_n is 0, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS bit that is 1. Then the encrpytion of I is X=E_N||E_{N-1}...||E_0, and, by construction, O(X) != I. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff
Ben Laurie wrote:
Such a machine cannot exist. Proof:
Let O be an oracle such that any encrypted message, E can be decrypted by O. That is, if E=Enc(M), then O(E)=M. Now, encrypt a message I as follows.
Let S be the set of all bitstrings. Let, C, the set of all ciphers, be the set of all finitely denumerable primitive recursive injections of S into itself. Let O, our oracle, associate with each M in C a map M', from range(M) onto S, such that for x,y in S and y = M(x), x = M'(y).
If bit 0 of I (I_0) is 1, then choose E_0 s.t. the MS bit of O(E_0)=0 If bit 0 of I is 0, then choose E_0 s.t. the MS bit of O(E_0)=1
Then for each subsequent bit, proceed as follows:
If I_n is 1, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS bit that is 0. If I_n is 0, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS bit that is 1.
Then the encrpytion of I is X=E_N||E_{N-1}...||E_0, and, by construction, O(X) != I.
Bzzzzzzzzzzzzzzzt. While we may without loss of generalization view O as acting on bitstrings, by encoding the ciphers and their inverses, neither the domain nor range of O is going to be the set of all bitstrings. Ergo, we can not simply "choose" things based on the application of O to bitstrings we arbitrarily construct. Your proof can be fixed, of course, but I think you'll find that it boils down to the usual diagonal argument that we can find a function on the integers which is not primitive recursive, by ordering the countable set of primitive recursive functions, and defining a new function that is for an input of N, something other than the output of the Nth function for N. As long as we restrict the ciphers to a countable set of "reasonable" computer programs which halt for all inputs and don't have neverending descriptions, the oracle exists, and your proof does not.
Cheers,
Cheers, -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
participants (6)
-
Ben Laurie -
Bill Stewart -
Eric Cordian -
Patrick -
Steve Schear -
Tim May