Cryptography-Digest Digest #886, Volume #10 Tue, 11 Jan 00 19:13:01 EST
Contents:
Re: Questions about message digest functions (Tim Tyler)
About DES algorithm. (Katsamakas Kostas)
Re: Questions about message digest functions (David A Molnar)
Re: "1:1 adaptive huffman compression" doesn't work (Mok-Kong Shen)
Re: About DES algorithm. (Anton Stiglic)
Re: Simple Encryption ... (Anton Stiglic)
Re: My background - Markku Juhani Saarelainen ("modokon")
Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?) (Nemo Outis)
Re: Questions about message digest functions (David Wagner)
Re: Simple Encryption ... (David Wagner)
Re: Questions about message digest functions (Tim Tyler)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Reply-To: [EMAIL PROTECTED]
Date: Tue, 11 Jan 2000 21:34:55 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler wrote:
:> [EMAIL PROTECTED] wrote:
:> : Tim Tyler wrote:
[a hash should approximate a pseudo-random function?]
:> :> I don't care *how* "simple" and "widely accepted"
:> :> it is - it's dead wrong.
:>
:> : The wide-acceptors have a reason: we can't find
:> : functions better than random.
:>
:> That's not entirely true. I could present one without
:> much difficulty.
: The one you suggest, quoted below, is a spectacular failure.
Hmm. My demonstration appears to be failing to convince for the lack
of a one-way permutation that is as hard to break as an orthodox hash :-(
:> Recall that I calim that each hash value should occur
:> with as near-equal frequency as possible given the
:> target distribution of message files to be hashed.
:>
:> A classical pseudo-random function would produce something
:> more like a bell-shaped distribution.
: First, to be have any meaning at all you have to
: say what random variable you think to have a
: bell-shaped distribution. [...]
Domain: possible hash values corresponding to plausible messages;
Range: the frequency of the occurrences of each hash value.
: Second for the meaningful statistics that we could use, it's the
: variance that indicates how nearly-equally frequent the digest
: are, not the shape.
I generally agree. However, a near flat distribution is always
the ideal, and a bell-shaped distribution almost always fails to
be as good, pretty much regardless of the variance.
:> : The improvement against brute force is entirely trivial, and seems
:> : to come at a terrible cost.
:>
:> Hang on. There *is* no "terrible cost".
: Your suggestion below requires memory for 2^160
: digests. There isn't that much memory yet made [...]
Well, that's if the hash we are comparing with happens to have the
same sized output as SHA1.
I am not convinced that there is a terrible cost.
You may well be right that such functions are not currently known.
I am not a good enough mathematician to comment at this stage on
the issue.
However I have seen no sign of an argument that such functions will remain
forever unknown - and I see no reason not to consider that today's hashes
demonstrably fail to provide best possible resistance against brute force.
These comments about difficulties in locating a suitable function only
apply to one-way hash functions. Hash functions that face blind forces
rather than active attackers may conform to the distribution I have
described without such theoretical problems. This alone makes
the distribution I'm describing of some interest to hash builders.
:> Personally I doubt that building a one-way hash function with the
:> characteristics I believe are desirable would be /that/ difficult.
:> All that would probably be required is some clear thinking on the
:> matter.
: So did you do any clear thinking about it? How did it turn out?
As a result of your post here, I /consider/ it possible the difficulties
in constructing such a secure hash may be larger than I had anticipated.
However, I currently see no good reason to think that the difficulties
may not be overcome.
[snip properties of hash functions]
:> : There's another property generally required of
:> : hash functions: a hash should be "preimage
:> : resistant", that is one-way.
:>
:> Firstly, not all hashes need to be one way.
: The _only_ example you described where your hash
: has a perceptible advantage is one where the
: digest space is at lease as large as the message
: space, and you only need collision resistance.
: That's a nonsense example because it doesn't call
: for any hash at all - just use the message.
Arrgh. No. Hashes where the digest space is somewhat larger
than the message also clearly suffer from the same problems.
Under such circumstances "just using the message" is not
practical.
Obviously "just using the message" is not a one-way hash.
Because I (correctly) state that not all hashes need to be one
way, does not mean my previous examples are nonsense.
To reiterate: in my previous examples collision resistance
was *not* the only design criteria. The hash functions I've
been thinking about typically also need to be one-way.
*If* no one-way hash functions with this property can be found,
then to my mind it will mean that practical hashes fail to approach
the ideal distribution of hashes. It will not mean that the ideal
needs to be modified to reflect the short-comings of today's hashes.
:> : Even for modest length messages, just
:> : a few bytes longer than the digest, random
:> : functions will map preimages to digest so evenly
:> : that the expected time for brute-force search will
:> : differ by an tiny fraction of a percent,
:> : compared to a hash that maps exactly the same
:> : number of preimages to each digest. [...]
:>
:> That's probably fair enough. My objections are only really
:> very significant when the size of the message is small.
: I suggest you find out why hashes are used. Your
: example is of no significance.
Surely this is not correct!
One purpose of hashes is signing messages. Another purpose of hashes is
condensing the entropy in a large file into a single, usually smaller,
large-entropy file of a given size. My objections bear on both these
cases. Resistance to brute-force attacks in these cases is not "of no
significance", IMHO.
:> When the messages to be hashes are much longer than the hash, the
:> hashes will still follow a bell-shaped curve, rather than being a
:> near-flat distribution.
: You lost me. You say the distribution function is
: bell-shaped for a random function, and flat for a
: function in which each digest has the same number
: of preimages? What random variable are talking
: about?
I've varied this reply rather than repeat it verbatim:
Domain: all possible hash values;
Range: the frequency of the occurrences of each hash value.
:> : But here's the problem - how do you create this
:> : pseudo-random permutation so that's it's as strong
:> : as pseudo-random-function hashes such as SHA-1?
:> : Can you describe a permutation on 160-bit vectors
:> : (or even an almost-permutation) that is easy to
:> : compute but takes anywhere near 2^160 steps to
:> : invert?
:>
:> You could use one /very/ big table representing
:> the random permutation. 2^160 is big, but not so
:> big that it's totally unmanagable.
: Look, I agree lordcow was overly rude to you in
: his initial post here, but if you're going to
: write stuff like that, what do you expect?
<fx: giggles>
A SHA1-sized hash with an ideal distribution is out of the grasp of
us mere mortals, until we can simulate it with some clever maths, then.
:> : There is no point to optimizing against brute force search.
:>
:> Huh? This doesn't seem to logically follow.
: Then go build your 2^160 entry table and enjoy
: your negligible advantage against exhaustive
: search.
The advantage is *not* negligible in some cases.
Recall that using the ideal distribution, rather than a PRF makes
finding hash collision *infinitely* more likely under some circumstances
:-(((
: There's some interesting insight to be gained by
: comparing how one might build a one-way
: permutation versus a one-way function.
What I'm /really/ after is more sophisticated than a one-way permutation.
A one-way permutation is under discussion as a possible proof of the
idea that a hash that does better than a random function exists.
So far, I'd agree that no such one-way permutation has been described
in this thread.
: But if you have no handle on what can be done and what can't,
: then all such insight is lost.
I don't know of an implementation - and I'm no longer certain it can be
done at all easily - as the discussion here has revealed.
I still don't think any of your objections relate to what should be
considered to be an ideal hash, though.
It is facinating that there may be engineering difficulties that
may make attaining such a hash difficult in practice. To my mind
it remains to be seen if these difficulties can be overcome.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
All complex things start life being simple.
------------------------------
From: Katsamakas Kostas <[EMAIL PROTECTED]>
Subject: About DES algorithm.
Date: Tue, 11 Jan 2000 23:50:42 +0200
Reply-To: [EMAIL PROTECTED]
��� I know that unix systems use the crypt function to encrypt a
password.
According to the man page, this function uses a variation of the DES
algorithm
using two extra characters as salt.
Where can i find the description of the algorithm the crypt function
uses, so i could implement it?
I would like also the DES algorithm.I have searched, but i have found
general descriptions of it.
Thank you in advance.
�
�
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Date: 11 Jan 2000 21:55:03 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> : Think about what happens if e and phi(n) are not relatively prime.
> This doesn't produce any noticable effect at this point - it seems that
> they would be, by design.
An example of "RSA with e and phi(n) not relatively prime" is the Rabin
function. For message m, the ciphertext c = m^2 mod n. Since phi(n) =
(p-1)(q-1) for n = pq, 2 is a factor of phi(n) and hence 2 and
phi(n) are not relatively prime. This is not a bijection, since there are
two square roots for each encrypted value c, and so the function is not
1-1.
Still, Rabin is certainly a trapdoor function, with the trapdoor
being the knowledge of the factors of n. Taking square roots mod n allows
you to factor n, so in some sense, "breaking Rabin" is equivalent to
factoring n. So as far as we know it is one-way for polynomial-time
bounded adversaries.
> Currently I can't imagine how the construction from the asymmetric cypher
> to the bijective one-way function could fail - though I'm happy to agree
> that an individual with no knowledge of the (discarded) private key
> has no way to easily verify that the structure is performing as it
> should be.
That much is true. If you are willing to do a little bit of work before
discarding the private key, however, you might produce a non-interactive
zero-knowledge proof that the public key is correctly formed and so the
function is bijective. Then even after the private key is discarded,
the proof could be used to convince everyone that the function really
is bijective.
AFAIK the most work for proofs of this kind has been done for showing RSA
keys are well-formed. Bob Silverman and Moses Liskov have a paper on the
subject; I think there were also papers in Eurocrypt '99 and ACM's CCS
1998 conference.
uh, but maybe a simpler way would be just to use g^x mod p, with p = 2q+1.
Then everyone can verify that x != 2 and x != q by trying them, and can
verify the primality of p. Then x is relatively prime to p-1 and so
g^x mod p is a bijection.
does that work for you?
Thanks,
-David Molnar
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Date: Tue, 11 Jan 2000 23:53:45 +0100
John Savard wrote:
>
> I can achieve that if I don't have to go to byte boundaries. I can
> achieve that if I'm allowed to use random padding with a length
> indicator. But trying to do it David Scott's way, that condition can
> no longer be achieved (well, I can always XOR my last byte with a
> checksum of the rest of the message to at least mask the bias...).
I am not quite sure whether one couldn't even attempt to 'define'
the 1-1 problem away with a 'convention'. That is, if on compression
the last code symbol does not fill to a byte boundary, then the
software has to do filling with bits that do not form a valid code
symbol and it is 'required' by convention that the filling is
to be random, say dependent on the system clock. Now if one
compresses one and the same file twice, the results are identical
with the exception of the filling bits. This way I suppose the
original argument for 1-1 in the case of the analyst using wrong
keys to decrpyt (i.e. the argument of thereby leaking some information
to him because of non-1-1) no longer applies. Certainly I admit
that what I described is a 'trick', but it works for the purpose at
hand, doesn't it? Or there could be technical problems of realizing
that 'convention' that I haven't yet seen? Thanks.
M. K. Shen
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: About DES algorithm.
Date: Tue, 11 Jan 2000 17:55:53 -0500
Katsamakas Kostas wrote:
> [...] I would like also the DES algorithm.I have searched, but i have
> found
> general descriptions of it.
>
> Thank you in advance.
>
>
For a description of DES, see FIPS publication 46-1 (or higher,
I forgot):
Data Encryption Standard.
You can get it on the web...
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Simple Encryption ...
Date: Tue, 11 Jan 2000 18:13:31 -0500
> What kind of situations could your first scenario
> apply to?
There are plenty of situations, here is a simple example:
graph isomorphism, Peggie wants to proove to Vicky
that the she knows the isomorphism of two graphs, G0 and
G1, without giving away the isomorphism (in your scenario,
Peggie would be one of the two people disputing, and
Vicky would be anybody else).
Now, to do this, Peggie picks a permutation W of
Gb (b = 0 or 1, she can chooose it randomly) and
computes the graph G = W(Gb), then gives G to
Vicky. Vicky then picks a random b' (b' = 0 or 1), and
asks Peggie to show her the isomorphism between
G and Gb'. If Peggie knowns the isomorphism between
G0 and G1, she won't have any problem answering,
no matter what G she picked and no matter what b'
Vicky picked. If Peggie doesn't know the isomorphism
between G0 and G1, and if Vicky picked b' != b, Vicky
is in trouble and she won't be able to answer (the
chances of this happening is 1/2).
So if Vicky is a layer, she'll get caught 1 times out of
2. You just repeat the protocol as many times as
it takes to convince Vicky, after k iterations, if
Peggie always answered correctly, Vicky can be
sure that Peggie knows the answer with prob.
at least of error < 1 - 1/2^k.
Vicky never learns anything about the isomorphism
of G0 and G1 (because at each iteration, she only
get's the iso of a newly choosen G with G0 or G1,
is she would have gotten both the iso between G and
G0 and the one between G and G1, then she could
have easily computed the iso between G0 and G1.
There is also ZK proofs that allow you to proove to
people that you know p and q such that n = pq, for
a given n, without revealing info about p or q, and
all sorts of other tricks.
If you want to know more, pick up a book like Stinson's
"Cryptography Theory and Practice" for an inroduction
to ZK proofs...
Anton
------------------------------
From: "modokon" <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia
Subject: Re: My background - Markku Juhani Saarelainen
Date: Tue, 11 Jan 2000 23:19:52 -0000
and?
Markku J. Saarelainen <[EMAIL PROTECTED]> wrote in message
news:857n5f$n3a$[EMAIL PROTECTED]...
> 1. Born in 1967 in Varkaus, Finland
>
> 2. Educated in Finland, U.S.A. and the USSR
>
> 3. Political beliefs: no political beliefs
>
> 4. Major Achievements:
>
> a. Successfully assisted and facilitated Al Gore's and Bill Clinton's
> re-election in 1996 on the Internet with several thousand people - did
> not get compensated for this.
>
> b. Enabled ISO people to understand specific requirements, intelligence
> and encryption
>
> c. motivated millions to make Yeltsin to resign
>
> d. helped thousands of people around the world to understand how to
> influence political (Presidential and Congress) elections in the U.S.A.
> on the Internet
>
> e. was able to make the encryption policy to fall
>
> 5. My religion: Judaism
>
> 6. My hobbies: intelligence and encryption
>
> 7. My business: intelligence and encryption
>
> 8. Citizenship: Finland and European Union
>
> 9. Shall leave the United States of America shortly
>
> 10. Believes strong family values and trust between spouses. Found
> America not to be trusted.
>
> 11. Work behavior: 24 hours / 7 days a week
>
> 12. The best invention: Genie Services
>
> 13. Dislikes CIA agents who broke the Golden Rule
>
> 14. Recent letters:
>
> Presidents: Finland, EU, Russia and USA
> Several embassies and consulates around the world
>
> 15. Nick Names known by the Kremlin: The Dark Lady and The White Wolf
>
> 16. The biggest mistake: coming to the United States of America
>
> 17. Current financial situation: No address and living in the car
>
> 18. Some main experiences: CIA's and NSA's counterintelligence messed
> up my life in the USA without any reason
>
> 19. The best experience: Having my first fish in the private island in
> Finland, when I was six years old.
>
> 20. The most important wish: To leave the USA for better life
>
> 21. In 1987 and 1989 met several KGB agents
>
> 22. The estimated date of death: Still unknown xx/xx/20xx
>
>
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Nemo Outis)
Subject: Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?)
Date: Tue, 11 Jan 2000 23:40:06 GMT
Another one that drives AI programs wild is: "I took the bishop to a chess
match."
Regards,
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>Guy Macon wrote:
>
>> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> (Tony T. Warnock) wrote:
>>
>> >"unionize" is fun to give to automatic hyphenation routines.
>>
>> Here are two sentences to give to automatic language translators:
>>
>> Time flies like an arrow.
>>
>> Fruit flies like an orange.
>
>"The spirit is willing but the flesh is weak."
>
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Questions about message digest functions
Date: 11 Jan 2000 15:39:36 -0800
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
> However, a near flat distribution is always the ideal, [...]
Why? It is widely accepted by most theoretical cryptographers that
a random function is the ideal, for many purposes. That doesn't mean
they are necessarily right -- noone is infallible -- but they've put
forward some pretty compelling arguments to support this contention.
This means that, if you want to say the conventional approach is wrong,
you ought to have some pretty good evidence for why your favorite
definition is to be preferred over the conventional approach. So far,
I haven't seen you make any such reasoned arguments.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Simple Encryption ...
Date: 11 Jan 2000 15:41:44 -0800
In article <[EMAIL PROTECTED]>, Anton Stiglic <[EMAIL PROTECTED]> wrote:
> > What kind of situations could your first scenario
> > apply to?
>
> There are plenty of situations, here is a simple example:
> graph isomorphism,
Sure, that's a perfectly fine situation,
but it's not what the original post asked for,
if I read it correctly.
I'll repeat that, if I understood correctly,
the primitive the poster was asking for is
known as `bit commitment'. Zero-knowledge
proofs are a fine way to build a bit commitment
scheme, but they're hardly the only way.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Reply-To: [EMAIL PROTECTED]
Date: Tue, 11 Jan 2000 23:19:50 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler I wrote:
:> [is building a secure, one-way pseudo-random permutation possible?]
:> ``It is possible to use a public-key encryption algorithm in a block
:> chaining mode as a one-way hash function. If you then throw away
:> the private key, breaking the hash would be as difficult as reading the
:> message without the private key.''
: Now look at how the time to break it compares with hashes based on PRF's.
As I understand it, usually the work required to break the construction
depends on how large the original primes are - rather than on the size
of the hash (provided the latter is not too large for the generating
primes in question).
Also note that the construction may be repeated a number of times, using
multiple keys and multiple private primes.
To clarify, is it your objection that it's too labor intensive to find
primes that are sufficiently large, and to apply such operations in series
enough times to the point where the level of security offered
roughly equals that of an ordinary hash?
Such a construction may be very slow - and difficult for a user to verify
it is operating as claimed - but I'm not sure it is necessarily weak.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
I will never lie to you.
------------------------------
** 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
******************************
