Re: How far is the NSA ahead of the public crypto community?
An interesting datapoint I've always had on this question: Back in 1975 or so, a mathematician I knew (actually, he was a friend's PhD advisor) left academia to go work for the NSA. Obviously, he couldn't say anything at all about what he would be doing. The guy's specialty was algebraic geometry - a hot field at the time. This is the area of mathematics that studied eliptic curves many years before anyone realized they had any application to cryptography. In fact, it would be years before anyone on the outside could make any kind of guess about what in the world the NSA would want a specialist in algebraic geometry to do. At the time, it was one of the purest of the pure fields. The friend he used to advise bumped into this guy a few years later at a math conference. He asked him how it felt not to be able to publish openly. The response: When I was working at the university, there were maybe 30 specialists in the world who read and understood my papers. There aren't quite as many now, but they really appreciate what I do. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How far is the NSA ahead of the public crypto community?
On May 8, 2008, at 19:08, Leichter, Jerry wrote: An interesting datapoint I've always had on this question: Back in 1975 or so, a mathematician I knew (actually, he was a friend's PhD advisor) left academia to go work for the NSA. Obviously, he couldn't say anything at all about what he would be doing. The guy's specialty was algebraic geometry - a hot field at the time. This is the area of mathematics that studied eliptic curves many years before anyone realized they had any application to cryptography. In fact, it would be years before anyone on the outside could make any kind of guess about what in the world the NSA would want a specialist in algebraic geometry to do. At the time, it was one of the purest of the pure fields. I've heard similar recollections of mathematicians from improbably abstract specialties being eagerly taken in by NSA, throughout the cold war. I've also heard it said that at one time NSA was the US's single largest employer of math PhDs. I don't know if that was actually true, but it certainly seems plausible. But it's also important to remember that crypto isn't the only area of the NSA mission that benefits from mathematical expertise. I suspect that while many of these NSA math PhDs were indeed doing cryptomathematics, a large fraction were (and are) working on other SIGINT problems such as signal processing, databases and searching, coding theory, machine learning, and so. Some of the (non-crypto) problems here seem rather specific to the NSA's domain, and so don't likely have an advanced civilian research community competing with them they way academic crypto does today. A couple of the papers from the 1970's hint (in redacted form, frustratingly) that the NSA then had large scale automatic systems for intercepting and processing morse code signals from large blocks of radio spectrum, which implies some pretty advanced (for that era) signal processing and computing, crypto aside. -matt - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How far is the NSA ahead of the public crypto community?
On 2008-05-09, Matt Blaze wrote: The guy's specialty was algebraic geometry - a hot field at the time. This is the area of mathematics that studied eliptic curves many years before anyone realized they had any application to cryptography. [...] I've heard similar recollections of mathematicians from improbably abstract specialties being eagerly taken in by NSA, throughout the cold war. I wouldn't say algebraic geometry is such a pure and abstract specialty in this context. It has its roots firmly planted in multivariate polynomial algebra, and even at that time it was quite clearly the field that was most intimately connected with mechanistic solutions to groups of nonlinear polynomial equations over finite fields. Which then is exactly what a mathematician sees when presented with a symmetric cryptosystem to break. As evidence of that, Hilbert's basis theorem (which underlies Groebner bases, which in case relinearization and the bunch are an independently discovered special case of) was well known and appreciated at that time. So, even if elliptic curve cryptography became later, the broader theory of algebraic geometry was *certainly* relevant to crypto even then, and should have easily been seen to be so. Some of the (non-crypto) problems here seem rather specific to the NSA's domain, and so don't likely have an advanced civilian research community competing with them they way academic crypto does today. Quite so. I think this is where one should be seeking for the signs of differential advantage. Not the broad fields of mathematical expertise which plausibly could have been acquired by the NSA for any of a number of reasons. A couple of the papers from the 1970's hint (in redacted form, frustratingly) that the NSA then had large scale automatic systems for intercepting and processing morse code signals from large blocks of radio spectrum, which implies some pretty advanced (for that era) signal processing and computing, crypto aside. Band agnostic, keying rate adaptable and error tolerant algorithms in this department most likely fall in the advanced category even today, especially if computationally thrifty. I've certainly never seen anything of the sort in what DSP literature I'm aware of. -- Sampo Syreeni, aka decoy - mailto:[EMAIL PROTECTED], tel:+358-50-5756111 student/math+cs/helsinki university, http://www.iki.fi/~decoy/front openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
How far is the NSA ahead of the public crypto community?
During the 1980's and 1990's crypto wars, an occasional topic of speculation was just how much the NSA was ahead of the open/public/academic cryptography research community in cryptanalysis and cipher design. We wondered (and still wonder) whether the NSA was merely a strong center of expertise, a bit ahead of the rest of us by virtue of their focused mission and culture, or were they more of a crypto-mathematical superpower, possessing amazing techniques that effectively demolish every cipher in the public domain? For those of us in the unclassified world, there has relatively little evidence to go on beyond the occasional tantalizing technical nugget, and even those have been hardly uniform in their message. The impressively well- engineered resistance of DES to differential cryptanalysis (apparently called the tickle attack on the inside years before Biham and Shamir's result) and the narrow -- but apparently solid -- resistance of Skipjack to various new attacks suggests a remarkably sophisticated set of decades-old cipher design and analysis tools that the civilian world is only beginning to catch up with. On the other hand, there have been blunders, like the early problems with SHA and the protocol weaknesses in Clipper, that suggest that the NSA's crypto toolkit might not be all that much sharper than ours after all. Anyway, there's now a bit more fuel for speculation. The latest batch of (still partly redacted) publicly-released NSA technical and historical publications includes several policy papers from the 1990's that touch on NSA's dominance over crypto in the face of an increasingly sophisticated public research community (among other factors). I found one of the most interesting (if frustratingly censored) new documents to address this point was Third Party Nations: Partners and Targets from Winter 1989: http://www.nsa.gov/public/third_part_nations.pdf This paper discusses the pros and cons (from the NSA's perspective) of sharing cryptologic technology with other countries. The specifics (presumably naming names of the countries concerned) are all redacted, but what remains is a hypothetical dialog between liberal (pro-sharing) and conservative (anti- sharing) internal viewpoints. Page 8 of the PDF (marked as page 17) addresses the general spread of cryptographic expertise.Interestingly, both the liberal and the conservative sides acknowledge the rapid development of public cryptographic expertise, and this was back in 1989. The conservative argument relied here not on the NSA's better crypto-mathematics (an advantage that they seemed to believe was shrinking), but rather on the large gap between the theory and actual deployment in the non-NSA world (a problem that we here have long recognized). Anyway, this isn't big news, since it's essentially what most of us have suspected all along, but this is the earliest document I'm aware of from inside the NSA to explicitly address the question. Personally, I suspect the NSA does have a large advantage in SIGINT technologies, but in those areas, like demodulation of unknown signals, for which there's less of a civilian research interest. The vibrant crypto research community, on the other hand, has probably evolved to the point of being a serious competitor to NSA. On a side note, I've also been enjoying filling in some of the redacted gaps in the various technical papers. I was particularly delighted to discover a fun little paper on safecracking (an analysis of the keyspaces of safe locks), which was very similar to part of a survey I published a few years ago. I discuss what's likely in some of the redacted material from that paper in a recent blog post at http://www.crypto.com/blog/nsa_safecracking/ -matt - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]