Cryptography-Digest Digest #879, Volume #8 Sun, 10 Jan 99 23:13:02 EST
Contents:
Re: Key-Active Encryption (Bill Stewart)
Re: Twofish vs DES? (Brad Aisa)
Re: Looking for pseudo-random number generators (Bill Stewart)
Re: Help: a logical difficulty ("james d. hunter")
Re: coNP=NP Made Easier? ("Bryan G. Olson")
Re: coNP=NP Made Easier? ("Bryan G. Olson")
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: Help: a logical difficulty
Shannon's paper (Jayant Shukla)
Re: SCOTT19U ENTROPY (Horst Ossifrage)
Re: Practical True Random Number Generator ("Trevor Jackson, III")
Re: Birthday Attack calculations. (Fred Van Andel)
Re: Key-Active Encryption (daAvatar)
----------------------------------------------------------------------------
From: Bill Stewart <[EMAIL PROTECTED]>
Subject: Re: Key-Active Encryption
Date: Sun, 10 Jan 1999 17:17:32 -0800
The active key is basically equivalent to handing out a much shorter key plus
a program.
This can't increase your security, but it can decrease it a lot in several
ways.
1) If the algorithm is any good, the Bad Guys need exponentially large work
to crack the key even if they know the algorithm. So making your key longer
by adding key bits is more useful than making it longer by adding a program.
2) Either the interpreter system you write the code in is secure
(e.g. a calculator language living in a sandbox that can't harm your real
system),
in which case it's only slower than using straight crypto,
or it's insecure (e.g. 386 assembler that can get outside the sandbox)
in which case anybody who can email you a message can attack your system.
The latter case is obviously Bad. How much do you trust the interpreter?
3) The bigger the key is, the less convenient it is to handle,
so systems with big keys are
- less likely to be used or integrated into other systems
- more likely to be compromised by mistakes in key handling
4) Some governments have rules about using crypto, which aren't generally
enforceable,
but may be practical to enforce against specific targets who are being
watched.
This means that if it's not safe to possess or transmit a normal crypto
program,
it's not safe to send any message using a key-includes-program system.
Also, programs are likely to have easily recognizeable forms,
while keys (at least symmetric keys) are likely to look like random bits,
so it's much easier to hide conventional keys.
daAvatar wrote:
> Hi,
> I thought of an key-active encryption method (in no point related with
> microsoft active-stuff).
> This is simple : The key is not only the key
> but some kind of interpreted code which will encode the data. Of course,
> you can add a layer of secure encryption before and after the key-active
> encryption to provide more security.
> BlowFish(k1,KAE(k2,BlowFish(k3)))
> I would like to have some comments on this.
Lurking....
Bill
------------------------------
From: Brad Aisa <[EMAIL PROTECTED]>
Subject: Re: Twofish vs DES?
Date: Sun, 10 Jan 1999 20:29:16 -0500
[EMAIL PROTECTED] wrote:
> > >NEITHER
> > >if you want something more modern than these weak
> > >old ciphers
>
> Joe the question was a B. S. troll in the first
> place how could anyone take it as a real question.
Oh, for christ's sake, the question was perfectly legitimate -- someone
was asking about the relative merits of two modern asymmetric
cryptographic algorthims. This is exactly the place to ask such a
question. Troll? Sheesh.
--
Brad Aisa
[EMAIL PROTECTED] -- PGP 5.0 public key available at:
http://keys.pgp.com:11371/pks/lookup?op=get&search=0x6F053CE9
"Laissez faire."
------------------------------
From: Bill Stewart <[EMAIL PROTECTED]>
Subject: Re: Looking for pseudo-random number generators
Date: Sun, 10 Jan 1999 17:28:24 -0800
Mike DeTuri wrote:
> Basically what I want to do is create a stream cipher where the key seeds
> three to five PRNGs of different types. Then the program XORs the various
> outputs together to create a keystream which can then be XOR'd with the
> plaintext. I have read Applied Cryptography and saw this same thing
> suggested with LFSRs and implemented in A5. I was just wondering what would
> happen if someone tried the same thing with PRNGs instead of LFSRs.
Don't do it :-)
Once you decide not to, think about why you wanted to do it, and why it was
a Bad Idea to start with....
If you've read Applied Cryptgraphy, go re-read Chapter 16.1 on LCGs,
and look up some of the papers to find out why they're cryptographically
useless.
And go look for Phil Zimmermann's documentation for PGP, where he talks about
Snake Oil (and the algorithms he invented early on), and find the Snake Oil
FAQ.
If you're looking for other kinds of PRNGs, besides LCG and LFSR,
i.e. you want something cryptographically strong,
check out the discussion in 14.11 of Karn, Luby-Rackoff, and MDC.
Lurking...
------------------------------
From: "james d. hunter" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: Sun, 10 Jan 1999 20:17:08 -0500
Reply-To: [EMAIL PROTECTED]
Ken Starks wrote:
>
> [EMAIL PROTECTED] (Dik T. Winter) wrote:
>
> >>
>
> > Depends on the language I would say. In our phonebook you would
follow
> > your friend, sorry. But dictionary order is also a specific
Computer
> > Science term and means first ordering by first element, next by the
> > second element. Even the collating sequence for the elements is
> > unspecified.
>
> I would side with Mike on this. Computer scientists should serve the
> wider community, not dictate to them. If this make their sorting
> algorithms a bit harder, so be it.
True up to the point where the dictums of computer science and
engineering are found to logically serve the public interest
rather than detract from the public interest. Many of the social
customs and conventions we live with were invented by
social engineers, who are known not to always have had
their logical caps on straight.
The main "confusion factor" usually isn't how a particular list
sorts, but how many different names does the same thing
have. The naming and convention translators are where I've
come across the most bugs. They're "in principle" trivial,
just like building a counter that doesn't roll-over at
2000 is "in-principle" trivial.
---
Jim
------------------------------
From: "Bryan G. Olson" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Sun, 10 Jan 1999 16:05:16 -0800
rosi wrote:
> Bryan, Rune, Vladimir:
> If you see pupil to pupil with Ilias on the prvious questions,
> you may try to answer this one (41 or 42) as well. Then I would
> not need to pursue the thread with you any more.
"Any mechanism" is undefined, so 41 and 42 are not stated
well enough to answer.
> For Bryan, if according to your understanding, the NDTM
> you quoted behaves (in terms of halting and output) as described
> in 26, please let me know. That case, your questions, I believe,
> can also be answered.
No. Twenty-six is trivial. A machine that always prints no
and halts satifies 26.
--Bryan
------------------------------
From: "Bryan G. Olson" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Sun, 10 Jan 1999 16:19:27 -0800
rosi wrote:
> Maybe, to some other people when NDTM is real, it is trivial
> that coNP=NP. Once one sees it, it is no longer too difficult. Once one
> is given a concrete construction, it will not be too difficult for one
> to see.
Rosi, at your request I copied the definition of a NDTM
from a text by Lewis and Papadimitriou. It's a four-tuple
of alphabet, states, transitions and start state. The question
of whether a NDTM can accept some language is the question of
whether such a 4-tuple exists.
Is negative four real? Can you show me -4 of something? I
don't mean something theoretical like a debt being negative
money or a step to the left being a negative step to the
right; I mean -4 real things.
The existence of mathematical entities follows from their
definitions, not from our ability to manufacture and exhibit
physical objects.
--Bryan
------------------------------
Date: Sun, 10 Jan 1999 21:34:13 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Sat, 09 Jan 1999 16:07:25 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >> It can, on a fundamental basis. Once you grasp the fundamental
> >> difference between a strong stream cipher and an OTP you will see why
> >> that is the case.
>
> >This is a strong statement. Can you describe the distinction you see
> >between the concepts?
>
> I will try. See below, after I finish commenting on the rest of your
> post.
>
> > As far as I can tell the latter is a subset of the
> >former; a OTP is a strong stream cipher.
>
> Not only is it "strong", it is proveably secure. That makes it more
> than just "strong". The fact that you are capable of deciding formally
> that it is strong makes it strong for certain. That is more than just
> "strong".
>
> >The reverse is completely wrong
> >though, some stream ciphers being totally unrelated to the OTP concept.
>
> All other stream ciphers are fundamentally different from the OTP
> system, because they are not proveably secure.
>
> >You seem to be making the case than an OTP is a distinct entity from all
> >other forms of stream cipher. On what is this distinction based?
>
> Here is my thinking, which developed from those thousands of posts a
> year ago when this discussion was raging in its full-blown glory.
>
> Cinsider two extremes - the OTP and the Book Cipher. The former is
> effected by taking the stream from the output from a TRNG and the
> latter is effected by taking the unadulterated output from a source of
> ordinary text, like a Book. Each stream is XORed with a given
> plaintext. Let's imagine that the plaintext is known by the
> cryptanalyst.
>
> Since the cryptanalyst knows the plaintext, he can XOR it against the
> two ciphertexts to give the two keys. Now here is where the
> fundamental difference between the OTP and the Book Cipher emerges.
> The key K1 from the OTP cipher will be random and the key K2 from the
> Book Cipher will not. K2 will be intelligible text, whereas K1 will
> not. All ciphers which result in unintelligible keys are excluded a
> priori. This narrows down the possibilities such that there can only
> be one intelligible message contained in the ciphertext - the one that
> is intended to be the message.
>
> With the OTP system, there are all possible messages of length N
> "contained" in a given ciphertext, including all possible intelligible
> messages. Each possible message, including the intelligible ones, are
> equiprobable - that is what makes the OTP system proveably secure,
> because the cryptanalyst has no rationale to pick any one particular
> intelligible message over another. "Attack at dawn" is just as likely
> the intended message as "Attack at dusk".
>
> [NB: To make matter worse for the cryptanalyst, you would always
> pre-encrypt your message, making *any* of the possible plaintexts your
> message, even unintelligible ones.]
>
> This is in contrast to any other stream cipher, where only one
> intelligible message is possible, due to the fact that the key was not
> produced by a TRNG. The limited keyspace of any stream not produced by
> a TRNG means that it is exceedingly unlikely (with vanishingly small
> probability as N increases) that any intelligible message other than
> the one you intended as your message would be present in the cipher,
> that is would be an allowed plaintext.
>
> IOW, in the extreme case of a Book Cipher, there is only one
> intelligible message that has a corresponding intelligible key. That
> means that breaking such a cipher is simple in principle - all the
> cryptanalyst has to so is search for intelligbile messages and when
> one comes up, see if the key is also intelligable. If so, then he has
> found your intended message.
>
> In between the OTP on one extreme and the Book Cipher on the other
> extreme there is a grey zone as you go from totally secure with the
> TRNG-based OTP system to totally insecure with the Book Cipher. But
> regardless of how close you get to total security of the OTP system
> with any particular stream cipher, it is still not proveably secure.
>
> Here's the fundamental difference you asked me to discuss: It is
> possible that a particular stream cipher looks extremely secure but
> unless it is *proveably secure*, it is not an OTP cipher. The emphasis
> is on *proveably secure*.
OK, let me try to summarize so far. You have divided the the spectrum of
ciphers into two classes: OTPs and others. OTPs, by your definition always
use TRNG keys, which makes them uncrackable by the principles of information
theory (as opposed to crackable, but ridiculously expensive).
Now, I see a case that is missing from your taxonomy. Let's call it an OTK
(one-time key). It's essentially an OTP with a poorly chosen key. By your
definition the OTK is not an OTP because the key was not generated by a
process that given complete independence to the individual elements (bits
most of the time).
I, on the other hand, define an OTP as any cipher with a use-once property.
Thus the OTK is an OTP under my definition. Under this definition, there are
varying strengths of OTP corresponding to the quality of the key.
Note that your definition excludes some classical ciphers that were attempts
to create OTPs, such as the Russian cipher attacked by the Venona project.
> Based on considerations of people like Greg Chaitin, it is not
> possible to prove the randomness of a number by formal procedures.
> Only a number produced by a TRNG can be proved to be random, and
> therefore suitable for the OTP.
I suspect this is a mis-statement. One cannot prove a number to be random.
There are no intrinsic properties of a random number.
> Therefore no matter how you try, you
> will never be able to prove the total security of a stream cipher
> unless it is the OTP system. There is always that possibility, however
> small it may seem at the time, that a non-OTP stream cipher can be
> broken in principle. And even in practical terms too - since quantum
> computers may one day be able to analyze npn-OTP ciphers and ferret
> out the intended message.
Agreed. Ths only a priori unbreakable cipher is what you are calling an OTP
and I am calling an OTP with 100% entropy density.
> So, as long as you use anything other than an OTP, you are using a
> stream cipher that is not proveably secure, no matter how practically
> secure you may think it is. That is the fundamental difference between
> the two - a difference that goes to the heart of algorithmic
> information theory like Godel's incompleteness theorem and Turing's
> halting problem - IOW, a difference that goes to the heart of number
> theory itself.
Not quite that fundamental. The figure of merit for this property is the
density of the entropy represented in the key material.
------------------------------
From: [EMAIL PROTECTED] ()
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: 11 Jan 99 02:38:04 GMT
Ken Starks ([EMAIL PROTECTED]) wrote:
: I would side with Mike on this. Computer scientists should serve the
: wider community, not dictate to them. If this make their sorting
: algorithms a bit harder, so be it.
Of course, in principle. However, in practice, the required algorithm for
sorting names in a conventional order is this: one converts the name into
a "canonical form", which is a simple character string that can be sorted
simply. Usually, storing people's names twice is an expense that is
difficult to cost-justify from a management perspective.
For computer professionals to impose a different ordering on
alphabetically-ordered lists on people would indeed be arrogant. However,
the resources required to do things properly are imposed upon them by the
nature of the problem, and the decision to make those resources available
is not theirs.
John Savard
------------------------------
From: [EMAIL PROTECTED] (Jayant Shukla)
Subject: Shannon's paper
Date: 11 Jan 1999 01:50:38 GMT
Hi,
I am looking for C.E.Shannon's classic paper "Communication
Theory of Secrecy Systems" in postscript of word format. I lost
the only copy I had and it is not available at my local library.
Couldn't find it on the web either.
regards,
Jayant
------------------------------
From: Horst Ossifrage <[EMAIL PROTECTED]>
Subject: Re: SCOTT19U ENTROPY
Date: Sun, 10 Jan 1999 19:08:02 -1000
Tim Redburn wrote:
> My number is NOT an estimate. If my maths and coding are correct, then
> 9187574 bits is a precise* maximum effective key length. With the
> emphasis on maximum, because other parts of the scott19u algorithm may
> reduce it still further.
>
> - Tim.
>
> *rounded to the nearest whole number.
Thank you, Tim for making this calculation. I am glad you had already
taken into account the decreasing modulus.
H. Ossifrage, San Jose, CA 95140
ps
Hey David, let's do lunch on Telegraph Avenue in Berkeley soon! I know an
Indian place that has some hot curry. You're invited too, Tim. David has
my phone number.
------------------------------
Date: Sun, 10 Jan 1999 22:16:02 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
R. Knauer wrote:
> On Sat, 09 Jan 1999 17:50:23 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >The name for the process you are suggesting be measured is "brownian
> >motion". The problem is that at any given temperature and pressure, it is
> >quite regular at the molecular level.
>
> That's news to me - do you have references for that assertion?
Sorry, I do not have references easily at hand. My statement was motivated by
the assumption of a homogeneous gas medium all at the same temperature. The
distribution of energy among the molecules is going to be fairly narrow. Thus,
given a molecule sensor, you'd have to filter out the long sequences of similar
values and only count the outliers.
> Bob Knauer
>
> "We hold that each man is the best judge of his own interest."
> --John Adams
------------------------------
From: [EMAIL PROTECTED] (Fred Van Andel)
Subject: Re: Birthday Attack calculations.
Date: Mon, 11 Jan 1999 03:43:01 GMT
Reply-To: [EMAIL PROTECTED]
"Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
>Hardly. Throwing away samples wastes the effort invested in creating them. For
>the purpose of the reply I assumed that each sample would be stored after
>comparison with the previously stored samples.
I obviously misunderstood what you were trying to say and I tailored
my comments around that misunderstanding. My apologies for
attempting to put words in your mouth.
However I still stand by my original statement. A birthday attack on
a 256 bit hash would require in excess of 2^128 hashes to be
calculated and stored before the odds of a collision reach 50%.
>You are still using the numbers for exhaustive search. The birthday attack
>numbers are much smaller. As I don't have an arbitrary precision calculator at
>hand I'll have to do some work to generate them accurately. I'll try to generate
>them and post here.
A birthday attack would require > 2^128 calculation while an
exhaustive search would need 2^255. There is a big difference. When
you are dealing with large hashes even a birthday attack becomes
impossible to do. Its the birthday attach that dictates the size of
hash required, not the exhaustive search.
Fred Van Andel
------------------------------
From: daAvatar <[EMAIL PROTECTED]>
Subject: Re: Key-Active Encryption
Date: Sun, 10 Jan 1999 21:18:17 -0500
Reply-To: [EMAIL PROTECTED]
(Bill Stewart wrote)
>
> The active key is basically equivalent to handing out a much shorter key plus
> a program.
> This can't increase your security, but it can decrease it a lot in several
> ways.
>
> 1) If the algorithm is any good, the Bad Guys need exponentially large work
> to crack the key even if they know the algorithm. So making your key longer
> by adding key bits is more useful than making it longer by adding a program.
But isn't that more complex for those Bad Guys to crack the key if they
don't even know the algorithm?
> 2) Either the interpreter system you write the code in is secure
> (e.g. a calculator language living in a sandbox that can't harm your real
> system),
> in which case it's only slower than using straight crypto,
> or it's insecure (e.g. 386 assembler that can get outside the sandbox)
> in which case anybody who can email you a message can attack your system.
> The latter case is obviously Bad. How much do you trust the interpreter?
Not machine code, interpreted code. If you trust a crypto program, why
wouldn't you trust a crypto-interpreter program? The interpreted code is
composed of crypto harmless functions, no interrupts, no calls, only
mathematics, loops and jumps.
>
> 3) The bigger the key is, the less convenient it is to handle,
> so systems with big keys are
> - less likely to be used or integrated into other systems
> - more likely to be compromised by mistakes in key handling
I agree
> 4) Some governments have rules about using crypto, which aren't generally
> enforceable,
> but may be practical to enforce against specific targets who are being
> watched.
> This means that if it's not safe to possess or transmit a normal crypto
> program,
> it's not safe to send any message using a key-includes-program system.
Political question...
> Also, programs are likely to have easily recognizeable forms,
> while keys (at least symmetric keys) are likely to look like random bits,
> so it's much easier to hide conventional keys.
I guess not. In example: 4 bits operations, 2 bits operator, 2 bits
operand.. So your key will look as other keys. "1011011110110101110001"
And if you want to avoid the "binary" style, just leave 2 unused bits
after each 6 used bits.
dA
------------------------------
** 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
******************************
