Cryptography-Digest Digest #954, Volume #8 Sat, 23 Jan 99 11:13:02 EST
Contents:
Re: Metaphysics Of Randomness (R. Knauer)
Re: Metaphysics Of Randomness (R. Knauer)
Re: french law about cryptography
Re: Metaphysics Of Randomness (Boson)
Re: Cayley (Herman Rubin)
Re: Help: Which secret key cipher? ("Trevor Jackson, III")
Re: Metaphysics Of Randomness ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Sat, 23 Jan 1999 12:18:23 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 22 Jan 1999 19:23:10 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>> A TRNG must be capable of generating all possible sequences of a given
>> length, as well as each of them being equiprobable. A filtered pool
>> does not meet the first criterion, even though it meets the second.
>Why? Please defend your claim regarding the first criteria.
As I have mentioned several times recently, the definition of a TRNG
above is the result of the prevailing consensus of opinion from the
discussions we had over a year ago. In a marathon session, with posts
numbering over a thousand, we thrashed out what crypto-grade
randomness for the OTP system means in terms of producing the keypads.
We discussed what appeared to be every practical consideration ever
conceived of, some of which are now being re-discussed in more
metamathematical ways now, and the following definition came out which
was approved by the crypto experts on sci.crypt:
+++++
TRNG: A physical device capable of outputting all possible strings of
a given finite length equiprobably.
+++++
>In a related post I proposed a drastic filtration system. Please quantize the
>vulnerability it creates.
I must have not seen that post. Please repost it so we can analyze it.
BTW, I have been calling for quantitative measures of vulnerability
myself. Apparently they are not easy to come up with.
The only method of attack for a stream cipher that I have heard of
here, assuming the stream cipher is not too weak, is the Bayesian
attack. I know nothing about the Bayesian method other than what
Patrick Juola has posted here, so I am talking outside any level of
credibility myself. But if the Bayesian method is the standard for
attacking strong stream ciphers, I would like to see if it could be
used to characterize the strength of a particular stream cipher
system.
First, you propose your stream cipher system, it is then subjected to
the Bayesian attack, and the results are quantified as a level of
confidence. Of course, I realize that just because your system could
sustain an attack of a given magnitude of effort, does not mean it
could sustain a more concerted attack later. But that is contained in
the measure called a level of confidence, namely that your system can
sustain at least that much of an attack.
Comments anyone?
Bob Knauer
"It is not the function of our government to keep the citizen from
falling into error; it is the function of the citizen to keep the
government from falling into error."
--Justice Robert H. Jackson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Sat, 23 Jan 1999 12:45:12 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 23 Jan 1999 05:15:30 -0600, "R H Braddam"
<[EMAIL PROTECTED]> wrote:
>What characterizes a random number as suitable for
>cryptographic use?
The method of generation, not a particular number itself.
A crypto-grade random number suitable for the OTP system must be
generated by a True Random Number Generator (TRNG) which is a physical
device capable of outputting all possible sequences of a given finite
length equiprobably.
In the sequence lenght it N, then the TRNG must be capable of
generating all 2^N sequences, and it must be able to generate each of
them with the same probability. For purposes of diagnostics, some of
us are willing to treat two pathological sequences, namely 111...1 and
000...0, to be prima facie evidence of a broken TRNG, since each is
the result of common malfunctions of digital hardware devices. But
other than that, no filtering of the output is permitted, or otherwise
you will not meet the criterion of "all possible sequences".
Notice why it is impossible to characterize any particular output of a
TRNG as random - they are ALL random, so there is no characterization
of particular number itself. The number 111...1 is just as random as
10110011 or 11010110 or any other of the 2^N numbers of length N.
>Is there a different set of
>requirements for random numbers used for the OTP and
>(collectively) session, public, or private keys?
If the requirement is for crypto-grade random numbers that can be used
as keypads for the OTP system, then they are the strongest you can
ever hope for - they are completely random.
>I understand that the length of the key for the OTP is
>the same as the message length, and that keys for
>session keys, private keys, and public keys are not. Is
>there any other difference?
Not in principle. Maybe in practice depending on how secure you need
your system to be.
>First, do you use ALL the output of a TRNG?
You select a sequence of a given length that is needed for your
application.
>Does your selection affect the "randomness" of the remaining
>output?
No, it cannot because of the way the TRNG is constructed - as long as
the TRNG is not malfunctioning.
>Second, do you accumulate TRNG output for later use?
Sure, why not? The assumption is that you keep them secret.
You have to "accumulate" them anyway in order to give the OTP keys to
your correspondent over a secure channel.
>What is the actual likelihood of a readable text string
>being output from an OTP?
It depends on the length of the readable text string. There is a thing
called the Unicity Distance which has to do with the probability of an
intelligible text string contained in a cipher with a given key
length. See Schneier's main book.
For example, with 56-bit DES keys, the Unicity Distance is only 8.2
characters. That means that if you discover an intelligible message in
a 56-bit DES cipher and it is over 8.2 characters in length, it is
almost certain to be the intended message. That is why the key for the
OTP must be as long as the plaintext - or longer if you want to pad
the plaintext with random garbage.
BTW, it is standard practice to compress the plaintext before
encryption to save on transmission length of the ciphertext, so that
means that intelligible plaintext won't jump out at you in the
ciphertext.
Bob Knauer
"It is not the function of our government to keep the citizen from
falling into error; it is the function of the citizen to keep the
government from falling into error."
--Justice Robert H. Jackson
------------------------------
From: [EMAIL PROTECTED] ()
Crossposted-To: talk.politics.crypto
Subject: Re: french law about cryptography
Date: 23 Jan 1999 13:34:20 GMT
128bits obviously. sorry about that.
ps. all the previous readers, me included, didnt notice that. They
were probably as surprised as me to really read my post :)
On Thu, 21 Jan 1999 03:03:48 GMT, Chem-R-Us <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>> 19 jan 1999. the french prime minister announced that the gouvernement
>> will allow the key size up to 128bytes.
>>
>> the original text in french:
>> http://www.premier-ministre.gouv.fr/PM/D190199.HTM
>
>Is that *bytes* or *bits*?????
------------------------------
From: Boson <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Sat, 23 Jan 1999 05:59:09 -1000
R. Knauer wrote:
>
> On Fri, 22 Jan 1999 19:23:10 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >> A TRNG must be capable of generating all possible sequences of a given
> >> length, as well as each of them being equiprobable. A filtered pool
> >> does not meet the first criterion, even though it meets the second.
>
> >Why? Please defend your claim regarding the first criteria.
>
> As I have mentioned several times recently, the definition of a TRNG
> above is the result of the prevailing consensus of opinion from the
> discussions we had over a year ago.
Too bad you came up with bullshit.
>In a marathon session, with posts
> numbering over a thousand, we thrashed out what crypto-grade
> randomness for the OTP system means in terms of producing the keypads.
Good, then if a million monkeys pound out a different version of Knuth's,
Seminumerical Algorithms using your terminology, then you would get your
thousand posts to agree with a faulty acronym: TRNG. The articulate
acronym is RNG, the T is for inarticulate potificating windbags.
> We discussed what appeared to be every practical consideration ever
> conceived of, some of which are now being re-discussed in more
> metamathematical ways now, and the following definition came out which
> was approved by the crypto experts on sci.crypt:
Is this a definition or a TRUE definition?
Your over-use of the adjective "true" is a gradeschool error. Next we
will need super-duper random number generators: SDRNG. Then Ultra-Pure
Random Number Generators: UPRNG.
If I gave you two sequences, could you clasify them as coming from a RNG
vs. a TRNG? No. A random number generator produces random sequences of
numbers. If you have to puff yourself up like an insecure simpleton by
adding "true" to it, then you are uselessly posting immense amounts of
crap. Or to use your notation, true crap.
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Cayley
Date: 23 Jan 1999 07:47:49 -0500
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>>[EMAIL PROTECTED] wrote:
>>> The logical next step after quaternions, therefore, had to use a different
>>> name - octaves - when it was developed...by Cayley. An octave has eight
>>> components, one real and seven imaginary.
>>Could you give a literature reference to octaves? Thanks in advance.
>Hmm. My reply from home hasn't showed up on this server.
>Early books on vector algebra or quaternions - such as one by Tait and
>Mortimer - should have such references. Even an old Britannica might.
>I looked up the table in General Algebra by Kurosh.
>But it shouldn't be *too* hard to hunt them down in a math library.
Cayley numbers are simple enough. But why should someone in
cryptography be interested in nonassociative division algebras over
the REAL NUMBERS? There is so much more flexibility over the
rational numbers, even commutative (field extensions) or
associative. The extensions of the Cayley idea to algebras over
other fields are called Cayley-Dickson algebras.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
Date: Sat, 23 Jan 1999 09:30:17 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Help: Which secret key cipher?
Terry Ritter wrote:
> On Fri, 22 Jan 1999 20:31:45 -0500, in <[EMAIL PROTECTED]>,
> in sci.crypt "Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
>
> >Terry Ritter wrote:
> >
> >> [major snip]
> >> We don't remember one-time pads.
> >
> >True. We shred/burn/stir-ashes or whatever. I do not recommend keeping OTP CDs
> >around at all. I'd recommend magnetic media that can be erased after each chunk is
> >used.
>
> This prevents compromise *after* use, but what possible compromise
> *before*? If we transport a huge amount of keying material we
> necessarily keep a lot around for a long while. And the longer we
> keep it, the more chance of compromise there is.
>
> And if we do not somehow "start anew" frequently, any earlier
> surreptitious compromise can bleed us dry.
Stipulated. This consideration applies to all keyed communication systems. Evem
spread
spectrum and changing phones numbers at embassies. But I fail to see how this is
affected by the amount of keying material. Once you've specified the refresh interval
for the keys and the key usage rate to be supported in that interval, you'd supply only
that amount plus some fudge.
If your secure carrier is a diplomatic pouch and you have to xmit 100K worth of keys or
100G of OTP pad every month the operational characteristics are about the same. This
holds true for the security provisions on the key repository at each installation.
Of course asymmetric-key systems do not have any physical key distribution issue, bt
they do have an issue of revocation and certification that symmetric-key systems do not
have (The courier is the analogue for the certificate).
> >[...]
> >I shouldn't have snipped so much because there no reason NOT to encrypt an OTP. A
> >hierarchy of pads is easy to envision. Assume a master key in some heavily guarded
> >repository and message keys masked by the master. This would provide some internal
> >security in the organizations using the system.
>
> But if we talk about encrypting an OTP with a master OTP, then,
> surely, we cannot use the master more than once (or it would not *be*
> an OTP). And if we cannot expand the amount of keying material in
> this way, it is hard to see how we could have a hierarchy.
By the classic definition of an OTP you are correct. I wrote that simplistic proposal
too quickly. However, I think there is a mechanism that may make it possible to povide
secure storage. This is an area in which I'm spending some effort, so my inability to
describe the concept sensibly is an artifact of the state of my analysis (incomplete).
I hope to bring this topic forward in a few days.
------------------------------
Date: Sat, 23 Jan 1999 08:59:09 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
R H Braddam wrote:
> It's frustrating to read posts from people with
> opposing views, when they both make sense. I have some
> questions (below), maybe someone can help me understand
> this.
>
> Patrick Juola wrote in message
> <78ab5s$q1f$[EMAIL PROTECTED]>...
> >In article <[EMAIL PROTECTED]>,
> >Dorina Lanza <[EMAIL PROTECTED]> wrote:
> >>Patrick Juola wrote:
> >>
> >>> In article <[EMAIL PROTECTED]>,
> >>> Dorina Lanza <[EMAIL PROTECTED]> wrote:
> >>> >> > You are making the mistake of trying to
> characterize a number as
> >>> >> > random on the basis of some inherent property,
> like lack of
> >>> >> > correlation or bias or somesuch. But we know
> that a characterization
> >>> >> > like that will not properly characterize
> crypto-grade random numbers.
> >>> >> > Only the characterization of the generation
> process is proper.
> >>> >>
> >>> >> Holy Cow Bob, if I give you a certifiably random
> string (say, with a
> >>> >> gorgeous Allan Deviation plot) and present it to
> you as crypto-grade, and
> >>> >> you give me one of your crypto-grade strings,
> I'll be able to test and
> >>> >> certify that your crypto-grade string is random,
> but you have no way of
> >>> >> knowing that I fibbed to you about the string I
> gave you because there is
> >>> >> no test to distinguish between crypto-grade
> strings and random strings. We
> >>> >> have discovered a distinction without a
> difference!
>
> I guess this identifies the first question. What
> characterizes a random number as suitable for
> cryptographic use? Is there a different set of
> requirements for random numbers used for the OTP and
> (collectively) session, public, or private keys? I
> understand that the length of the key for the OTP is
> the same as the message length, and that keys for
> session keys, private keys, and public keys are not. Is
> there any other difference?
No, there is no other difference. The fundamental concept is that the
key value should be selected (generated) by a method that makes it as
hard as possible for an attacker to guess the key.
> >>> >I think it's worse than this. The statement that
> the output of a filtered
> >>> >random source is non-random is false. If, for
> crypto purposes, we exclude
> >>> >pathological values such as zero from a TRNG we
> still have an equiprobable
> >>> >selection from a pool of possible values. The
> fact that the pool is slightly
> >>> >smaller does not reduce the randomness because the
> selection process is the
> >>> >same. The entropy would be slightly less, but not
> the independence of the
> >>> >samples.
> >>>
> >>> "The entropy would be slightly less" is sufficient
> to make the
> >>> resulting system less than perfectly secure. At
> this point it's
> >>> just Yet Another stream cypher.
>
> This brings up another set of questions.
>
> First, do you use ALL the output of a TRNG? If not,
> how do you select which part of the output to use? Does
> your selection affect the "randomness" of the remaining
> output? If so, how, since each bit output is completely
> independent of all preceding bits?
If you selection depends on the output values of the TRNG the selection
process will impose some predictability (loss of independence) upon the
value produced. The predictability can range from zero to complete.
> Second, do you accumulate TRNG output for later use? Or
> do you just use that portion of output which is
> generated while you are encrypting a message or data? I
> understand that accumulating the key introduces risks,
> but you have to distribute keys anyway.
In theory it does not matter. In practice it depends on the design and
implementation of the system.
> >>False. A filtered pad is not less secure than an
> unfiltered pad. (Now, before we
> >>spin lock on yes/no/yes/no..., please give a summary
> of your reasons for
> >>concluding the filtering weakens an OTP.
> >
> >Simple statistics. If you filter the pad -- and I
> know that (and how)
> >you filter the pad, which is a standard and defensible
> assumption --
> >then I can eliminate potential decryptions.
> >
> >A simple example : if I know that your two possible
> messages are
> >"attack at noon" and "attack at dawn", and I receive a
> cyphertest message
> >reading "attack at noon", I cannot, in fact, infer
> that you intend to
> >attack at noon *OR* at dawn.
> >
>
> How do I determine that those are the only two possible
> messages? I thought that the ciphertext would decipher
> to all possible plaintexts using an OTP.
Exogenous factors such as traffic analysis combined with the real-world
situation may restrict the space of messages so much that only a few
make sense.
> >If I know that you throw away all pads that are all
> zero, and I receive
> >the message above, I know that you do *NOT* intend to
> attack at noon,
> >I therefore know that you will attack at dawn.
> >
> >q.e.d.
> >
> >Unlikely? Yes -- but no more unlikely than the all
> zero pad being
> >generated in the first place.
>
> What is the actual likelihood of a readable text string
> being output from an OTP? Most of the encrypted files
> I've looked at contained very few readable strings of
> even two characters. I would think that a readable
> string output would be more likely to be the result of
> an accidental transmission of plaintext or a zero key
> than it would be the result of a readable string
> encrypting to another readable string.
To answer this precisely you need to provide a definition of "a readable
text string". In terms of letters and spaces in ASCII the odds would be
(65/265)^N where N is the length of the string of text. Of course this
formula treats upper and lower case as similar so it includes WiErD
STRingS liKE thiS One.
> >(n.b. -- if the message I receive reads "attacd at
> nown", and you use
> >a stronger filter of never allowing six successive
> zeros, then I can
> >still unbutton your message. The reason being the pad
> necessary to
> >produce "attack at noon" would be an illegal pad --
> and hence you're
> >still attacking at dawn).
>
> Is this an indication of a "fatal flaw" in the OTP?
> From what I've read in this newsgroup, it appears that
> much of an analyst's work is discovering how plaintext
> is leaked into the ciphertext. With the OTP, any byte
> of zero in the key leaks a plaintext character, and
> that would seem to make analysis possible. Or, as
> described here, maybe easy. On the other hand, if I
> knew that the only two possible messages were "attack
> at noon" and "attack at dawn", I wouldn't bother
> worrying about which the message specified. I'd already
> know enough to prepare for an attack.
>
> >>My reasons for concluding the opposite are contained
> in this
> >>gedanken experiment. [snip]
> >
> >Math generally trumps gedanken experiments. Math
> *plus* examples generally
> >trumps even math. 8-)
> >
> >>
> >>> As to whether or not the loss of entropy is
> significant to make a
> >>> practical difference -- that depends on the degree
> of filtering.
> >>> What you do really buy by doing the filtering? Not
> much --- and
> >>> every time the filter triggers introduces a
> weakness.
> >>
> >>Among other things, a crypto system needs to inhibit
> the identity operation on
> >>plaintext. I.e., the idea of a crypto system that
> includes the possibility that
> >>ciphertext == plaintext has a flaw. Mathematically,
> the system including the
> >>possibility is infinitesimally "stronger" due to the
> larger search space, but
> >>that's not the unit of measure for crypto strength.
>
> See what I mean? Both paragraphs above make sense and
> sound right. There are (simplistically) only four
> possibilities:
> The first is wrong and the second is right.
> The first is right and the second is wrong.
> Both are right.
> Both are wrong.
> However, if both are right, then both are also wrong,
> if they actually contradict each other.
>
> Maybe they don't contradict each other and both are
> right.
I think the latter is true. The discussion above involves two
conclusions: 1. any filtration reduces strength by some amount; and 2.
Filtering out pathological patterns is not harmful to the security of
an OTP.
> I mean, theoretically, a TRNG could start up generating
> a 2^1000 bit sequence of zeros, and that be a
> legitimate output. I don't think that would be very
> useful. Same with a sequence of ones the same length.
> Either could be a valid output, though, if I understand
> what I've read here ( in sci.crypt) correctly. I guess
> valid doesn't have to mean useful. I guess I could just
> throw the TRNG away and get another, after a period of
> monitoring to see if the sequence changes into one more
> useful.
>
> The TRNG could also start up generating a random
> sequence of ones and zeros, which should be more likely
> and definitely would be more useful. Suppose it ran
> long enough to generate 3,000,000 bytes before I needed
> to use it, and they were 1,000,000 bytes of mixed ones
> and zeros, 1,000,000 bytes of zeros, then 1,000,000
> bytes of mixed ones and zeros. Does the fact that I
> didn't use the 3MB of output affect the entropy or
> randomness of the 3,000,001 through 3,000,016 bytes I
> use for a Blowfish session key? I don't think so, but
> not for mathematical reasons. Just because the TRNG
> doesn't know if I use its output or not. My use or lack
> of it has no effect on the output. Every bit will
> continue to be generated completely independently of
> every preceding bit. Does my lack of use of output
> (between messages) constitute an unintentional form of
> filtering?
In theory yes. An attacker knowing your intention to avoid using "bad"
patterns does not have to consider those keys. Thus his job is easier.
However, the amount of reduction in the work he has to do is
infinitesimal.
> >This is simply and utterly false. This is, in fact,
> one of the major
> >weaknesses in the Enigma system. By inhibiting the
> identity operation,
> >one made it very much easier to evaluate and discard
> wrong or unlikely
> >decryptions.
> >
> > -kitten
>
> I've been writing about a type of use practically
> impossible with the OTP. I was ignoring the pad
> distribution problem and the necessity of generating
> pads ahead of time and distributing them before
> communications took place. I think my comments about
> use of the TRNG are still valid, even though they
> require distributing the pad after the message was
> sent. That isn't practical, but it is possible. My use
> of a TRNG would be to generate session, public, and
> private keys. The concerns about filtering are
> applicable there, too.
In theory filtration is "bad". In practice, you run the numbers, and
find that reasonable filtration reduces you key strength by around one
bit. Consider it a form of "weak key" avoidance.
> Thanks in advance for any clarification or corrections
> you provide.
>
> Rick [EMAIL PROTECTED]
>
> Murphy's Law is the only sure thing in the universe.
------------------------------
** 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
******************************
