Re: Cryptographic Algorithm Metrics
On Wed, 3 Jan 2001, Ben Laurie wrote: > > A cipher is Conditionally Computationally Secure > > (CCS) if the cipher could be implemented with keys > > that are not quite "long enough" or with not quite > > "enough" rounds to warrant a CS rating. Examples: > > SKIPJACK and RSA. This seems a bit strange to me. I would have expected "conditionally" computationally secure to mean "secure if some condition holds." For instance, Rabin is secure if factoring is hard. > An example of this would be the cipher used on DVDs, or the mobile phone > one, both of whose names I've forgotten. The mobile phone one would be A5, with two variants A5/1 and A5/2. A5/1 likely qualifies as Weak, while A5/2 would now be Very Weak. -David
Re: Book on cryptography for programmers
On Fri, 11 Aug 2000, John R Levine wrote: > * Don't try to invent a new crypto systems. Amateurs can't write secure > crypto systems, as often as not professionals can't either. By the way, I would extend this to include "don't try to write your own new crypto code, unless you really, really have to." Also something on how to find and use test vectors.
Re: What would you like to see in a book on cryptography for programmers?
On Thu, 10 Aug 2000, Michael Paul Johnson wrote: > What would you like to see covered in a practical book on cryptography for > programmers? > * Practical random number generation -- /dev/random, entropy gathering daemon, Yarrow, etc. Some examples of bad random number generation to put the fear of JHVH-1 into the reader. Places to find code for doing practical random number generation. Places to look for updates and bug reports. * How to design a program in such a way that it's easy to upgrade crypto involved. * Quick rundown on what crypto primitives exist, the most common kinds used in each application, and "how to decide between primitives." Mention the controversy over key sizes (c.f. cryptosavvy.com and last RSA Bulletin for starters). * "War stories," as in Skiena's _Algorithm Design Manual_ may be worth looking at, but may be too informal for some tastes. Certainly real-world examples of a project started and finished using crypto would be relevant (for an extreme example of this, _Clouds to Code_ focuses on a single project for the whole book). Preferably projects which address common applications like logging in (although logging in already has ssh and so on, so maybe something else). * Writing your own code vs. using a crypto library. * Discussion of crypto libraries available (say an updated version of Shostack's comparisons), with attention to licensing issues. Discussion of multi-precision integer libraries available for various languages. Also their performance on various OS and chip combinations. * What is and is not provided by a library. What should a programmer expect to write? what should he or she certainly not try to write? * Memory management for paranoids. General discussion of swap files and so on, then specific examples of how to do Windows and/or linux memory management. * Practical details of encoding schemes which may come up in practice (such as what ASN is, how to use it, whether you need it, etc). * Explanation of the PKCS standards, what they are, how to find them, whether you need to conform to them, etc. Ditto for IEEE 1363 standards, ISO, whatever. Some real world perspective on which parts of the standards make sense and which don't. (e.g. "safe primes") * Information on "where to find standards" and "where to look for new information on breaks in systems." Some idea of how to find and interpret results like the ISO-9796 padding breaks. * Speaking of which, it should cover padding. OAEP would be neat. Briefly mentioning the security proof for OAEP would be very cool, but I suppose it's not strictly necessary. * All the _Handbook of Applied Cryptography_ type material on good ways to generate prime numbers and other encryption parameters. Maybe in smaller scope than the HAC (you might not need to include provable prime generation for instance), but explicitly specified at each step. * Fast algorithms for common operations, like modexp. Precomputation algorithms. Source code for such things. Ditto for things like DES; explain what bitslicing is and how it works. * Lots of examples of how to screw up in subtle ways. Either cryptographically (e.g. not verifying that a particular element is a member of a subgroup or something else sneaky) or with the language (buffer overflows). Especially examples of tempting, but wrong, things to do. * Real-world examples of systems which screwed up due to protocol or programming errors. * Some discussion of "speed vs. security" tradeoffs, with specific reference to such things as using e=3 for RSA, moduli of the form n = p^2 q, and so on. Try to distinguish tricks which almost certainly don't affect security from those which might from those tricks which certainly do. -David Molnar
Re: names to say in late september
On Sun, 30 Jul 2000, Arnold G. Reinhold wrote: > By the way, I could not find the April 2000 RSA Data Security > Bulletin on three primes at > http://www.rsasecurity.com/rsalabs/bulletins/index.html Is there a > better link? The link I had in mind was ftp://ftp.rsasecurity.com/pub/pdfs/bulletn13.pdf The discussion is an appendix to the discussion of RSA key lengths. Note that it is actually more general than just 3 primes; various combinations of number of primes and their length are discussed, along with security against known factoring algorithms. Even if you may disagree with Silverman's assumptions about "safe" security levels, this is a very good place to start when looking at RSA with more than two factors. As for terminology, I would prefer to keep the RSA name and just modify it (e.g. "polyprime RSA," or better "3-384-prime RSA") to indicate that a modulus with more than two factors is in use. -David
Re: names to say in late september
On Fri, 28 Jul 2000, Steve Reid wrote: > remember someone (I think it was Richard Schroeppel) a few years ago > advocating RSA with a three-prime modulus. The idea was that having > three primes instead of two would not weaken the algorithm in any > practical way, but it could make CRT operations even faster. It Note that Compaq is trying to push this under the name "Multiprime." Bob Silverman has a nice analysis of the number of factors and size of factors vs. security tradeoff in the April 2000 RSA Data Security bulletin. It's only in the PDF version (or was), though. PKCS #1 is also being amended to allow for multiple distinct primes. The idea of using CRT is due to Couvreur and Quisquater, as far as I know...although I haven't read the original paper and don't know if they suggested multiple primes or not. -David
Re: Extracting Entropy?
ctions might be worth looking at, but I think that fails the no preimages requirement... In any case, if this stab at a definition is any good, maybe a first step would be to try to see if a collection of mn random one bit to one bit functions satisfies it or not. Then move on to David Wagner's proposal considering H as a random oracle, and then onto constructions with real hash functions. -dmolnar
Re: NTRU Public Key Cryptosystem
On Mon, 17 Apr 2000, dmolnar wrote: > > Hi, > Is it known how tightly related NTRU is to the shortest vector problem? Is > there a reduction known yet from SVP to NTRU, or is it still in a ^^^ my mistake -- from NTRU to SVP is what I should have written! Thanks, -David
Re: NTRU Public Key Cryptosystem
On Mon, 17 Apr 2000, Joseph Silverman wrote: Hi, > The hard problem underlying the NTRU cryptosystem is called the > "Shortest Vector Problem" (or SVP), which is the problem of finding the > shortest nonzero vector in a lattice. Is it known how tightly related NTRU is to the shortest vector problem? Is there a reduction known yet from SVP to NTRU, or is it still in a position analagous to RSA and factoring? Not that a reduction would necessarily be a good thing, as Ajtai and Dwork found out the hard way... :-) Seriously, is anything known about how "good an approximation" would be needed to break NTRU? Apologies if this is already answered in the Coppersmith paper or someplace else; just point me there. Thanks, -David Molnar
