Dr. Dobbs Dev. Update 1/5 July 94 & Schneier
Once again DDDU has an encryption News Brief re the Standards & clipper, and Bruce Schneier has an article on Eurocrypt '94 with some highlights from the same. As he is on the list (yes?) perhaps he might upload it here... -NetSurfer #include standard.disclaimer
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> == = = |James D. Wilson |V.PGP 2.4: 512/E12FCD 1994/03/17 > " " " |P. O. Box 15432 | finger for full PGP key > " " /\ " |Honolulu, HI 96830 |====================================> \" "/ \" |Serendipitous Solutions| Also NetSurfer@sersol.com > >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
EUROCRYPT '94 CONFERENCE In the cryptographic world--at least, the cryptographic world outside the military--there are two major annual conferences: Crypto and Eurocrypt. Eurocrypt '94 was held in Perugia, Italy, on May 9-12. There were about 300 people in attendance, representing the best in academic cryptography from five continents (I didn't notice anyone from South America or Antarctica). A total of 37 papers were presented at the main session, and another twenty or so at an informal "rump session" one evening. Much of what was presented was very theoretical, and only of marginal interest to front-line programmers actually implementing this stuff. Here is a list of what I found useful and important: Feedback with Carry Shift Registers (FCSRs): Linear Feedback Shift Registers (LFSRs) have been the workhorse of military cryptography for years. Goresky and Klapper have discovered a new class of shift registers which should prove to be just as useful. There are analogues for most of the LFSR theory that apply to FCSRs. Algorithms that were implemented with LFSRs can be implemented with FCSRs, possibly with different degrees of security. Even more interesting should be cryptographic algorithms which use a mixture of LFSRs and FCSRs. I expect this development to dramatically change the development of stream ciphers. Synthesis of Public-Key Algorithms: There are a lot of public-key digital signature algorithms in the literature based on the problem of taking discrete logarithms in a finite field: ElGamal, Schnorr, and the Digital Signature Standard (DSS) are three examples. Nyberg and Rueppel presented a paper which unified all of these algorithms (108 in total) into one unified family. They also showed how to do encryption with all of them. What this does it allow further research to proceed on the entire family of algorithms, and not just on one particular one. It also lays to rest Schnorr's claim that the DSS infringed on his patent; it is now clear that both Schnorr and DSS are specific cases on this general algorithm. The Digital Signature Standard: Naccache, M'Raihi, Raphaeli, and Vaudenay presented enhancements to the DSS: one that increases speed, one that reduces storage requirements (important for smart-card implementations), etc. Their most interesting enhancement is the ability to verify multiple signatures in a single operation. A complaint against DSS is that signature verification is slow; the batch verification method in this paper should silence that complaint once and for all. Visual Cryptography: Shamir developed a one-time-pad cryptosystem that is suitable for encrypting visual images. The key is a pattern of black and white pixels on a transparency; the ciphertext is another pattern of black and white pixels. Overlay the key on the ciphertext and the message appears. This is unconditionally secure; even alien civilizations with undreamed- of computing power cannot break this cryptosystem. Applications include sending an encrypted message via fax: the receiver can carry the key transparency with him and can receive the encrypted fax from an insecure machine. Cool stuff. Designated Confirmer Signatures: Undeniable signatures are signatures which need permission from the signer to verify. Applications include computer publication of data. The recipient of the data wants to be able to verify the publisher's signature, so he knows that the data is authentic. The publisher only wants his signature to be verifiable by people who have paid for the data, and not by people who have pirated it. Undeniable signatures do that. Chaum's extension allows the publisher to designate an agent who can help receivers verify the signatures. Differential and Linear Cryptanalysis: Both of these techniques were further refined by several people. Two papers, one by Biham and another by Chabaud and Vaudenay, looked at similarities between the two. Matsui found an alternate order for the S-boxes that is resistant to linear cryptanalysis, but unfortunately it is weak against differential cryptanalysis. Self-Shrinking Generator: The shrinking generator was a big hit at Crypto '93. Basically, a LFSR is decimated by another LFSR. This stream algorithm is simple to implement, and looks very strong. Meyer and Staffelbach developed a variant of this generator, which uses a single LFSR. The even bits of the generator are used to decimate the odd bits. This is even simpler to implement and is just as strong. Formal Protocol Design: One of the problems with authentication protocols, like Kerberos, is proving that they are correct. There's nothing more embarrassing than fielding a protocol and finding a security problem two years later. Syverson and Meadows have developed an expert system that helps detect security problems in protocols. Several interesting papers were presented at the rump session. Biham presented a paper showing that triple-DES in cipher feedback mode, with triple-DES as the bock cipher, is more secure than a large number of variant possibilities. Knudsen found a class of "weak" keys for DES and LOKI when those algorithms are used as one-way hash functions. There is nothing to worry about; the odds of picking such a key at random is very small. Charnes and O'Connor presented some initial comments on the GOST algorithm, an encryption algorithm from the Soviet Union. Also interesting were the side discussions. At least two cryptographers are working on something called "higher-order differential cryptanalysis." Although this technique has had great success against DES with only 5 rounds, no one knows how to extend it to full 16-round DES. One cryptographer has developed an alternate set of DES S-boxes that is resistant to both differential and linear cryptanalysis, while another has developed a method for generating key-dependent S-boxes that increase the effective key size of DES beyond 56 bits. If there are going to be any more attacks against DES, this--and Hellman's attempts to combine differential and linear cryptanalysis--is where to watch for them. RSA-129 was recently factored. This is the 129-digit number, the product of two large primes, that was featured in Martin Gardner's original Scientific American column about the RSA algorithm. Although this doesn't affect the security of the 1024-bit numbers used in programs like PGP, it does show how far we've come in fifteen years. Gardner was sure this number would not be factored for millions of years. The other big news is a security problem with the Secure Hash Algorithm (SHA), discussed in the Apr 94 DDJ. The cryptographers at NSA have found a problem with the algorithm. They won't tell anyone what it is, or even how serious it is, but they promise a fix soon. Everyone is waiting with baited breath.
-----BEGIN PGP SIGNED MESSAGE-----
Feedback with Carry Shift Registers (FCSRs): Linear Feedback Shift Registers (LFSRs) have been the workhorse of military cryptography for years. Goresky and Klapper have
An interesting thought hit me when reading this. The "classic" Cray series (Cray-1, X-MP, Y-MP) all have a rather curious instruction generally known as population count. All it does is to take a register and count the number of one bits in it, and return that count. Originally I could never figure out a use for this, but later was told that it was the "canonical NSA instruction", and was consistently demanded by almost all military SIGINT operations. On reading this, I realised that one possible use was to implement a vectorized version of a LFSR. Take a vector register (the shift register), AND it with a mask of the taps into another vector register, and then do a population count to determine the carry in. Just a thought. It's the only plausable use that I have yet thought of for this instruction. Has anyone else got any ideas? As for military ciphers having been "the workhorse of military cryptography for years", I am reminded (with some amusement) of the structure of A5. I wonder if all of the fuss about secrecy was not about the almost non-existant security of the cipher, but simply it's similarity to more sophisticated military ciphers? Ian. -----BEGIN PGP SIGNATURE----- Version: 2.3 iQCVAgUBLhX/qtCZASdT8NoBAQF8SAP/V5FKgEaCk1GQXV9rrK+AMry2Bzb9Xlyu bYMqjN94mAqqkNOe1r2ChmUF4kleTUMxdx1Krje3xhLDPL31HH4lvJ386sm6Ogrm /iu/TgjoSnGbMYtoq+C2ZJacA/NBDzItTeUaZgkWRS62Emo/cFIGarT130clL8/x HnNbtdGtSOE= =VVZZ -----END PGP SIGNATURE-----
An interesting thought hit me when reading this. The "classic" Cray series (Cray-1, X-MP, Y-MP) all have a rather curious instruction generally known as population count. All it does is to take a register and count the number of one bits in it, and return that count. Originally I could never figure out a use for this, but later was told that it was the "canonical NSA instruction", and was consistently demanded by almost all military SIGINT operations.
On reading this, I realised that one possible use was to implement a vectorized version of a LFSR. Take a vector register (the shift register), AND it with a mask of the taps into another vector register, and then do a population count to determine the carry in.
Just a thought. It's the only plausable use that I have yet thought of for this instruction. Has anyone else got any ideas?
This operation is ideal for computing the "hamming distance" between two binary words, an important operation in the encoding and decoding of forward error correcting codes. It's also used when correlating binary streams, eg, searching for frame synchronization vectors or despreading spread spectrum signals. All these operations are fundamental to modern digital radio communications. I've written software that implements a correlator, a convolutional coder and a sequential decoder. All three make heavy use of this operation, so I know first hand how useful it would be to have such an instruction. The best I can do on the 386/486 when is to add the results of table lookups on manageable pieces of the word (e.g., 8 bits at a time). People keep assuming that NSA spends most (or even all) of its CPU cycles on cryptanalysis. They forget that before you can attack a cipher, you need some ciphertext. Usually this comes by radio. This means analyzing, demodulating and decoding (as opposed to deciphering) the digital RF modulation being used by your target. A Cray with a library of signal analysis and demodulation programs would be ideal for this purpose. I would make an educated guess that this, and not cryptanalysis, is NSA's biggest use for their Crays. A Cray is not especially cost-effective for cryptanalysis, at least compared with special purpose hardware that could, say, attack DES far more cheaply. And then there's this friend of mine who works for IDA/CRD, the NSA think-tank in Princeton. His specialty is digital signal processing, often using Crays. As a lark, he once demodulated some amateur packet radio signals that were used in "Star Trek IV" as background sound effects. Great fun. Another time he helped the Russians demodulate some telemetry signals from their "Vega" Venus balloon probe. Sucked the bits right out of the noise. Phil
On Fri, 1 Jul 1994, Bruce Schneier wrote:
Synthesis of Public-Key Algorithms: There are a lot of public-key digital signature algorithms in the literature based on the problem of taking discrete logarithms in a finite field: ElGamal, Schnorr, and the Digital Signature Standard (DSS) are three examples. Nyberg and Rueppel presented a paper which unified all of these algorithms (108 in total) into one unified family. They also showed how to do encryption with all of them.
Hrm... As far as I recall they showed how to do _message_recovery_ (not encryption) with the discrete log signature functions. Message recovery and encryption are two quite different things for assymetric schemes such as the discrete log ones (as opposed to RSA). Correct me if I'm wrong...
Visual Cryptography: Shamir developed a one-time-pad cryptosystem that is suitable for encrypting visual images. The key is a pattern of black and white pixels on a transparency; the ciphertext is another pattern of black and white pixels. Overlay the key on the ciphertext and the message appears. This is unconditionally secure; even alien civilizations with undreamed- of computing power cannot break this cryptosystem. Applications include sending an encrypted message via fax: the receiver can carry the key transparency with him and can receive the encrypted fax from an insecure machine. Cool stuff.
Yea, cool stuff, especially if the fax doesen't shrink the transmitted picture :-) This is also great for demonstrating crypto to newbies by showing that noise+noise=picture. -- Rolf ---------------------------------------------------------------------- Rolf Michelsen "Standards are wonderful -- Email: rolf.michelsen@delab.sintef.no everyone should have one" Phone: +47 73 59 87 33 -- Ancient FORTH proverb ----------------------------------------------------------------------
Applications include sending an encrypted message via fax: the receiver can carry the key transparency with him and can receive the encrypted fax from an insecure machine. Cool stuff.
Yea, cool stuff, especially if the fax doesen't shrink the transmitted picture :-) Shamir's comment on this at his talk at MIT was that the accuracy of a fax machine in the horizontal direction was much better than the accuracy in the vertical direction. If the visually encrypted document is a text file, you can adjust it so that it's correctly registered for a few lines, read those lines, slide the key transparancy by a small fraction of an inch, read the next few lines, and repeat until you're done with the message. - Bill
participants (6)
-
Ian Farquhar -
NetSurfer -
Phil Karn -
Rolf Michelsen -
schneier@chinet.chinet.com -
sommerfeld@orchard.medford.ma.us