Cryptography-Digest Digest #256, Volume #9 Sat, 20 Mar 99 13:13:02 EST
Contents:
QDD v0.1 : Quantum Computer Emulation C++ Library (beaner)
Re: Random Walk ("Douglas A. Gwyn")
Does PGP use salt when hashing passphrases? (Lincoln Yeoh)
Re: a little math please ([EMAIL PROTECTED])
Re: a little math please ([EMAIL PROTECTED])
Re: Does PGP use salt when hashing passphrases? ([EMAIL PROTECTED])
Re: One-Time-Pad program for Win85/98 or DOS ([EMAIL PROTECTED])
Re: a little math please ([EMAIL PROTECTED])
Re: a little math please ([EMAIL PROTECTED])
Re: Testing Algorithm (hash) ([EMAIL PROTECTED])
Please look at this rather odd cipher (Ketema J,00996270)
SHS (Sha) ([EMAIL PROTECTED])
Re: a little math please ([EMAIL PROTECTED])
Re: pRNG that is "predictable to the left"? (Paul Onions)
Re: Random Walk (R. Knauer)
Re: Please look at this rather odd cipher ([EMAIL PROTECTED])
Re: SHS (Sha) (Kent Briggs)
Re: Does PGP use salt when hashing passphrases? (Paul Crowley)
Re: SHS (Sha) (iLLusIOn)
----------------------------------------------------------------------------
From: beaner <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.physics,sci.logic
Subject: QDD v0.1 : Quantum Computer Emulation C++ Library
Date: Fri, 19 Mar 1999 22:25:58 -0600
I'm pleased to announce the first release of QDD, a C++
Library for Quantum Computer Emulation. QDD is unique in
its use of Binary Decision Diagrams (BDDs) to represent
quantum state. The BDD representation provides QDD with
relatively high performance in comparison to other quantum
computing platforms. A reference implementation of Shor's
quantum factoring algorithm, called SHORNUF, is provided
with the QDD library and is capable of factoring a 16 bit
number in approximately 8 minutes on a P200 with 64M of RAM.
QDD was developed under Linux and is open source software.
The QDD home page : http://home.plutonium.net/~dagreve/qdd.html
Comments and feedback appreciated :)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Sat, 20 Mar 1999 04:23:25 GMT
"R. Knauer" wrote:
> So, there you have it - not only do statistical tests fail in general
> for true random number generation processes, ...
Only if the tests are inappropriate, or if their results are
misinterpreted.
You might as well say that "0100011101" has only 1 chance in 1024
of occuring, so if it is the output of a random bit generator, the
generator isn't very random. That doesn't prove anything about
statistics, other than how easy it is to give a plausible argument
that is actually quite misguided. Good statisticians don't make
this sort of mistake.
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Crossposted-To: comp.security.pgp.discuss
Subject: Does PGP use salt when hashing passphrases?
Date: Sat, 20 Mar 1999 07:59:27 GMT
Reply-To: [EMAIL PROTECTED]
Heh I know I should look at the source myself, but does anyone know?
Was wondering if using salt for hashing/encrypting passphrases be a good
idea. It's done for unix passwords to make pre-encrypted dictionary attacks
harder. Just imagine 32 bits of salt, nice dictionary ;).
Cheerio,
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: a little math please
Date: Sat, 20 Mar 1999 09:23:09 GMT
A few have given incorrect answers of 2^255. You have 2^256 total
squares, of which, 2^255 must be 0. Thus, you have (2^256 choose
2^255) total choices for the 0's, which is equivalent to what you
asked.
Mike
On Fri, 19 Mar 1999 17:55:29 GMT, [EMAIL PROTECTED] wrote:
>What I would like to know, given a grid of 16x16, filled with an even number
>of 0 and 1 bits, how many combinations are there?
>
>Not 2^256, because remember that they have to be even.
>
>Thanks,
>Tom
>
>-----------== Posted via Deja News, The Discussion Network ==----------
>http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Decrypt [EMAIL PROTECTED] with ROT13 for email address.
NOTICE TO BULK EMAILERS: Pursuant to US Code,
Title 47, Chapter 5, Subchapter II, 227, any
and all nonsolicited commercial E-mail sent to
this address is subject to a download and archival
fee in the amount of $500 US. E-mailing denotes
acceptance of these terms.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: a little math please
Date: Sat, 20 Mar 1999 10:25:41 GMT
On Sat, 20 Mar 1999 09:23:09 GMT, [EMAIL PROTECTED] wrote:
>A few have given incorrect answers of 2^255. You have 2^256 total
>squares, of which, 2^255 must be 0. Thus, you have (2^256 choose
>2^255) total choices for the 0's, which is equivalent to what you
>asked.
>
>Mike
oops. 256 choose 128.
Guess I spoke too soon also
>
>On Fri, 19 Mar 1999 17:55:29 GMT, [EMAIL PROTECTED] wrote:
>
>>What I would like to know, given a grid of 16x16, filled with an even number
>>of 0 and 1 bits, how many combinations are there?
>>
>>Not 2^256, because remember that they have to be even.
>>
>>Thanks,
>>Tom
>>
>>-----------== Posted via Deja News, The Discussion Network ==----------
>>http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
>
>Decrypt [EMAIL PROTECTED] with ROT13 for email address.
>
>NOTICE TO BULK EMAILERS: Pursuant to US Code,
>Title 47, Chapter 5, Subchapter II, 227, any
>and all nonsolicited commercial E-mail sent to
>this address is subject to a download and archival
>fee in the amount of $500 US. E-mailing denotes
>acceptance of these terms.
Decrypt [EMAIL PROTECTED] with ROT13 for email address.
NOTICE TO BULK EMAILERS: Pursuant to US Code,
Title 47, Chapter 5, Subchapter II, 227, any
and all nonsolicited commercial E-mail sent to
this address is subject to a download and archival
fee in the amount of $500 US. E-mailing denotes
acceptance of these terms.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.security.pgp.discuss
Subject: Re: Does PGP use salt when hashing passphrases?
Date: Sat, 20 Mar 1999 12:23:04 GMT
> Was wondering if using salt for hashing/encrypting passphrases be a good
> idea. It's done for unix passwords to make pre-encrypted dictionary attacks
> harder. Just imagine 32 bits of salt, nice dictionary ;).
You should use a larger salt then that. You should really only use salts
where key and OTP systems are concerned. It has little to no effect on
RC5/RC6 for example.
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.security,alt.privacy
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Date: Sat, 20 Mar 1999 12:19:48 GMT
> Then you should learn why.
>
> HINT: Why is the OTP system proveable secure?
>
Does that have anything todo with the large number of valid keys? (pads...)
> HINT: It depends on how many messages of what length you plan to send.
Shouldn't you only end one message, then use another pad? Just like with RC4?
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: a little math please
Date: Sat, 20 Mar 1999 12:29:05 GMT
> Other posters gave you the correct number assuming that by "even", you mean
> that the number of 0's (and the number of 1's) must be an even number.
> However, if you mean the numbers of 0s must be the same as the number of 1s
> (that is, there are precisely 128 0's and 128 1's), then there are:
>
> 256!
> -----------
> 128! * 128!
>
> combinations, which is approximately:
>
> 2^251.672843
Sorry about that, I meant to ask if the # of 1's and # of 0's are equal not
even.
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: a little math please
Date: Sat, 20 Mar 1999 12:27:55 GMT
<snip>
I printed off your post, I will look into it more.
So basically there are 256! / 128! combinations? Can you estimate that number
please?
Thanks,
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Testing Algorithm (hash)
Date: Sat, 20 Mar 1999 12:33:24 GMT
> You could probably improve the "mixing" by relying more on (nonlinear?)
> boolean functions and relying less on rotates. Then you could reduce
the
> number of rounds to something more reasonable. This is the traditional
> approach to hash functions, MDx related ones anyhow. (Unfortunately, the
> choice of boolean functions is not trivial, cf the paper on HAVAL, and others
> by Zheng, Zhang, and Seberry at the cryptosoft site above. And you need to
> choose your functions to defend against both linear and differential types of
> attacks, which they don't address.)
>
> Hope this helps!
>
Thanks for the feedback. No I performed some entropy tests on the output and
it bombed. Well I am getting "Applied Crytography" soon (for my b-day), and I
hope to pick up some stuff from there.
Right now I am just teaching myself stuff. I wouldn't consider TH1 or SHC2
very secure. They are ok for checksums though :)
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Ketema J,00996270 <[EMAIL PROTECTED]>
Subject: Please look at this rather odd cipher
Date: Sat, 20 Mar 99 14:48:35
Hi,
I would like some help with the following cipher, a friend gave it
to me:
(This is pseudo java script, all the arrays contain numbers between
0 and 256 and they are all 64 integers long)
Key expansion:
exp = new Array[64];
tmp = Math.PI;
for(i = 0; i < 64; i++) {
tmp = ((tmp * int_array_1[i % 16]) + int_array_2[i % 4]) % 256;
exp[i] = tmp
}
exp is the expanded key.
Decoding:
for(i = 63; i >= 0; i--) {
swp = floor(exp[i] % 64);
if(swp == i) {
swp = (swp + 1) % 64;
}
help = cipher_text[i];
cipher_text[i] = cipher_text[swp]^floor(exp[i]);
cipher_text[swp] = help;
}
At the end cipher_text contains the decrypted text.
Now the question is, given the cipher text and a peice of plain text,
retrieve the key or the complete plain text.
I want to ask two things about it (keep in mind I'm new to the
business of attacking ciphers):
1. Should this cipher be classified as a block cipher?
2. Could someone give me some hints about attacking this cipher.
Intuitively I think it's not a real hard one, although I could
be mistaken.
Thanks for helping me,
Jeroen Ketema
------------------------------
From: [EMAIL PROTECTED]
Subject: SHS (Sha)
Date: Sat, 20 Mar 1999 14:15:18 GMT
I went to the FIPS site to learn about SHA but the description is kinda
lacking detail. Does anybody have a clear and consise definition for SHA,
it's setup and runtime?
thanks,
tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: a little math please
Date: Sat, 20 Mar 1999 14:44:43 GMT
> No, there are 256! / (128! * 128!) combinations.
>
> > Can you estimate that number please?
>
> 5768658823449206338089748357862286887740211701975162032608436567264518750790
>
> Quite large, as you can see.
Thanks a lot. I just needed to know. BTW, how did you calc that? (what
program?)
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Paul Onions <[EMAIL PROTECTED]>
Subject: Re: pRNG that is "predictable to the left"?
Date: Sat, 20 Mar 1999 15:22:27 +0000
Steve Myers wrote:
>
> Scott Fluhrer wrote in message <7cuog9$[EMAIL PROTECTED]>...
> >In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] ("Steve Myers") wrote:
> >
> >>
> >>It is an easy theorem to prove that a generator is unpredictable to the left
> >>iff the generator is unpredictable to the right iff the generator is
> >>pseudo-random. Therefore, you have a generator which is predictable in both
> >>directions, you're just no aware of the predictibility in one direction.
>
...
>
> Proof Sketch (Presumably the only semi-interesting Direction)
> G is not pseudo-random=> G is not predictable from the left.
^^^
...
>
> Hope you're convinced.
>
> Steve
I think an easier proof that Scott's construction can't exist is simply to show that:-
G predictable to left => G not pseudo-random
which is really just the (left-handed) converse of what you've shown above
(removing your typo from the RHS of the statement). The proof is pretty trivial
(which I guess is why you didn't mention it) but for completeness (and for the
benefit of anybody else who is reading this) goes something like:-
given an n-bit sequence, remove the first few bits and give the result to the
"left-predictor" circuit. If this circuit can regenerate those bits then we
know with high probability that the sequence was produced by G, otherwise it
was probably random.
This is enough to show that Scott's idea can't exist.
Of course, the above can be applied to "predictable to the right" as well. And
coupling
this with your proof above (in left and right variations) gives us the if-and-only-if
existance theorem you mention.
So now we know that Scott's generator cannot be called pseudo-random, but that doesn't
mean that it can't be useful for something. I think it's quite an interesting idea in
its own right - but I can't immediately think what it might be used for (or what it
might be called). It probably also needs a more rigorous definition to ensure that
potential solutions are "interesting" :-)
Anyway, can I ask if you had some intended application for this Scott?
Regards,
Paul(o)
--
Paul Onions [EMAIL PROTECTED]
PGP 2.6.3 key available
D704688BEFBF2D5D 546BC1D603E2A8E0
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sat, 20 Mar 1999 16:08:49 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 20 Mar 1999 04:23:25 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>> So, there you have it - not only do statistical tests fail in general
>> for true random number generation processes, ...
>Only if the tests are inappropriate, or if their results are
>misinterpreted.
That is the whole point I am making, namely that statistical testing
are inappropriate and their results are misinterpreted when they
applied to crypto-grade randomness.
There is no statistical test to decide if a keystream is crypto-grade
random. Therefore ALL applications of statistical tests for that
purpose are inappropriate and their results misinterpreted.
>You might as well say that "0100011101" has only 1 chance in 1024
>of occuring, so if it is the output of a random bit generator, the
>generator isn't very random.
You might say that but I certainly would not. All possible sequences
of finite length are equiprobable when produced by a true random
number generator (TRNG). So if the string above is generated by such a
TRNG, then it is crypto-grade random. So are "0000000000" and
"1111111111", assuming the TRNG is not malfunctioning.
> That doesn't prove anything about
>statistics, other than how easy it is to give a plausible argument
>that is actually quite misguided. Good statisticians don't make
>this sort of mistake.
Good statisticians, just like good physicists, know that it is
misguided to characterize crypto-grade randomness with statistical
tests. But that does not stop the false worship at the altar of
statistical testing in crypto.
Bob Knauer
"Every government always exercises the maximum amount of power its
rulers feel the people will stand for without revolting."
-- Alongside Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Please look at this rather odd cipher
Date: Sat, 20 Mar 1999 16:12:38 GMT
> 1. Should this cipher be classified as a block cipher?
It's a stream cipher.
>
> 2. Could someone give me some hints about attacking this cipher.
> Intuitively I think it's not a real hard one, although I could
> be mistaken.
I would have to look closer.
Why not check out RC4, it works similarly, and there are no known attacks
against it (other then OTP matching).
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: SHS (Sha)
Date: Sat, 20 Mar 1999 16:32:15 GMT
[EMAIL PROTECTED] wrote:
> I went to the FIPS site to learn about SHA but the description is kinda
> lacking detail. Does anybody have a clear and consise definition for SHA,
> it's setup and runtime?
The full spec including test vectors is here:
http://www.itl.nist.gov/div897/pubs/fip180-1.htm
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp.discuss
Subject: Re: Does PGP use salt when hashing passphrases?
Date: 20 Mar 1999 13:39:50 -0000
[EMAIL PROTECTED] (Lincoln Yeoh) writes:
> Heh I know I should look at the source myself, but does anyone know?
>
> Was wondering if using salt for hashing/encrypting passphrases be a good
> idea. It's done for unix passwords to make pre-encrypted dictionary attacks
> harder. Just imagine 32 bits of salt, nice dictionary ;).
Passphrases should where possible be salted and stretched for
security. See Kelsey, Schneier, Hall, Wagner, "Secure Applications of
Low-Entropy Keys", available from http://www.counterpane.com/ .
I don't know what PGP does. I don't think it follows the procedure in
that paper.
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
Date: 20 Mar 1999 18:08:05 -0000
From: iLLusIOn <Use-Author-Address-Header@[127.1]>
Subject: Re: SHS (Sha)
=====BEGIN PGP SIGNED MESSAGE=====
>I went to the FIPS site to learn about SHA but the description is kinda
>lacking detail. Does anybody have a clear and consise definition for SHA,
>it's setup and runtime?
lacking detail? %-) this was the best description I was able to find,
good explanations with many examples.
I wrote an implementation of SHA just a few days ago, I think its source code
is rather easy to understand (compared to the other SHA source codes I
have found on the net), if you want me to send it to you let me know.
//iLLusIOn
~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Sat Mar 20 18:07:55 1999 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQEVAwUBNvPkA05NDhYLYPHNAQEDAAf/XklRmnc+N/lQWISmM2n9Rle6SU/q/b6V
YqBuzGGCN8XNqepmdZE7JaZpyCvp9boZBeM5VPv+bFrv8fZv7PA8OyMu3vVB2KqM
BIoKhUNqnd8G+koRMXcaXwsIOGjqCkYqPDTGIUYYnIN9uwGTx94KdttPEC1sR43D
QGCVzZ1T6co4vh7iGD4R5ljjiHAACPjB3IDQOoPKwglhbvZyGLcJiKunonB/5oOX
SDZG+7lvOaKIubPmzdrWaaZFZiH0amq58F4V1JP8qtTTaZNtwO5jUm4lu5UzQB2g
cB3csB23BsiuexwcQ6ZOfTpZHpndvss84KhrRW9RVdilxltZLL+lcQ==
=rcKN
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
