Protocol Wanted!!
Here is a simple problem. Late one night, Bob discovers a clever new method of factoring large products of distinct odd primes. Bob may now perform such factorizations in only a few hours for numbers up to 1024 bits on his trusty old 486. Bob spent a lot of time coding and testing his new algorithm, and wishes to recover some of his expenses by factoring a few RSA keys for well-to-do clients. Bob wants to do this without disclosing his identity, so a certain evil three-letter agency will not cover him with rubber hose marks trying to learn how his algorithm works. Alice is the CEO of a company who suspects PGP-encrypted mail is being used by an employee to transfer trade secrets to a foreign competitor. Alice would pay any amount of money to read this mail and confirm her suspicions. Alice is a potential client for Bob. Now for the hard part... How does Bob make Alice, and other potential clients, aware of the service he wishes to offer? How do Bob and Alice conduct business anonymously while making absolutely sure that neither is spoofing the other? Alice needs to know Bob isn't lying about being able to factor. Bob needs to know Alice has the means to pay him before he cracks a key. Bob and Alice need to exchange a factored key for money with no chance that either will back out at the last moment and try to steal from the other. How much work should Bob expect to come his way if he charges $10 a bit for his factoring service? $100 a bit? $1000 a bit? Comments anyone? -- Mike Duvos $ PGP 2.6 Public Key available $ mpd@netcom.com $ via Finger. $
Commenting on Mike Duvos's original article:
Here is a simple problem.
Late one night, Bob discovers a clever new method of factoring large products of distinct odd primes. Bob may now perform such factorizations in only a few hours for numbers up to 1024 bits on his trusty old 486.
Bob spent a lot of time coding and testing his new algorithm, and wishes to recover some of his expenses by factoring a few RSA keys for well-to-do clients. Bob wants to do this without disclosing his identity, so a certain evil three-letter agency will not cover him with rubber hose marks trying to learn how his algorithm works.
Alice is the CEO of a company who suspects PGP-encrypted mail is being used by an employee to transfer trade secrets to a foreign competitor. Alice would pay any amount of money to read this mail and confirm her suspicions.
Alice is a potential client for Bob. Now for the hard part...
How does Bob make Alice, and other potential clients, aware of the service he wishes to offer?
How do Bob and Alice conduct business anonymously while making absolutely sure that neither is spoofing the other? Alice needs to know Bob isn't lying about being able to factor. Bob needs to know Alice has the means to pay him before he cracks a key. Bob and Alice need to exchange a factored key for money with no chance that either will back out at the last moment and try to steal from the other.
How much work should Bob expect to come his way if he charges $10 a bit for his factoring service? $100 a bit? $1000 a bit?
Comments anyone?
-- Mike Duvos $ PGP 2.6 Public Key available $ mpd@netcom.com $ via Finger. $
Of the several problems stated above, I find the pricing protocol the easiest to deal with. There are a few things that need to be known. For example, what is the complexity of Bob's algorithm? Does it do it in polynomial time or (even better) some variant of logarithmic time? The cost should bear relation to this fact. The cost should also be related to the number of bytes in the message. If Bob was canny enough, he probably would set the price P (in $ or DM or Magic Money or any other currency I'm grouping under the title "cypherbucks") to be: P = F(KB) * L * D where K (in bits) is the length of the key, L (in bytes) is the length of the message, D (in cypherbucks/bytes) is the "decoding" cost, B (in cypherbucks/bits) is the "factoring" cost for the key, and F is a function from the set of cypherbucks amounts to itself that is proportional to the complexity of Bob's algorithm. If the algorithm is logarithmic, F should be logarithmic. If the algorithm takes O(n^2) time, F should be O(n^2); and so on. There are other choices for deriving P; one such is: P = F(KB) + (L * D) and of course others can make their own up. Of course, it is assumed that Bob is operating as a monopoly, and can set whatever pricing policy he pleases. For example, 20% discount for students and unemployed. He could even barter for goods ("I'll decode this 100K message for one of your Cray computers.") If the monopoly disappears, the price would be driven down. Alas, I can't say anymore at the moment. Study beckons. :-( I hope this was of some help. ======================================================= | Peter Murphy. <pkm@maths.uq.oz.au>. Department of | | Mathematics - University of Queensland, Australia. | ------------------------------------------------------- | "What will you do? What will you do? When a hundred | | thousand Morriseys come rushing over the hill?" | | - Mr. Floppy. | =======================================================
Peter Murphy <pkm@maths.uq.oz.au> writes:
Of the several problems stated above, I find the pricing protocol the easiest to deal with. There are a few things that need to be known. For example, what is the complexity of Bob's algorithm? Does it do it in polynomial time or (even better) some variant of logarithmic time? The cost should bear relation to this fact.
[Thud](Sound of Bruce Henderson fainting) This is an interesting perspective. I would find myself arguing almost the opposite. It would seem to me that the price one charges for a product or service should depend only on its value to ones clients. Not upon ones cost to produce it. If the value of your product to your customers is $100,000, then the price should be $100,000 regardless of whether it costs you $1 or $10,000 to make.
The cost should also be related to the number of bytes in the message.
I'm not sure about this either. A short message about a hidden bomb which reads "under your chair" is infinitely more valuable than a lengthy message containing the last six months of postings to rec.pets.cats. Once Bob gives Alice the factors, all messages encrypted with that RSA public key can be decrypted, so the number of messages and the length of each aren't really an issue. Bob could keep the factors and sell Alice the plaintext of individual messages, but this requires a continuing business relationship which the anonymous Bob may not want. If the messages contain confidential information, Alice may not want Bob to see them. Since Alice is paying Bob big bucks to factor the key, it is unlikely Alice would agree to let Bob keep the factors to himself. -- Mike Duvos $ PGP 2.6 Public Key available $ mpd@netcom.com $ via Finger. $
Peter Murphy <pkm@maths.uq.oz.au> writes:
Of the several problems stated above, I find the pricing protocol the easiest to deal with. There are a few things that need to be known. For example, what is the complexity of Bob's algorithm? Does it do it in polynomial time or (even better) some variant of logarithmic time? The cost should bear relation to this fact.
[Thud](Sound of Bruce Henderson fainting) This is an interesting perspective. I would find myself arguing almost the opposite. It would seem to me that the price one charges for a product or service should depend only on its value to ones clients. Not upon ones cost to produce it.
Not quite. I thought that the price that Bob would set would be as high as he could get away with, without alienating the clients. If Alice sends Bob a message to be decrypted, and shells out $100,000, then Bob (assuming he's honest) will decrypt it. It's too bad if it turns out to be just a juicy love letter - Bob's purpose was there to decrypt it, and not to work out the value to the customer. After all, if it turns out that the file was actually a design to some FTL vehicle, then setting a flat price in the negotiation phase prevents Bob from going around and upping the price to $10,000,000.
If the value of your product to your customers is $100,000, then the price should be $100,000 regardless of whether it costs you $1 or $10,000 to make.
I'm sorry - we seem to be thinking differently. The way I was thinking was that Alice was actually giving Bob the message only, and that Charlie (our suspected criminal) was smart enough to keep his public key away from the office (or on a floppy disk). Of course, if Charlie is stupid enough to leave his public key around, then Alice can send only this key to Bob, and leave the 'naughty' message at the office. Otherwise, Bob has only the ciphertext to go on - or possibly a bit of plaintext, although Alice probably won't do that either.
The cost should also be related to the number of bytes in the message.
I'm not sure about this either. A short message about a hidden bomb which reads "under your chair" is infinitely more valuable than a lengthy message containing the last six months of postings to rec.pets.cats.
But again, that's assuming that Alice does know what is in the encrypted file. She (rightly) suspects that Charlie is giving stolen goods away.... but she doesn't know that. See above. Anyway, Bob may have other clients, and the time on his 486 is fairly precious.
Once Bob gives Alice the factors, all messages encrypted with that RSA public key can be decrypted, so the number of messages and the length of each aren't really an issue. Bob could keep the factors and sell Alice the plaintext of individual messages, but this requires a continuing business relationship which the anonymous Bob may not want.
If the messages contain confidential information, Alice may not want Bob to see them. Since Alice is paying Bob big bucks to factor the key, it is unlikely Alice would agree to let Bob keep the factors to himself.
Ooh.. this is a tough subject to police. It is possible that we have a company rep (Denise - isn't alphabetical naming beautiful :-)) looking over Bob's shoulders while he's doing his stuff, and checking that he's not saving the information to a private file. Possibly, Bob would do the encrypting in Denise's office. After all, he may have built in an option that saves all information acquired to a "key ring". Denise does not want him to do this, and makes sure that he only bring the executable file with him. She also makes sure that no suspicious files are created . Remember that Bob does not want to give the program to Denise - it contains his secret special recipe for factorization, and doesn't want anyone else to examine the program too closely.
-- Mike Duvos $ PGP 2.6 Public Key available $ mpd@netcom.com $ via Finger. $
======================================================= | Peter Murphy. <pkm@maths.uq.oz.au>. Department of | | Mathematics - University of Queensland, Australia. | ------------------------------------------------------- | "What will you do? What will you do? When a hundred | | thousand Morriseys come rushing over the hill?" | | - Mr. Floppy. | =======================================================
From: Peter Murphy <pkm@maths.uq.oz.au> Date: Sun, 12 Jun 1994 14:40:54 +1000 (EST) > It would seem to me that the price one charges for a product or > service should depend only on its value to ones clients. Not quite. I thought that the price that Bob would set would be as high as he could get away with, without alienating the clients. Value can be reasonably defined in terms of what the market will bear. Rick
participants (3)
-
mpd＠netcom.com -
Peter Murphy -
Rick Busdiecker