Cryptography-Digest Digest #233, Volume #9 Sun, 14 Mar 99 16:13:03 EST
Contents:
Re: SHA algorithm (iLLusIOn)
Throwing complexity at known PRNGs (Christopher)
Re: Total beginner ("Steve Sampson")
Re: Total beginner (Scott Fluhrer)
Re: Certicom Benchmark ("Michael Scott")
Throwing complexity at known PRNGs (revised) (Christopher)
Random salt ("Alex")
Factoring large numbers: MPQS algorithm. (Cryptolab)
64-bit hash of password ([EMAIL PROTECTED])
Re: SHA algorithm (Jim Gillogly)
Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Re: SHA algorithm (iLLusIOn)
Re: Random salt ([EMAIL PROTECTED])
Re: RSA-examples ([EMAIL PROTECTED])
Re: 64-bit hash of password (Jim Gillogly)
Re: Throwing complexity at known PRNGs ("Trevor Jackson, III")
Re: SHA algorithm (Jim Gillogly)
----------------------------------------------------------------------------
Date: 14 Mar 1999 13:32:05 -0000
From: iLLusIOn <Use-Author-Address-Header@[127.1]>
Subject: Re: SHA algorithm
=====BEGIN PGP SIGNED MESSAGE=====
>Never. You must have the 1 bit, and you must have the 64-bit length,
>so you must always hash at least 65 bits more than your data, and a
>multiple of 512 bits total.
Thanks for your help, now my implementation of the SHA-1 passes all
3 test vectors described in the FIPS PUB 180-1. :-)
The two main problems I had probably occured because of little/big-endian
conversion (still do not really understand why, took me quite some time of
debugging to figure out what I have to do to make it work).
I wrote a C++ method which is used to hash partial blocks (by first padding
them out to 512 bits and such). One of this method's parameters is the
full message's length (in bits). To append this 64bit value to the end
of the block I just used memcpy(buffer+56, &msglength, 8), what I later
noticed is that I have to reverse msglength first (from big- to
little-endian).
The same problem occured in the method used to hash a full 512 bit block,
before setting up W0, W1, W2, ..., W15 I first had to reverse M0, M1, ..., M15.
Is this normal? I mean, would SHA-1 work on little-endian cpu's without such
(slow) conversions? Or does this have to do with the compiler (Visual C++ 5)
I'm using?
//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: Sun Mar 14 13:32:02 1999 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQEVAwUBNuu6VE5NDhYLYPHNAQE5Cgf/SdA5+DGxlyOOE5/xtN+CgbBTYz1iCP0y
10kkqA7Uc8ok32idDu/ARjLA2iJaWUYE14vOgIKsP52Yp7zfkfVON7uMl22aS2t4
ZA804Kp55uaciBfMgLmdHd/hO+9BRCUkFdSIH2HLYp5npen7+Y4MS2GQU/emf3Io
Lo5C2l7BcxQL0/yJfAefSNGjsGI9wXHPiHJcIRa7o0eRD1kn7PHvXks5EaQg3lLW
1cCMIYPcz4LzGDUZjsP9gFUsBxM3eqIxOsDL1m1XPknaeittlQ2Qv71c2A0SjADY
YtqrD4xa2yOJOfc3abl6uEGajlZOyNaOckaEegx0r0MigJTtTo6FIA==
=ctOk
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Christopher)
Subject: Throwing complexity at known PRNGs
Date: Sat, 13 Mar 1999 20:17:58 -0500
For generating a stream cipher the concensus here seems to be that the
problem is with an attacker knowing the generator.
So here's an idea, probably not new, but I haven't seen it discussed here
since I've been trying to catch up. For simplicity I'll use two
generators in the example, although the idea came to me using four or
eight, depends on where the weakesses are and how simple it should remain.
Suppose the key is hashed differently for each of two PRNGs, perhaps
Yarrow and KISS, the hunch is that the algorithms should be different, or
at the least their periods. Go through the usual throwing away of so many
initial iterations then; iterate both, use the parity of the XOR of the
two results to decide which generator to use for that character in
encryption, repeat.
Sounds simple enough, an analysis would show multiple correlations
presumably making it more difficult to attack. And with more than two
generators being multiplexed this way seems to make it even more useful.
Four generators that keep large internal states, but output a word each
could be used - at step k the low-order byte is used from one, the
high-order byte from another, and another to determine the choice of
generators for step k+1.
Like I said, sounds simple enough, so let me know what I'm missing, or
where to look for any work done here. In particular would feedback from
the final output into the generators make analysis harder, or open up new
holes in the system? I put together an outline of such a system at
<http://home.ptd.net/~kruslicc/mprng/prngMUX.html>, if anyone is
interested.
------------------------------
From: "Steve Sampson" <[EMAIL PROTECTED]>
Subject: Re: Total beginner
Date: Sun, 14 Mar 1999 09:13:55 -0600
Bitch, Bitch, Bitch. You sound like an old lady...
His web page is Javascript. You can look at it with your browser.
Whether it is bad or good deserves a comment if you are interested.
If you aren't interested, and busy with other things, don't waste your
time. But to just bitch and whine seems rather shallow.
Scott Fluhrer wrote
>Oh, and I tried your Web page. Normally, I whine at newbies not to shove
>their code at me, and instead give me a mathematical description of their
>algorithm. Here, you didn't even do that -- you gave me a black box (which
>didn't even work). Next time, write up your algorithm in sufficient detail
>that I could write a program for it on my computer (and you don't know what
>type of computer or what programming language I use).
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Total beginner
Date: Sun, 14 Mar 1999 15:41:36 GMT
In article <tpQG2.12$[EMAIL PROTECTED]>,
"Steve Sampson" <[EMAIL PROTECTED]> wrote:
>Scott Fluhrer wrote
>
>>Oh, and I tried your Web page. Normally, I whine at newbies not to shove
>>their code at me, and instead give me a mathematical description of their
>>algorithm. Here, you didn't even do that -- you gave me a black box (which
>>didn't even work). Next time, write up your algorithm in sufficient detail
>>that I could write a program for it on my computer (and you don't know what
>>type of computer or what programming language I use).
>Bitch, Bitch, Bitch. You sound like an old lady...
>
>His web page is Javascript. You can look at it with your browser.
>Whether it is bad or good deserves a comment if you are interested.
>If you aren't interested, and busy with other things, don't waste your
>time. But to just bitch and whine seems rather shallow.
>
I respectfully disagree. He said he was a complete newbie. So, I would be
derelict not to inform him of the standards that are generally expected
around here. After all, he should understand that he's asking for our
help: we're not getting paid for this; it's his responsibility to present
his ideas in a manner that doesn't waste our time to try to figure out what
they are. And so, I told him what he was doing wrong, and pointed out what
he should have done. That's not whining, that's instruction.
And, if I chided him a bit too roughly, well, that was the version *after*
I rewrote it to soften it a bit...
An old lady? Trust me on this one, I'm no lady...
--
poncho
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Certicom Benchmark
Date: Sun, 14 Mar 1999 17:21:16 -0000
>First -- what computer were the quoted times generated for (the 91.67 >ms,
etc.)?
All times (mine and their's) were on a Pentium Pro 200MHz
>
>Second -- what were your times for the ECDH used in the comparison?
>
I didn't do my own timings for ECDH. I accept the accuracy of theirs.
>...
>IMO, you need to make the comparisons on the same playing field.
I did.
Mike Scott
------------------------------
From: [EMAIL PROTECTED] (Christopher)
Subject: Throwing complexity at known PRNGs (revised)
Date: Sun, 14 Mar 1999 02:08:58 -0500
For generating a stream cipher the concensus here seems to be that the
problem is with an attacker knowing the generator.
So here's an idea, probably not new, but I haven't seen it discussed here
since I've been trying to catch up. For simplicity I'll use two
generators in the example.
Suppose the key is hashed differently for each of two PRNGs, the hunch is
that the algorithms should be different, or at the least their periods.
Go through the usual throwing away of so many initial iterations then;
iterate both, use the parity of the XOR of the
two results to decide which generator to use for that character in
encryption, repeat.
An analysis would show multiple correlations presumably making it more
difficult to attack. And with more than two generators being multiplexed
this way seems to make it even more useful.
Please let me know what I'm missing, or where to look for any work done
here. In particular would feedback from the final output into the
generators make analysis harder, or open up new holes in the system? I put
together an outline of such a system at
<http://home.ptd.net/~kruslicc/mprng/prngMUX.html>, if anyone is
interested. Basically it uses four generators and sets some parameters to
make it easier to comment directly.
PS - apologies for the second posting, the first one a glaring error in it!
--
It's easier to judge a book by its cover knowing nothing of its contents.
------------------------------
From: "Alex" <[EMAIL PROTECTED]>
Subject: Random salt
Date: Sun, 14 Mar 1999 20:31:57 +0300
How to use random salt values when hashing password with SHA1?
For example, I want to generate random key and for this purpose hash
password with 64 bits of salt.
------------------------------
From: Cryptolab <[EMAIL PROTECTED]>
Subject: Factoring large numbers: MPQS algorithm.
Date: Sun, 14 Mar 1999 18:52:16 +0100
Reply-To: [EMAIL PROTECTED]
Hi everyone,
I am actually doing a study on the factoring algorithms but I still
have some trouble with the MPQS. I perfectly understand how the basic
quadratic Sieve works but I don't get the multipolynomial stuff.
If someone knows anything or any site which can tell me more about
this algorithm (complexity proof - working process in detail), I'll
apreciate it very much.
MENIER Clement.
E-Mail: [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: 64-bit hash of password
Date: Sun, 14 Mar 1999 16:52:46 GMT
As you may have known I have released RC4E my public RC4 file encryptor (uses
a salt). However my private key generation is not very secure....
Basically are there any good 64/128 bit hashes for small (<64 bytes) messages?
(also urls for the papers would be nice :) )
Thanks,
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: SHA algorithm
Date: Sun, 14 Mar 1999 10:26:51 -0800
iLLusIOn wrote:
> Thanks for your help, now my implementation of the SHA-1 passes all
> 3 test vectors described in the FIPS PUB 180-1. :-)
If you implement the full spec (partial bytes are allowed), Francois
Grieu and I have agreed on some additional test vectors to test the
points where internal buffers fill up and roll over. I'd be happy to
provide them as needed.
> full message's length (in bits). To append this 64bit value to the end
> of the block I just used memcpy(buffer+56, &msglength, 8), what I later
> noticed is that I have to reverse msglength first (from big- to
> little-endian).
> The same problem occured in the method used to hash a full 512 bit block,
> before setting up W0, W1, W2, ..., W15 I first had to reverse M0, M1, ..., M15.
>
> Is this normal? I mean, would SHA-1 work on little-endian cpu's without such
> (slow) conversions? Or does this have to do with the compiler (Visual C++ 5)
> I'm using?
Endianness annoyances are normal, but since SHA-1 is inherently a
big-endian algorithm, as MD5 is inherently little-endian, I would
have expected your annoyance to go the opposite way -- you did
indicate you're on a big-endian platform, right?
--
Jim Gillogly
Mersday, 22 Rethe S.R. 1999, 18:08
12.19.6.0.7, 2 Manik 20 Kayab, Seventh Lord of Night
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Date: 14 Mar 99 17:44:42 GMT
Frode Weierud ([EMAIL PROTECTED]) wrote:
: After
: I was told (I think by John Savard) that the link not longer was
: functional I took contact with CESG.
It was a link to Motorola's web page about the AIM chip I had told you
about (they changed a directory name by one letter) - somebody else
deserves the credit for checking this link.
John Savard
------------------------------
Date: 14 Mar 1999 19:35:45 -0000
From: iLLusIOn <Use-Author-Address-Header@[127.1]>
Subject: Re: SHA algorithm
=====BEGIN PGP SIGNED MESSAGE=====
>If you implement the full spec (partial bytes are allowed), Francois
>Grieu and I have agreed on some additional test vectors to test the
>points where internal buffers fill up and roll over. I'd be happy to
>provide them as needed.
Right now my implementation doesn't allow partial bytes, but I'm thinking
about adding this function (after I did some size and speed optimizations).
Please send these test vectors to my email address or to the NG (if not too
big).
>Endianness annoyances are normal, but since SHA-1 is inherently a
>big-endian algorithm, as MD5 is inherently little-endian, I would
>have expected your annoyance to go the opposite way -- you did
>indicate you're on a big-endian platform, right?
oops sorry, I ment that I'm on a little-endian platform, the application
will run on Win32 systems with Intel the like cpu's.
As SHA-1 is 'inherently a big-endian' algorithm all of the problems I had
make sense now. ;-)
//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: Sun Mar 14 19:35:33 1999 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQEVAwUBNuwPj05NDhYLYPHNAQFvHAf+MzD5Qqt2FfN1ssUgxf9ArocXR/wi5nFt
/5WX6s8JgWdq5reGIv5BQ6xBbrnaTfnG+Tt8vy+jCJWnCq2r2qUqdvPZ3aU3VQDp
MnQHj3FgrnU4Lw+nW4C1lLAVuoYjumfq8B8RX3EOIFY/NCmwWOc+at5hGDy+FmPL
T0ocGm7djvMPZJt2mDfIwyc2eRhid8LatOe9bjMptJuIrqD1MmBEpPT760ZVU5AH
eRlYaxYbuRJXhqpXJ9+1Ld2vZSIlLhsECDXdRCgIhJaoOb5sL/jA2zmzHUyFwbbG
3/pbMNdM549JjVeSbzOuHe7XmqFBPRUEIzoczPbTBpveGmuFvGoDNA==
=YtEX
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random salt
Date: Sun, 14 Mar 1999 20:01:37 GMT
> How to use random salt values when hashing password with SHA1?
> For example, I want to generate random key and for this purpose hash
> password with 64 bits of salt.
>
>
The purpose of a salt is to thwart OTP attacks. Therefore the salt should be
in no way related to the secret key, which includes hashing of the secret key.
Although something like SHA-1 (assmuning 160bit salt) would be feasible, it
would give someone something to go on when verifying your key.
You can use SHA1 or MD5 but I would suggest a more 'random' source of salt.
i.e SHA1 and MD5 (well MD5 has a weakness I am told) would be effective, just
don't rely on it.
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA-examples
Date: 14 Mar 1999 20:10:32 GMT
>
> RSA-examples
>
> From: [EMAIL PROTECTED]
> Reply to: [EMAIL PROTECTED]
> Date: Fri, 12 Mar 1999 13:31:29 GMT
> Organization: Deja News - The Leader in Internet Discussion
> Newsgroups:
> sci.crypt
> Followup to: newsgroup(s)
>Hello,
>
>The update of my RSA examples implemented as MS Access
>data base(354Kb.ZIP) contains 36 tables. There is
>following name convention. A table with the name 'tab_P_Q_M'
>represents a modulus, where P and Q are prime multiplier of
>the modulus and M is the period.
>If (n,e) is a key and p is the period then (n,e+k*p) are keys
>with the same en/decryption. A period can be found as follows.
>Let n=11*13 be a modulus. 11-1= 2*5. 13-1=2*2*3.
>The period of 11*13 is 5*2*2*3=60.
>A period is responsible for all different key pairs. This is why
>tables with the name PGP_M, where M is a period, contain all
>possible pairs of exponents, which can be used for en/decryption.
>Pairs, which contain different exponents, represent asymmetric
>encryption. There are pairs, which contain equal exponents.
>Such exponent represent symmetric encryption. For example.
>Suppose your modulus is 11*13. The name of the correspondent
>table is tab_11_13_60. While period is 60 you can find all
>possible key pairs in the table PGP_60.
>The examples can be used for learning more about RSA encryption
>and checking your RSA implementation.
>
>You can download examples from:
>
>www.online.de/home/aernst/RSA.html
>
>My own encryption, implemented as stream and block cipher, with
>detailed algorithm description, freeware executables, Delphi 4
>source code you can find at
>
>www.online.de/home/aernst
>
>
>Best regards
>Alex
>
>-----------== Posted via Deja News, The Discussion Network ==----------
>http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: 64-bit hash of password
Date: Sun, 14 Mar 1999 12:21:34 -0800
[EMAIL PROTECTED] wrote:
> As you may have known I have released RC4E my public RC4 file encryptor (uses
> a salt). However my private key generation is not very secure....
>
> Basically are there any good 64/128 bit hashes for small (<64 bytes) messages?
SHA-1 is the current most recommended hash; RSA Labs, the author of MD5,
deprecates MD5's use for new implementations because of a weakness found
by Hans Dobbertin in its compression function. Note that hashing crappy
salts will not add any randomness to them, but merely disguise the fact
that they don't have much -- so you still need to make sure you're
stuffing enough entropy into the hash function for what you need on
the other end. The advantage of the hash is that it can take a few
hundred bytes of input that may have 128 bits of randomness total in
them, and condense it down into the size of salt you need.
If you don't need all 160 bits of SHA-1, simply keep as many as you
want. There are no known biases in whether the first 64/128 or the
last are any better than any other bits.
Other hashes have been proposed (e.g. Anderson & Biham's "Tiger",
optimized for 64-bit machines); none has gotten as much analysis
as SHA-1 so far.
--
Jim Gillogly
Mersday, 22 Rethe S.R. 1999, 20:10
12.19.6.0.7, 2 Manik 20 Kayab, Seventh Lord of Night
------------------------------
Date: Sun, 14 Mar 1999 15:20:11 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Throwing complexity at known PRNGs
Christopher wrote:
>
> For generating a stream cipher the concensus here seems to be that the
> problem is with an attacker knowing the generator.
>
> So here's an idea, probably not new, but I haven't seen it discussed here
> since I've been trying to catch up. For simplicity I'll use two
> generators in the example, although the idea came to me using four or
> eight, depends on where the weakesses are and how simple it should remain.
>
> Suppose the key is hashed differently for each of two PRNGs, perhaps
> Yarrow and KISS, the hunch is that the algorithms should be different, or
> at the least their periods. Go through the usual throwing away of so many
> initial iterations then; iterate both, use the parity of the XOR of the
> two results to decide which generator to use for that character in
> encryption, repeat.
>
> Sounds simple enough, an analysis would show multiple correlations
> presumably making it more difficult to attack. And with more than two
> generators being multiplexed this way seems to make it even more useful.
> Four generators that keep large internal states, but output a word each
> could be used - at step k the low-order byte is used from one, the
> high-order byte from another, and another to determine the choice of
> generators for step k+1.
>
> Like I said, sounds simple enough, so let me know what I'm missing, or
> where to look for any work done here. In particular would feedback from
> the final output into the generators make analysis harder, or open up new
> holes in the system?
Whe you create feedback you open up the possibility of degeneracy. A
short cycle of states is easy to create this way, and deadly to the
desired properties of the generator (maximal period)).
If you are extremely careful and can analyticaly prove that no short
cycles are created you may be able to realize the full capability of the
system, but you can usually do that anyway without feedback.
I put together an outline of such a system at
> <http://home.ptd.net/~kruslicc/mprng/prngMUX.html>, if anyone is
> interested.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: SHA algorithm
Date: Sun, 14 Mar 1999 13:02:34 -0800
iLLusIOn wrote:
> Right now my implementation doesn't allow partial bytes, but I'm thinking
> about adding this function (after I did some size and speed optimizations).
> Please send these test vectors to my email address or to the NG (if not too
> big).
Francois Grieu and I agreed on these partial-byte test vectors, using
two quite different implementations.
In the following we use the notation bitstring#n to mean a bitstring
repeated n (in decimal) times, and we use | for concatenation. Therefore
110#3|1 is 1101101101.
110#148|11 : CE7387AE 577337BE 54EA94F8 2C842E8B E76BC3E1
110#149 : DE244F06 3142CB2F 4C903B7F 7660577F 9E0D8791
110#149|1 : A3D29824 27AE39C8 920CA5F4 99D6C2BD 71EBF03C
110#149|11 : 351AAB58 FF93CF12 AF7D5A58 4CFC8F7D 81023D10
110#170 : 99638692 1E480D4E 2955E727 5DF3522C E8F5AB6E
110#170|1 : BB5F4AD4 8913F51B 157EB985 A5C2034B 8243B01B
110#170|11 : 9E92C554 2237B957 BA2244E8 141FDB66 DEC730A5
110#171 : 2103E454 DA4491F4 E32DD425 A3341DC9 C2A90848
011#490 : B4B18049 DE405027 528CD9E7 4B2EC540 D4E6F06B
011#490|0 : 34C63356 B3087427 20AB9669 14EB0FC9 26E4294B
011#490|01 : 75FACE18 02B9F84F 326368AB 06E73E05 02E9EA34
011#491 : 7C2C3D62 F6AEC28D 94CDF93F 02E739E7 490698A1
Here is a set near 2^32 bits to test the roll-over in the length
field from one to two 32-bit words:
110#1431655764|11 1eef5a18 969255a3 b1793a2a 955c7ec2 8cd221a5
110#1431655765| 7a1045b9 14672afa ce8d90e6 d19b3a6a da3cb879
110#1431655765|1 d5e09777 a94f1ea9 240874c4 8d9fecb6 b634256b
110#1431655765|11 eb256904 3c3014e5 1b2862ae 6eb5fb4e 0b851d99
011#1431655764|01 4CB0C4EF 69143D5B F34FC35F 1D4B19F6 ECCAE0F2
011#1431655765 47D92F91 1FC7BB74 DE00ADFC 4E981A81 05556D52
011#1431655765|0 A3D7438C 589B0B93 2AA91CC2 446F06DF 9ABC73F0
011#1431655765|01 3EEE3E1E 28DEDE2C A444D68D A5675B2F AAAB3203
--
Jim Gillogly
Mersday, 22 Rethe S.R. 1999, 20:59
12.19.6.0.7, 2 Manik 20 Kayab, Seventh Lord of Night
------------------------------
** 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
******************************
