Cryptography-Digest Digest #139, Volume #12 Fri, 30 Jun 00 00:13:00 EDT
Contents:
Re: Idea or 3DES ("Joseph Ashwood")
Re: Blowfish for signatures? (Arthur Dardia)
Re: Idea or 3DES ("Joseph Ashwood")
Re: Blowfish for signatures? ("Joseph Ashwood")
Re: Java & Win32 ("Charles Oram")
Re: MD5 Expansion ("Scott Fluhrer")
Re: Another chaining mode ("Scott Fluhrer")
Re: Compression & Encryption in FISHYLAND (John Savard)
Re: Observer 4/6/2000: "Your privacy ends here" ("P.D.Stamford")
Re: MD5 Expansion (David A. Wagner)
Re: very large primes (Dennis Ritchie)
When you know the PT is ascii (Andrew John Walker)
Re: How Uncertain? ("Douglas A. Gwyn")
Re: very large primes ("Douglas A. Gwyn")
Re: very large primes ("Douglas A. Gwyn")
Distribution of keys in binaries? ("Anonymous Coward")
Re: Compression & Encryption in FISHYLAND ("Douglas A. Gwyn")
Re: Distribution of keys in binaries? (Paul Rubin)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Idea or 3DES
Date: Thu, 29 Jun 2000 16:31:04 -0700
Crossposted-To: alt.security.scramdisk,comp.security.pgp.discuss
Perhaps you're not too good at math with really big numbers, so I'll try
again.
First, it is by no means such a small factor, with a value of 2^100+, 2^38
certainly looks like epsilon, the same way that 2^-60 is easily considered
epsilon in the small numbers that are easier for the bulk of the population
to deal with. However it is a _factor_ of 2^38 by which they differ, so
instead of comparing 2^112+2^38 with 2^112 like you were doing in your
statement, we are comparing 2^112 to 2^128, this is difference is of course
far from what you had stated, ebing a difference of a factor of only 2^16.
What you have to remember is that cryptography is not a true science yet,
there are very few real answers. Considering the space needed to perform the
meet-in-the-middle reduction of 3DES to 2^112, and the fact that at the
current space densities known to the public the space alone would occupy a
significant portion of the volume of the earth, I believe the value was
something like 2^70 large capacity backup tapes (if you need any help 2^70
is a very, very big number, I think you might get confused if I wrote it out
for you). While the attack you are thinking of (and apparently the only
attach you think possible, however wrongly) for IDEA takes 196-bit of total
space outside of the algorithm, I remain confident that we can certainly
build the equipment to perform the IDEA attack, but are unable to even
concieve of the effort used to create the equipment for the 3DES attack. So
basically if we consider only the feasible attacks on the 2 we have 3DES at
168-bits, and IDEA at 128-bits, leaving 3DES ahead by a rather substantial
40 bits, or a factor of 2^40. If we consider all possible attacks IDEA is
brought down small amounts by various attacks, and after careful
consideration I have decided to label it as approximately 100-bits worth of
security at this time, or the same position I give for 3DES and CAST.
If you are going to insist on an algorithm, please make sure you do the
research and not make the same mistake that the third reich did in world war
2, and blindly trust what the fools tell you.
Joe
"jungle" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> IDEA should be considered extremely more secure than triple DES ...
> - exactly, from 2^38 to 2^20 steps more secure ...
>
> Joseph Ashwood wrote:
> >
> > CAST is kind of the loose choice for this. In terms of security
differences,
> > all 3 algorithms are really only seperated by epsilons (numbers small
enough
> > that they are only maintained for accuracy, not for relevance).
>
> I will call # of steps of 2^38 as EPSILON only when I'm ignorant ...
>
>
------------------------------
From: Arthur Dardia <[EMAIL PROTECTED]>
Subject: Re: Blowfish for signatures?
Date: Thu, 29 Jun 2000 19:37:46 -0400
> "Noam E. Kirly" is actually 3654 029817 <[EMAIL PROTECTED]>.
> 0123 4 56789 <- Use this key to decode my email address and name.
> Play Five by Five Poker at http://www.5X5poker.com.
You may well indeed have the most absolutely ridiculous anti-spam reply
address.
--
Arthur Dardia Rensselaer Polytechnic Institute [EMAIL PROTECTED]
PGP 6.5.1 Public Key http://www.webspan.net/~ahdiii/ahdiii.asc
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Idea or 3DES
Date: Thu, 29 Jun 2000 16:37:23 -0700
Crossposted-To: alt.security.scramdisk,comp.security.pgp.discuss
"jungle" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Arturo wrote:
> > And what if we accept the fact that not even the USG is all-powerful?
>
> accepting above fact has nothing to do with the reality ...
Except that accepting the fact would be a first for you from what I've read.
No government is all-powerful, nothing is all-powerful. To be blind to power
is often folly, to be blind to the lack is always folly.
>
> > They can´t stop the flow of drugs into the US or prevent a
starving-to-death
> > country like North Korea from becoming a nuclear power,
>
> why above jobs are left not finished is the matter of preference
> AND NOT the inability ...
Trust me, there is NO POSSIBLE WAY that any government can completely
eliminate drugs, just look at history. The third reich seems to be a good
example for much of what you say, they taught that the Arians were
invinsible (the Arians by the way in actuality had nothing to do with
Germany, and were actually from the middle east where they were the first
people tat I'm aware of to practice slavery based on race), they were proven
very wrong, and it took decades for Germany to recover from the losses
mostly because Germany was split and kept by 2 seperate countries for much
of that time.
In short it _is_ the inability.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Blowfish for signatures?
Date: Thu, 29 Jun 2000 16:44:15 -0700
Actually, yes you can, simply perform the following (one of many solutions,
some of which are better, some worse):
1)choose a key (K) no larger than 384-bits
2)Use that key to encipher the first block of the text (call the input T[1],
the output C[1])
3)pad K with C[1] to form K[2]
4)encrypt T[2] (the second block of the text) with K[2] to get C[2]
...
form K[n] by padding K with C[n-1]
encrypt T[n] with K[n]
.....
The last C[n] is your signature, just transfer K securely and it can be
verified and will be difficult to fake.
Joe
------------------------------
From: "Charles Oram" <[EMAIL PROTECTED]>
Subject: Re: Java & Win32
Date: Fri, 30 Jun 2000 12:12:32 +1200
I haven't tried this, but you could take a look at
http://www.ritlabs.com/tinyweb/index.html where someone has succesfully used
OpenSSL with Delphi.
============================================================================
=======================
Charles Oram - Real-time and Embedded Systems Development
Email: [EMAIL PROTECTED]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Thu, 29 Jun 2000 18:37:26 -0700
Anton Stiglic <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> Andrew Bortz <[EMAIL PROTECTED]> wrote:
> > In the interest of increasing the size of a MD5 hash, I have been
> > thinking of a fairly simple method:
>
> So a provable way of extending the output of a secure hash
> function h is to simply split the input m into two equal halves
> am and bm (such that m = am || bm, || is concatenation) and output
> h(am) || h(bm).
> (Like Simon Johnson described).
>
> On way to prove that the extended function is strongly collision
> resistant.
> You do this by proving that it's as strongly collision resistant as a
> single hash.
> So now let's say I can find an existential collision with h,
> m != m' such that h(m) = h(m'), I can trivially find an existential
> collision on the extended scheme: m || n and m' || n, where you
> would split m || n into m and n, and split m' || n into m' and n,
> will collide in the extended scheme.
> So now let's go the other way around, let's say that we can find
> a collision with the extended scheme, say that n and n'
> are such that h(an) || h(bn) == h(an') || h(bn') (where the splitting
> of x gives ax, bx). You can see that an, an' will form a collision
> for h, so will bn, bn'. This means that if the extended scheme
> is not strongly collision free, the initial hash function h isn't
> either.
>
> As simple as that!
I think the point is to have an extended hash function be more strongly
collision resistant as the underlying hash, not merely "just as good as".
If you needed a hash function that output more bits, and needed to be no
stronger than the underlying hash primitive h, then an even simpler way is
to define the extended scheme:
h'(M) = h(M) || 00000..00000
where 00000..00000 is exactly as many zero bits as you needed to get the
length up. A similar argument to yours will show that h' is no less
collision resistant than h, and it can be computed almost as efficiently as
one evaluation of h.
:-)
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Another chaining mode
Date: Thu, 29 Jun 2000 18:47:56 -0700
Mark Wooding <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Scott Fluhrer <[EMAIL PROTECTED]> wrote:
>
> > With DES, this gives 2**16, which is probably not enough. For AES,
> > this is 2**32, which is (IMHO) borderline. And, yes, as you observed,
> > this works best on ciphers with large block size.
>
> This is a concern, but I'm not sure that it's as bad as you've painted
> it. Note that even if the input plaintext is random, we'll get
> collisions in the output half-block with after 2^{n/4} blocks. But
> these tell us nothing at all about the plaintext! I'm not sure that you
> can easily pick out a `signal' caused by equal input plaintexts from the
> background `noise' of natural collisions.
Actually, I wouldn't think it'd be that hard for an attacker to notice.
For one, note that my observation needs stereotypical sequences of plaintext
blocks (actually half-blocks), not just single blocks. For such sequence,
AAA BBB CCC DDD EEE
the first 4 corresponding ciphertext halfblocks would be a function of those
5 plaintext halfblocks, plus the ciphertext halfblock immediately before it.
And, if two sequences of 5 identical ciphertext half-blocks occur, it is far
more likely to be caused by 5 identical plaintext half-blocks than by random
chance. And so, if the attack just searches for common sequences within the
ciphertext, he might be lucky, and find likely common sequences within the
plaintext.
A major concern? Maybe not. However, it is a weakness compared to CBC...
---
poncho
>
> -- [mdw]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Compression & Encryption in FISHYLAND
Date: Fri, 30 Jun 2000 02:08:22 GMT
On 28 Jun 2000 15:29:08 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote, in part:
> As I have told you many times. With my huffman compression routine
>you can change the last byte to any of its 256 combinations and
>in each case it will decompress to a file that when compressed
>back it will be that same file. THis concept is apparently over
>your head.
That concept I understand.
However, some of those 256 combinations take place when the
unconverted message ends in a particular sequence of two bits, like
01, and others of them take place when the unconverted message
(Huffman compressed, but without the additional wrinkle that gets to
even bytes) ends in a particular sequence of seven bits, like 1011011.
Although there are 32 times more possible 2156 bit messages than there
are 2151 bit messages, that does *not* mean that people send 2156 bit
messages 32 times more often than 2151 bit messages. If that were the
case, you would never be able to live long enough to download more
than an infinitesimal fraction of the postings on this newsgroup.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "P.D.Stamford" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Fri, 30 Jun 2000 02:37:40 +0100
In article <[EMAIL PROTECTED]>, Simon Elliott
<[EMAIL PROTECTED]> writes
>JimD <[EMAIL PROTECTED]> writes
>>On Tue, 27 Jun 2000 21:25:34 +0100, Andy Dingley <[EMAIL PROTECTED]>
>>wrote:
>>
>>>[EMAIL PROTECTED] (JimD) a écrit :
>>>
>>>>>>>Maybe the webmaster's been assassinated by MI6.
>>>
>>>>Absolutely. There was that woman from Shrewsbury they had
>>>>murdered.
>>>
>>>Hilda Murrell ?
>>
>>None other.
>
>What was that all about? I don't remember reading about this in the
>papers.
About ten years ago.
--
P.D.Stamford
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: MD5 Expansion
Date: 29 Jun 2000 18:18:32 -0700
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> So a provable way of extending the output of a secure hash
> function h is to simply split the input m into two equal halves
> am and bm (such that m = am || bm, || is concatenation) and output
> h(am) || h(bm).
Be careful. This can't make collisions any easier to find, but the
`secrecy properties' get worse, because the construction can make
dictionary attacks easier.
(Each half of the message might have only half the entropy of the total
message, so the complexity of dictionary attacks might go down from 2^n
to 2^{n/2}, or something like that.)
------------------------------
From: Dennis Ritchie <[EMAIL PROTECTED]>
Subject: Re: very large primes
Date: Fri, 30 Jun 2000 03:17:49 +0000
"Douglas A. Gwyn" wrote:
>
> Roger Schlafly wrote:
> > Maybe not "simple", but there are polynomials whose positive
> > values are precisely the set of primes.
>
> I'd be interested in seeing one.
I no longer remember the precise results and their consequences,
but it is probably more like: for every recursively enumerable set,
there is a polynomial f(a; x1, x2, ..., xn) where n is fairly small
(10 or 20 or so) whose coefficients are integers, such that there is a
solution in integers for f()=0 if and only if a<0 or a is a member
of the r.e. set.
Look up Matiyasevich and Diophantine or Hilbert's Tenth Problem.
Don't miss Matiyasevich's own home pages (which are spread about), e.g.
http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/Julia/
about his collaborations with Julia Robinson.
Don't look to this work as a good way to generate primes (or
members of other recursively enumerable sets). But it's beautiful.
Dennis
------------------------------
Subject: When you know the PT is ascii
From: [EMAIL PROTECTED] (Andrew John Walker)
Date: 30 Jun 2000 10:18:17 +1000
How secure are encryption methods such as DES, IDEA etc when you
know the PT consists of printable text or some other subset of
the ascii character set? From what I've read many methods that
have been proposed are quite suceptible to plain-text attacks,
however I haven't seen how this relates to my question, ie
if knowing this would allow a quicker attack than a straight
brute force search. I am assuming that
all you have is one or perhaps a few encrypted texts using the
same key and no plain text.
Andrew Walker
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How Uncertain?
Date: Thu, 29 Jun 2000 23:26:19 -0400
Mark Wooding wrote:
> The definition of entropy I'm using is ...
... one that is suitable only for independent events.
English is a lot more predictable than the uniliteral frequencies
would lead one to believe.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: very large primes
Date: Thu, 29 Jun 2000 23:34:43 -0400
Mike Andrews wrote:
> It's a process -- or algorithm, if you specify a max. number,
> but it's not a formula (IMHO) because it's not closed-form.
To a large extent, what we perceive to be the difference between
a formula and an algorithm is largely a matter of what we have
compact, expressive notation for that is conventionally accepted
by working mathematicians. For example, summation of an indexed
expression over some index set (even a simple one such as i=1..n)
is allowed in "expressions", but if you look hard at it, it seems
to be algorithmic. See also some of the notation introduced in
the book "Concrete Mathematics".
Our ability to perform "algebra" (symbol rearrangement) with
"algorithms" is generally less than with "formulas", but that's
a matter of degree, which can change over time as more is learned.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: very large primes
Date: Thu, 29 Jun 2000 23:43:28 -0400
Dann Corbit wrote:
> http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
For those who are curious but not suffocoently so to go on a
Web hunt, the cited page starts off:
"Legendre showed that there is no rational algebraic function
which always gives primes. In 1752, Goldbach showed that no
polynomial with integer coefficients can give a prime for all
integer values (Nagell 1951, p. 65; Hardy and Wright 1979, pp.
18 and 22)."
That's what my vague recollection referred to.
It continues:
"However, there exists a polynomial in 10 variables with integer
coefficients such that the set of primes equals the set of
positive values of this polynomial obtained as the variables run
through all nonnegative integers, although it is really a set of
Diophantine equations in disguise (Ribenboim 1991)."
That seems to be what Dennis was referring to.
There is more, but mainly about defective generators.
------------------------------
Date: Thu, 29 Jun 2000 23:50:46 -0400
From: "Anonymous Coward" <[EMAIL PROTECTED]>
Subject: Distribution of keys in binaries?
How secure is it to distribute a key (for encryption/decryption) somehow hidden inside
a binary? How difficult is it to reverse-engineer the binary to extract the key, if
the
exact encryption algorithm (2fish, blowfish, idea, 3des, etc.) is not known?
I know that many people much more knowledgeable than meself hangout in these
newsgroups.
Thanks!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Compression & Encryption in FISHYLAND
Date: Thu, 29 Jun 2000 23:59:14 -0400
"SCOTT19U.ZIP_GUY" wrote:
> That is just it by showing that it is relavent to a brute force
> search. Then it opens up in other avenues of attack. If the compression
> your using can immediately show an enemy that certain classes of keys
> can't lead to a valid decryption then those classes of keys can be
> ignored.
For it to really matter, you'd have to be able to concisely
*characterize* those key classes, and especially you'd have
to do that from an analysis of the ciphertext. So far nobody
has exhibited any clue as to how that structure could "shine
through" any reasonable encryption.
> Why do anything that helps the enemy when it is so easy to
> avoid the potential problem altogether.
I have some sympathy for that point of view. If one is going
to use a compressor (highly recommended for plaintext containing
a lot of redundancy), then your criterion should be given some
weight in choosing the compression scheme. However, with such
low risk to start with, other factors might have more weight.
For example, nearly everybody has access to gzip/gunzip and can
use that with very little additional effort (in an environment
such as UNIX where it is easy to combine functions in a pipeline).
Certainly, that would be risky when a low-grade form of encryption
is used, which is when your suggestion would offer the most benefit.
For high-grade encryption, one-on-one compression wouldn't seem to
much affect the odds of successful cryptanalysis.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Distribution of keys in binaries?
Date: 30 Jun 2000 04:03:50 GMT
In article <[EMAIL PROTECTED]>,
Anonymous Coward <[EMAIL PROTECTED]> wrote:
>
>
>How secure is it to distribute a key (for encryption/decryption)
>somehow hidden inside a binary?
Not secure.
>How difficult is it to
>reverse-engineer the binary to extract the key, if the exact
>encryption algorithm (2fish, blowfish, idea, 3des, etc.) is not
>known?
It's a pain in the neck, but if it's protecting something worthwhile,
somebody will go to the trouble.
------------------------------
** 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
******************************
