Cryptography-Digest Digest #327, Volume #11 Tue, 14 Mar 00 04:13:01 EST
Contents:
Re: Birthday paradox (Raphael Phan Chung Wei)
PERL crypt command ("Bob Manning")
[Tabloid Humor] Greatest threat ever to computer security ([EMAIL PROTECTED])
Re: sci.crypt.applied (Paul Rubin)
Re: PERL crypt command (Andru Luvisi)
Re: sci.crypt.applied (Paul Rubin)
Re: PERL crypt command ("Bob Manning")
Re: US export status of RC4? (Guy Macon)
Re: sci.crypt.applied ("Joseph Ashwood")
Improvement on Von Neumann compensator? (Guy Macon)
Re: MD5 collisions (Larry)
Re: MD5 collisions (stanislav shalunov)
Re: Just *Germain* primes ("Lassi Hippel�inen")
Re: Vahan meni sinne Federal Building ...... :) (Dealer)
Assistance needed With finding an algy that does not (Nemo psj)
Re: MD5 collisions (Terje Mathisen)
Re: Random permutations (Mok-Kong Shen)
Re: why xor?(look out,newbie question! :) ("Douglas A. Gwyn")
----------------------------------------------------------------------------
Date: Tue, 14 Mar 2000 11:57:39 +0800
From: Raphael Phan Chung Wei <[EMAIL PROTECTED]>
Subject: Re: Birthday paradox
James Muir wrote:
> The birthday paradox says that if X is a random variable drawn
> uniformily from an interval of n values then we expect that X will take
> on a repeated value after sqrt( pi*n / 2 ) draws.
>
> People's birthdays are just occurences of the random variable X drawn
> uniformly from [1..365]. So we expect that in a group of sqrt(
> pi*365 / 2 ), which is approximately 24, two people will share the same
> birthday ( a birthday collision ).
>
> The principle can be applied to block ciphers and hash functions.
> Assume your cipher outputs a random string of n bits for each key
> value. A key value represents an occurence of the random variable X
> sampled from the interval [1..2^n]. Thus we expect a collision in
> every group of sqrt( pi*n / 2 ) key values.
>
> -James
James... Thank you for your explanation. Now I get the picture
--
Regards,
Raphael Phan
Faculty of Engineering
Cyberjaya Campus
Multimedia University
+603-83125314
------------------------------
From: "Bob Manning" <[EMAIL PROTECTED]>
Subject: PERL crypt command
Date: Mon, 13 Mar 2000 23:10:28 -0500
Does anyone know of a decrypt for the PERL crypt command?
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.computer.security
Subject: [Tabloid Humor] Greatest threat ever to computer security
Date: Tue, 14 Mar 2000 04:28:28 GMT
http://www.weeklyworldnews.com/stories/
1745.html
I'm going down, all the way down
on the highway to Hell -AC/DC
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: sci.crypt.applied
Date: 14 Mar 2000 04:46:09 GMT
In article <Zo4z4.1645$[EMAIL PROTECTED]>,
Gary Watson <[EMAIL PROTECTED]> wrote:
>I haven't seen a great deal of discussion of applied cryptography in this
>ng, that is, the nuts-n-bolts techniques used to implement a cipher in such
>a way that the final product is secure. I'm not proposing a new
>sci.crypt.applied newsgroup, but if it existed, perhaps the charter would
>propose discussions of: ...
Most of those topics are not about cryptography. They are already discussed
in the comp.security newsgroups.
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: PERL crypt command
Date: 13 Mar 2000 20:32:06 -0800
"Bob Manning" <[EMAIL PROTECTED]> writes:
> Does anyone know of a decrypt for the PERL crypt command?
Perl's crypt function is an interface to the unix crypt function,
which is more like a hash: it's meant to be nonreversable.
The idea is this: you hash the user's password along with two random
charactors chosen from the set [a-zA-Z0-9./], called the salt. You
store the result, along with the two random charactors, in the
password file. When a user gives you their password, in order to
check that it's correct, you get their password hash from the password
file, hash the salt (stored with the hash) along with the supplied
password, and see if the result matches the hash in the password file.
crypt makes this easy on you, since it places the salt at the
beginning of the returned hash for you, and only pays attention to the
first two charactors of the salt string you pass it, so you can use it
like this:
if(strcmp(pw.pw_passwd, crypt(user_supplied_passwd, pw.pw_passwd))) {
/* we know the password is wrong and kick the user out. */
}
or in perl:
if($passwd_hash ne crypt($user_supplied_passwd, $passwd_hash)) {
# we know the password is wrong and kick the user out.
}
The reason for the salt is to slow down dictionary attacks by stopping
you from storing the hashed values in a lookup table, and then just
having to hash each word in the dictionary once and see if it's in the
table. With the salt, you have to hash each word in the dictionary
once for each user, which means your work is multiplied by the number
of users, or 4096 (the number of possible salts), whichever is
smaller.
If you're interested in doing encryption in perl, check out the crypto
modules from CPAN.
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: sci.crypt.applied
Date: 14 Mar 2000 04:52:03 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>In my understanding, the reason for creation of a subgroup is
>normally because a certain subfield has very often been discussed
>and has occupied a very significant portion of the whole traffic
>such that it would cause some inconvenience to those who have less
>interest in that subfield, i.e. the reason is not because certain
>subfields have almost never beed touched upon.
I agree with this. I think we should make a subgroup
(sci.crypt.secure?) for provably secure cryptography systems such as
one-time pads and truly random number generators. Discussions of
advanced ciphers such as SCOTT16U could also go there, as could
discussions of NP-completeness. Sci.crypt would be left for, um, more
conventional topics like AES, public key implementation, etc. Then
the more brilliant of the leading-edge types could use
sci.crypt.secure and the rest of us would stick with sci.crypt. Sound
like a plan?
------------------------------
From: "Bob Manning" <[EMAIL PROTECTED]>
Subject: Re: PERL crypt command
Date: Tue, 14 Mar 2000 00:18:09 -0500
Thanks for the detailed explanation!!
--
=====================================================
Click here for Free Video!!
http://www.gohip.com/freevideo/
Andru Luvisi <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Bob Manning" <[EMAIL PROTECTED]> writes:
> > Does anyone know of a decrypt for the PERL crypt command?
>
> Perl's crypt function is an interface to the unix crypt function,
> which is more like a hash: it's meant to be nonreversable.
>
> The idea is this: you hash the user's password along with two random
> charactors chosen from the set [a-zA-Z0-9./], called the salt. You
> store the result, along with the two random charactors, in the
> password file. When a user gives you their password, in order to
> check that it's correct, you get their password hash from the password
> file, hash the salt (stored with the hash) along with the supplied
> password, and see if the result matches the hash in the password file.
>
> crypt makes this easy on you, since it places the salt at the
> beginning of the returned hash for you, and only pays attention to the
> first two charactors of the salt string you pass it, so you can use it
> like this:
> if(strcmp(pw.pw_passwd, crypt(user_supplied_passwd, pw.pw_passwd))) {
> /* we know the password is wrong and kick the user out. */
> }
>
> or in perl:
> if($passwd_hash ne crypt($user_supplied_passwd, $passwd_hash)) {
> # we know the password is wrong and kick the user out.
> }
>
> The reason for the salt is to slow down dictionary attacks by stopping
> you from storing the hashed values in a lookup table, and then just
> having to hash each word in the dictionary once and see if it's in the
> table. With the salt, you have to hash each word in the dictionary
> once for each user, which means your work is multiplied by the number
> of users, or 4096 (the number of possible salts), whichever is
> smaller.
>
> If you're interested in doing encryption in perl, check out the crypto
> modules from CPAN.
>
> Andru
> --
> --------------------------------------------------------------------------
> | Andru Luvisi | http://libweb.sonoma.edu/ |
> | Programmer/Analyst | Library Resources Online |
> | Ruben Salazar Library |-----------------------------------------|
> | Sonoma State University | http://www.belleprovence.com/ |
> | [EMAIL PROTECTED] | Textile imports from Provence, France |
> --------------------------------------------------------------------------
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: US export status of RC4?
Date: 14 Mar 2000 00:38:00 EST
In article <8ak54h$2u2$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Bill Unruh)
wrote:
>Make sure that you do NOT call it RC4. RC4 is encumbered by trade secret
>(??) law and trademark law. The powers that be might well decide that it
>does not fall under the conditions for release of free software. Instead
>use ARC4 which is a free encryption system which of course has nothing
>to do with RC4 ( except that all test vectors encrypt the same way with
>ARC4 as with RC4, but I am sure that that is just coincidence.:-)
...and if the owners of RC4 say different, let them release the
source code and prove it! ;)
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: sci.crypt.applied
Date: Mon, 13 Mar 2000 21:35:20 -0000
Actually I draw a very strong line between Scott16U (or 8 or
19) and OTP, because OTP is well defined, has proper
documentation, etc. ScottXu has David Scott's claim, and no
documentation outside of the source code (which last time I
checked wouldn't compile on any system I had access to). If
proper documentation (or at least readable/portable source
code) is ever provided for Scott's ciphers I will look at
them, and see if they suit me, and perhaps I can make a
judgement on their security, until such a time I have little
choice but to lump them in the same category as all the
other unexamined, untested, unrevealed ciphers, the probably
insecure, and I'm not going to rely on them for security
category. At this moment I am actually downloading Scott's
source code again, I am willing to give him a chance.
And since he can't even code a page to detect
Java/Javascript correctly, I have little doubt.
Joe
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:8akghj$902$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >In my understanding, the reason for creation of a
subgroup is
> >normally because a certain subfield has very often been
discussed
> >and has occupied a very significant portion of the whole
traffic
> >such that it would cause some inconvenience to those who
have less
> >interest in that subfield, i.e. the reason is not because
certain
> >subfields have almost never beed touched upon.
>
> I agree with this. I think we should make a subgroup
> (sci.crypt.secure?) for provably secure cryptography
systems such as
> one-time pads and truly random number generators.
Discussions of
> advanced ciphers such as SCOTT16U could also go there, as
could
> discussions of NP-completeness. Sci.crypt would be left
for, um, more
> conventional topics like AES, public key implementation,
etc. Then
> the more brilliant of the leading-edge types could use
> sci.crypt.secure and the rest of us would stick with
sci.crypt. Sound
> like a plan?
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Improvement on Von Neumann compensator?
Date: 14 Mar 2000 00:57:47 EST
Recently we had a discussion about turning certain time related physical
effects that are believed to have a random component (time between zero
crossings of a thermal noise source, time between radioactive decay
events) into a string of ones and zeros without (if possible) adding bias.
Now if I latch the output of a free running oscillator that has lots of
cycles between the random events, I will get somewhat random data, but
I am counting on a perfgect 50/50 duty cycle and a perfect 50% threshhold.
Otherwise I get a bias towards ones or towards zeros.
It has been suggested (and implemented by Intel) that a Von Neumann
compensator (0 followed by 1 = 1, 1 followed by 0 = 0. 1 followed
by 1 or 0 followed by 0 = ignored)would remove the bias.
I recently heard of another method: measure the time between a pair
ov events, then do it again. If the first time measurement is longer,
call it a one. If the second time measurement is longer, call it a
zero. Would this be a better scheme than the Von Neumann compensator?
------------------------------
From: [EMAIL PROTECTED] (Larry)
Subject: Re: MD5 collisions
Date: 14 Mar 2000 01:38:35 -0500
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Kevin Buhr) writes:
>What is the context?
For the sake of argument: it's 50,000 usernames. All 95 printable
ASCII characters are legal. I want to create a file for each
username. If these usernames have a limit of 19 characters, then:
95 ~= 2 ^ 6.57 --> 6.57 bits per char
6.57 * 19 chars = 125 bits
6.57 * 20 chars = 131 bits
MD5 hash = 128 bits
So, there is room in the MD5 address space for all printable 19
character strings, but not all 20 character strings. But of course,
that doesn't mean that you can hash all 19 character strings without a
collision.
(OK, I do see that I don't really want a "hash" here, since if I could
handle 2^128 bins with md5, it would be easier to handle 2^125 bins
and just use the username unchanged.)
My original desire to use MD5 was that it always yields output of
constant format. (ie: if some smartass uses username "/etc/passwd/"
it's easier and safer to use 9/2/3/1fb35b4431d59eae53a8c0d673231 - yes
I can clean up their input and quote the special chars - it's just
easier and safer not to go there.... But if I have to detect
collisions, it's not worth it.)
So I guess what I'm actually looking to do is hash the first few
charaters of the username to generate a three tierd directory - then
use the (untainted) username as the file name.
Also, if only purely out of curiousity, my original question stands --
has anyone looked into the largest string of printable characters that
is safe from md5 collisions.
--L
------------------------------
Subject: Re: MD5 collisions
From: stanislav shalunov <[EMAIL PROTECTED]>
Date: Tue, 14 Mar 2000 07:00:41 GMT
[EMAIL PROTECTED] (Larry) writes:
> For the sake of argument: it's 50,000 usernames.
When you get some 2^64 users you should seriously start worrying about
collisions. Now you only have 2^16 users. The probability of
collision is rather small and it's unlikely that it would happen to
anyone.
But if this bothers you, you could append SHA1 to MD5.
------------------------------
From: "Lassi Hippel�inen" <"lahippel$does-not-eat-canned-food"@ieee.org>
Subject: Re: Just *Germain* primes
Date: Tue, 14 Mar 2000 07:26:38 GMT
[EMAIL PROTECTED] wrote:
>
> In article <[EMAIL PROTECTED]>,
> Paul Koning <[EMAIL PROTECTED]> wrote:
> >there are other possible explanations, and absent any evidence
> >that others explanations don't fit (no such evidence was given)
>
> The only other explanation I can think of for the term "Sophie Germain
> prime" would be to distinguish her from some other famous mathematician
> named Germain - as we might very well do when talking about Marie or
> Pierre Curie, instead of just "Curie", because they both did significant
> work in the same fields. But, as I *did* point out in my original post,
> there isn't another famous mathematical Germain to confuse Sophie Germain
> with.
>
> What are the other "other explanations" that might fit?
> --
> Matthew Skala "Ha!" said God, "I've got Jon Postel!"
> [EMAIL PROTECTED] "Yes," said the Devil, "but *I've* got
> http://www.islandnet.com/~mskala/ all the sysadmins!"
As a hypothetical example, the full name of the mathematician might have
been "Mathieu de Sophie Germain" :-)
Anyway, using the first name to indicate gender is unreliable. "Sophie"
is easy, if you have an indo-european background, but there are also
ambiguous cases. Is "Jean" male or female? How about "Kari" - in Norway
a female, in Finland a male. Things get even more difficult, when
non-European scientist are considered; both as contibutors and as the
addressed audience.
I support the practice of using only the family name whenever possible.
-- Lassi (male, if you didn't know... derived from "Laurentius")
------------------------------
From: Dealer <[EMAIL PROTECTED]>
Crossposted-To:
alt.politics.org.cia,soc.culture.russian,soc.culture.ukrainian,soc.culture.nordic,soc.culture.europe,soc.culture.british,soc.culture.soviet,soc.culture.baltic,alt.security
Subject: Re: Vahan meni sinne Federal Building ...... :)
Date: Mon, 13 Mar 2000 22:55:41 +0000
Markku J. Saarelainen wrote:
>
> "Markku J. Saarelainen" wrote:
>
> > "Markku J. Saarelainen" wrote:
Are you talking to your damn self or what?
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Subject: Assistance needed With finding an algy that does not
Date: 14 Mar 2000 08:06:26 GMT
Im looking for an algy that does not spiral down to nohitng like if i
encrypt frase
F with pass Q and i keep changing pass Q, F will eventually turn into "s"
(where s represents a single character)and i am out of luck.
Rc4 does this so i cant use it in my algy and the other algys i have found are
in java. Does anyone know where i can find some source in VB?
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: MD5 collisions
Date: Tue, 14 Mar 2000 09:27:10 +0100
stanislav shalunov wrote:
>
> [EMAIL PROTECTED] (Larry) writes:
>
> > For the sake of argument: it's 50,000 usernames.
>
> When you get some 2^64 users you should seriously start worrying about
> collisions. Now you only have 2^16 users. The probability of
> collision is rather small and it's unlikely that it would happen to
> anyone.
'rather small' indeed:
My math is rusty, but I'll make a stab at estimating the odds, assuming
the hash function is 'perfect', i.e. all 128-bit hashes are equally
likely, and a single bit modification of the input will on average
modify half the output bits. This seems like a reasonable set of
assumptions for a good hash?
The second username has odds of ((2^128-1) / 2^128) to not collide, the
third will then have
((2^128-2) / 2^128) etc. up to ((2^128-50000) / 2^128)
The product of these odds must be _less_ than the last term raised to
the power of 50,000:
((2^128 - 50000) / 2^128)^50000 (or (1 - 50000/2^128)^50000)
Expanding that, and taking the first two terms (the reamining terms are
lost in the underflow), I get:
1 - 50000 * 50000/2^128
This means that the odds of getting even a single collision will be less
than
50000^2/2^128, which is about 7.3e-30
This is odds that I'd be willing to risk.
I.e. your hard disk will crash and/or memory will be corrupted a long
time before you get a collision. :-)
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random permutations
Date: Tue, 14 Mar 2000 09:39:29 +0100
Herman Rubin wrote:
>
>
> The low comparison method, together with the swap, is
> as follows; the code can be tweaked for greater
> efficiency. We denote by q(k) the smallest integer
> j such that k <= 2^j. The array is a[k], 0 <= k < n.
>
> for(m=n; m>1; m--){
> until(k < m) k = binary number with q(m) random bits;
> swap(a[k], a[m-1);
> }
>
> The bit managing can be done fairly efficiently, and
> the computation of q(m) can be moved to the modified
> for loop.
>
> This will reduce the number of comparisons far below
> that for any kind of sort, and the number of bits
> used to at most a small factor over the minimum.
Is this result already in the literature, or would you like to
publish it so that others may be able to learn more about the
topic? (There is at least one journal specifically for short CS
articles with fairly short waiting times.)
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: why xor?(look out,newbie question! :)
Date: Tue, 14 Mar 2000 08:45:26 GMT
"r.e.s." wrote:
> Now as random streams, a is independent of b;
That is an extremely strange notion of "random streams"!
After the first 2 bits, both a and b are perfectly predictable.
> (Sometimes the chi-square test is stated with a "rule of
> thumb" to the effect that each expected cell-count be at
> least some small number, but we could satisfy that by
> tweaking the present example.)
The rule of thumb is: at least 5 observations in every cell.
Kullback's information statistic does not have this shortcoming.
------------------------------
** 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
******************************
