Cryptography-Digest Digest #590, Volume #13 Tue, 30 Jan 01 02:13:00 EST
Contents:
Re: Security of Centrinity's FirstClass Product ("Scott Fluhrer")
Re: A Password Protocol (Benjamin Goldberg)
Re: How many bits of security can a password give? (Benjamin Goldberg)
Re: Primality Test ("Matthew J. Ricciardi")
Re: How many bits of security can a password give? (Paul Rubin)
Re: On combining permutations and substitutions in encryption (Terry Ritter)
Re: How many bits of security can a password give? ("Joseph Ashwood")
Re: How many bits of security can a password give? (Samuel Paik)
fast signing ("Joseph Ashwood")
Re: On combining permutations and substitutions in encryption ("Matt Timmermans")
Re: What do you do with broken crypto hardware? ("Lyalc")
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Security of Centrinity's FirstClass Product
Date: Mon, 29 Jan 2001 19:24:41 -0800
Jim Gillogly <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] wrote:
> >
> > You said:
> > > beware snake oil.
> >
> > Thanks... thats the impression I got too. Anything else? I need to give
> > a more "tangable" assessment of this product from a security point of
> > view, to a few who have not read 'The snake-oil FAQ'.
>
> If you're giving an <honest> assessment of the security of the product,
> you'll have to say that you can't. No matter how good the designer of
> their proprietary crypto algorithm is, it has evidently not gone through
> the kind of public gauntlet and thrashing that other algorithms have.
>
> Now that you know it's a stream cipher you can look at their white papers
> and such to see whether they make the obvious stupid play (i.e. using the
> same key for more than one message), and perhaps run some tests on the
> software itself to see whether other stuff is being obviously exposed,
> but there's no way you'll be able to assess the actual security of the
> product from a black box analysis.
Oh, and don't forget the other obvious stupid play -- allowing bit flipping
attacks, where the attacker can flip various ciphertext bits, and change the
corresponding plaintext bits undetected. This attack can be defended
against, but they might have forgotten...
--
poncho
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: A Password Protocol
Date: Tue, 30 Jan 2001 03:38:51 GMT
John Savard wrote:
>
> I suspect this password protocol isn't new, but as I don't recall
> offhand anything like it, I thought I would describe it here.
>
> Scenario:
>
> User: Knows a password.
>
> Host: A general purpose computer; files it has on its disks may be
> read by an adversary, but its computations are assumed to be secure.
>
> Security Computer: This computer is secure, but it's connected to the
> host over an insecure network, so both passive and active attacks on
> its link to the host are possible.
>
> I had hoped to avoid the use of public-key techniques, but if an
> adversary is impersonating the host, without such techniques, a user
> can be successfully impersonated (although an alarm would sound,
> because no genuine user could be successfully verified); but I only
> use them once, between the host and the security computer.
Given the scenario requirements, it seems quite obvious that the best
thing to be using is Kerberos. Do a google search, and you'll get lots
of decent descriptions.
A fairly good graphical description is the PDF file at:
http://www.computerworld.com/computerworld/records/images/pdf/kerberos_chart.pdf
An html description with useful references and GIF diagrams is:
http://www.isi.edu/gost/publications/kerberos-neuman-tso.html
>
> This is my solution to the problem.
>
> The Security Computer keeps a table containing:
>
> User ID; Hash of the user's password; User Master Key
>
> The Host keeps a table containing:
>
> User ID; Hash of the user's password after that password has been
> encrypted with the user master key.
>
> a) When the user logs in, the user first transmits his user ID to the
> host computer.
>
> b) The host computer then passes the user ID and a random session key
> *encrypted with the security computer's public key* to the security
> computer.
>
> c) The security computer transmits a challenge vector to the host
> computer.
>
> The challenge vector has the following form: it consists of the
> concatenation of the user master key, the session key, and a random
> value, and is then encrypted with the hash of the user's password.
>
> (To obtain the session key, the security computer needs to use its
> private key.)
>
> d) The host transmits the challenge vector to the user.
>
> e) The user enters his password, and the user's computer does the
> following:
>
> 1) The hash of the user's password is calculated: H(PW).
>
> 2) The challenge vector is decrypted: D(CV,H(PW)) -> ( MK, SK, R )
>
> 3) The master key is used to produce the hash of the user's password
> that the host computer posesses. H(E(PW,MK))
>
> 4) This hash is used as the key to encrypt the challenge vector, and
> the result is hashed.
>
> 5) This result is then encrypted by the session key, and the result is
> hashed, and this hash is transmitted to the host computer.
>
> f) The host computer, knowing H(E(PW,MK)) and the session key, can
> repeat the calculation applied to the challenge vector, and verify the
> user's identity.
>
> The security of this protocol rests on the fact that the session key
> is not available to an attacker.
>
> I was hoping to obtain security from the fact that the master key is
> not available to the attacker, but with the impersonator using
> modified software, a bogus security computer can issue an invalid
> challenge vector, and then the impersonator can simply encrypt that
> challenge vector using H(E(PW,MK)) obtained from the disk of the host
> directly. One needs to know H(PW) to issue good challenge vectors, so
> even without using public-key methods to protect the session key, an
> impersonation attempt will cause the system to fail.
>
> With protected session keys, however, the steps in this protocol
> relying on the master key become unnecessary, and it can be
> simplified:
>
> a) When the user logs in, the user first transmits his user ID to the
> host computer.
>
> b) The host computer then passes the user ID and a random session key
> *encrypted with the security computer's public key* to the security
> computer.
>
> c) The security computer transmits a challenge vector to the host
> computer.
>
> The challenge vector has the following form: it consists of the
> concatenation of the session key and a random value, and is then
> encrypted with the hash of the user's password.
>
> (To obtain the session key, the security computer needs to use its
> private key.)
>
> c) The host transmits the challenge vector to the user.
>
> d) The user enters his password, and the user's computer does the
> following:
>
> 1) The hash of the user's password is calculated: H(PW).
>
> 2) The challenge vector is decrypted: D(CV,H(PW)) -> ( SK, R )
>
> 3) The session key is used as the key to encrypt the challenge vector,
> and the result is hashed, and this hash is transmitted to the host
> computer.
>
> e) The host computer, knowing the session key, can repeat the
> calculation applied to the challenge vector, and verify the user's
> identity.
>
> Essentially, the host generates a session key in secret, and it is
> first transmitted to the security computer guarded by the security
> computer's public key, and then it is transmitted to the user's
> computer, guarded by the direct hash of the user's password, which is
> not kept on the host computer.
>
> Once the extraneous steps are removed, perhaps it isn't all that
> original...
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: Tue, 30 Jan 2001 04:17:27 GMT
Joseph Ashwood wrote:
>
> "Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > If you have a 14 char password, made of the first letter of each
> > word of a passphrase, you have something which is easily
> > memorizable, has a decent per-character entropy, is fairly easy to
> > type in, and works well with existing password systems, which often
> > limit the length of the password. There is significantly more
> > entropy per character with this method than if you used a 14 letter
> > english word, or two or three words whose lengths add up to 14.
>
> While it may be an over specification of it, I consider such
> constructs to be "passwords with memorizable derivers" so I would
> still consider them passwords. They certainly do have higher entropy,
> however not having studied in detail what the first letter of each
> word in a sentence is, I can't be certain of the entropy. Come to
> think of it, this could be rather easily estimated by taking a large
> collection of webpages, and looking at the first letter of each word,
> and building the list from there. I think I may do this processing
> some time. The only question what sources to use? I was considering
> using all the RFCs as a beginning.
> Joe
The problem with your proposed method of making a password/passphrase
dictionary is that any kind of text might be used, just as it might be
when the entire phrase is typed in. What are the odds of your method
having included in it tbatstdgagitw, unless you scanned in the
Jabberwocky?
People using this method are likely to use something from a book, not
something found on the web -- and since Jabberwocky is surely somewhere
on the web, don't use it! Could any of you possibly guess from what
poem the passphrase bakogasisatt came from, even with the hint that it's
the first sentence of each word? I seriously doubt it, even though it
is on the web.
Also, there's no reason to assume that users will always use the *first*
letter -- I could just as easily have used that bit of Jabberwocky to
generate winhloiyninha, or perhaps sgdeysdedenee, by using the second,
or last, letter of each word.
PS, if you want to know from what phrase I made bakogasisatt, send me an
email, and I'll tell you the name of the poem, and the lines I used.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: "Matthew J. Ricciardi" <[EMAIL PROTECTED]>
Subject: Re: Primality Test
Date: Mon, 29 Jan 2001 23:17:45 -0500
Thanks for the assistance. It's now testing 512-bit numbers in well under a
second.
Regards,
Matt Ricciardi
[EMAIL PROTECTED]
"Bryan Olson" <[EMAIL PROTECTED]> wrote in message
news:9551v7$rh3$[EMAIL PROTECTED]...
Matthew J. Ricciardi wrote:
> As an exercise for a discrete math course, I was asked to write
> a program to test numbers for primness. I also chose the use
> the Rabin-Miller method as described in Schneier's Applied
> Cryptography and am experiencing similarly slow performance.
[...]
> The source code for the computation currently reads as follows:
>
> z = 1;
>
> for(int x = 1; x <= m; x++)
> {
> z *= a;
> z = (z % p);
> }
[...]
> Can any further improvement be easily made to improve performance?
Read section 11.3 "Mathematical Background/Number Theory" from
the beginning. The algorithms you want are under "addition
chaining".
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: 29 Jan 2001 20:25:07 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> writes:
> If you have a 14 char password, made of the first letter of each word of
> a passphrase, you have something which is easily memorizable, has a
> decent per-character entropy, is fairly easy to type in, and works well
> with existing password systems, which often limit the length of the
> password. There is significantly more entropy per character with this
> method than if you used a 14 letter english word, or two or three words
> whose lengths add up to 14.
What I've found is after you use a password/phrase a few dozen times
you tend to remember it even if it's random. So when I generate a new
passphrase (example: "riley qa hahn tidy carne") I'll try to associate
some images with it (Ensign Riley from Star Trek performing quality
assurance on a chicken ("hahn" in German) well you get the idea. I'll
also (heresy!) write the phrase on a piece of paper and carry it
around, and refer to it whenever I need the passphrase. After a few
days logging in several times a day, I don't need the paper any more
and I can destroy it.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On combining permutations and substitutions in encryption
Date: Tue, 30 Jan 2001 04:40:14 GMT
On Tue, 30 Jan 2001 02:49:12 GMT, in
<IYpd6.175740$[EMAIL PROTECTED]>, in sci.crypt "Matt
Timmermans" <[EMAIL PROTECTED]> wrote:
>"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> The obvious attack is on the RNG keyspace, the internal state. But we
>> can easily make ciphers with hundreds of thousands of bits of internal
>> state, which is far more than "large enough." When we do, we at least
>> have the opportunity of proving that any attack on the keyspace must
>> be impractical. There is nothing unreasonable about this.
>
>Resistance to particular attacks can be proven. Resistance to *any* attack
>requires P!=NP, becuase "Given this pt/ct pair, is it possible that the n'th
>bit of the RNG state is a 1"? is in NP if encryption is in P.
Really? Well, here is my first paragraph again, unchanged:
"It is easy to have a prejudice that a cipher cannot be provably
secure. The most difficult part of this might be the implicit
understanding of "from any possible attack." But most ciphers have a
range of currently-known and most-likely attacks, each of which might
be addressed and proven *impractical*, if not absolutely impossible."
So, exactly what about the idea of addressing "currently-known and
most-likely" attacks sounds to you like "*any* attack"?
The information contained in RNG state has the specialized and
interesting property of being accessible from only two directions:
Input (the RNG is keyed), and Output (the RNG runs). Since Input
generally occurs at a particular time in a particular way (and, in a
real system, from a large random, not human chosen value), that end
should be fairly easy to secure *against practical attack*.
It is instead the Output part of RNG state which is most generally at
risk. But to the extent that the output stream flows into a combiner,
it is at least potentially hidden. The Dynamic Transposition
structure comes to mind, because no sequence at all is visible to the
outside, and no unique ciphering permutation is visible either. The
only attacks on the RNG output are those which the combiner allows.
Of course we cannot discuss the extent to which various combiner
structures hide RNG output, because those issues have not been
explored in the technical literature.
>> I am unaware of any proofs in cryptography which would prevent one
>> from achieving a complete information hiding in a combiner or a
>> sequence or array of combiners.
>
>I believe that the above qualifies as such.
Clearly not: You have not accepted the stated assumptions.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: Mon, 29 Jan 2001 21:07:18 -0800
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> The problem with your proposed method of making a password/passphrase
> dictionary is that any kind of text might be used, just as it might be
> when the entire phrase is typed in. What are the odds of your method
> having included in it tbatstdgagitw, unless you scanned in the
> Jabberwocky?
I was not making a dictionary, what I was going to make is an estimate of
which letters should be expected in which frequency. While this is a
different quantity from entropy, it will approximate it. This was just to
get a rough estimate of the entropy per character of the use the first
letter of each word. I wouldn't dream of making a dictionary for such a
thing, it would require some interesting girations to get working correctly.
Joe
------------------------------
From: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: Tue, 30 Jan 2001 05:25:09 GMT
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> Actually I need simply refer back to the proofs by, I believe it was,
> Shanon. Which proved rather conclusively that English has between
> 1 and 1.5 bits of entropy per character.
Proof is the wrong word here. Shannon estimated the entropy of
English text based on human experiments.
According to the secondary information I've got here (Text
Compression, Bell, Cleary, Witten, 1990), he estimated the
entropy of English text to be 3.2-4.0 bits/char given no
context, to 0.6-1.3 bits/char given a context of 100+ characters,
i.e, if you knew the preceding 100 characters in English text,
subjects guessed the next character correctly about half the time.
Overall, I'd say this and other similar results doesn't apply
to passwords/passphrases other than as a really rough guide.
Sam Paik
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: fast signing
Date: Mon, 29 Jan 2001 21:40:07 -0800
I've got a question for some of the other people. What is the fastest secure
signing algorithm? Right now I'm using DSA (openssl) but I'd like to get it
up around 20 times faster. Any ideas?
Joe
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Tue, 30 Jan 2001 06:32:39 GMT
"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Really? Well, here is my first paragraph again, unchanged:
> [...]
> So, exactly what about the idea of addressing "currently-known and
> most-likely" attacks sounds to you like "*any* attack"?
Nothing at all. Your first paragraph, I conceded immediately. That's not
the idea I quoted.
I quoted this:
> >"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >> The obvious attack is on the RNG keyspace, the internal state. But we
> >> can easily make ciphers with hundreds of thousands of bits of internal
> >> state, which is far more than "large enough." When we do, we at least
> >> have the opportunity of proving that any attack on the keyspace must
> >> be impractical. There is nothing unreasonable about this.
and was referring to the part where you explicitly said "any attack". You
meant "any attack against the internal state", and so did I:
> <IYpd6.175740$[EMAIL PROTECTED]>, in sci.crypt "Matt
> Timmermans" <[EMAIL PROTECTED]> wrote:
> >[...]
> >"Given this pt/ct pair, is it possible that the n'th
> >bit of the RNG state is a 1"? is in NP if encryption is in P.
And so, if P=NP, any DT cipher with bounded key size can be cracked in
polynomial time. This is probably not a practical disadvantage, but it
certainly is a hard barrier to provable security.
> "It is easy to have a prejudice that a cipher cannot be provably
> secure. The most difficult part of this might be the implicit
> understanding of "from any possible attack."
"Prejudice" is a belief, and irrelevant, because you do not take *provable*
security on faith -- you take it on proof. Please provide one. I suspect
the hard part will be in defining "any possible attack" in some strange way
that suits your purposes.
> But most ciphers have a
> range of currently-known and most-likely attacks, each of which might
> be addressed and proven *impractical*, if not absolutely impossible."
This is the part I didn't argue with. There is a big difference between
proving security against a finite set of specific attacks and proving
security against some set of attacks the gets bigger as people invent new
algorithms. You keep saying that a cipher with bounded key size can be
provably secure in the latter sense, and it's just not true Today -- "any
possible attack against the RNG state" is one of these sets.
So, I'm sorry -- DT can certainly be quite secure, but not provably so.
Just like any other quality cipher.
> The information contained in RNG state has the specialized and
> interesting property of being accessible from only two directions:
> Input (the RNG is keyed), and Output (the RNG runs).
I assume you just mean that the output is the only way he sees the state.
If you've been assuming that the attacker doesn't know the RNG algorithm,
then stop me now, because that would invalidate my arguments and your
cipher.
> Since Input
> generally occurs at a particular time in a particular way (and, in a
> real system, from a large random, not human chosen value), that end
> should be fairly easy to secure *against practical attack*.
Agreed again, as it does not imply provability.
> >> I am unaware of any proofs in cryptography which would prevent one
> >> from achieving a complete information hiding in a combiner or a
> >> sequence or array of combiners.
> [...]
> Of course we cannot discuss the extent to which various combiner
> structures hide RNG output, because those issues have not been
> explored in the technical literature.
It would help if you would simply define "complete information hiding". It
would then be quite clear whether it was possible or not.
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: Tue, 30 Jan 2001 17:46:54 +1100
In my bank IT Security experience (not Citibank), a faulty unit would either
be compacted along with a junk car body, or industrial incineration,
witnessed by myself or other relevant bank person.
Lyal
Paul Rubin wrote in message <[EMAIL PROTECTED]>...
>[EMAIL PROTECTED] (Peter Gutmann) writes:
>> In addition, erasing the cell doesn't necessarily mean the data is
>> really gone. If you're really concerned I'd physically destroy the
>> memory, and if you're really paranoid and worried about big-budget
>> attackers, the crypto device it fed as well.
>
>I'm wondering what normal policy is in high security commercial
>organizations, e.g. What Would Citibank Do? In practice I don't think
>we're that paranoid. We're just trying to identify and follow best
>industry practices for this type of operation.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
