daemon@ucbvax.UUCP (08/24/84)
From MCGREW@RUTGERS.ARPA Thu Aug 23 21:24:26 1984
HUMAN-NETS Digest Thursday, 23 Aug 1984 Volume 7 : Issue 48
Today's Topics:
Computer Networks - Telephone Taps on Int'l Calls (2 msgs) &
Crack the Data Encryption Standard?
Information - Re: Low level microwaves and cancer
Chess - Number-Cruncher vs. Humans: 9th Move
----------------------------------------------------------------------
Date: Wed, 22 Aug 84 22:06:39 pdt
From: fair%ucbarpa@Berkeley (Erik E. Fair)
Subject: Re: Telephone Taps on Int'l Calls
The USENET link to Europe goes at 1200 baud from Merrimack, NH to
Amsterdam, Holland. Do you think the NSA will be interested in
huffman coded netnews? Only 16Mbytes per month!
curious,
Erik E. Fair ucbvax!fair fair@ucb-arpa.ARPA
P.S. Among other things, this digest goes over that link...
------------------------------
Date: 23 August 1984 03:56-EDT
From: Jerry E. Pournelle <POURNE @ MIT-MC>
Subject: U.S. may tap lines to halt software smuggling by phone
To: Rutenberg.pa @ XEROX
What did the article SAY? It is rotten journalism. one
official is named; he is quoted as saying that "discussion took
place", not that he thought tapping phones would be any use. he
is also quoted as saying that "it will be a problem to us."
All the rest of the article is speculation, or quuotes
ananymous sources, with no possible verification.
It may be that they're planning to do something about
telephoned software, but you sure can't prove that by anything
in the article, which seems to be pure spec.
------------------------------
Date: Wed, 22 Aug 84 14:33:45 pdt
From: E. Howard Alt <alt%sri-terra@sri-tsc>
Subject: Crack the DES?
I don't remember if the DES and cryptography have been brought
up here before (I was probably asleep or somthing), but I guess
I'd like to comment about the DES, etc.
The effort to develop the DES (Data Encryption Standard) was a
joint effort between the No Such Agency and the Incredible Bowel
Movment. IBM developed a cryptographic scheme that is fairly
changable (key length, internal variables, etc). NSA specified the
various parameters (key length, internal variables, etc).
There are 2 ways to break a cryptographic system. The first
is to discover the key that was used to generate the ciphertext.
The second is to break the system itself so you don't need the
key. The first situation is easy to solve (in theory), all you
have to do is make the key so big that it would take too long
to run through all possible combinations (and protect it... but
that is a different sort of attack). The other method is based on
finding a shortcut through the algorithm so you can find the key.
There are people in the (non government) cryptographic world that
believe one could (today) spend $20 million and build a machine that
could mount a known plaintext attack and discover a key. Note that
the requires the bad guy to have some plaintext-ciphertext pairs. Also
note that a ciphertext only attack is not possible under this machine.
The idea is that we went out and stole some messages that were sent,
and we also have a copy of the encrypted version of the message. We
are assuming that further messages we might want to read are encrypted
under the same key. The way we discover the key is to do an exaustive
search over the 10^17 possible keys. If we could check one key every
microsecond, we could do all of the keys in 10^11 seconds (or 10^6
days). Now, if we build a million of these little machines (10^6),
and each are checking one key, it only takes one day to solve for a
key. If the key were 128 or 256 bits, it would cost $2 X 10^25. In
fact, quantum mechanical and thermodynamic considerations rule out
exhaustive searches on keys of several hundred bits.
The DES is pretty complicated, and I don't feel like looking
in the fips pub and describing it here. In a very general way,
here it is:
There are 3 user supplied part to the DES, the plaintext, the
ciphertext and the key. The plaintext is split up into
64 bit chunks to be applied to the 56 bit key, and out pops
the 64 bit ciphertext (this is encryption if you haven't guessed).
Between the popping in and popping out, the 64 bits gets shifted,
permuted and xored according to various parameters.
The parameters are all variable are set by the NSA for the
standard. According to the cryptographic heavys, the NSA chose
very funny numbers for these parameters. In fact, they say that
one could just about pick the parameters at random, and chances
are very good that they would be better than the ones NSA chose.
These people are pretty much convinced (at least this is what they
say) that NSA didn't pick these parameters to create a trap door
in the DES (although they did believe this at one time).
Oh yes, I should mention something else. I have been mumbling a
lot about NSA, but you chould know (if you don't already) that
NBS (National Bureau of Standards) is the group that is the
official part of the government responsible for DES. I doubt
NSA is officially responsible for anything (other than keeping an
eye on things like this... hi guys).
If some company wanted thier encrypted data to be secure (although
non standard), all they would have to do is change the DES parameters
around a bit, or do a more sophisticated application of DES (there are
several well known methods that make DES much more secure).
Pretty exciting, eh? I always fall asleep in talks about this sort
if thing... I almost fell asleep writing it...
Howard.
------------------------------
Date: 23 August 1984 04:00-EDT
From: Jerry E. Pournelle <POURNE @ MIT-MC>
Subject: Low level microwaves and cancer
To: vortex!lauren @ RAND-UNIX
So that's why the Russians were beaming microwaves at our
Embassy?
------------------------------
Date: Thu Aug 23 14:47:43 1984
From: mclure@sri-prism
To: ailist@sri-ai
Subject: number-cruncher vs. humans: 9th move
The Vote Tally
--------------
Folks, the moves are in and have been tallied.
The winner is: 8 ... cxd4.
A total of 20 moves were cast. Please relay this message to any
friends you have who might be interested in participating. This
includes non-net people.
The Machine Moves
-----------------
Depth Move Time for search Nodes Machine's Est
8 ply cxd4 18 hours, 7 minutes 6.5x10^7 +=
Humans Move # Votes
BR ** -- BQ BK BB -- BR 8 ... cxd4 8 8 ... Qe7 1
** BP ** BB ** BP BP BP 8 ... Qc7 3
BP ** BN BP -- BN -- ** 8 ... Be7 3
** -- ** -- BP -- ** -- 8 ... Qb6 1
-- ** -- WP WP ** -- ** 8 ... e6 1
** -- ** -- ** WN ** -- 8 ... b5 1
WP WP -- ** -- WP WP WP 8 ... d5 1
WR WN WB WQ WR WB WK -- 8 ... Bg4 1
Prestige 8-ply
Note that the machine now thinks it is ahead positionally.
The Game So Far
---------------
1. e4 c5 6. Re1 a6
2. Nf3 d6 7. Bf1 e5
3. Bb5+ Nc6 8. d4 cxd4
4. o-o Bd7 9. cxd4
5. c3 Nf6
Commentary
----------
Goodell@xerox, USCF ?
I think 8 ... Be7 would be a good move now to prepare for castling
to the strong side. My second choice would be g6 followed by Bg7,
but I think it would take too long.
BLee.ES@xerox, USCF ?
8 ... Qb6 a) develops the queen, b) attacks d4 again, c)
discourages movement of white's queen bishop, d) prepares castling
long.
Tli@Usc-Eclb, USCF ?
Unfortunately, the voting will also keep out the inspired moves.
So we get an average game of all playing....
SLOAN@WASHINGTON
8. ... b5
It is worth noting a classical problem here in building a chess
program:
1) The machine was following its book until this move,
2) As White, the machine should enjoy AT LEAST EQUALITY in the
first position following "book" recommendations,
3) However, having switched from "book" evaluation to its own
opening/middle game evaluation, the machine now decides that it
doesn't much like this position after all!
There are several possibilities:
0) Black is superior in the starting position (unlikely!)
1) the book (at least this line) is inferior, and the machine
should discard it (anyone out there think that the Prestige will
do this?)
2) the book is (objectively) correct, but this line does not match
the playing "style" of the machine (i.e., the position is OK, but
the machine doesn't know the correct thematic continuations, and
hence will indeed find the position to be difficult.)
This last possibility is most likely, and is not limited to machine
play. Many human players have the same problem when they memorize
columns and columns of analysis without understanding the REASONS
for the evaluations at the ends of the columns. This leads to
post-mortem conversations of the form "That master isn't so strong;
I had him CRUSHED in the opening...but he SOMEHOW escaped to a dead
drawn ending - he didn't even know that it was theoretically drawn-
he refused my draw offer! - I was so mad at him for that that I
lost my concentration for 1 move and hung a piece."
CMP.WERNER@UTEXAS-20, USCF ?
Qc7 risky, but requiring a non-trivial evaluation by white.
JPERRY@SRI-KL, USCF 1893
I vote that Black's eighth move should be 8... cd
The reason I voted for this move is that Black
can occupy the thematic QB file sooner than white by
taking with the QBP. The move 8...ed seems to be a
blunder because white can try to prepare favorable
complications on the K file with e5. 8... Be7
seems plausible but allows 9. d5 and then Black has
no counter play on an open file. All in all, 8...cd
seems like Black's most logical retort to the bold
8. d4.
tpeters@BBNCCP, USCF ?
I vote for 8. ...Be7. I disagree with the
computer's assessment. Black may have equalized or
white may have a slight advantage, but there is no
reason to think that black is better. The following
is taken from Sizilianisch II by Rolf Schwarz. It
should be viewed as a guideline and source of ideas,
not as infallible gospel.
8.d4:
A. 8. ...Be7 9.d x c5! d x c5 10. Na3 slight advantage to white
[but why not 10. ...b5 equal? TP]
B. 8. ...c x d4 9. c x d4 Bg4 10. d5 Nd4 11. Be3! N x f3+
12. g x f3 Bh5 with slight advantage to white
I picked 8. ...Be7 because white's advantage in B.
seems small but quite clear. He (it?) has pressure
down the c file and the white light-square bishop
can become very active on h3. Moreover, his doubled
pawns are nowhere near as weak as they may seem to
some. At any rate it just doesn't seem reasonable
to open the center by 8. ...c x d4 while the
kingside is underdeveloped.
Schaer.dlos@XEROX, USCF ?
I vote for 8 ... cd
Cannot stand d5. Don't know what I intend to do after 9. cd, but
probably 9 ... Be7 and worry about 10. d5 later.
EWG@Cmu-Cs-Ps1, USCF ?
The comment that the group of humans won't have a
long term strategy is, I think, naieve. It is just
as easy for us to analyze lines of play (e.g.
kingside vs queenside attack, try to trade off and
queen a pawn, etc.) as it is for us to analyze the
single position. If anything it's somewhat easier,
since we think about that anyway. Why not solicit
votes on that level as well and at least report the
judgement (if not allowing it to directly choose the
move at hand, which would be rash). A suggestion
for later in the game, at least. This harkens back
to memories of 10 or so years ago when I was still
reading the chess books, and ran across a comment by
one of the grandmasters (Sam Reshevski, I think?)
who liked to play blitz and always used the style of
spending a significant time thinking about lines of
play at the start of the middle game.
His strategy was to have the lines firmly in
mind for later play. The comment was that his
opponents often got bored waiting for him to reply
at that time and wasted the real time; he could then
play at blitz pace much better as the game
progressed and the opponent struggled for the right
line(s) of play. It also had the surface appearance
of him putting himself deliberately
in time trouble, which wasn't the case.
rod@Maryland, USCF 2115
My rating is USCF 2115. I didn't want to enter until you were
in the middle game but 7....,e5??? is a mistake. Now, either
you allow 9. d5 in which case your queen-knight will be
difficult to develop, or you open the game which is very
dangerous becouse your king is in the middle and it will
take some time to 0-0.
If the machine plays right you will end up with an
isolated pawn or with d5 which will constraint you. Now here are
some of my thoughts:
if 8....,cxd5
9cxd4 Nc6
10 Nc3! (no yet d5 so your bishop-king will not go out)
and now you are almost forced to get an isolated pawn and the
machine is in much better posiiton.
In this position oyu may try
10....Qb6
but after
11 dxe dxe
12 Be3!
you can't play 12....Qxb2 because of 13 Nb5!+-
Let's get back to our initial position.
You may try
8...., Nc6
9 Bg5 Rc8 (no 9....,Be7 10d5 Nb8 and the rook can't go out)
10 Na3 Nc6
11 dxe dxe
12 Nc4 Qc7
13 Bxf6 gxf (no 13...,Bxf6 14Nd6+)
14 Ne3
and you are in a very difficult position in spite of
the pair of bishops. As you can see is very easy to
get out of the book but is much difficult to play
well. It much better to think that you are playing the
game of your life and that you have to play
the best you possible can. Find the best move in
every position, no matter who you are playing with.
Let's go back again. An interesting move although a little
dangerous is the following:
8...., Bc6!?
if 9 d5 then 9....,Bd7 you have lost one move but you have close
the position so it doesnt matter that much. You will then develop
your Q-Knight via a6-c7 and then try b5, a5 and c4. Here comes
the interesting part
9 dxe Nxe4
10 exd Qxd6
and no 10...,Bxd6 11 Qc2!! (no 11Kfd2 0-0! 12Kxe4 Bxe4
13Rxe4 Bxh2+! FORGET the last line.
10...., Bxd6 is good!
11 Ng5 0-0!!
12 Bf4+ Kh8
13 Kf7+ Rxf7
14 Bxf7 Bxh2+!+-
You will end up much more developed than the machine. So I think
she'll play safely 9 d5.
Solicitation
------------
Your move, please?
Replies to Arpanet: mclure@sri-unix or Usenet: sri-unix!mclure.
DO NOT SEND REPLIES TO THE ENTIRE LIST! Just send them to one of
the above addresses.
------------------------------
End of HUMAN-NETS Digest
************************