On Thu, 7 Sep 2000, Asymmetric wrote:

Now, my main question about D/H is quite simple.. what is considered a "good" size for the prime and primitive used, in bits? Obviously something somewhat large, but how large is large enough? 64bits? Less or more? I can't find much information on this anywhere, and my copy of Applied Cryptography (2nd ed.) while covering D/H in detail, doesn't even mention this.

The modulus should be rather large -- something like 512 or 1024 bits. With 64 bits, someone can use Pollard's method to find discrete logs in roughly 2^32 trials, which is Bad. Taking discrete logs for larger primes requires a variant of the number field sieve; the largest announced modulus for which I'm aware of this being done is 300-400 bits, but it hasn't received as much attention as factoring. I think www.cryptosavvy.com has some key length recommendations. You might also check the April RSA Data Security Bulletin for Bob Silverman's dispute of their model. The storage problem he mentions is actually worse for discrete logs; while the vectors involved in the final step of factoring are 0-1, the vectors in the final stage of discrete log finding have full-size group elements and are therefore harder to store and manipulate. The size of the generator is a different issue. I don't see any reason why a small size generator would hurt...but I haven't thought about it very much. Note that you need the factors of p-1 in order to test if something's a generator, which means you may want to look into Maurer or Mihailescu's methods for prime generation. (Mihailescu has a paper on the subject aimed at implementors at http://www.inf.ethz.ch/~mihailes/papers/primgen.ps )

Delphi and has any libraries like this already, I'd much appreciate hearing about them.. or even some a web resource or paper Real Book (tm) resource that explains in abstract terms how to go about something like this would be appreciated.

It was after my time, but the AP Computer Science curriculum now has a BigInteger library as its "case study." :-) A web search turned up http://www.efg2.com/lab/library/Delphi/MathFunctions/Cryptography.htm which has, among other things, a Pascal header for the Gnu MP library. -David

On Thu, 7 Sep 2000, Asymmetric wrote:

...

Mihailescu's methods for prime generation. (Mihailescu has a paper on the subject aimed at implementors at http://www.inf.ethz.ch/~mihailes/papers/primgen.ps )

Ah.. I have implemented a sieve of eros..whatever his name is.. ;) for

Erastothenes, I think. I don't know what a sieve of eros is. I think I'd like to try one sometime. :>

finding smaller primes.. it runs very fast, the old rules don't apply so much anymore, memory footprint being more a concern then speed I've noticed so far.. moving the found primes into a sparse array as you find them and then reusing the memory is one way around that.. even my quickly written implementation takes negligible time to find all the primes within 16 bits..

Right - I think you may find that this slows down a bit at the 500-bit range. Still, there are supposed to be ways to use sieving in conjunction with random search to speed up prime generation.

but I've been looking at rabin-miller and some other methods as well. I'll take a look at that link, thanks.. reason again for the math library.. my stuff (obviously) falls apart > 32bits since my library for handling larger numbers is unfinished.

Once you have the primitives, Rabin-Miller is straightforward to implement from the Handbook of Applied Cryptograpy. I was surprised at how easy it was... Another nice trick -- compute the product of the first 1000 primes or so. Take the GCD of this product and a candidate number. Eliminates candidates with small prime factors and often faster than trial division.

(for reasons that should be obvious) felt that writing the routines myself (with extensive testing) would be preferable, so I could avoid licensing issues as well as bugs/backdoors, but I'll look into this.. Thanks for the

Backdoors are your responsibility with GMP, so no worries, right. :). It is GPL'd, though, so be careful.

quick response.. the application will of course be available to anyone who wants it once finished.. and once Borland finishes Kylix, should compile nicely on the various x86 *nixes out there..

Looking forward to it. -David

At 15:08 09/07/2000 -0700, Bill Stewart wrote:

Servers are the price of scalability. The nice thing about ICQ and similar instant messaging applications, unlike IRC, is that the server only tracks who's on and where, and doesn't carry the actual communication traffic between users. Obviously this is for one-to-one conversations between two users rather than IRC's everybody-to-everybody model. Another option in this space is the everybody's-a-server model, like Usenet uses. Servers also offer the benefit that it's harder to tell who's talking to whom, unlike point-to-point conversations, but they do cause risks from compromise and downtime.

Right.. I consider the benefits to outweigh the costs. I am keeping the protocol robust enough that if you wanted to implement a server on your own, you could probably do so with minimal impact to the clients themselves. When finished, you'll be able to add servers just as you do other users to your "buddy list" if you will, and communicate with a larger group that way. Inter-server communications is not restricted either, but it's a ways down the road.

...

everyone must maintain an active TCP connection to everyone else..

That's a MAJOR downside. Most operating system and programming environments limit how many open TCP connections you can keep, typically <20, so this limits the sizes of communities you can maintain. Also, if you have TCP connections you need to write code to handle having them go up and down at unplanned times, while UDP just dribbles in. On the other hand, TCP sessions are good for data transfer. Voice over TCP is a sketchier issue - the problem is that the best way to handle lost voice packets is just to ignore the noise, as opposed to waiting for the retransmission to arrive and speeding up or delaying talk until you've caught up.

Yes.. I understand the differences in TCP/UDP pretty well, and their strengths and weaknesses. I've done extensive programming using both, and have decided to go with TCP. I do however have two points to bring up with the beginning of this section of your reply. 1) I've never encountered the 20 socket limit on any OS in recent memory.. and many applications open more than this on a regular basis. 2) The target audience of this application is very small, and currently restricted to Win32 users because it is written in Delphi. Before long Delphi will be available for Linux, and cross-compiler compatability will have to be tested, but it is a big selling point with Borland/Inprise. When Kylix (Delphi/C++ Builder on Linux) is available, I am keeping my fingers crossed that it will run well on FreeBSD, since I refuse to touch Linux with a ten foot pole, but have several years experience not only with Delphi, but with Administration of FreeBSD as well as NT based boxes. I agree that voice using TCP has the drawbacks that you mentioned, however, because of the other existing requirements such as CBC and File Transfer, it is required that you have a reliable connection to get even the basic functionality of the program to work. I'd rather have a delay in hearing the voice messages until the packets have arrived than decrease their security by using ECB.

Your issues about ECB mode with UDP are good, though. The alternative is to use CBC mode and trash the next couple of packets after the lost/damaged one - CBC does self-recover. This is ok for voice; may or may not be for chat.

CBC does self recover yes, if bits are flipped that should not be flipped. According to AC, a one bit error will cause a corresponding 1bit error, as well as mangling the following block.. but subsequent blocks will be OK. However, it states very clearly that receiving the wrong number of bits in the stream will destroy the rest of the stream beyond repair for the decryption end, and that makes sense. If a UDP packet is lost, then the rest of the stream is screwed and must be reinitialized. Since the only way around this problem (besides using EBC) is to write my own connection-handling on top of UDP; I instead choose to let the OS handle this for me, in the form of TCP. To quote Applied Cryptography, 2nd edition.. p195, pp5 "In CBC mode, a single-bit error in the ciphertext affects one block and one bit of the recovered plaintext. The block containing the error is completely garbled. The subsequent block has a 1-bit error in the same bit position as the error." ... p196, pp2 "While CBC mode recovers quickly from bit errors, it doesn't recover at all from synchronization errors. If a bit is added or lost from the ciphertext stream, then all subsequent bits are shifted one bit out of position and decryption will generate garbage indefinitely." I assume that losing an entire block worth of bits will cause as much havoc as losing just one bit would. If that isn't correct, I'd like to hear it..

The rule of thumb is that you need at least twice as many bits of DH as you need of secure session key for your application, and you need at least as many bits of DH as you would need for RSA. You wouldn't want to use fewer than 1024 bits of RSA these days, so don't use fewer than 1024 bits of DH. That's enough for multiple 128-bit keys. There are various format proposals for turning the DH key into a session key, like using Hash(DHKey,YourIP,TheirIP,maybe-a-counter-or-Salt). 4096 may be overkill, but it depends a lot on how often you'll be rekeying and how long you're willing to watch the CPU crunch to set up a connection.

The D/H is going to be used just to generate a key to securely transfer a 4096 bit key for use in symmetrical crypto routines later in the program, for actual encryption of the chat/voice/file data transfers. Using 1024 bits of D/H is fine to generate a key-encryption key to just transfer the 4096bit key. I chose 4096 because it's large enough to be used in any symmetric crypto algorithm to max out it's key length.

The bigger risk, though, is the quality of random numbers available for seeding your DH keys. Don't even DREAM of using Delphi's builtins, if it has them - go find good crypto-quality-randomness work to reuse, unless you know you'll only run on Linux where there's /dev/random. At least use sound-card noise or user-entered mouse tracks to help. Lots of "secure" systems have been cracked by cracking their random seeds.

Of course. ;)

If you don't have any other keying mechanism, you need to worry about man-in-the-middle attacks. A simple approach is to use PGP public keys to sign the keyparts; that lets you reuse all the PGP infrastructure. There are alternatives, at least for voice, like reading the bits of the shared keys to each other. See the PGPFONE docs for much discussion on user interfaces - and think about how much of their code you can rip off\\\\\\ reuse.

Well, truth be told, everyone knows that there is the problem "If Mallory is God.." which in this world simply means, if Mallory is your upstream you're in some serious trouble. He could just as easily intercept the PGP keys and replace them with his own if they didn't already exist on the server.. this would cause problems for keys signed outside mallorys realm, say if you could distribute your key outside his available channels... however, if you could do that, you could just as easily trade a PRNG and a list of seeds, or even discuss whatever it is you mean to discuss over a cup of coffee.. :) There comes a point of diminishing returns in trying to defeat the mallorys, where instead of making the problem harder for them, you just replace it with an equally hard/easy problem of a different nature. I'm as paranoid as the next guy, but if mallory exists (in a given scenario) and he is in a position to intercept/forge a D/H exchange, then chances he is in a position to intercept/forge his own PK are highly likely.

Also read the Photuris internet drafts - there's a lot of experience on denial-of-service attacks that they've incorporated, and it doesn't take much work to prevent most of them.

Ah, sorry.. how did we get on the topic of denial of service?

Gak! Don't do something that ugly. There are lots of math libraries available,

Hey, I tend to find asm totally the opposite of ugly. I've been writing it for years and have become pretty proficient at it, and my solutions are usually quite fast and elegant. But, I have found a library I am going to be using instead.. the FGInt library.

such as the GMP Gnu Multiple Precision integer package. Depending on how Delphi feels about calling C routines, the most you should need to write in assembler are some little wrappers to format the function calls, and hopefully you don't need to do that.

Delphi can call C routines no problem, I have two problems with GMP that however have nothing to do with Delphi.. First, It's GPL'd, or under a modified version of the GPL. I find the GPL to be distasteful and it forms a barrier more than a bridge to continued software development. The reason for this I think is pretty simple; the GPL (I refer to the classic GPL.. I am not sure of modifications to it that may have been made for it's application to GMP) has made it excruciatingly clear that any program or library using any GPL'd source code must itself be open source, and cannot be sold for profit, but only "at-cost". This represents a very "scary" proposition to professional developers such as myself, who are used to being paid for our work, since it basically states that any person can just come along, take a copy of our source code (which may in and of itself contain anything analogous to a "trade secret"), modify it and release it under a different name. It also bars me from ever releasing a for-pay version or revision of the software based on GPL'd code. I'm not in the support business, and any examination of the stock market would make it pretty obvious that those companies that claim they are in that business aren't doing so well. I much prefer the BSD license which allows you to take, modify and use the source code within, and sell it or distribute it without source code if you so choose, provided you include the existing copyright for the sections of code you have used. It gives the developer more freedom over how to distribute his/her own code, and incidentally allows people like myself who aren't in the support business and don't want to be the freedom to continue paying the bills by doing development on our own terms. Sorry for the rant.. I'm a big fan of the Free Software movement, as well as the Open Source movements.. I am however mature enough to realize that there are situations when either one may be inappropriate, and I'm a far bigger fan of freedom than I am of free/open. I believe that if you want to make your source code open and free, then you do so without restrictions.

Also, some versions of the RSAREF libraries had Diffie-Hellmann code in them, as well as multiple-precision integers.

Other chat and messaging systems have been written. Check out GALE at gale.org, and look through the Cypherpunks archives for encrypted IRC and DCC variants. Don't let that stop you from coding, but do steal code rather that writing from scratch when you can.

Ah, but that really detracts from the joy of a lot of it.. :) The only parts I'd steal would be parts that I'm finding difficult to do, like the large math libraries.. and that takes all the fun out of learning for yourself.. :) Far from inventing the wheel though, I will use libraries/snippets that stand up to my testing as well as my scrutiny of their license.. I want to get a version working now (without gpl-like restrictions) and then I probably will go back and rewrite every line myself that I have obtained elsewhere, just so I know how it all works, I am free of licensing restrictions, and I can implement bug fixes/features without worrying about maybe breaking something I didn't write. You know how difficult it can be to understand code written by other people, I'm sure.. ;)

It's been high for years - thanks for adding Signal :-)

I'll try and continue. ;)

Listening in on cordless phones can be a legitimate cpunks kind of topic, though it's been discussed in the past and this was probably just a troll or a clueless newbie. As far as giving people drugs, the standard Cypherpunks approach is to say "That's a hardware problem" and then discuss whose Palm-pilot digicash system you can use for payment, though there has also been crypto protocol work like "The Cocaine Auction Protocol" on how suppliers and consumers can find each other without interference by non-participants, or building conferencing systems for ravers where the server operator provably doesn't have anything subpoenable that would indicate which chatters were discussing where to get drug X at event Y. (There are also noisier Cypherpunks approaches to drugs, like saying "Jim, yer off yer medication again" or "smells good, got any more?" or "He's obviously smoking something *very* good and not sharing" or "No, in a geodesic gift economy you really *might not* charge for drugs." :-)

hahah.. of course.. well, again, sorry for ranting above a bit and possibly contributing some to the noise.. I'll be around, but for now, there is another window open with code crying out to be written... ;) Take it easy. -------signature file------- "'There comes a time when the operation of the machine becomes so odious, makes you so sick at heart, that you can't take part; you can't even passively take part, and you've got to put your bodies upon the gears and upon the wheels, upon the levers, upon all the apparatus, and you've got to make it stop. And you've got to indicate to the people who run it, to the people who own it, that unless you're free, the machine will be prevented from working at all!" -Mario Savio- Founder of the Free Speech Movement.

At 02:06 09/08/2000 -0700, Bill Stewart wrote:

You can still do CBC with UDP. You might want to look at hybrid solutions, like basic connectivity and voice connections on UDP and separate TCP connections for data transfer, though that may be more trouble than it's worth.

I've thought about it and it's definitely something to keep in mind.. another advantage to doing TCP from my standpoint is that it's easier to multithread. The old version had some problems where on occasion it would stall for a while if it was doing a reverse lookup or something like that, and you wouldn't receive any more traffic until whatever operation was finished. Threading the application allows any of the connections to stall or slow down without taking the rest of the application with it.. and threading UDP isn't nearly as easy. Honestly, with the tools I have available, I don't even know if it's possible. :)

There are synchronization problems you can recover from and ones you can't. You need to stay aligned on the encryption-block barrier, e.g. 64 bits for DES or 128 bits for some other algorithms. If you lose that, you're toast. But if you always pad your packets to multiples of the block size, you don't have a problem with UDP, since packets either arrive or don't. So if you lose a packet, then you've toasted the first 16 bytes of the next, but the rest of the packet and the rest of the conversation are ok. With TCP, you don't lose packets, though you don't always have convenient mechanisms for keeping track of packet boundaries, but you're always going to write in block-size chunks anyway.

Ah ok.. so losing a block will just nuke the entire next block, and then it will recover? I thought it would be a more serious problem than that, but I guess it makes sense that the feedforward wouldn't be able to affect any blocks beyond the immdiate next block. Keeping the packets aligned on block boundaries makes so much sense that it's something I'm doing anyway regardless of this problem. :)

Any symmetric algorithm will have maxed out by 256 bits, and most by 128, though you may want different keys for your two directions. So generating the DH key with 1024 bits is probably enough, though it doesn't hurt much to do 2048 or 4096 - no need for separately generating a key and shipping it. In particular, DH takes advantage of both machines' sources of randomness, which is a major win over something generated by one end unless you've got a good reason for it.

Well, the information I have is that Blowfish takes up to 448 bits, RC2 up to 1024 bits, Mars up to 1248bits, RC5 and RC6 both up to 2048 bits of key material.. is that incorrect? The system currently supports Blowfish, Cast (128 and 256), Gost, IDEA, Mars, Misty1, RC (2, 5 and 6), Rijndael and Twofish for ciphers, and Haval, RipeMD160 and SHA1 for hashes. The user chooses what cipher they want to communicate to the other users with, so incoming traffic can possibly use a different cipher on every connection, while outgoing traffic will all use the same cipher. This brings up another question. My document states that Cast256, IDEA(*), Mars, Misty1(*), RC5, and RC6 are all patented.. * = "Free for noncommercial use." Is there a good repository somewhere with information on all the licensing issues/rules of these algorithms?

Sometimes Mallory _is_ your ISP - even without Carnivore. Public key technology only needs one untampered data transfer to happen, and PGP has a lot more infrastructure for that than trading PRNGs. Signing DH keyparts is a job for public-key signatures.

True, and it is something that I've considered, but I would really like to stay away from any kind of server-based options as possible. The fewer points of failure in the chain the better for this application. I think it would suit me better to implement a public-key algorithm in the application itself, and then have each client maintain a list of all the public keys it has seen and allow the option to the user of signing them with it's own key and then sending them back to the owner. This would allow the same failure-rate where only one transmission needs to occur untampered in order to allow for key validation. Possibly in the future clients could exchange all their keys and then raise the trust level of a public key the more times they see it from different clients. Since participation is entirely voluntary by both parties in both the overall application as well as the key signing/trust parts, then a DoS related to a single user forging a key and then connecting to many clients with many other clients isn't really an issue. The lack of centralized communications means that the malicious user isn't going to have a "master list" to poison, or even an accurate view of all the clients in use. This is all tenative however.. I haven't thought this far ahead until just now. For now, I just want to get the D/H working and the key generation underway. Ah, as an aside to something you mentioned before about using the built-in random functions with Delphi... Borland gives you full source to all the run-time libraries and components that ship with the language, so It's easy enough for me to just rewrite them to be cryptographically strong if I want to do that instead of writing auxiliary libraries.. why I would want to do that however, escapes me just now, but at least I can investigate the methods it is using and see how strong/weak they are.

By saying "I'm going to put this chat server on the Internet".... Crypto has its own special denial-of-service flavors in addition to the regular ones, and Photuris addresses a lot of it with minimal work.

Ah ok..

The "Library GPL" was written to address just that problem. Stallman calls it the "Lesser GPL", because he doesn't like it (:-), but LGPL says you have to distribute source code for the LGPL'd libraries you use or modify (or indicate where to download them) but doesn't GPLize the code you wrote that isn't part of the libraries. So you can use it in your proprietary product without publishing your code, charge money for it, etc.

Ah ok, well I'm no lawyer.. I did look at the GMP license and it still appeared to be worded rather strangely. If the library is linked in to your code then your code must also be open source. If the library is instead loaded at runtime and also is not required for the application to function, it appears the rest of the source can be closed.. I refer to section 6, and section 7 subsection 1. However it's worded, I've found a different math library who's only restriction is that if I decided to charge money for whatever I've written with it, I have to pay the author of the library an amount equal to the cost of one license for the application. A lot more straightforward, and appealing than the legalese of the (L)GPL. See ya 'round. -------signature file------- "'There comes a time when the operation of the machine becomes so odious, makes you so sick at heart, that you can't take part; you can't even passively take part, and you've got to put your bodies upon the gears and upon the wheels, upon the levers, upon all the apparatus, and you've got to make it stop. And you've got to indicate to the people who run it, to the people who own it, that unless you're free, the machine will be prevented from working at all!" -Mario Savio- Founder of the Free Speech Movement.

At 01:44 09/09/2000 -0700, Bill Stewart wrote:

Not incorrect, but 2**256 possible keys gets you into age-of-the-universe territory for cracking.

Well yes, but better safe than sorry.. you never know when the next breakthrough might come that makes anything under 256bits "weak." Not too likely I know, but doesn't hurt to keep that in mind.

I'm not aware of one. IDEA's "non-commercial" definitions have gotten fuzzier over the years, and it's patented in lots of places. Avoid Misty. Several of the AES candidates had policies of "it's patented now but if we're the AES winner you can all use it for free", which means you won't really know licensing issues until NIST picks a winner.

Ah.. I'll just have to keep digging myself.. maybe I'll put together a page of my own for this purpose. It's aggravating having to dig all over the place for this kind of info. What's the deal with Misty? ....signature.... PGP Key ID: 0xCCC57FD7 PGP Key Fingerprint: 446B 7718 B219 9F1E 43DD 8E4A 6BE9 D739 CCC5 7FD7 Available from ldap://certserver.pgp.com