Cryptography-Digest Digest #524, Volume #14 Tue, 5 Jun 01 13:13:00 EDT
Contents:
Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. ("Douglas A.
Gwyn")
Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. Dulles / AKA
Loki) ("Scott Fluhrer")
Re: Def'n of bijection (Tim Tyler)
Re: Def'n of bijection (Tim Tyler)
Re: Def'n of bijection ("Douglas A. Gwyn")
Re: BBS implementation (Mark Wooding)
Re: Def'n of bijection ("Douglas A. Gwyn")
Re: National Security Nightmare? ("Douglas A. Gwyn")
Re: National Security Nightmare? ("Douglas A. Gwyn")
Re: Def'n of bijection (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Paul Pires")
Re: Def'n of bijection (Mark Wooding)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mark Wooding)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P.
Date: Tue, 5 Jun 2001 14:51:42 GMT
Tom St Denis wrote:
> "Dave Howe" <[EMAIL PROTECTED]> wrote...
> > ... "Tom St Denis" <[EMAIL PROTECTED]> said :
> > >Take all primes and form a composite N. Add one to N. Now N is not
> > >divisible by any of the "known" primes. Thus N+1 is a new prime not
> > >in the list.
> > or is divisible by a prime not in the original list
> That's not possible. Since we already have all consecutive primes...
> 3*5*7+1 = 106
> 106 is not divisible by any known prime (assume the only known primes are 3,
> 5, 7). ...
We have been through this before, just a few months ago.
The problem is that for purposes of the particular proof,
"prime" is being given a hypothetical meaning that is not
what it turns out to actually mean. This is okay, since
all that the proof requires is for a contradiction to be
produced. However, once the proof is established, we can
see other contradictions; for example, N+1 is (sometimes)
not a prime after all. If the proof is not carefully
stated, then such other contradictions may get in the way
of establishing the proof. It certainly confuses many
people, who seem to believe that they will always obtain a
prime when they add 1 to the product of all smaller primes.
Smiley-proof:
2+1 = 3, prime
2*3+1 = 7, prime
2*3*5+1 = 31, prime
2*3*5*7+1 = 211, prime
2*3*5*7*11+1 = 2311, prime
... obviously it works :-)
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.security,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. Dulles /
AKA Loki)
Date: Tue, 5 Jun 2001 08:08:24 -0700
Kyle Paskewitz <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom -
>
> You've forgotten that 2 is also prime. If you take the product of any
> number of consecutive primes beginning with 2 (the first prime) and add 1,
> you will get another prime. E.G.
>
> 2*3 + 1 = 7
> 2*3*5 + 1 = 31
> 2*3*5*7 + 1 = 211 , etc...
Really??? I was under the impression that:
2*3*5*7*11*13+1 = 30031 = 59*509
2*3*5*7*11*13*17+1 = 510511 = 19*97*277
2*3*5*7*11*13*17*19+1 = 9699691 = 347*27953
2*3*5*7*11*13*17*19*23+1 = 223092871 = 317*703763
weren't prime. I must be delusional, I suppose...
--
poncho
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 15:15:03 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler <[EMAIL PROTECTED]> writes:
:> Yes. The case where the key is as large as the original message is not
:> where compression helps.
: Smaller message ==> smaller key. Compression is a great way to economize
: your OTP key material.
It also helps with bandwidth - but it doesn't help with security.
:>: if keys contain exactly as much entropy as the original message...I
:>: further conjecture that this is what the theorems on OTP actually say.
:>
:> I don't think they mention the possibity of compression.
: But I'll bet you a beer they mention entropy.
I'm sure they do - but I doubt they discuss what you were talking about.
: Loosely speaking, the best compression is the one for which ``bits in
: output file'' equals ``bits of entropy in input file''. By the definition
: of entropy, better (lossless) compression is impossible. And perfect
: security can probably be achieved if ``bits of entropy in key'' equals
: ``bits of entropy in message''.
I wouldn't dispute any of that.
:>: Anyway, that seems to be the problem here: Scott (and some others) are
:>: conflating the notions of ``compression'' with the desirable
:>: properties of a OTP, and then expressing their confused ideas with
:>: confusing language.
:>
:> A bizarrely inaccurate representation of the situation IMO. AFAICS,
:> nobody is "conflating the notions of ``compression''" with anything.
: Then think carefully about it. With gzip, brute-forcing the key might
: mean, ``decrypt, and check for a valid gzip header.'' With BICOM, it might
: mean ``decrypt, then decompress, then check for meaningful content.''
: If done right, that does add work to the decryption stage, which is nice.
: But that is effectively a form of cipher chaining. IOW, BICOM represents
: a compressor which also obscures information. Applying ROT128 to a gzipped
: file would have a similar effect [...]
Let's get this straight. BICOM is a Bijective compressor, with an
attached bjiective (from all files to all files) version of Rijndael.
What are you saying here? That ROT128 has a "similar effect" to Rijndael?
That gzip is a bijective compressor?
Do you understand that "checking for meaningful content" can become a less
effective strategy after compression - due to more files looking like
plausible messages?
: In short, if the cipher is so easy to brute force that spotting gzip's
: header does a lot for you, then the cipher is no good. Adding work is
: nice, but you really want a cipher which stands on its own merits. It
: should be perfectly safe to encrypt ASCII-coded English.
You apparently neglect the possibility of keyspace reduction through other
means than cryptanalysis of the messages themselves.
Say the keys are stored in a key book which is partially destroyed during
capture. Then a brute force search of the remaining keyspace becomes
possible.
Say the keys are generated by a faulty RNG that is 80% predictable.
Then a brute force search of the remaining keyspace becomes possible.
Even in the unlikely circumstances where cryptanalytic attack *was* the
only possible approach, how would you know that your cypher was immune?
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 15:34:44 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler <[EMAIL PROTECTED]> writes:
:>: In particular, BICOM merely adds a layer of obscurity to a message;
:>
:> The aim of the compressor is mainly compression - not adding obscurity.
: Precisely. Which is why you (and other BICOM fans) are slightly confused.
It appears to be you who are confused :-| You happily make patronising
statements (like the one above) but then go on to spoil things by making
false statements that indicate you don't properly understand the situation ;-(
: You yourself just said, ``all other compressors add information which
: can be used by a cryptanalyst to reject decrypts''. In other words, you
: wish the compressor would contribute obscurity.
Those are indeed "other words". However they do not convey anything
remotely like the meaning I intended.
I do *not* "wish the compressor would contribute obscurity".
The compressor is an unkeyed transformation. You can't get much
obscurity with an unkeyed transformation - unless you try and keep
the algorithm secret.
: Hint: If compressors are used to compress, not add obscurity, then the
: presence of ``known plaintexts'' is a non-issue. [...]
If (for example) the compressor adds a header during compression
then that is known plaintext that can obviously feed known plaintext
attacks.
Adding known plaintext /is/ a concern when compressing.
:>: [...] one simply decompresses the message and THEN checks it for
:>: meaningful content.
:>
:> I *keep* hearing this - as though it is some sort of mantra.
: Because that's what one does. [...]
It's the assertion that this operation will still work just the same as
before that I am objecting to.
: Why are you upset that people point out what ``brute-forcing'' means
: for BICOM?
I'm not upset.
:> In cases where checking for meaningful content might have worked with
:> uncompressed messages, it will not necessarily work where the messages
:> have been compressed, since there are likely to be more decrypts that
:> look as though they contain meaningful content.
: That statement requires proof. [...]
Not to those who actually understand it. It should not be controversial.
: Hint: It's false. Each compressed file has exactly one decompressed
: original. One merely decompresses and THEN looks at the result.)
You are totally mistaken. That strategy can fail after compression, due
to the greater number of decompressions that look like plausible messages.
I though you agreed that with "perfect" compression, all decrypts would
look a lot like plausible messages - in which case your posposed strategy
would fail miserably.
:> Compression increases the resulting unicity distance for a system.
:> This makes it likely that some messages which had unique decrypts will no
:> longer do so if compression is applied.
: Since BICOM compression is ``bijective'', there is exactly one message
: per compresssed file. All I have to do is decompress--I am then guaranteed
: to be looking at the file whose compression I started with. There are not
: ``lots of possible'' decompressions.
I never said there were.
For any possible *cyphertext* there are many possible decompressions -
probably about one for each key.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Tue, 5 Jun 2001 15:19:22 GMT
Tom St Denis wrote:
> I would say if he could map one english message to a random english
> message that would be very cool. (Without wasting tons of memory)
A mapping is easy; just use a good source model. There is an example
of this in Kernighan & Pike: "The Practice of Programming".
The hard part is establishing an *invertible* mapping of that kind.
Probably even harder is parameterizing the mapping so that a crypto
key can be used.
If you really want to pursue this, you'd be well advised to permit
the ciphertext to have a somewhat different size than the plaintext.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: BBS implementation
Date: 5 Jun 2001 16:10:58 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> As I understand it, if you know the length of the cycle you only know
> factors of (p-1)(q-1) right?
I'm caught out.
If you can find short cycles with nonnegligible probability then you can
factor. Just falling over one by accident I believe has a nontrivial
probability of allowing you to factor given additional polynomial-time
effort, but won't automatically drop the factors out.
-- [mdw]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Tue, 5 Jun 2001 15:35:54 GMT
[EMAIL PROTECTED] wrote:
> Anyway, that seems to be the problem here: Scott (and some others) are
> conflating the notions of ``compression'' with the desirable
> properties of a OTP, and then expressing their confused ideas with
> confusing language.
No, there is more to it. If you take a 2048-bit ciphertext
from a system that uses a 128-bit key, there are only 2^128
possible plaintexts, nowhere near the 2^2048 that an ideal
system would have. D.Scott's goal, in general terms, seems
to be to develop a system that avoids having that property.
Since compression would be a natural component of a secure
system anyway, why not exploit it to help with this matter.
As a general matter, I support the idea that security can
benefit from being integrated with other aspects of data
encoding, rather than treated orthogonally. Whether this
is a good idea depends on requirements for the system; if
the system has to support a wide variety of encodings, a
layered approach may be the only feasible solution.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Tue, 5 Jun 2001 15:52:35 GMT
Mok-Kong Shen wrote:
> If everyone of the world were honest and behaved correctly,
> laws would have been an absolute nonsense from the very
> beginning.
That's nonsense, since "behaving correctly" necessarily
translates to "following some laws", such as obeying
traffic signals. Also, disputes can arise even among
reasonable people, and a system is necessary to resolve
them, unless you really prefer that disputes be settled
by uncontrolled brute force.
It is possible, and useful, to make a distinction between
arbitrary regulations vs. rational, objectively defined
rules. Nobody of good will should object to the latter.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Tue, 5 Jun 2001 15:47:52 GMT
"SCOTT19U.ZIP_GUY" wrote:
> And from what little they get back it shows that FIOA's
> are a joke. I know people who swear somthing happend at Roswell
> and that the government is hiding it.
Well, if there is a UFO cover-up, they have also managed to hide
it from people with *very* extensive access to intelligence archives.
Something *did* happen at Roswell; nobody has disputed that.
The dispute is about the nature of the event(s). Some of the
UFO sightings can now be attributed to Mogul. (Why such a high
level of secrecy was imposed on that project still escapes me.)
Other sightings have been traced to experimental aircraft.
So far, there has been no credible evidence that space aliens
are involved, other than as a popular "explanation".
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 16:36:40 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> Anyway, that seems to be the problem here: Scott (and some others) are
:> conflating the notions of ``compression'' with the desirable
:> properties of a OTP, and then expressing their confused ideas with
:> confusing language.
: No, there is more to it. If you take a 2048-bit ciphertext
: from a system that uses a 128-bit key, there are only 2^128
: possible plaintexts, nowhere near the 2^2048 that an ideal
: system would have. D.Scott's goal, in general terms, seems
: to be to develop a system that avoids having that property.
I'm not sure I'd put it quite like that.
If you take a ciphertext from a system that uses a 128-bit
key, there *are* generally only 2^128 possible plaintexts.
AFAICS, developing a system which /didn't/ have this property would imply
the use of a non-deterministic decryption algorithm (e.g. with many
plaintexts mapping to each cyphertext) - which isn't really what David's
talking about most of the time.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Tue, 5 Jun 2001 09:44:56 -0700
Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Paul Pires <[EMAIL PROTECTED]> wrote:
> : Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> :> : (How long must this go on?)
> :>
> :> I don't know:
> :>
> :> Maybe until you realise that an OTP doesn't have perfect secrecy if it's
> :> dealing with finite files, and converting them to cyphertexts of the same
> :> length as the plaintexts?
>
> : Ehrr? Why not? [...]
>
> See the definition of "perfect secrecy" - e.g.:
> http://www.io.com/~ritter/GLOSSARY.HTM#PerfectSecrecy
>
> ``The unbreakable strength delivered by a cipher in which all possible
> ciphertexts may be key-selected with equal probability given any
> possible plaintext. This means that no ciphertext can imply any
> particular plaintext any more than any other. This sort of cipher needs
> as much keying information as there is message information to be
> protected. A cipher with perfect secrecy has at least as many keys as
> messages, and may be seen as a (huge) Latin square.''
>
> : It seems to me that that a Ct could be from any possible Plaintext of
> : exactly the same size.
>
> That's perfectly correct.
>
> : Are you saying that just leaking the size is a lapse in perfect secrecy?
>
> Yes. It is - unless your system is a bizarre one which can only transmit
> one byte messages.
I don't believe you answered the question.
You pointed me to Terry's site and a description of perfect secrecy
in wich OTP is an example. It clearly states that a requirement
is that it have "as much keying information as there is message
information" and "at least as many keys as messages". Does "a finite file
converted to a ciphertest of the same size" have something about it
that cannot fulfill this requirement? Should Terry revise his site and
add an additional, clearly stated requirement? Is there some subtle useage
of the term "information" implied here?
If you saying that perfect secrecy requires the masking of the true length
Well, that's in there already if one chooses to use it. If the information is
secure, there is nothing to stop someone from securely encrypting an
instruction to remove some random nonsense that was added to change
the file length. It is still a finite file where the ciphertext is the same size as
the message encrypted but the true file size is now unknowable right?
Once again, what is this message VRS Ciphertext size constraint to
perfect secrecy?
Paul
> --
> __________
> |im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Def'n of bijection
Date: 5 Jun 2001 16:57:34 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> You are totally mistaken. That strategy can fail after compression, due
> to the greater number of decompressions that look like plausible
> messages.
I'm not sure this can work.
Let C (our bijective `compression' function) be a permutation on
{0, 1}^* -- the set of finite bitstrings. There is a subset P \subseteq
{0, 1}^* of `plausible' strings. I assume that E is relatively small
compared to {0, 1}^*, otherwise the whole effort is rather pointless.
We claimed that C was a permutation on bitstrings. So |C(P)| = |P|.
That is, the proportion of compressed strings whose decompressions are
plausible is equal to the proportion of plausible strings among all
bitstrings.
What have I missed?
> For any possible *cyphertext* there are many possible decompressions -
> probably about one for each key.
No more than there are possible plaintexts prior to compression, since
as claimed the decompression function is bijective.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: 5 Jun 2001 17:03:23 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> So what? I know that 45893475893475893475378893573895 is an n-digit
> composite, but I don't know the factors...
45893475893475893475378893573895 =
3.5.53.5741.10055328798694131799486841
Glad to be of service.
-- [mdw]
------------------------------
** 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
******************************
