What Would You Do With a New Form of Encryption? 868
Kip Knight asks: "I've been sitting on an invention for six months now. I'm debating whether to 'give it to the world' or patent it. I would obviously like to feed my family on the fruits of my endeavour but don't see much hope in the open source route. My invention improves upon the 80 year old One-Time Pad encryption turning it into a 'Many-Time Pad'. Since I haven't got my export license to speak about the details yet, I won't describe further. The advantages are proof (i.e. unbreakable) against brute force attacks and known-plaintext attacks (unlike the OTP). The disadvantage is carrying around a very large digital key (which could easily fit on one of those USB memory key fobs). My question is this: Could I sell enough $10 shareware GPG extensions to compensate for not locking in 20 years of patent protection (and the $20,000 to patent it)?" While the claims made by the submittor have yet to withstand the crucial test of time (and prying eyes), if you had developed a new form of encryption, what would you do?
Get the patent... (Score:5, Informative)
What about.... (Score:2, Informative)
You don't lose control when you patent it. (Score:5, Informative)
I say patent it and then decide based on what offers you get. Once you patent it you can shop around for people to license it to. You can define the terms of the license (3 years and then you can offer it as GPL or NOT)
Don't be a fool, its your blood and sweat, you deserve to own it.
Check the FAQ (Score:2, Informative)
Patent it. Then license it. (Score:3, Informative)
Patent:
A grant made by a government that confers upon the creator of an invention the sole right to make, use, and sell that invention for a set period of time.
License:
Official or legal permission to do or own a specified thing. See Synonyms at permission.
I would patent it, then license it. It could be licensed for free use to non-profit groups, and governments could be required to pay a yearly sum.
But that sounds almost too easy to me :)
Kip Knight from Prism Research? (Score:1, Informative)
I suppose Prism Research feels it could use a little venture capital...
Quoting:
What to do first? (Score:3, Informative)
frob.
Patent Pending...... (Score:2, Informative)
it should cost a couple hundred bucks at most.
I have read that the process takes about 2 years before they will get back to you saying YEA or NAY. It is at that point that you must come up with the money for the patent.
The trick is patent PENDING. Once you have put in the request your invention is protected (assuming that the patent office comes back in 2 years to grant the request)
If you believe it will work, then scrape up the dough for the application. Once you have applied, you can then get third party verification, or release your own application to test the market, and still be protected.
P.S. if you are in the USA, check out the Small Business Association, and their SCORE program.
This should get you on the right track.
Re:If you want to make money, patent it (Score:5, Informative)
Note, however, that the claims made by the submittor is basically a laundry list of the kinds of claims that makes seasoned cryptographers go "oh no, not again."
No kidding. Read sci.crypt for a while, and you'll see any number of "revolutionary" encryption schemes, most of which are obviously junk invented by naive crypographer-wannabes. (Note: I'm not a cryptographer, nor do I play one on TV.)
At least the submitter understands that OTP only works if you have a big chunk of shared secret data to use as a pad. However, his mention that OTP is vulnerable to chosen-plaintext attacks makes me think that he's just another crackpot. Think about it--you use the random bits in the OTP only once, and they contain no information about future bits in the pad. Thus, OTP is 100% resistant to chosen plaintext.
My advice: DON'T BOTHER SPENDING ANY MONEY ON PATENTING THIS!!! If you decide that I'm full of it, at least do some serious study into cryptography before giving a dime to a patent lawyer.
get a provisional patent (Score:1, Informative)
Hooray for Snake Oil - Go for it, Patent your Oil (Score:1, Informative)
OTP is not vulnerable to brute force attacks. Unless you use the key more than once. But in that case, it's no longer an OTP, is it?
Known plaintext attacks really aren't applicable to OTPs. Since key material in an OTP can only be used once, if you have any two of the plaintext, the key material, and the ciphertext, you have all the information you need. So what do you mean by OTPs having known plaintext attack weakness? Do you mean that if you have the ciphertext and the plaintext you can recover the keying material? That is certainly true, but doesn't really matter since any intelligent use of OTPs always requires that plaintext and key material NOT be exposed to your enemy, and without two of the three, your enemy provably cannot discover any of the other unknowns. Or do you mean something else?
Your statement and claims so closely match the modus operandi of snake oil crypto vendors that I seriously doubt you have anything of value in your invention.
I suggest you go ahead and patent your idea, then present it to the world. I doubt it will stand up, but hey, you could always form a snake-oil selling company (or use an existing one) to try to recoup your patent expenses. Such companies love to tout "patented" algorithms.
And in the unlikely event your discovery truly is revolutionary, a patent is just good sense.
Go for it!
Re:Hehehehe (Score:5, Informative)
It can't be 'unbreakable' under the normal definition of the word. It's impossible because truly unbreakable crypto requires a key that contains at least as much information as the plaintext, and a 'many-time pad' does not satisfy this precondition.
It would seem to me that this simple observation disproves his claim without even knowing his algorithm.
Re:Mathematically impossible (Score:3, Informative)
That is not correct. Information theory proves that one-time pad is unbreakable. Optimality, on the other hand, is a whole other thing. For one you have to specify what you are measuring: Security? Easyness of operation? Ability to distribute keys easily (like PKC)?
Many people think PKC is best because key distribution is a lot simpler than for most other encryption schemes.
Re:Hehehehe (Score:2, Informative)
For those not clear, let me explain: in an OTP, you might say:
"take pad K (a sequence of random bits) and xor it with plaintext P."
This is both the encryption and decryption step. If you know that I'm likely to be talking about the "World Trade Center", you can then plug that key phrase into the resulting cyphertext at every possible point and look at the result. If you get a message back that looks like:
"T*e atta** **ll *e at ******* on t*e World Trade Center"
you can be pretty sure that you've identified part of the message because the result looks an awful lot like reasonable english. There are statistical ways to do this without having to attack it by eyeballing english. They're even pretty reliable.
Of course, I'm oversimplifiying, but bottom line: I don't see how you can perform "one-time-pad-like" unbreakable encryption and not suffer from this problem without also solving the problem for OTPs.
Now, on to "MTPs". If your idea is: "use an OTP as the generator for a function which produces many pads in a pre-determined sequence", stop now it's been done. If your idea is: "use an OTP plus a permutor as the generators for a function which produces one OTP per unique permutor", stop now it's been done.
I'm not talking about weaknesses. I'm saying you can't patent these ideas because they are as old as the hills.
Re:Hehehehe (Score:5, Informative)
I'm going home now...
Re:Hehehehe (Score:2, Informative)
What does Crypto-Gram say? (Score:5, Informative)
Memo to the Amateur Cipher Designer
Congratulations. You've just invented this great new cipher, and you want to do something with it. You're new in the field; no one's heard of you, and you don't have any credentials as a cryptanalyst. You want to get well-known cryptographers to look at your work. What can you do?
Unfortunately, you have a tough road ahead of you. I see about two new cipher designs from amateur cryptographers every week. The odds of any of these ciphers being secure are slim. The odds of any of them being both secure and efficient are negligible. The odds of any of them being worth actual money are virtually non-existent.
Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. And the only way to prove that is to subject the algorithm to years of analysis by the best cryptographers around.
"The best cryptographers around" break a lot of ciphers. The academic literature is littered with the carcasses of ciphers broken by their analyses. But they're a busy bunch; they don't have time to break everything. How do they decide what to look at?
Ideally, cryptographers should only look at ciphers that have a reasonable chance of being secure. And since anyone can create a cipher that he believes to be secure, this means that cryptographers should only look at ciphers created by people whose opinions are worth something. No one is impressed if a random person creates an cipher he can't break; but if one of the world's best cryptographers creates an cipher he can't break, now that's worth looking at.
The real world isn't that tidy. Cryptographers look at algorithms that are either interesting or are likely to yield publishable results. This means that they are going to look at algorithms by respected cryptographers, algorithms fielded in large public systems (e.g., cellular phones, pay-TV decoders, Microsoft products), and algorithms that are published in the academic literature. Algorithms posted to Internet newsgroups by unknowns won't get a second glance. Neither will patented but unpublished algorithms, or proprietary algorithms embedded in obscure products.
It's hard to get a cryptographic algorithm published. Most conferences and workshops won't accept designs from unknowns and without extensive analysis. This may seem unfair: unknowns can't get their ciphers published because they are unknowns, and hence no one will ever see their work. In reality, if the only "work" someone ever does is in design, then it's probably not worth publishing. Unknowns can become knowns by publishing cryptanalyses of existing ciphers; most conferences accept these papers.
When I started writing _Applied Cryptography_, I heard the maxim that the only good algorithm designers were people who spent years analyzing existing designs. The maxim made sense, and I believed it. Over the years, as I spend more time doing design and analysis, the truth of the maxim has gotten stronger and stronger. My work on the Twofish design has made me believe this even more strongly. The cipher's strength is not in its design; anyone could design something like that. The strength is in its analysis. We spent over 1000 man-hours analyzing Twofish, breaking simplified versions and variants, and studying modifications. And we could not have done that analysis, nor would we have had any confidence in that analysis, had not the entire design team had experience breaking many other algorithm designs.
A cryptographer friend tells the story of an amateur who kept bothering him with the cipher he invented. The cryptographer would break the cipher, the amateur would make a change to "fix" it, and the cryptographer would break it again. This exchange went on a few times until the cryptographer became fed up. When the amateur visited him to hear what the cryptographer thought, the cryptographer put three envelopes face down on the table. "In each of these envelopes is an attack against your cipher. Take one and read it. Don't come back until you've discovered the other two attacks." The amateur was never heard from again.
I don't mean to be completely negative. People occasionally design strong ciphers. Amateur cryptographers even design strong ciphers. But if you are not known to the cryptographic community, and you expect other cryptographers to look at your work, you have to do several things:
1. Describe your cipher using standard notation. This doesn't mean C code. There is established terminology in the literature. Learn it and use it; no one will learn your specialized terminology.
2. Compare your cipher with other designs. Most likely, it will use some ideas that have been used before. Reference them. This will make it easier for others to understand your work, and shows that you understand the literature.
3. Show why your cipher is immune against each of the major attacks known in literature. It is not good enough just to say that it is secure, you have to show why it is secure against these attacks. This requires, of course, that you not only have read the literature, but also understand it. Expect this process to take months, and result in a large heavily mathematical document. And remember, statistical tests are not very meaningful.
4. Explain why your cipher is better than existing alternatives. It makes no sense to look at something new unless it has clear advantages over the old stuff. Is it faster on Pentiums? Smaller in hardware? What? I have frequently said that, given enough rounds, pretty much anything is secure. Your design needs to have significant performance advantages. And "it can't be broken" is not an advantage; it's a prerequisite.
5. Publish the cipher. Experience shows that ciphers that are not published are most often very weak. Keeping the cipher secret does not improve the security once the cipher is widely used, so if your cipher has to be kept secret to be secure, it is useless anyway.
6. Don't patent the cipher. You can't make money selling a cipher. There are just too many good free ones. Everyone who submitted a cipher to the AES is willing to just give it away; many of the submissions are already in the public domain. If you patent your design, everyone will just use something else. And no one will analyze it for you (unless you pay them); why should they work for you for free?
7. Be patient. There are a lot of algorithms to look at right now. The AES competition has given cryptographers 15 new designs to analyze, and we have to pick a winner by Spring 2000. Any good cryptographer with spare time is poking at those designs.
If you want to design algorithms, start by breaking the ones out there. Practice by breaking algorithms that have already been broken (without peeking at the answers). Break something no one else has broken. Break another. Get your breaks published. When you have established yourself as someone who can break algorithms, then you can start designing new algorithms. Before then, no one will take you seriously.
Creating a cipher is easy. Analyzing it is hard.
See "Self-Study Course in Block Cipher Cryptanalysis": http://www.counterpane.com/self-study.html
Publish it.... (Score:3, Informative)
B) The fundimental building blocks for crypto these days are all patent free: You have free hashes, free block cyphers (AES), free public key (RSA). There is no reason for someone theses days to choose a patent-entangled encryption primitive.
C) A one time pad is not vulnerable to known plaintext. I don't know what the poster is talking about. Since one time pads are never reused, the known plaintext tells NO information about the rest of the pad.
D) For the US, you can publish THEN patent, you do have a year between when there is a public disclosure and when you can patent it. This does NOT apply to non-US patents. But since the US is at least half the market, who cares about the rest?
D is really critical, because the post does raise many "snake oil" warning flags. If it's NOT snake oil, he can disclose it and patent it after people at least get a look at it. If it IS snake-oil, then it can be shot down before spending the k$s needed to patent it.
Re:Get the patent... (Score:2, Informative)
This gives you the option of simply not paying any more and releasing it into the wild.
And remember the old axiom - a patent is only worth the money you have to defend it!
-Nano.
Re:If you want to make money, patent it (Score:5, Informative)
analog to inventing a perpetual motion machine.
Not only is the true one-time-pad proven to provide perfect secrecy, we
can also prove that no system that uses less key material can provide
perfect secrecy (at least not for arbitrary plaintext languages).
The results are found in the first half of Claude Shannon's seminal and
quite readable paper:
"Communication Theory of Secrecy Systems", Bell System Technical
Journal, vol.28-4, page 656--715, 1949.
which is available on-line, see:
http://www.cs.ucla.edu/~jkong/research/security
Also, the "known plaintext" weakness of the OTP is a myth. The idea is
that an attacker who knows the plaintext can compute the ciphertext of
any message he chooses, and substitute it for the intended ciphertext.
But the classic OTP is a secrecy system, and attacks on authentication
are irrelevant to its function.
We can, incidentally, also obtain provable authentication, and this also
requires use of one-time keys. Look up "universal hashing" for further
info.
--
--Bryan Olson
Cryptologic Engineer, Certicom Corp
Re:learn to play the patent game (Score:3, Informative)
Re:Is it worth patenting? (Score:3, Informative)
Re:learn to play the patent game (Score:5, Informative)
That's a complete myth. Just think about how easy it would be to mail yourself an unsealed envelope and place your documents in later.
From http://www.forbes.com/asap/2002/0624/066sidebar.h
But don't mail your idea to yourself hoping that the postmark will prove the date you came up with the idea. This oft-tried strategy is filled with legal holes. Instead, file a $10 USPTO disclosure document (see www.uspto.gov/web/offices/pac/disdo.html [uspto.gov]).
From http://www.bpmlegal.com/patqa.html#10 [bpmlegal.com]
Can I protect myself by sealing a description of my invention in an envelope and mailing it to myself?
The mythical "postmark patent" offers no protection whatsoever. Having someone sign your written description as a witness would accomplish the same thing - documenting your date of conception of the idea. You might find our Invention Disclosure Form to be helpful in preparing a detailed written description. It doesn't provide any protection, either, but it will help you get your thoughts in order when you contact a patent attorney (our firm, we hope), and you'll save the 37 cents it would cost to mail it to yourself.
Re:learn to play the patent game (Score:5, Informative)
But Certified mail is.
worthless invention (Score:1, Informative)
If your invention only has 1 pad stored, then when the first pad is used, the rest of them become compromized, since a translation can be made between the first pad and the next. Even if the means of translating between the two requires some other form of encryption, the system is only as strong as its weakest link and thus the one-time-pad is now an RSA scheme.
What makes a one-time-pad the only form of unbreakable encryption is the fact that it is so lead-pipe simple, but this same simplicity makes it impossible to improve upon.
I would also suggest you hire a patent lawyer to search for similar devices...with stuff like this, there's a good chance that somebody's done it already.
Mod Parent Down! (Score:2, Informative)
He is describing how you crack a replacement cryptographic system.
The way this system works is, you take a letter in your alphabet, say E and always replace Es with Rs.
When you "plug in" a peice of text, for instace "world trade center" to a piece of cipher text, you are saying (if the cipher text begins with x)... "ok, I'm going to see what happens when I tell all Xs to become Ws.
In this way, the rest of the text can "fall out" in the way he described. This is because, when you make one replacement that replacement is continued throughout the rest of the doccuemtn. This means there is a pattern, and patterns are the enemy of cryptography.
In a one time pad, there is no pattern. This is because the replacement scheme is different for every letter. This means, even if you "plug in" World Trade Center, it doesn't tell you anything about the rest of the text, because no pattern holds for the rest of the text
The parent text is describing the cracking of a system other than one time pad. This illustrates a fundamental problem with cryptography, that many people are pointing out in this article... it is tough to tell when someone makes a claim, if they know just what the hell they're talking about.
---Lane
Re:Easy. (Score:4, Informative)
Before you go to a lawyer, start an invention journal, document your invention, document how you thought up of the invention, and have two trusted friends read/understand/sign/date every page of it. If the need arises, those two friends of yours have to be credible in a court of law, so don't ask your girlfriend or your family to do this. Then you can go to a lawyer to ask for further advice.
WHO SAID OTP? (Score:2, Informative)
Read the "Memo to Amateur Cipher Designers" (Score:2, Informative)
http://www.counterpane.com/crypto-gram-9810.htm
Re:Easy. (Score:1, Informative)
That's a myth and this way offers no protection.
Independent analysis is ignored or challenged... (Score:1, Informative)
Long story short, the algorithm broke in five minutes. Badly. The designer revised the algorithm. I broke it in ten minutes. We repeated the process a number of times, and it never took longer than about half an hour to flesh out an attack on the algorithm (and not just theoretical attacks, either).
The inventor of the algorithm wouldn't have it, though. The algorithm was secure. He told me that none of my attacks were practical; I wrote programs that demonstrated the attack in mere seconds. He finally told me that I was rigging the attack demos, that I was just jealous for not having thought of it first, and that he was going ahead with using the algorithm in his product.
Moral of the story? Crackpots won't listen to reason. Hire anybody you want; if you won't listen to them, you're just wasting your goddamn money.
Re:learn to play the patent game (Score:1, Informative)
Read the Snake Oil FAQ (Score:2, Informative)
-some cypherpunk
Re:Easy. (Score:5, Informative)
That is true.
With OTP the size of the key and message are identical, and has been proven unconditionally secure. It has also been proven that no encryption with more bits of message than key can ever be unconditionally secure. This means that any cryptosystem with a many time pad or a pseudo random OTP is less secure than a real OTP.
In other words what this guy claims to have invented was proven impossible a long time ago. I find it hard to believe people when they claim to have done the impossible.
Re:Easy. (Score:4, Informative)
I agree, patent the algorithm. Some useful things to remember:
US$20,000 is the initial cost of patenting your algorithm. It may cost upwards of US$1 million to defend it in courts if people piss all over you.
Also, NDA's are hardly ever enforceable. It's best to use a trusted friend or family member if available (we should all be so lucky).
The angel investing approach to funding the patent may work, but you'll probably have to give up a percentage of the proceeds.
Good luck. I hope you're successful!
Mail it to the patent office... (Score:4, Informative)
This loophole exists for people like you who have an idea, but are not willing to pay a patent lawyer without testing it.
PS: This is my first slashdot post, so please be kind...
Re:Most encryption is relativley simple to break (Score:2, Informative)
PGP Timestamping Service (Score:5, Informative)
Well, since this is crypto related, I think an even better way would be to use the PGP Timestamping Service [itconsult.co.uk].
It has several different modes, but basically you just encrypt your ideas, send an email to the timestamper with the encrypted files and it will sign the file, and the signature will contain a timestamp and a serial number.
The signatures are available on a daily basis and are posted weekly at alt.security.pgp for all the world to see.
DON'T MAIL STUFF TO YOURSELF!!! (Score:3, Informative)
there is a way to copyright your stuff cheaply involving a notary -- basically you give the notary a copy and they hang on to it for you. notarys are like government approved honest people.
back to the forging the self-mailing thing -- to forge:
1. mail an empty envelope to yourself with weak tape sealing the flap
2. hang on to envelope for 10 years
3. place patented material in envelope and seal
4. forgery complete, sue for prior art.
other possibilities include steaming open your sealed envelope and replacing the contents.
a visit to the notary usually costs less than $20.
Slightly Skeptical (Score:2, Informative)
A one-time pad is a a sequence of random bits b0..bn.
A plaintext message is a sequence of bits p0..pm with m =< n.
The cyphertext is the sequence of bits c0..cm where ci = pi xor bi.
Since the bi are random, the ci are also random - hence in the absence of the OTP the cyphertext is undecodable.
Important: having decyphered the message, both sender and receiver delete bits b0..bm from their OTPs.
The problem with OTPs is arranging for secure delivery of b0..bn in the first place, without interception.
It seems the poster is suggesting that there is a secure way to use OTPs, without the important step of discarding used bits. This means that bits will be reused according to some function. So in effect the "many time pad" (MTP) is generating a longer stream of "xoring" bits from a b0..bn - that is, the MTP "xoring" bits m0... are constructed according to mi = f(i, b0..bn) - with f presumably being publically available - and the cypher text is given by ci = pi xor mi.
The problem is that for infinitely many i, j, k, f(i, b0..bn) = f(j, b0..bn) = f(k, b0..bn)...
After we have seen enough cyphertext go by (presumably many, many times more than n+1 bits, if f is any good) we will start to learn more and more about b0..bn (xored with some plaintext). Eventually we will collect a library of bits
pi xor f(i, b0..bn), pj xor f(j, bo..bn and so forth where we know that f(i, b0..bn) = f(j, b0..bn), hence we can work out pi xor pj. But this is just the xor of two non-random plaintext messages, which is subject to fairly straightforward attack.
So the upshot of it all is that if f is good then you should be able to (significantly) extend the life of your OTP, but eventually you will have to ditch the b0..bn and get some new ones. However, if for, say, n = 10^9 you get a useful lifetime of, say, 10^18 message bits, then you'll be happy with your scheme for a long time!
That said, you still have to solve the key exchange problem, which is the real stopping point with symmetric crypto systems.
If I were you I'd... (Score:3, Informative)
2) Patent it yourself.
3) Prepare an iron clad NDA/Trade Secret plan yourself.
4) Have a specalist lawyer bullet proof your NDA/Trade secret plan.
5) Hire a lawyer under your bullet proof trade secret plan
6) Hire someone who knows how to start a company while you help protect your ownership rights to your invention under your bullet proof plan.
7) Sell your super product
8) After you have earned enough money for you and your family, take some of the excess cash and pay lawyers to help you find ways to start a patent sharing scheme that grants people license to use your patent if they grant you rights to the inventions they create based on it.
9) If the company you found turns out to bite you make sure there is a poison pill where you as the inventor can open the invention free to the world without negative consequences.
Most importantly, ASK PHIL ZIMMERMAN FOR HELP EVEN IF YOU MUST BEG HIM OR BRIBE HIM. He's been there, and got screwed. Doubtless he learned something about how he would do it the second time around. You see he knows more about this than us Slashdotters.
BTW, if you are looking to hire an experienced software developer or just getting started at project management type. I need a damn job and you need a Gantt for your project. Just kidding, sorta.
Re:Easy. (Score:5, Informative)
The reason it's a myth is that it's perfectly possible to mail yourself an open envelope. Do that a few times when you're 18, wait ten years, and seal them up with a decade of inventions, make a billion dollars.
But there's nothing wrong with the theory, and there are plenty of ways to do something similiar. For example, banks keep track of when people access safe deposit boxes, so you could just rent one of those and stick it in there.
Actually, banks probably provide a service of this exact type.
Of course, the only reason this would matter is if someone steals your invention. If they invent it independently, you gain nothing at all. they've patented your invention, and it doesn't even count as prior art. (It has to be published to be that.)
But the whole thing's stupid. By defination you can't reuse one time pads, so I'm not sure how this even got on slashdot.
OTP (Score:1, Informative)
Re:Hooray for Snake Oil - Go for it, Patent your O (Score:3, Informative)
This probably applies to any cryptosystem, BTW. ;)
Re:Easy. (Score:2, Informative)
You could send yourself an unsealed envelope. The post office doesn't have a problem with that as long as the envelope flap is tucked in.
It would still be your word against someone else's.