Cryptography-Digest Digest #883, Volume #8 Mon, 11 Jan 99 13:13:04 EST
Contents:
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
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 (John Briggs)
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: On the Generation of Pseudo-OTP (Yak)
Re: RSA-Modulus decomposition (Robert I. Eachus)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 15:09:48 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 14:35:23 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>But on 10 Jan 17:58:07 you wrote:
You don't have to cite the archive - I know what I said earlier.
> Only a number produced by a TRNG can be proved to be random, and
> therefore suitable for the OTP.
>So how do you prove? By informal (hence in the strict sense
>questionable) means, or what?
I commented on this in an earlier post.
In short, the TRNG as defined above relies on the underlying
randomness of the quantum mechanical process it is based on. If the
TRNG measures radioactive decay intervals, then its randomness depends
on the intrinsic randomness of radioactive decay. If it alternates the
direction of the interval, it effectively removes bias too.
If you challenge the intrinsic randomness of radiactive decay, best
bring your lunch because you will be around for a long time trying to
convince physicists they are wrong (including me since I am a
physicist who happens to have worked on quantum effects based on
radioactive decay - specifically nuclear gamma ray resonance, aka the
Mossbauer Effect).
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 15:55:54 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 14:55:35 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> A crypto-grade random number is one which resists a successful
>> Bayesian Attack. There is no more to it than that, other than to point
>> out that a properly constructed TRNG will generate such numbers.
>Let's see how you PROVE that random numbers obtained from hardware
>noise 'resist Bayesian attacks' independent of the quality of
>that (bias etc.).
I am not going to attempt to prove anything regarding hardware noise,
since I have no idea what the source of the noise is. As I have
already discussed on at least two previous occasions already today, I
would chose readioactive decay for the TRNG, and measure the interval
between decays forward and backward in time to remove any bias due to
the depletion of the isotope with time.
Specifically I would measure one interval and then a second subsequnet
interval. I would compare the times for each interval in one time
direction, say the second interval minus the first. If the second
interval is longer than the first I would emit a 1 and if the opposite
a 0. Then I would measure two more consecutive intervals but do the
comparison in reverse. That way any bias would cancel from one
measurement to the next.
Since the decay of selected radioactive isotopes is completely random
in time, the probability that the TRNG outputs a 1 or a 0 is the same
for all measurements. IOW, there is no reason for the decay process
and the method of measurement to favor one bit output over the other.
That means that all bit sequences are possible and equiprobable. There
are neither any excluded bit sequences nor any sequences that are more
or less probable than any others.
Therefore an OTP cipher based on the output of such a TRNG would be
impervious to a Bayesian Attack, because all sequences of a given
finite length are both possible and equiprobable. There is no
periodicity, bias or correlation present in any of the sequences, nor
any other discernable pattern. There is no way to distinguish one
sequence from any other. There is no way for a Bayesian Attack to take
hold, since no information is being leaked by the TRNG.
Does that convince you that I can PROVE what I said?
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 16:11:51 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 14:59:11 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Is a sequence obtained from hardware noise 'good OTP', 'not so good
>OTP' or 'NOT OTP' according to your definition??
My TRNG would not be based on "hardware noise", so your question is
not relevant as stated. However, if you will allow me to build my TRNG
of choice I can comment.
The output from a TRNG which meets the stated specifications of a
crypto-grade random number generator would indeed be a "good OTP".
That specification is that the TRNG must be capable of outputting all
possible sequences of a given finite length equiprobable. That is
possible in practice with a properly constructed TRNG, such as one I
have discussed earlier based on radioactive decay.
But that is not the topic here. The topic here is whether it is
possible to construct an algorithmic generator which would fulfill the
same specification - such as one based on strong mixing (FIPS 140-1)
of streams generated from arbitrary offsets into digit expansions of
arbitrary transcendental constants - or text streams, like originally
discussed by both you and me at different times.
>And that 'only one possible OTP' does NOT exist in the real world,
>unfortunately!!
Neither does a Perfect Circle, but that doesn't stop people from
driving cars.
I think that you are being way overbearing in beating this poor horse
to death. We all know that there is no such thing as a perfect
anything - including that very statement.
What we want to achieve is a system that is practically secure by
modelling it after a system that is perfectly secure. The tires on
your car are not Perfect Circles, but they are round enough to be
practically circular because they are modeled after the design
specifications of a Perfect Circle.
Can we now drop this exercise in nitpicking and move on to more
fruitful discussions? Thanks.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 17:07:26 +0100
R. Knauer wrote:
>
> If you challenge the intrinsic randomness of radiactive decay, best
> bring your lunch because you will be around for a long time trying to
> convince physicists they are wrong (including me since I am a
> physicist who happens to have worked on quantum effects based on
> radioactive decay - specifically nuclear gamma ray resonance, aka the
> Mossbauer Effect).
I don't have to do that challenge. But every measurement in physics
(not 'gedanken' experiment) has to be done by certain apparatus
and that has errors. The time signal, for instance, is now extremely
accurate but it is nonetheless NOT absolutely accurate. Your
radio-signal driven clock is accurate for ALL practical purposes
but it is NOT perfect.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: On the Generation of Pseudo-OTP
Date: 11 Jan 1999 16:34:46 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (R. Knauer)
writes:
>On Sun, 10 Jan 1999 06:29:39 -1000, Bill <[EMAIL PROTECTED]> wrote:
>
>>Which compression algorithm would you recommend?
>
>The one which reduces the plaintext the most in size.
Which plaintext?
Please specify clearly whether the plaintext is selected before or after
the compression algorithm. And specify how the recipient knows which
decompression algorithm to use.
John Briggs [EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 17:00:53 +0100
R. Knauer wrote:
>
> With the advent of computers, experimental mathematics is a growing
> field of study and comes none too soon on the heels of Godel's
> Theorem, Turing's Halting Problem and Chaitin's Mathematical
> Indeterminancy.
>
> Pretty soon the only way to know if a mathematical proposition is true
> is to test it on a computer.
There has been some debate, if I correctly remember, whether a proof
obtained with a program on a computer is a genuine proof. (I feel
myself too ignorant to take position on one side or the other.)
A fact is that software may have bugs and hardware faults. But
there were also accepted humans proofs that were later found to be
falacious.
> I should have said "in a practical manner as proven by mathematical
> experiment" - such as subjecting a given decorrelation scheme to a
> Bayesian Attack to see if it can withstand it.
>
> Remember that "proveably secure" does not have to be limited to formal
> proof - experimental proof is an acceptable form of proof if conducted
> properly. Otherwise there would be no body of knowledge known as
> physics.
If any assertion derived from experiment, physical or computational,
is in terms of probability, i.e. associated with an appropriately
estimated confidence interval, then everything is o.k. Absolute
assertions are possible if they are deduced from axioms by logical
rules. But then the truth of these depends on the axioms. If I
don't err, nothing sensible can be deduced from an empty set of
axioms.
M. K. Shen
------------------------------
From: Yak <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 08:34:40 -1000
Mok-Kong Shen wrote:
yak yak yak bla yak bla bla bla
XOR
> >> With the OTP system, there are all possible messages of length NXOR
bla yak bla bla yak yak yak yak bl bla bla
XOR
> > >> "contained" in a given ciphertext, including all possible intelligible
XOR
bla yak bla bla bla bla yak yak bla yak yak bl bla bla
XOR
> > >> messages. Each possible message, including the intelligible ones, are
XOR
bla yak bla yak bla bla bla yak yak bla bla yak yak bl bla bla
XOR
> > >> equiprobable - that is what makes the OTP system proveably secure, bla bla yak
>bla yak yak yak bla bla bla yak yak bla bla bla yak yak bl
bla bla
XOR
> > >> because the cryptanalyst has no rationale to pick any one particular
XOR
10101001011101010111100010100100111100100100
XOR
> > >> intelligible message over another. "Attack at dawn" is just as likely
bla bla yak bla yak bla bla bla yak yak bla bla yak yak bl bla bla
MOD 2049
XOR
> > >> the intended message as "Attack at dusk".
> >bla bla yak bla yak bla bla bla yak yak bla bla yak yak bl bla bla
MOD 2049
XOR
> > >If the real message is 'Attack at noon' and one XOR it with two
> > >texts (pseudo-OTP) 'Attack at dawn' and 'Attack at dusk', how
> > >does the analyst proceed?bla bla yak bla yak bla bla bla yak yak bla bla yak yak
>bl bla bla
MOD 204
XOR
> > I did not mean for "Attack at dawn" or "Attack at dusk" to be the
> > pads. I intended for them to be possible plaintexts.bla bla yak bla yak bla bla
>bla yak yak bla bla yak yak bl bla bla
MOD 2049
XOR
> > Please restate your question in light of that.MULTIPLY BY 1278966764329
MOD 12398
> Yes. These are plain texts. Here I use these as given, i.e. applyingxor
bla bla yak bla yak bla bla bla yak yak bla YAK yak yak bl bla bla
XOR
> no techniques of removing correlations, only that I XOR the givenxor
bla bla yak bla yak bla bla bla yak yak bla YAK yak yak bl bla bla
XOR
> plain texts and use the resulting sequence as a 'pseudo-OTP' to
> encrypt the message 'Attack at noon' through an XOR.xor
bla YAK yak bla yak bla bla bla yak yak bla YAK yak yak bl bla bla
XOR
> >
> > >Referring to your phrase 'Only a number produced by a TRNG can bexor
bla bla yak bla yak bla YAK bla yak yak bla YAK yak yak bl bla bla
XOR
> > >proved to be random', could you give the conrete proof algorithm??ADD
>13297866717324
MOD78213390873403
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement:
> > I should rephrase that statement: MOD 76324897676
= POTP
------------------------------
From: [EMAIL PROTECTED] (Robert I. Eachus)
Crossposted-To:
alt.privacy,alt.security,alt.security.pgp,comp.security.pgp.discuss,talk.politics.crypto
Subject: Re: RSA-Modulus decomposition
Date: 11 Jan 1999 16:29:19 GMT
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Robert I.
Eachus) writes:
> But I don't know of an easy way to find the solutions, even given
> p and q. (Well for small n, it isn't too difficult. First find
> the two prime factors of n ;-) then count two registers up by p
> and q respectively, only adding to the smaller register until the
> registers differ by one.)
I don't know if anyone is interested in this, but I thought a bit
about this on the way home Friday... The two solutions must be (1,0)
and (0,1) in Chinese Remainder notation. There are four numbers such
that m^2 = m mod n, where n is the product of two primes. (0,0) = 0
and (1,1) = 1 are the trivial solutions. So you can find these
solutions by applying the Extended Euclidian Algorithm to p and q.
--
Robert I. Eachus
with Standard_Disclaimer;
use Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 17:02:31 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 16:35:46 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>So please give a FORMAL and rigorous proof of the security! Does
>'arbitrary limit of precision' mean an approximation or perfectness??
Is there an echo in here? Every time I open one of your posts you are
asking the same question.
I will omit a response this time to let you get caught up on the
several earlier posts where I have discussed this about as
exhaustively as I am able to do right now (although I do have more to
discuss later when we get past these hurdles).
>Practical security is not identical to theoretical security. Practical
>security is relative to the risk and the cost of securing a certain
>level of security.
By practical security in the context of an OTP cryptosystem, I mean
that a successful Bayesian Attack is not possible, even if there is
the slightest leakage of information due to a TRNG that is not
perfect.
>Can you give good literature references to 'Bayesian Attacks'?
No. I am not a cryptanalyst. I am only someone who reads the posts
submitted here and makes judgements based on the expert opinions
presented. You will have to ask the experts here to provide you with
that information.
I believe someone did do so a year ago, but I can find nothing in my
bookmarks or text archives regarding it. But that person, Patrick, a
bona fide expert cryptographer who lent considerable insight to these
discussions a year ago, is either not on here at the moment, or is
lurking - or has not opening this thread.
Terms like "pseudo-OTP" in the subject header do have a strong
tendency to scare off experts, because they assume that the person who
would use such a term is a complete neophyte. That's why it is
important to learn the proper use of terms lest you end up talking to
just yourself in the long run.
>Are these 'systematically' applicable to ALL ciphers, even without
>knowing the underlying algorithms?
I do not know - I only know that the Bayesian Attack is applicable to
stream ciphers because it looks for probabilistic anomolies in the
ciphertexts - such as would be caused by using a poorly constructed
stream cipher like a straight book cipher.
The OTP relies on a pad created from a generator that is capable of
outputting all possible sequences of a given finite length
equiprobably. If the pad is not so constructed, the sequneces it
outputs do not follow the expected probabilites of occurance. That
makes the cipher based on it susceptible to a probablistic attack,
like the Bayesian Attack.
Bayes was a mathematician who was responsible for the foundations of
probability theory as we have it today, so the use of his name is not
all that esoteric. The Bayesian Attack looks for probabilistic
anomolies that are unexpected if the pads are constructed from a TRNG
(and only used one time, of course).
>Every method in practice is non-perfect from the very beginning.
>But you can remove correlation through permutation, substitution,
>etc. I listed in my orignal post some of what I believe (not sure!)
>to be promising in reducing (not entirely remove) the correlations.
Listing is not enough. You either have to prove your assertions
yourself or rely on experts to prove them for you. The roadway of
cryptography is littered with the corpses of unproved assertions of
one kind or the other - as well as assertions that people thought were
proven at one time.
I personally have it easy - not being an expert means I do not have to
prove anything myself. I do, however, have to rely on the opinions of
experts, which is not all that demanding since there are so many
experts in the field of crypto who are ready and willing to offer an
opinion here. It's just a matter of flushing them out.
>Taking every second or third character of a text also reduces the
>correlations.
That has not been proven. In fact, one expert here claimed that such a
procedure was worthless. Nobody rebutted him, so his expert opinion
formed a consensus that remains unchallenged even to today. If you
must rely on the expert opinions of others, as I must, then the best
you can hope for is a consensus based on prevailing opinion.
>Let a bunch of characters be taken from a large number
>of texts and put these into a buffer and shuffle it. The result
>can be expected to have less correlations than in the original texts.
That would depend crucially on the algorithm you use to do the
shuffling. Remember that every algorithm, no matter what it is,
consists of a finite state machine calculation, which necessarily
introduces correlations into the bitstream. If I can calculate one bit
and the then next, there is necessarily a correlation between those
two bits. If that correlation stretches to all bits, then you have
major trouble.
>Note that every practical method can only give an approximation.
>But if you appropriately 'concatenate' a number of such approximations,
>then the resulting sequence will very likely have a better quality
>than each of the methods applied alone.
As FIPS 140-1 states, such strong mixing is supposed to remove
correlations from bitstreams. But I have never seen an expert here say
he agrees with that, and I have seen one expert say the contrary. Thus
prevailing opinion is against such strong mixing as a means of
removing correlations, even for a practical stream cipher that could
presumably withstand a Bayesian Attack.
But such pessimism doesn't mean we should not continue to inquire.
After all, that lone expert could have been completely wrong, or his
comments could have been limited to a specific case of mixing which is
inherently weak. In fact, that is exactly what it was - he was
commenting on the procedure outlined in Schneier's main book, where
two bitstreams were mixed according to a simple scheme.
Since no one came in to the discussion to propose better mixing
schemes, I was forced to conclude, tentatively at the least, that all
mixing schemes are not suitable. Yet I do not believe that is true in
a practical sense - but I am not capable of proving that.
I am like you - I would expect some form of strong mixing based on
non-linear algorithms to remove correlations from bitstreams, even
ones constructed from the least significant bits of text streams. But
I am not in a position to prove it, or to appeal to prevailing opinion
of the experts here on sci.crypt (regardless of other expert opinions
such specs as FIPS 140-1).
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 17:18:13 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 17:00:53 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>There has been some debate, if I correctly remember, whether a proof
>obtained with a program on a computer is a genuine proof. (I feel
>myself too ignorant to take position on one side or the other.)
>A fact is that software may have bugs and hardware faults. But
>there were also accepted humans proofs that were later found to be
>falacious.
If such faults prevent us from proving things experimentally, we might
as well close shop.
>If any assertion derived from experiment, physical or computational,
>is in terms of probability, i.e. associated with an appropriately
>estimated confidence interval, then everything is o.k. Absolute
>assertions are possible if they are deduced from axioms by logical
>rules.
Even that has been challenged on several fronts. In terms of axiomatic
formal systems, you run into Godel's Theorem. In terms of computation,
you run into Turing's Halting problem. And in terms of elementary
number theory, you run into Chaitin's Matematical Indeterminancy.
>But then the truth of these depends on the axioms. If I
>don't err, nothing sensible can be deduced from an empty set of
>axioms.
Other than the set is empty.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 17:19:30 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 17:07:26 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>I don't have to do that challenge. But every measurement in physics
>(not 'gedanken' experiment) has to be done by certain apparatus
>and that has errors. The time signal, for instance, is now extremely
>accurate but it is nonetheless NOT absolutely accurate. Your
>radio-signal driven clock is accurate for ALL practical purposes
>but it is NOT perfect.
I know, I know. Nothing in the real world is perfect, not even this
statement.
But so what?
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 17:49:12 +0100
R. Knauer wrote:
>
> My TRNG would not be based on "hardware noise", so your question is
> not relevant as stated. However, if you will allow me to build my TRNG
> of choice I can comment.
I remember you mentioned Nobel prize. If you could obtain a perfect
RNG, I am sure you could get a sizable prize from the computing
community, though not awarded by the Nobel committe.
>
> The output from a TRNG which meets the stated specifications of a
> crypto-grade random number generator would indeed be a "good OTP".
> That specification is that the TRNG must be capable of outputting all
> possible sequences of a given finite length equiprobable. That is
> possible in practice with a properly constructed TRNG, such as one I
> have discussed earlier based on radioactive decay.
>
> But that is not the topic here. The topic here is whether it is
> possible to construct an algorithmic generator which would fulfill the
> same specification - such as one based on strong mixing (FIPS 140-1)
> of streams generated from arbitrary offsets into digit expansions of
> arbitrary transcendental constants - or text streams, like originally
> discussed by both you and me at different times.
If there are concrete specifications, say in terms of the magnitude
of auto-correlations, or there are specific test algorithms given,
then one can test a given sequence, whether from hardware or software,
to see whether the specification is met. If the user is satisfied
with what is prescriben in the specification, then everything is
o.k. But ssuch a test can at best deliver a result saying that it
meets certain confidence level. You get a statistical assertion of the
quality of the sequence, never an absolute assertion. Of course,
that is o.k. for practical purposes.
>
> >And that 'only one possible OTP' does NOT exist in the real world,
> >unfortunately!!
>
> Neither does a Perfect Circle, but that doesn't stop people from
> driving cars.
>
> I think that you are being way overbearing in beating this poor horse
> to death. We all know that there is no such thing as a perfect
> anything - including that very statement.
Well, let's forget an ideal OTP in the present thread and save much
unnecessary debates!
>
> What we want to achieve is a system that is practically secure by
> modelling it after a system that is perfectly secure. The tires on
> your car are not Perfect Circles, but they are round enough to be
> practically circular because they are modeled after the design
> specifications of a Perfect Circle.
>
> Can we now drop this exercise in nitpicking and move on to more
> fruitful discussions? Thanks.
That is exactly what I was desperately trying to achieve. See above.
M. K. Shen
------------------------------
** 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
******************************
