Digestifier
Sun, 03 Dec 2000 09:01:55 -0800
Cryptography-Digest Digest #264, Volume #13 Sun, 3 Dec 00 12:13:01 EST Contents: Re: Pentium 4 and modular exponential (Quisquater) Re: SRP - not good enough? (Thomas Wu) Re: Entropy paradox (Mok-Kong Shen) Re: Revised cipher (Mok-Kong Shen) Re: On mutation of crypto algorithms (Mok-Kong Shen) Q: Discrete transforms in practice (Mok-Kong Shen) Re: Q: Discrete transforms in practice (Tom St Denis) Re: On mutation of crypto algorithms (Tom St Denis) Re: Revised cipher (Simon Johnson) Re: The Next Step After OTP (John Savard) Re: SRP - not good enough? (John Savard) Re: The Next Step After OTP (John Savard) Secure Passwords On The Cheap (John Savard) Re: The Next Step After OTP (John Savard) ---------------------------------------------------------------------------- From: Quisquater <[EMAIL PROTECTED]> Subject: Re: Pentium 4 and modular exponential Date: Sun, 03 Dec 2000 10:41:59 +0100 Paul Rubin wrote: > > Wei Dai <[EMAIL PROTECTED]> writes: > > The 32x32 -> 64 packed multiply instruction (PMULUDQ) in SSE2 is > > clearly designed with modular exponentiation in mind. > > What makes you say that??? If it were made for big-integer arithmetic > it would have a wide carry register or large accumlator. The best > architecture I've seen yet for modexp is the Motorola 56000 series DSP. > This can start a 24x24 multiply-accumulate every cycle, with a 56 bit > accumulator, so you can add up to 256 partial products before you > have to worry about carry overflow. The best architectures for modexp are the dedicated ones at the moment (for instance, the coprocessor from Philips FAME-X smart card using a 32-bit architecture model, from Thomson, from Siemens, ...). See also the strongARM. What I don't understand very well is the fact it is well known what to do for good modexp and designers are again and again doing the same wrong things (maybe they are only thinking in terms of DSP). ------------------------------ From: Thomas Wu <[EMAIL PROTECTED]> Subject: Re: SRP - not good enough? Date: 03 Dec 2000 01:41:06 -0800 [EMAIL PROTECTED] (John Savard) writes: > On 01 Dec 2000 22:18:47 -0800, Thomas Wu <[EMAIL PROTECTED]> > wrote, in part: > > >So the > >final answer might be that strong password protocols ARE in fact "good > >enough" by your requirements. > > I think they aren't, but I can't prove it. In fact, the rest of your post seems to indicate exactly that they are, because the strategies you describe can be relatively easily applied to nearly all strong password methods, which would retain their ability to leverage resistance to network dictionary attacks, while improving resistance to dictionary attacks based on compromise of stored information. There seems to be an unstated false assumption here that strong password protocols can't solve this problem, when in fact the reality is that they make ideal building blocks to implement effective solutions to this exact problem in a variety of threat environments, as I explain later. > Basically, the assumptions I started with are that: > > 1) at the start, the client has an opportunity to communicate securely > with the host, and the host is informed of the client's password, or a > function of it; > > 2) neither the client's computer, nor the host's computer, is > considered to be vulnerable to compromise of the actual computations > performed to carry out the protocol; > > 3) both the client's computer and the host's computer may have some > information stored persistently between sessions, _but this > information is vulnerable to compromise in both cases_. > > This does mean that an attacker can simulate everything both computers > do, and so test the protocol by trying passwords. So it _seems_ like I > can't avoid plaintext equivalence of some of the persistent data - it > seems like I can't be immune to a dictionary attack. > > However, I was thinking I _might_ be missing something nonobvious, > involving things like setting up encryption with nonces, functions > with one-sided collision resistance, and so on. > > Now, Kaliski-Ford is one way to achieve a 'good enough' security by > changing the assumptions - but only slightly, and in a robust way. > > I thought in more pedestrian directions, and noted how a specific > secure box, which acted like a *good password typer* at the host end > could be used. > > There are other possible variations. Perhaps in addition to a short > password for each account, the user might keep a good key on his > system in storage protected by one passphrase...i.e., the host > computer could retain the password hash of each user _encrypted by his > PGP public key_. This way, the user is memorizing a good pass phrase, > but not a different one for each computer he uses. > > Doing encryption inside a secure 'cryptoprocessor' at one or both ends > could also solve the problem because all that's needed is secure > storage of one private key for each user. > > So the second question would be, if the assumptions need to be > changed, what is the most convenient way to change them, without > losing most of the advantages of these schemes? If we can't get > exactly what we want, how can we come the closest? Kaliski-Ford is one > good answer to that. You need to introduce some other non-compromised authentication factor into the system to avoid the "client-server simulation" attack. KF's solution uses an additional server as that factor. Your proposals use a secure crypto module on either the client or server end. Either way, it is fairly straightforward to extend almost any existing strong password protocol to incorporate this additional secure storage, with varying consequences for convenience. The advantage to building your solution on time-tested password protocols is that they are more trustworthy and well-studied than a more ad-hoc proposal, and it is less likely that you will accidentally introduce new vulnerabilities that make it weaker than a straight password-only protocol. > John Savard > http://home.ecn.ab.ca/~jsavard/crypto.htm -- Tom Wu * finger -l [EMAIL PROTECTED] for PGP key * E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in Phone: (650) 723-1565 exchange for security deserve neither." http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/ ------------------------------ From: Mok-Kong Shen <[EMAIL PROTECTED]> Subject: Re: Entropy paradox Date: Sun, 03 Dec 2000 11:21:06 +0100 John Savard wrote: > [snip] > While it takes effort to increase 'computational entropy' as you call > it, it takes a different kind of effort to increase real entropy, and > the distinction is very important. That is what I was arguing. Agreed. On the other hand, it seems to be true that it is often more difficult to obtain (and use) more 'real' entropy than more 'computational' entropy, because in the first case one has to use a hardware source and there is the problem of communicating the (more voluminous) bit sequences to the partner. (It may be mentioned that in block encryption a (little) key is used to secure a huge amount of information and that's a common manifestation of 'computational entropy'.) M. K. Shen ------------------------------ From: Mok-Kong Shen <[EMAIL PROTECTED]> Subject: Re: Revised cipher Date: Sun, 03 Dec 2000 13:01:11 +0100 Benjamin Goldberg wrote: > > I've done a bit of rewriting on the cipher I recently sent to this NG. > I've added a key schedule, and written the decryption function. A little bit off-topic comments: It is in my view extremely remarkable that the authors of Rijndael have succeeded to realize a fairly simple and very strong block cipher. (Of the four components in its rounds, three are key-independent and 'clean', while the remaining one is simply an addition of the round key.) Independent of Rijndael's status as the future standard of encryption, this fact inevitably means an essential barrier to users' acceptance of alternative future algorithms. For they would ask themselves: Why complicated, if simple stuffs will do? (I subjectively consider your use of LFSR to be not simple.) M. K. Shen ------------------------------ From: Mok-Kong Shen <[EMAIL PROTECTED]> Subject: Re: On mutation of crypto algorithms Date: Sun, 03 Dec 2000 12:59:15 +0100 Tom St Denis wrote: > > [EMAIL PROTECTED] wrote > > > > The Rijndael state doesn't have to be square. Either a 2x4 array > > (Nb = 2, word size 4 bytes, and shift offsets C1 = 1, C2 = 0, C3 = 1, > > for example) or a 4x2 array (Nb = 4, word size 2 bytes, C1 = 1) appear > > to work. > > Wouldn't it have to be a 4x2 to work? The C(x) column transform is a > 4x4 MDS is it not? But you can use a 2*2 matrix. (On scaling-down, one normally has to twist a little bit.) M. K. Shen ------------------------------ From: Mok-Kong Shen <[EMAIL PROTECTED]> Subject: Q: Discrete transforms in practice Date: Sun, 03 Dec 2000 13:02:42 +0100 I like very much to know whether, which kinds of, and to what extent and success, if any, discrete transforms (other than PHT used in some algorithms) have occured in actual practical applications. Thanks in advance. M. K. Shen ------------------------------ From: Tom St Denis <[EMAIL PROTECTED]> Subject: Re: Q: Discrete transforms in practice Date: Sun, 03 Dec 2000 15:02:55 GMT In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]> wrote: > > I like very much to know whether, which kinds of, and to > what extent and success, if any, discrete transforms (other > than PHT used in some algorithms) have occured in actual > practical applications. Thanks in advance. Things like the DFT and DCT are not normally "invertable" in practice. The Fast Fourier Transform is used in numerous designs such as the CS- Cipher and FFT-HASH (and TC2 out of my personal collection). Tom Sent via Deja.com http://www.deja.com/ Before you buy. ------------------------------ From: Tom St Denis <[EMAIL PROTECTED]> Subject: Re: On mutation of crypto algorithms Date: Sun, 03 Dec 2000 15:03:43 GMT In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]> wrote: > > > Tom St Denis wrote: > > > > [EMAIL PROTECTED] wrote > > > > > > > The Rijndael state doesn't have to be square. Either a 2x4 array > > > (Nb = 2, word size 4 bytes, and shift offsets C1 = 1, C2 = 0, C3 = 1, > > > for example) or a 4x2 array (Nb = 4, word size 2 bytes, C1 = 1) appear > > > to work. > > > > Wouldn't it have to be a 4x2 to work? The C(x) column transform is a > > 4x4 MDS is it not? > > But you can use a 2*2 matrix. (On scaling-down, one normally > has to twist a little bit.) You can't perform the C(x) on a 2x2, only on a 4x1. Otherwise it is NOT rijndael. Tom Sent via Deja.com http://www.deja.com/ Before you buy. ------------------------------ From: Simon Johnson <[EMAIL PROTECTED]> Subject: Re: Revised cipher Date: Sun, 03 Dec 2000 15:37:44 GMT In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]> wrote: > > > Benjamin Goldberg wrote: > > > > I've done a bit of rewriting on the cipher I recently sent to this NG. > > I've added a key schedule, and written the decryption function. > > A little bit off-topic comments: > > It is in my view extremely remarkable that the authors > of Rijndael have succeeded to realize a fairly simple and > very strong block cipher. (Of the four components in its > rounds, three are key-independent and 'clean', while the > remaining one is simply an addition of the round key.) > Independent of Rijndael's status as the future standard of > encryption, this fact inevitably means an essential barrier > to users' acceptance of alternative future algorithms. For > they would ask themselves: Why complicated, if simple > stuffs will do? (I subjectively consider your use of LFSR > to be not simple.) > > M. K. Shen > Yeah, if your gonna use an LFSR. Why not replace the whole round- function with one. That allows you to have nearly any block size you want. Any key-size you want and it would be fast in hardware (but not so fast in software). As an Example, take an Self Shrinking LFSR of length 64-bits. Allocate 32-bits to the key shedule and 32-bits to the plain-text block. Then clock 32-bits out of the generator as the output of your round function. I'd take a guess and say that this cipher is equal in security to that of the LFSR. And is considerably simpler than the one you created. -- Hi, i'm the signuture virus, help me spread by copying me into Signiture File Sent via Deja.com http://www.deja.com/ Before you buy. ------------------------------ From: [EMAIL PROTECTED] (John Savard) Subject: Re: The Next Step After OTP Date: Sun, 03 Dec 2000 15:51:32 GMT On Sun, 3 Dec 2000 00:07:42 -0800, "Scott Fluhrer" <[EMAIL PROTECTED]> wrote, in part: >Actually, the usual approach to avoid bit-flipping (or any other form of >active attack) is to add a MAC (message authentication code). That's certainly true, and that can be combined with public-key methods to make a digital signature and so on as well. I am sorry if, by neglecting to mention that possibility, my post appeared misleading. I was simply noting that the OTP is sometimes considered inadequate _as a cipher_ because it is vulnerable to bit-flipping, while other ciphers (i.e. DES in CBC mode) are not, and therefore I was concerned with showing how the OTP could be adapted, with minimal alteration, to correct this. John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm ------------------------------ From: [EMAIL PROTECTED] (John Savard) Subject: Re: SRP - not good enough? Date: Sun, 03 Dec 2000 16:06:19 GMT On 03 Dec 2000 01:41:06 -0800, Thomas Wu <[EMAIL PROTECTED]> wrote, in part: >You need to introduce some other non-compromised authentication factor >into the system to avoid the "client-server simulation" attack. Exactly. And, since I'm looking at the question from the viewpoint of research, and not implementing something tomorrow, I'm looking to see if there is a new and unexpected way of having such an authentication factor with a lower "cost" than in existing methods. Ah, *of course*. (smacks head) Just force *root* to sign on with a long pass phrase every time the system is booted up, if the assumption is that memory can't be compromised, but the hard disks can. (Taking that assumption that far makes it highly flawed from a security standpoint, but that's *another* issue.) John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm ------------------------------ From: [EMAIL PROTECTED] (John Savard) Subject: Re: The Next Step After OTP Date: Sun, 03 Dec 2000 16:00:44 GMT On Sun, 03 Dec 2000 08:37:27 GMT, Bryan Olson <[EMAIL PROTECTED]> wrote, in part: >I dislike your proposed solution because it does not detect >forgeries. It is still vulnerable to bit-flipping, though >the attacker cannot choose the decrypted outcome. You are quite right that using a secure hash function is more normal and more sensible. Since whoever knows the plaintext knows its hash, there are still some wrinkles to doing authentication with OTP, but that is the sort of thing you and others have explained. (i.e., eliminate known plaintext by picking 160 random bits, then use the OTP to encipher the message consisting of the 160 random bits, the 160 random bits XOR the hash of the message, and the 160 random bits repeatedly XORed with the plaintext of the message) As noted in my other reply, I was simply addressing the idea that the OTP is inadequate _as a cipher_, so I wanted to show how one could advance from the OTP to something that provides an essentially random permutation for each symbol without having to go to a completely different type of cipher. I did not mean to mislead people away from the use of hash functions, which is indeed more sensible when real authentication is desired. John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm ------------------------------ From: [EMAIL PROTECTED] (John Savard) Subject: Secure Passwords On The Cheap Date: Sun, 03 Dec 2000 16:19:30 GMT In an earlier series of posts, I expressed concern with SRP and PAK, because they did not really eliminate the possibility of a 'dictionary attack' on passwords if the password file in the server was compromised. Such an attack would be slowed by involving public key computations, but not public-key cracking as in the simple passive attack on EKE communications. I tried to address the problem using a hierarchical model inspired by Kerberos; a secure machine, in effect, types a second 'password' for the user at the host end. I learned about the Kaliski-Ford method, which uses multiple hosts at an equal level, but maintains security as long as they are not all compromised. Well, given the assumption that ongoing processes and RAM aren't compromised, because if they can be, no security could be obtained, but everything left on a hard drive is subject to compromise, I have come up with a 'solution' to the problem which stretches this assumption to its limit - by making one item kept in memory a very attractive target - but which does provide the level of cryptographic security I think is needed, even if it is dubious from the larger computer security viewpoint - while not requiring the users to memorize better passwords, or requiring any special hardware to be put in. It's really quite simple. Use a long, secure, PGP-style pass-phrase...to encrypt the password file. Require the system operator to type it in when starting up the system. Then, the secret key for each user, kept in the password file, corresponding to the public key for the user which is on the user's computer, encrypted by his little password, is now well enough protected that we actually have security. Of course, that does *not* mean it isn't a very good idea to have a separate computer, that users don't run their own programs on, to handle the encryption and user authentication, it just means that a halfway decent solution that really does eliminate the dictionary attack is possible without extra hardware. John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm ------------------------------ From: [EMAIL PROTECTED] (John Savard) Subject: Re: The Next Step After OTP Date: Sun, 03 Dec 2000 16:33:31 GMT On Sun, 03 Dec 2000 16:00:44 GMT, [EMAIL PROTECTED] (John Savard) wrote, in part: >(i.e., eliminate known plaintext by picking 160 random bits, then use >the OTP to encipher the message consisting of the 160 random bits, the >160 random bits XOR the hash of the message, and the 160 random bits >repeatedly XORed with the plaintext of the message) Oops. That would NOT work. Change that to: 'the message consisting of the 160 random bits, the plaintext of the message XORed repeatedly with the 160 random bits, and the hash of the message as so modified', and it will work. With a known plaintext and a known hash, bit flipping isn't prevented if what one does is equivalent to just using a different OTP - which is what my imperfect proposal would be. John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm ------------------------------ ** FOR YOUR REFERENCE ** The service address, to which questions about the list itself and requests to be added to or deleted from it should be directed, is: Internet: [EMAIL PROTECTED] You can send mail to the entire list (and sci.crypt) via: Internet: [EMAIL PROTECTED] End of Cryptography-Digest Digest ******************************