Cryptography-Digest Digest #415, Volume #12 Fri, 11 Aug 00 07:13:00 EDT
Contents:
Re: 1-time pad is not secure... (Tim Tyler)
Re: Random Number Generator (Tim Tyler)
Re: 1-time pad is not secure... (Tim Tyler)
Re: 1-time pad is not secure... (Tim Tyler)
Re: Knowing when you've cracked an encryption (Roadkill)
Re: Copyright isue - SERPENT (Runu Knips)
Re: BBS and the lack of proof (Mark Wooding)
Re: 1-time pad is not secure... (Tim Tyler)
Re: 1-time pad is not secure... (Tim Tyler)
Re: Random Number Generator ([EMAIL PROTECTED])
Re: Q: CD (Tim Tyler)
Re: Random Number Generator ([EMAIL PROTECTED])
Re: OTP using BBS generator? (Mark Wooding)
Re: Cross-platform secure chat ([EMAIL PROTECTED])
Re: OTP using BBS generator? (Mark Wooding)
Re: 1-time pad is not secure... ("Jott")
Explain S-boxes please ("MVJuhl")
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 Aug 2000 08:56:29 GMT
[EMAIL PROTECTED] wrote:
: I think all the crypto-books are wrong. One-time pad is only secure
: based on the assumption that random numbers do exist.
: But can you prove that random numbers really exist? No.
: Can you generate truely random numbers? No.
In practice OTPs aren't definitely secure. But this is old hat.
See, for example, http://www.io.com/~ritter/NEWS2/OTPCMTS.HTM
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Random Number Generator
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 Aug 2000 08:49:37 GMT
tomstd <[EMAIL PROTECTED]> wrote:
: Try a 1GB string and compress it. Also a random string
: should compress a little over lots of data.
>From this it looks like you don't share Chaitin and Kolmogorov's notion
of what randomness is.
See http://www.cs.auckland.ac.nz/CDMTCS/chaitin/cmu.html below
"Randomness: lack of structure" for a brief summary of their views,
or Chaitin's home page: http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 Aug 2000 09:05:18 GMT
fvw <[EMAIL PROTECTED]> wrote:
: <8mth1u$vpt$[EMAIL PROTECTED]> ([EMAIL PROTECTED]):
:>Can you generate truely random numbers? No.
: yes. time between radioactive decays for instance is a
: textbook example of a perfect random generator.
No such thing as a perfect random number generator has ever been created.
Time between radioactive decays /may/ be random - or it may not be.
Without vertain access to a complete theory of physics nobody knows.
...but this is beside the point - even *if* such a random process were
available, there's no way of measuring it without using a detector
which is potentially subject to non-random environmental interference.
: a 100 byte message encrypted with a OTP would have would have
: 2^800 keys, meaning all possible messages could be 'bruteforced'
: from that plaintext. Even with a prng, all possible plaintexts
: are possible [...]
With a 100 byte message? Unlikely - unless the PRNG has a comparable seed
size.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 Aug 2000 09:08:51 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
: fvw wrote:
:> <8mth1u$vpt$[EMAIL PROTECTED]> ([EMAIL PROTECTED]):
:> >Can you generate truely random numbers? No.
:> yes. time between radioactive decays for instance is a
:> textbook example of a perfect random generator.
: Yep.
: I'm very surprised to hear someone believes true random isn't available.
Why's that? True randomness has never been demonstrated.
There's /plenty/ of room for scepticism.
: Shows a serious lack in ideas about modern physics, doesn't it ?
It does not.
Modern physics rarely discusses the construction of random number
generators. Even if there *were* fundamentally random processes in
basic physics = which is far from proven - that would be unlikely to
make building a "true" random number generator possible.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
Date: 11 Aug 2000 09:27:48 -0000
From: Roadkill <[EMAIL PROTECTED]>
Subject: Re: Knowing when you've cracked an encryption
Davic Barber wrote:
>
> A problem I never see discussed is: How do you know when you've successfully
> cracked an encryption?
An answer I have not seen in the replies so far (on my news server) is
that e.g. PGP *knows* when you have entered an incorrect pass phrase. In
version 2.x it has a 16 bit checksum inside the cyphertext to determin
this. 16 bits is not much, but allows you to discard 99.998% of the
possible plain texts.
Roadkill
--
"If you're so special, why aren't you dead" - Kim Deal
------------------------------
Date: Fri, 11 Aug 2000 11:25:37 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Copyright isue - SERPENT
kihdip wrote:
> A candidate for AES has to be free for everybody to use, but is it correct
> that SERPENT has some limitations in implementations because of a copyright ??
> If so, how much of the SERPENT implementation does this copyright involve ??
No, the only AES algorithm with a license problem is RC6, which will
only be free if it becomes AES, which is unlikely because it doesn't
offer key agility.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: BBS and the lack of proof
Date: 11 Aug 2000 09:33:05 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
>
> > tomstd <[EMAIL PROTECTED]> wrote:
> >
> > > Among many BBS is thought to be a prng that is as secure as at least
> > > factoring the associated modulus. However... nobody really knows
> > > anything about the generated bits or the period of them.
> >
> > Predicting the output of a BBS generator mod n is proven to be as
> > difficult as deciding quadratic residuosity mod n. If the period is
> > short enough for you to traverse a cycle, you'll be able to predict the
> > generator's output. Hence, traversing a cycle is at least as hard as
> > deciding quadratic residuosity. QED.
>
> Are you sure it is the traversal of a cycle rather than the finding of
> a cycle to traverse that is equivalent? Can you mention a reference
> that makes this distinction?
Err... What's the distinction you think I've drawn?
Wherever you start, you'll be on some sort of a cycle. This is clear,
because the state is fiinte, and the transformation x |-> x^2 is a
permutation over Q_n. So merely finding a cycle, in this sense, is a
bit like finding the ground beneath your feet, and doesn't tell you
anything very interesting.
So the issue is whether you can find a cycle which is short enough to
actually traverse. If you can do this, you can clearly predict the past
and future of the generator, and (as proven in the paper) this allows
you to decide quadratic residuosity.
My feeling is that we're having a minor disagreement about terminology.
I don't mind this: I like to give things the right names where I can, so
if you have an improvement to offer then I'll accept that gladly. If
this isn't terminological, could you please explain what it is in more
detail so that I can respond to it sensible? ;-)
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 Aug 2000 09:13:15 GMT
Guy Macon <[EMAIL PROTECTED]> wrote:
: Actually, oddly enough, what I learned in Seminary explains why we
: keep seeing this idea much better than anything I ever learned in
: a Physics class.
: There is a branch of theology that seems to be influencing people
: who don't know the root source of the ideas they hold. [...]
: Alas, by this time enough people were infected with the "no randomness"
: meme that it became a self-sustaining memeplex which attempts to
: propagate into sci.crypt on a regular basis.
Save your psychoanalysis until you have a "perfect" random number
generator which you can demonstrate has the property in question.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 Aug 2000 09:19:27 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: On Thu, 10 Aug 2000 06:11:11 GMT, [EMAIL PROTECTED] wrote, in part:
:>One-time pad is only computationally secure, no difference than any
:>other systems. The key-generating process may be duplicated, if not
:>exactly, to some probability.
: If the key is produced by, for example, rolling dice by hand, I am not
: exactly sure how one would even begin attempting to 'duplicate' the
: key generation process in order to arrive at the same, or a similar,
: sequence of numbers.
A similar sequence of numbers may not be necessary - only that the key
may be duplicated "to some probability".
Even a /tiny/ bias - of the type expected with casino dice - may be
sufficient to leak information:
You should be able to reject the possibility that the cyphertext
represents a given plaintext with a high level of confidence - even if the
bias in the OTP is very small - provided with a large enough message.
This is a leak.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random Number Generator
Date: Fri, 11 Aug 2000 09:45:36 GMT
[EMAIL PROTECTED] wrote:
> Do you think that there is no mapping of finite sets of natural
> numbers into set of infinite sets of natural numbers?
> Please evaluate this algorithm and you will believe.
You know, from what I can see, alot of people have evaluated this
algorithm, and your block cipher and found problems with both. Not to
mention your discrete log solver. ;)
What I'd really like to know is how does this generator compare to the
one in your quasi-one time pad cipher (AESC or AOTP or whatever it's
called now). Did you take to heart any of the critisisms on it before
launching into developing this?
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Q: CD
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 Aug 2000 09:26:06 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: If the error probability is of some appropriate magnitude,
: I guess that there could be at least the following application:
: One purposedly create, presumably with special hardware, groups
: of 'pits' that are errors when interpreted by the normal
: reading device and hence are ignored by it. Through an appropriate
: scheme one could embed information bits there. For an outsider,
: these groups of bits would be hardly distinguishable from
: those that are naturally expected to occur. One achieves thus
: a steganographical transmission of information with CDs.
There's plenty of scope for this. Errors are expected and dealt with by
error correction codes before the user sees them, and there's enough
overkill to allow space for messages while still retaining some error
correction for these.
I wouldn't like to guess at the capacity for sending secret messages -
except to say that a CD's capacity in this area is likely to be large.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random Number Generator
Date: Fri, 11 Aug 2000 09:52:23 GMT
[EMAIL PROTECTED] wrote:
> Arithmetic operations with lose of overflow bit by addition and overflow
> byte by multiplication implement one way function. It is impossible to
This isn't clear at all. And in any case, a one way function should be
impossible to guess the input to as well. I mean, if you lose one bit
you've basically got a 50-50 chance of guessing what it was. ;)
> Let me ask you how can man implement permutation of bits not using
> Assembler?
Frankly, _this_ is what gets most people's goat. What I completely
fail to understand is how someone so interested in math and invested
the time to learn x86 assembly can't manipulate bits in a higher level
language.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 11 Aug 2000 09:57:11 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> On 10 Aug 2000 15:01:56 GMT, in <[EMAIL PROTECTED]>,
> in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>
> >Errr... no. The proof not statistical. It states that the output of
> >a BBS generator cannot be distibguished from random data by any
> >polynomial-time test by an adversary who cannot decide quadratic
> >residuosity.
>
> That is simply false when a short cycle is used. Unless you
> absolutely prevent such a thing, you cannot assume in your reasoning
> that it has not occurred. On the contrary, if something *might*
> occur, you must assume that it *has* occurred, and reason the
> consequences from there.
Now you're just being deliberately stupid.
I made a clear statement about the nature of the BBS proof. The output
of a BBS generator *cannot* be distinguished from random data in
*polynomial time* by an adversary *unable to decide quadratic
residuosity*.
If a short cycle is used, then adversaries can factor the modulus and
decide quadratic residuosity. The proof *still applies*. Those
adversaries are allowed through by the proof's hypotheses.
> Saying something is "proven" is no advantage unless we need the object
> of the proof. Here the issue is *not* whether BB&S is secure; the
> issue is whether the reduced version -- including short cycles -- is
> secure even if we assume factoring is hard.
Yes, of course it is. The proof still stands. Your assumption might
look a bit iffy, but that doesn't invalidate the proof. It might make
the proof less useful or relevant, but it doesn't make it *wrong*.
> I am happy to agree that reduced BB&S is *almost* always secure, but
> since we can prevent the short-cycle weakness completely, almost
> always is not good enough. And claiming that *must* be secure because
> the math says so is just wrong. Using an insecure system is not
> secure.
But the proof doesn't say that BBS is *secure*. It's says that it's
*as secure as factoring*.
I'm smelling disingenuousness again.
> >Actually, this is wrong. If there's a distinguisher for the BBS,
> >then either it's not polynomial time, or we can solve the QRP in
> >polynomial time. The former would be quite interesting; the latter
> >would be an extremely important result. The proof is not
> >statistical: these are the only two possible outcomes.
>
> Then the proof is wrong. For we *absolutely* *know* that using a
> short cycle can be weak (when we traverse the cycle).
The proof says nothing about *weakness* or *strength*. It *compares*
difficuulties of doing two things: on the one hand, predicting the
output of a BBS generator, and on the other, factoring composite
integers.
> >For example, how is the cycle length related to the size (log_2) of
> >the modulus? Is the relationship polynomial or (sub)exponential? In
> >the latter case, we've not found anything interesting, because we
> >always knew we could distinguish BBS with greater-than-polytime
> >tests; in the former, yes, that's interesting.
>
> One can always question experimental design. But only a scalable
> cipher allows us to run comprehensive experiments in the first place.
> Trying to understand a cipher from experiments on a real-size system
> is generally hopeless, unless there are such massive errors that
> incredibly sparse sampling would detect them. On a tiny cipher we
> expect to have examples of the same sorts of errors, which implies
> that they will be represented with greater probability. That is
> great, because if the problems were represented with their real-size
> probability, we would not even detect them.
This entirely fails to answer the question. One less charitable than
myself might believe it to be a dodge.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cross-platform secure chat
Date: Fri, 11 Aug 2000 10:00:00 GMT
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
>> But anyway, something in java would be great...needs to
> run on a
>> PC/Mac...any links?
On the up and coming front, there's http://silc.pspt.fi. Unfortunatly,
it's developed on Linux and needs gmp and zlib, and is apparantly
curses based. So while it may be runnable under cygwin, you'd probably
need the new Server X not MacOS on the mac front.
Still, it might be worth keeping an eye on as a long term thing. If it
catches on a Windows client will probably spring up. :)
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 11 Aug 2000 10:11:15 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
>
> > Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> >
> > > Interesting verb: "find". AFAICT the issue is not finding short
> > > cycles by searching for them, but finding a short cycle in the "oops"
> > > sense of having inadvertently selected one for use. The practical
> > > impossibility of finding one on purpose is independent of the
> > > theoretical possibility of finding one by accident.
> >
> > Errr... no.
> >
> > If finding X by trying very hard is impractically difficult, then
> > finding X by accidentally tripping over it must be at least as
> > difficult. Otherwise, I have the algorithm for finding X by trying very
> > hard: pick possible values at random and hope to trip over one by
> > accident. This must work unless X can read minds and is deliberately
> > perverse.
>
> Two conterclaims:
>
> 1) The space of short cycles is _larger_ than the space of factors to
> evaluate. This it is not as hard to pick a bad (short) key as it is
> to find the factors of a long cycle. I'm interested in detailed
> refutations of this claim if you are able to mention any.
I'm confused by your terminology. What is a `bad (short) key' here?
What are the `factors of a long cycle'?
> 2) The proposed algorithm fails because "tripping over X" works by
> finding _any_ short X rather than _the_ X selected. This appears
> obvious. Am I being stupid?
In the above, in both cases, `X' is `any element of Q_n which lies on a
short cycle'. Who do you think is doing the selection of `_the_ X'?
-- [mdw]
------------------------------
From: "Jott" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 12:34:59 +0200
> Even if there *were* fundamentally random processes in
> basic physics = which is far from proven - that would be unlikely to
> make building a "true" random number generator possible.
Is there some fundamental definition of randomness that I have missed? And
especially of "true randomness"?
I am only aware of the statistical criteria, and the definitions of
Kolmogorov/Chaitin/Martin-Löf.
Regards
Anders J Johansson
------------------------------
From: "MVJuhl" <[EMAIL PROTECTED]>
Subject: Explain S-boxes please
Date: Fri, 11 Aug 2000 12:45:47 +0200
Could someone please explain where the S-boxes come from ? I mean, how are
the computed.
How would you select your own S-boxes ? What should you be careful of and
what should you have in mind ?
I only know that you substitute any given data with the content of the
S-boxes in a specified order, and that these S-boxes have a inverse for
decrypting. So if you would enlighten me, please do so.
If you know of any links to papers explaining the S-box, please post/send
them.
Thanks
M.V. Juhl
[EMAIL PROTECTED]
------------------------------
** 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
******************************
