Cryptography-Digest Digest #82, Volume #11 Wed, 9 Feb 00 16:13:02 EST
Contents:
Re: Does hashing an encrypted message increase hash security? (Stefek Zaba)
All Intelligence Systems Behavior Newsletters - A web site .. (Markku J. Saarelainen)
Re: Guaranteed Public Key Exchanges (John Savard)
Re: New standart for encryption software (Eric Lee Green)
Re: new standart for encryption software.. (Eric Lee Green)
Re: Guaranteed Public Key Exchanges (No Brainer)
Re: Compression cannot prevent plaintext recognition (was Re: is signing a
signature with RSA risky?) (Tim Tyler)
Re: permission to do crypto research ([EMAIL PROTECTED])
Re: Latin Squares (was Re: Reversibly combining two bytes?) (zapzing)
Re: Compression cannot prevent plaintext recognition (was Re: is signing (Anton
Stiglic)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Stefek Zaba)
Subject: Re: Does hashing an encrypted message increase hash security?
Date: 9 Feb 2000 19:05:00 GMT
In sci.crypt, Erann Gat ([EMAIL PROTECTED]) wrote:
> Suppse I do the following:
> 1. Generate a 128-bit MD5 hash of a message.
> 2. Generate a second 128-bit MD5 hash of the same message encrypted
> with (say) Blowfish using an N-bit key.
> 3. Concatenate the results together to form a 256-bit hash.
> Does the resulting 256 bit hash have any more security than the
> original 128-bit MD5 hash by itself? How much more?
Well, let's say that by "more security" you mean "harder (still) to find
another message M' such that the hash of M' is the same as the hash of M",
i.e. second pre-image resistance. Yes, it would be harder to find an M'
if the hash is the MD5 of the message concatenated with the MD5 of a
ciphertext of that message. Note that MD5 has not been shown to be weak
against second pre-image finding as such, though there are doubts...
(By "harder" I'm assuming a better-than-brute-force attack against MD5,
i.e. that the would-be forger has knowledge about MD5 which allows an M'
to be computed more efficiently than by trying successive M' candidates.
Clearly if the opponent is using only so simple-minded an attack, you've
not really slowed them down beyond a constant factor, representing the
increased runtime of MD5 + block-cipher + MD5 over bare MD5. Note, though,
that enumeration of messages *may* be a feasible attack w.r.t pre-image
resistance as opposed to 2nd pre-image resistance: if the "message" is
a short password, which you're trying to guess, running through a dictionary
of possible passwords and their systematic variations may well reveal the
password in reasonable time: and here the second hash you suggest adds no
added security.)
However, it's unnecessarily complicated to re-apply MD5 to the whole
ciphertext; you could as simply use the last block or last two blocks of
the ciphertext as a hash with the right sorts of properties; or indeed
- if you're going to run another crypto algorithm - append the SHA-1 of
the message. (I'm skipping over details of preferred hash constructions
based on block ciphers: see section 9.4 of Menezes/van Oorschot/Vanstone's
Handbook of Applied Cryptography, available on-line, for details).
> .................................................... What if
> the Blowfish encryption key is known -- is there still something
> to be gained in terms of hash security by concatenating a hash
> of the cleartext with a hash of the Blowfish ciphertext?
Yes, there's still an infeasible*infeasible instead of only an infeasible
quantity of computation for 2nd pre-image resistance in this case...
Stefek
------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia,soc.culture.russian,soc.culture.israel
Subject: All Intelligence Systems Behavior Newsletters - A web site ..
Date: Wed, 09 Feb 2000 19:58:28 GMT
All Intelligence Systems Behavior Newsletters ...
http://home.earthlink.net/~mjsion/isbn.htm
I'll provide encryption tables and matrixes in the future ....
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Guaranteed Public Key Exchanges
Date: Wed, 09 Feb 2000 13:06:03 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote, in part:
>In article <[EMAIL PROTECTED]>,
> No Brainer <[EMAIL PROTECTED]> wrote:
>> Does anyone know of a secure way to exchange public keys between two
>> people via the Internet (e-mail) without using any other form of
>> communication?
> Public keys are already public. Why is there a
>need to exchange them via mail? Or perhaps you mean exchange a
>private key USING public keys?
Well, isn't there a need to use another means of communication to
exchange key certificates?
i.e. Certicom had to give its original key certificate to Netscape by
some means that excluded a man-in-the-middle.
And people wishing to get key certificates have to prove their
identity to the key certifying authority by some other means than
E-mail.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: New standart for encryption software
Date: Wed, 09 Feb 2000 13:13:00 -0700
finecrypt wrote:
>
> >One reason that PGP is so popular (and so hated by most closed-source
> vendors)
> >is because you can go to http://www.pgpi.com and download the source code,
> >examine it yourself, and verify that if there's a back door in there, it's
> a
> >mighty subtle one.
>
> If you don't compiled your copy of PGP how you can believe that your copy
> downloaded from pgpi.com works as you expected looking in the source code?
Actually, I run Red Hat Linux (or Caldera Linux v2.4 when it comes out), and
the only way to run PGP on my machine is to compile it from the source code.
(Luckily all Linux machines come with a standard compiler).
> Secondly, you cannot check PGP with oficial test vectors, as you can with
Official test vectors merely denote that the implementation matches another
implementation for that particular set of keys and data vectors. This is
important to know for interoperability purposes, but says nothing about the
strength of the key generator, the strength of the encryption protecting the
keyring, and whether or not this program leaves key material living
unprotected in /tmp or /swap or some other place that an attacker could
conceivably get to.
> vectors of authors of algorithms. Third, if you take randomness of
> ciphertext as a very very rough measure of quality of encryption and the
> standart deviation as a rough measure of randomness, you will see that
The desired property is unpredictability, not randomness. That is, the desired
property is that the result of encrypting a given text (without knowledge of
the key) has no statistical correlations with the input -- i.e., you cannot
predict the input, given the output (and vice-versa, for that matter), unless
you happen to have the key. Running statistical tests upon the output of an
encryption algorithm is an interesting exercise, but not indicative of much
else.
Standard deviation is not a rough measure of randomness. Standard deviation is
a rough measure of whether the output is well distributed over the number
field, but that's again not a measure of cryptographic algorithms. It could be
a useful thing to know about a key geneator (key generators, unlike ciphers,
must produce a random distribution, though it must produce an UNPREDICTABLE
random distribution), but that's another issue.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: new standart for encryption software..
Date: Wed, 09 Feb 2000 13:15:39 -0700
finecrypt wrote:
> I agreed with you that you cannot trust program if you don't know how it
> works. But if you test the program with oficial test vectors of authors of
> algorithms and IF ciphertext produced by the program will *exactly matches*
> with test ciphertext, THEN you will know how program works.
Key generator. You keep ignoring those two words. I haven't seen your key
generator.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: No Brainer <[EMAIL PROTECTED]>
Subject: Re: Guaranteed Public Key Exchanges
Date: Thu, 10 Feb 2000 04:15:16 +0800
Darren New wrote:
> No Brainer wrote:
> > secret...however I thought there may be some kind of protocol whereby two
> > people unknown to each other can exchange public keys and retain integrity.
>
> There is. You just don't know *who*! :-) If they're unknown to you, you can
> exchange public keys with them securely, but have no idea what person you're
> exchanging the keys with. Think about it. ;-)
LOL :)
If you're talking about the middle man - yes - you definitely would be able to
exchange keys with him/her securely, however if I wanted to exchange public keys
with YOU, how would you and/or I know that the keys received are the "real" keys
and not just substituted ones (via Mr Middle)?
Based on this, what *are* the _minimum_ requirements for a guaranteed public key
exchange - one that involves the exchanging of public keys between two parties?
I know I certainly don't want to make a telephone call just to verify
everything...especially if they're in a totally different time zone.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression cannot prevent plaintext recognition (was Re: is signing a
signature with RSA risky?)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 9 Feb 2000 20:06:36 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Anton Stiglic <[EMAIL PROTECTED]> wrote:
:> : Tim Tyler wrote:
:> :> Anton Stiglic <[EMAIL PROTECTED]> wrote:
:> :> : Tim Tyler wrote:
:> :> :> A compressor with an accurate model of the data will not just make it more
:> :> :> difficult to detect a correct message from an incorrect one, it can make
:> :> :> it *massively* more difficult.
:> :>
:> :> : Not true at all. If a compressor is used, the attacker will probably have
:> :> : his hands on it, it won't complicate stuff much for him at all!
:> :> : This is what people tend to forget...
: [...]
:> :> Compression *can* make finding halting criteria harder.
:>
:> : No, it does not make it any harder. The attacker just tries to decrypt
:> : to some plaintext p', then decompresses that, call the result p, and
:> : checks if p has the headeras he is looking for.
:>
:> If the compression is correctly and accurately targetted at the datatype
:> it is compressing, there will be zero files which lack the "header" in
:> question.
: Who said that all files are of a single datatype?
Nobody.
: Many, perhaps most encryption systems do not just work on a single datatype.
Whatever the target dataset, there'll be compressors which on average
maximally compress target files. Alternatively there'll be another
"compressor" which results in all cyphertexts occuriing with equal
frequency.
Whether or not it's practical to byuild such an ideal compressor depends
on the set of target messages - for some, it is demonstrably possible.
:> If all files have the header, the compressor can strip it out, and the
:> decompressor can insert it again at the other end.
:>
:> If not all files have the header, it's not going to work very well
:> as a halting criterion.
: On the contrary, the compressor and decompressor have to work for all
: files that *could* be transmitted, whereas the attacker only has to
: implement a halting criterion that works for the particular files
: that *are* transmitted. For example, the attack might be targetted at
: a particular user who only encrypts files of a certain type.
If the actual traffic doesn't reflect what the compressor is tragetted at
then obviously it's not a very ideal compressor for that traffic any more.
: Take email, for example. Here are some characteristics common to my
: outgoing email messages:
: - the headers include information about my mail reader, return address,
: the location of my ISP, my company name, and so on, most of which is
: constant.
: - they are written in English, but with a particular word distribution
: atypical of most English text (e.g. words relating to cryptography
: or computer security occur disproportionately often).
: - most sentences would pass a simple grammar check that doesn't attempt
: to assign any meaning to words.
: - quoting is always done using "> ".
: - there is exactly one space separating a full stop from the next
: sentence.
: - punctuation goes outside rather than inside quotation marks,
: "like this".
: - the lengths at which lines are wrapped are not consistent (as they
: would be with automatic line wrapping).
: - there are often lists like this one in which each item is introduced
: by "-" indented by exactly one space.
: - they have the same plaintext .sig.
: - they are PGP signed with my key.
:
: An attacker can choose *any* characteristic that distinguishes a real
: message from a random output of decompression, and the compression
: algorithm can't possibly remove all of them.
OK this is a domain in which building a good compressor is extremely
difficult.
Note that I don't claim to have a text compressor that works terribly
well on email messages. If you look at what I actualy wrote, it should
be obvious that I never claimed anything remotely like this.
: You can go to as much trouble as you like tailoring the compression
: to particular message types, but if the attacker knows anything at all
: about the distribution of expected messages, he/she can probably find
: a relatively simple distinguishing feature that you missed.
This is certainly not /always/ true. Near-perfect compressors for some
data types can be easily and simply constructed.
If you're still talking about your personal PGP-signed email messages,
attempting to build a "perfect compressor" for this set would probably be
a foolish move anyway - since the decompressor would be likely to need to
contain something that was effectively a representation of your PGP
private key - something you would not want to distribute.
: Partly this is because the redundancy is only clear when looking
: "across" messages, while the compressor can only work on individual
: messages.
Compressors can in principle compensate for messages which have differing
frequencies, to produce "compressed" files which all have the almost
the same frequency. What they need to be able to do this is a source of
good random numbers. If they do this, your objection becomes irrelevant.
:> Much the same is true for any other plaintext characteristic - with good
:> enough compression, *all* possible decrypted files will decompress to
:> plausible-looking plaintext files.
: You're wrong, for three main reasons:
: - the compressor/decompressor has to actually implementable, within the
: current state of the art, and take a reasonable amount of time and memory.
: The problem of creating plausible-looking random messages (which is
: strictly easier than the problem of creating an optimal compressor
: for messages with the same distribution) is not within the current
: state of the art, and has no reasonable prospect of being so short of
: the development of human-level artificial intelligence.
Your objection relates to difficulties in constructing the compressor.
Note that I wrote "with good enough compression" - assuming a-priori
the existence of such a good compressor for the data type.
Consequently, your objection does not relate to my claim.
For /some/ data types, I agree, such a compressor is impractical to build
today. Similarly, for /some/ data types, such a compressor is almost
trivial.
: - even if it could be implemented, it would not be accurate to characterise
: this type of compression as "good", since the compressor and decompressor
: would be large, extremely complex, and slow. At the very least, it would
: have to be programmed with the vocabulary and grammar of every language,
: or the characteristics of every binary format that messages could be
: transmitted in.
"Good" was intended to refer to the quality of output of the compressed
files, in terms of size.
Performance is a secondary consideration to security sometimes.
Note that I've never tied this discussion to text files. Any claim that
*all* high-quality compressors are necessarily large and slow is false.
: - the attacker can spend more effort designing and implementing the
: recogniser than is spent designing and implementing the compression and
: encryption [...]
If the compressor is "sufficiently good" any such effort on his part
is likely to be totally wasted.
:> :> With a good enough compressor a halting criteria - short of testing the
:> :> integrity of the message in the real world - becomes well nigh impossible.
:>
:> : It makes no difference if the compresser is good or not!
:>
:> If the compressor is not good at compressing the data near-maximally,
:> it is very unlikely that all decrypted files will decompress to plausible
:> looking plaintexts.
:>
:> Consequently the analyst might have the possibility of using a halting
:> criterion available to him.
:>
:> With good enough compression, halting criteria can be rendered practically
:> impossible to find.
: No, they can't.
Yes they can.
For some reason, we don't seem to agree :-(
Are you sure you have a good understanding of my position?
I do *not* believe (for example) that anyone can today build a compressor
which is good enough to remove all concievable halting criteria from email
messages.
Please note that my comments were in response to someone who /appears/ to
be under the delusion that compression can't possibly affect an attacker's
ability to find halting criteria, even in principle.
As I mentioned - for some types of traffic - compression can reduce the
cryptanalyst to having to look at the real-world phenomena which
the messages relate to in order to reject keys.
This is something which is likely to slow down his search - and is likely
to provide him with much the same information as breaking the messages
would anyway.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Stop smoking in public places, please.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto,misc.int-property,misc.legal.computing
Subject: Re: permission to do crypto research
Date: Wed, 09 Feb 2000 20:41:34 GMT
In article <87npgt$5pa$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mike Eisler) wrote:
> ... What is to
> prevent one from taking a DVD and copying the encrypted contents onto
> another (writable) DVD? Couldn't one then take that DVD and play it in
> on an "authorized" DVD player? As the judge says, there are lots of
> non-Linux players out there.
Without the "key track" properly written the encrypted contents is
useless. I have read (but verified myself) that DVD-R blank discs have
the "key track" pre-written with zeros or some other content so it isn't
possible to even get a hacked DVD burner to include the needed keys so
that encrypted content can be played.
The other issue is access to even read the protected files. On my Pioneer
DVD-ROM any attempt to read the protected vob files in the Finder result
in access errors. This is exactly as is described in the Mt Fuji
specification documents. I have not seen reference to this by others but
I'm assuming that is because they jst have not tried. The CSS specs
certainly refer to using a shared secret to carry out the authorization
phase before you even get a chance to decrypt.
--
---
Steve Bryan
pgp fingerprint: D758 183C 8B79 B28E 6D4C 2653
E476 82E6 DA7C 9AC5
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Wed, 09 Feb 2000 20:45:31 GMT
In article <87q8f5$qdo$[EMAIL PROTECTED]>,
"r.e.s." <[EMAIL PROTECTED]> wrote:
> "Tony T. Warnock" <[EMAIL PROTECTED]> wrote ...
> : All combiners will have to be Latin squares.
>
> The Latin Square combiners appear to be a subset of all
> possible combiners, corresponding to "balanced" rows &
> columns in the table; so a combiner that's an Lsquare
> might be *better* than one that's not, in some context,
> but not all combiners need be Lsquares, as far as I can
> see in common usage of the term. (But it does seem that
> to be a combiner it must allow for later recovery of the
> message -- resulting in N!^N possible NxN combiners.)
>
> To take the most extreme example:
> If row corresponds to enciphering-symbol and column
> corresponds to message-symbol, then for an alphabet of
> 4 symbols even the square
>
> 0123
> 0123
> 0123
> 0123
>
> yields a combiner -- but not a good one, since a given message
> symbol will result in an output independent of enciphering
> symbol. Whether less-extreme non-balanced (i.e. non-Lsquare)
> combiners are ever desirable -- that would seem to be another
> question.
>
OK, I posted about this before but apparently
I just did not make myself clear, or something,
so I will try again (assuming that the
moderators will be patient with my lack of
communication skills).
You do *not* need a latin square,
because what you refer to as the
encyphering symbol never needs to be
recovered. The only thing you ever really
need to do is recover the message symbol
from the combined symbol.
I will give an example which is hopefully
better explained. Suppose we have two bit bytes,
then coinsider the combining function given
by the table:
m= 0123
----
e=0 3102
e=1 2130
e=2 0231
e=3 1320
Now if you had the encyphering symbol
and the combined symbol then you could
recover the message symbol, but you
could not recover the encyphering symbol
from the combined symbol and the message
symbol, but that's OK, because you never
need to do that anyway.
This sort of combining function would
be much easier to do than making a
latin square, and there are more
possibilities also, so why would you
need a latin square? That was not
a rhetorical question , I really
do want to know why, if you would
be so kind as to clue me in.
Also, If you wanted a combining
function that was more function-like
than table-like, you could use something
like this:
c=(m+e+47)^e
Then you could recover the message symbol
like this:
m=(c^e)-e-47
this would also be reversible for
message symbol recovery but not for
encrypting symbol recovery.
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Compression cannot prevent plaintext recognition (was Re: is signing
Date: Wed, 09 Feb 2000 16:09:44 -0500
Wooo, this is deviating again. Let me make this as simple as possible:
E_k: encryption algorithm using a key k,
D_k: decryption algorithm using a key k,
Z: compression function,
U: uncompression function
m: a plaintext message
So, encrypting m, would be done as follows:
-first compress m,
-then encrypt the result
That gives E_e(Z(m)), where e is the encryption key
Now, if you are testing out a decryption key d, you do
y <- D_d(E_e(Z(m)))
Now, if you have the correct key y=Z(m), so you simply
unzip y , call the result x (x <- U(y)), if you have the right
decrypiton key, x = m. So an attacker will simply look
for the headers in x.
Where does anyone see this as complicating an attackers
job???? Seriously, you can talk about using modes of operations,
or come up with a different ciphertext, but compression doesn't
help to prevent an attacker from finding out if he has the
correct decryption key.
Anton
------------------------------
** 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
******************************
