Cryptography-Digest Digest #86, Volume #12 Thu, 22 Jun 00 13:13:00 EDT
Contents:
Re: Try it. (Mark Wooding)
Re: DH - Man In The Middle (Doug Stell)
Re: Missing Info in the crypto-gram of MR BS (SCOTT19U.ZIP_GUY)
Re: Quick Question on Primitive Elements GF(p) (Simon Johnson)
Re: Try it. (None)
Re: How encryption works (Simon Johnson)
Re: MD5 Expansion (Simon Johnson)
Re: MD5 Expansion (Simon Johnson)
Re: Try it. (None)
Re: Quick Question on Primitive Elements GF(p) (Mark Wooding)
Re: Try it. (Mark Wooding)
Re: How encryption works (Mark Wooding)
Re: I need help to find reliable external MIME decoding utility, (JPeschel)
Re: Try it. (Mark Wooding)
Re: Missing Info in the crypto-gram of MR BS (SCOTT19U.ZIP_GUY)
Re: MD5 Expansion ("Scott Fluhrer")
Re: MD5 Expansion (Mark Wooding)
Re: Quick Question on Primitive Elements GF(p) (Simon Johnson)
Re: Encryption on missing hard-drives (David A. Wagner)
Re: Variability of chaining modes of block ciphers (David A. Wagner)
Re: How encryption works (David A. Wagner)
Re: Linear Feedback Shift Register *with* lock-up? (David A. Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Try it.
Date: 22 Jun 2000 15:36:19 GMT
John <[EMAIL PROTECTED]> wrote:
> Hmmm...I wonder, though, should they just have put the source code on
> this group? :-)
Well, if they'd done that we would at least have had a chance to perform
analysis and decide whether it was as good as the unwarranted
advertisement which started this thread suggested. However, I think we
tend to prefer descriptions in mathematical English here, rather than
raw source code.
> HOw can they make money if they can't protect there source?
Design of symmetric encryption algorithms isn't a good field to be in if
you want to make money. There's far too much good stuff out there
that's free for all uses for proprietary systems to survive except by
taking advtantage of the idiocy of customers (stupid people form a
particuarly useful market sector -- see Dilbert passim).
Asymmetric cryptography is more profitable, but I think (and fervently
hope) that with the expiry of the RSA patent we'll see proprietary
algorithms sidelined here as well.
If they're using sensible bits of publicly reviewed cryptography and
providing a convenient interface to using it then that's more sensible,
but then I can't see why they'd want an NDA.
> Oh well, this is sure a strange business.
It is that.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: DH - Man In The Middle
Date: Thu, 22 Jun 2000 15:10:02 GMT
On Thu, 22 Jun 2000 05:47:22 GMT, "Mark" <[EMAIL PROTECTED]> wrote:
First of all, why are you using DH with fixed keys? The result is that
the session key will be the same each time that two communicates begin
a connection. DH permits EITHER authentication or randomness of the
result. To get both, you must use other techniques. For example, KEA
is a dual D-H exchange in which both fixed and ephemeral keys. You
could also use a singed ephemeral D-H exchange or various other
combinations of techniques.
>Im thinking of using a DH exchange to setup my keys (client/server app).
>To stop the man in middle attack i need to sign the public values of the DH
>exchange.
>
>Im planning on storing my servers public DSS key inside the client EXE. (is
>that ok?)
It's OK until your server's key reaches the end of its cryptoperiod or
is compromised. Having the keys hard coded will prevent you from ever
changing them. However, if they are not in the client EXE, you have to
now ensure that your server's public key is trusted.
>I know i NEED to sign the public values from the server.
>what im wondering is if i can skip the signing on the client public values
>that get sent to my server.
>(this way i wouldnt need to generate any primes on the client (or am i
>missing something?))
Left to the previous response.
>If i read everything right, only 1 large prime needs to be generated for a
>DH exchange (a public value) and 2 primes need to be generated to sign using
>DSS. If i can keep this to the server it should speed up initial connection
>setup..
The numbers need not be prime, just random.
>Does this comprimise the exchange so a man in the middle attack can still
>happen (or any other).
One would have to study your complete protocol. There are several MIM
attacks that could potentially occur.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Missing Info in the crypto-gram of MR BS
Date: 22 Jun 2000 15:33:45 GMT
[EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
>James Felling <[EMAIL PROTECTED]> wrote:
>
>: I will state that I feel that in all likelyhood there is a
>: "recognisability" factor that a compression algorithim posseses.
>: Similarly there is a "recognisability" factor that any type of input
>: may have. I believe that if the compression is more easily recognised
>: than the input then do NOT compress, as you make the situation worse.
>: If that is not the case, you will make the situation no worse than it
>: previously was.( assuming that your compression either shrinks or
>: leaves the file size equal)
>
>While I largely agree with this, there's enough present for me to want
>to pick at.
>
>Firstly, if the plaintext is recognisable, it does /not/ follow that the
>result of arbitrary decompressions is recognisable.
>
>The counterexample is where practically all decompressions result in
>plausible looking target text.
>
>My usual example of this involves compression using message numbering.
>
>I.e. 0 -> "All clear on the western front"
> 1 -> "It rains on the plains of Spain"
> 2 -> "Send more troops" ... etc.
I like your example of pretenting messages represent numbers.
One could think of an ascii file ( who knows .pd .pdf .doc .txt )
as a set of ascii symbols that represent a number. All compression
routines that are not 1-1 and work on any file casue the file to
grow in size. But a 1-1 compression makes max use of the set of numbers.
but non 1-1 compression schemes don't fully use the set of numbers
that a file is mapped to when it is compressed.
Know for what I hope clears this up a little. If you compress a file
you hopefully are compressing a file to a smalles file based on something
common in messages of desire. If you compress "perfectly" and you get
a small number. Each of these small numbers represent a valid message
of the type the compressor was designed for and an attacker would
be stuck trying to guess which the valid message is.
Now suppose the compressor is perfect except for it is not 1-1 it
starts mapping to the "odd" numbers only. Know when an attack tests
a key half the files don't map to a real message so they can be eliminated
and only those that map to "odd" numbers need to be considered. This
makes the job of eliminating a class of bad files easy with perfect
presision.
Know suppose you are using 1-1 compresion where the odd files respresent
highly likely messages. While the even numbers represent very unlikely
messages. Both compression methods compress to the same degree. ( That is
for the targeted set of files ) however when an attacker tries a key
and the result is an odd file it is very likely to be a possible message.
But in this case when an attacke gets an even file. It decompresses to
a valid file that when recompressed goes back to the guessed file.
Know this even file is highly unlikely to be the correct file. but it
could be since the propability is not zero like it was in the case above.
If the file is large and the keyspace is large the number of these low
probability files is very large and in many cases this could be the
actually message. Especially if the NsA is decoding a short file written
by someone with my speeling ability. ( our like when i ask for an ascii
file i get a word file ms version 6.x)
Using non 1-1 compression gives immedate answers that many keys can
not be correct. Such information is not immediately availabe when one
use 1-1 cmopression.
>
>Such a "compressor" can retain a bijection between the set of all
>possible messages and the resulting compressed files, by an expanding
>encoding scheme used for unrecognised inputs, if this is considered
>desirable.
>
>Here, valid plaintext messages are normally easily distinguished from
>random files. They are (after all) ASCII text. However, for most
>messages decrypting with the wrong key will result in a message that
>decompresses to something very plausible looking :-(
>
>How "easy" the original message plaintext is to recognise is not
>relevant. Whether this is ASCII text or not doesn't come into it.
>
>What matters is how easy it is to identify a correct decrypt
>form the encryption component - i.e. how easy it is to distinguish
>a genuine compressed message from some random garbage.
>
>The other problem I noticed was in the idea that if it is easier to
>recognise the plaintext than the compression method, using an
>identifiable compression method will not make things worse.
>
>To my ears this sounds like the idea that if it's generally easier to
>spot spies based on their accent, than by checking their employment
>references, you shouldn't bother with getting their faked references
>straight.
>
>One problem is that sometimes use of methods to recognise the plaintext
>do not uniquely identify the correct plaintext.
>
>In such a case, the availability of *additional* halting criteria can
>help extract the correct meaning from the cyphertext.
>
>Another problem is that different halting criteria may be useful in
>different circumstances.
>
>Say there's problem (caused by a bug) that allows the last half of each
>block to be successfully decrypted - while the first half remains
>unknown.
>
>Here decompressing is likely to be impossible; since there are a
>stupendous number of possible decompressed files.
>
>However, imagine the case of a non 1-1 compressor which uses each 32nd
>bit as a CRC check.
>
>Under such circumstances it will be much easier to check for the
>signature of a poor compression method than to check for plaintext,
>even if checking for the plaintext is normally very easy.
>
>In short, you can't normally make a blanket statement that one halting
>criteria is harder to use than the other. Thay may be of differing
>utility under different circumstances.
I think we agree
http://members.xoom.com/ecil/compress.htm
------------------------------
Subject: Re: Quick Question on Primitive Elements GF(p)
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 22 Jun 2000 08:34:52 -0700
Thanxs very much for your replies......
It's not obvious why 0 cannot be part of the group. :D
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Try it.
From: None <[EMAIL PROTECTED]>
Date: Thu, 22 Jun 2000 08:37:41 -0700
John, sounds like a commie to me. Seems that he/she has
something against people making money. :-)
I agree. If they put out the source code to the public, you
wouldn't need an NDA at all! If it was public, how could
companies make money? I mean, it's like saying you'll put the
source code for Windows in the public arena and also sell it as
well. Sounds kind of ass backwards to me.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: How encryption works
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 22 Jun 2000 08:37:40 -0700
Yup wrong.......
I meant:
d= e^((p-1)(q-1))-1 mod pq
Thanxs......
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: MD5 Expansion
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 22 Jun 2000 08:43:20 -0700
Good point.......
I'll revise my suggestion:
Divide the message into two parts,a,b. do this by taking the
first character and appending it to a, the second character and
appending it to b, the third character and append this to a, the
forth character and append it to b. And so on and so fourth.....
Then:
Output = h(a) & h(b)
This should now be secure enough, with a 128-bit birthday attack.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: MD5 Expansion
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 22 Jun 2000 08:47:19 -0700
nor do i.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Try it.
From: None <[EMAIL PROTECTED]>
Date: Thu, 22 Jun 2000 08:50:54 -0700
I can only describe the encryption system in question as follows:
1. It uses Random #s
2. The outputs of the system pass the statistical tests on the
theorietical and empirical level.
Encryption is the oddest field. No other area in software is
filled with so much hype. I don't think I'm as stupid as some
think I am. I mean, if you pick a pass phrase and plaintext and
can't figure out if the cyphertext is whole without the source
code, oh well, I don't think I'll get qnywhere.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Quick Question on Primitive Elements GF(p)
Date: 22 Jun 2000 15:56:37 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Thanxs very much for your replies......
> It's not obvious why 0 cannot be part of the group. :D
A group (G, *) is a set G and a binary operator * with the properties:
* closure: for any x, y <- G, x * y <- G.
* associativity: for any x, y, z <- G, (x * y) * z = x * (y * z).
* identity: there exists i <- G such that, for any x <- G, i * x =
x * i = x.
* inverse: for each x <- G, there exists x' <- G such that x * x' =
x' * x = i.
Simply put, zero doesn't have an inverse, so it can't be in the group.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Try it.
Date: 22 Jun 2000 16:00:13 GMT
None <[EMAIL PROTECTED]> wrote:
> John, sounds like a commie to me. Seems that he/she has something
> against people making money. :-)
Or possibly he has good reasons, based on lots of experience with
cryptography, to believe that proprietary systems are less secure than
open ones.
> I agree. If they put out the source code to the public, you
> wouldn't need an NDA at all! If it was public, how could
> companies make money? I mean, it's like saying you'll put the
> source code for Windows in the public arena and also sell it as
> well. Sounds kind of ass backwards to me.
Yeah. Nobody makes any money out of Linux, do they? ;-)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: How encryption works
Date: 22 Jun 2000 16:02:04 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
> I meant:
>
> d= e^((p-1)(q-1))-1 mod pq
Oh, well. You can't get everything right first time. ;-)
It's still wrong, by the way.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: I need help to find reliable external MIME decoding utility,
Date: 22 Jun 2000 16:05:25 GMT
jungle [EMAIL PROTECTED] writes:
>I need help to find reliable external MIME decoding utility,
>decode MIME from file
WinZip can handle MIME file formats. It doesn't seem to
recognize the .mme extension, so I usually change the
extension to .uue, and WinZip decodes it.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Try it.
Date: 22 Jun 2000 16:09:00 GMT
None <[EMAIL PROTECTED]> wrote:
> I can only describe the encryption system in question as follows:
>
> 1. It uses Random #s
> 2. The outputs of the system pass the statistical tests on the
> theorietical and empirical level.
Dilbert: `Our product is beige. It uses electricity.'
Marketroid: `Woah! Brain overload!'
Oh, by the way, those are nowhere *near* being sufficient conditions for
security. (Using random numbers and passing statistical tests, I mean.
Beigeness and use of electricity aren't actually necessary. Some crypto
boxes are blue, for example. ;-) )
> Encryption is the oddest field. No other area in software is filled
> with so much hype. I don't think I'm as stupid as some think I am.
Actually, from where I'm sitting, I think it's remarkably free of hype.
There's a load of dross, but you just ignore that. Compare the amount
of hype about things like XML and Java.
> I mean, if you pick a pass phrase and plaintext and can't figure out
> if the cyphertext is whole without the source code, oh well, I don't
> think I'll get qnywhere.
Nope. You've lost me. I only understand English, French, German and
Latin.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Missing Info in the crypto-gram of MR BS
Date: 22 Jun 2000 16:06:56 GMT
[EMAIL PROTECTED] (James Felling) wrote in
<[EMAIL PROTECTED]>:
>
>
Snip
>First off I will agree that this is not true in all cases. If the file
>being compressed fills the space of possibles more efficiently than the
>compression algorithim as applied to that space does, then yes, not
>compressing is to our benefit. However, if the compression results in a
>more dense mapping of possibles within that space, then we are
>benefiting. I claim that at least in the case of text( which it seems
>we are discussing) that compression will more fill that space more
>densely( or worst case the same densly) with possibles than uncompressed
>text. Remember, the objective is to uncompress as few possible blocks
>as one can. I will agree that as the amount of data assembeld goes up
>compression gets more easily recognisable, but I find it hard to accept
>that it EVER is MORE easily recognised than text.
I hope this is cpverec in "Tim Tylers" notes or my response to
it. From what I have read he is far more cabable than my to get a point
across. He is using what to me looks like counting theorm arguments.
But I might be wrong maybe he and I see it differently. But the
concept that a file "X" failing Test "a" is black and white. It is
yes or not. But the test that is file X is a valid ascii file is not black
and white. Because I aske people to send my an ascii file and I seem
to get something generated by the latest version of Microcrap and I can't
read it becuase I don't have the latest workd processor. What are we
expected to do.You don't have a black and white (or yellow) test
program to tell if it is a valid ascii file that was entercepted. Even
stating it is asci is not enough. Since in theory ascii is an eight
bit character code. Some people have machines that only use 7 bits with
the eighth being "odd parity or zero".
test "a" where a is partial string of deciphered data by a guess key does
compress( decompress (a) ) = a
if no then the possibility of decompress (a) being the encrypted message
is exactly "ZERO"
with any other method you have a longer way to go.
I do relize that in some compression methods like arithmetic
with out proper end treatment that one would have to consider
the whole file before it could be exactly ruled out since as
Matt has noted the error in this type of compression is in the
ending of the file. But even in any case one would test the
whole file if one had a candidate solution. And sometimes the
enemy uses short files. In which case proper EOF treatment is
even of more concern to those encrypting.
>
>> <<snip>>
>
>I will state that I feel that in all likelyhood there is a
>"recognisability" factor that a compression algorithim posseses.
>Similarly there is a "recognisability" factor that any type of input
>may have. I believe that if the compression is more easily recognised
>than the input then do NOT compress, as you make the situation worse.
>If that is not the case, you will make the situation no worse than it
>previously was.( assuming that your compression either shrinks or leaves
>the file size equal)
You say you belive that yet the test to tell if a file is
a possible compressed file is the test "a" given above. It is
very easy to test. Take a random file of 20 bytes. see useing
the headerless compression routines close to you heart.
What % pass this
compress ( uncompress ( random 20 byte file)) == same random 20 byte file.
Know do the same using Matts or my compression decompression routines.
http://members.xoom.com/ecil/compress.htm
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Thu, 22 Jun 2000 08:59:33 -0700
Simon Johnson <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Good point.......
> I'll revise my suggestion:
>
> Divide the message into two parts,a,b. do this by taking the
> first character and appending it to a, the second character and
> appending it to b, the third character and append this to a, the
> forth character and append it to b. And so on and so fourth.....
>
> Then:
>
> Output = h(a) & h(b)
>
> This should now be secure enough, with a 128-bit birthday attack.
Not particularly. Suppose you know M != M' such that h(M) == h(M'). If h
has a 128 bit output, this takes no more than O(2**64) work
Then, consider the function f(X) that takes a message X, and replaces each
character with two of that same character. For example,
f( "I am a message" ) = "II aamm aa mmeessssaaggee".
It is clear that f(M) != f(M')
Then, if you apply your hashing mechanism to f(M), f(M'), then you'll find
the a=b=M, a'=b'=M', and so Output==Output', giving you a colision in no
more than O(2**64) work.
For more fun, you can consider f's which interleave M and M', which gives
you more colisions.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: MD5 Expansion
Date: 22 Jun 2000 16:17:17 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
> nor do i.
For a rose-tinted look at the security of various Rivest hashes back in
1996, see RSA Laboratories Bulletin 4: Recent Results for MD2, MD4 and
MD5, <ftp://ftp.rsasecurity.com/pub/pdfs/bulletn4.pdf>.
I'd feel very worried about using any of them now just because of the
small hash sizes. The other weaknesses are just icing on the cake.
-- [mdw]
------------------------------
Subject: Re: Quick Question on Primitive Elements GF(p)
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 22 Jun 2000 09:12:00 -0700
Ahhh, i see. Thanxs
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Encryption on missing hard-drives
Date: 22 Jun 2000 09:22:34 -0700
In article <Gy945.14$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
> On a more sci.crypt note, noone's answered my original question which
> is if it's possible to encrypt a device such that it's impossible to
> read the contents without leaving a trail.
Well, you can detect the _first_ read (to any particular file/record/block),
but then the reader could have made a copy of everything they read and
squirreled it away somewhere out of your control, so you can't reliably
detect any _subsequent_ read's. This is fundamental, I think.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Variability of chaining modes of block ciphers
Date: 22 Jun 2000 09:30:17 -0700
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> The most recent ciphers of significance are
> certainly the AES candidates. How many of these allow you to vary the
> key size from 128 by steps of, say, 8 all the way to 256?
Quite frankly, who cares?
If 152-bit keys are good enough for you, then 192-bit or 256-bit keys
should also be perfectly sufficient.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: How encryption works
Date: 22 Jun 2000 09:37:54 -0700
In article <[EMAIL PROTECTED]>,
Mark Wooding <[EMAIL PROTECTED]> wrote:
> Yes. The DSA spec says that DSA parameters p and q must be limited in
> size (p to 1024 bits, q to 160). Both restrictions seem bizarre to me.
Yup. But, there's nothing stopping you from using larger p's and q's
in your favorite implementation.
Anyway, here's a guess where those restrictions may be coming from.
First, without a trusted hash that has outputs longer than 160 bits,
we can't make q any longer (or, at least, doing so won't add security).
That handles the restriction on the size of q. On to the size of p.
The second point is that, with today's known discrete log algorithms,
1024 bits is already large enough to ensure that the best algorithm for
computing d.log.'s in a DSA-subgroup is to use the square-root attacks,
whose running time depends only on the size of q. Increasing the size
of p won't increase the difficulty of these attacks, and so would just
cause a false sense of security.
Or so the argument might go, anyway.
(Of course, if improvements to NFS were found, this latter point might
have to be revised, and it might be wise to increase the size of p.)
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Crossposted-To: comp.theory,sci.math
Subject: Re: Linear Feedback Shift Register *with* lock-up?
Date: 22 Jun 2000 09:46:55 -0700
In article <8iocit$1ghu$[EMAIL PROTECTED]>,
Ponder <[EMAIL PROTECTED]> wrote:
> Also, is there a good algorithm for converting the elements of
> an LFSR sequence into the actual value of the count?
Yes, it's ``just'' the discrete log problem in GF(2^N), and subexponential
algorithms are known.
For the sizes you are talking about, they will be very efficient,
but also probably more complex than you'd like. A simpler -- but less
efficient -- algorithm is to use Pollard's rho or some other variant,
which has complexity 2^{N/2}, which might be sufficient for your purposes.
See any good book on computational number theory or public-key cryptography.
------------------------------
** 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
******************************
