Cryptography-Digest Digest #906, Volume #12 Thu, 12 Oct 00 21:13:01 EDT
Contents:
Securely hashed passwords ([EMAIL PROTECTED])
Re: Bored with AES? SHA-256/384/512 spec now out! ("Joseph Ashwood")
Re: NSA quote on AES (Eric Smith)
Re: naval code books were "weighted" (Albert Yang)
Re: My view of election. (Albert Yang)
Re: Bored with AES? SHA-256/384/512 spec now out! (David Crick)
Re: Rijndael implementations (Tim Tyler)
Re: Rijndael implementations (Roger Schlafly)
Problem with SHA256 implementation (Tom St Denis)
Re: Bored with AES? SHA-256/384/512 spec now out! (Tom St Denis)
Re: Securely hashed passwords ("Joseph Ashwood")
Re: A new paper claiming P=NP ([EMAIL PROTECTED])
Re: A new paper claiming P=NP ([EMAIL PROTECTED])
Re: Problem with SHA256 implementation (Tom St Denis)
SHA-256 implementation in pure C (free) (Tom St Denis)
Re: Code Book Cipher Challenge Cracked (Scott Contini)
Re: Bored with AES? SHA-256/384/512 spec now out! (lcs Mixmaster Remailer)
Re: Code Book Cipher Challenge Cracked (Jim Gillogly)
Re: A new paper claiming P=NP (Stas Busygin)
Re: naval code books were "weighted" (John Savard)
Re: Bored with AES? SHA-256/384/512 spec now out! (Roger Schlafly)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Securely hashed passwords
Date: Thu, 12 Oct 2000 21:57:51 GMT
Can someone show me an easy way to generate securely hashed passwords?
I need to import them as flat files into LDAP, and I expect them to
look like this: {SHA}NWdeaPS1r3uZXZIFrQ/EOELxZFA=
I tried using SHA.pm, but I'm having trouble getting it into a 32 bit
string.
A small perl snippet would be greatly appreciated.
Thanks in advance,
Mike Coughlan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Bored with AES? SHA-256/384/512 spec now out!
Date: Thu, 12 Oct 2000 14:55:58 -0700
[re my worries about square versus cube roots being used]
OOPS. I wasn't checking the page of the spec, but instead the page number of
the document, the correct pages are: page 7, and page 3, respectively.
Joe
------------------------------
From: Eric Smith <[EMAIL PROTECTED]>
Subject: Re: NSA quote on AES
Date: 12 Oct 2000 15:18:59 -0700
I asked:
> What Skipjack fiasco is that?
[EMAIL PROTECTED] (Mack) wrote:
> So far as I know the 80 bit key was
> the major weakness. 56 bit keys are obviously crackable.
> 80 bits is 16 million times harder but that certainly isn't going
> to prevent attack 20 years from now. Anyone with enough money
> could probably build a skipjack cracker that will provide keys for
> a specific known plaintext/ciphertext pair.
If there is no attack more efficient than brute-force, then
the cipher is very well designed.
Whether 80 bits is enough is an important question, but has no
bearing on whether Skipjack met its design objectives.
------------------------------
From: Albert Yang <[EMAIL PROTECTED]>
Subject: Re: naval code books were "weighted"
Date: Thu, 12 Oct 2000 22:29:58 GMT
Yeah, you mean book+ 100lbs of lead, or do you mean that there is a
statistical bias that is detectable in the code itself??
I thought all sensitive naval stuff was not weighted, but rather,
written on water sensitive paper that smeared if it got wet..
Albert
------------------------------
From: Albert Yang <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: My view of election.
Date: Thu, 12 Oct 2000 22:34:30 GMT
If you want REAL crypto export friendliness, try Harry Browne.
I asked what Harry's stance was on crypto export, and here is the
official response from their office::
"Harry Browne believes in totally free trade, no restrictions
on what may be traded or with whom.
Cordially,
[EMAIL PROTECTED]
"
So there you go...
Albert
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: Re: Bored with AES? SHA-256/384/512 spec now out!
Date: Thu, 12 Oct 2000 23:35:22 +0100
Ian Goldberg wrote:
>
> >http://csrc.nist.gov/cryptval/shs.html
> >
> >PDF spec at: http://csrc.nist.gov/cryptval/shs/sha256-384-512.pdf
>
> Hmmm. It worries me a bit that they define functions R and S, and
> that R is "shift" and S is "rotate". Are these for sure not mixed up?
Or it could be security by confusity ;)
Email the NIST guys if you're worried. No doubt they will be
able to confirm the notation - or at least be able to check
it with the people who write the Nice Secure Algorithms.
--
+-------------------------------------------------------------------+
| David A. Crick <[EMAIL PROTECTED]> PGP: (OCT-2000 KEY) 0xE0F73D98 |
| Damon Hill Tribute Site: http://www.geocities.com/MotorCity/4236/ |
| M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
+-------------------------------------------------------------------+
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Reply-To: [EMAIL PROTECTED]
Date: Thu, 12 Oct 2000 22:04:08 GMT
Brian Gladman wrote:
>Paul Schlyter" <[EMAIL PROTECTED]> wrote:
>> David Eppstein <[EMAIL PROTECTED]> wrote:
>> >In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
["octets"?]
>> >> This is what "byte" *should* mean in the first place. Having "byte"
>> >> defined as "set of bits that represent a single character" seems
>> >> like a really dumb idea to me.
>> >
>> >You've obviously never programmed a 36-bit architecture.
>>
>> ...or a 60-bit architecture...
>
> ....or 39...
I still think there should be a single term for units of 8 bits. I think
that term should be "byte". To my mind that's more or less the way things
are at the moment.
If you speak about bytes without qualification, that's what people think
you mean. For example, nobody asks whether you're talking about 8-bit
kilobytes/megabytes/gigabytes, or some other type - it's just taken for
granted.
Unicode means characters are frequently represented in 16-bit chunks -
AFAIK, these *never* get called "bytes".
Hopefully, the size of a "byte" will become fixed. This has already
happened in computer languages - if you look at C the size of int, chars
is implementation dependent. By contrast in Java, everything -
including bytes - are of predefined sizes. Hopefully normal usage will
follow suit.
At the moment a 6-bit byte makes sense (according to the dictionary).
I expect in the far future, it will appear to be contradictory nonsense.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Chaste makes waste.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Thu, 12 Oct 2000 15:37:42 -0700
Kasper Pedersen wrote:
>
> "David Eppstein" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > > This is what "byte" *should* mean in the first place. Having "byte"
> > > defined as "set of bits that represent a single character" seems like a
> > > really dumb idea to me.
> > You've obviously never programmed a 36-bit architecture.
>
> Or an architecture where words are 14 bit and bytes 8 (not 7). Mighty
> annoying.
>
> They (strange bit sizes) are rather common when one leave the 'mainstream'
> micros in search of something more efficient/cost effective for a particular
> task.
What are you guys programming? When I was in school, they still had
a CDC 6600 humming in the basement. But it's been a long time since
I heard of anyone building a machine with a byte being anything
other than 8 bits.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Problem with SHA256 implementation
Date: Thu, 12 Oct 2000 23:03:59 GMT
At http://www.geocities.com/tomstdenis/files/sha256.c is my "portable"
implementation of SHA-256. I have triple checked the code (found
numerous typos) but it still doesn't produce the correct output... I
would seriously appreciate some help!!!
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Bored with AES? SHA-256/384/512 spec now out!
Date: Thu, 12 Oct 2000 23:02:16 GMT
In article <OO2Z0aJNAHA.321@cpmsnbbsa09>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> Personally I'm more worried by:
> Page 9: These are the rst thirty-two bits of the fractional parts of
the
> cube roots of the first sixty-four primes.
> Page 5: which are obtained by taking the fractional parts of the
square
> roots of the rst eight primes
>
> Both discussing the initial state of SHA-256.
I am in the midsts of doing a portable SHA-256 and I found no problem
recreating those tables with a short program...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Securely hashed passwords
Date: Thu, 12 Oct 2000 15:50:39 -0700
While I don't speak perl, I can tell you how to do it. In something
resembling pseudo-code it look like this:
20 entry array of chararacters C := SHA(password)
4 entry array of characters A = first 4 characters of C
Enter A in database
There is a problem though, it will take an attacker an average of 65536 work
to find an effective password. Considering that we now rate processors in
terms of billion of operations a second, 65536 is an extremely small number
and represents something is far from secure.
Joe
<[EMAIL PROTECTED]> wrote in message
news:8s5c4r$7rp$[EMAIL PROTECTED]...
> Can someone show me an easy way to generate securely hashed passwords?
> I need to import them as flat files into LDAP, and I expect them to
> look like this: {SHA}NWdeaPS1r3uZXZIFrQ/EOELxZFA=
>
> I tried using SHA.pm, but I'm having trouble getting it into a 32 bit
> string.
>
> A small perl snippet would be greatly appreciated.
>
> Thanks in advance,
>
> Mike Coughlan
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Thu, 12 Oct 2000 23:05:38 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
> Given T a consistent finite collection of axioms in a recursively-
presented
> language, T consistent, Q relatively interpretable in T. For any
> theorem s of T, let f(s) be the length of its shortest proof. Now
> let g(n) be the maximum value of f(s), where s ranges over all
theorems
> of T having n or fewer symbols.
>
> Conjecture: g(n) grows faster than any primitive recursive function.
>
> Can anyone prove or refute?
>
> I'd be willing to extend the conjecture to r.e. collections of axioms,
> except that somehow the sequence of states of the program producing
> the axioms must be charged to the length of the proof. Otherwise
> every theorem could be an axiom, so every theorem with n symbols
> would have a proof with n+k symbols for some constant k.
>
Godel proved that in mathematics for any N there are propositions whose
shortest proof is longer than N. But that is weaker than what you are
looking for.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Thu, 12 Oct 2000 23:10:36 GMT
In article <8ruked$kb7$[EMAIL PROTECTED]>,
David Bernier <[EMAIL PROTECTED]> wrote:
>
> Suppose P is a proof in ZFC of FLT similar to Wiles', but with
> proofs of all lemmas and all background material included
> (i.e. a self-contained proof). I wonder what the order of magnitude
> of the length of P might be...
>
> David Bernier
>
Considering that Principia Mathematica requires several volumes to
prove that 1+1=2, Wiles' proof at that level of rigor would be quite
lengthy.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Problem with SHA256 implementation
Date: Thu, 12 Oct 2000 23:39:44 GMT
In article <8s5g0r$b7h$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> At http://www.geocities.com/tomstdenis/files/sha256.c is my "portable"
> implementation of SHA-256. I have triple checked the code (found
> numerous typos) but it still doesn't produce the correct output... I
> would seriously appreciate some help!!!
Problem fixed and it conforms to the test vectors. Let's just say the
printer put the xor symbol as a - symbol ... hehehehe
I would like people on big endian platforms to test it to make sure it
does work there too...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: SHA-256 implementation in pure C (free)
Date: Thu, 12 Oct 2000 23:44:10 GMT
At http://www.geocities.com/tomstdenis/files/sha256.c you can find a
free copy of the SHA-256 hash function in C. It's rather easy to drop
in and use. I hope SHA-256 is in fact secure though... heheheh
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Code Book Cipher Challenge Cracked
Date: 13 Oct 2000 00:05:55 GMT
In article <[EMAIL PROTECTED]>,
JPeschel <[EMAIL PROTECTED]> wrote:
>All 10 stages of Singh's Code Book Cipher Challenge
>have been cracked.
>
>See:
>
>http://www.simonsingh.com/cipher.htm
>
>Joe
>__________________________________________
>
>Joe Peschel
>D.O.E. SysWorks
>http://members.aol.com/jpeschel/index.htm
>__________________________________________
>
Congratulations to the Swedish team!
Since there were a lot of rumors about other teams breaking all 10
stages, I wonder if any other team had sent in a solution after the
Swedish team but before the solution was announced?
Maybe Jim Gillogly and others could comment how close they came to
factoring the final number?
I also think there are a few misleading statements on the web page
indicated above, though Singh admits there may be mistakes when he
writes:
Before continuing, I apologise for any
typographical errors or any other mistakes, but I
had to rush to complete this summary. I felt that it
was important to release this news as soon as
possible, rather than risk leaks and rumours.
(regarding stage 10 of the cipher challenge:)
Singh claims that they rewrote the number field sieve so that it
can run on an ordinary computer rather than a supercomputer. I think
that the correct statement is that they rewrote only the matrix part of
the NFS code so that it can run without the use of a supercomputer,
which is one of 4 or 5 stages of the NFS. The other stages have always
been done on ordinary computers. However this is not to take anything
away from the Swedish team: making the matrix run efficiently on an
ordinary computer is definitely an important research topic and I
hope they will publish the details of their implementation.
My understanding from http://answers.codebook.org/node53.html is that
they used mostly CWI's NFS code. It would be great if they publish
specific details of their factorisation: the polynomials used, the
parameters (rational & algebraic factor base sizes, sieve interval length,
etc...), timings for the different stages, etc....
I find it is especially significant that although many groups were
competing to factor this 155-digit number, the group that did it had
only 5 members, and they were unknown (ie in stealth mode) to everybody
else. I am also a bit curious what size numbers these groups would
be able to conquer if they all worked together, along with the cabal
group who has been setting all the previous factoring records (the
factorisation of the Singh number ties the factorisation of RSA-155
for largest general purpose factorisation). More than likely the biggest
problem for going to larger numbers will be the matrix, so the insite
of the Swedish team on this part is of extreme cryptographic importance!
As a side note, Peter Montgomery has also been working on this problem.
Scott
------------------------------
Date: 13 Oct 2000 00:20:03 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: Bored with AES? SHA-256/384/512 spec now out!
Ian Goldberg wrote:
>
> >http://csrc.nist.gov/cryptval/shs.html
> >
> >PDF spec at: http://csrc.nist.gov/cryptval/shs/sha256-384-512.pdf
>
> Hmmm. It worries me a bit that they define functions R and S, and
> that R is "shift" and S is "rotate". Are these for sure not mixed up?
Just implemented it, it's an easy change to SHA-1 to get SHA-256. We can
confirm their test vectors, using R as right shift and S as right rotate,
as written in the spec.
Here's another output for others to check, SHA-256 of one million bytes
of 'a' (ascii 0x61):
CDC76E5C 9914FB92 81A1C7E2 84D73E67 F1809A48 A497200E 046D39CC C7112CD0
SHA-512 is just about the same as SHA-256, except everything is done with
twice the width. This means that all the arithmetic is 64 bits.
That's going to take a bit more work to convert.
Adding (ah,al) + (bh,bl) = (ch,cl) in C, using unsigned 32 bit ints:
cl = bl + al;
al = ah + bh + (cl<bl);
i.e. there is a carry if the sum is smaller than either of the operands.
Next we need an extension to the DSA spec to use this new hash, with
rules about which size keys use each different hash.
Be nice to have an OID too for use with PKCS-1. Anyone got one?
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Code Book Cipher Challenge Cracked
Date: Fri, 13 Oct 2000 00:18:00 +0000
Scott Contini wrote:
> Maybe Jim Gillogly and others could comment how close they came to
> factoring the final number?
I estimate that we (John Palagyi, Alec Muffett, and me) were
about 2.5 months away from success -- we got a late start, but
were sieving up a storm.
--
Jim Gillogly
Sterday, 22 Winterfilth S.R. 2000, 00:15
12.19.7.11.6, 9 Cimi 9 Yax, First Lord of Night
------------------------------
From: Stas Busygin <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Fri, 13 Oct 2000 03:48:03 +0300
First of all, thanx a lot for really sensible criticism as previous
attacks were out of the matter.
Eric Lehman wrote:
> Please understand that this paper is nearly unintelligible. Almost
> every sentence contains at least one grammatical or punctuation error (I
> do *not* exaggerate),
Well, I can't argue with this as English is not my first too. But
as the author pointed me, the paper was looked through by a person
from the U.S. who is a professional editor (working with fiction
literature, to tell the truth). However, I agree that the style of
the paper is not good and I had to pay more attention to this. Ok,
I'll try to delve into every detail next time.
> and there appear to be mathematical slips as
> well. For example, even the little 3-step algorithm on pages 5-6 seems
> to have an indexing error. In particular, N must decrement n times for
> the procedure to terminate, but by then variable i could easily exceed
> n, which is nonsensical. Am I overlooking something?
Thanks, I think you are right. I'll forward this to the author.
> Given this mess, I doubt the paper will ever be verified or refuted
> without someone to answer detailed questions on the text. You've
> decided to widely popularize the paper; will you take on this
> clarification task for us?!
Feel free to point out any unclear detail. According to the
publishing rules of my *REPOSITORY* any stuff in it can be renewed
at any time, so all found faults are to be corrected by authors.
That is why I think my publishing policy makes sense -- anyone who
wishes can become familiar with proposed stuff in its raw form and
help authors to correct/improve it. And this will not take a number
of years as in many known journals. I respect them very much, but
/I just draw a random volume of SIAM Review from my bookshelf/ do
you think it's ok when a paper submitted in 1995 was published only
in the beginning of 1998? Personally I think that an algorithmic
proposal has a great chance to be outdated for such term if its
field develops appropriately... not on the basis of *beliefs* as it
is around P?=NP domain...
> The rest of this post concerns details of the paper. Here's where I'm
> stuck:
>
> On page 10 he shows how to direct the edges of a graph G to get a DAG,
> which defines a poset. Fine. Take a minimum chain decomposition.
> Fine. Now we get definitions:
>
> A path P in G is said to be "stretched" on the set of chains that it
> intersects. Is this correct?
Yes.
> The definition of "densely stretched" confuses me. A path P in G is
> said to be "densely stretched" on the set of chains it intersects
> *provided* no two adjacent vertices on the path lie in the same chain.
> Is this correct? Or is it that no two vertices connected by an edge in
> G can lie in the same chain? As I understand it, every simple path is
> "stretched" on some set of chains, but not every simple path is "densely
> stretched" on some set of chains. Correct?
Though I think that the definition is clear, I reformulate it for
you: a path P is densely stretched on chains it intersects iff any
set of vertices belonging to the path and a chain simultaneously
forms a clique. Is it clear? Well, here is an example:
7
/|\
/ | \
4 5 6
|\/|\/|
|/\|/\|
1 2 3
Let the chain decomposition be {(1,4),(2,5,7),(3,6)}. Path (cycle)
{2,4,7,6} is *not* densely stretched on it since 2 and 7 are not
joined.
> Then I get down to this: "It is easy to see that a simple undirected
> path of the length L can be densely stretched on not less than
> ceil(L/2)+1 paths of P..." Where are the quantifiers in this
> assertion? Is he making a statement that holds FOR EVERY poset that can
> be generated from a graph G by his procedure, EVERY minimum chain
> decomposition, and EVERY path of length L in G? And what's with the
> "can be" in here?
> To clarify matters, can you explain his assertion with regard to the
> following example? Suppose I take graph G itself to be a simple path of
> length 6. Then I obtain a poset from G as follows. First, I pick every
> other vertex and form one maximal independent set. Then I pick the
> remaining vertices to form a second maximal independent set. This gives
> me a poset with a Hasse diagram like this:
>
> /\/\/
>
> Now the minimum chain decompsition is unique and consists of the three /
> chains. Let's consider the simple path consisting of the entire graph
> G. Now it seems that is is not densely stretched on ANY set of chains,
> because adjacent vertices lie in the same chain. I'm lost...
This question will be forwarded to the author -- I think I
understand what he meant, but it'll be better to have his answer.
Best regards,
Stas Busygin
email: [EMAIL PROTECTED]
WWW: http://www.busygin.dp.ua
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: naval code books were "weighted"
Date: Fri, 13 Oct 2000 00:37:45 GMT
On Thu, 12 Oct 2000 22:29:58 GMT, Albert Yang <[EMAIL PROTECTED]>
wrote, in part:
>Yeah, you mean book+ 100lbs of lead, or do you mean that there is a
>statistical bias that is detectable in the code itself??
Book plus 5 lbs or 10 lbs - or maybe 2 lbs is enough - of lead: just
enough so it will sink.
>I thought all sensitive naval stuff was not weighted, but rather,
>written on water sensitive paper that smeared if it got wet..
That was tried by the Japanese, but it didn't work properly: even in
the cabins of a ship, where no spray hits the codebook, the
environment is very humid. Although others may have had better
success, since I see a post notes that the Germans did this with
keylists: they only had to last for a month (after being taken out of
a sealed envelope), unlike a codebook which often served for several
years.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Bored with AES? SHA-256/384/512 spec now out!
Date: Thu, 12 Oct 2000 17:41:17 -0700
Ian Goldberg wrote:
> Hmmm. It worries me a bit that they define functions R and S, and
> that R is "shift" and S is "rotate". Are these for sure not mixed up?
Chicago used to have 3 phone books, called A, B, C. A was just
the white pages. B and C were the yellow pages, and were confusing
because sometimes you'd look something up in one, and it was
really in the other. To be safe, you had to consult an index
that told you which book to find it. Anyway, they used:
B = consumer Buying guide
C = business & Commercial pages
Hard to see how they could have made it more confusing.
(I heard they eventually switched B and C. Anyone know?)
------------------------------
** 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
******************************
