Cryptography-Digest Digest #818, Volume #8 Thu, 31 Dec 98 02:13:03 EST
Contents:
Birthday Attack calculations. (Fred Van Andel)
Re: On leaving the 56-bit key length limitation ([EMAIL PROTECTED])
Re: MTP Complex Number Cipher (Terry Boon)
Re: Birthday Attack calculations. (DJohn37050)
Re: Decoder for Reed-Solomon codes? ([EMAIL PROTECTED])
Re: Opinions on S/MIME ("Roger Schlafly")
Compound Cipher... (Rebus777)
Free Steganographic program ([EMAIL PROTECTED])
Re: Birthday Attack calculations. (Fred Van Andel)
"Barry Bouwsma" forged spams -- encrypted lines? (Tomoyuki Tanaka)
Re: On leaving the 56-bit key length limitation (wtshaw)
Re: Birthday Attack calculations. ("Adam Atkinson")
Re: Compound Cipher... (wtshaw)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Fred Van Andel)
Subject: Birthday Attack calculations.
Date: Wed, 30 Dec 1998 23:16:02 GMT
Reply-To: [EMAIL PROTECTED]
How does one calculate the exact number of documents that need to be
hashed to ensure a collision? I know that it is approximately
1.2*2^(M/2), but what is the exact formula or procedure for
calculating the number?
Thanks
Fred Van Andel
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: On leaving the 56-bit key length limitation
Date: Wed, 30 Dec 1998 23:10:10 GMT
In article <76a53p$sia$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>
> [much snippage]
> [only thing I can say now from first bit :]
>
> Could you recommend a good treatment of the unicity distance? Are
> Shannon's papers the best place to start ?
I would suggest to begin with Shannon's two papers:
[Sha48] Shannon, C. A Mathematical Theory of Communication. Bell Syst. Tech.
J., vol. 27, pp. 379-423, July 1948. See also
http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html for a WWW copy.
[Sha49] Shannon, C. Communication Theory of Secrecy Systems. Bell Syst. Tech.
J., vol. 28, pp. 656-715, 1949.
See also http://www3.edgenet.net/dcowley/docs.html for readable scanned images
of the complete original paper.
But the last one shows its age. As I commnented in the original posting,
the concept of "unicity distance" needs to be revisited IMO. I am working
on a public presentation of the main arguments involved, which I will submit
here and elsewhere for public comments.
>
> Would such a system be on the lines of probabilistic systems, except that
> all possible decryptions "look valid" ?
First, note that it is hard to define what is "to look valid" -- since you do
not know the plaintext. This is an identification problem. Using the
Identification Theory outlined in
http://www.mcg.org.br/coherence.txt and http://www.mcg.org.br/coherence2.txt
I can consider the four possible identifications of all possible decryptions,
defined by identification level I-2, as:
D - Distinguished -- when an observer can distinguish one
plaintext.
A - Ambiguous -- when an observer can distinguish different
plaintexts but is uncertain which one to take.
O - Obscure -- when an observer cannot distinguish a plaintext
but can percieve information.
F - Formless -- when an observer cannot detect any form of
information exchange.
The table above is given just to illustrate the difficulties posed by the
question -- what is to "look valid"?
It also serves to introduce the generalized concept of identification -- "to
identify is to look for coherence" -- which allows identification to be
defined *without* a previosuly required identity. This removes the
circularity implied by the usual definition (see references) and allows an
intrinsic treatment of identification -- as I need here.
>
> [much snipping]
> [create multiple perfectly "valid" but not true decryptions]
> > -- which the user's system can choose based on some trusted
> > information provided out-of-band.
> ^^^^^^^^^^^^
>
> What kinds of systems would use such information without turning it into a
> secret key ?
An example:
anything you can communicate by phone, person-to-person, trusted courier,
trusted line, etc. can help you define *settings* in a software such that this
software is personalized to these choices.
> or is the point to reduce key exchange to a single larger,
> out of band transfer instead of doing all these in band, policeable
> exchanges ?
Can be a combination -- but can also be an automated process.
>does it make sense to ask how large such information would
> need to be, or do we need designs first?
>
design first -- since it depends on the "unicity distance".
> Please feel free to give pointers to designs or lit - this sounds
> intriguing, but I think I'm missing the point. :\
>
Your questions were fine to the point. The bottom-line is: we need to stop
wasting key-length bits -- they are a valuable resource now and the current
WA limit is NOT bad when one works in terms of "unicity distance". This may
actually *increase* the resilience of security designs -- over fat keys that
do not deliver the security they seem to promise, when "unicity distance"
issues are ignored.
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Terry Boon)
Subject: Re: MTP Complex Number Cipher
Date: Thu, 31 Dec 1998 00:21:18 GMT
=====BEGIN PGP SIGNED MESSAGE=====
On Wed, 30 Dec 1998 21:13:14 GMT, [EMAIL PROTECTED] (R. Knauer)
wrote:
>Here is an MTP (Many Time Pad) cipher based on complex numbers.
[snip]
>Are there any realistic analytic attacks possible if the pad is used
>multiple times? It would seem that because of the way that the
>ciphertext is built, it is not possible to learn the identity of any
>group of three numbers from a known plaintext attack.
>
>IOW, even if I know the ciphertext pair, (X, Y), belongs to a known
>plaintext character, 'd', I cannot know (a, b, c) even though
> X = (ac - bd) and Y = (ad + bc).
There is a known-plaintext attack if we know *two* distinct
plaintext-ciphertext pairs. Suppose:
(x1, y1) being the ciphertext of d1,
(x2, y2) being the ciphertext of d2,
each being encrypted with the key triple (a,b,c)
then we can decrypt any ciphertext (x3, y3) encrypted with the same
key to reach the corresponding plaintext d3.
By the definition of the cipher,
x[n] = ac - bd[n]
y[n] = ad[n] + bc
for n=1, 2, or 3.
- From this, we get
x1 - x2 = -b(d1 - d2)
x1 - x3 = -b(d1 - d3).
Hence
(x1 - x2)/(x1 - x3) = (d1 - d2)/(d1 - d3)
and the denominators are non-zero as long as b is non-zero and the
ciphertext we seek to decrypt is distinct from the two ciphertexts we
already know.
(In the special case where b is zero, we use a similar technique with
y1, y2, and y3, requiring that a is non-zero. If both a and b are
non-zero then the key is invalid: encryption by multiplying by zero
doesn't lend itself to subsequent decryption by anyone.)
Now the LHS is known; on the RHS, all the quantities other than d3 are
known, so we can deduce the value of d3.
Best wishes,
Terry Boon
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use
<http://www.pgpi.com>
iQCVAwUBNorDP+raDInvl9TRAQEOLwP9Ecp+iEl5jWr3pW03t8mJvAweccSnHHaS
oBUA5kmNjpFS+2Muhy0TW0ohjROmaH1jsAGI5vx6OuiK4JGJwAFsLqjJQhnsGPqG
8IvN2R66kiOhMHSaW71w/8VmGFsY+OVTnzMGCdrKVDmkw6SDi1+VFBhpMI4m70pm
aKcYdW5tqTU=
=6UEb
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Birthday Attack calculations.
Date: 30 Dec 1998 23:59:16 GMT
To ensure a collision, the exact number is n+1. THe birthday attack in
probabilistic. See the HAC.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.dsp,sci.math
Subject: Re: Decoder for Reed-Solomon codes?
Date: 31 Dec 1998 01:18:32 GMT
[Note Followup-To]
In sci.crypt [EMAIL PROTECTED] wrote:
> I'm trying to implement a decoder for "Reed-Solomon" codes.
> I checked out the ECC codes page, and found a few encoders/decoders,
> but they all are designed for codes based on GF(2^m), m usually being
> Appreciate any pointers to freely accessible C code...
While it does not do Reed-Solomon directly, a package I've found
useful for doing arbitrary polynomial math (including GF) is LiDIA,
which is available at:
ftp.informatik.tu-darmstadt.de:/pub/TI/systems/LiDIA
<notices headers>
Well, it's probably a bit large for dsp work, but what do I know? ;-)
--
...God does not play dice with the universe; He plays...an obscure and
complex version of poker in a pitch-dark room, with blank cards, for
infinte stakes, with a Dealer who won't tell you the rules, and who
_smiles all the time_. -- _Good Omens_ by N.Gaiman and T.Pratchett
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Opinions on S/MIME
Date: Wed, 30 Dec 1998 17:44:55 -0800
Sam Simpson wrote in message <[EMAIL PROTECTED]>...
>Once quick question; you state that "Breaking a 512-bit DSA key is
>significantly more difficult. [than an RSA key]". Could you please explain
>(in laymen terms - I'm not that bright <g>). I thought ElGamal and RSA
keys
>of the same length were thought to be equivalently secure?
The asymptotics are similar. But breaking DH (ElGamal or DSA) requires some
large tables. Much larger RSA keys have been broken than DH keys.
------------------------------
From: [EMAIL PROTECTED] (Rebus777)
Subject: Compound Cipher...
Date: 31 Dec 1998 02:53:53 GMT
After obtaining and experimenting with the 4 Tiny algorythms
(TinyIdea, DosFish, GoldFish and TinyRC6) that I DL from
Robert Durnal's great page, I got to thinking about what you
might have, if you combine 2 of the Tiny algorythms into one package.
Maybe Goldfish and TinyRC6.
I was wondering if it Would be possible, or desireable, to offset the
second encryption by 2 or 3 bytes so that blocks from the second
encryption overlaped the blocks from the first encryption? If
speed became a factor, maybe some rounds could be cut back in the
individual algos. I think only one password entry would be good also.
Does this seem like something that would be of benefit?
I have heard of the possible weekness introduced when 2 block ciphers
are combined, but I thought that the offset I have proposed might
over come this and produce a strong encipherment.
Regards,
--RSC
If you haven't checked out Robert's page, he also has nice free
Win 3.1 & W95 versions of Blowfish. Plus Stego programs
www.members.tripod.com/~afn21533/
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.privacy,fido7.crypt,talk.politics.crypto,alt.privacy.anon-server
Subject: Free Steganographic program
Date: Thu, 31 Dec 1998 03:16:44 GMT
Free 32 bit program
Hide your encrypted data's in a picture file, so there is no
traces of encryption.
Visit the Data Privacy Tools home page.
http://www.xs4all.nl/~bernard
------------------------------
From: [EMAIL PROTECTED] (Fred Van Andel)
Subject: Re: Birthday Attack calculations.
Date: Thu, 31 Dec 1998 03:46:01 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (DJohn37050) wrote:
>To ensure a collision, the exact number is n+1. THe birthday attack in
>probabilistic. See the HAC.
I should have stated for 50% probibality, the formula given is for
that value. My aploogies.
Fred Van Andel
------------------------------
From: [EMAIL PROTECTED] (Tomoyuki Tanaka)
Crossposted-To: alt.fan.hofstadter,alt.tanaka-tomoyuki
Subject: "Barry Bouwsma" forged spams -- encrypted lines?
Date: 31 Dec 1998 04:01:21 GMT
i've been seeing these "Barry Bouwsma" forged spams for the
last several weeks.
>Jimm feo ivee ueda tif
>deyo cih pdo ldfs iri gl?
can these lines be easily decoded?
====================================================================
In article <[EMAIL PROTECTED]>,
Newsgroups: soc.culture.jewish,alt.gothic,nes.software.nntp,
alt.slack,alt.fan.hofstadter
Tomoyuki Tanaka <[EMAIL PROTECTED]> wrote:
>BOVINE BACKSTABBER BARRY BOUWSMA BRUTALLY BITES BELGIAN BABY
> BOYS' BROWN BUNGHOLES !!!
>
>Jimm feo ivee ueda tif
>deyo cih pdo ldfs iri gl?
>
>Meylki telpp hh eiqlem aod.
>
>Uekhd uha zswpr tlvy fcfg jbtu?
====================================================================
new WWW links in the next version of "GEB" FAQ include ...
====================================================================
http://www.earlham.edu/~peters/hometoc.htm Peter Suber
http://www.pronetinc.net/~fermigas/DouglasHofstadter.html
http://www.forum2.org/tal/books/marot.html
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: On leaving the 56-bit key length limitation
Date: Wed, 30 Dec 1998 21:42:19 -0600
In article <76ebsc$h3l$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> The bottom-line is: we need to stop
> wasting key-length bits -- they are a valuable resource now and the current
> WA limit is NOT bad when one works in terms of "unicity distance". This may
> actually *increase* the resilience of security designs -- over fat keys that
> do not deliver the security they seem to promise, when "unicity distance"
> issues are ignored.
>
You can have both fat keys and algorithms with an extended unicity
distance, or one without the other, or neither. I suggest, and I have
done so before, that contemplating how much ciphertext is necessary to
confirm solution of a whole key is a useful measure of an algorithms
security, a long unicity distance is preferable.
This may be a useful way to approach Ritter's observation, that we have no
real measure of the security of an algorithm.
It is really up to experience to know what that practical amount is, and
we have lots of experience with some of the older algorithms. Take
something simple like a tableau cipher, that some are rather adept in
solving. Rather than just using an extremely longer key, I rather try to
modify things with an entirely new additional key.
Now, the question I pose is how much longer, if any, is the unicity
distance and can it be quantitatively determined in something like Code
Blue, which I recently described? Is the varation in algorithm as useful
as an increase in the standard key of the same amount? I was thinking of
Ritter's multiple algorithm idea when I did this one, something scaled
down from anything really spectacular.
--
New Year's Resolution: Strive to be accurate, even if it means telling a lie or
misrepresenting the whole truth; after all, this is how Congress does it.
------------------------------
From: "Adam Atkinson" <[EMAIL PROTECTED]>
Subject: Re: Birthday Attack calculations.
Date: 31 Dec 98 04:55:33 +0000
On 31-Dec-98 03:46:01, Fred Van Andel said:
>>To ensure a collision, the exact number is n+1. THe birthday attack in
>>probabilistic. See the HAC.
>I should have stated for 50% probibality, the formula given is for
>that value. My aploogies.
well, doing it "by hand" in perl would look something like:
$n=43949268;
#$n=365; #gives 23, which is right
$p=1;
for($i=1;$p>0.5;$i++) {
$p*=($n-$i)/$n;
}
print $i."\n";
--
Adam Atkinson ([EMAIL PROTECTED])
Verbing weirds language. (Calvin)
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Compound Cipher...
Date: Wed, 30 Dec 1998 23:21:26 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Rebus777) wrote:
> After obtaining and experimenting with the 4 Tiny algorythms
> (TinyIdea, DosFish, GoldFish and TinyRC6) that I DL from
> Robert Durnal's great page, I got to thinking about what you
> might have, if you combine 2 of the Tiny algorythms into one package.
> Maybe Goldfish and TinyRC6.
>
> I was wondering if it Would be possible, or desireable, to offset the
> second encryption by 2 or 3 bytes so that blocks from the second
> encryption overlaped the blocks from the first encryption? If
> speed became a factor, maybe some rounds could be cut back in the
> individual algos. I think only one password entry would be good also.
>
> Does this seem like something that would be of benefit?
> I have heard of the possible weekness introduced when 2 block ciphers
> are combined, but I thought that the offset I have proposed might
> over come this and produce a strong encipherment.
>
Rules of thumb when chaining algorithms: they should have as little in
common as possible; it might make a difference which is used first; the
ciphertext from the first encryption should not be easily recognized so as
to inhibit or prevent staged solutions; rules of thumb may or may not
apply, or be understatements, so be careful.
Consider an ancient category, tableau ciphers, and consider a more recent
one, a simple block cipher, and, having done a pair of implementations
partly for the chance to use one key structure, in two wildly different
algorithms, the result can produce something much stronger through
chaining than with either alone. If I followed, the rules for chaining,
it becomes rather a pain to think about solving them both together.
this is the input text used for the message and to generate the keys used
in both algorithms.
The two algorithms are Code Blue and Trinity 27, but encryption must be
first in Trinity 27, or there is a conflict in formats. Here are the
keys, identical:
Subs1(T27): sfipjqtgb klnyuvc/w zrdaemoxh
Subs2(T27): eqfvwamgb rdxtnhsiu cyjzokpl/
Trans(T27): s/tdciobp xfameqrjy gnuzhkvlw
Key1(CB): sfipjqtgb klnyuvc/w zrdaemoxh
Key2(CB): eqfvwamgb rdxtnhsiu cyjzokpl/
Key3(CB): s/tdciobp xfameqrjy gnuzhkvlw
In Trinity 27, text is preformatted and last group is padded to 9 characters:
this/is/t he/input/ text/used /for/the/ message/a nd/to/gen erate/the
/keys/use d/in/both /algorith msxelgxof
Ciphertext from Trinity 27 and Plaintext for Code Blue:
fpbarzeek lcixnsltf g/wtxnepu smokuvhhb qzlozelcn m/azldiss vkgl/wzzi
vdryadnox jsljszplc d/mfyxhpx sqpcutlai
Ciphertext from Code Blue:
mxgbkyzch zqjrshlbv bmacfxbuo ekxejbprs viyzdjwwi rfxsunqln rvtjfjvnl
tuttqt/ec rytvpstsf cnecireml bcqkiqlmc
Regrouped and padded an extra character to hide the 9 character groups:
mxgbk yzchz qjrsh lbvbm acfxb uoekx ejbpr sviyz djwwi rfxsu nqlnr vtjfj
vnltu ttqt/ ecryt vpsts fcnec ireml bcqki qlmcr
Aside from the weird slant sign in one group, which might be taken as an
indicator of some kind, a analysis type guy or gal has a real problem
knowing where to start to wrestle with it. Keep all your messages short
and chain the keys, to protect the comments about where you store you
jelly bellies.
This paragraph for fellow keylength freaks: One could use two different
sets of keys, each of the six keys having a keyspace of 27!, for a
combined total keylength equivalent to 353.12 bits. Now, alone, Code Blue
is a pretty weak sister, while Trinity 27 is a bit more formidable;
together, chained just this way, we have a new algorithm, not much of a
slacker come to think of it. Strangely enough, Trinity 27 is a lot faster
cipher than Code Blue.
Of course, these are limited ciphers, just done for such an example needed
to illustrate my couple of points worth a penny a piece, or 0.16 Texas
bits total, if you know the value of a bit a hundred years ago. The same
concepts should not be lost in any other situation, no headers, no hitch'n
posts midstream, ciphertext flowing from one algorithm to the next.
Look closely at the two algorithms you want to chain together and see if
they can follow the rules I gave.
--
New Year's Resolution: Strive to be accurate, even if it means telling a lie or
misrepresenting the whole truth; after all, this is how Congress does it.
------------------------------
** 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
******************************
