Cryptography-Digest Digest #589, Volume #13 Mon, 29 Jan 01 22:13:01 EST
Contents:
Re: Primality Test (Bryan Olson)
Re: MIKE - alternative to SPEKE and PAK (Thomas Wu)
Re: A Password Protocol (Thomas Wu)
Some Cryptogram deciphering help ("Todd Luther")
Re: Primality Test (Splaat23)
Re: Recommendations on simplest way to add client/server encryption ("Joseph
Ashwood")
Re: How many bits of security can a password give? ("Joseph Ashwood")
random number generators. Can someone help? ([EMAIL PROTECTED])
Re: random number generators. Can someone help? ("Joseph Ashwood")
Re: A Password Protocol (John Savard)
Re: How many bits of security can a password give? (Benjamin Goldberg)
Re: Very short redundant serial number ("Matt Timmermans")
Power mod operation optimization ("Adam Smith")
Re: On combining permutations and substitutions in encryption ("Matt Timmermans")
Re: What do you do with broken crypto hardware? (Paul Rubin)
Re: How many bits of security can a password give? ("Joseph Ashwood")
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Primality Test
Date: Tue, 30 Jan 2001 00:30:30 GMT
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: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: MIKE - alternative to SPEKE and PAK
Date: 29 Jan 2001 16:47:41 -0800
"Michael Scott" <[EMAIL PROTECTED]> writes:
> "Thomas Wu" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Michael Scott" <[EMAIL PROTECTED]> writes:
> >
> >
> > Have you given any thought to how a verifier-based version of MIKE could
> > be derived? I can't think of any easy way other than by using the
> > existing, patented A- and B- extensions, and these also tend cripple the
> > performance of the protocol to below the level of existing verifier-based
> > protcols like SRP. MIKE would be much more interesting if an efficient
> > alternate verifier-based construction could be found.
> >
>
> Yes. In fact MIKE (and I now regret the name, but if your name ends in KE
> its hard to resist), seems to support a verifier based SRP-style protocol
> very naturally as the password is already in the exponent. Using the
> notation of SRP, x=H(s,P), and the verifier stored by Steve v=4^x, then in
> your description of SRP (Table 4) replace steps 3, 4 and 5 as follows (p is
> a safe prime):-
>
> 3. A=3^a.4^x mod p Carol sends A to Steve
> 4. B=3^b. Steve sends B to Carol.
> 5. Carol calculates S=B^a. Steve calculates S=(A/v)^b
I thought of that too, but I noticed that Carol's computation of A
requires her to know 4^x, not x, so that if an impostor Chris stole
v=4^x from Steve, she could compute A=3^a*v mod p and Steve would be
none the wiser. Comments?
> Then proceed as for SRP. Note that 3 and 4 are both generators of the
> (p-1)/2 sub-group for any safe prime.
>
> I suspect a PAK-like proof of security may also be possible here, as MIKE is
> very similar to PAK.
>
> Mike Scott
Tom
--
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: A Password Protocol
Date: 29 Jan 2001 16:53:40 -0800
[EMAIL PROTECTED] (John Savard) writes:
> On Mon, 29 Jan 2001 12:42:00 -0700, John Myre <[EMAIL PROTECTED]>
> wrote, in part:
>
> >Both forms of this protocol are vulnerable to an off-line
> >password guessing attack, requiring only eavesdropping on
> >the user's communications. It is not necessary to deal
> >with the "host computer" or the "security computer" at all.
>
> Yes. Of course, that's obvious; no attempt is made to strengthen the
> password through the use of EKE or similar techniques.
Is the goal of your system to thwart an attacker who breaks into the
"host computer" to try a dictionary attack? What if that attacker
decides to install a sniffer on the host computer?
Tom
> 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/srp/
------------------------------
From: "Todd Luther" <[EMAIL PROTECTED]>
Subject: Some Cryptogram deciphering help
Date: Mon, 29 Jan 2001 18:08:38 -0700
I have this following quotation that is encoded and I could use some
assistance....I have tried a monoalphabetic decryption, the Vigenere table,
a columnar, and upto a 3 alphabet polyalphabetic subsitution with no
solution still....can anyone help me?
pbegu uymiq icuuf guuyi qguuy qcuiv fiqgu uyqcu qbeme vp
I thought the Vigenere table was the key to solving it due to the occurences
of the "guuy" but I still couldnt make anything out of it....I even tried a
few algorithms of my own but no solution (I admit Im not an expert yet at
decryption).
If anyone can solve this I would appreciate an email to
[EMAIL PROTECTED] and with the answer a simple explanation of how you
got the answer.
Thanks,
Todd V Luther
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: Primality Test
Date: Tue, 30 Jan 2001 01:03:57 GMT
I'll send one, and you'll just have to hope I'm a good person (which I
am) who will never see this key in use, or recognize in if I do. In any
case, I'll humor you (hey, it's not everyday that someone asks a bunch
of strangers to generate a _full_ PGP key for them).
1024-bit (and 2048-bit key if you need it) on its way.
- Andrew
In article <f1nd6.3$[EMAIL PROTECTED]>,
"Adam Smith" <[EMAIL PROTECTED]> wrote:
> I'm running VB, that could be the problem. The author of my bignum
package
> cites the following for the primality test:
>
> 'Schneier, Applied Cryptography, p.260
> 'Robbins, Beginning Number Theory, p.262
>
> so I assume he knows what he's doing. It probably has something to
do with
> VB's high-level calls...
>
> At any rate, this is my final plea. I considered posting this to a
new
> thread, but that would be my fourth on this RSA stuff...but it comes
down to
> this: I need ONE RSA key. If I plugged away at this thing, I would
only
> generate one key with it anyway. Could someone who has the
facilities to
> generate RSA keys do so to make a 1024 bit key and send it to me?
(Note: in
> the form of the numbers n, e, and d (p & q optional), not like one
generated
> by PGP or anything)
>
> Thanks!
> Adam Smith
>
> "Splaat23" <[EMAIL PROTECTED]> wrote in message
> news:9522t5$bvm$[EMAIL PROTECTED]...
> > Umm, written in native Python (an interpreted language), a single
> > Miller-Rabin round on a 512 bit condidate takes .05 seconds. You've
> > done something wrong with the algorithm, or your big number library
is
> > REALLY slow.
> >
> > One of the best ways to generate primes is to pick a random number
of
> > the correct range, fix the most and least significant bit to 1, and
> > increment by 2 until you get a prime. Each candidate can be tested
> > first with trial division of the firxt X primes to screen obvious
> > composites, then with a couple of rounds of Miller-Rabin.
> >
> > Your posts here are not getting annoying, but most of the answers
_are_
> > available from other, better sources, such as books. I would
recommend
> > getting the Handbook of Applied Cryptography. It's even available
for
> > free on the Internet. Read it before asking a question and you'll be
> > guaranteed that the answer is not _completely_ obvious.
> >
> > - Andrew
> >
> > In article <8I%c6.3988$[EMAIL PROTECTED]>,
> > "Adam Smith" <[EMAIL PROTECTED]> wrote:
> > > Once again, this is for generating RSA keys...if all of my posts
here
> > are
> > > getting annoying or are out-of-place, please say something....
> > >
> > > I'm not having trouble generating random numbers with 150-200
digits,
> > my
> > > problem comes in testing to see if they're random...I'm using an
> > > implementation of the Rabin-Miller primality test with even only
one
> > round
> > > (if true then probability that the number is composite is < .25^
> > (number of
> > > rounds)), but it's taking an extremely long time to test...I had
to
> > force
> > > close the app before it even tested one number (it's using a
Pentium
> > III 500
> > > MHz chip)...
> > >
> > > Any tips on generating 512 bit prime numbers?
> > >
> > > Once again, thanks in advance!
> > > Adam Smith
> > >
> > >
> >
> >
> > Sent via Deja.com
> > http://www.deja.com/
> >
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Recommendations on simplest way to add client/server encryption
Date: Mon, 29 Jan 2001 17:03:41 -0800
Crossposted-To: comp.security.misc
Sorry I guess I should be more specific. Because you don't need to be
compatible with anyone else, so there is no standard yet available for you.
Simply do the following for a connection:
(I assumes the client already has the public key of the server, this is
psuedocode, it just looks somwhat C-like)
Connecting.....
Client:
K = random 160-bit number
IV1 = random 64-bit number
IV2 = random 64-bit number
X = RSA_OAEP_ENCRYPT(K to Server)
send(X, server);
send(IV1, server)
send(IV2, server)
K = K | 0x00
ClientToServer3DESConnection = 3DES_CBCInit(K, IV1)
ServerToClient3DESConnection = 3DES_CBCInit(K, IV1)
Server
receive(X, client)
receive(IV1, client);
receive(IV2, client);
K = RSA_OAEP_DECRYPT(X);
K = K | 0x00
ClientToServer3DESConnection = 3DES_CBCInit(K, IV1)
ServerToClient3DESConnection = 3DES_CBCInit(K, IV1)
Sending data:
Client:
X = 3DES_CBCEncrypt(data, ClientToServer3DESConnection);
send(X, server);
Server:
X = 3DES_CBCEncrypt(data, ServerToClient3DESConnection);
send(X, client);
Receiving Data...........
client:
receive(X, server)
data = 3DES_CBCDecrypt(X, ServerToClient3DESConnection)
Server:
receive(X, client)
data = 3DES_CBCDecrypt(X, ClientToServer3DESConnection);
That will be a rather stripped down SSL connection, allowing only 3DES and
RSA, without a lot of the indirection that shouldn't have been there in the
first place. I've also left the serialization to you, and stripped out the
MACs which you may want to add back in. This is a high level version of a
semi-secure protocol, there are various substitution attacks against it that
you could deal with by in the keying phase using
Server2ClientKey = SHA1("Server2Client" | K)
Client2ServerKey = SHA1("Client2Server" | K)
and a few other more obscure attacks. Just be aware that this is not as
strong of a protocol as SSL3, but it will be sufficient for most purposes,
if you add the 2 keys instead of single key, and the MACs it will be
approximately as strong as SSLv3 (in fact it'll be virtually identical).
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: Mon, 29 Jan 2001 17:09:44 -0800
Right, but when it comes to security, I'd rather bet pessimistically than
optimistically. All you can do really is choose how pessimistic you want to
be (I for example find that humans are absurdly predictable given a bit of
information about the individual and I'd say that most passwords have < 10
bits of entropy). Some people like being highly optimistic I think they are
foolish, some people are hopelessly pessimistic (Some of my statements are
probably borderline). Regardless we're arguing over how bad a password is,
whether it's 2^6 or 2^36 it's weak, so I vote from freeing up some bandwidth
to trash Szopa.
Joe
"Splaat23" <[EMAIL PROTECTED]> wrote in message
news:954u1s$ntu$[EMAIL PROTECTED]...
> My memory may be failing me, but I recall Shannon's numbers are wrt.
> large texts (i.e. books), where patterns have more of a chance to be
> exposed. With passwords, I bet there's around 3-4 bits per byte,
> because they are short and don't have spaces (generally). Shannon's
> research, however, is definately applicable to passphrases, because
> they are "phrases". However, all of this is simplistic logic, so use
> with caution.
------------------------------
From: [EMAIL PROTECTED]
Subject: random number generators. Can someone help?
Date: Tue, 30 Jan 2001 01:26:44 GMT
Sorry to bother. I don't know if there is a more appropriate NG for my
question or not. I was wondering if there is a web-site that will allow
you to program simple random # routines without actually
programming/without having to do any downloading, out there? I figure
someone must have thought of this idea, before me, and since most people
are less lazy, and have more resources available, I would guess that
someone has done it. If there isn't now was there ever one? Is there a
better NG (or elist, etc.)for me to be asking this qwuestion @?
--
amo sapientia love of wisdom
anhelo scientia lust for knowledge
cultus apud verum-I worship of truth
The above is :left:my attempt at a latin translation of: right: My
magickal motto. elist heuristic mysticism :
http://www.egroups.com/group/heuristic_mysticism
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: random number generators. Can someone help?
Date: Mon, 29 Jan 2001 17:58:06 -0800
Typically we just make use of known-strong parts that are fast. I have seen
very few occassions where a pRNG was needed where ARCFOUR wouldn't work just
fine. It's cryptographically strong, it's very fast, it's small, and I can
write the code from scratch faster than I can locate a copy of it online. If
you want something a bit more complicated looking you use ISAAC. If you want
something that people will ooh and aaah at you use Yarrow, or counter mode
with Rijndael, or a dozen others. It may however be useful to create a
source of experimentation with pRNGs which may fuel further development.
Joe
<[EMAIL PROTECTED]> wrote in message news:95558c$u7k$[EMAIL PROTECTED]...
> Sorry to bother. I don't know if there is a more appropriate NG for my
> question or not. I was wondering if there is a web-site that will allow
> you to program simple random # routines without actually
> programming/without having to do any downloading, out there? I figure
> someone must have thought of this idea, before me, and since most people
> are less lazy, and have more resources available, I would guess that
> someone has done it. If there isn't now was there ever one? Is there a
> better NG (or elist, etc.)for me to be asking this qwuestion @?
>
> --
> amo sapientia love of wisdom
> anhelo scientia lust for knowledge
> cultus apud verum-I worship of truth
> The above is :left:my attempt at a latin translation of: right: My
> magickal motto. elist heuristic mysticism :
>
> http://www.egroups.com/group/heuristic_mysticism
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: A Password Protocol
Date: Tue, 30 Jan 2001 02:00:33 GMT
On 29 Jan 2001 16:53:40 -0800, Thomas Wu <[EMAIL PROTECTED]>
wrote, in part:
>Is the goal of your system to thwart an attacker who breaks into the
>"host computer" to try a dictionary attack? What if that attacker
>decides to install a sniffer on the host computer?
The goal here is, excluding the possibility of dictionary attacks, to
thwart only the simplest direct attacks: using the hash stored on the
host computer to successfully execute a challenge-response without
knowing the password.
To thwart a dictionary attack, one needs to add EKE or similar
techniques to this; it should be possible to combine them.
It is assumed that all the communications can be intercepted, but
computations on the host are secure, both from interference and from
monitoring. The unique feature is only that the link between the host
and the 'security computer' doesn't have to be secure.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: Tue, 30 Jan 2001 02:29:30 GMT
Joseph Ashwood wrote:
>
> "Rex Stewart" <[EMAIL PROTECTED]> wrote in message
> news:94vg0l$ec9$[EMAIL PROTECTED]...
> > passphrazes between 8 and 14 characters
> > (the standard advice given nowadays for networks)
>
> That's wrong. That is the lengths expected for passwords, the expected
> length for passphrases is in the 20 to 100 character range. That is
> the primary reason for moving from passwords to passphrases, it's not
> simply a name change.
> Joe
There's two uses of the word passphrase: The first, where you type in
the entire phrase as your password, and the second, where you type in
the first [or last, or whatever] letter of each word of the phrase as
your password.
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.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Very short redundant serial number
Date: Tue, 30 Jan 2001 02:41:34 GMT
If these are hex digits, then an 8-bit CRC would be good.
------------------------------
From: "Adam Smith" <[EMAIL PROTECTED]>
Subject: Power mod operation optimization
Date: Tue, 30 Jan 2001 02:47:59 GMT
Well, I finally got some keys donated to me : )
I plugged them in and notice that it takes an extended amount of time to
generate a signature or verify it (for those of you who have read my
previous posts, surprise surprise!)...
All of the things taking up the time is my power mod function ( (x ^ y) mod
z) ). Here's the code I have as of now (for those of you who don't know VB,
it's pretty easy to catch on):
BEING CODE
===================
'outp = (s1 ^ s2) mod s3
Public Sub bModPower(s1 As String, s2 As String, s3 As String, Outp As
String)
(NOTE: First part is just notes (starts with a '))
'Use variation of "Russian Peasant Metho
' d" to figure m=(c^d) mod n.
'Byte, Jan 83, p.206.
'test value: (71611947 ^ 63196467) mod 9
' 4815109 = 776582
'm=1
'do
' if d is odd then m=(m*c) mod n
' c=(c*c) mod n
' d=int(d/2)
'loop while d>0
'm is the answer
'remember modulus for next call
Dim c As String, d As String
Static n As String
'positive numbers only, modulus must be
' >1! Find mod inverse if s2=-1.
Outp = err
If Len(s3) Then n = s3
If bIsNeg(s1) Or bIsNeg(n) Then Exit Sub
If bIsNeg(s2) Then
If bIsEqual(s2, "-1") Then bModInv s1, n, Outp
Exit Sub
End If
c = s1
d = s2
Outp = one
Do
If bIsOdd(d) Then bMul (Outp), c, Outp: bMod (Outp), n, Outp
bMul (c), (c), c
bMod (c), n, c
bDivInt (d), two, d
Loop Until bIsZero(d)
End Sub
END CODE
NOTES: Most of the functions whose code is not included are pretty self
explanitory (i.e. bIsNeg & bMul). However, the format is more-or-less odd
(hey, I didn't code it! : ) ... for most of the functions, instead of
naming them as functions they're Subs, and it returns its result in the last
argument you pass it (for example for this you pass four variables: s1, s2,
s3, and outp. Outp is where you get the results from)...All of the code
executes very quickly until you get to the Do loop. then the time it takes
for each loop seems to increase.
Any thoughts?
Thanks once again,
Adam Smith
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Tue, 30 Jan 2001 02:49:12 GMT
"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.
> 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.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: 29 Jan 2001 18:51:41 -0800
[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.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: Mon, 29 Jan 2001 18:53:20 -0800
"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
------------------------------
** 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
******************************
