Cryptography-Digest Digest #500, Volume #12 Mon, 21 Aug 00 20:13:01 EDT
Contents:
Re: What is required of "salt"? ([EMAIL PROTECTED])
Re: New algorithm for the cipher contest ([EMAIL PROTECTED])
Re: My unprovability madness. (JPeschel)
Kryptos and Gillogly (Achilles Outlaw)
Re: 215 Hz five-qubit quantum processor ("Trevor L. Jackson, III")
Re: blowfish problem ("Kelsey Bjarnason")
The DeCSS ruling (Jim Steuert)
Re: What is required of "salt"? (David A. Wagner)
Re: My unprovability madness. ("Douglas A. Gwyn")
Re: Hidden Markov Models on web site! ("Douglas A. Gwyn")
Re: The DeCSS ruling (Mr. Alen I. Koy)
Re: How many bits of strength does the ZIP encryption have? (Christian Ghisler)
Re: How many bits of strength does the ZIP encryption have? (Christian Ghisler)
Re: My unprovability madness. ("Paul Lutus")
Re: How many bits of strength does the ZIP encryption have? ([EMAIL PROTECTED])
Re: What is required of "salt"? (John Savard)
Re: Provable (or probable) primes (Nomen Nescio)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: What is required of "salt"?
Date: Mon, 21 Aug 2000 21:55:43 GMT
In article <[EMAIL PROTECTED]>,
John Myre <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > John Myre <[EMAIL PROTECTED]> wrote:
> > >
> > > I'm wondering what (cryptographic) properties "salt" has to have.
> > >
> <snip>
> >
> > Salts only need to be unique. If you can afford that it's ok.
> > Otherwise just pick a salt at random.
> <snip>
> >
> > It also means that people who use the same password will not have
the
> > same passwd hash unless the salt was the same too.
> <snip>
>
> I think you are agreeing with me on the actual requirements of
> a salt: (mostly) different for each login, to hide collisions
> in passwords.
>
> > So make the salts random that's all.
>
> That's one way. What I'm trying to figure out is if that has
> to be the only way. Different situations would make other
> alternatives attractive. For instance, if the username could
> be taken as the salt, then we don't have to store a salt, we
> don't have to "generate" it, we don't have to communicate it.
> So - is there a reason why that technique is insecure?
Yes. Same name/passwd on a diff machine would have the same hashed
output.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New algorithm for the cipher contest
Date: Mon, 21 Aug 2000 22:05:47 GMT
In article <8ns07a$4ne$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi,
>
> I'm submitting a new algorithm to the cipher contest.
>
> The algorithm main characteristics are:
>
> - Doesn't have a Feistel structure.
>
> - The block encryption function presents only four C commands (four
> rounds).
>
> - Each round uses 3 primitives operators: one multiplication, one
> XOR and one bit-reversal function.
>
> - My old Pentium 166 MHz encrypts 3.06 MBytes/s (54 Cycles/Byte) in
> CBC mode. Since the bottleneck is 64-bit multiplications and bit-
> reversal, I think a 64-bit processor and some assembly can give
> competitive performance.
>
> A simple algorithm like this may be easy to analyze, but I couldn't
> break it yet.
>
> I hope the points above might encourage you to take a look at this
> cipher.
>
> Please download the documentation and source file (19 KB):
> http://www.meubrfree.com.br/~gauss-inf/nimbus/unimbus.cpp
>
> Sorry for my english, my primary language is portuguese.
It looks like you are doing multiplications modulo 2^64, may I suggest
this neato thing called differential cryptanalysis? Since your
multiplication doesn't create a group structure you don't get the nice
decorrelation you would have otherwise. Also there are many weak keys
per round (i.e even keys). Consider any key with the lower 'n' bits
set to zero ... there are sum from i=1 to 63 (2^64) over 2^i, weak
keys... or just over 2^63... Well this is per round. If your cipher
only uses 8 32-bit words as the key, then it's slightly more
I suggest you could make neat differentials such as toggleing the
middle bit which would affect the upper 32 bits in the first round,
then only the lower 32 bits in the next round (with some probability)
etc... this could be made into a four round differential.
I can't think of a specific attack for it yet, but I bet others could :)
Back to the drawing board :)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: My unprovability madness.
Date: 21 Aug 2000 22:23:06 GMT
Future Beacon [EMAIL PROTECTED] writes, in part:
>Dealing with this kind of discourteousness is
>too high a price to pay for your conversation.
Jim,
Maybe it was Bob's signature that you
felt was insulting: the "You can a lead
a horse's..." thing. Everyone Bob replies
to gets stung with it. Don't know if it's
original, but it's clever and kind of funny,
although if the first time you see it is
in reply to your own post, you might feel
a tad insulted.
I didn't understand some math in a post
Bob once made. Asked a math professor friend
of mine about it. As she began explaining
it to me, I mentioned Bob's little stinger.
"That was terrible," she said.
She finished explaining the math, and, after
pausing a moment, said, "About that quote
-- can I use it?"
I told her sure, but RSA may own it.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Achilles Outlaw <[EMAIL PROTECTED]>
Subject: Kryptos and Gillogly
Date: Mon, 21 Aug 2000 22:21:33 GMT
A small diversion concerning posts made about a month or so ago (just
read them now); I've been following this with immense interest:
Jim-- you made mention that part three of the code is a reference to
Howard Carter's discovery of King Tutankhamun's tomb; and it (the
plaintext) ends in the question "Can you see anything?" I should point
out that the plaintext is not a very accurate reproduction of his diary
entry (is there a reason for this?). But in a post you stated that the
answer Carter gave was, "Yes, wonderful things." That's actually not
true-- what he said was, "I replied to him, Yes it is wonderful."
(http://www.ashmol.ox.ac.uk/gri/4sea1not.html, see November 26). I
only mention this in pursuit of a better crib. That response reminded
me of a smiliar statement from the book/film 2010 Odyssey 2, in which
the scientist asks the "ghost" of David Bowman "What's going to
happen?" And the response was, "Something wonderful."
A somewhat loose tangent, but, like I said, all in pursuit of a better
crib...
--
Achilles Outlaw
26 Wedmath 1993
12.19.7.8.13.8.16 Lord O' Night 2 ----> give or take a millenium
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Mon, 21 Aug 2000 18:33:39 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Maynard Handley wrote:
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
> <[EMAIL PROTECTED]> wrote:
>
> >Maynard Handley wrote:
> >> I would contend that what's interesting about Godel is more that certain
> >> things ARE true, but can't be PROVED true. The standard example is always,
> >> of course, Goldbach's conjecture ...
> >
> >Actually I don't think that is a good example, because our intuition
> >is that its proof should be feasible (if it's indeed true). The
> >kind of "unprovable truths" we are sure are Godelian are ones that
> >are carefully engineered to be self-referential in a suitable coding,
> >but they aren't very interesting compared to statements like
> >Goldbach's conjecture. Using Godel incompleteness as a possible
> >reason why we haven't yet proved some possible theorem seems to be
> >a cop-out (a lame excuse).
>
> I think it's a great example because it gets to the root of why this is
> interesting. I mean, let's face it, who apart from five logicians in the
> world gives a damn about the sort of self-referential statements that
> Godel used to prove the theorem? What people actually care about are
> things like Golbach or Riemann zeta function zeroes. We assume that if
> these things are true, we should be able to prove them---Godel tells us
> that is not necessarily the case. Now these may NOT be undecidable---heck,
> one could have included Fermat's theorem in the list a few years ago---but
> what is interesting is that this option of undecidability is a REAL
> possibility.
>
> To put it another way, IMHO this stuff is a whole lot more interesting
> when looked at from the point of view of Chaitin, and something like
> Goldbach's conjecture naturally falls into Chaitin's view point.
It is of more than passing interest to engineers who must deal with self
reference. Ownship is impersonal enough to be safely abstracted. But "me" is a
much harder concept. One that is hard to test for correctness if the fundamental
issue is undecidable.
------------------------------
From: "Kelsey Bjarnason" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Date: Mon, 21 Aug 2000 22:38:05 GMT
[snips]
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I am unaware of *any* C implementation for which sizeof(char)
> is other than 1. Within the context of defining what C is,
> a "byte" is the unit of addressability (as you said) of at
> least 8 bits, and type "char" is required to occupy precisely
> one byte.
"Precisely"? Hmm...
3.4#1
byte: addressable unit of data storage large enough to hold any member
of the basic character set of the execution environment.
3.5#1
character: bit representation that fits in a byte
To me the latter suggests that a C byte could be, say, 17 bits, while the
char is 8; the char does, indeed, fit in the byte... but does not "occupy
precisely one byte" as I would tend to think the phrase implies (i.e. fully
and completely occupies, without wasted space.)
Even later(6.2.6.1#2..4), where object representations are discussed, it
seems to imply that while you can copy objects to unsigned char buffers, and
you can get some sort of result, there is not necessarily a bit-for-bit
equivalence.
So, am I missing something?
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: The DeCSS ruling
Date: Mon, 21 Aug 2000 18:44:00 -0400
Reply-To: Jim, Steuert
I am horrified to learn about the DeCSS
case. The judge has
ruled in favor of the MPAA (Motion Picture
Arts Association) and
enjoined 2600 magazine from publishing the
DeCSS code on it's web
site.
The judge apparently ruled that publishing
keys to a bank
vault, even if the publisher never intended
to rob the bank,
would force the bank to re-program it's
vault. And that
constitues illegal intent.
Where I think the judge is mistaken is his
lack of distinction
between publishing the specific keys to a
specific bank vault, versus
reverse-engineering a publicly visible vault
mechanism (software).
Isn't what is discussed on this newsgroup
equivalent to
"vault mechanisms?". And if so, isn't
publishing an attack on
a commericially used encryption algorithm
(DES certainly)
illegal?
Is anyone in this newgroup concerned about
this ruling?
-Jim Steuert
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: What is required of "salt"?
Date: 21 Aug 2000 16:01:34 -0700
In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]> wrote:
> I'm wondering what (cryptographic) properties "salt" has to have.
If I recall correctly, there is an excellent discussion in
R. Morris, K. Thompson, ``Password security: a case history,''
{\em Communications of the ACM}, vol. 22, no. 11, Nov. 1979.
A simplified answer is that the salt makes dictionary attacks
more costly: it prevents you from re-using off-the-shelf DES
hardware, and it forces you to try each dictionary word separately
for each user, rather than amortizing the cost of a dictionary
attacks across all users.
> Usually I see the assumption that the salt is "random". I
> don't see, however, why this is so. For example, what would
> be wrong with using a simple counter to generate salt values?
> Or, what if the salt were the concatenation of the user name
> and the server name (or address)? Is there a reason to
> change the salt when we change the password?
Using just the username would be bad (someone could build a
password -> encrypted-password codebook for specially targeted
users, e.g., "root"), but username + fully-qualified server name
seems ok as far as I can see. Counter is probably ok as long
as you avoid correlations between servers (e.g., if all servers
started at counter zero, that'd be bad).
However, in general I think the Unix model of storing a hashed
password in a publicly-readable location is a really bad idea
these days. Experience is that many passwords have very low
entropy, so low that no amount of salting can save you.
Passwords are basically an obsolete technology, unsafe at any
speed. I'd recommend that you consider the alternatives to
passwords, and the risks of passwords, very carefully before
deploying any new systems that use passwords for authentication.
------------------------------
Crossposted-To: sci.math,sci.physics
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: My unprovability madness.
Date: Mon, 21 Aug 2000 22:11:13 GMT
Future Beacon wrote:
> If you're interested, the message below was selectively answered to
> make it appear that I disagree with Goedel's theorem.
It does seem from what you just included that you think
there is some way to avoid the existence of undecidability.
Other than the head-in-the-sand approach, how can that be
done?
> I don't agree with you in your assessment of the discourteousness
> involved, but I may have taken it worse than it was intended.
It is all too easy in this medium to lose context and
get confused over attributions. Generally speaking,
postings are likely to be responded to as they stand
without reference to preceding articles in the same thread.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Hidden Markov Models on web site!
Date: Mon, 21 Aug 2000 22:05:11 GMT
John Savard wrote:
> http://home.ecn.ab.ca/~jsavard/co041003.htm
That didn't work, but the following does:
http://home.ecn.ab.ca/~jsavard/crypto/co041003.htm
------------------------------
From: [EMAIL PROTECTED] (Mr. Alen I. Koy)
Subject: Re: The DeCSS ruling
Date: Mon, 21 Aug 2000 23:20:17 GMT
Jim Steuert <[EMAIL PROTECTED]> wrote:
> Is anyone in this newgroup concerned about
>this ruling?
What really burns me is that the court had the nerve to tell web site
operators that they can't even post links to sites that have the code. To
attempt to impose such patently unfair restrictions, favoring big business
over human rights, will only encourage defiance on the Internet.
--
"Mr. Alen I. Koy" is actually 0674 529381 <[EMAIL PROTECTED]>.
01 2345 6 789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: Christian Ghisler <chris@ghisler=remove.com>
Subject: Re: How many bits of strength does the ZIP encryption have?
Date: Tue, 22 Aug 2000 01:29:24 +0200
Reply-To: chris@ghisler=remove.com
On Sat, 19 Aug 2000 23:32:48 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>: What strength (in bits) does the ZIP encryption have, compared e.g.
>: with DES (56 bit) or IDEA (128 bit)? [...]
>
>I'm not sure what units strength is measured in - but I know that
>it's not measured in bits.
Well, of course it's not directly measured in bits, but encryption
strength of one algorithm is often compared to other algorithms and
the number of bits of that algorithm, e.g. a 1xx bit elliptic curve
algorithm is equivalent to a 1yyy bit Diffie-Hellman etc. Therefore I
mentioned 56 bit DES and 128 bit IDEA. The US government seems to
think in bits too. We could also talk about the GFLOPs needed to
break it, but this depends on hardware and implementation.
>You can compare the number of trial encryptions under the assumption that
>brute force is the best attack - but this fails to take into account the
>effort a single decryption takes - and with things like key stretching,
>this may vary significantly.
Yes, therefore the number of floating point operations to try half the
key space would be a measure for the brute force attack strength.
>: ZIP encryption uses three 32 bit keys, so the strengh is probably
>: somewhere between 32 and 96 bit. [...]
>
>The size of the keyspace of the zip algorithm isn't relevant to its
>strength - since the algorithm is rather broken and there's a known
>plaintext attack.
I'm aware of the plain text attack - but this can be avoided by
special means like dual compression without a header on the inner
file. You write that the algorithm is rather broken - do you have any
references (e.g. to papers or other published work) describing the
weaknesses besides the known plaintext attack weakness?
>: I'm not talking about known plain text attacks here, just cryptographic
>: strength with no known plaintext.
>
>You've got to know /something/ about the plaintext in order to be able to
>distinguish a successful decrypt.
Yes, that's true, but knowing only that the contents is plain ASCII is
usually not enough for a known plain text attack (it may be in some
cases).
>The idea that cryptographic strength remains meaningful if you disallow
>the concept of known plaintext seems dubious.
I'm talking about the case where the user is aware of the known
plaintext attack and takes steps to avoid it, e.g. include only a
single file in the zip. The most stupid usage of zip encryption I have
seen was a zip file which contained a readme, and the same readme was
also available separately - unencrypted. Took me less than an hour to
break with a freely available tool...
------------------------------
From: Christian Ghisler <chris@ghisler=remove.com>
Subject: Re: How many bits of strength does the ZIP encryption have?
Date: Tue, 22 Aug 2000 01:29:24 +0200
Reply-To: chris@ghisler=remove.com
On 18 Aug 2000 23:41:21 GMT, [EMAIL PROTECTED] (Bill Unruh) wrote:
[ZIP encryption strength]
>From what I have read here, I suspect the answer is something like 20
>bits. Zip encryption is apparently very easily broken. Do NOT use it for
>anything of any value.
>(I assume I will be corrected if my memory has failed me.)
I have heared that too, but I thought that the main problem were the
known plaintext attacks, especially when encrypting multiple files -
knowing part of one allows to get the password (or better: the 3 keys)
for all others too.
Do you have any reference to the '20 bits'? I made some lit. searches
(iquest) but unfortunately found nothing, but perhaps it was in some
overview paper.
Christian Ghisler
------------------------------
From: "Paul Lutus" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.physics
Subject: Re: My unprovability madness.
Date: Mon, 21 Aug 2000 16:49:39 -0700
> If you're interested, the message below was selectively answered to
> make it appear that I disagree with Goedel's theorem.
>
Simply disagreeing with Gödel's Theorem carries about as much weight as
disagreeing with a woman. You would need to have a technical basis to
disagree with it, something no one else has thought of. Good luck.
> I am
> fed up with all of the dirty tricks and unkindness. I will be more
> careful about accusing anybody, but something has to be done.
Something has to be done? Like E. Robert Tisdale, who just caused sci.astro
to self-destruct by proposing, then publishing, a "blacklist" of posters he
personally didn't think were on topic?
We're better off tolerating the occasional slight. IMHO.
--
Paul Lutus
www.arachnoid.com
Future Beacon <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
<snip>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How many bits of strength does the ZIP encryption have?
Date: Mon, 21 Aug 2000 23:58:37 GMT
Christian Ghisler <chris@ghisler=remove.com> wrote:
> I have heared that too, but I thought that the main problem were the
> known plaintext attacks, especially when encrypting multiple files -
> knowing part of one allows to get the password (or better: the 3 keys)
> for all others too.
> Do you have any reference to the '20 bits'? I made some lit. searches
> (iquest) but unfortunately found nothing, but perhaps it was in some
> overview paper.
The "key" is 8 bits. (The algorithm in its entirety appears on pp
394-5 of Applied Cryptography in the second edition).
Basically, K0, K1, K2 are three 32 bit magic numbers. For every
plaintext byte P you get a plaintext one P by:
C = P ^ K3
K0 = crc32(K0, P1)
K1 = K1 + (K0 * 0x000000ff)
K1 = K1 * 134775813 + 1
K2 = crc32(K2, K1 >> 24)
K3 = ((K2 | 2) * ((K2 | 2) ^ 1)) >> 8
In pkzip 12 random bytes are prepended to the plaintext and the
algorithm is run once, discarding the output to initialize the keys
before encrypting the file.
Apart from the damning plaintext attack, I think the two biggest
problems are:
1. It's easy enough to find a better stream cipher tht this will never
be used anywhere but in pkzip.
2. For end users, it's easier to just encrypt the zip file with a
seperate program than bother trying to cludge around the plaintext
attack with multiple compressions or anything.
If you have some knowm plaintext, and know the contents of the file
are compressed x times, couldn't you simply modify your attack to look
for the plaintext compressed x times? (Assuming you knew the
compression algorithm used.)
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: What is required of "salt"?
Date: Tue, 22 Aug 2000 00:00:38 GMT
On Mon, 21 Aug 2000 11:44:00 -0600, John Myre <[EMAIL PROTECTED]>
wrote, in part:
>The main purpose of salt, as I understand it, is to ensure
>that entries for the same password aren't the same (or rather,
>that the adversary cannot tell that the entries are for the
>same password). Is there more?
Basically, it is meant to hinder precomputation. So if a hacker has a
dictionary of possible passwords, instead of once computing the hash
of each one, he must go through the whole dictionary for every
password file entry he wishes to compromise.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Nomen Nescio <[EMAIL PROTECTED]>
Subject: Re: Provable (or probable) primes
Date: Tue, 22 Aug 2000 02:00:10 +0200 (CEST)
primes
>4294967291
>4294967279
------------------------------
** 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
******************************
