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
******************************
