Cryptography-Digest Digest #508, Volume #13 Sat, 20 Jan 01 20:13:00 EST
Contents:
Re: Differential Analysis (Tom St Denis)
Re: 32768-bit cryptography (Jerry Coffin)
Re: crypto cracking screen savers ("William A. McKee")
Re: Dynamic Transposition Revisited (long) ("Matt Timmermans")
Re: Differential Analysis ("Matt Timmermans")
Re: Dynamic Transposition Revisited (long) (John Savard)
Re: Full text to the book ``Underground'' released ([EMAIL PROTECTED])
Re: Dynamic Transposition Revisited (long) (Benjamin Goldberg)
Re: Dynamic Transposition Revisited (long) (Benjamin Goldberg)
Re: Why Microsoft's Product Activation Stinks (zapzing)
Re: Where can I find software tools for Known-text decryption ("�eeker")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sat, 20 Jan 2001 18:42:19 GMT
In article <94ciem$qb6$[EMAIL PROTECTED]>,
Splaat23 <[EMAIL PROTECTED]> wrote:
> Man, you are way out of control! Calm down a bit, please. Your input to
> every thread I've read has been great and useful except when you go
> overboard attacking something or someone. Of course, now you will
> attack me...
Actually upon reflection I agree I have been a bit tempermental. I am in
fact sorry. I've just been pre-occupied with exams and can't be bothered to
humor silly posts.
Advice taken, I think I will try to be a bit cooler :-)
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: 32768-bit cryptography
Date: Sat, 20 Jan 2001 12:55:28 -0700
In article <Pine.OSF.4.10.10101201749250.2394-100000
@cassius.its.unimelb.edu.au>, [EMAIL PROTECTED] says...
> On Fri, 19 Jan 2001, Paul Pires wrote:
>
> > 1024 bit cryptography (If you are talking symmetric) will never be broken
>
> Pfffft!
>
> Computing power doubles every 18 months or so. Brute force is all you
> need if you have enough power. Within your lifetime, 3xDES will be
> completely crackable.
That works up to a point. Even if we assume it can be extrapolated
out that far, this would theoretically mean that 1024-bit encryption
could be cracked by brute-force sometime over 1400 years from now.
If you honestly think you can predict what's going to happening 1400+
years into the future, you're clearly insane.
There's a LOT of room for question as to whether a method of
computation that involves pushing electrons around could come
anywhere close to finishing this size of job before it used up all
the energy in the universe.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
Reply-To: "William A. McKee" <[EMAIL PROTECTED]>
From: "William A. McKee" <[EMAIL PROTECTED]>
Subject: Re: crypto cracking screen savers
Date: Sat, 20 Jan 2001 22:12:42 GMT
http://www.distributed.net
--
William A. McKee <[EMAIL PROTECTED]>
http://www.cjkware.com/wamckee/
cjkware.com inc.
http://www.cjkware.com/
"We're starfleet: weirdness is part of the job." - Janeway
"I have seen things I cannot deny." - Scully
PGP public key at http://www.cjkware.com/wamckee/pgp/ ( ID = 0x11162FF2)
Finger Print: F5B8 6251 050C 7595 6A84 6C37 6041 4258 1116 2FF2
"We need your help... " - http://www.distributed.net/
<[EMAIL PROTECTED]> wrote in message news:94adju$81u$[EMAIL PROTECTED]...
> Greetings:
>
> I have heard about some projects for cracking crypto algorithms via
> distributed processing in which they farm out bits and pieces to the
> mass public in the form of a screen saver and use computer idle time to
> crunch away. Are there any such projects currently running? Where would
> one go to register and get a screen saver?
>
> Thanks!
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sat, 20 Jan 2001 22:47:26 GMT
"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> You need to be more explicit. In Dynamic Transposition, each block is
> ciphered independently under a running keystream starting from a
> random message key.
Each block is ciphered independently only if the RNG sequence for multiple
blocks is independent. Otherwise, there will be correllations between
blocks in the permutation chosen.
> Dynamic Transposition is about building an unbreakable cipher
> *without* needing an unbreakable RNG. This is done by hiding the
> breakable sequence behind multiple levels of haystack, each so massive
> that they cannot be searched. So the sequence in question cannot be
> revealed, which makes it somewhat difficult to attack.
Are you using "unbreakable" in two different senses, here? OTP can be
provably
unbreakable, because there is as much key as message. No cipher is
unbreakable when you have more message than key.
> >If you don't know anything about the RNG, then there's no such thing as a
> >known-plaintext attack.
>
> Allow me to teach what a known-plaintext attack is:
>
> Known-plaintext is nothing more than the situation of the opponent
> having one or more ciphertext blocks with the associated plaintext
> blocks. It is quite possible to have that situation without knowing
> anything of the RNG. A known-plaintext attack is any attack which
> capitalizes on this information situation (as opposed, say, to
> ciphertext-only).
Yes, I know what known plaintext is, and the condescension is unnecessary.
I
said there were no known plaintext _attacks_ if you know nothing about the
RNG. If you know nothing about the RNG, then it could be perfect (i.e., OTP
perfect), no matter what bits you have in your known plaintext/ciphertext
pair. A perfect RNG is not attackable (i.e, no way to do the _capitalize_
part of your paragraph above), because nothing you know about it can be used
to make predictions about its future behaviour. Therefore, a
known-plaintext attack against Dynamic substitution or an XOR stream cipher
is impossible when you know nothing about the RNG, because you cannot gather
any information that would allow you to distinguish the RNG from a perfect
one.
> In an additive stream
> cipher or conventional OTP, known-plaintext reveals the enciphering
> sequence immediately and completely.
It reveals part of the sequence, and that part is useful only if you can
attack the generator with it. Dynamic substitution is the same, but the
part of the sequence revealed doesn't align nicely on bit boundaries -- you
provide more obfuscation, but not the provable security you claim.
> Dynamic Transposition is unusual in that knowing the plaintext and the
> associated ciphertext does not reveal the enciphering permutation.
> The reason for this is that many different bit-permutations will
> produce the bit-for-bit exact same transformation between plaintext
> and ciphertext. Therefore, having known plaintext does not reveal the
> enciphering permutation, and thus cannot be exploited to begin to
> expose the RNG sequence.
It doesn't reveal the entire enciphering permutation, but it _does_ reveal
an amount of information about the sequence that is roughly equivalent to
the block size.
> >With 4096-bit blocks, one block of known plaintext gives you over 4000
bits
> >of information about the state of the generator
>
> Not true, as far as I know. Certainly, as a completely unsupported
> assertion, it is not believable on faith alone.
I left that out, because it's easy.
As you said, the generator state is big enough to produce any possible
permutation, i.e., it's at least 43000 bits big, 4096! is about 2^43000.
There are 2^39000 permutations that will produce the same output (that's
(2048!)^2). If output permutations are evenly distrubuted among possible
generator states, that means that only one out of any 2^4000
(2^43000/2^39000) possible generator states could have produced any given
output, and so a single known plaintext provides 4000 bits about the state
of the generator.
> Known plaintext simply does not identify the correct permutation
> produced by the confusion sequence. It certainly does not identify
> the sequence which produced that permutation.
It rules out all but one of every 2^4000 possible sequences.
> Each one of every possible permutation is equally probable. This
> exposes no information at all.
Each possible permutation is equally probable only if your generator is
unknown. It's easy for me to devise generators that will produce the same
permutation for every block. I can also make generators that produce
related permutations for every block. Clearly, Dynamic Substitution would
not be secure with generators of these types. If dynamic substitution is to
be secure, then, it's security must rely in some way on the security of the
generator.
What generator properties are required before this cipher is safe? How do
these requirements differ from the requirements for safe XOR ciphers?
> >It's probably a good idea for
> >amplifying the security of a stream cipher,
>
> No. Dynamic Transposition is a block cipher.
It's a block cipher that relies on a secure keyed RNG. I would call it a
block-oriented combiner for stream ciphers.
> I suspect it is provably secure, and furthermore does not depend upon
> unproven mathematical assumptions.
>
> Dynamic Transposition gives us a way to achieve believable practical
> security beyond that available from a classic OTP, while using keys of
> reasonable size.
Classic OTP is provably secure. Dynamic Transposition is provably secure
when you use an OTP key as your RNG stream. It's not a cipher, though,
until you specify an RNG. When you specify an RNG that uses keys of
"reasonable size", you will not be able to prove DT secure without taking
the security of the RNG as axiomatic.
In fact, once you specify a bounded key size K, then it's provably breakable
by brute force in randomized O(2^K) with O(K) of known plaintext. That
works for all ciphers, of course, and that's why there are no ciphers with
bounded key sizes that are provably secure in the same way that OTP is.
There is just no getting around the fact that a cipher is breakable in
principle as soon as you have more message than key material.
Now, even though there's nothing "provably secure" about anything you've
said, I do belive that DT is a useful combining mode. It's likely that
using DT as a combiner for any standard stream cipher RNG would go a long
way towards protecting the resulting cipher from attacks that are found
against the XOR version.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sat, 20 Jan 2001 22:54:55 GMT
Ah, you for got the rule #253 -- always count to ten before clicking the
send button. And the corollary -- if you don't have time to count to ten,
then you don't have time to post.
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:94cm6a$tf5$[EMAIL PROTECTED]...
>
> Actually upon reflection I agree I have been a bit tempermental. I am in
> fact sorry. I've just been pre-occupied with exams and can't be bothered
to
> humor silly posts.
>
> Advice taken, I think I will try to be a bit cooler :-)
>
> Tom
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sat, 20 Jan 2001 23:48:44 GMT
On Sat, 20 Jan 2001 05:43:52 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>Dynamic Transposition is about building an unbreakable cipher
>*without* needing an unbreakable RNG. This is done by hiding the
>breakable sequence behind multiple levels of haystack, each so massive
>that they cannot be searched. So the sequence in question cannot be
>revealed, which makes it somewhat difficult to attack.
In the sense that for any particular N-bit block with N/2 one bits and
N/2 zero bits, given known plaintext, the permutation chosen from
among the N! possibilities gives the same ciphertext as any
permutation from a set of (N/2)!^2 permutations?
And you were, in addition, proposing to transpose twice.
But these things can certainly all be done with substitutions as well,
and more conveniently. However, I certainly will admit that the XOR of
several PRNGs is easier to analyze than the composition of several
permutations, but the use of substitution does not force us to be as
unimaginative as that - and gives us a much wider choice of options
than transposition does.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.security,alt.security.espionage,comp.os.linux.security
Subject: Re: Full text to the book ``Underground'' released
Date: Sun, 21 Jan 2001 00:04:24 GMT
Interesting story-like presentation of lesser-known but important
computer crimes. Lots of specific details.
Worth reading. :)
In article <[EMAIL PROTECTED]>,
Julian Assange <[EMAIL PROTECTED]> wrote:
>
> I'm very pleased to announce that thanks to Random House, Suelette
> Dreyfus and myself the complete and unabridged electronic text to our
> famed computer crime book ``Underground'' (approx 500 pp.) has been
> publically released.
>
> +---------------------------------------------------------+
> | Format | Name | Size (bytes) |
> |---------------------------------------------------------|
> |---------------------------------------------------------|
> | Text | underground.txt | 979993 |
> |---------------------------------------------------------|
> |---------------------------------------------------------|
> | Text, ZIP | underground.zip | 357915 |
> |---------------------------------------------------------|
> |---------------------------------------------------------|
> | Text, GZIP | underground.txt.gz | 355953 |
> |---------------------------------------------------------|
> |---------------------------------------------------------|
> | Text, BZIP2 | underground.txt.bz2 | 265014 |
> |---------------------------------------------------------|
> |---------------------------------------------------------|
> | Palm Basic Doc | underground.pdb | 519140 |
> |---------------------------------------------------------|
> |---------------------------------------------------------|
> | Palm Teal Doc | underground-tealdoc.pdb | 520661 |
> +---------------------------------------------------------+
>
> The Palm formated files will allow you to read the book on
> a Palm Pilot and various other handheld machines.
>
> See http://www.underground-book.com/download.php3
>
> Feel free to forward this message.
>
> Julian.
>
> --
> Julian Assange |If you want to build a ship, don't drum up
people
> |together to collect wood or assign them tasks
and
> [EMAIL PROTECTED] |work, but rather teach them to long for the
endless
> [EMAIL PROTECTED] |immensity of the sea. -- Antoine de Saint
Exupery
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sun, 21 Jan 2001 00:23:24 GMT
John Savard wrote:
>
> On Sat, 20 Jan 2001 05:43:52 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
> in part:
>
> >Dynamic Transposition is about building an unbreakable cipher
> >*without* needing an unbreakable RNG. This is done by hiding the
> >breakable sequence behind multiple levels of haystack, each so
> >massive that they cannot be searched. So the sequence in question
> >cannot be revealed, which makes it somewhat difficult to attack.
>
> In the sense that for any particular N-bit block with N/2 one bits and
> N/2 zero bits, given known plaintext, the permutation chosen from
> among the N! possibilities gives the same ciphertext as any
> permutation from a set of (N/2)!^2 permutations?
>
> And you were, in addition, proposing to transpose twice.
If I select a permutation p1, from among one of N! possibilities, and
another permutation, p2, also from one of N! possibilities, and then
take the composition p3 = (p1 o p2), then the resulting permutation is
also one of the N! possibilities. Additional transpositions don't
change any of the properties of the ciphertext. What they do change, is
this:
Suppose I have found a way to identify from a known plaintext
*precisely* what permutation (p3) was applied to it. Now suppose I also
have a way to way to go from a single permutation to the generator
which, umm, generated it. There is a large difficulty now: To get the
generator output, I need p1 and p2. If their selection was unbiased,
then there are N! different combinations of (p1, p2) which compose to
p3.
> But these things can certainly all be done with substitutions as well,
> and more conveniently.
Except that it is quite difficult to create, for example, a secure 4096
bit substitution, whereas it is easy to create a 4096 bit permutation.
> However, I certainly will admit that the XOR of
> several PRNGs is easier to analyze than the composition of several
> permutations, but the use of substitution does not force us to be as
> unimaginative as that - and gives us a much wider choice of options
> than transposition does.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sun, 21 Jan 2001 00:24:04 GMT
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Sun, 21 Jan 2001 00:19:40 GMT
In article <94aq44$imi$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> Gunner <[EMAIL PROTECTED]> wrote:
> > On Wed, 17 Jan 2001 13:46:49 -0500, "Mysterion" <[EMAIL PROTECTED]>
> > wrote:
> >
> > >Sounds like Microsoft is determined to shoot themselves in the
foot.
> >
> > Give the boyz at Warez.com a couple weeks...no problem....lol
>
> Gee, Gunner. I dunno. An entire week?
>
> I wonder if a backup copy of the harddrive would need to be activated?
The operating system probably checks periodically
to make sure that the hardware configuration is
exactly what it thinks it should be. There is also
an interesting possibility of checking the chip
ID number, if they ever go ahead with that.
--
Void where prohibited by law.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "�eeker" <[EMAIL PROTECTED]>
Subject: Re: Where can I find software tools for Known-text decryption
Date: Sun, 21 Jan 2001 00:52:15 GMT
> Do you have a particular cipher in mind? Both CSS, and the PKZIP stream
> cipher have famous known-plaintext attacks implemented in public-domain
> software. I don't know of any others that have actually been implemented
> and distributed.
With WinZip I see that there are four possible ways to compress a file and a
setting for uncompressed. If one were to, say, have a Word document that
was compressed within the zip file, is it feasible to extract some header
information from a generic Word file and use that for a plain-text attack?
The same questions applies for other file types.
If one knew that WinZip were used to compress the file and knowing that
WinZip offers only four levels of compression, could that be used to
implement one of four methods of a plain-text attack using header info? I'm
assuming for the moment, perhaps incorrectly, that the header info would
have to be compressed using the same compression that is in the archive.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
