- cypherpunks-legacy@lists.ogf.org

Re: Software Patent Institute
by norm＠netcom.com 11 Aug '93

11 Aug '93

I am interested in the issue of patenting ideas that have already been put into practice or that would be obvious to any of many practitioners. I have a patent and my patent attorney included in the ideas that were not new. We were not motivated to spend the time and money to revise the patent to avoid this. The patent examiner had little experience in programming and missed the old ideas. I would be curious to know what software patents exist and the outcome of any court fights to overturn patents on ideas that were indeed not new. I am not good a keeping track of publications where I have learned of ideas but I often do know people who were using various ideas going back to 1955 when I began programming professionally. I do not know very much about patent law but I understand that IBM, for instance, regularly publishes "Technical Disclosures" which is mostly comprised of the work products of IBM patent attorneys when they have decided that it is not worth the expense of patenting some particular idea. It would be good to have a public repository of programming ideas that are good but not worth patenting. Let me know how I can help.

1 0

Re: How long would it take?
by smb＠research.att.com 11 Aug '93

11 Aug '93

Its generally unwise to make the assumption that the only possible attack on your conventional scheme is a brute force attack. Certainly the attacks used on many previous generations of cryptosystems were never brute force -- and certainly every generation of naive cryptographer has said "well, using brute force it would take N years to break my cypher". A simple vingenere cypher with a 12 letter key would seem to be very strong indeed (stronger than DES), and yet we know you can break one in a few moments because there are better attacks than brute force. We have suprisingly little in the way of general theory on what would or would not make a conventional cryptosystem strong. Certainly differential cryptanalysis will not be the last thing people come up with. Until we know everything the NSA knows, I will be hesitant to say "unless something better comes up" and more comfortable saying "until something better comes up." Indeed. The key length is a worst-case analysis for the cryptanalyst; they can do no worse than that. We can be confident that NSA has cracked DES because an exhaustive search engine is within their means, but we don't know how much better they can do. A while back, Shamir gave a talk on differential cryptanalysis here at Murray Hill. He mentioned Coppersmith's letter, which said that IBM knew about differential cryptanalysis back when they built DES, and they designed it to resist the attack. That's obviously the case -- so Shamir said that he asked Coppersmith to state that in the intervening 18 years, IBM had not come up with a stronger attack on DES. Coppersmith was silent, from which you can draw any conclusions you wish.

1 0

Re: Secure voice software issues
by hfinney＠shell.portal.com 11 Aug '93

11 Aug '93

A couple of comments on the cryptophone idea. First, there has seemed to be general agreement in our earlier discussions of this concept that the hard part is compressing the voice to the point where it can go over commonly-available modems. The government-standard CELP algorithm is too slow for general-purpose home computers. You need an algorithm that can operate in real time and compress intelligibly down to about 13K bits per second. It has to be either able to compress and decompress simultaneously or else you need some switching logic to decide which person is talking and which is listening at each moment, with both sides reversing roles in synchrony. Second, Diffie-Hellman key exchange will probably take about as long as an RSA decryption with similar modulus sizes. So speed would not seem to be a reason to choose DH over RSA for key exchange. If PGP is slow on your machine, DH will be, too. Hal Finney hfinney(a)shell.portal.com

1 0

How long would it take?
by williacw＠vuse.vanderbilt.edu 11 Aug '93

11 Aug '93

Could the NSA reverse PGP encryption on a message that was iencrypted with a 1264bit key? Do you think they could do this in a matter of hours? Why, or why not? How long would it take? What do you know that corroborates this? This is a genereic question, which I hope aeveryone who knows about this will attempt to answer. If this is not the right subject for the LIST, send replies via EMAIL to wesley(a)ctrvax.vanderbilt.edu Thanks

4 3

Re: How long would it take?
by collins＠newton.apple.com 11 Aug '93

11 Aug '93

>How does your "Yes" wash with the next paragraph of your note? I'm sorry. My answer was misleading (read 'wrong'). What I was trying to say was: "Yes, but not in a reasonable amount of time." My implication was that an attack against RSA with a 1264 bit key and an attack against IDEA with a 128 bit key are both prohibitive, but that my _guess_ is that cryptanalysis of the IDEA cypher would be the more fruitful attack. If the real question is: "Am I safe from the NSA when I use PGP and encrypt with a 1264 bit key?" Then I must answer: "In my opinion, you are reasonably safe." If the question is: > Could the NSA reverse PGP encryption on a message that was encrypted with a > 1264 bit key? Then I must answer: "Yes, it is mathematically possible; although unlikely in the extreme." I apologize. >Sorry I didn't include more numbers, ...really sorry. They said what I meant. >And IDEA is not susceptible to diff.cryptan - that's the way >it was *designed* (actually the designer proved mathematically >the invinsibility of IDEA to this attack). Thanks for this info. I have been trying to get the IDEA papers: "Detailed Description and a Software Implementation of the IPES Cipher" "Markov Ciphers and Differential Cryptanalysis" without success, as yet. Perhaps you have them or know of an ftp site? Thanks, Scott Collins | "Few people realize what tremendous power there | is in one of these things." -- Willy Wonka ......................|................................................ BUSINESS. voice:408.862.0540 fax:974.6094 collins(a)newton.apple.com Apple Computer, Inc. 1 Infinite Loop, MS 301-2C Cupertino, CA 95014 ....................................................................... PERSONAL. voice/fax:408.257.1746 1024/669687 catalyst(a)netcom.com

1 0

Chaos harnessed for encryption / Fluctuations and Order research
by gnu 11 Aug '93

11 Aug '93

EE Times, Aug 9, 1993, p. 31 reports that "MIT's Research Lab of Electronics is creating new signal processor designs, based on chaos theory, that could open up a simple route to secure communications. The new designs use a recent discovery called synchronized chaos to transform a meaningful signal into what only seems to be random noise., A similarly constructed receiver responds to the noisy signal, sychronizing its own chaotic behaviour to extract the message. The MIT design requires only eight op-amps and is based on the Lorenz attractor, which generates a simple three-dimensional chaotic system." There's more, this is just a pointer. Their current encryption system is analog, not digital, and encrypts analog signals like audio; I don't know if this is a fundamental design property or not. They claim it's not super-great encryption, just cheap and interesting. Wired Sep/Oct 93 also reports (p.118) a Sep 9-12 conference on "Fluctuations and Order" at Los Alamos National Labs' Center for Nonlinear Studies. "The labs are gathering a couple dozen researchers who have realized they can induce order into systems by using noise and randomness. As one abstract says, `The addition of noise to certain types of driven systems can paradoxically cause a signal to become clearer.'" These seem related, to me. John

3 2

Cryptographics Journals
by henrik＠stat.tamu.edu 11 Aug '93

11 Aug '93

Hi, could anyone mail me info on the Cryptology oriented journals like Cryptologia and Journal of Cryptology? Specifically, how do I subscribe to them? Thanks. - Henrik

1 0

New Chaos?
by Kent Hastings 11 Aug '93

11 Aug '93

New Chaos? John Gilmore wrote: >EE Times, Aug 9, 1993, p. 31 reports that "MIT's Research Lab of >Electronics is creating new signal processor designs, based on chaos >theory, that could open up a simple route to secure communications. ... >The new designs use a recent discovery called synchronized chaos to >transform a meaningful signal into what only seems to be random >noise... I saw something like this in the latest Scientific American, but is it new?? >From my survey of spread-spectrum techniques, this 1950's approach to signal hiding is called a "Transmitted Reference." Random thermal noise in a resistor was transmitted in one band, and the same noise mixed with a message was sent in another. The receiver would take the the difference between the two noisy signals to get the message. Although casual snoopers would be thwarted, the key is broadcast openly, therefore this should not be considered secure. Mix it with modern Stored Reference techniques like frequency-hopping, direct- sequence, and time-hopping and you might get a great hybrid system. Are there any freeware spread-spectrum designs, analogous to PGP, to solve the physical data communications problem? Encryption is great, but the phone company is enemy territory. bypass. Bypass. BYPASS!!!! Kent <jkhastings(a)aol.com>

1 0

Re: Chaos harnessed for encryption / Fluctuations and Order research
by Peter Wayner 11 Aug '93

11 Aug '93

There was a paper several years back in Cryptologia that came to the conclusion that many of the chaotic functions were unsuitable for encryption. By this, they mean the "classic" chaotic functions like the Lorentz attractor. DES is obviously a very nice chaotic generator. The problem with the systems has its basis in the philosophical foundations of the field. Mathematicians have been basically saying, "Like Wow. These very simple equations just generate stuff that is totally out of whack." The equations are just simple differential equations that go kablooie. In many cases, though, the kablooie only means that a small pertubation in the system causes large changes in the outcome. While this is a necessary effect for solid encryption, it is not sufficient for a good system. What we really want to know is whether you can recover x from f(x) where f is the encryption function. if f(x+small value) is wildly different from f(x), then this is good, but not good enough. Now, think a minute about the "synchronization" of these two chaotic generators. This means that both ends of the conversation have set their scramblers to the same "key". But since this is analog, things might not be _exactly_ the same on both ends. If this was a really chaotic system then the tiny differences in the two systems should make things go kablooie. My guess is that they figured out some way to use a feedback mechanism to fix small pertubations and keep things from going kablooie in a small range. I would guess that this could lead to a hole for attacking the system. Just a guess, though. This insight is similar to the holes that people found in linear feedback shift registers. These systems are pretty good random number generators, but they're not secure if the user can guess a few bits of your message. Why? Because the equations are simple enough to be inverted. The only question is whether the chaotic equations can be inverted. I think that the Cryptologia paper came to the conclusion that it could be done. I'm sorry I don't have a complete reference to the Cryptologia paper. Perhaps my memory is a bit flawed here as well. It would be interesting, though, to study the EE times article in depth. I think John is right that there is a certain amount of philosophical convergence between the work at MIT and the work at Los Alamos. -Peter

1 0

Re: How long would it take?
by collins＠newton.apple.com 11 Aug '93

11 Aug '93

Hello, When you encrypt a message M with PGP, you are really doing several things: 1. Generating a random IDEA key K 2. Encrypting M with K yielding IDEA(K,M) 3. Encrypting K with the public key of the recipient, Rpub yielding RSA(Rpub,K) (note that if YOUR key is 1256 bits, but THEIR key is only 512 bits, you only get 512 bits of 'security' because you are encrypting to them, not to yourself) 4. Sending (essentially) the message {RSA(Rpub,K)+IDEA(K,M)} Someone who wants to read the message (e.g., the recipient or some interceptor) must either know Rpri (Rpub's corresponding private key) to extract K, or must be able to break RSA, or must know K a priori, or must be able to break IDEA. This is a lot of ways to get in. Most of them prohibitive, except for the recipient who can be expected to know Rpri. > Could the NSA reverse PGP encryption on a message that was encrypted with a > 1264 bit key? Yes. Although, I think it would be more likely through cryptanalysis of the IDEA cypher than of the RSA encrypted IDEA key. > Do you think they could do this in a matter of hours? I don't think so. > Why or why not Cracking RSA is presumed to be as hard as factoring one of the components of the key. Although this has not been proven, I think it likely that no better attack is currently known. I have no figures yet on the complexity of the IDEA cypher. I do not know if it is susceptible to differential cryptanalysis. To my knowledge, exhaustive search is the only attack. With a random 128 bit key, search is prohibitive. Sorry I didn't include more numbers, Scott Collins | "Few people realize what tremendous power there | is in one of these things." -- Willy Wonka ......................|................................................ BUSINESS. voice:408.862.0540 fax:974.6094 collins(a)newton.apple.com Apple Computer, Inc. 1 Infinite Loop, MS 301-2C Cupertino, CA 95014 ....................................................................... PERSONAL. voice/fax:408.257.1746 1024/669687 catalyst(a)netcom.com

1 0