Cryptography-Digest Digest #860, Volume #8 Thu, 7 Jan 99 14:13:04 EST
Contents:
Re: Help: a logical difficulty ("Trevor Jackson, III")
Re: Graph Isomorphism (Shahrokh Saeednia)
Re: PGP International (Gurripato (x=nospam))
Re: Highly structured info. (XML) and decryption (Mok-Kong Shen)
Re: New Twofish Source Code Available ([EMAIL PROTECTED])
Re: ScramDisk - password size - high ASCII ("jay")
Re: What is left to invent? (Mok-Kong Shen)
Re: What is left to invent? (wtshaw)
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: On the Generation of Pseudo-OTP (R. Knauer)
----------------------------------------------------------------------------
Date: Thu, 07 Jan 1999 10:24:51 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Nicol So wrote:
> Trevor Jackson, III wrote:
>
> > Nicol So wrote:
> >
> > > Of course, because you don't even have enough names for infinite
> > > sequences. (There are uncountably many infinite strings, but only
> > > countably many finite strings that can be used as descriptions). The
> > > infinite binary strings capable of finite representation correspond to the
> > > decidable languages.
> >
> > I find this statement confusing. What does "countably many finite" mean as
> > opposed to "finite". Are there finite numbers that are uncountable???
>
> You misunderstood the sentence. The phrase "countably many finite strings"
> should be parsed as "(countably many) (finite strings)", not "(countably many
> finite) strings". "Finite" in the context means "finite-length".
Ah. Grok.
> > Also, is there are reason why name or description strings have to be finite?
> > Consider the string 3.14159265... (in binary or any other radix), with the
> > name "3.14159265..." (in binary or any other radix).
>
> The reason you want a description to be finite is that you want to be able to
> write it down, store it, communicate it, or do something useful with it. In
> your example, the number pi is a transcendental number, and therefore has a
> non-terminating decimal expansion. Note that finite prefixes of the decimal
> expansion of pi are NOT descriptions of pi. "3.14" is not the value of pi,
> neither is "3.14159265". There are infinitely many real numbers beginning with
> "3.14159265...", so "3.14159265..." is not a description of pi either. (If
> somebody talks about a number beginning with "3.14159265...", he could be
> talking about "3.141592651111...").
Of course. However, using a finite length string as a key imposes a length limit
that a POTENTIALLY infinite length string does not. Thus using a finite string as
the name for an infinite string has some (minor) benefit.
> The number pi is usually defined as "the ratio of the circumference of a circle
> to its diameter". Because this ratio doesn't vary from one circle to another,
> the above description uniquely and unambiguously specifies a real number. The
> fact that the decimal representation of pi begins with "3.14159265..." is just a
> consequence of its definition.
>
> You can also express pi as the sum of an infinite series, but even in such a
> case, the math expression can still be completely specified in a finite number
> of symbols, leaving nothing to intuition or guesswork.
Of course.
> > Why is the set of
> > strings any larger than the set of string names?
>
> The short answer is: Cantor's diagonalization argument.
>
> Let's consider the set of all *infinite* binary strings (the binary alphabet is
> as good as any finite alphabet).
>
> An infinite binary string can be interpreted as encoding a subset of the natural
> numbers. If the i-th bit of the string is 1, the integer i is in the set. With
> this interpretation, different infinite strings encode different subsets of the
> natural numbers. Therefore, the set of all infinite binary strings has the same
> cardinality as the power set of the natural numbers.
>
> On the other hand, a finite binary string can be interpreted as encoding a
> natural number. If we order all finite binary strings in lexicographical
> (dictionary) order, we can interpret the i-th string as encoding the integer i.
> It is easy to see that the set of all finite binary strings has the same
> cardinality as the set of natural numbers.
>
> By Cantor's theorem, the two sets cannot be equipotent (having the same
> cardinality).
Duh. Is is really necessary to use the diagonalization construct to prove that a
the cardinality of the set of FINITE strings is not the same as the cardinality of
the set of INFINITE strings? Hardly. This is simply a problem of definition.
Aleph-null v. Aleph-one.
------------------------------
From: Shahrokh Saeednia <[EMAIL PROTECTED]>
Subject: Re: Graph Isomorphism
Date: Thu, 07 Jan 1999 14:03:28 +0100
Alan Martin wrote:
> Is graph isomorphism still considered to be a hard problem suitable
> for use in cryptography?
Yes it is. The problem is open, but considered to be hard in the general
case. However, for most categories of graphs, isomorphism may be found
in poly time. The only strong category I know consist of "strongly
regular graphs" from which some subcategories with well chosen
parameters would resist "isomorphism-finding algorithms".
Unfortunately, building such graphs are difficult and might be as hard
as finding isomorphism. I think there are softwares that allow to build
such graphs with up to 30-35 vertices, but these are surely not
sufficient for cryptographic applications.
Shahrokh
------------------------------
From: [EMAIL PROTECTED] (Gurripato (x=nospam))
Subject: Re: PGP International
Date: Thu, 07 Jan 1999 16:00:06 GMT
On Tue, 05 Jan 1999 19:39:19 GMT, [EMAIL PROTECTED] (David
Hamilton) wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>"Jason Shea" <[EMAIL PROTECTED]> wrote:
>
>>Hi all,
>>
>>i figure ill probably get kicked in the ass for this question, but, is there
>>a difference between PGP, and PGP international. Nothing in the manuals seem
>>to indicate that it is in anyway different...
If you mean www.pgpi.com (Schumacher�s International PGP page,
not related to www.pgpinternational.com), the only difference is that,
although they come from scanned+OCRed freeware versions, it does have
RSA generation+management capabilities. As for the manual, it is the
same as the US freeware copy; as part of the spanish translation team, I
had to include a note stating that the International copy is
RSA-enabled.
>>Im told by several people that the PGP international version is considerably
>>weaker than the american version.
And I would like them to prove their claims
>These 'several people' that you refer haven't got a clue about the subject
>matter. (ie They are 100% wrong.)
>
I agree.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Highly structured info. (XML) and decryption
Date: Thu, 07 Jan 1999 16:58:23 +0100
Anders W. Tell wrote:
>
> I have a few questions concerning encryption/code breaking of highly
> structured information
> and especially the emerging internet/web standard XML.
>
> This standard have number of properties which make it easier to guess a
> large parts of
> a message plaintext. An example:
>
> <?xml version="1.0" standalone="no" encoding="UTF-8"?>
> <!DOCTYPE IDL SYSTEM "theschema.dtd">
> <ROOT>
> <COMMENT> text text text...</COMMENT>
> <COMMENT> text text text...</COMMENT>
> </ROOT>
>
> Here the message have a well defined start (the ?xml tag),
> a reference the structure of the rest of the message on second row
> (DOCTYPE)
> and all information is enclosed on tags (ROOT and COMMENT)
>
> My first question is are current encyption algoritms and key lengths
> enough to handle this class of highly stuctutured messages when
> their schemas are knowned ?
I guess that you mean that the presence of much structures would
render an algorithm weaker than when applied to normal messages.
I believe that a simple scrambling, e.g. blockwise permutation,
applied before the algorithm suffices to destroy such structures
and thus renders such concerns unnecessary. A good encryption
algorithm shouldn't however be affected by the presence of such
structures in any significant way.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Twofish Source Code Available
Date: Thu, 07 Jan 1999 16:59:22 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> On Thu, 07 Jan 1999 09:38:08 GMT, [EMAIL PROTECTED] (KloroX)
> wrote:
>
> >Just to know what to look for, what is the file name of the archive?
> >File names should not be subjected to export restrictions.
>
> They might be if they are greater than 40 bits in length.
>
> Bob Knauer
Huh? You missed a smiley, right?
--
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "jay" <[EMAIL PROTECTED]>
Subject: Re: ScramDisk - password size - high ASCII
Date: 7 Jan 1999 17:19:53 GMT
[EMAIL PROTECTED] wrote in article
<772btt$mm5$[EMAIL PROTECTED]>...
> AFAIK password can only be composed from A..Z, a..z, 0..9 and a few other
> characters such as: ()[]<>,.{}!"� etc etc - you certainly can't use all
255
> ASCII characters.
>
To clarify possible misunderstanding by the original poster, once this
passphrase is hashed, the resulting key bytes will be in the range 0-255,
so it is not like only a limited subset is being used.
Jay
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Thu, 07 Jan 1999 19:16:47 +0100
wtshaw wrote:
>
> Given your German address, from your prospective, do you think that this
> is set for you, no means of protest?
It is my humble opinion that it might be easier (and more promising)
to find ways to realize sufficient security (despite the restriction)
than to argue with the authority. But other people may think that the
other way round is better.
Note, though, that I assume that in most of the 33 countries there
will not be a general ban of the use of encryption (as is the case
in France).
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: What is left to invent?
Date: Thu, 07 Jan 1999 11:14:56 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
> I guess that good key management schemes would be of significant
> practical value, now that key length for the common people is going
> to be restricted to 56 bits.
>
Given your German address, from your prospective, do you think that this
is set for you, no means of protest?
--
If government can make someone answer a question as they want him to, they can make
him lie, then, punish him for not telling the truth. Such an outrage constitutes
entrapment.
In Base 81: y\7RBRNBN 6*1O+aDR* QBOMR1OhE \*/XtS4+~ ;g/4,Y=Jn 6)IL;OC;H o93bR?bk\
v+/G(J=lE Ni@8L*x)I L(!\+O6;E Hu~u;Ho;R 9lX=g3x*n :Y(Yce;w~ 3l(9kS;NT YfmnPX=ya
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 18:46:15 +0100
Darren New wrote:
>
> > I understand a TRNG to be an IDEAL random number generator, with
> > sequences absolutely unpredicable, in particular without any bias.
> > Such a perfect thing simply can't exist in the real world, though
> > the concept is useful.
>
> Why do you say such a thing? Quantum physics is full of random events
> that have no bias, and indeed no known way of even influencing them to
> have a bias. Radioactive decay springs to mind. Modern devices
> appropriate for a computer card are built with semiconductors
> reverse-biased (i.e., "hooked up backwards") with the leakage caused by
> individual quantum electron events measured to produce the random
> numbers.
>
> Heck, SGI (if I remember who properly) even has a patent on using lava
> lamps to generate random numbers.
How do you KNOW that any particualr realization of a physical process
based on quantum theory is without bias? I am not a physicist but
even the quantum theory itself is yet a theory and not 100% without
disputes, if I don't err.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 18:45:31 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 07 Jan 1999 17:41:02 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>If you think any physical device,
>good or bad, gives you a TRNG, than I have nothing to argue with you.
>I understand a TRNG to be an IDEAL random number generator, with
>sequences absolutely unpredicable, in particular without any bias.
>Such a perfect thing simply can't exist in the real world, though
>the concept is useful.
There is no such thing as a Perfect Circle either, even in mathematics
(since there are non-computable numbers in Mathematics, there are
non-computable numbers on the locus of a Perfect Circle which means
that much of that locus is undefined formally). But that did not
prevent the invention of the wheel.
Even though there is no such thing as an Ideal TRNG, there is one in
the real world which is crypto-grade for purposes of the OTP system.
>Did I say that 'a very good PRNG IS a TRNG'?? I said it approximates
>a TRNG. How good it approximates depends on its quality.
I still disagree with you. There is a *fundamental* difference between
a PRNG and a TRNG.
A PRNG cannot output all of the sequences of a given finite length,
whereas a TRNG does (by definition). Not only that, the limited count
of sequences that a PRNG does output are not necessarily equiprobable,
whereas they are for a TRNG (by definition).
You are using the term PRNG when you really mean Stream Generator. A
PRNG has the distinguishing characteristic that it begins from a
seeded state and is therefore repeatable if restarted from that same
state. A TRNG does not begin from such a state and is therefore not
repeatable.
How a Digit Expansion Generator (DEG), like the BBP Pi algorithm or
any other transcendental constant digit expansion algorithm, fits into
all this is the question I have here.
Does a DEG have periodicity? Are some periodic depending on the
transcendental constant chosen but others not? If so, what are the
selection criteria?
A DEG is certainly repeatable when restarted from the same offset. But
is the sequence it generates completely unpredictable, as long as its
characteristics are kept secret?
>As already said, a TRNG is an ideal.
As already stated I disagree with you in the same sense that a Perfect
Circle is an ideal but that does not stop engineers from coming up
with designs that work exceptionally well in the real world.
Remember that there are fundamental limits on decryption - for example
there is only so much energy in the Universe, and it takes energy to
do decryption. It also takes memory in some cases, and there is only
so much matter in the Universe (although the recent discovery of
"Ghost Matter" makes that number much larger than currently known.)
>You can approximate it with
>a well-designed physical device. But that has more or less bias
>nontheless and is not PERFECT. A RFC on that (I don't have the number
>at hand) treats the topic of dealing with the bias in a practically
>useful way.
RFC 1750. But that is not intended to be the last word on such an
involved topic. Anyway if you are concerned about bias and
correlation, test the output. In fact, part of the specification we
discussed for a TRNG was to test the output in real time to make sure
it is not outputting all 0s or all 1s - known as a Broken TRNG.
>>There are an infinity of transcendental constants to
>> choose from, such as ln(x), etc.
>If you use arbitrary offsets, you would get troubles in most cases
>for practical computation.
As I understand it, the BBP method relies on the ability to compute
the nth digit for terms of the type 1/n. I suppose if you cannot
express a given transcendental constant in terms of a series in 1/n,
then you would have to look for other ways. I thought there were other
ways than just the BBP method used for Pi initially.
>The only exception known to me is Pi, for
>which you can start to obtain the digits at an arbitrary position.
Why is Pi the lone exception? Surely it is not so special that only it
can be digit expanded.
>Of course, if some sequences have been computed to hundreds of
>millions of digits and are available from a server, then that suffices
>for practical purposes, i.e. for any practical offsets.
Apparently you believe it is possible to digit expand transcendental
constants other than Pi.
>The output of a PRNG has a finite period length, even though it may be
>very large. A transcendental constant does not have that, it is not
>periodic.
Is that always true? Someone a year ago claimed that it is not
universally true.
>But whether a finite subsequence of such a constant has
>good statistical qualities could be a matter of concern for practice.
Define "good statistical qualities"?
Remember that you cannot formally prove that a number is random, only
that it is not random. Just because a given number has no bias or
correlation does not mean that it is crypto-grade.
>Yes. But again remember a TRNG is not strictly speaking obtainable
>and that the best physical device only approximates it.
And the best "approximations" are more than adequate for purposes of a
totally secure OTP cryptosystem. The reason is that the TRNG relies on
the intrinsic randomness of some physical process that is known to be
totally random in the crypto sense. Radioactive decay is one such
physical process.
>That is, one uses the leverage of one half of the key space to
>render the brute force time to become a practically infeasible value
>for the analyst. The price the user pays is some higher processing time.
If the key is 56 bits in length, then at most there are 2^56 possible
ciphertexts for a given message. If the message is longer than the
uniticty distance (8.2 ASCII characters), only one human intelligible
message will be be discovered in a brute force attack.
I fail to see how other considerations play any part.
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 17:41:02 +0100
R. Knauer wrote:
>
> On Thu, 07 Jan 1999 11:32:31 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >I am not quite clear about your terminology point. PRNG is to TRNG
> >just like pseudo-OTP is to OTP, in my humble opiniobn.
>
> PRNG you know and TRNG means True Random Number Generator. We
> discussed the concept of a TRNG a year ago and concluded that it was a
> physical device capable of generating all sequences of a given finite
> length with equal probability.
>
> Note that under that definition even the sequence 111...1 is a
> crypto-grade random number. The only redeeming feature is that for
> sequences of any decent length, such a sequence is extremely unlikely
> to be output.
>
> We even discussed what would happen if you tried to filter such
> "non-random" sequences from a TRNG - it would leak the slightest
> amount of information making the OTP not totally secure.
It depends on what you mean. If you think any physical device,
good or bad, gives you a TRNG, than I have nothing to argue with you.
I understand a TRNG to be an IDEAL random number generator, with
sequences absolutely unpredicable, in particular without any bias.
Such a perfect thing simply can't exist in the real world, though
the concept is useful.
>
> >If a PRNG is
> >very good, it approximates a TRNG.
>
> I believe you are fundamentally wrong. A "Very Good PRNG" is not a
> TRNG. They are completely different concepts. A PRNG is based on an
> algorithmic procedure and a TRNG is based on a random physical
> process.
Did I say that 'a very good PRNG IS a TRNG'?? I said it approximates
a TRNG. How good it approximates depends on its quality.
>
> >A side point, I was NOT claiming putting forward new ideas. See
> >the '(Remark: ....)' in the original post. I just wanted to call
> >attention to the utility of pseudo-OTP in light of the 56-bit
> >export restriction.
>
> My purposes in pointing out that this discussion took place a year ago
> is to alert you to that fact in case you want to peruse the archives,
> and to let you know that we came to certain conclusions which you seem
> not to be aware of, at least not in the terms we stated them.
>
> >Almost covered above. An ideal OTP is a theoretical concept, it
> >does not exist in the world. (I mentioned this in the original post.)
>
> I disagree. I believe that a TRNG can be constructed that produces a
> crypto-grade random sequence. We also discussed several precautions
> that must be taken in the construction of such a device. For example,
> electromagnetic shielding is crucial, as any 50 or 60 cycle
> alternating current noise pickup would introduce periodic patterns in
> the output electronics.
As already said, a TRNG is an ideal. You can approximate it with
a well-designed physical device. But that has more or less bias
nontheless and is not PERFECT. A RFC on that (I don't have the number
at hand) treats the topic of dealing with the bias in a practically
useful way.
>
> >I didn't exclude mathematical constants (but to the contrary). But
> >there are enomously more texts than (easily computable) mathematical
> >constants to choose from.
>
> I disagree. There are an infinity of transcendental constants to
> choose from, such as ln(x), etc.
If you use arbitrary offsets, you would get troubles in most cases
for practical computation. The only exception known to me is Pi, for
which you can start to obtain the digits at an arbitrary position.
Of course, if some sequences have been computed to hundreds of
millions of digits and are available from a server, then that suffices
for practical purposes, i.e. for any practical offsets.
> I would like to see this line of thought pursued more. Is the "digit
> expansion" of a transcendental constant the same as a PRNG? For one
> thing, supposedly some such expansions are not periodic. Or is that
> incorrect?
The output of a PRNG has a finite period length, even though it may be
very large. A transcendental constant does not have that, it is not
periodic. But whether a finite subsequence of such a constant has
good statistical qualities could be a matter of concern for practice.
>
> >I think that what is important is how to
> >obtain bit sequences that approximates OTP from all such easily
> >available sources.
>
> There is no formal way to prove that sequences generated by algorithms
> are crypto-grade random numbers suitable for a totally secure OTP. At
> best all you can show that a given sequence is not random for crypto
> purposes.
>
> That's why you must fall back on the concept of the TRNG, which is by
> definition capable of generating crypto-grade random numbers based on
> its underlying construction, e.g., random physical processes.
Yes. But again remember a TRNG is not strictly speaking obtainable
and that the best physical device only approximates it.
>
> >That's why I recently proposed the paradigm 'security through
> >inefficiency' to render brute force infeasible.
>
> Now it's my turn to beg ignorance - I missed that. Can you restate it
> in summary form.
In the original post (outdated now on my server) starting the thread
'On living with the 56-bit key length restriction' I wrote:
Recently I have (as a layman) designed a 56-bit data encrytion
algorithm WEAK3-EX, which has the property that the user can
choose a system configuration parameter such that the algorithm's
initialization time can be arbitrarily long. On the assumption
that brute force is the only viable method of attack, which is
highly likely the case if the user selects to use a sufficiently
large number of rounds of the algorithm, calculation shows that
an initialization time of, say three minutes (which should be
tolerable in extreme cases of necessity), would give rise to an
average analysis time greater than 2*10^11 years for the same
hardware, thus easily catering for the case that the analyst has
an aboundant number of much faster processors. While I don't yet
have any evaluations of my design excepting the very subjective
one of myself, it can be well expected on the other hand that
experts of crypto will fairly soon invent 56-bit algorithms that
are highly secure and perhaps much much better than the humble
design of mine. (In the meantime I have also released WEAK2-EX
and WEAK4-EX which are easily implementable though less efficient
than WEAK3-EX.)
That is, one uses the leverage of one half of the key space to
render the brute force time to become a practically infeasible value
for the analyst. The price the user pays is some higher processing time.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 19:00:14 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 07 Jan 1999 18:46:15 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>How do you KNOW that any particualr realization of a physical process
>based on quantum theory is without bias?
Macroscopic turbulence is not quantum mechanical, so you question does
not apply to the lava lamp.
>I am not a physicist but
>even the quantum theory itself is yet a theory and not 100% without
>disputes, if I don't err.
There are many quantum mechanical processes that are known to be
completely random in the TRNG sense. Radioactive decay is one of them.
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
** 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
******************************
