Cryptography-Digest Digest #821, Volume #8 Thu, 31 Dec 98 21:13:06 EST
Contents:
Re: FAQ: as up to date as it should be? (John Savard)
Re: Session key establishment protocol with symmetric ciphers (Shawn Willden)
Re: All-or-nothing encryption idea? (Shawn Willden)
Re: coNP=NP Made Easier? ([EMAIL PROTECTED])
Re: seeking SSH shell account ([EMAIL PROTECTED])
Re: History of Cryptanalysis (CryptoBook)
Re: History of Cryptanalysis (John Savard)
SSL, Diffie-Hellman-Hill (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: FAQ: as up to date as it should be?
Date: Thu, 31 Dec 1998 23:20:11 GMT
"Joel Noble" <[EMAIL PROTECTED]> wrote, in part:
>...or was I just not looking in the right place for the current version? :)
No, there was in fact a recent thread concerning the need to update
the FAQ somewhat. It is holding up rather well, though.
Some things it might have added to it:
a mention of the current AES process, aimed at creating an Advanced
Encryption Standard which will replace DES;
discussion of the EFF's DES-cracker;
some updating of the bibliography (Koblitz and Schneier are now out in
2nd editions).
Some technical information - on the current best factoring methods,
for example - needs continuous updating.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
Date: Thu, 31 Dec 1998 10:30:42 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Session key establishment protocol with symmetric ciphers
"Michael A. Greenly" wrote:
> This protocol is vulnerable to a man in the middle attack.
I think you're wrong. Although the MITM can always compute
F(R_A, R_B), he cannot compute K_S directly, because he doesn't
know K, even if he chose R_A or R_B. It seems to me that the
best he can hope for is to choose an R_B' to send to Alice or an
R_A' to send to Bob (or both) such that a previously used session
key is reused, though he can't know what that session key is.
However, assuming Alice and Bob are careful to avoid reusing
values (or simply choose them at random from a sufficiently large
space) then the properties I described in my first post should
close out this opportunity as well.
Have I missed something? If so, what?
> >Suppose Alice and Bob share a secret key K and wish to
> >establish a session key to be used for encrypting
> >messages.. Alice generates a random R_A and Bob generates a
> >random R_B. Alice sends R_A to Bob and Bob sends R_B to
> >Alice, then both compute:
> >
> > K_S = E( F(R_A, R_B), K)
> >
> >to get the session key K_S.
Shawn.
------------------------------
Date: Thu, 31 Dec 1998 14:29:46 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: All-or-nothing encryption idea?
Darren New wrote:
> Just thinking on it, would it be reasonable to use the following scheme
> to encrypt data such that the entire file must be decrypted at least
> once before one could check for a valid decryption?
Maybe, I see a possible problem.
> 1) Generate a random stream of data R of the same length as the
> plaintext P.
How is this random data generated? If a predictable PRNG is
used, an attacker could trial-decrypt a few blocks of W and
then
use the recovered bytes of R to predict the remainder of R,
compute
the hash and decrypt the first few blocks of I, looking for
P.
If you use a truly random R, or a secure PRNG, your approach
should
work.
> Of course, this doubles the file size, but a similar technique could be
> used just putting one bit of R for each block (minus one bit) of P.
If you have a secure PRNG, you could do the following, which
would
reduce the resulting file size from 2n to n+c:
1) Seed your secure PRNG with a seed S and generate R as in
the first
version.
2) Xor R with P, yielding I.
3) Hash I, xor S with the hash and append the result to I,
yielding W.
3) Encrypt W, yielding M.
So every bit of I depends on S (via P) and recovery of S
depends on
decrypting all of I.
Note that this is essentially Rivest's all-or-nothing
encryption
technique, though he suggests using a block cipher to
encrypt a
known sequence with a random key to produce R and uses a
simple xor
of the blocks in I as the hash in step 3.
Shawn.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Fri, 01 Jan 1999 00:29:06 GMT
In article <[EMAIL PROTECTED]>,
rosi <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> [only important part selected, hope there is no problem]
> > >
> > > 24. In addition, if I understand correctly, that you mean M is
> > > NOT to be run more than once for it to provide the answer.
> > > NOTE: again here providing the answer is: to halt and to
> > > print YES# on M's output tape when i' (and S) are input to
> > > M.
> >
> > There is no sense in running a det. M "more than once"; it does
> > the same thing every time.
> >
> > There is no point in "running" a N.D. M _at all_... not even once --
> > unless if you use the "guessing" version of NP's definition.
>
> Actually, running a det. M multiple times should never bother us. We are
> interested, for so far the questions asked and answered, in: there IS such an
> M (don't care det. M or magic rock). If a det. M can (ALWAYS) answer in one
> run in finite time, the question is answered positively (i.e. there is such
> a mechanism). If no det. M can answer, no matter how many times it is run,
> the question is answered negatively (only for det. M of course). I can see
> that you are worried about my not distinguishing N.D. M and det. M. In this
> discussion (and for the questions so far) they make no difference. If you can
> give one det. M for the task or a N.D. M (or a piece of magic rock), I will
> accept if you commit to a pecific, well-describe mechanism (as you have agreed
But there _is_ a difference... when you consider TM's with time bounds!
a) Anything that can be done by a ND TM ("done" in the sense I have
described) can also be done by a Det. TM -- at an exponential increase in
cost. To wit, you can make a D TM that tries out systematically all
possible computations of your ND TM (which has nothing to do with _running_
the ND TM "many times"... since then you don't know _which_ computation is
or isn't taking place).
b) A ND TM with a polynomial time bound, treated as in (a), would be
"replaced" by an exponential-time D TM; trivial... and of no help.
> to 26 being your version of the M), one that 'answers' in _finite time_. As
> to 'in finite time', a det. M will do, right? No need to make a distinction.
>
> >
> > The problem is, you are not making a distinction between N.D. and
> > D. machines... or so it seems!
>
> You are right. Not for the questions asked so far.
>
> >
> > > In addition,
> > > 25. You asked me to be more specific about my assumption (think my
> > > guess is correct that's what you want). If you really want a
> > > repetition of the definitions and the assumption, I can include
> > > in the next post. Please let me know.
> > > Actually, all I want is that you allow an assumption to be made,
> > > be it true or false. We will concentrate on the derivation, i.e.
> > > we first try to establish that there is no problem with the steps
> > > going from the assumption to coNP=NP (even though the assumption
> > > might be in error). We will finally deal with the validity of the
> > > assumption. Is this fine?
> >
> > Yes, I asked exactly what the assumption is.
>
> I should not be picky and I am not picking. I have posted the assumption
> and you are asking for it. I wonder if you have read carefully mine which
> has the assumption as an important point. It is not really so important at
> this junction and we can do for now without it. But as I promised, I give it
> again here:
>
> Assumption: Output equivalent automata are equivalent in
> comupting power (or are computationally
> equivalent).
What does "output equivalent" mean for ND TM's, M_1 and M_2? On input
x, M_1 may well have 2^|x| possible computations... each with some output
behavior; likewise for M_2.
> >
> > > Please accept my apologies and let me know if any of the above
> > > of my understanding is incorrect or not accurate. I am, in fact,
> > > particularly concerned with my interpretation of 24. From your previous
> > > posts I seem to see that you may have adopted a specific notion of
> > > NDTM's. That is fine, as long as one does not give trouble. As I have
> >
> > It _is_ the notion of NDTM generally accepted; there is no variability
> ^^^^^^^^^^^^^^^^^^
> Be it so (am referring to _generally_).
> No, not really acceptable if that generally accepted one is 26, the one
> (you said below) just as the "K" you described! I will make the point later;
> and it will be made very soon, I promise. For now, let us not be distracted.
> We do a few questions at a time.
The "K" I described _is_ standard and generally acceptable.
> > > Since I sensed something, I think I'd better make it explicit and
> > > clear so that I do not misunderstand you. To be concrete, I give two
> > > notions and would like you to pick one that you really mean:
> > > 26. M will always halt. If YES# is printed on the output tape on
> > > halt, we know for sure that the integer input to M IS a subset
> > > sum. However, it may print things (trivial included) other than
> > > YES#, and we know nothing. In such a case, the input could very
> > > well be a subset sum, but for the particular run (know you
> > > do not quite like the word 'run', you may give it a verb to
> > > denote the execution/processing), no definite answer is provided.
> > > NOTE: since you seemed to have mentioned 'no multiple run',
> > > I should not have given this. But I have to make sure.
> >
> > In fact I described just such a machine... "K". I don't dislike the term
> ^^^^^^^^^^^^^^^^^^^^^^^^^^
> Wonderful! Beautiful! Fabulous!
>
> > "run"; I pointed out that K, as well as other N.D. machines, have many
> > feasible "runs" on one and the same input.
>
> As I said I seem to have been wrong all the time! The choice of a NDTM
> (I am specific here) has never been settled among the candidates, which
> include 26 and 27!
>
> >
> > > 27. M will halt and print YES# iff the input IS a subset sum of S.
> > > Otherwise, M's execution is UNDEFINED. UNDEFINE is not specific
> > > enough. Some people prefer this to be non-halting. For our
> > > discussion, we can, but not necessarily have to, say that M
> > > halts (in such cases) only after 'exponential time' to avoid
> > > later embarrassment.
> >
> > Again, this is unclear. What do you mean by "M"?? Is it D, or ND?
> > If it is to be ND, then saying "IFF" above is pointless.
> >
>
> Do not really care as long as it works. If you or anyone can give even
> a D (believe you mean det. M) that works this way, I will be happy. I at
> least at this point will not ask you to show me one.
No, "27" is useless for ND TMs. You're saying "iff"... i.e. all
possible runs on a yes-input are to print YES#...?! Think about it!
> We can dwell on 27 later. But for now, as you have picked 26, we will use
> it and forget about 27 for a while. (It appears to be a personal taste thing.
> Yet it is one aspect of the core issue!)
>
> Now I am going to ask the FIRST crucial question. I suggest that you
> think about the question very carefully before answering. You should think
> about my other questions very carefully too, and especially about your
> commitment of picking 26 as your NDTM for answering the SS problem
> (positively). If you have any questions about anything (including the
> assumption), please make them clear before I evaluate the answers you
> provided. Please, be extremely careful.
>
> I want to add. I will go strictly by and with 26, i.e. including taking
> into consideration the fact that the M of 26 (or your "K") may halt and
> print other things (or even nothing) when i' --- a subset sum of S --- is
> the input. But it will always halt within finite time.
>
> Now _"THE"_ question:
>
> Does there exist a mechanism MM (any mechanism) that
> 1. HALTS within a polynomial bound (or in other words: whose complexity
> is bounded by some polynomial function f(n) where n is the input/
> problem size) and
> 2. ANSWERS POSITIVELY (or our version to be specific: prints YES# on
> its output tape on halt)
> when i', a subset sum of S, is given as input? (S as input as well of
> course. No need perhaps to go to such details to make this explicit)
>
> To further avoid misunderstanding, I add the following:
> 1. To answer is to ALWAYS answer. If it sometimes does and sometimes does
> not. or sometimes does wrongly, it is not the M we are looking for.
> 2. NDTM is fine. Any mechanism is fine as long as it behaves as describe
> in 26.
No, not "fine", because it's unclear what you mean by (1). The
definition of NP is in terms of THERE EXISTS, not of ALWAYS. I've
spelled it out in prior postings. Please read it carefully. (I can see you
don't like it, and you are trying to find something "else"... Unfortunately,
it is what it is). K satisfies the definition of "solves SS in ND pol.
time".
It seems (1) allows deterministic computation only... Asking "is there a
Det. pol. time TM J for SS" amounts to: is P = NP? ....
MM need not be my mechanism or your "K". The questions is asking
> if there is ANY such mechanism. If your "K" works, great. If your "K"
> does not work, just as great. That way we can be free from bondage in
> pursuit of such a mechanism.
> If we can find such a mechanism, we have 'achieved a lot' (a what
> victory?) at great cost. :)
> If we can not find such a mechanism, somebody is in real trouble! :)
> 4. Lastly a question, which you are not obliged to answer: Do you believe
> in Turing's Thesis?
> You believe in Church's that is very good. I believe you do in Turing's
> as well. I hope that you see the relevance, or will soon.
What do you mean by Turing's Thesis? How does it differ from Church's?
Happy new year!
Ilias
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.security.ssh,alt.security
Subject: Re: seeking SSH shell account
Date: Thu, 31 Dec 1998 23:58:45 GMT
In article <76bkuc$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gregory G Rose) wrote:
> In article <768uup$7aa$[EMAIL PROTECTED]>,
> James J. Lippard <[EMAIL PROTECTED]> wrote:
> >Most people seem to prefer SecureCRT to F-Secure SSH, in my experience.
>
> I would dispute this gross generalisation. But
> then I'm not "most" people. Are you?
I'm not "most people" myself, but I work with many people in an organization
for which I obtained an F-Secure SSH client license (100 clients). Many of
the people in the company who rely on SSH to do their jobs have tried
SecureCRT, and every person I have heard from who has done so preferred
SecureCRT, without exception. Most cited the user interface and in
particular the terminal setting options for fonts, colors, etc. as the reason
for their preference (similar to Nico Garcia's observation).
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (CryptoBook)
Subject: Re: History of Cryptanalysis
Date: 01 Jan 1999 00:45:23 GMT
In article <76bucf$20n$[EMAIL PROTECTED]>, "Don Chiasson" <[EMAIL PROTECTED]>
writes:
> Another classic (is it still in print?) is Herbert O. Yardley's
>"The American Black Chamber", originallly published in 1931.
>It is about American code breaking from 1913 until 1929 when
>secretary of state Stimson shut down the operation with a
>remark to the effect that "Gentlemen do not read other people's
>mail." It is a good read.
Yardley's classic expose is still in print. The following edition
is carried in stock at CCB:
Yardley, Herbert O.
The American Black Chamber
Aegean Park Press (C-52), 375 pp.
SB: Pub. $28.80, ACA Member $23.05
A related book of interest, which is out of print, but also is in
stock at CCB in new condition is:
Bryden, John
Best-Kept Secret:
Canadian Secret Intelligence in the Second World War
Much has been written about the British and American successes
in cryptanalysis during the Second World War but until this book,
not nearly as much had been known about those of our Canadian
allies. At the start of the war, Canada had virtually no capability.
But before long, with the help of Herbert Yardley of American Black
Chamber notoriety, it had a team breaking codes and ciphers from
Vichy France, Japan, and other countries. Lester Publishing, 1993,
390 pp, POP.
HB: Pub. $28.95, ACA Member $22.95
For ordering infomation, a complete catalog of crypto books, or for
information about membership in the American Cryptogram
Association, please send email to [EMAIL PROTECTED]
Happy New Year!
Gary Rasmussen
Classical Crypto Books
E-Mail: [EMAIL PROTECTED]
Fax: (603) 432-4898
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: History of Cryptanalysis
Date: Fri, 01 Jan 1999 01:04:38 GMT
[EMAIL PROTECTED] (Bruce Schneier) wrote, in part:
>David Kahn, THE CODEBREAKERS.
Yes, that is *the* book, par excellence, for historical information on
ciphers and cryptanalysis up to World War II.
The American Black Chamber came out in a paperback edition from
Ballantine, but it may not be easy to obtain in that inexpensive form
now.
Some libraries may have Fletcher Pratt's "Secret And Urgent".
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: SSL, Diffie-Hellman-Hill
Date: Fri, 01 Jan 1999 01:26:01 GMT
While the RSA and/or Diffie-Hellman patents were still in effect,
people wanting to use the Secure Sockets Layer protocol with the
freeware (and open-source, free software, GNU-type) server program
Apache had to purchase a commercial implementation of SSL.
Now that the RSA patent is nearing expiry, there is a plan to start
work on OpenSSL, but there is some controversy raging about whether
that is a good idea, or whether support should continue to be directed
to improving SSLeay.
This I noticed by visiting a newsgroup that echoes the coderpunks
mailing list...
and there was mention of a new encryption program that somehow uses
matrix multiplication to implement a fast, efficient, public key
method.
Visiting the site didn't tell me if it is in any way similar to my own
failed suggestion, the "Diffie-Hellman-Hill" cipher that was wrecked
as soon as someone reminded me that matrices can be *diagonalized*.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
** 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
******************************
