Cryptography-Digest Digest #839, Volume #10 Wed, 5 Jan 00 00:13:01 EST
Contents:
Re: RSA encrypt ("John Enright")
Re: cracking Triple DES (David Hopwood)
Re: Anonymous Source Problem (Ken Lamquist)
Re: Followup: Help Needed For Science Research Project ("John E. Gwyn")
Re: Questions about message digest functions (Tim Tyler)
Re: Data Encryption in Applet? (Tim Tyler)
Re: PKZIP compression security (Tim Tyler)
Re: Truly random bistream (Tim Tyler)
Re: compression & encryption (Tim Tyler)
Re: "Variable size" hash algorithm? (Tim Tyler)
----------------------------------------------------------------------------
From: "John Enright" <[EMAIL PROTECTED]>
Subject: Re: RSA encrypt
Date: Tue, 4 Jan 2000 18:33:18 -0700
Paul Rubin wrote in message <84u1qs$rdd$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>, Brice <[EMAIL PROTECTED]> wrote:
>>I have a question about RSA.
>>
>>If I was to calculate M^d (M: message, d: secret key) and give it away for
>>the modular step to be done by someone else (say), how easy would it be
for
>>that person to find what my secret key is since my public key is available
>>to anyone ?
>
>Trivial, but why on earth would you want to do that anyway?
>M and d will be about the same size, so if M is 1024 bits (typical),
>then M^d will be about 1 megabit. What type of protocol could that
>be practical in?
Actually, it's a LOT larger than that. If d were only 16 bits, the result
would be about 64 Megabits, or 8 MB without modular reduction. I say
'about' because it depends upon what bits are 'on' in d. Since the secret
key d is typically about the same size as the modulus, there isn't enough
hard drive space in the entire world to hold the resulting number (assuming
the 1024 bit modulus example)! Consider the typical "square and multiply"
method of exponentiation. The result of each squaring operation alone (for
each bit of the exponent) will be double the bit length, or 1 less than
double. So 2^16 * 1024 = 67,108,864 (64 MB, which is 64 * 1024^2). In
other words, double 1024 16 times to get a rough estimate of the end size.
------------------------------
Date: Wed, 05 Jan 2000 01:12:08 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: cracking Triple DES
=====BEGIN PGP SIGNED MESSAGE=====
"John E. Gwyn" wrote:
>
> DJohn37050 wrote:
> > Attack in the middle. Attack one pair of keys with 2**112 and the
> > other with 2**56 and look for matches.
>
> Easier said than done. How are you going to implement "look for
> matches"? Store 2^56 blocks of on the order of 64 bits each, or
> set up a hash table that big?
He didn't say it was practical (clearly, an attack with work factor
more than 2^112 is not practical regardless of the memory requirements).
Combining Stefan Lucks' attack, which I gave a reference to in another
article, with van Oorschot and Wiener's work on parallel collision search,
might give some improvement (still not enough for a practical attack).
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOHKaXjkCAxeYt5gVAQE+Cwf/bkNvm5rGKeHB58YX0JJM78tySuamF83b
aXhUMH6JqNFFUNBmd6njM0LSk3ecM6LUiRP9lbspLQQguragLO9nrUJpXbEOQNG8
6VvI7TXgeTQCVThcJzF1F++ngSvO42zCfh+IBFAb2dAL62jHAa6rAqkDYwCn86av
RgeEIiv47f+sQpVIzeo0PAavV81f5bYAqZfd/9S59IpjaXUxoRA83iXmhmTmS/0l
N5aX5E2n/EEFaQoPpHFHxUt2ZzQcY7qNJ4Y5fNi+npSTqX/L9LMdGNX/XLdWUFP4
n5GEI2+CvgGhpdy0/1eFCIkHKzZOLMXNB9GLdAvAtRM36mmMSsTXXQ==
=M9fK
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Ken Lamquist)
Subject: Re: Anonymous Source Problem
Date: 5 Jan 2000 02:21:50 GMT
"Hans" <[EMAIL PROTECTED]> wrote:
> Peggy has some information she wants to send Victor, who is
> a reporter for a newspaper. Peggy wants to remain anonymous.
> Since Victor is able to verify the information Peggy provided,
> he now trusts her even though he doesn't know her true identity.
[big snip]
> Everyone (Peggy, Victor, and Carol) has an ID certificate with their true
> identities which is signed by Trent, a CA trusted by everyone. The ID
> certificate has a unique value which identifies the individual. So, Peggy
> asks Victor for his certificate, and checks it with Trents verifiying
> signature.
>
> The problem is- how Peggy prove her (anonymous) identity to Victor?
Peggy creates a public/private key pair for use when communicating
with Victor. She signs all the messages to Victor with the private
key, and mails Victor the public key. Victor can then verify that all
messages from Peggy came from the same person.
Alternatively, Peggy can send Victor a private key in her first message
to him, and Peggy and Victor can use this private key to encrypt all
subsequent communications.
A third approach is for Peggy to inform Victor in her first message
that she will add a specific tag phrase to the end of her subsequent
messages.
> I'm hoping there is a way of Peggy can create a new 'anonymous' certificate
> based on Peggy's and Victor's (or Carol's) certificate. My thinking is
> this- Since Victor must be sure this new certificate could only come from
> his anonymous person (Peggy), it must be based on Peggy's certificate
> (without revealing her true identity).
A certificate is a signed statement asserting that a particular public
key corresponds to a private key known to a specified person. Since
Peggy doesn't want to prove (or even reveal) her true identity to
Victor, she doesn't use a certificate.
Kenneth Almquist
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Followup: Help Needed For Science Research Project
Date: Tue, 04 Jan 2000 21:44:33 -0600
segals-2 wrote:
> Encrypt text using RC4 (and possibly other symmetric algorithms as
> well) and then find the probability of finding a particular
> character in the encrypted message. Basicly, count the total
> number of characters and the total of number of each character. I
> believe that the probability in this particular case would be 1/255
> (i think that's the one). If a higher probability occurred for some
> characters, or lower for others, it could be concluded that RC4 did
> not completely turn the text message into "random garbage". ... I am
> hoping to determine whether or not RC4 is as dependable as is
> believed.
To be scientific, you should be testing some hypothesis and the
hypothesis must be testable, i.e., an experiment should produce
data that bears directly on the validity of the hypothesis. A
suitable hypothesis in this case might be "RC4-encrypted data
has the same first-order statistical distribution as uniformly
randomly generated bits." You'll need to read up on some basic
statistics in order to appreciate the following: It would be
*most unusual* for RC4 output to have *exactly* uniform flat
distribution, even if the hypothesis were true. (Most modern
ciphers actually work on bits, not "characters"; if you chunk
the output into 8-bit "characters", your tests lose some of
their power to test the hypothesis.) This is due to the
*expected* variation among samples resulting from a truly
random process. What you need to discover (it will be in any
good introductory statistics book) is a mathematical measure
of the discrepancy between the output of a hypothetical model
and the actual observed data; Pearson's "chi-square" test is
the usual one, but there are others. One can relate the
outcome of the chi-square test (both the chi-square statistic
and the number of "degrees of freedom") to the likelihood of
seeing at least as much variation in the actual data if the
hypothesis is true. This may seem like a fuzzy, indirect way
of stating the outcome, but that is inherent in measuring any
form of "randomness"; even a perfectly random process *could*
produce a highly patterned output like 11111111111111111111
every so often (the pattern I just gave occurs about once in
every million samples of 20 random bits), so one cannot state
that the system definitely is or is not truly random based on
a finite amount of observation of its output.
If you are able to understand, use, and explain information
like the above, it should make for a good science-fair project.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Reply-To: [EMAIL PROTECTED]
Date: Wed, 5 Jan 2000 03:20:40 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
[snip not-very-one-way hash functions from block cyphers]
:> When applied to a single block, this *retains* the
:> bijective nature of the block cypher. This
:> is, in fact, a useful thing for it to do.
: Why? Just because there are no collisions between
: messages of a specific length, doesn't mean that it is
: difficult to find collisions between messages of that
: length and a different length.
Indeed. Making it difficult to locate two messages which hash to the
same value, and reducing the frequency of hash collisions of message
pairs chosen at random are different properties a hash can have.
By arguing that the latter is useful, I don't mean to say that the
former should necessarily be completely neglected.
When "hash size" = "message size", a bijection is /clearly/ useful, as it
increases the difficulty of finding two messages that hash to the same
value to an infinite figure.
: I can't think of many applications where this limited form of
: collision-freedom would gain you anything.
Hashing small messages is one such application. Hash collisions may
occur and be located if the hash function sumulates a pseudo-random
function. This is one sensible and practical reason why a hash function
should /not/ simulate a pseudo random function.
:> > A hash function should be indistinguishble from
:> > a random function, not random permutation.
:>
:> No. You are mistaken.
:>
:> No hash function should *ever* be indistinguashable from a random
:> function.
:>
:> If it /does/ have the characteristics of a random
:> function, this means hash collisions are more likely
:> to occur - and consequently easier to find - than
:> they could be.
:>
:> The whole point of hashing is to make finding hash
:> collisions as difficult as possible.
: No it isn't. "lordcow77" is perfectly correct; a hash should
: approximate a PRF (Psuedo Random Function).
No. Hashes which do this exhibit a greater frequency of hash collisions
than is possible. Preventing hash collions is not always the *only*
point of using a hash - I overstated this - but it is often an important
one.
For most applications of a hash, reducing collision frequencies below
the level which would be offered by a pseudo-random function seems to
be both possible and desirable.
If you have some reasoning behind the statement that a hash should
approximate a PRF, by all means present it. I have already explained why
I think this is disadvantageous property for a hash to have.
: Also, there are other desirable properties of a hash than collision
: resistance [...]
Yes, I will grant this. Many types of hash functions should be "one way",
for example.
: If for some application we needed a function that, when applied
: to fixed-length inputs, *cannot* result in collisions, we should
: use a PRP, not a hash.
PRPs are not always appropriate. Imagine the messages are typically 10%
larger than the hash. In this case a PRP is impossible. Yet using a hash
function which simulates a PRF clearly has unnecessarily poor
hash-collision properties. The solution should be obvious.
:> Can you remember how you arrived at the mistaken
:> idea that hashes should simulate random functions?
:>
:> Has anyone else apart from you ever claimed this?
: See, for example: [snip reference]
It seems at least that the notion that hash functions should simulate
random functions is not confined to a few individuals.
However, what are the advantages of allowing such an unnecessarily high
frequency of hash collisions? The disadvantages should be obvious enough
- for example, in some cases it will make finding hash collisions
"infinitely" easier.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
X <-- Press here to reveal you're an idiot.
------------------------------
Crossposted-To: comp.lang.java.security
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Data Encryption in Applet?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 5 Jan 2000 03:32:45 GMT
In sci.crypt David Hopwood <[EMAIL PROTECTED]> wrote:
: "Law Wun Suen, Brian" wrote:
:> Tim Wood wrote:
:> > [from] message <[EMAIL PROTECTED]>...
:> > >I am looking for a way to encrypt data through an applet using symmetric
:> > >(or asymmetric) encryption. I thought of sending an applet containing a
:> > >symmetric key to a client.
:> >
:> > How? [...]
:>
:> I think if the application have to consider about the performance, better
:> to use both (symmetric and asymmetric) encryption together. It really look
:> like how the SSL work. You generate a random key (secret key) for the
:> symmetric encryption and encrypt this securet key with your own private
:> key. The client program receive the key and decrypt it by the public key.
:> Then use that secret key for that sesssion communication.
: This is no more secure than sending the applet containing a symmetric key.
I think some public/private confusion may perhaps have taken place
in the explanation being replied to.
In a more conventional scenario, the key to be used with the symmetric
algorithm is generated by the applet (from, say mouse movements and
keypresses), and is then sent to the server under encryption by the
server's public key.
Such a scheme is likely to be more secure than sending a key used for
symmetric encryption along with the applet - though there are the usual
problems you mention in authenticating the public key on the server.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
.ARC: what the .ZOO animals travelled in.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: PKZIP compression security
Reply-To: [EMAIL PROTECTED]
Date: Wed, 5 Jan 2000 03:47:27 GMT
Johnny Bravo <[EMAIL PROTECTED]> wrote:
: On 27 Dec 1999 19:34:51 GMT, [EMAIL PROTECTED] (BigJim44) wrote:
:>I know it's not exactly PGP but would zipping a text file with PKZIP before
:>encipherment significantly increase the security of the link?
: It is only useful for decreasing bandwidth since the first few known
: bytes in standard headers will not affect the security of modern
: ciphers as they are designed to withstand plaintext attack of the
: entire file, much less a few bytes.
Hmm. Two troll-like posts in a row ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
.44 Magnum: The ultimate point-and-click user interface.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Truly random bistream
Reply-To: [EMAIL PROTECTED]
Date: Wed, 5 Jan 2000 03:52:54 GMT
Nigel Fitchard <[EMAIL PROTECTED]> wrote:
: I would like to get hold of a truly random bitstream - about 2^24 bits long
: should be plenty. Does anyone know if such a thing exists for download ?
No such thing is known to exist anywhere on the planet.
If anyone were ever foolish enough to puport to offer such a service,
it would not be possible to verify whether their material was genuine.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
0.666 - number of the millibeast.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Reply-To: [EMAIL PROTECTED]
Date: Wed, 5 Jan 2000 04:15:21 GMT
Kenneth Almquist <[EMAIL PROTECTED]> wrote:
: Compressing using a nonbijective algorithm and then encrypting twice
: may be faster than compressing using a bijective algorithm and then
: compressing once.
Multiple encryption with independent algorithms and bijective compression
produce different types of security benefit. With Moore's law demolishing
any performance reasons for using labour-intensive encryption, there are
good reasons for using both multiple-encryption and compression.
: That is because some of the compression algorithms
: which provide the best combination of speed and compression ratio
: (such as the one used by gzip) are not bijective.
Bijective compression has only just been invented. The current situation
/should/ eventually reverse - since making a compression system bijective
demonstrably makes optimal use of the range of the compressor.
: I believe that except in special circumstances, it is a mistake to
: assume that an opponent will not be able to mount a known plaintext
: attack. [...]
Well yes - when analysing security, consider worst-case scenarios.
: For this reason, I believe that the apparent improvement
: in security offered by bijective compression is an illusion.
There is no sign of logical argument, though. Compression reduces the
effectiveness of partial known plaintexts. It makes little difference to
*complete* known plaintexts. However, the former are very common.
Defending against them is likely to be genuinely worthwhile, if you do not
know for certain what attackers can do with any known plaintext you give
them.
: If your encryption is strong enough to resist a known plaintext attack,
: then it doesn't matter if your compression algorithm is bijective or
: not. [...]
This is known for approximately zero cypher systems, though :-(
: If your encryption algorithm is vulnerable to a known plaintext
: attack, then the chances are that a determined attacker will obtain
: a known plaintext an break your cipher, so it is not likely to matter
: whether you use bijective encryption.
A known plaintext breaks a message key, not a cypher. If the attacker
faces a subsequent message, with a partial known plaintext, certain
types of compression can make a *big* difference to the attacker's ability
to exploit this.
: Sure, it's *possible* for bijective compression to stop an attack on
: a cryptosystem, just as it's possible that prefixing the encrypted text
: with an obscene message will stop an attacker with delicate sensibilities.
: My point is that "possible" is not the same as "probable."
Unfortunately, you present no clear argument about the relative costs.
Yes, you should consider the expenditure on relevant components of your
system before deploying it. Compression is a good idea before
encryption for so many reasons, that it is quite likely you will be
employing it in some form anyway - the bijective compression enthusiasts
ask only that it be done properly.
: Designers of cryptographic systems do better to concentrate their
: efforts on other approaches.
Designers of cryptosystems designed to ensure privacy of mail messages
should cover all possible approactes to the best of thair ability.
Neglecting something as fundamental as depriving cryptanalysts of their
raw material in the form of regularities in the plaintext by using
good compression would probably be verging on the severely negligent.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
I'm telling you, they are EVERYWHERE.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: "Variable size" hash algorithm?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 5 Jan 2000 04:18:24 GMT
Peter K. Boucher <[EMAIL PROTECTED]> wrote:
: Why not have your program measure the entropy of the input [...]
Hmm, this first stage looks like it might be a little bit tricky to perform.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
You have been selected for a secret mission.
------------------------------
** 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
******************************
