Cryptography-Digest Digest #243, Volume #13 Wed, 29 Nov 00 19:13:00 EST
Contents:
Re: keysize for equivalent security for symmetric and asymmetric keys
([EMAIL PROTECTED])
password synchronisation ("johan cowe")
Re: DES question: Has this ever been proven before? (Francois Grieu)
Re: SRP - not good enough? (Thomas Wu)
Re: SRP - not good enough? (Thomas Wu)
Re: RC4 Questions (Tom St Denis)
Re: On mutation of crypto algorithms (Tom St Denis)
Re: keysize for equivalent security for symmetric and asymmetric keys (Roger
Schlafly)
Re: SRP - not good enough? (John Savard)
Re: SRP - not good enough? (John Savard)
Re: SRP - not good enough? (John Savard)
Re: SRP - not good enough? (David Hopwood)
Re: keysize for equivalent security for symmetric and asymmetric keys ("Michael
Scott")
Re: SRP - not good enough? (John Savard)
Re: keysize for equivalent security for symmetric and asymmetric keys (David Wagner)
Re: keysize for equivalent security for symmetric and asymmetric keys (David Wagner)
Re: keysize for equivalent security for symmetric and asymmetric keys (Stanley Chow)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Wed, 29 Nov 2000 22:02:45 GMT
In article <903sgc$jv9$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
>
> (2) Why do you go from "Phil Zimmermann says..." to "It is generally
> accepted"? On what basis do you make this extrapolation?
> Phil is right when he says "same work factor", but "same work factor"
> does not mean "equivalent strength".
sorry, am not a regular in sci.crypt,
am a regular in pgp newsgroups, where people are familiar with PRZ's
quotes and do 'generally accept' it as a guideline for practical pgp
key sizes.
will try to be more exact for further posts here.
> > the 15k rsa estimate given is very helpful toward that end,
>
> Using a 15K RSA key is worse than ridiculous. Using a 256 bit
> AES key is gross overkill as well.
agree and never planned to do so,
intent of the question was to establish a similar upper bound that PRZ
wrote for the 128 bit session key, now that pgp 7.0 allows for 256 bit
Twofish, and c-kt builds of pgp 7.0 will probably be available in the
future.
vedaal
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "johan cowe" <[EMAIL PROTECTED]>
Subject: password synchronisation
Date: Wed, 29 Nov 2000 23:03:59 +0100
Hello,
At our firm, we are looking for a password-synchronisation tool that works
as well on Mainframe (ACF2 !!!), UNIX, NT ... as much platforms as possible.
We are looking for tools like 'PSynch'
Anyone who can help us, please mail to: [EMAIL PROTECTED]
Greetings,
Johan Cowe - NV Infoco (Belgium)
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: DES question: Has this ever been proven before?
Date: Wed, 29 Nov 2000 23:17:33 +0100
David Wagner wrote:
> Now we can go back to the beginning and compute a(i),a(i+n)
> for i=1,2,3,...; note that the smallest i such that a(i) = a(i+n)
> is always less than or equal to n, and moreover a(i-1), a(i+n-1)
> give the desired collision.
I like these enlighted days when I learn something simple and
potentialy usefull. Thanks, David. You where right, and now you
explained why.
> If a(n) = a(2n), then the period of the cycle is n. Well, the
> period might divide n, but almost always it is n, if n is the
> least value such that a(n) = a(2n) and if you are iterating a
> random function.
Now I'll believe you on this one, but is there a simple argument
showing that the header length is almost allways smaller than the
cycle ?
Francois Grieu
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: SRP - not good enough?
Date: 29 Nov 2000 14:29:22 -0800
[EMAIL PROTECTED] (John Savard) writes:
> In SRP, the host computer stores the values s and v, where v is a
> public key, derived from a private key calculated from a hash of s and
> the user's password.
>
> This means that a dictionary attack can be mounted on the password
> file, since for each password tried, one just performs two direct
> computations: hash s and P, then calculate a public key from a private
> key.
This is true of any strong password method where only one server
participates, including A-EKE, B-SPEKE, and the appropriate PAK
variants. The non-verifier-based protocols don't even supply this
level of protection, since the server data is plaintext-equivalent
to the password.
If you capture the server's secrets, you can simulate the server and
have the ability to distinguish valid passwords from invalid ones.
You can make this more difficult by splitting the verification
information securely across multiple servers, a la Kaliski/Ford.
--
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/srp/
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: SRP - not good enough?
Date: 29 Nov 2000 14:33:46 -0800
[EMAIL PROTECTED] (John Savard) writes:
>
> Since the claim for PAK-X, or, now, PAK-RY, was that it was not
> vulnerable to server compromise, nothing was mentioned about
> vulnerability to compromise of files on the user's computer. I
> concluded that meant that problem was not solved; I suppose this means
> I was mistaken, and there is nothing on the user's computer to
> compromise.
>
> My specific concern, though, is with what was stored on the host
> machine for SRP:
>
> a random hash value s,
>
> and the Diffie-Hellman public key A^H(p,s) mod P.
All strong password protocols that use one server can be attacked IF
the server is compromised in this way. SRP is no different in this
regard.
> PAK, I'll admit, is still a bit beyond my depth. If indeed PAK has
> succeeded where SRP failed, without needing to cheat in the way I
> proposed (by having a secure server behind the host system) to fulfill
> the goals:
There is no failure - what you seem to be asking for is provably
impossible. It can be addressed by using multiple servers, or
other variants based on altering assumptions.
--
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/srp/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
Date: Wed, 29 Nov 2000 22:31:14 GMT
In article <903pe1$2stv$[EMAIL PROTECTED]>,
"James" <[EMAIL PROTECTED]> wrote:
> After reading the information on the ciphersaber web site, I have a
few
> questions about RC4.
>
> The site led me to believe that the maximum secure key length was 512
bits
> (where the key is the string used to initialize the random number
> generator). Is this correct??? Could I use a longer key and not
have my
> security compromised?
The maximum effective key size is log2(256!) ~ 1683 bits in length.
However, keys over 256 bits in length are purely overboard.
> Also, the ciphersaber implemtation suggests appending a fixed number
of
> random bytes to the end of the key (10), and then placing these
random bytes
> at the start of the encrypted stream. Doesn't this compromise
security???
> Is there something I'm missing??
Yes. Figure out why for yourself!
> Also, I own a copy of Applied Cryptography, and in the description of
RC4 it
> states you could make the S array larger.... in the standard
algorith, it's
> at 8x8, but the book suggested changing this to 16x16, and
lengthening the
> init period for the sake of speeding up the algorith (you can code 2
bytes
> at a time now...) Would this have any affect on the security of the
> alogorithm at all?? Would larger sizes be more secure (like 32x32)??
First off I suggest you study what an sbox is first. A 16x16 sbox
requires 128kb of ram and would actually slow down RC4 (on a commodity
desktop). A 32x32 is infeasible at best.
> Finally, I was thinking of creating a larger byte pattern using the
password
> and the password length, and then hashing with SHA to get a final 160-
bit
> key to encrypt with... is there anything that I should be careful
about or
> watch out for???
Well if you use a hash to parse the key before sending it to RC4 (a
good idea btw) make sure you append a IV to the user key before hashing.
>
> Thanks for the information... I appreciate it.
No problemo.
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: Wed, 29 Nov 2000 22:31:48 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > > An interesting question is how would a scaled-down version
> > > of Rijndael compete with DES. My feeling of the gut is that
> > > 20 rounds would probably suffice to provide a fairly safe
> > > bet.
> >
> > Irrelevant. Rijndael cannot process 64-bit blocks. The closest
thing
> > is a 72-bit block.
>
> What hinders a scaling-down to 64 bit blocks?
The fact that you cannot build a square with eight elements...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Wed, 29 Nov 2000 14:41:19 -0800
Doug Kuhlman wrote:
> > Unstated: "Because I work for Certicom and it is in my company's
> > best interest to make RSA keys as large as possible relative to EC
> > keys. That way, EC cryptography appears to have much better
> > performance".
> >
> I just feel compelled to point out that Bob Silverman works for RSA, so
> you have to take his arguments and numbers with a grain of salt, too.
> And don't ask me, because I'm not unbiased on this topic, either.
Yes. Funny how neither one of them uses an email address or sig line
that identifies his employer. (Ok, I don't either.)
I am certainly not partial to RSA Security. I battled them in court.
But Bob is right about this. If you want to estimate the security of
RSA, then you have to look at the cost of the best attacks on RSA.
Don argues that it is more conservative to make certain unrealistic
assumptions, such as infinite memory being completely free, but this
makes no sense to me. Such an assumption might be useful as a
simplifying assumption, but it is not conservative.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: SRP - not good enough?
Date: Wed, 29 Nov 2000 22:31:54 GMT
On Wed, 29 Nov 2000 13:32:04 -0500, Philip MacKenzie
<[EMAIL PROTECTED]> wrote, in part:
>What files? No information about the password is stored
>on the user's machine in any of these protocols (PAK, SRP, EKE, etc.).
Yes, I completely got that wrong, nothing is stored on the user's
machine in PAK-RY. But the protection against server compromise in
PAK-RY does _not_ exclude the possibility of a dictionary attack on
the password file, as is specifically noted on your page, so, except
for the fact that it has a proof of security, PAK-RY belongs to the
same general class as SRP, providing good security, but not 'ideal'
security in a sense (a dictionary attack can be cheaper than cracking
Diffie-Hellman even once).
Presumably, one could envisage a protocol in which the user's password
was augmented with something on the user's computer to give the user,
in effect, a longer password. This would prevent dictionary attacks if
the server, but not the user's computer, was compromised, and it would
therefore be of value in some situations.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: SRP - not good enough?
Date: Wed, 29 Nov 2000 22:39:18 GMT
On Wed, 29 Nov 2000 13:32:04 -0500, Philip MacKenzie
<[EMAIL PROTECTED]> wrote, in part:
>See the Ford and Kaliski paper linked from the
>Integrity Sciences web site for discussion on this...
>http://www.IntegritySciences.com/links.html
Interesting, and far more advanced than the relatively simple idea I
was thinking of.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: SRP - not good enough?
Date: Wed, 29 Nov 2000 22:51:43 GMT
On 29 Nov 2000 14:29:22 -0800, Thomas Wu <[EMAIL PROTECTED]>
wrote, in part:
>If you capture the server's secrets, you can simulate the server and
>have the ability to distinguish valid passwords from invalid ones.
>You can make this more difficult by splitting the verification
>information securely across multiple servers, a la Kaliski/Ford.
I was thinking of somehow putting a piece of the verification
information on the user's computer (used as a terminal) to get around
this.
For this to be secure, even when the terminal's persistent secrets are
compromised, is probably impossible. But because the terminal's
secrets are closer to the password, because nonce public/private key
pairs can be generated at both ends, and because a protocol could make
use of more than one hash involving the password, I didn't want to
totally deny the possibility of some clever idea that I might have
missed.
At the end of the day, though, the host needs to have a pass/fail
result of the user's identity, regardless of the nonce values for a
particular run, so without a non-compromised server somewhere, indeed
it seems this is impossible. Kaliski/Ford is more powerful than my
idea, since it doesn't specify which server has to be the one not
compromised - essentially, I thought of a Kerberos-style security
server that acted like a second user, able to type in a longer
"password" at the other end of the link.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Wed, 29 Nov 2000 23:05:22 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: SRP - not good enough?
=====BEGIN PGP SIGNED MESSAGE=====
John Savard wrote:
> In SRP, the host computer stores the values s and v, where v is a
> public key, derived from a private key calculated from a hash of s and
> the user's password.
>
> This means that a dictionary attack can be mounted on the password
> file, since for each password tried, one just performs two direct
> computations: hash s and P, then calculate a public key from a private
> key.
The design constraints for SRP-3 assume that the client stores no
persistent data. In that case, if the password file is compromised,
the attacker can simulate both sides of the protocol, and so nothing
could prevent it from being able to do a dictionary attack.
If you don't have the constraint that clients can store no persistent
data, then instead of having the server store the salt and sending it
in the protocol, have the client store it as a local secret [*]. The salt
should be random and of length suitable for a secret key. Then an
attacker has to compromise both client and server, in order to be able
to do a dictionary attack. This should work for other strong password
protocols, as well as SRP-3.
Another advantage of this is that if you calculate the verifier as
g^(H*(H(P) XOR salt)), where H is an ordinary hash and H* is the
computationally intensive hash, then a client can change its password
entirely locally, by setting salt := salt XOR H(oldP) XOR H(newP).
(It is still necessary to have some way of changing the server's
verifier, since that is the only way of recovering if a password is
compromised. However, the server doesn't need to know, or be able to
dictionary-attack, the client's password.)
[*] A particularly useful variant would be to store the salt on a
smart-card; in order to implement two-factor authentication. If
the smart-card is stolen and its secrets recovered, the attacker
still has to either guess the password on-line, or compromise the
server.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOiT81zkCAxeYt5gVAQEWXwf+NrY2FtfmRY9QPo0syC6XYs3c/Z+QXbm0
ezP4eKMzCkTpAWRzMoT9Nq0FACwhOQffI18yosNEGp5kE81TUA5MMY0tVnk0rufg
z44NXhFRw1AWG1oBsxiC6Y4GDV24yCIhn3OMN1f+q7Ug91+qcorvcAXBFU04PL41
4xQsh19c+yAeFKN+NkHKn7l8+AwLAAeI17PCVW5LkxmAG9tnKxk0YD7BjNBWFSBg
PK2FdPRIDEs0ZTnyGpv1IgUt+yVN2aWSzU1249LQmUu300V6xVyU50KCa4772KRf
o5UUzoq9mZSXBigadA+S7TZB9SgJ5OlfitwcDBcLKTNwcPN1lqIRdA==
=cbGW
=====END PGP SIGNATURE=====
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Wed, 29 Nov 2000 23:27:57 -0000
"Bob Silverman" <[EMAIL PROTECTED]> wrote in message
news:903sgc$jv9$[EMAIL PROTECTED]...
>
> Using a 15K RSA key is worse than ridiculous. Using a 256 bit
> AES key is gross overkill as well. I suggest you do the arithmetic
> to see how long it will take to break a 128-bit key. You may assume
> computers 1 million times faster than existing computers. You may
> assume that you have a billion of them available.......
> you buy.
Perhaps the thinking behind 256-bit keys is in response to the threat from
quantum computing, for which if I remember right there there is an O(n^0.5)
algorithm for exhaustive search - which brings us back effectively to 128
bits
Mike Scott
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: SRP - not good enough?
Date: Wed, 29 Nov 2000 23:20:12 GMT
On 29 Nov 2000 14:33:46 -0800, Thomas Wu <[EMAIL PROTECTED]>
wrote, in part:
>There is no failure - what you seem to be asking for is provably
>impossible. It can be addressed by using multiple servers, or
>other variants based on altering assumptions.
OK. I suspected that, but such things as nonces and secrets (which I
assumed could be compromised too) on the user's computer made the
proof too complicated for me to carry it out, so I thought there might
be room for a clever idea I was missing.
That's why I came up with a multiple server idea that was not nearly
as sophisticated as Ford/Kaliski. (See Password Protocol: a need to
cheat?)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: 29 Nov 2000 23:43:20 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
One issue that I don't see discussed much is that traditionally
algorithms have often been compared in the published literature
by their complexity, where complexity := max {time, storage}.
For today's factoring algorithms, usually time >> storage. But,
since it is usually easier to find resources to do N
modular-exponentiations than to store N words of memory, it's
not clear that this is the right measure. Arguably a better
measure for security might be something like cost (in dollars).
At the same time, it seems likely that research is driven -- at
least in part -- by a desire to publish, and if publication goes
more by the "complexity" measure than the "cost" measure, I could
imagine a possibility that this might have the effect of slightly
biasing the direction of research.
(My impression is that this is changing, at least in the crypto
conferences, but there is always some inertia in academia, and
also, since the state of knowledge today is the sum of all past
work, I would still expect that the historical criteria might
have some semi-lasting effect on today's understanding of these
problems.)
If all the above conjectures are correct, then we could imagine
that there might be a systematic bias against research in algorithms
that would reduce storage cost and in favor of research in new
techniques that reduce the running time (potentially at some cost
in storage). The effect would be that we might be over-estimating
the storage complexity of factoring by a wider margin than we are
over-estimating its time complexity.
If this is true, then it might be reasonable to adjust for this
bias by conservatively assuming that today's algorithms are a
little bit pessimal with respect to their memory usage, and that
the gap between the true and today's-estimate memory complexity
of factoring is wider than the gap between the true and estimated
time complexity of factoring.
This might justify downplaying the storage costs of today's
factoring algorithms, making the conservative assumption that
tomorrow's clever attacks might find a way to ensure that the
storage costs are not the barrier.
But: I'm not a factoring expert, so I'm wildly guessing here, and
the above should be treated as a speculative hypothesis. I'd be
interested to hear opinions on whether you think that this is a
valid concern.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: 29 Nov 2000 23:45:15 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Roger Schlafly wrote:
>Don argues that it is more conservative to make certain unrealistic
>assumptions, such as infinite memory being completely free, but this
>makes no sense to me. Such an assumption might be useful as a
>simplifying assumption, but it is not conservative.
That's not the conservative assumption. The conservative assumption
is that advances in factoring might reduce the storage costs more than
they reduce the running time in factoring algorithms.
This assumption may or may not be the best one to base your analysis
on, but it *does* fit the usual definition of what it means to be
conservative as a cryptosystem designer.
------------------------------
From: Stanley Chow <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 30 Nov 2000 00:07:10 GMT
David Wagner wrote:
>
> That's not the conservative assumption. The conservative assumption
> is that advances in factoring might reduce the storage costs more than
> they reduce the running time in factoring algorithms.
There is an unspoken agreement that whatever the assumptions, the result
should be useful. In particular, if the objective is to compare RSA
vs ECC, then it is important to compare them fairly; otherwise, the
whole thing is a waste of time.
> This assumption may or may not be the best one to base your analysis
> on, but it *does* fit the usual definition of what it means to be
> conservative as a cryptosystem designer.
I have a new model - conservatively assume that advances in DL might
reduce CPU time to O(n). What conclusion would you draw? Would it
be useful?
--
Stanley Chow VP Engineering [EMAIL PROTECTED]
Cloakware Corp (613) 271-9446 x 223
------------------------------
** 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
******************************
