Slashdot Mirror
What Would You Do With a New Form of Encryption?
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?
IF you patent the idea, you retain all rights to give it away freely, sell it or whatever, to whomever. If you don't you lose your rights over the invention.
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.
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.
That's "Mr. Soulless Automaton" to you, Bub.
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.
And now you can all laugh at the sick guy (I have a head cold) for describing how a rotating cypher attack can be used against an OTP, thus rendering a century of research moot.
:-)
I'm going home now...
Quote
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
Yeah, we see this all the time on sci.crypt. It's the cryptologic
/ sh annon.html
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
Document everything. Mail it to yourself. The postmark is sufficient proof of the date.
t ml :
:
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).
From http://www.bpmlegal.com/patqa.html#10
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.
But Certified mail is.
One Time Pad is _provably_ unbreakable.
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.
Do you care about the security of your wireless mouse?
Well, since this is crypto related, I think an even better way would be to use the PGP Timestamping Service.
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.
All editorial writers ever do is come down from the hill after the battle is over and shoot the wounded.
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.
If corporations are people, aren't stockholders guilty of slavery?